大规模室外地形的实时渲染

1、2011年10月一、海量地形数据的存储二、LOD算法三、四叉树结构四、四叉树结构中的LOD算法五、地形裂缝的消除六、几何突变问题七、实例展示一、问题的由来 在FPS（第一人称视角）和MMORPG（大型多人在线角色扮演）游戏中几乎都存在室外场景，虽然很多游戏对室外场景大小的要求并不高，但设计一个具有无限大小的室外游戏场景仍是非常重要的。 对于一个100Km*100Km的地形而言，如果以每个网格0.1m*0.1m来计算，则需要存储：10000*10000=1亿个点的高程数据。如果直接将这么多的数据春放在计算机内存中，则对计算机内存和显卡的要求将非常高，且会极大的影响图形显示的速度。事实上，在游戏过

2、程中，人的视角是有限的，不可能一览100Km* 100Km大小的地形，因此直接显示在计算机屏幕上的区域事实上很有限。 那么如果来存储这些地形数据，以及如何读取以及何时读取这些地形数据呢？二、数据的分块存储 从下面的图形可以看到，人在浏览三维游戏场景时，往往只能看到整个场景的一部分（下面的2幅截图在不同时刻截取，其内容各不相同），也就是说在视频显示时实际上只能显示图形区域的一部分。这样就没有必要将整个场景的数据一次性的读入到内存中，而只需要将视觉范围内的数据读入到计算机内存即可。当然，当人的视点移动时，就需要更新相应的数据。二、数据的分块存储 从下面的图形可以看到，人在浏览三维游戏场景时，往往只

3、能看到整个场景的一部分（下面的2幅截图在不同时刻截取，其内容各不相同），也就是说在视频显示时实际上只能显示图形区域的一部分。这样就没有必要将整个场景的数据一次性的读入到内存中，而只需要将视觉范围内的数据读入到计算机内存即可。当然，当人的视点移动时，就需要更新相应的数据。 这样可能也存在一个问题，当人的视点频繁移动时，会不停的从磁盘中读取数据。由于磁盘读取数据所花的时间比较长，因此会严重削弱地形绘制的实时性。可采用如下方式提高数据读取的速度： （1）对数据进行分块存储，将人的视点所能观察到的范围的数据作为一块，并将整个地形分成若干个这样的块，以块为单位进行存储。如下图所示。MNOPQ1LC2K

4、B3JI4YXDERAFSHGTWVU56789 当人的视点停留在区域A时，其视觉范围不会超过AI之间的区域。因此只要判断视点所在的区域就可以确定读入到内存中的数据块。在上图中，如果视点在A所在的区域，则需要将AI所指示的区域的数据读入到内存中。同时由于相邻的9个数据块可分成3组，分别是C、D、E；B，A，F；I，H,G。组内的块均相邻，每块的数据连续存储，因此减少了数据读取的时间。 （2）双缓存技术。为了进一步减少读取数据的时间。当视点在A区域内时，可以事先将AI的数据放到显存中，以便显示，并开辟一个数据读取线程，读取磁盘中的JY数据块的数据并保存在内存中。当视点从A区域移动到I区域时，则将

5、显存中K，J，Y，X，W区域的数据取代原来用于保存C、D、E、F、G区域的数据，同时从磁盘中读取19的数据取代原内存中MU的数据。这样能够保证数据读取的实时性。在这里需要注意的是，在每从磁盘中读取一块数据时，需要计算该数据块在文件中的偏移地址，同时还应计算其在内存中的偏移地址，以便实现正确的交换；同样，从内存交换到显存也应该计算其交换地址。 上述处理方法不仅可用于游戏中设计大型的场景，在虚拟现实，GIS等领域也可使用。 不过，在一些游戏中，比如空战游戏，视点往往会发生变化，其视角所能观察的范围也会发生变化。有些时候视角很大，所观察的区域也很大，如果按照上述方法将所有的物体均按照其原来的的大小全

6、部放入显存进行渲染，则会极大的影响显示的速度。但事实上，在视点距离物体较远时，玩家根本无法区分物体的细节，也就没有必要用相同的点来描述物体。因此可以对距离玩家较远的物体进行模型简化，有的甚至可以用一个点来表示，这样就可以使得需要渲染的三角面数量减少，从而提高渲染的速度。在DirectX 3D中，专门提供了一个ID3DXPMesh的接口，该接口可通过其提供的方法减少或增加构成物体网格的面片数，从而实现不同细节层次下的网格。如下图所示。 上述接口对于单个的模型而言没有任何问题，而且恰当地选择细节层次模型能在不损失图形细节的条件下加速场景显示，提高系统的响应能力。选择的方法可以分为如下几类：一类是去

7、掉那些无法用图形硬件绘制的细节，如基于距离和物体尺寸标准的方法。另一类是去掉那些人类视觉觉察不到的细节，如基于偏心率，视野深度，运动速度等标准的方法。此外还有一种方法考虑的是保持恒定帧率。 （1）剔除法 在一些特定的情况下，场景中的一部分几何形体是什么时候都无法被观察者看到的。在此情况下，图形系统不再绘制这部分物体。 （2）距离标准 这种方法考虑的是物体到观察者的距离。这个距离是从视点到物体内指定点的欧氏距离。这种方法的理论依据是当一个物体距离视点越远，此物体能够被观察到的精细的细节部分就越少。这就意味着选择较粗糙的细节层次来表示物体不会对显示的逼真度有很大影响。 （3）尺寸标准 这种方法利用

8、了人眼辨识物体的能力随着物体尺寸的减小而减弱的特性。它考虑到待表示物体的尺寸，较小的物体用较粗糙的细节层次，较大的用较精细的细节层次。 （4）偏心率 此方法利用了人眼辨识物体的能力随着物体逐渐远离视域中心而减弱的特性。视网膜的中心对物体细节的分辨能力较强，视网膜边缘的分辨能力较弱。根据这个原理，将显示的场景分为具有较精细细节层次的中心部分（对应于眼睛视域的中心）和外围部分（对应于视域的外围部分）。 （5）视野深度 这种方法根据观察者眼睛的焦距来为物体选择合适的细节层次。在聚焦区域的前面或者后面的物体不被聚焦。 （6）运动速度 该方法是根据物体相对于观察者视线的角速度选择合适的细节层次。在屏幕上

9、快速运动的物体看起来是模糊的，这些物体只在很短的时间内被看到，因而观察者可能看不清它们。这样就可以用较粗糙的细节层次来表示它们。 LOD模型的生成可采用如下的算法： （1）近平面合并法 采用几何优化方法检测出共面或近似共面的三角面片，将这些三角面片合并为大的多边形，然后用较少数目的三角形将这个多边形重新三角化。这个方法的步骤是：A、迅速地将面片分类为近似共面的集合；B、快速合并这些集合中的面片；C、简单而且鲁棒的三角化。面片分类依据的是他们的各自的法线之间的夹角。该算法的误差衡量标准可以归为全局误差，但是由于它仅仅依据法线之间的夹角，它的误差评估准确性较差。它不能保证一定误差限制。 （2）几何

10、元素（顶点/边/面）删除法 几何元素删除法通过删除满足距离或者角度标准的顶点来减小三角网格的复杂度。删除顶点留下的空洞要重新三角化填补。该算法速度快，但不能保证近似误差。它估算局部误差，未考虑新面片同原始网格的联系和误差积累。 （3）重新划分算法 重新划分算法先将一定数量的点分布到原有网格上 ,然后新点与老顶点生成一个中间网格 ,最后删除中间网格中的老顶点 ,并对产生的多边形区域进行局部三角化 ,形成以新点为顶点的三角形网格 。其中分布新点采用排斥力算法 ,即先随机分布新点 ,然后计算新点之间的排斥力 ,根据排斥力在网格上移动这些新点 ,使它们重新分布 。排斥力的大小与新点之间的距离、新点所在

11、三角形的曲率和面积有关。这种方法对那些较光滑的模型是很有效的 ,但对于那些不光滑的模型 ,效果较差; 由于根据排斥力重新分布新点 ,涉及到平面旋转或投影 ,计算量和误差都较大。（4）聚类算法 聚类算法通过检测并合并相邻顶点的聚类来简化网格。每个聚类被一个代表顶点取代，这个代表顶点可能是顶点聚类的中心或者是聚类中具有最大权值的顶点（定义顶点的权值是为了强调相对的视觉总要性）。然后，去处那些由于聚类操作引起的重叠或者退化的边或者三角形。算法简化引入的误差由用户定义的准确度控制，这个标准用来驱动聚类尺寸的选择。该算法实现简单、速度快，但是没有考虑到保持原始网格的拓扑和几何结构，有可能生成非常粗糙的近

12、似网格。 （5）小波分解算法 小波分解算法使用了带有修正项的基本网格，修正项称为小波系数，用来表示模型在不同分辨率情况下的细节特征。算法的三个主要步骤： 分割：输入网格M被分成一些（数目较少）三角形的区域T1,.,Tn, 由此构成的低分辨率三角网格称为基本网格K0。 参数化：对于每个三角区域Ti，根据它在基本网格K0上相应的表面进行局部参数化。 重新采样：对基本网格进行j次递归细分就得到网格Kj，并且通过使用参数化过程中建立的参数将Kj的顶点映射到3维空间中得到网格Kj的坐标。 此算法可以处理任意拓扑结构的网格，而且可以提供：有界误差、紧凑的多分辨率表示和多分辨率尺度下的网格编辑。 四叉树是指

13、每个结点有四个孩子结点，如下图所示。123456789101112131415161718192021 显然每一个结点都有四个指向孩子的结点，同样如果为了能够很好的寻找其双亲结点，还可以为每个结点增加一个指向其双亲结点的指针。除上面的指针之外，还应包含其他一些属性，比如该结点处于那一层，该结点是否是叶子结点，该结点在遍历是是否访问过，该结点是否可见等信息。当用于描述3D空间中的某个顶点时，还应包含该结点的顶点坐标等信息。 在地形生成过程中，需要用四叉树来表示地形网格的划分情况。四叉树第一层四叉树第二层四叉树第三层 在上面的图形中，第一层为根，只有一个结点，包含四个顶点的坐标，顶点的法线以及顶点

14、的纹理坐标，颜色等属性以及指向四个孩子结点的指针和一个指向双亲结点的指针。第二层有四个结点，每个结点同样包含上述内容。这样一层一层细分，就可形成细密的网格。如果绘制的网格由同一层的顶点构成，则网格的密度均匀。如果最终构成的图形不是由同一层的网格构成，则网格将不均匀。如下图所示。 其对应的四叉树结果如下图所示。绘制的时候只绘制叶子结点，而非叶子结点则不绘制。从下图可以看到，该四叉树结构可以表示不同密度的网格。而这正是为什么在地形绘制中采用四叉树的原因。12345101112131415161718192021 从前面的描述可以看出，可以用四叉树来表示准确表示不同密度的地形。结合前面介绍的LOD算

15、法，便可以用四叉树的结构来实现LOD算法。 在LOD算法中需要解决结点的评价问题，也就是说在四叉树中，某个结点是否应该被显示。某个结点是否被显示可依据其距离视点的远近来判断，如果该结点距离视点很近，则应该被显示，反之则可以被忽略。 在评判的过程中，如果全部采用结点评价，则运算复杂度较高。可采用基于块的简化准则。也就是判断某一块（四叉树中的一个结点）是否需要简化，如果需要简化，则采用细节层次较低的结点来表示，否则对其进行网格划分。判断的方法是： 首先计算某地形块的粗糙度u,其计算公式如下： min)maxmin)(max() (maxminmaxmin2,yyxxzzuxxyyyx 其中xmax

16、表示该地形块中所有点x的最大值，xmin表示该地形块中所有点x的最小值。Ymax表示该地形块中所有点y的最大值，ymin表示该地形块中所有点y的最小值。Zx,y表示点(x,y)的Z坐标的值。Z表示该地形块中所有点的Z坐标值的平均值，可通过下面的公式计算得到：min)maxmin)(max(maxminmaxmin,yyxxzzxxyyyx 粗糙度的计算与地形本身有关，可以在构造四叉树时计算获得。判断该块是否应该简化则需要通过下面的方法来进行判断： 如果u*L/dc则该地形需要简化，反之则应该进行网格划分。 其中d表示视点距离该块中心点的位置，L表示地形块的边长。C为某一常数，可根据用户的感观来

17、设置该值。 确定了评价原则之后，实际上就可以从四叉树的根节点开始，判断每个结点是否需要网格划分，如果需要，则用下一层的结点取代；如果不需要则直接用该层的结点来显示即可。 通过上面的处理之后，就会出现下面这种类型的图形。 仔细观察上面的图形，会发现依照这样的网格绘出来的图形可能会出现下面的裂缝。 图中红线所围部分即为裂缝发生的区域，产生的原因在于P点和M点可能不在NM和MH线段上。从而产生一个新的三角形区域。而这个三角形没有绘制的，从而出现黑色的裂缝。PMHMNAB 如何消除所出现的裂缝呢？首先裂缝的出现一定是这些要显示的结点处于不同的层。从四叉树的构造结构可以看出，四叉树同一层的1右边的结点为

18、2，下边的结点为3，3右边的为4,上边的结点为1,2左边的结点为1，下边的结点为4,4左边的结点为3，上边的结点为2；不同层右边相邻的结点为1、3结点，左边相邻的结点为2、4结点。上边相邻的结点为3,4结点，下边相邻的结点为1,2结点。注意这儿指的是层次低的与层次高的之间的对应关系。 由于结点2与结点3、4相邻，而3、4在LOD地形中显示的结点与2不处于同一层，这样就需要查找结点2相邻的且处于不同层的结点。本例中2与结点18、20、8、10、11相邻，结点7与19,21相邻等。123456789101112131415161718192021 可通过下述方法来判断是否存在裂缝： （1）如果与某

19、结点处于同一层的上下左右结点均为叶子结点（不存在的结点除外），则该结点与周边结点不存在裂缝。 （2）如果上述条件不存在，则一定存在裂缝。 如何查找与裂缝相关的点呢？首先查找的范围只限于叶子结点，且查找应该从层级最高的开始查找，依次进行。可通过如下方法来获取： （1）如果该结点相邻的右边的结点存在，且不是叶子结点，则查找其子树中结点编号为1、3的结点，如果其中有叶子结点则保存，如果没有继续查找其子树的1、3结点，直到有叶子结点为止，并保存。这样就找到与其相邻的右边的结点中所有的结点。 （2）同样对于该结点的左边的结点则查找2、4结点。下边的结点则查找1、2结点；上边的结点则查找3、4结点。 （3）对于层级最低的结点不做上述查找。 通过上述的处理后可以找到所有存在裂缝的结点集。对每一个这样的集合做如下的处理即可消除裂缝。 （1）删除裂缝中最长的那条边。该边一定存在在层级较低的结点中。比如在上面的例子中，结点2与其他结点存在的裂缝中最长的便即为结点2中第