一种地球漫游中海量地形LOD绘制算法

[摘要]在地球三维漫游过程中，对应海量的地形数据，一个好的优化的动态LOD算法起决定性的作用。随着Lindstrom基于规则网格视点相关的连续细节层次（CLOD）的提出，基于规则网格视点的算法得到了广泛的应用。本文对规则网格视点相关中经典的节点评价公式提出改进，从空间上进行延伸，从空间几何和数学角度分析，求得更佳的节点判定参数，并给出了严密的论证说明。基于该判定参数，减少冗余节点，使得LOD算法更优化。并基于该算法成功实现了海量三维GIS可视化系统。

[关键词]四叉树 LOD CLOD 海量地形

[中图分类号] P183 [文献码] B [文章编号] 1000-405X（2014）-4-124-2

1引言

参考文献[2][6]基于Lindstrom的四叉树思想，从不同的两角度提出简化、消除T行裂缝，更加的简单和快速。[6]中采用一个节点的四个子节点任何一个需要分割全分割的简化实现，[2]利用节点判定公式，强制提高相邻父节点的起伏值，从而约定两临近块分辨率层次不会超过1。四个子节点任何一个需要分割全分割的简化消除方法，计算快，但同时带来更多的需要绘制的三角形。参考文献[2]提供的顶点评价系统非常的快速。

本文主要基于[2]中的思想，基于规则网格视点相关中经典的节点评价公式。加以扩展改进，从空间几何角度、和数学表达式极值角度求取了更优的节点判定中的参数，说明了消除T行裂缝的方法。一次性求取节点的起伏检测因素的值，强制约定临近块分辨率层次不会超过1，从而消除T形裂缝。顶点评价系统快速、简单、高效。

2 LOD算法

2.1 LOD节点评价系统

（1） 距离评价因子

首先需考虑的是物体里观测者的远近，离观察者近的地方细节越多，反之则越少。显然格网宽度d的大小决定了网格的粗细，决定了细节的多少。也就是d与离观测点的距离成正比，离观测者越远，d越大，地形细节越少。因此，设置一距离临界值来根据节点离视点距离，对该节点实现不同层次划分，由此可以得到如下的公式：

其中l为节点的中心位置到视点的距离，d为节点网格的大小。根据视点距离，初始化设置一C值，当节点d的网格大小满足该公式时，节点继续分割，当不满足这个公式的时候，节点不再分割。

（2）地形起伏梯度评价因子

其次需要考虑的因素是地形本身的粗糙程度，我们希望地形起伏比较崎岖的区域有较高的细节程度，而平坦的地方则不需要我们浪费过多的图元。

如图1，中心点与4个边点在节点被分割和不被分割时候会引起一定的误差，沿着四条边点分别产生dh1、dh2、dh3、dh4四个边点误差，由于四个节点不一定在同一个平面上，因此dh5、dh6分别表示中心顶点到两对角顶点连线的距离，取d1至d6中的最大的一个除以节点的大小作为这个节点粗糙度的评价值，即

明显节点的r值乘以该节点的网格宽度，即得到最大的地形起伏误差，因此r乘d可以用来判断是否要继续分割节点保持细节。因此，根据地形起伏度，给出第二个评价公式：

C2越大，细节程度越高。

（3）节点评定公式

综上式（1）和式（2）可得节点评价公式：

该公式基本被当成处理规格网的经典公式，许多基于规则网格的LOD的节点评价都引用该公式，如参考文献[7][8]中的节点评价公式都以该公式为节点评价公式。

当地形起伏不大，视点很近时，观测者同样希望看到的是具有精确细节的地形。但以上评价公式可能由于d值小，而使得f值大，而未显示高分辨率细节。且基于该公式，不利于进一步的裂缝消除，不利于裂缝消除的简化。因此变形得一个更为方便、适用的节点评价公式：

如果，地形节点的 比1小，我们只考虑距离，也就是如果离视点很近的节点，我们都根据距离近的需要而继续分割，显示精确细节。如果地形起伏较大，距离稍远就要考虑地形的粗糙度。当f

3 裂缝消除

由于网格分割的形状，如图2，一个节点包含了一个中心点和若干个围绕着中心点的点，刚好排列成一个三角形扇，因此自然的采用三角形扇的方式来绘制节点。但是如果只考虑节点评价公式（4），由于相邻网格的细节程度差异，会产生T形裂缝现象，如图2左图所示。

细节粗的节点，由于以上节点评价公式f>1而未继续分割，因此该节点起伏梯度不是很大。因此，为了简化网格，可以选择忽略该T型缝点的绘制，如图2所示。该忽略过程，通过绘制中的节点激活检测来保证，具体激活检测请参考文献[7]。

如图2右图，O1和O2为两相邻不同分辨率的网格。O2被绘制的时候要保证O1同时也被绘制，这样就可以达到两分辨率层次相差不会超过1的目的。因此我们只需保证O2符合公式（4）被绘制时，保证O1也应该符合以上公式而被绘制则可。而当O1到视点的距离小于Cd的时候，O1节点符合f

对于符合式（5）的两节点，如果f2

如图3，以O1点为圆心，O1至O2为坐标X轴正向，x、y轴都落在平面O1-O2-S内。视点位置为（x，y）， 的极值转化为：

求 的极值，其中（ x>， >Cd。C为大于2的常数，d为大于0的常数）。通过几何法和代数法可以求得：当x=Cd，y=0时取到符合条件的极值M =（C>2）。

因此令M = （C>2），在遍历四叉树求取r的时候，约束保证临近上层节点的r2≥M×r1，即≥M≥成立。因此保证临近不同分辨率节点间f1

综上，先对空间任意视点构面，从固定平面圆求取规定区域极值。而所有固定距离的极值都落在同一直线上，进而进一步转换到求取直线上的极值。最后求得空间视S在如图3的Smin处取得最大值：

在参考文献[2]中的经典算法中，基于一特殊平面求得M值，M值不够优化且严密性不强。同时节点剔除不充分。

本文算法要基于文献2，一次建立r树，无需在动态简化绘制地形时再次考虑该节点与临近根节点的关系，再去检验分割生成的四叉树是否合法。且改进的算法从空间角度用严密的数学方式求得了较理想的M值，使得细层次上的临近节点的r值的比重得到最合理的提升。地形简化更合理，从而提高程序运行效率。

4应用分析

该算法建立在经典的快速算法之上，根据需求对经典的判定公式进行改进。同时从空间上获取了更好的M值，快速有效地消除T形裂缝。如图4，基于该改进的LOD算法和其他数据组织等算法的结合，实现大型地形的流畅漫游。