在GPU图形加速技术之前，如何提高复杂场景的绘制效率的关键环节就是尽可能减少构建场景所需的三角形数据（靳海亮，2010）。除了单纯的对复杂模型进行简化外，细节层次（Level Of Detail，LOD）技术是目前最常用的减少场景三角形数据的方法（殷小静，2012）（Losasso F，2004）。该技术依据人眼观察近处物体清晰观察远处物体模糊的视觉特性，为同一物体或同一物体的不同部分创建多个不同细节层次的模型，依据观察者距离模型的远近选择粗略或精细模型进行显示。用LOD技术构建地形场景时，在保证地形显示效果变化不大的前提下，能有效降低数据冗余，减少场景绘制所需的三角形数目。

1.地形LOD模型分类

依据构建原理不同，通常可以将地形LOD模型分为两大类：离散层次细节模型（Discrete LOD，DLOD）和连续层次细节模型（Continuous LOD，CLOD）。离散LOD模型为同一个物体预先构建多个不同分辨率的细节模型，每个细节模型内部的精细程度相同，依据距离观察者的远近选择合适的细节层次模型进行绘制。由于不同LOD层次模型的几何拓扑结构不同，不同LOD层次模型进行切换时会在视觉上会引起明显的跳跃或突变现象（李志勇，2007）。

连续LOD模型在构建场景时，不需要预先建立地形的细节层次结构，而是在绘制过程中通过相应的绘制算法来实时动态计算场景各个区域所需的分辨率层次。离视点近的且地形起伏较大的部分使用精细的模型，离视点远的且地形平坦的地方使用粗糙的模型，然后自动生成与观察者位置相关的细节层次来完成场景的绘制（图10-16）。连续LOD模型方法可以有效减少场景漫游过程的突变现象，然而由于在同一场景中需要不同分辨率的地块模型来拼接整个地形场景，这些地块之间将会出现明显的裂缝（王晓军，2009）。相对于解决离散LOD的突变问题，裂缝的消除更为容易。

图10-16　地形的连续LOD结构及实例

2.连续LOD模型生成

连续LOD模型的实时生成算法与地形表达的数据组织结构密切相关。DEM的数据组织形式主要有规则格网（Regular Square Grid，RSG）和不规则三角网（TriangulatedIrregular Network，TIN）两种形式（王晓军，2009）。对于规则格网DEM，为了实时构建连续LOD模型，常采用基于四叉树或二叉树的地形细分剖分方法。而对于不规则三角网TIN，由于其几何结构的不规则性，细化剖分相对复杂。比较常用的方法类似于一般三维几何对象的三角网简化算法，通过边折叠、顶点删除、边删除、三角形删除等一系列几何简化操作来实现，比较经典的有Hoppe提出的渐进格网（Progressive Meshs，PM）算法及改进后的视点相关的渐进格网（View-Dependent Progressive Meshes，VDPM）算法。由于大规模海量地形常采用规则格网形式，因此这里对基于TIN的连续LOD生成不做过多讨论。

（1）基于四叉树的连续LOD生成

该算法思想是：首先把整个地形作为一个矩形地形块，然后根据视点离地形块的距离和地形块本身起伏信息确定当前地形块是否满足渲染精度。若不满足，则将当前地形块化分成四块，再依次判断它们是否满足精度；若满足，则将这块地形块三角化并渲染到屏幕上。按上述步骤循环迭代，直至所得的地形块达到所要求的精度。具体细化分割过程如图10-17所示。

（2）基于二叉树的连续LOD生成

图10-17　基于四叉树的CLOD细分

三角形二叉树与四叉树类似，只是将矩形的四叉分割换成了三角形的二叉分割。比较典型的就是地形实时优化自适应格网算法，即ROAM算法。算法基于二叉树结构，其每一个区块都是一个简单的二等边正三角形。整个地形块最初由两个直角等腰三角形表示，然后从三角形的顶点到其斜边的中点对其进行分解，可生成两个新的二等边正三角形。递归地重复对其子三角形进行分割直到达到所希望的细节层次为止（图10-18）。这是一个自顶而下的剖分过程，该方式能够保证相邻两个三角形的层数不超过1，从而较容易避免裂缝和T型连接的产生。

图10-18　基于二叉树的CLOD细分

二叉树结构构建连续LOD的优点在于每个二叉树节点刚好是一个网格渲染单元，绘制阶段可以更快地构建出地形场景。但是二叉树结构的剖分层次较深，构建二叉树场景的处理时间较长，细分过程还会出现增加相同顶点的情况，因此绘制时会产生冗余三角形。使用四叉树构建连续LOD模型则比二叉树结构的剖分层次少，模型构建时间相对较少。

3.地形误差计算

在连续LOD实时生成过程中，网格是否需要细分的条件往往受制于地形表达的精度。当同一地块采用不同LOD层次的格网来进行表达时，存在精度上的差异，细节层次水平越高，表达精度越高；反之越低。由高细节水平层次采样得到低细节层次水平的过程中，顶点个数的减少会带来地形表达精度的损失，即地形表达误差。由于此时的地形表达误差仅仅考虑了顶点减少带来的地表几何形态的变化，没有考虑观察角度的影响，因此该误差值是一个固定值，可称之为静态误差（赵庆，2009）。比如利用四叉树建立的金字塔结构，两个相邻分辨率层次之间损失的顶点总是精细层的中点，其损失的高度是一个固定的值。静态误差是计算可视化情况下动态综合误差的重要组成部分，表达了删除顶点偏离平均地形表面的偏离程度，可以通过考察被删除顶点与周围邻接点的关系来计算（图10-19（a））。

图10-19　静态误差计算

设当前格网点为P，当删除P点获得较低细节层次水平的格网时，P点删除导致的静态误差可以通过P点的实际高程值与分布其周围的八个格网点所形成的四个断面来估算（上下、左右、左上右下、右上左下）。例如在GC剖面上（图10-19（b）），设HP为P点的实际地面高程，通过G、C可计算P点在该剖面上的估算高程H′P为：

H′P与HP的差dGC反映了P点在GC剖面方向上的偏离程度：

(www.daowen.com)

由于地形表面的各向异性，一般在四个剖面上下BF、左右HD、左上右下AE、右上左下GC分别计算出P的四个偏差，并取其平均值为P的静态误差，计算公式如下：

上述静态误差是以铅垂线方向上的高差变化来衡量地形几何形态的精度损失，有时候采用P点到拟合面的垂直距离来衡量将更好地描述地形几何精度的损失情况。

在三维真实感地形可视化系统中，当从不同距离和方位进行观察地形静态误差时，这个误差值投影到显示屏幕上的大小往往是变化的，因此我们把顾及视点因素的静态误差在屏幕上的投影误差称之为动态误差。动态误差常常用像素作为单位来衡量大小，若对应的投影像素数较小，人眼就不容易察觉这个视觉上的变化；若投影像素数较大时，就会引起人眼的注意。因此，在地形动态创建时需要确定一个投影误差计算公式，并提供一个可被人眼察觉的动态误差阈值，当误差值小于阈值时表明它不会被人眼察觉，可不作处理，反之，则需要强制剖分当前地形节点。

通常动态误差的计算涉及的因素包括：场景节点到观察者的距离与方位、场景节点的边长、场景节点的静态误差值、场景单位长度到屏幕像素投影的比值、投影视口宽高比等。动态误差计算公式的优劣和选择的屏幕像素阈值大小，直接影响地形场景的绘制效果及其绘制帧数，因此它是评价一个地形LOD算法好坏的关键。

4.裂缝处理

在连续LOD地形绘制时，由于不同地块采用不同分辨率细节层次模型绘制，这些不同分辨率的地块之间通常会产生裂缝。如图10-20所示，在两个不同分辨率的地形块的拼接边缘处，高分辨率地块的中点处使用该顶点的真实高度值，而低分辨率地块上没有该顶点高度数据，需要由两边界顶点插值计算获得，这样将导致同一地形位置出现两个高度值，从而产生地形裂缝。

图10-20　地形裂缝的产生

裂缝消除是LOD技术中要解决的关键问题之一，常用的解决方法有：

（1）增/删顶点法

在低分辨率边界中点增加一个顶点，其高程值为该位置高分辨率地块中对应的实际高程值。这样就避免了同一顶点位置存在两个高程值而产生的裂缝，然而由于增加了一个本来不属于低分辨率层次的顶点，会使原有的多分辨率层次结构变的复杂而难以维护，因此该方法使用较少（赵庆，2009）。为了避免对原有的地形多分辨率结构造成影响，删除高分辨率地块边界的中间顶点来消除裂缝更为常用。该法不需要将该中间顶点的高度数据从高分辨率节点的存储结构上删掉，只是在绘制过程中跳过不去连接该点，也就是所说的“跳点法”。该处理方式较简便，需要绘制的三角形个数较少，不仅提高了绘制效率，且可避免T型连接。当然，在地块接边处会带来一定的地形表达精度损失。

跳点法处理的关键步骤是在高细节层次边界忽略中间顶点后的该区域的三角形结构重构，图10-21给出了三角形结构重构的两种方式：①重构区域的边都连接在边界上的同一个顶点上；②重构区域的边分别连接在边界上的两个顶点上。前者在边界处会产生狭长的三角形，后者则减少了狭长三角形出现的概率。

（2）强制剖分法

图10-21　跳点后三角形的重构

增加顶点或跳点法适用于两个地块节点的分辨率等级相差不超过1的情况，当两地块节点分辨率等级相差超过1时，通常的做法是对低分辨率的节点进行强制剖分，使其分辨率等级逐渐递增，直到整个地形中间节点的分辨率等级差均不超过1，这样就可以使用上述的增/删顶点的方法来消除裂缝。基于二叉树结构的ROAM算法（Duchaineau，1997）和受限四叉树算法都是使用强制剖分的方法来控制相邻节点的分辨率等级差。强制剖分显然也会改变当前场景的分辨率结构，但是由于改变后的结构具有一定的规律性，因此整个场景的节点数据仍然容易管理。强制剖分存在的关键问题是计算量大，需要时刻检查边界，效率偏低。

在基于二叉树结构的地形格网细分过程中，分割和合并操作算子是在一个类似“钻石”结构的单元上进行的。如图10-22所示，对于三角形T，其直角边连接的是左右三角形TL、TR，其斜边对应的是基三角形TB。当要对三角形T进行细分时，需要其对应的基三角形TB与T处于同一个分辨率层次；合并时，要保证被合并的四个三角形处于同一分辨率，且两两共享直角边。因此，当需要对三角形T进行分割时，需要首先创建一个“钻石”结构，也就是需要把TB分割，而分割TB也需要首先创建一个“钻石”结构，即需要把TC分割，依次类推，直到TD和TE组成的“钻石”结构。这种约束剖分使得地形不同精度的格网之间的过渡是逐渐变化的，直接避免了裂缝的产生。

图10-22　基于二叉树结构的强制剖分

（3）“裙带”法

裙带法又叫垂直边缘法，主要思想就是在各节点边界周围生成垂直边缘填充裂缝，垂直边缘的顶部为节点的边界值连成的折线，其底部为节点块最高分辨率模型时在该边界处的最小值，这样可以确保在该边界的所有边界格网点肯定在该底部之上。即在每个数据块的四周添加垂直的连续三角形条带（图10-23），取条带的高度为该块对应边界误差值的最大值，从而在视觉上消除裂缝。该方法简单有效，但是不能保证模型表面的几何连续性。

图10-23　垂直悬挂的“裙带”