连载三：3D游戏引擎中的室外大场景渲染技术研究与实现

　　3.5游戏中地形绘制更好的方案.

　　随着图形卡数据吞吐能力的不断提高，每秒钟处理上亿个三角形己不再困难。很多计算，比如几何变换和光栅处理都可以交给GPU去计算。所以在GPU数据吞吐量很大的情况下，如果一个算法在剔除渲染顶点的过程中占用了太多CPU资源，出现GPU等待CPU的情况，那么即使算法在剔除多余顶点方面做得很好，总体绘制效率也不是高效的。上面讨论的两种动态LOD算法(RoAM和基于四叉树的动态LOD)都存在这方面的缺陷。并且，受硬件带宽的限制，频繁地传输海量顶点数据，使得时间集中消耗在数据“迁移"过程中。过多的DP(Draw Primitive)也使得图形卡不能发挥最大功效，造成资源极大浪费。所以要适应现代图形卡的硬件架构，算法必须改进，几何多重映射(GeoMipMap，Geometrical Mipmapping)等算法由此产生。

　　本设计在GeoMipMap算法的基础上，改进了原算法关于抑制不同细节分辨率模型之间突变的处理方法，使得在提高绘制效率的同时，保证了绘制图形的质量。通过使用查表法的分块网格顶点数据组织方式，使得CPU的工作进一步减轻。此外，本设计还利用了现代图形卡的存储功能来优化地形的绘制。

　　3.5.1 GeoMipMap算法

　　●基本思想

　　GeoMipMap算法是Willem根据纹理多重映射的概念提出的H3，他把整个地形场景在XZ平面上进行分块(block)，比如用33×33的block把1025X 1025的地形表示为32×32个block。每个分块可用不同分辨率的网格模型来描述。在同一分块内，网格模型的分辨率相同。采用隔行采样的方式生成不同分辨率的网格。整个地形的模型表示和组织如图3.9所示：

　　不同的block之间互相拼接时，如果分辨率不同则可能产生裂缝。为了消除裂缝，在较高分辨率的block边界上，忽略一些点作为网格顶点，如图3.10所示：

　　每个block分辨率是通过屏幕空间误差H3来决定的。在地形数据预处理阶段，取一个屏幕误差阀值￡(一般取4个像素)，预先计算出当e等于4个像素时，视点到block的距离d和相应的block分辨率，并保存在查找表中。当实时绘制时，根据视点到每个block的距离查找表中的d，查找决定该block的网格分辨率。

　　●优点和不足

　　GeoMipMap算法的网格生成方式显然和ROAM算法以及基于四叉树的连续性LOD算法大不一样。以基于四叉树的连续性LOD算法为例，他是通过自顶向下的方式用四叉树递归地将地形分成一个个小地形块，越往下细分，地形块越小，直至不能细分。当视点发生改变时，所有的顶点都必须重新参与细分的递归运算，这种算法能根据实际情况最大程度确定整个地形的网格分辨率，但计算量很大，并且递归层次很多，CPU的负载极大。而对于GeoMipMap算法来说，当

　　视点改变时，只需要判断可见的每一个block的网格分辨率应该是多少，block内部的顶点并不参与计算。虽然这种做法不能最大化减少进入渲染管道的顶点，减少三角形面片，但是增加的这些渲染顶点对现代图形卡来说是不会影响绘制速度的。相反，由于他减小了实时绘制时模型简化的计算复杂度，速度得到极大提高，所以他是符合现代图形卡硬件架构的地形绘制算法。此外GeoMiaMap相对固定的三角形面片组织方式，也使得进入固定渲染管线的顶点能更好的组织成三角形带，大大减少传入图形卡的顶点个数。

　　但是，这种算法由于不是连续的LOD算法，也就是说LOD的粒度比较粗放，因此在block的网格分辨率发生改变时，会产生网格形状的突变，使得在地形漫游时，图形过渡不自然。虽然通过屏幕投影误差来选择block的网格分辨率可以使突变的效果有所减轻，但对用户来说仍比较明显。本设计通过线性插值的思想，使层次过渡由突变转为逐步递进，极大减小了这方面的不足。

　　3.5.2 GeoM i pMap优化算法

　　·地形数据的总体组织和表示

　　我们首先读入一个场景的高度图数据(heightmap)，保存在一个顶点线性表中，然后把这个场景在XZ平面上划分成均匀大小的多个block。block的大小按需求而定，其边长满足2l+l，如9×9，17×17，33×33等。如果地势总体比较平坦，我们可以选得大一点，如果对地形的细节要求较高我们可以选得小一点。本文以17×17作为block的大小。block通过顶点索引所组成的三角形带描述他负责的一片小的区域。整个场景用一棵完全四叉树把这些blocks组织起来。实时渲染时完全四叉树负责场景的裁剪，决定哪些blocks应该绘制，然后计算可见block的网格分辨率，从而得到整个地形要渲染的三角形面片。其数据组织图如下所示：

　　用面向对象的方式描述地形对象：

　　当地形是超大地形绘制时，我们采用多线程机制加上场景缓冲池的方法实现大地形数据的动态调入和管理。每一个场景Tile作为动态加载单元，用一个缓冲池来管理，用单独线程来维护。详细讨论在3.7节。

　　· block多分辨率网格模型的构造和数据组织

　　Willem在他的论文中指出当细节层次不同时block的顶点取舍方法，以及为了避免出现T型裂缝，block的边界顶点应该怎么调整。在他的思想基础上，本设计提出一种基于查找表的block三角形带生成方法。

　　我们把block的中心地带和边界分开对待。在预处理阶段就生成五个顶点索引表。如图3.12所示：

　　中心地带索引表负责生成block中心的三角形条带，其索引参数就是自身的网格分辨率。边界索引表负责生成与其他block相邻区域的三角形带(防止T型裂缝)。索引参数有三个：自身的网格分辨率，相邻的方向，相邻block的网格分辨率。

　　网格都使用三角形带(Triangle Strip)的方式生成，有些地方需要生成一些退化三角形，用于三角形带的连接。运用三角形带的方式比三角形扇和纯粹三角形方式更能减少顶点个数，提高绘制效率。

　　这五个位置的网格所关联的索引表一起就能够描述任何一个block网格所有顶点的相对位置(在block区域内的位置)。在场景渲染初始化时，我们读入block的五个LOD顶点索引表，得到block的不同分辨率网格。在实时渲染的时候，针对一个特定的block，我们可以根据这个block在场景中的起始位置，他的网格分辨率，和他四周block的网格分辨率，直接查表得到这个block完整的三角形带顶点索引，减少了CPU的判断和计算量。内存中只保存一个block网格顶点的相对索引，不是整个场景的所有block的顶点索引都保存，因此不会造成什么内存消耗。

　　· 用面向对象的方式来描述block

　　block是本算法很重要的对象，可以描述如下：

　　· 利用线性插值逐步过渡不同分辨率的网格模型

　　当block的网格分辨率次发生变化时，其网格模型可能变化较大，由于变化是在瞬间完成的，极易被观察者察觉。但如果我们把这种变化由突变改为渐变，用户就不易察觉，其视觉影响也就可以忽略不计。

　　我们在预处理阶段已经得到一个合适的查找表，可以查出block的网格分辨率c与block到视点的距离d之间的对应关系。我们假设d=lOOOm时c=n+l，d=2000m时c=n。

　　如果现在d=1500m，则网格的分辨率正处在n和n+l的过渡阶段。我们取网格顶点为c=n+l时的索引，他比c=rl时多出一些细节顶点，对这些多出的细节顶点，我们对其高度进行线性插值，使其缓慢在分辨率n+l和分辨率rl之间过渡。如图3.13，v3为高分辨率时出现的细节顶点，v4为模型在低分辨率时v3的初始点。随着网格向高分辨率过渡，v4逐步过渡到v3。v’的Y坐标由下面的公式决定：

　　如3.13图：

　　采用这种插值的手段后，只增加了很少的计算，视觉效果上却得到了很大的提高。

　　·利用显存保存地形的顶点表

　　现代图形卡已经支持把一定大小经常使用的数据直接保存在显存中，所以如果我们把经常使用不频繁变动的数据保存在显存中，可以避免大量数据在渲染时频繁从内存传输到显存。在实验中通过0penGL的VBO(Vertex Buffer Object)方式把顶点线性表数据保存在显卡中，经比较渲染速度大幅提高。

　　·描述算法的流程

　　预处理阶段：

　　(1)载入地形数据，初始化顶点线性表。

　　(2)初始化所有分辨率的block模型所对应的三角形带顶点索引表，此表保存的是组成三角形带的相对顶点索引。生成描述整个地形场景的block数组，每个block记录自身在场景中的绝对位置。

　　(3)构造完全四叉树，每个子节点对应管理一片区域(一个或多个block)，设置包围球半径。每个叶子节点都对应一个block索引。实时绘制阶段：

　　(4)遍历完全四叉树，根据空间裁剪算法，得到可见block的索引。

　　(5)计算这些block的网格分辨率，根据分辨率和网格的三角形带索引表，顶点表，可以得到组成地形网格的所有三角形带顶点的完整信息。

　　(6)根据前面介绍的线性插值方法，调整相关顶点的高度信息。

　　(7)送入渲染管道绘制。

　　(8)回到(4)。

　　●测试结果

　　我们使用大小为2049×2049的高程图作为实验数据，以Athlon2500+，DDR IG，ATI 9550，128M显存作为硬件环境对上述算法进行测试。程序用VC+OpenGL在windows平台上完成。其中分块大小为17×17，共分4个细节分辨率，以下是场景绘制的网格形式截图：

　　从表3.1中的技术参数统计来看，新算法的渲染效率有很大提高，能满足大规模地型的渲染要求。