一种基于几何多重映射的地形绘制优化算法

1、一种基于几何多重映射的地形绘制优化算法摘要为了使地形绘制算法更好适应现代图形卡的硬件架构，到达PU和GPU的均匀负载，提出一种基于几何多重映射的地形绘制优化算法。该算法利用线性插值的方法改善了几何多重映射算法中由于网格分辨率变化引起的图像突变，经实验数据证明，优化后的算法绘制速度得到极大进步，并且分辨率不同的网格间过渡自然，图像质量得以进步。关键词地形绘制；线性插值；LD地形绘制在3D游戏、GIS、计算机仿真中应用很多，关于这方面的算法也一直是计算机图形学领域研究的热点。地形的绘制需要很多数据参与，对系统资源消耗宏大。加上早期图形卡的数据吞吐才能相当有限，缺乏计算功能，因此当时对地形绘制算法的

2、研究主要集中简化网格模型，减小绘制多边形数目，以期减轻图形卡的数据负载，到达实时渲染大地形的目的。在二十世纪九十年代中后期，出现的Prgressiveeshes1，RA2，ntinuesLD3，以及相关的改进算法都称为LD(Levelfdetail)算法，其根本思想都是根据视点的位置和地形几何复杂度实时产生细节分辨率不同的网格简化模型。即离视点近或总体起伏较大的模型用高精度的网格来绘制，离视点较远或起伏不很明显的模型用相对低精度的网格绘制。很显然，这中间需要实时计算很多评价参数，需要实时构建全部的地形网格，PU工作量极大。随着图形卡数据吞吐才能的不断进步，每秒钟处理上亿个三角形已不再困难。很多

3、计算，比方几何变换和光栅处理都可以交给GPU去计算。所以在GPU数据吞吐量很大的情况下，假如一个算法在剔除渲染顶点的过程中占用了太多PU资源，出现GPU等待PU的情况，那么即使算法在剔除多余顶点方面做的很好，但总体绘制效率也不是高效的。而传统的LD算法都存在这方面的缺陷。并且，受硬件带宽的限制，频繁的传输量宏大的顶点数据，使得时间集中消耗在数据“迁移过程中。过多的DP(DraPriitive)也使得图形卡不能发挥最大成效，造成资源极大浪费。所以要适应现代图形卡的硬件架构，算法必须改进，几何多重映射(Geetrialipapping)4等算法由此产生。本文在Geipap(Geetrialipap

4、ping)算法的根底上，改进了原算法抑制不同细节分辨率模型之间突变的处理方法，使得在进步绘制效率的同时，保证了绘制图形的质量。通过使用查表法的分块网格顶点数据组织方式，使得PU的工作进一步减轻。此外，本文还利用了现代图形卡的存储功能来优化地形的绘制。2.1根本思想Geipap算法是ille根据纹理多重映射的概念提出的，他把整个地形场景在xz平面上进展分块(blk)，比方用3333的blk把10251025的地形表示为3232个blk。每个分块可用不同分辨率的网格模型来描绘。在同一分块内，网格模型的分辨率一样。采用隔行采样的方式生成不同分辨率的网格。整个地形的模型表示和组织如图1所示。不同的bl

5、k之间互相拼接时，假如分辨率不同那么可能产生裂缝。为了消除裂缝，在较高分辨率的blk边界上，忽略一些点作为网格顶点，如图2所示。每个blk分辨率是通过屏幕空间误差4来决定的。在地形数据预处理阶段，对每个blk的每个分辨率模型，都取一个屏幕误差阀值一般取4个像素，预先计算出当等于4个像素时，视点到blk的间隔 d，并保存在查找表中。当实时绘制时，根据视点到每个blk的间隔 查找表中的d，从而决定该blk的网格分辨率。2.2优点和缺乏Geipap算法的网格生成方式显然和RA算法以及基于四叉树的连续性LD算法大不一样。以基于四叉树的连续性LD算法为例，他是通过自顶向下的方式用四叉树递归地将地形分成一

6、个个小地形块，越往下细分，地形块的大小越小，直至不能细分。当视点发生改变时，所有的顶点都必须重新参与细分的递归运算，这种算法能根据实际情况最大程度确定整个地形的网格分辨率，但计算量很大，并且递归层次很多。而对于Geipap算法来说，当视点改变时，只需要判断可见的每一个blk的网格分辨率应该是多少，blk内部的顶点并不参与计算。虽然这种做法不能最大化减少进入渲染管道的顶点，减少三角形面片，但是增加的这些渲染顶点对现代图形卡来说是不会影响绘制速度的。相反，由于他减小了实时绘制时模型简化的计算复杂度，速度得到极大进步，所以他是符合现代图形卡硬件架构的地形绘制算法。此外Geiaap相对固定的三角形面片

7、组织方式，也使得进入固定渲染管线的顶点能更好的组织成三角形带，大大减少传入图形卡的顶点个数。但是，这种算法由于不是连续的LD算法，也就是说LD的粒度比较粗放，因此在blk的网格分辨率发生改变时，会产生网格形状的突变，使得在地形遨游时，图形过渡不自然。虽然通过屏幕投影误差来选择blk的网格分辨率可以使突变的效果有所减轻，但对用户来说比较明显。本文通过线性插值的思想，使层次过渡由突变转为逐步递进，极大减小了这方面的缺乏。3.1地形数据的总体组织和表示我们首先读入一个场景的DE数据(高程数据)，保存在一个顶点线性表中，然后把这个场景在xz平面上划分成均匀大小的多个blk。blk的大小按需求而定，其边

8、长满足，如99，1717，3333等。假如地势总体比较平坦，我们可以选得大一点，假如对地形的细节要求较高我们可以选得小一点。本文以1919作为blk的大校blk通过顶点索引所组成的三角形带描绘他负责的一片小的区域。整个场景用一棵完全四叉树把这些blks组织起来。实时渲染时完全四叉树负责场景的裁剪，决定哪些blks应该绘制，然后计算可见blk的网格分辨率，从而得到整个地形要渲染的三角形面片。其数据组织如图3所示。当地形是超大地形绘制时，我们采用文献5的方法，用多线程机制加上场景缓冲的方法实现大地形数据实时动态调入和管理。每一个场景作为动态加载单元，用一个缓冲区来管理，用单独线程来调度。3.2Bl

9、k多分辨率网格模型的构造和数据组织ille在他的论文中指出当细节层次不同时blk的顶点取舍方法，以及为了防止出现T型裂缝，blk的边界顶点应该怎么调整。本文试着在他的思想根底上，提出一种基于查找表的blk三角形带生成方法。我们把blk的中心地带和边界分开对待。在预处理阶段就生成五个顶点索引表。如图4所示。中心地带索引表负责生成blk中心的三角形条带，其索引参数就是自身的网格分辨率。边界索引表负责生成与其他blk相邻区域的三角形带防止T型裂缝。索引参数有三个：自身的网格分辨率，相邻的方向，相邻blk的网格分辨率。网格都使用三角形带(TriangleStrip)的方式生成，有些地方需要生成一些退化

10、三角形，用于三角形带的连接。运用三角形带的方式比三角形扇和纯粹三角形方式更能减少顶点个数，进步绘制效率。这五个索引表一起可以描绘任何一个blk中组成网格的所有顶点的相对位置在blk区域内的位置。在实时渲染的时候，针对一个特定的blk，我们可以根据这个blk在场景中的起始位置，他的网格分辨率，和他四周blk的网格分辨率，直接查表得到这个blk完好的三角形带顶点索引，减少了PU的判断和计算量。内存中只保存一个blk网格顶点的相对索引，不是整个场景的所有blk的顶点索引都保存，因此不会造成什么内存消耗。3.3利用线性插值逐步过渡不同分辨率的网格模型当blk的网格分辨率次发生变化时，其网格模型可能变化

11、较大，由于变化是在瞬间完成的，极易被观察者觉察。但假如我们把这种变化由突变改为渐变，用户就不易觉察，其视觉影响也就可以忽略不计。我们在预处理阶段已经得到一个适宜的查找表，可以查出blk的网格分辨率与blk到视点的间隔 d之间的对应关系。我们假设d=1000时=n+1，d=2000时=n。假如如今d=1500，那么网格的分辨率正处在n和n+1的过渡阶段。我们取网格顶点为=n+1时的索引，他比=n时多出一些细节顶点，对这些多出的细节顶点，我们对其高度进展线性插值，使其缓慢在分辨率n+1和分辨率n之间过渡。如图5，v3为高分辨率时出现的细节顶点，v4为模型在低分辨率时v3的初始点。随着网格向高分辨率

12、过渡，v4逐步过渡到v3。v的Y坐标由下面的公式决定：如图5所示。采用这种插值的手段后，只增加了很少的计算，视觉效果上却得到了很大进步。3.4利用显存保存地形的顶点表现代图形卡已经支持把一定大小经常使用的数据直接保存在显存中，所以假如我们把经常使用不频繁变动的数据保存在显存中，可以防止大量数据在渲染时频繁从内存传输到显存。在实验中通过penGL的VBVertexBufferbjet方式把顶点线性表数据保存在显卡中，经比较渲染速度大幅进步。3.5描绘算法的流程预处理阶段：(1)载入地形数据，初始化顶点线性表。(2)初始化所有分辨率的blk模型所对应的三角形带顶点索引表(见2.2)，此表保存的是组

13、成三角形带的相对顶点索引。生成描绘整个地形场景的blk数组，每个blk记录自身在场景中的绝对位置。(3)构造完全四叉树，每个子节点对应管理一片区域(一个或多个blk)，设置包围球半径。每个叶子节点都对应一个blk索引。实时绘制阶段：(1)遍历完全四叉树，根据视锥体裁剪算法，得到可见blk的索引。(2)计算这些blk的网格分辨率，根据分辨率和网格的三角形带索引表，顶点表，可以得到组成地形网格的所有三角形带顶点的完好信息。(3)根据3.3介绍的线性插值方法，调整相关顶点的高度信息。(4)送入渲染管道绘制。(5)重复(1)。我们使用大小为20492049的高程图作为实验数据，以Athln2500+，

14、DDR512，ATI9500，126显存作为硬件环境对上述算法进展测试。程序用V+penGL在inds平台上完成。其中分块大小为3333，共分5个细节分辨率，图6是场景绘制的网格形式截图。图6地形场景绘制截图表1地形绘制测试结果不使用简化模型基于四叉树的LD算法新算法三角形个数4096K10K11K帧数6FPS120FPS210FPS从表1中的技术参数统计来看，新算法的渲染效率有很大进步，能满足大规模地型的渲染要求。本文在Geipap算法的根底上，提出了一种生成分块网格模型的方案。用查找表方式生成三角形带来表示分块模型，大大减少PU计算，减少了传入渲染管道的顶点个数。此外，用插值法把网格模型的分辨率突变转换为逐步递进，改善了渲染图像质量。把常用的顶点保存在显存中，缓解了传输的带宽压力，极大进步了渲染速度。1HppeH.Vie-dependentRefineentfPrgressiveeshes.PreedingsftheASIGGRAPHnferenenputerGraphis.LsAngeles：APress，1997：189-1982DuhaineauarkA，linskyurray，SigetiDavidE，RAingTerrain：Real-tieptiallyAdaptingeshes.IEEEVisualizatin19