基于Chunked LOD的实时细节增强地形算法

宋省身，全吉成，赵秀影，王宏伟，王 宇

（1.空军航空大学 航空航天情报系，吉林 长春130022；2.军事仿真技术研究所，吉林 长春130022）

0 引 言

近年来，关于地形场景的渲染技术在三维仿真的诸多领域得到了广泛的应用，当前主流的研究集中在视点相关的LOD 算法上，通常将之分为两类，前GPU 算法和后GPU 算法［1］。早期基于CPU 的算法如ROAM 和VDPM，每次都要计算优化误差并依此选择优化的方案，需要耗费大量的内存和CPU 时间。现在的图形处理器GPU 具备强大的浮点运算能力和多条流水线，如Chunked LOD 使用了块状四叉树结构，仅需要最小限度的CPU 参与就可以绘制大量的多边形表面。

然而这项技术以静态数据作为渲染源，即将预处理好的地形网格按层次呈现，并不具备实时添加新细节的能力，当视点观察的网格深入到数据的最高分辨率层级时，系统就无法继续细化，此时就会出现地形纹理模糊和网格棱角化的现象。同时，文献 ［2］还指出Chunked LOD 对视点距离的计算过于简单，仅提供了近似三维距离的误差度量，造成了细节分配不均。

为了充分利用GPU 的绘制速度，增强细节视效，本文在研究了Chunked LOD 的基础上，提出了实时增加细节的改进方案，相对于文献［3］的局部三角面化简算法和误差评估与控制算法，该算法结合了Geomipmap的思想［4，5］，以规则格网为处理单位修改细节的生成和过渡算法，以及误差度量的计算和判断准则，更高效地利用GPU 的批处理能力实现绘制，经过实验证明，达到了实时增强细节的效果。

1 Chunked LOD 基本算法

Ulrich在Siggraph 2002 年会上提出了一种基于GPU的地形LOD 算法，称之为Chunked LOD［6］。

该算法的核心是构建一个四叉树结构，树上的每个节点 （Node）包含一块地形，每个子节点包含其父节点地形的1／4，但其分辨率却更高。这样自上而下，根节点包含整个地形区域，是其最粗糙的表示，叶子节点则是数据集中所能达到的最高分辨率进行分块得到。节点与节点之间相互独立，节点中的地形数据以静态的方式存储在网格中，称之为Chunk。每个块内的数据可以通过一个绘制命令和一个高级的混合通道来完成绘制。

Chunked LOD 创新的另一处是对缝隙的消除［7］。在块的周围构造垂直的裙边来消除缝隙，裙边的上边与块边相接，下边则延伸到比所有的细节层次都低，裙边只影响本块，不与其他块联系，纹理也可以直接采用原来块的纹理，这样的方法可以有效地消除缝隙。由于块之间相互独立，方便实现out－of－core算法对数据进行分页管理和预读调度，开启独立的线程专门用于调用不同区域的地形块即可。但这需要在服务器或是硬盘存储事先处理好的数据。

该算法的主要缺陷就是预处理工作量大，处理出来的数据为静态数据，无法实时更新或者增强细节，面对分辨率有限的地形数据，当视点高度离地面很近时，显示的视觉效果真实感不足。

此外，当视点逐渐接近一个块时，这个块将会根据误差控制分裂为很多的小块，屏幕上会产生明显的突跳现象，这种现象比逐三角形的LOD 算法如ROAM 算法等要明显的多［8］，而当视点位置恰好处于两个层级的临界点时，这种闪烁现象会变得尤为突出，其解决办法便是借助于几何过渡来减缓网格结构的变化。

2 Chunked LOD 细节增强的改进

2.1 细节增强的基本原理

为当前的高度场添加细节，即增加更多的采样点。根据Geomipmap的思想，细节的添加是其简化过程的逆运算，通过隔行隔列添加的方法使采样点密度变为原来的4倍，分裂出4个子节点，如图1所示。

图1 细节的添加过程

在这里，我们将节点分为两类，一种是静态节点，即在预处理过程中通过采样获取同一区域不同分辨率节点，在渲染时，我们可以通过将对应分辨率的节点调入显存中直接进行渲染；另外一种是动态节点，它是在四叉树结构延伸至叶子节点时，若还不能满足视点阈值的需求，由计算机实时计算生成并加入四叉树中的节点，作为本文研究的重点，这里仅介绍动态节点的生成算法。

新生成的节点，理想上要与已有的节点相关联，保持原来的拓扑关系，显然，线性插值不能满足这种要求，它仅能提供C0连续性，原来的结构并没有发生任何变化，为此我们需要一种高阶的插值算法，并结合位移函数来制造出均匀的变化，增强真实感，其过程如图2所示。

图2 动态节点的生成过程

2.2 算法的具体实现

地形网格进行线性插值后，原本尖锐的网格仍保持尖锐，尽管对某些崎岖的地形可以接受，但我们还是希望能够移除这些突兀的边缘，代之以平滑连续的地势，获得流畅的视觉观感。

本文结合并改进了的文献 ［8］的插值算法——Kobbelt算法，使之能够适用于地形模型的细分。该算法在构造复杂的曲线曲面中都取得了很好的效果，由于细分方法构造简单、计算快速且能够保证生成图形的光滑连续等性质，由于Kobbelt插值细分基于四边形网格模型，正适用于RSG 类型的地形网格进行细分。

Kobbelt细分的基本思想是在四边形网格的原始顶点上根据细分掩膜插入面点和边点，并与原始顶点连接成新的四边形，这样原来的一个四边形面片被分割成4个新的四边形，从而实现对原始网格进行细分的目的。在细化过程中，所有新生成的非边界顶点度数为4，边界顶点度数为3，都是正则点，从而可以迭代进行。

其细分规则如下：

如图3所示，当我们对四边形V5V6V7V8进行细分时，会在其4条边上形成4个边点E0E1E2E3，同时还有一个面点F，使原来的面片分裂成4个子面片。E0，E1，E2，E3的值如下公式

面点F 的值由下公式得出

图3 细分过程

这种细分算法只能应用于正则点所在规则格网上，对于奇异点不予考虑。由于Chunked LOD 算法的特点，细化过程是在每个块内独立进行的，对于邻块内的网格无从知晓，当掩膜移动至块的边缘时，传统的边外推和对角点替换都会产生假边缘，为了保证视觉上的真实感，我们在块结构中再存储上邻块的边采样点，只有在对边进行细化时才使用其作为控制点，块内的细分则对其不予考虑，以少量增加数据为代价换取边缘的连续性。

位移函数用在插值之后，它的作用是提供更加丰富的地形细节。分形理论就能够很好地解决这一问题。描述自然界中存在的随机分形，目前通用的模型是由Mandelbrot等人提出的分形布朗运动 （fractal brown motion，FBM），其二维定义如下。用变量 （x，y）表示曲面上点的坐标，X（x，y）表示该点在曲面上的高。则FBM 曲面定义为在某概率空间上，指数为H （0＜H＜1）的一个随机过程。

随机变量X：R→R2满足：

（1）以概率1，X（0，0）＝0，即过程自原点开始；且X（t）是t的连续函数。

（2）对任意变量 （x，y），（h，k）∈R2，其二维增量X（x＋h，y＋k）服从期望为0，方差为 （h2－k2）H的正态分布，其概率满足

使用分形技术绘制的三维地形能够产生无限具有自相似性的逼真场景，易于进行平滑和插值。Geoclipmap中的细节合成采用了高斯噪声函数，文献 ［9］采用的是Perlin噪声函数，利用有限带宽频率的逐次增加合成地形表面，通常需要多次的运算和校正以获得合适的效果，这会造成较大的计算负载，使得实时获取变得困难。为了权衡实时性与渲染质量，一般的做法是预存分形函数在不同频域下的处理结果，当需要调用函数时，仅对结果进行插值以获得粗糙的采样值。这样做虽然可以节省计算量，但颗粒度较大，伪渲染的痕迹明显。

因此算法的效率显得尤为重要，中点位移法因其实现简单，运算速度快而被选为本文的分形函数。

本文采用文献 ［10］中的Diamond－Square算法作为位移函数，由种子点组成的正方形开始，通过若干次中点位移法迭代后，不断细分种子正方形以获得逼真的三维地形，同时增加自由参数H 和方差σ构成的 “补偿项”强化地势的起伏性并避免 “尖峰”和 “折痕”的出现。由于对其算法并未做出改进，这里不再赘述。

插值与位移递归地进行时会遇到这样一个问题，在某次插值时，其基础是上一次插值并进行位移之后的节点，那么会导致新生成的节点叠加了之前所有的位移量，这样会造成相对于原始网格难以控制的偏差。为了解决这个问题，需要将插值和位移分离，即设置基础高度图和位移高度图两个网格，其中，基础高度图用于递归地插值，位移高度图则用于将插值得到的点加入其中进行位移调整。基础高度图由四叉树中的叶子节点所对应的网格得到，但不同的是叶子节点不可以再细分，而基础高度图却可以插值细分。位移高度图与高度图具有相同的大小和采样点数目，但其采样点的值是由基础图对应点通过位移函数计算得出的。

2.3 几何过渡

为了避免地形绘制时所有节点同时分裂造成的突变现象，在细节层次进行变换时采取一种缓慢渐变的方式，即为几何过渡。这种过程可以根据时间或是误差进行，相比之下后者在视点移动时才会进行，有助于减少渐变时产生的 “闪烁”。

由于数据存储在四叉树结构中，子节点在各个方向上的采样点数量均是父节点的二倍，但是它们所共有的点具有相同的位置，因此相邻的两个层之间由粗到细的过渡仅仅是把子节点中的精细点添加到父节点上，反之简化就是移除相应的顶点即可。虽然过渡变换发生在三维空间中，但所有顶点仅在竖直方向上变化，因此仅需要一个参数即可描述所需变换的程度。我们取f∈［0，1］作为其过渡因子，h为该过渡点当前高程与目标高程的差值，变换公式如下

其中，d 表示视点到当前点的距离，dchild表示视点到子节点的距离，dparent表示视点到父节点的距离。同时，利用矩阵模板进行计算方便利用GPU 顶点着色器进行实现。几何过渡的效果图如图4所示。

图4 顶点的几何过渡

2.4 误差度量的调整

传统的四叉树结构其叶子节点的误差设为0，因此对四叉树的遍历可以在此停止，这些是针对预先生成的静态节点所设计的，当为四叉树添加动态节点时，就必须给叶子节点也加入误差，当视点靠近时，若当前块已到达底层，但误差仍大于设定阈值，则可以利用之前的算法继续细化。

原理上对叶子节点的插值和细分可以无限地进行，因而误差的大小也需要无限地嵌套，但这并不符合实际要求，所以误差需要用一种逼近的表示方法。我们通过对叶子节点的数据使用位移函数进行处理，在经过多次的动态节点插入后，取与原始网格距离最大的值作为该节点的误差。由于四叉树结构中的误差度量自下而上嵌套，叶子节点误差改变后就必须对整个四叉树节点的误差进行调整，而这些可以在预处理阶段完成。实时加入的动态节点，按照Chunked LOD 的方法，将其误差设为其父节点的1／2即可。

总结上述过程，用伪代码表示改进的LOD 生成算法：

3 实验与分析

为了检验本算法的实用性与实际效果，使用一块地形数据大小为16385×8193的高度图，原始网格中共包含了268435456个三角形，预处理时采取33×33进行分块，共构建了8 层LOD。实验所用的计算机主要配置为：AMD AthlonⅡ处理器，4G 内存，GTX580 显卡，屏幕分辨率为1920×1080，操作系统为Win2003Server，编程语言为C＋＋和DirectX。图5 （a）为没有采用细节添加前效果，（b）为添加了两层节点后的结果。表1给出了在不同LOD 层级的载入时间和漫游时间。

图5 仿真效果

表1 静态节点与动态节点的运行时间比较

数据显示，随着视点的降低，LOD 层级也逐渐深入，三角形数目不断增长，但同时与视见体相交的块也减少了，所以第8级LOD 的三角形数目在高度较低的情况下突然减少。第9级和第10级是动态节点加入后的结果，三角形数目开始增加，但载入速度也有所减慢。同样，前8 级是由预处理过程生成的静态节点，浏览时仅需从存储中读取对应的地形块，帧速较为稳定，而动态节点的插入给实时渲染带来一定负担，帧速的变化取决于地形复杂度和三角形数目。

由图5可以看出，算法对于增强视效的作用显而易见，在整个渲染过程中，图5 （a）的三角形数目为672，而图5（b）则为10752，恰好为前者的16倍，这是由于算法在视锥裁剪上并未做优化，对于背离视点和距离视点较远的网格不加区分地动态细分造成的结果。漫游时的帧速稳定在45－50f／s间，当添加细节时在复杂地形区域会产生帧速下降现象，但绘制完成后会恢复稳定，基本达到了预期的效果。

4 结束语

本文在分析了经典算法Chunked LOD 的基础上，结合了其利用四叉树块结构对地形数据进行分组，提高独立渲染速度的优势，针对其只能处理构建静态数据，无法实时添加细节的不足，提出了利用插值和分形实时地生成动态节点，强化视觉的真实感，弥补由于数据分辨率不足产生的地形变形，该算法利用掩膜对地形网格进行处理，适用于GPU 编程实现。实验结果表明，该算法可以在普通计算机上实现大范围地形的快速绘制和实时漫游。

本文研究所采用的地形数据仍然是一种静态数据，即不支持实时的编辑和变形，诸如爆炸和山体滑坡之类的实时改变地形无法实现，而渲染过程中添加的细节是一种计算结果，非真实数据，今后我们将对于实时的地形编辑和数据更新做进一步的研究。此外，利用视见体的背面剔除和遮挡剔除，考虑在选择绘制时删除不必要的数据块，以提高显示的实时性也是下一步研究的重点。

［1］CAI Chang.Theory and key technology research on 3DGIS web service ［D］.Zhengzhou：PLA Information Engineering University，2011 （in Chinese）.［蔡畅.三维地理信息网络服务的理论与关键技术研究 ［D］.郑州：解放军信息工程大学博士学位论文，2011.］

［2］Strugar F.Continuous distance－dependent level of detail for rendering heightmaps ［J］.Journal of Graphics GPU and Game Tools，2009，14 （4）：57－74.

［3］SHEN Yanchun，ZHU Youhong，WEN Zhuanping，et al.Procedual level of detail enhancement algorithm of Chunklod real time terrain rendering ［J］.Journal of System Simulation，2008，20 （21）：5763－5766 （in Chinese）.［申闫春，朱幼虹，温转萍，等.Chunklod地形的过程化细节度增强算法 ［J］.系统仿真学报，2008，20 （21）：5763－5766.］

［4］LIU Huiyuan.Research and implement on 3Dseabed digital terrain ［D］.Harbin：Harbin Engineering University，2009 （in Chinese）.［刘惠媛.三维海底地形绘制方法研究与实现 ［D］.哈尔滨：哈尔滨工程大学，2009.］

［5］JIANG Jie.Research on key technologies in global virtual geographic environment construction ［D］.Changsha：National University of Defense Technology，2010 （in Chinese）.［蒋杰.全球大规模虚拟地理环境构建关键技术研究 ［D］.长沙：国防科学技术大学，2010.］

［6］JIANG Jie，WU Lingda，CAO Rui，et al.management and web publication of global satallite remote－sensing images［C］／／7th International Conference on Information，Communications and Signal Processing，2009.

［7］ZHANG Yunan，WANG Dong，XIA Yi.A quad－tree dynamic terrain levels algorithm ［J］.ACTA Armamentaria，2011，32（11）：1411－1415 （in Chinese）.［张豫南，王东，夏乙.瓦片块四叉树动态地形层次细节算法 ［J］.兵工学报，2011，32（11）：1411－1415.］

［8］LIN Mouguang.Research on mesh simplification and display method for interactive mobile 3D graphics ［D］.Guangzhou：Zhongshan University，2008 （in Chinese）.［林谋广.面向交互式移动三维图形的网格简化与显示方法研究 ［D］.广州：中山大学，2008.］

［9］LIAO Xuejun，WANG Rongfeng.Digital battlefield visualization and application ［M］.Beijing：National Defense Industry Press，2010：39－42（in Chinese）.［廖学军，王荣峰.数字战场可视化与应用［M］.北京：国防工业出版社，2010：39－42.］

［10］MA Shufang.Generating method based on GPU acceleration for fractal terrain ［D］.Dalian：Dalian University of Technology，2008 （in Chinese）.［马淑芳.基于GPU 加速的分形地形生成方法 ［D］.大连：大连理工大学，2008.］