基于四叉树空间划分的地形实时渲染方法

地形是计算机图形的一个重要组成部分，而它又具有特殊的形态。地形往往覆盖面积极广，且精度要求很高，使得我们必须用许多多边形来描述。这样的特点使得我们不能像对待其他普通模型那样对待地形。要想实时地渲染地形，我们需要一些特殊的方法。

    地形渲染一直以来都是计算机图形学中一个重要的研究领域。并且在这一方面已经诞生了许多优秀的算法。其中包括基于体素的渲染方法，也有基于多边形的渲染方法。早期的游戏，如三角洲特种部队就是采用体素渲染法的成功例子。体素法类似光线追踪渲染，它从屏幕空间出发，找到地形与屏幕像素发出的射线交点，然后确定该像素的颜色。这种方法不依赖具体的图形硬件，整个渲染过程完全使用CPU处理，因此它不能使用现代硬件来加速，并且对于一个场景来说，往往不只是地形，还有其他使用多边形描述的物体，体素法渲染的图像很难与硬件渲染的多边形进行混合，因此这种方法现在用得极少。而多边形渲染方法则成为一种主流。选择多边形来描述和渲染地形有很多的理由和优点。最重要的是它能够很好地使用硬件加速，并且能够和其他多边形对象一起统一管理。

    已有大量优秀的基于多边形的地形渲染算法。比较经典的算法有M. Duchaineau等人提出ROAM算法。这个算法采用一棵三角二叉树来描述整个地形。一个地形在最初的层次上由两个较大的等腰直角三角形组成，这两个等腰直角三角形可以被不断地细分来展现地形的更多细节。每一次细分过程都向直角三角形的斜边的中点处增加一个由高程数据所描述的顶点，该点将所在的直角三角形一分为二，同时该算法也定义了一些规则来保证地形中不会因相邻两个三角形细节层次的不同而出现裂缝。这个算法已被许多游戏所采用。还有一类算法，通过将地形在X-Z投影面上不断地规则细分来得到不同的细节，这就是本文要介绍的四叉树空间划分算法。另外，最新提出的一个地形算法也不得不提，Hugues Hoppe在2004年提出的几何裁剪图方法(Geometry Clipmaps)，算法使用了最新硬件所支持的顶点纹理来定义地形的外观，并且对于距离摄影机不同远近的地方采用不同的纹理层，最大限度地使用硬件加速了地形渲染的过程。这个方法听起来非常美妙，但它目前只被较少的硬件支持。因为顶点纹理是Shader Model 3.0才支持的功能，也就是说只有DirectX 9.0c级别的显卡才能支持这种算法。这对于某些有普及性要求的图形应用程序，尤其是对游戏来讲不是一件好的事情。因此大多数人现在还在使用经典的地形渲染方法。

    首先，基于四叉树的地形渲染方法使用高程数据作为数据源。且算法要求高程数据的大小必须为2ⁿ+1的正方形。所谓高程数据，即色彩范围在0-255的灰度图片，不同的灰度代表了不同的高度值。如果某高程数据指出这个高程数据最高处的Y坐标值是4000，那么在高程数据中一个值为255的像素点就表示这个点所代表的地形区域的高度是4000，同理如果该像素值是127那么就表示这个点所代表的地形区域的高度是4000×(127/255)=2000。高程数据的每个像素都对应所渲染网格中的一个顶点。另外还有一个参数描述顶点与顶点之间的水平距离，以及一个描述最大高度的参数。因此地形的基本数据结构如下：

    struct Terrain
    {
        char **DEM; //一个描述高程数据的二维数组
        float CellSpace;
        float HeightScale; 
    }

    其中，各变量的具体意义如下图所示：

    有了这些参数，我们可以很容易地由高程数据的参数值得到它所表述的多边形网格。得到这个网格之后，可以简单地把它放入顶点数组，并为之建立一个顶点索引，就可以传入硬件进行渲染了。然而，事情并不是这么简单。对于较小尺寸的高程数据(如129×129)，这样做确实可行，但随着高程数据规模的增大，所需的顶点数和描述网格的三角形数会急剧膨胀。这个数值很快就会大到最新的显卡也无法接受。比如一个1025×1025的高程数据，我们需要1025×1025=1050625个顶点，以及1050625×2=2101250个三角形。就算你的显卡每秒能够渲染1000万个三角形，你也只能得到不到5fps的渲染速度，况且你的场景可能还不只包括地形。因此我们必须想办法在不影响视觉效果的情况下缩减所渲染的三角形数量，另外还应该注意一次性将最多的数据预先传给硬件以节约带宽。

    这里要讲解的算法，目的就是在不影响或在视觉可以接受的范围内缩减所渲染三角形的数量，以达到实时渲染的要求。根据测试，本算法在漫游大小为1025*1025的地形时速度稳定在150fps以上(在nVidia Geforce 6200 + P4 1.6GHz的硬件上得到)。

    由于地形覆盖范围广，但它的投影在XZ平面上均匀分布(以下采用OpenGL中的右手坐标系，Y轴为竖直向上的坐标轴)，因此我们有必要考虑对地形进行空间划分。正是由于这样的均匀分布，给我们的划分过程带来了便利。我们不需要具体地去分割某个三角形，只要选择那些过顶点且和X或Z轴垂直的平面作为划分面即可。例如对于一个高程数据，我们可以以坐标原点作为地形的中心点，然后沿着X轴和Z轴依次展开来分布各个顶点。如下如所示。

    首先，我们可以选择X=0和Z=0这两个平面，将地形划分为等大的四个区域，然后对划分出来的四个子区域进行递归划分，每次划分都选择交于区域中心点并且互相垂直的两个平面作为划分面，直到每个子区域都只包含一个地形单元块（即两个三角形）而不能再划分为止。例如对于上图所示9*9大小的地形块，经过划分之后如下图所示：

    由图可知，只有高程数据满足大小2ⁿ+1的正方形这个条件，我们才可能对地形进行均匀划分。我们可以把划分结果用一棵树来表述，由于每次划分之后产生四个子节点，因此这棵树叫四叉树。那么，这棵树中应该存储那些信息呢？首先对于每个节点，应该指定这个节点所代表的地形的区域范围。并不是把地形网格中实际的顶点放入树中，而是要在树中说明这个节点覆盖了地形的那些区域。比如一个子节点应该有一个Center(X,Y)变量，指定这个节点的中心点所对应的顶点索引，或编号。为了方便起见，可以把地形中心点编号为(0,0)然后沿着坐标轴递增。此外还要有个变量指定这个节点到底覆盖了地形的多少个顶点。如下图所示。

    我们目前的四叉树的数据结构如下：

    struct QuadTreeNode
    {
        QuadTreeNode *Children[4];
        int CenterX,CenterY;
        int HalfRange;
    }

    有了四叉树之后，如何利用它的优势呢？首先我们考虑简单的视见体裁剪(View Frustum Culling，以下简称VFC)。相信很多接触过基本图形优化的人都应该熟悉VFC，VFC的作用既是对那些明显位于可见平截头体之外的多边形在把它们传给显卡之前剔除掉。这个过程由CPU来完成。虽然简单，但它却非常有效。VFC过程如下：

    1.为每个节点计算包围球。包围球可以简单的以中心顶点为球心，最大坐标值点(节点所覆盖的所有顶点的最大X、Y、Z值作为此点的坐标值)到球心的距离为半径。

    2.根据当前的投影和变换矩阵计算此时可视平截头体的六个平面方程。这一步可以参考Azure的Blog上的一篇文章，这篇文章给出了VFC的具体代码。单击这里。

    3.从树的根结点以深度优先的顺序遍历树。每次访问节点时，测试该节点包围球与视见体的相交情况。在下面的情况下，包围球与视见体相交：

        1) 球心在六个平面所包围的凸状区域内部。
        2) 球心在六个平面所包围的凸状区域外部，但球心到某个平面的距离小于半径。

    4.如果相交测试显示包围球和视见体存在交集，继续递归遍历此节点的4个子节点，如果此节点已经是叶节点，则这个节点应被绘制。如果不存在交集，放弃这个节点，对于这个节点的所有子节点不再递归检查。因为如果一个节点不可见，那么其子节点一定不可见。

    这样，我们剔除了那些不在视见体内的地形区域，节约了一些资源。但这还不够。在某些情况下，VFC可能还会指出整个地形都可见，在这种情况下，将这么多三角形都画出显然是不可取的。

    因此还要考虑地形的细节层次(LOD)。我们应该考虑到，地形不可能所有部分都一样平坦或陡峭。对于平坦的部分，我们用过多的三角形去描述是没有意义的。而对于起伏程度较大的区域，只有较多的三角形数量才不让人感到尖锐的棱角。再者，无论地形起伏程度如何，那些距离视点很远的区域，也没有必要花费太多的资源去渲染，毕竟它们投影到屏幕上的面积很小，对其进行简化也是必要的。

    既然我们要对起伏程度不同的区域采用不同的细节级别，我们首先必须找到一种描述地形起伏程度的量。与其说起伏程度，不如说是地形的某个顶点因为被简化后而产生的误差。要计算这个误差，我们先要了解地形是如何被简化的。

    考虑下图所示的地形块，它的渲染结果如下图右图所示。

   现在如果要对所需渲染的三角形进行简化，我们可以考虑这个地形块每条边中间的顶点(下图左侧红色点)：

   如果将这些红色的顶点剔除，我们可以得到上图右边所示的简化后的网格。误差就在这一步产生。由于红色的顶点被剔除后，原本由红色顶点所表示的地形高度现在变成了两侧黑色顶点插值后的高度。这个高度就是误差。如下图。

    因此，对于每个节点，我们先计算这个节点所有边中点被删除后所造成的误差，分别记为ΔH1, ΔH2, ΔH3, ΔH4。如果这个节点包含子节点，递归计算子节点的误差，并把四个子节点的误差记为ΔHs1, ΔHs2, ΔHs3, ΔHs4。这个节点的误差就是这八个误差值中的最大值。由于这是一个递归的过程，因此应该把这个过程加到四叉树的生成过程中，并向四叉树的数据结构中加入一个误差变量。如下。

    struct QuadTreeNode
    {
        QuadTreeNode *Children;
        int CenterX,CenterY;
        int HalfRange;
        float DeltaH;  //节点误差值
    }

    下面来看一下地形的具体渲染过程。

    首先，我们位于四叉树的根结点。我们此时考虑根结点的误差，如果这个误差小于一个阈值，直接使用根结点的中心点以及此节点的四个边角点作为顶点渲染一个三角扇形，这个三角扇形就是渲染出来的地形。但是更经常的情况下，根结点的误差值是很大的，因此算法认为要对根结点进行细分，以展现更多细节。于是对于根结点的每个子节点，重复这个步骤，即检查它的误差值是否大于阈值，如果大于，直接渲染这个节点，如果小于，递归细分节点。目前我们的算法伪代码如下。

    procedure DrawTerrain(QuadTreeNode *node)
    {
      if (node->DeltaH > k)
      {
           for (i=0;i<4;i++)
           {
                DrawTerrain(node->Children[i]);//递归划分
           }
      }
      else
      {
           GraphicsAPI->DrawPrimitive(node);//以节点的中心点和四个边角点绘制三角扇形
      }   
    }

    这个伪代码在一个较高的层次上表述了算法的基本思想。然而我们还有许多问题要考虑。其一是目前我们仅仅考虑了地形的细节层次和地形表面起伏程度的关系，但还应该考虑地形块距离视点远近跟地形细节层次的关系。解决这个问题很简单，我们只需在伪代码的条件中加入距离这一因素即可。即把

        if (node->DeltaH > k)
        {
            ...
        }
        else ...

    改为：

        if (node->DeltaH / d > k)
        {
            ...
        }
        else ...

    其中d为节点中心点与视点之间的距离。而事实上，当细节程度与距离的平方成反比时，能够减少更多的三角形，而且视觉效果更好，只要阈值k设置得当，根本感觉不出地形因为视点的移动而发生几何形变。因此，我们最终的条件式为：

    node->DeltaH / d² > k

    还有一个很重要的问题，就是这个算法所产生的地形会因为节点之间细节层次的不同而产生裂缝。下图说明了裂缝的产生原因。

    有两个方法可以解决这个问题，一个方法是删除左侧节点中产生裂缝的顶点，使两条边能够重合。另一种方法是人为地在右侧地形块中插入一条边，这条边连接中心点和造成裂缝的顶点，从而消除裂缝。在渲染地形时，可以采取下面的办法避免裂缝的产生：

    1.在预处理阶段，为所有顶点创建一个标记数组，标记以该顶点为中心点的节点在某一帧是否被细分。如果被细分则标记为1，否则标记0。

    2.从根节点开始，以广度优先的顺序遍历四叉树，使用之前提出的条件式判断节点是否需要分割。如果公式表明需要分割，并且与节点相邻的四个节点的中心点都被标记为1，那么把这个节点及其四个子节点的标记设为1，并递归细分这个节点。否则，将这个节点的标记设为1，把这个节点的四个子节点的标记设为0，然后采用下面的方法绘制这个地形块：

        1)将节点的中心顶点和四个边角点添加到即将绘制的三角扇形列表中。
        2)依次检查与四条边相邻的节点的标记数组，如果相应的标记为1，那么将该点添加到三角扇形的顶点列表中，否则跳过该点。
        3)绘制三角扇形。

    我们最终的伪代码如下。

    另外，一个重要的优化是利用硬件的缓冲区或顶点数组(对于不支持顶点缓冲的硬件而言)。因为地形无论怎样简化，顶点数据总是固定不变的。我们在每一帧动态产生的仅仅是顶点索引，因此我们有必要实现将地形的所有顶点数据输入到顶点缓冲中，然后在渲染时一次性将所有的索引传给显卡，以提高速度。实验表明，使用顶点缓冲比直接使用glBegin/glEnd绘制图形要快5倍以上。

    以上讲述了如何做到实时地渲染大型地形。主要应用了LOD和VFC两种手段来精简三角形数量。然而VFC只能剔除不在视见体内的图形，而对于在视见体内但被其他更近的物体遮挡的情况却无能为力。如果要实现地形的自遮挡剔除，地平线算法是一个好的选择。然而当你的场景不仅仅是包含地形时，地平线算法也只能处理地形的自遮挡情况。因为地平线算法只对2.5D的地图(即在XZ平面上无重合投影的场景)有效。对于完全3D场景，地平线并不能很好的工作。所以当你在引擎中使用地形时，可以考虑将地形分块后放入场景的管理树中，如BSP或Octree等。然后根据引擎的性质使用入口(Portal)、PVS或者遮挡测试(Occlusion Culling)等方法进行遮挡剔除。值得强调的是，遮挡测试是一个非常灵活的实时的剔除算法，且无需任何预计算过程。但要想有效的实现它并不是一件容易的事。我曾将地形分块后使用遮挡剔除来完成地形的自遮挡，但是渲染速度不但没有提升，反而有轻微的下降。因此如果要使用遮挡剔除的话必须和引擎结合起来统一进行遮挡测试，才有可能提高效率。

    现在你应该了解了基本的地形实时渲染方法。要想让地形的外观更加真实，我们还需要更多的工作。我们需要为地形加上纹理贴图和光照。首先考虑地形的光照。由于地形的多边形网格是实时产生的，它会随着视点的移动而变化，因此如果你直接使用OpenGL内置的顶点光照，你会得到极度不稳定的光照效果。你会看到地形表面会因为你的移动而不断跳动。因此我们必须使用其他的光照方法来避免这个问题。我们想到了光照贴图。光照贴图是一个游戏中常用的光照技术。它是一个覆盖了场景中所有多边形的贴图。通过给贴图赋值，我们可以得到多边形表面复杂的光照效果。使用好的算法计算出来的光照贴图可以模拟极度逼真的光影效果。它给我们带来的视觉享受远远地超过了OpenGL的内置光照。有关光照贴图的计算可以参考我翻译的一篇文章：辐射度算法(Radiosity)

   

   你可以简单地为地形覆盖上单一的纹理，这看起来些许增加了地形的真实性：

    在上图中，我们创建了一个地形，并运用了一个重复的纹理。这个过程让地形的无论哪一个区域看起来都是一样的（例如都是草地）。这显然不太真实，也过于乏味。或许你会创建了一幅超大的图片，以拉伸覆盖的方式映射到地形表面。这样做的后果是内存开销过于庞大，这样做也很会受到硬件的限制。因此我们应该使用一种更好的纹理贴图方式，纹理索引贴图。

    纹理索引贴图对三个可重复的纹理进行索引贴图。所谓索引贴图，就是对三个可重复纹理进行索引，以决定地形的哪些区域需要使用哪些纹理的混合来贴图。因为对于任意的贴图，都由一组包含3个颜色通道（即R、G、B）的像素组成。用于索引的贴图的像素并不表示地形的某个区域的具体颜色，而是表示地形的某个区域用何种具体的纹理贴图。因为具体的纹理细节存储在这三个可重复的纹理中，因此索引贴图的贴图方式也为拉伸到地形表面，但它的分辨率可以大大降低。

    纹理索引贴图的工作方式如下：对于地形投影到屏幕上的像素，查找该像素所映射到索引贴图上的像素。然后根据这一像素R、G、B分量的不同，决定R、G、B分量所代表的具体纹理贴图的混合因子。根据这个混合因子混合三个可重复贴图后，将混合得到的最终颜色值输出到屏幕上。

    例如，令索引贴图的R分量代表沙滩的纹理，G分量代表草地，B分量代表岩石。如果索引贴图上一个像素的值是(0,255,0)，即绿色，则这个像素所对应的地形区域的具体纹理就为草地。如果该像素颜色值是(127,127,0)，即黄色，则该像素所对应的地形区域的纹理为草地和沙滩的混合，看起来既有草，又有沙。又如下图显示了一个样本索引贴图，以及使用该贴图索引纹理之后的渲染效果。

    原理很简单，下面讲解一下具体的实现过程。首先，我们准备4个纹理，其中1个纹理索引贴图，它将被拉伸覆盖整个地形，然后3张细节贴图，并将它们绑定到相应的纹理通道上。然后使用Vertex Shader为每个顶点自动计算索引贴图的纹理坐标，在Fragment Shader里，对索引贴图进行纹理查找，使用查找得到的颜色值的RGB颜色信息混合3张细节贴图，得到当前像素的颜色。最后还应该把这个颜色和光照贴图中的值相乘，得到最终的结果。下面是相关的Shader代码，使用GLSL编写。

    最后，如果你对本文有不解之处，欢迎和我共同讨论。

posted on 2008-05-11 13:54 RedLight 阅读(1313) 评论(1)  编辑 收藏 引用 所属分类: 3D渲染技术