地形细节分层技术（，

1.技术的基本思想与应用举例

现代的图形工作站可以在与用户交互的过程中瞬时显示上万个封闭的或带纹理的多边形。但是，许多应用系统所包含的几何图形的复杂性还是远远超出了普通图形显示硬件的能力。这个问题在处理复杂的多边形表面模型时尤为明显，如数字高层模型和虚拟可视化。为了使计算机在处理复杂物体表面模型时还可以保持实时的显示速度，人们提出了LOD（Level of Detail）技术。它使用多分辨率模型和近似多边形表面的方法使物体在离视点不同距离时产生不同精度的表面模型。可以在多维动态地图中根据人眼观察现实世界的基本规律和计算机的能力采用不同的空间分辨率和时间分辨率来表达同一地理实体，既可以提高实时显示速度又可以模拟“越近看得越清”的视觉规律。

1）基本思想

LOD技术的基本思想是：同一个物体与眼睛距离不同，所看到的该物体的详细程度也不同。根据这一视觉规律，事先为同一物体构造一组详细程度不同的模型。计算机在生成三维图像时，以此模拟“越近看得越清”的视觉规律。

2）应用举例

图6-8是LOD技术应用的一个例子。从中可以看出，LOD技术可以减少要显示的多边形数量，近处的地形表面分辨率变化不大，但通过减少距离远的多边形数量，降低分辨率，可以大大提高三维显示速度。

图6-8 视点抬高时地形分辨率的变化情况（左边为线框显示，右边为实体绘制效果）

2.技术的实现思想与过程

LOD技术的主要实现思想和过程如下：①模型建立：对空间目标建造不同分辨率（详细程度）的模型并赋予唯一标识。②确立模型与视距（或比例尺）的关系：即不同的视距下对应不同分辨率的模型，近视距下采用分辨率高的模型，在远视距下采用分辨率低的模型。在实时显示时，通过计算机视点与目标中心的距离作为视距来确定应显示的模型。

3.常用地形LOD生成算法

地形数据根据其数据结构不同可以分为TIN和Grid两种形式。使用TIN和Grid都可以用来建立多分辨率的地形LOD。不规则三角网TIN模型由于三角形面中各点的位置是变化的，所以它可以使用比其他方式更少的多边形来表达任何精度的表面。但动态创建分层的TIN模型在算法的计算代价上是极其昂贵的。而规则Grid的结构形式比较简洁，在多分辨率的LOD技术中更容易进行数据重组织，只需要对格网的高程数值进行重采样就可以建立简化的分层模型，而TIN模型则需要重新三角网化，所以在LOD的算法中，Grid更具有优势。表6-1是目前常用的地形LOD生成算法分类表及其优缺点。

表6-1 地形LOD模型生成算法分类

基于TIN的层次结构LOD模型的生成算法包括层次模型算法、自适应层次模型法和渐进格网法。

1）层次模型生成算法

De Florian提出用层次结构描述地形LOD模型。在层次地形LOD模型中，用一分三（Ternay）的方法在TIN中移去或增加点来构造层次TIN模型。设τ0表示覆盖整个地形区域的根三角形；再在τ0中插入一个最大误差点P，将τ0分裂成三个新三角形；然后，判断所形成新三角形的误差是否大于该层次的误差阈值；如果是，则继续插入新点并对该新三角形进行分裂，直到所有新三角形的误差均小于该层次的误差阈值，即完成该层次的地形LOD模型的构建。此后，可以进行下一层次的TIN模型构建。

2）自适应层次模型法

Scarlatos et al提出用自适应方法来建立层次TIN模型。与De Florian的三角形分裂规则不同，该算法将三角形的分裂分为五种情况。设三角形ti的三个顶点为V1、V2和V3，所对的三条边分别为e1、e2和e3，令ti和e1、e2、e3的最大误差分别为E（ti）、E（e1）、E（e2）、E（e3），所对应的最大误差点分别为p、p1、p2、p3。若分裂误差阈值为ε，则五种分裂情况如图6-9所示。

图6-9 自适应层次模型三角形分裂的五种情况

3）渐进模型生成算法

Hoppe将渐进格网（Progressive Mesh，PM）的概念引入地形LOD模型中，提出了渐进模型生成算法（PM法）。该算法通过一系列的顶点分裂（Split）与合并（Collapse）实现对原始模型的变换，从而构建不同分辨率的LOD模型。该类算法能严格控制复杂模型的简化误差，并产生较好的图像效果。

TIN顶点的邻接关系是算法的基础。如图6-10所示，顶点的分裂是通过增加一个顶点到原TIN中，从而产生更精细的TIN模型；顶点的合并则是通过删除一个顶点，从而产生更简略的TIN模型。即通过顶点的分裂与合并操作，得到一系列不同分辨率的层次模型（LOD）。

图6-10 渐进格网（Progressive Mesh，PM）顶点的分裂与合并

基于Grid网格地形LOD模型的生成算法包括四叉树剖分算法、二叉树剖分算法和实时优化自适应网格。前两种方法如图6-11所示。

图6-11 基于Grid网格地形LOD的四叉树剖分算法和二叉树剖分算法

（上图为四叉树剖分、下图为二叉树剖分）

1）四叉树剖分算法

其实质是通过递归方法对地形进行自顶向下的四叉树分裂。在分裂过程中实时计算节点的误差；若该节点的误差大于规定的阈值，则该节点继续分裂。如此进行，直到所有节点的误差均小于给定的阈值。该算法要求地形格网的行列交点数满足（2n＋l）×（2n＋l），而实际上经常不能满足，则可能造成父节点的四个子节点所对应区域的分辨率不一样，从而在区域交界处出现不连续，可视化时出现空洞现象。

四叉树模型生成算法的基本流程为：

第一步，判断Grid模型的行列交点数是否满足（2n＋l）×（2n＋l）的要求。若是，进行下一步；若非，则对格网重新釆样或补网。

第二步，对原始模型进行四叉树分裂，同时记录其四个子块的行、列数目以及该顶点的误差。

第三步，进行递归运算，直到每个区域的长、宽大小均等于原始Grid模型的最小分辨率为止。

第四步，结束。

2）二叉树剖分算法

Evans等提出釆用直角三角形二叉树剖分方法来建立层次网。该算法的实质是将矩形地形区域按对角线划分成两个直角三角形，判断每个直角三角形的误差是否大于给定的阈值，若大于，则使用该直角三角形的直角顶点和斜边的中点的连线对该三角形进行再次划分，使其变为两个三角形，重复上述方法直到所有的三角形误差都小于给定的阈值误差，则剖分操作停止，如图6-12所示。

图6-12 二叉树剖分算法

3）实时优化自适应网格（Real-time Optimally Adapting Meshes，ROAM）

Duchaineau et al（1997）提出了著名的ROAM算法，该算法基于GRID网。依据视点的位置和视线的方向等多种因素，对于表示地形表面的三角形片元进行一系列的基于三角形二叉剖分分裂与合并，形成一颗二叉树，存储当前三角形的左邻三角形、右邻三角形、底部连接三角形等信息，以便后续三角形的分裂与合并，如图6-13所示，最终形成和原始表面近似且无缝无叠的简化连续三角化表面。

图6-14是地形ROAM网格实例。

4.LOD模型中裂缝修正算法

该算法通过对原始大区域进行分块，减少了直接进行LOD建模的数据量，一定程度上可提高算法的运行速度，尤其为大规模并行计算提供了基础。但是，也正因为区域分块，不同区域离视点的远近不同而分辨率不同，导致三维可视化时在不同模型（Grid和TIN）子块的接边处出现“裂缝”或“漏洞”，如图6-15所示。

图6-13 ROAM网格剖分原理图

图6-14 ROAM网格实例

产生原因如图6-16所示，某一子块区域的四个子区域A、B、C和D的分辨率不一致，A区域的分辨率比其他区域分辨率高。如果在它们的公共边界上不做任何处理，则可视化时，在与A区相邻的B、D区域的公共边界上导致“缝隙”或“漏洞”。

图6-15 实际LOD地形产生裂缝现象

图6-16 LOD区域分块由于相邻区块精度不同导致裂缝的产生

如果将相邻区块公共边两边的三角形的精度提高即可缝合裂缝。也就是将公共边精度低的三角形进一步地剖分，使其精度和另外一个三角形精度一样，即可消除裂缝。如图6-17所示。

图6-17 LOD相邻区块裂缝的消除方法

5.地形子场景块的视景体可见性选择

整个场景地形数据分块处理后，在地形的实时绘制过程中，每一帧显示处理的数据只占整个地形数据中的很小一部分。在某一瞬间，视点位置、视线方向、视角等参数确定时，只有处于视景体内（由近远裁剪平面、上下裁剪平面、视角裁剪范围确定）的场景块才参与地形场景绘制。

如图6-18和图6-19所示，场景块与视景体的位置关系包括场景块全在视景体内、部分在视景体内和完全在视景体外三种。在图中，全部或部分处在视景体内部的块都有绘制，其余的是完全处于视景体外的块不绘制。同时离视点越近的地形块分辨率越高，远离视点的地形块分辨率低，这样既不失去效果，又提高渲染速度，从而达到超大地形的实时漫游。

图6-18 视景体与场景块可见性选择俯视图

在视景体可见块选择时，根据地形场景特点，算法考虑了远裁剪平面、视域范围和视向三个参数，而不考虑近裁剪平面和上下裁剪平面三个参数，场景瞬间视点位置P（X，Y），视角跨度为α，视线方向Nview和远裁剪平面Pfar。

在视景体参数已知的情况下，根据子场景块在视景体内（包括完全和部分在视景体内）和外两种情况，确定场景块在当前帧是否参与场景绘制。本算法通过计算待判断块四角点与视点方向、视线方向夹角和视角范围α的大小比较进行可见块的快速选取。①当场景块四角点与视点方向、视线方向夹角小于α／2，则该场景块完全在视景体内；②当场景块只有部分角点与视点方向、视线方向夹角小于α／2，则该场景块部分在视景体内；③否则该场景块完全在视景体外。①、②两种情况下，场景块参与场景绘制，而③则不参与场景绘制。

图6-19 视景体与场景块可见性选择全景图

大区域三维地形进行地形分块且在某一显示瞬间参与场景绘制的场景块已经选取后，地形显示时离视点越远的场景清晰度越低，离视点越近的场景清晰度越高。

6.存在问题与解决办法

LOD技术在实际应用时有两个需要解决的问题。

（1）会发生“跳跃”现象：随着视距的变换，不同分辨率模型在切换时会发生“跳跃”现象，可以将两个模型进行加权融合，并使用透明技术使前一模型逐渐消失，新的模型逐渐出现，使两个模型变换更加自然。

（2）不能连续光滑显示：由于数据地形范围比较大并且是连续的，不同密度的格网地形连续光滑地显示是不可能的，在实践中除采用分辨率渐变的形式来显示地形，即在视距较近时，数字地形分辨率降低很小，视距较远时，分辨率降低较大，同时还需采用“雾化”处理来屏蔽分辨率不同造成的视觉失真。