基于GeometryClipmap的三维地形可视化研究

殷青松　哈力木拉提·买买提

(新疆大学新疆多语种信息技术实验室　新疆 乌鲁木齐 830046)



基于GeometryClipmap的三维地形可视化研究

殷青松哈力木拉提·买买提

(新疆大学新疆多语种信息技术实验室新疆 乌鲁木齐 830046)

摘要随着数字科技的广泛应用和信息化普及的逐渐深入，实现地形的三维可视化的重要性日渐彰显。但目前的普通PC内存容量无法容纳海量的几何数据和纹理数据。为解决这个问题并提高绘制的效率，采用Geometry Clipmap算法绘制地形，充分利用GPU以提高绘制效率，通过顶点纹理获取各顶点高程值。同时，简化了三角形条带的组织方式，使用简化的视锥体裁剪方法和动态确定绘制层数方法减少需要绘制的顶点数。根据特定层结构，提出数据更新的新方法(二进制定位法)减少视点移动时各帧的数据更新量。实验结果表明，该方法使用很少的内存完成大规模地形绘制，且取得了较高的帧率，漫游流畅，保证了地形的真实感，能满足大规模地形实时可视化的要求。

关键词几何剪切图剪切图地形可视化顶点纹理获取图形处理器

0引言

三维地形渲染从用途分类，主要有两种方式：一种是人为设计各种地形并采用多种纹理素材。通过混合、拼接等操作实现地形的渲染[1,2]，这种方式常用于大型3D游戏等人为设计的虚拟环境渲染中。它的特点是高程和纹理人为合成设计，可重复利用，所以数据量小，比较容易实现。另一种是采用真实的高程数据和纹理(如通过卫星探测拍摄)来进行三维地形的渲染[3,4]。这种方式一般用于需要真实地形模拟的场合，如数字地球、军事用途等。采用第二种方式实现三维地形渲染时，要处理的数据量相当大，一般内存容量不能一次容纳这么多数据，所以此法对数据的加载和调度算法要求比较高，实现难度更大。为了减少数据的处理量，提高渲染速度，LOD(LevelofDetails)细节层级技术应运而生，产生了许多优秀的算法。LOD技术指根据物体模型的节点在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重要物体的面数和细节度，从而获得高效率的渲染运算。

从三维地形网格图的实现方式来看，也主要可分为两类：规则格网Grid模型[5]和不规则三角网TIN模型[6]。

近年来，随着GPU的出现和迅速发展，GPU强大的数据处理能力尤其是对浮点型数据的处理能力极大地缓解了CPU的负担，所以最大限度地利用GPU来渲染地形能够使渲染速度大幅加快。相比TIN模型，具有规则结构的Grid模型在利用GPU提高效率方面明显更具优势。

由于传统的LOD算法(如ROAM算法[7]、基于四叉树的地形算法[8]等)需要实时地建立和修改网格结构，极大地依赖CPU，限制了绘制速度，所以近年来的研究都专注于面向GPU的LOD算法，Mipmap算法和收稿Clipmap算法[9]就是其中的佼佼者，极大地提高了绘制速度并节省了存储空间。Clipmap算法比Mipmap算法复杂，但占用更少内存。

2004年Losasso和Hoppe提出了GeometryClipmap算法。这是一种基于视点的连续LOD方法，将地形看作是一张由高程数据组成的纹理图像，采用Clipmap结构将地形几何数据组织成嵌套的规则网格形式并进行绘制[10]。Asirvatham和Hoppe将GeometryClipmap结构每层数据分解成多个规则块，并利用了显卡的VTF(VertexTextureFetch顶点纹理获取)新特性，提高了绘制速度[11]。康宁等使用“裙”的方法解决各层之间的裂缝问题，但数据精度仍有待提高[12]。袁建锋等采取直接改变GeometryClipmap结构不同层边界对应顶点高程的方法避免裂缝，减少了弥补裂缝的计算量，但仍会产生视觉不连续的情况[13]。王春通等过降低GeometryClipmap结构两相邻层中较精细层对应顶点高度值的方法，避免了裂缝的产生[14]。张浩等给出了一种不对称GeometryClipmap结构，在构造GeometryClipmap结构时，不再以视点为中心，而是以视点偏移后得到的中心点为新的中心，并通过使用不对称GeometryClipmap结构的更新方法，提高了原方法对网格的利用率[15]。Clasen等将GeometryClipmap结构扩展到球面[16]。

综上所述，要使用面向GPU的Grid模型LOD算法模拟真实地形，GeometryClipmap算法无疑是一个很好的选择。本文采用GeometryClipmap算法来实现三维地形网格的绘制，并利用SM3.0以后版本显卡的VTF新特性使大绘制任务转移到GPU中实现。采用了特定的GeometryClipmap层结构，并根据其特定结构优化了三角形条带的组织方式，使用了简化的视椎体裁剪方法，运用了随视点高度动态调整Clipmap层数的方法，大大减少了需要绘制的顶点数。尤其是提出了与层结构对应的各层位置调整和数据更新方式——二进制定位法，以保证各层嵌套严密，并大大减少了数据更新量。

1Geometry Clipmap算法介绍

GeometryClipmap算法是Losasso和Hoppe提出的嵌套规则网格LOD算法。主要思想(如图1所示)：把地形高程数据看做一张2D高程纹理图，然后类似于Mipmap，将其过滤为不同分辨率的L层棱锥(相邻的两层中较精细层的行宽是较粗糙层行宽的两倍)，但完整的棱锥太大，存储器仅有的容量容纳不下。所以算法在每层缓存一个数据大小都为n×n的窗口，各层窗口组成一个以视点为中心的嵌套的规则网格结构(最粗糙层的窗口恰好完全覆盖当层棱锥)。由于较粗糙层中间部分会被较精细层覆盖，所以渲染时除了最精细层全部渲染，其他层都只渲染一个口字型区域。由于只有最粗糙层窗口完全覆盖了当层的棱锥，所以当视点移动时，只有最粗糙层窗口保持不变，其他各层窗口随视点移动在各自所在的棱锥各层移动更新。

图1　高程数据组织原理图

最初的方法通过将每层的高程数据分别存入一个顶点缓冲区来实现，但这样的方式需要大量CPU干涉。所以当显卡具有顶点纹理新特性(即在顶点着色器中使用纹理的能力)时，将每层的高程数据存储为一个2D纹理的方法成为更好的选择，它能解放CPU，使大部分渲染任务都转移到GPU上执行，利用GPU强大的浮点型数据运算能力，大大提高渲染的效率。

采用顶点纹理方式的实现方法为：将顶点坐标(x,y,z)分为单独的两部分：水平面位置(x,z)和高度值y坐标。前者可通过计算得知，存储为常量数据。后者则从DEM文件中读取出来并以单通道2D纹理形式保存在显卡中，称之为高程图，并为每一层设置一个单独的大小为n×n的高程图。当视点移动时，这些高程图也随之更新。在顶点着色器中各层顶点通过VTF重新获取保存在相应层纹理中的高程值。

2Geometry Clipmap算法具体实现

2.1Geometry Clipmap层结构设计

每层的边大小n都为2k-1，这样可以使层间边界上的较粗糙的层的顶点位置刚好落在较精细层上的顶点上，有利于避免产生裂缝。

最精细层全部渲染，设置成一个整块。

除最精细层外，其他层都只渲染一个口字型区域，分为18个区块，如图2所示。

图2　Geometry Clipmap各层区块划分

可以把每层(最精细层除外)划分为3种固定大小类型，共18个区块。如图2所示，三种区块大小可固定表示为m×m(1至12白色区块)，m×3(13至16灰色区块)和(2m+1)×2(17、18黑色区块)，其中m=(n+1)/4。这样做的好处是我们可以利用固定的顶点序列及索引序列来组织三角形条带，方便简单地调用绘制函数把每层的网格结构绘制出来，而且还有利于后期的视锥体裁剪操作。

2.2获取顶点坐标数据

对于水平面位置(x,z)部分，很容易实现，只需要定义一个大小为n×n×2(n×n个顶点，每个顶点水平位置有x和z两个数据)的数组并可通过计算定初值。然后创建顶点数组对象VAO和顶点缓冲区，将数组存入顶点缓冲区，最后指定顶点属性数组并启用顶点属性数组即可。

对于高度值y坐标部分，就相对要复杂点。首先需要从DEM文件中读取高程数据。本文采用国际标准的USGS_DEM格式的DEM文件。按照该文件特定的存储数据的格式，可以方便地将数据读取出来，并以数组形式保存。然后就可以创建并绑定纹理，将数组中的高程值以单通道纹理方式保存于显存中。具体步骤如下：

1) 创建纹理名称；

2) 将纹理名称绑定到二维纹理绑定点；

3) 指定二维纹理的宽高，设置为单通道，并指定构成二维纹理的数组；

4) 设置放大和缩小纹理过滤器的过滤方式为最近邻过滤。

接着就可以通过VTF方式获取高程值，具体方法为在顶点着色器中定义纹理采样器，并通过顶点x、z位置坐标计算出纹理坐标。最后使用GLSL中的内置函数texture从高程纹理图中采样出高程值。可以通过纹理数组与VTF结合的方式来获取各层顶点的高程值。

2.3视锥体裁剪

显而易见，地形绘制的顶点数量是相当大的，而视域内所见的区域通常只是整个地形的一部分。所以如果只让GPU处理视域内顶点的数据，就可以大大减少计算量，提高绘制速度同时又不影响真实感。在调用draw函数前进行简单的视锥体裁剪，就可以达到这个目的。将视锥体左右平面定为裁剪平面。每个m×m块可以通过四个角中的两个顶点是否在左右平面之间来判断这个块中是否有顶点在视锥体中，若有，则绘制这个块，否则不绘制。这种方法使每层占绝大多数顶点的12个m×m块平均减少到4个，且只需少量计算即可剔除大量不在视域内的块，避免了CPU对每个顶点进行计算。

另外，若视点升得太高，距离精细层太远，那么实际上精细层的精细表示是一种浪费。可根据视点距离精细层的距离动态决定Clipmap的层数。具体方法为如果视点到某层的距离大于0.4ngl(gl为各层相邻顶点的间距)，则不绘制这层及更精细的层。此方法可在不影响显示效果的前提下减少不必要的绘制开销。

2.4绘制三角形条带

在进行绘制时，使用顶点的索引序列和三角形条带方法绘制，而不直接使用顶点坐标和单个三角形。这样做的好处是可以大大节省存储空间，并且更简单易行。

一个顶点坐标包括3个浮点型数据，共12个字节；而一个索引则只需1个整型数据，只占4个字节，使用索引序列来绘制三角形占用内存明显更少。如图3中第一行条带所示，10个顶点组成有8个三角形的三角形条带。如果使用单个三角形方式绘制，每个三角形3个顶点，共需存储3×8=24个顶点；而使用三角形条带方式绘制则只需一个10个元素的顶点数组即可。在地形绘制这种需要绘制的顶点比较多的情况下，尽可能地利用顶点索引和三角形条带来绘制，可以大大节省存储空间。

图3　组织三角形条带的顶点索引序列

在绘制时使用组合绘制函数glMultiDrawElements绘制三角形条带，与文献[12]文献[17]相比，这样可以进一步地减少存储的顶点数量，并简化了索引序列的组织。如图3所示，将三角形条带第一行部分的索引序列加上顶点数10，就是第二行部分的索引序列，后面各行依此类推。

具体实现方法为：先创建并绑定索引缓冲区；然后按照各区块的结构将索引组织成三角形条带索引序列并存入索引数组；接着将数组保存在显存的索引缓冲区中，最后调用glMultiDrawElements函数按照索引缓冲区中的索引序列绘制三角形条带。

由于GeometryClipmap各层的结构是固定的，所以各不同区块的索引数组都是固定的，并不随每帧的数据更新变化而改变。相比文献[12]和文献[17]，这样可以进一步节约CPU资源，提高绘制效率。

2.5数据更新

当视点移动时，各层也会相应地移动更新，但由于在相邻各层之间，较粗糙层相邻顶点间隔是较精细层相邻顶点间隔的两倍。各层的移动更新步调不一致，就会导致各层之间不能维护完整严密的嵌套层级结构。

图2中所示第17、18区块，叫做内部调整块，通过对它的位置的调整，我们可以完美地解决各LOD层级更新的问题。

各层更新步骤以第18区块为例，假定有1个无内部调整块的精细层和三个带内部调整块的口字型区域层，如图4所示。

图4　各层位置更新方式

注：黑色的是各层的内部调整块，灰色的是各层大小为m×3的块，视点一步移动两小格(即最小内部调整块宽度)

如果各层第18区块调整块在左侧标记为1，在右侧标记为0，那么从外层到内层，调整块初始位置为{0,1,0}。视点向右移动一步后各层调整块位置变为{0，1，1}。再向右移动一步后各层调整块位置变为{1,0，0}。由此可见，调整块跟随视点的变化规律恰恰类似于二进制数相加减：视点右移几步，由调整块初始位置构成的二进制数就加几；反之，视点左移几步，由调整块初始位置构成的二进制数就减几。根据得到的新二进制数的各位数值是1还是0，就可判断各层的内部调整块应该在左侧还是在右侧。第17区块内部调整块的调整方案与第18区块的相同。

由此推出视点移动时，各层内部调整块位置的计算方法——二进制定位法：

1) 设置两个全局数组adjust1[]和adjust2[]，并以0和1为两数组各元素初始值，以此分别确定z轴方向和x轴方向各层调整块(即各层17、18区块)初始位置序列。

2) 将步骤1)中的调整块序列数组中各元素作为一个二进制数的各位，并将此二进制数转化为十进制数。

3) 利用三角函数计算视点在z轴和x轴方向的分位移，从而得到视点在两个方向的移动步数。

4) 将2)中得到的两个十进制数分别加上3)中的在z轴、x轴方向的移动步数，得到两个新的十进制数。

5) 用位移和按位与操作计算4)中得到的两个新十进制数的二进制形式的各位，并以此更新1)中全局数组各元素的值，得到视点移动后各层的调整块位置。

容易看出，当一个较粗糙层的调整块位置改变时，它内部的所有更精细的层都会进行位置更新，而它所在的层以及所有更粗糙的层的位置都不变，也就不用更新数据。由于视点的移动是连续的，所以我们总是会更新较精细层的数据，而较粗糙层的数据总是很少更新。也就是说，我们总是只更新精细的几个层的数据，而不是所有层的数据都更新，这样可以明显减少视点移动时各帧的数据更新量，从而提高绘制效率。

由于第17区块可在上边或下边，第18区块可在左边或右边(如图2中的黑色区块)，不像其他两种区块位置固定不变。所以，在绘制内部调整块三角形条带时，需要判断各层的内部调整块位置，根据其位置来确定它的顶点索引序列。另外，确定了较粗糙层的内部调整块位置后，才能确定较精细层的位置，即各层的首顶点位置需要根据各层调整块的位置算出。

3算法实现

3.1绘制阶段流程图

图5　流程图

3.2实验环境及效果展示

实验采用的地形高程和纹理数据来自PugetSound，地形绘制的范围大小为16 256×16 256。采取n的大小为127，层数为8。每层127×127个数据，8层，每个数据为float型，占用内存仅127×127×8×4byte/1024≈504KB。

硬件和软件环境如表1、表2所示。

表1　硬件环境表

表2　软件环境表

令视点逐步升高，则所需绘制的Clipmap层数逐渐减少。由图6可明显看出，随着绘制的层数减少，绘制时的帧率越来越大。

图6　视点高度逐步升高时的平均帧率图

由图7可见GeometryClipmap的层层嵌套结构。相邻两层，外层顶点间距是内层的2倍。效果如图8所示。

图7　线框模式效果图

图8　纹理映射效果图

4结语

本文利用了现代图形卡的新特性，对大规模地形的绘制进行了研究。利用现代图形卡的可编程特性和强大的计算能力将GeometryClipmap的绘制任务转移到GPU上。利用现代图形卡近年出现的VTF新特性完成了高程值的获取。特别地，本文详

细描述了各层的更新方式和内部调整块的调整方案，解决了视点移动时各层如何更新和调整块如何调整的问题，保证了各层之间结构严密吻合。使用简易的视锥体裁剪方法和随视点高度动态确定绘制的层数方法大大减少了绘制的计算量。实验取得了较高的帧率，视点移动时画面流畅，可以满足大规模地形实时可视化的需求。

参考文献

[1] 赵瑞斌,张燕玲,王继东,等.特征控制下的多样图地形纹理合成算法[J].计算机工程,2012,38(10):197-199.

[2] 王继东,赵瑞斌,庞明勇.基于特征草图和分形插值的可控真实感地形合成[J].计算机应用,2013,33(2):519-542.

[3] 王响,雷小永,戴树岭.基于视点预测的大规模地形的实时渲染[J].系统仿真学报,2013,25(6):1202-1206.

[4] 李钦,戴树岭,赵永嘉,等.分块LOD大规模地形实时渲染算法[J].计算机辅助设计与图形学学报,2013,25(5):708-713.

[5] 陈希亮,曹雷,崔平.基于ROAM算法的实时地形可视化研究[J].计算机技术与发展,2013(1):243-247.

[6] 周雪梅,黎应飞.基于Bowyer-Watson三角网生成算法的研究[J].ComputerEngineeringandApplications,2013,49(6):198-200.

[7]DuchaineauM,WolinskyM,SigetiDE,etal.ROAMingterrain:real-timeoptimallyadaptingmeshes[C]//Proceedingsofthe8thConferenceonVisualization’97.IEEEComputerSocietyPress,1997:81-88.

[8]LindstromP,KollerD,RibarskyW,etal.Real-time,continuouslevelofdetailrenderingofheightfields[C]//Proceedingsofthe23rdannualconferenceonComputergraphicsandinteractivetechniques.ACM,1996:109-118.

[9]TannerCC,MigdalCJ,JonesMT.Theclipmap:avirtualmipmap[C]//Proceedingsofthe25thannualconferenceonComputergraphicsandinteractivetechniques.ACM,1998:151-158.

[10]LosassoF,HoppeH.Geometryclipmaps:terrainrenderingusingnestedregulargrids[J].ACMTransactionsonGraphics(TOG),2004,23(3):769-776.

[11]AsirvathamA,HoppeH.TerrainrenderingusingGPU-basedgeometryclipmaps[J].GPUgems,2005,2(2):27-46.

[12] 康宁,徐青,周杨,等.一种基于图形硬件的海量地形实时可视化算法[J].系统仿真学报,2007,19(17):3988-3992.

[13] 袁建锋,崔铁军,姚慧敏.一种基于GPU的大规模地形实时生成算法[J].海洋测绘,2009,29(1):35-38.

[14] 王春,马纯永,陈戈.基于GPGPU的海量山地地形数据的实时绘制算法[J].计算机应用,2009(8):2105-2108.

[15] 张浩.不对称的GeometryClipmap算法[D].武汉:华中科技大学,2005.

[16]ClasenM,HegeHC.Terrainrenderingusingsphericalclipmaps[C]//ProceedingsoftheEighthJointEurographics/IEEEVGTCconferenceonVisualization.EurographicsAssociation,2006:91-98.

[17] 殷小静,慕晓冬,陈琦.基于图形硬件的海量地形可视化算法[J].火力与指挥控制,2013,37(11):61-64.

ON 3D TERRAIN VISUALISATION BASED ON GEOMETRY CLIPMAP

Yin QingsongHalmurat Mamat

(Xinjiang Laboratory of Multi-Language Information Technology,Xinjiang University,Urumqi 830046,Xinjiang,China)

AbstractWith the wide use of digital technology and the growing popularisation of informatisation, the importance of realising 3D terrain visualisation becomes increasingly clearer. But the normal PC memory capacities cannot accommodate massive geometric and texture data. To solve this problem and to guarantee the efficiency of drawing, we adopted the Geometry Clipmap algorithm to draw the terrain, made the full use of GPU to improve the efficiency of drawing, and obtained elevation values of every vertex through vertex textures. Meanwhile, we simplified the organisation mode of triangle strips, used the simplified view frustum clipping method and the dynamic rendering layers number determination method to reduce the number of vertexes to be drawn. Based on the structure of specific layer, we came up with the new method (binary positioning method) of data update to reduce data updating amount of each frame during the motion of viewpoint. Experimental results showed that the new algorithm completed the large-scale terrain rendering by using a little memory, and got a higher frame numbers with smooth roam, guaranteed the realistic display of terrain, and was able to meet the demand of real-time visualisation of large-scale terrain.

KeywordsGeometry ClipmapClipmapTerrain visualisationVertex texture fetch (VTF)GPU

收稿日期：2014-12-24。国家高技术研究发展计划项目(2013AA 013702)。殷青松，硕士生，主研领域：计算机图形学。哈力木拉提·买买提，教授。

中图分类号TP391.9

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.049