瓦片块四叉树动态地形层次细节算法

张豫南，王冬，2，夏乙，李瀚飞

(1.装甲兵工程学院 控制工程系，北京100072;2.武汉军械士官学校 无人机系，湖北 武汉430075;3.重庆航天职业技术学院，重庆400021;4.66222 部队 北京100000)

地形可视化是虚拟战场环境、三维室外场景游戏以及车辆驾驶训练模拟系统中重要的组成部分，一直是计算机图形学里研究的热点问题。在某些特殊应用中，地形的某个区域的属性(如高程值或颜色等)还可能会随时发生改变。如多用途工程车等工程装备对地表的破坏、炸弹爆炸留下的弹坑、车辆在松软土地上行驶后留下的车辙等，这类地形被称作动态地形。动态地形应用中典型的是车辙的可视化，且一直是动态地形中研究的热点问题。

以基于图形处理器(GPU)的动态地形形变算法为基础，扩展并实现了一种基于GPU 的视点相关连续动态地形层次细节(LOD)算法。该算法以瓦片块四叉树算法作为地形绘制算法，通过重复使用一小块顶点缓存和索引缓存，结合不同的缩放和平移因子来渲染不同细节层次的瓦片块，很好的表现了车辙效果。对地形块增加“裙子”顶点，消除了不同细节层次的瓦片块拼接时可能产生的裂缝现象。最后通过实验证明了该算法是可行的和有效的，适合于大规模动态地形的绘制。

1 动态地形可视化算法概述

Summer 等［1］通过4 个渲染步骤来模拟行人在沙地、泥泞地和雪地上留下的脚印。然而由于该算法只能产生光滑的形变，而且需要手动调节5 个渲染参数来达到理想的视觉效果，因此并不适合实时渲染等场合。He 等［2］采用二叉三角树结构，通过对ROAM 算法进行扩展，提出了一种实时动态地形可视化方法DEXTER.文献［3］针对动态地形的特殊情况，采用嵌套球半径作为误差，给出了一种实时可视化动态地形的完整解决方案。文献［4］在ROAM算法的基础上，提出一种基于规则网格的块间裂缝解决算法，根据分裂点在有向无环图(DAG)中的依赖关系来消除裂缝。文献［5］提出了一种基于三角带模板的车辙实时可视化算法。

随着图形硬件的发展，为了充分利用现代GPU特性，Aquilio［6］提出了一种基于GPU 的动态地形形变算法，该算法利用帧缓冲区对象和2 次顶点纹理拾取操作，将对形变顶点的处理由CPU 转移到GPU，释放了CPU 负担，为动态地形的可视化引入了一个新的研究方向。王冬［7］等在文献［6］的基础上进一步将每帧更新的动态地形深度纹理作为拾取对象，只进行一次顶点纹理拾取操作来产生地形形变效果。

由于文献［6-7］在绘制形变后的地形时采用的是强迫分割算法，且并没有进一步给出如何将该算法和基于GPU 的地形LOD 算法相结合，因此限制了其在大规模动态地形上的应用。本文在文献［7］的基础上，结合瓦片块四叉树地形LOD 绘制算法，提出并实现了一种基于GPU 的动态地形LOD算法。

2 基于GPU 的动态地形LOD 算法

整个基于GPU 的动态地形LOD 算法分为动态地形形变算法和动态地形绘制算法2 个部分。

2.1 基于GPU 的动态地形形变算法

整个动态地形形变算法的伪代码描述如下:

动态地形形变算法分为4 个阶段［7］，其基本思想是首先利用帧缓冲区对象的渲染到纹理功能将地形高程图转化为原始的地形深度纹理，如图1(a)所示。为了计算由于车辆对地面的压力造成的地表顶点的沉陷位移，需要通过模型视点变换和投影变换产生车辆的深度纹理(通过视点在地面下方垂直向上观察地形表面得到)，如图1(b)所示。将第1 步产生的原始地形深度纹理减去第2 步产生的车辆深度纹理，这样就可以在片元着色器里得到表示车轮陷入到地表以下深度值的偏移图，如图1(c)所示。在片元着色器里通过对原始地形深度纹理和深度偏移图进行运算，产生此刻形变地形的深度纹理，最后通过顶点纹理拾取操作产生连续车辙效果，如图1(d)所示。

2.2 基于GPU 的地形绘制算法

由于文献［7］在绘制形变后的地形时采用的是强迫分割算法，没有考虑LOD 简化技术，占用了较多的系统资源，因此本文采用瓦片块四叉树多分辨率网格来绘制地形。

2.2.1 基本思想

瓦片块四叉树算法里每一个地形块可以用统一的缩放和平移变量来表示不同细节层次的地形块，因此更适合于在GPU 上实现地形绘制［8-9］。该算法的基本思想是，所有地形块组织成(2k+1)×(2k+1)规则网格，每个顶点都对应于高程图(2n+1)×(2n+1)中的某一个元素。所有地形块在送入图形管线时都是平面网格，地形块的高程值在顶点着色器通过拾取高程图纹理来获得。由于地形块顶点的位置是在顶点着色器里计算而不是在CPU 中计算，而且由于每个地形块包含相同数量的顶点以及相同的网格连接关系，因此所有地形块可以重复使用同一个顶点缓存和索引缓存。

2.2.2 误差估计

算法使用一种简单的基于距离的评估标准，距离视点较远的地形块将覆盖更多的区域，离视点越近的地方细节越丰富。另外，还可以采用文献［10］里的对地形块使用最大屏幕空间误差方法，这将不仅考虑视点与地形块的距离，还包括地形表面的粗糙程度。

基于距离的评估标准由下式给出)

图1 基于GPU 动态地形形变算法原理Fig.1 Dynamic terrain deformation algorithm

式中:l 为地形块中心到视点的距离;d 为世界坐标系下地形块网格间距;C 为一个可调节的控制地形渲染质量的参数。如果测试成功，地形块分割成4个子节点，并向下递归继续校验;如果测试失败，则渲染地形块。

对于地形块大小的选择，如果地形块太大，会导致地形太过粗糙或太精细。使用小的地形块虽然可以在细节层次上有更大的变化，但是会增加渲染函数调用的次数。因此，需要根据试验来确定合适的地形块大小，以达到渲染调用的次数和三角形大小多样化之间的一种平衡。

2.2.3 裂缝消除

瓦片块地形算法中相邻的不同细节层次瓦片块之间会出现裂缝问题。本文使用一种简单而且高效的“裙子”缝合方法，每个瓦片块四周都有一个沿着垂直边界扩展的“裙摆”，如图2所示。

图2 瓦片块四周沿着边界添加垂直裙摆Fig.2 Added vertical skirt to tile block's borde

将这些额外的“裙子”顶点添加在顶点缓存的最后，绘制时首先在索引缓存里正常绘制地形瓦片块，接着通过添加一个褪化三角形来开始绘制裙子三角形。同时，为了优化性能需要将裙子三角形和地形瓦片块三角形通过一次性三角形条带(Triangle_Strip)来绘制。

即使利用裙子算法可能会引起一些光照及纹理拉伸问题，然而由于填充的裂缝一般都很小，因此这些问题不容易被察觉到。另外，虽然这样做会增加一些多边形的数量，然而相对于利用CPU 做缝合，这种消耗可以忽略不记，而且这种方式很容易在GPU 上实现。

2.2.4 碰撞检测

通常碰撞检测是由CPU 来查询存放在内存里的地形高程数据来获取相应位置的顶点高程，即操作是在CPU 和内存之间完成。然而，这样做会增加CPU 的负担，对于需要查询大量的外部实体与地形碰撞检测的应用场合，这种负担将急剧增加。

文献［8］在地形漫游时为了避免视点陷入到地面以下，提出了一种基于GPU 的查询视点所在位置处地形高度的方法，该方法将高程图载入到显存之后，就释放系统内存里的相应资源，然后，在像素着色器里查询高程图纹理中视点所在位置处的像素颜色信息;接着，利用帧缓冲区对象将该像素颜色信息渲染到一个1 ×1 大小的纹理中;最后，通过读取该纹理来获得查询点的高程值。整个操作在GPU 和显存之间完成，能够有效降低CPU 的负担。

在车辆与地形的匹配算法中，通常需要查询的匹配点不止一个，通常为3 点或4 点匹配算法［11］。本文扩展了文献［8］中的方法，使得可以同时查询多个高程值。初始化时利用帧缓冲区对象创建一个大小为2 ×2 的纹理作为渲染目标。在渲染到纹理时，将我需要查询的4 个点的x，z 世界坐标归一化成0～1 范围内的纹理坐标，并以点图元(GL_POINTS)进行绘制。

为了在2 ×2 大小的纹理中区分这4 个像素值，绘制时需要对这4 个输入点进行平移使它们分别位于如图3所示的P1，P2，P3，P4四个区域内。

图3 2 ×2 大小的渲染目标纹理Fig.3 2 ×2 target texture

3 实验结果与分析

针对本文的思想和方法，已经在微机上实现了一个基于GPU 的车辙实时可视化演示系统，很好的表现了车辆在松软地面行驶时留下的车辙效果。硬件配置为:CPU Intel Pentium Dual-Core 2.5 GHz，2 GBRAM，NVIDIA GeForce9500 显卡，128 M 显存;软件环境为:Windows XP，VC++.Net 2003、OpenGL 2.0，GLSL v1.2.

对2 049 ×2 049 大小的地形数据，地形块大小为33 ×33，窗口大小为800 ×600，系统的平均帧率在90 f/s 以上。

图4给出了系统运行时的截图。图4(a)、图4(b)为视点离车辆较远时，车辆所在的瓦片块具有较低的细节层次，虽然此时的网格间距大于轮胎宽度，相应的顶点高度并没有发生改变，但由于场景离视点较远，通过车辙纹理就能够很好的表现出车辙效果。图4(c)为视点离车辆较近时，车辆附近的瓦片块具有较高细节层次水平，从中可以清晰的看出车轮下的地形发生的形变。

使用1 024 ×1 024 大小的地形，对本文算法和文献［7］算法的性能进行比较，结果如表1所示，从中可以看出使本文的算法提高了系统性能。

表1 绘制1 024 ×1 024 大小地形时的性能比较Tab.1 Performance comparison in rendering 1 024 ×1 024 terrain

4 结论

本文以动态地形中的车辙实时可视化为研究对象，提出了一种基于GPU 的瓦片块四叉树动态地形LOD 算法;并针对车辆与地形的匹配问题，提出了基于GPU 的同时查询多个高程值的方法。理论分析与实验结果表明，本文算法中的将GPU 的加速能力同地形多分辨率绘制算法相结合，对于提高动态地形的绘制效率是很有效果的，并且该方法还可以在其他类型的地形形变可视化中推广应用，均有一定的理论和使用价值。

后续的研究工作包括进一步优化该算法的性能，使用最大屏幕空间误差方法来进一步减小需要绘制的三角形数量;关于进一步如何突破单张纹理大小限制的问题，考虑使用地形的多分辨率金字塔模型和外存技术来实现大规模地形的存储，并结合纹理数组技术来加载需要绘制的地形。

References)

［1］ Sumner R W，O'Brien J F，Hodgins J K.Animatingsand，mud，and snow［J］.Computer Graphics Forum，1999，18(1):17-26.

［2］ Yefei He，James Cremer，Yiannis Papelis.Real-time extendibleresolution display of on-line dynamic terrain［C］∥Proceedings of the 2002 Conference on Graphics Interface.Calgary，Alberta:A K Peters，Ltd，2002:151-160.

［3］ 王林旭，李思昆，潘晓辉.动态地形的实时可视化［J］.计算机学报，2003，26(11):1524-1531.WANG Lin-xu，LI Si-kun，PAN Xiao-hui.Real time visualization of dynamic terrain［J］.Chinese Journal of Computers，2003，26(11):1524-1531.(in Chinese)

［4］ Chen Guojun，Zhang Jing，Xu Xiaoli，et al.Real-time visualization of tire tracks in dynamic terrain with LOD［C］∥Proceedings of the 2nd International Conference on Technologies for E-Learning and Digital Entertainment.Berlin，Heidelberg:Springer-Verlag，2007:655-666.

［5］ 蔡兴泉，李凤霞，李立杰，等.基于三角带模板的车辙实时可视化方法［J］.系统仿真学报，2006，18(10):2843- 2846.CAI Xing-quan，LI Feng-xia，LI Li-jie，et al.Real-time visualization of ruts based on strip masks［J］.Journal of System Simulation，2006，18(10):2843-2846.(in Chinese)

［6］ Anthony S.Aquilio，Jeremy C.Brooks，Ying Zhu，et al.Realtime GPU-based simulation of dynamic terrain［J］.ISVC，LNCS 4291，2006:891-900.

［7］ 王冬，张豫南，李瀚飞，等，基于GPU 的动态地形实时可视化［J］.计算机工程与应用，2010(14):177-179.WANG Dong，ZHANG Yu-nan，LI Han-fei，et al.Real-time visualization of dynamic terrain based on GPU［J］.Journal of Computer Engineering and Application，2010(14):177-179.(in Chinese)

［8］ Mike Dickheiser.Game programming gems 6［M］.Boston，Massachusetts:Carles River Media，2006:461-471.

［9］ 王冬，张豫南，李瀚飞，等.一种基于GPU 的瓦片块四叉树地形绘制算法［J］.系统仿真学报，2009，(增刊1):106-109.WANG Dong，ZHANG Yu-nan，LI Han-fei，et al.Tiled block quadtree terrain rendering algorithm based on GPU［J］.Journal of System Simulation，2009(S1):106-109.(in Chinese)

［10］ Ulrich T.Rendering massive terrains using chunked level of detail control［EB/OL］.［2002-04-01］.http:∥tulrich.com/geekstuff/chunklod.html.

［11］ 宋汉辰，魏迎梅，吴玲达.三维对象模型与地形的匹配方法研究［J］.计算机辅助设计与图形学学报，2003，15 (9):1167-1171.SONG Han-chen，WEI Ying-mei，WU Ling-da.Matching research of 3D object model with terrain in virtual environment［J］.Journal of Computer-aided Design ＆ Computer Graphics，2003，15(9):1167-1171.(in Chinese)