2.11 创建一个ROAM地形

问题

虽然你可以使用前一个教程的四叉树技术让XNA只绘制在相机视野中的地形小块，这个方法还不是最好的。那些远离相机的方块仍会以离相机很近的方块的同样细节进行绘制，而有些三角形在屏幕上的绘制大小不超过一个像素。

因此，你想使用Lecvel-Of-Detail(LOD)方法让远离相机的方块以低细节绘制，当使用不同的细节层次绘制地形时，你会发现在边界上会出现破裂。

译者注：ROAM是Real-Time Camera-Dependant Optimally Adapting Mesh的缩写，可翻译为依赖相机的实时优化网格。

解决方案

本教程介绍一个强大的技术，这个技术从覆盖整个屏幕的两个三角形开始。在算法的迭代中，每个三角形计算离开相机的距离并判断它是否需要分割成两个三角形，最后，你获得一个最匹配当前相机位置的网格。

只要相机的位置或旋转发生改变就需要更新这个地形网格，要对相机的新状态保持优化，每个三角形还需要判断是否需要和邻近的三角形合并以再次减少细节层次。

工作原理

本教程的目标是从覆盖整个屏幕的两个三角形开始，创建一个算法让每个三角形可以根据相机判断是否需要分割或合并。

在实际开始之前，你需要找到一个三角形布局可以很容易地进行分割和合并。针对处理地形的情况，我使用一个基于方块的固定网格。如果你将这个由两个三角形组成的方块分割以增加细节时，每个方块需要被分割成由8个三角形组成的4个方块，如图2-14的右图所示。添加额外的六个三角形是前进过程中的一大步。

图2-14 在基于方块的布局中增加细节层次

但是两个方块的边界处会出现破裂，如图2-15所示。显示了图2-14右图的3D表示，你需要进行拼接修复这个破裂，这并不简单。

图2-15 基于方块的地形的不同细节层次会产生破裂

因此，这个教程会使用一个不同的三角形布局，不是处理每个方块，而是处理每个三角形。当一个三角形需要增加细节层次时，你只需将它分割成两个，如图2-16所示。这可以让你将两个三角形变成四个三角形。

图2-16 基于三角形布局增加细节层次 这个分割不会导致破裂。

在某些情况中，你可以继续使用这个方式分割三角形而不会产生破裂。例如，图2-17左图显示了另三个安全的分割。

图2-17 三个安全的分割（左），导致出现破裂的一次分割

但是，图2-17的右图显示了将三角形B分割成C和D会导致地形上出现破裂。图2-18显示了这个破裂的3D显示。

图2-18 由基于三角形布局的不同细节层次引起的破裂

幸运的是，你可以避免这个情况的发生，要避免在分割三角形时出现破裂，你可以进行以下操作：

• 确保父三角形也被分割
• 将共享长边的三角形也进行分割

图2-19显示了分割三角形A的过程。在左上图中，虚线表示你想进行的分割。根据第二条规则，共享长边的三角形（三角形B）需要首先被分割，如右上图的虚线所示。但是，根据第一条规则，在分割三角形B之前，你需要首先将三角形B的父三角形（三角形D）分割成B和C，如左中图的虚线所示。但在分割D之前，你需要首先分割三角形E。幸运的是，三角形E没有父三角形，所以你可以分割三角形E，之后分割D，如中右图所示。现在可以安全地分割B，如下左图所示，最后分割A，如下右图所示。

图2-19 在逐三角形布局中的分割过程

这就是分割过程。要使地形在相机移动时保持最优化（即使用尽可能少的三角形），除了可以分割三角形还需要可以合并它们。当两个三角形A和B合并在一起时，对面的两个三角形C和D也应该合并以避免产生破裂，如图2-20所示。

图2-20 逐三角形布局的合并过程

初始化

现在开始编写代码。首先加载包含高度图的图像并基于这个图像创建一个VertexBuffer。在这个教程中，图像的长和宽必须是（2的整数幂+1）。你要么创建一个这个大小的高度图，要么开始时使用大小为2的整数幂的高度图，然后手动添加最后一行和一列。为了将注意力放在后面的操作上，本教程假设你使用的就是（2的整数幂+1）大小的高度图，虽然你也可以在本教程的代码中发现LoadHeightDataAndCopyLastRowAndColumn方法。

在LoadContent方法中添加以下代码，加载图像并创建对应的VertexBuffer，解释可见教程5-8：

Texture2D heightMap = Content.Load<Texture2D>("heightmap");
heightData = LoadHeightData(heightMap);

myVertexDeclaration = new VertexDeclaration(device, VertexPositionNormalTexture.VertexElements);
VertexPositionNormalTexture[] terrainVertices = CreateTerrainVertices();
int[] terrainIndices = CreateTerrainIndices();
terrainVertices = GenerateNormalsForTriangleStrip(terrainVertices, terrainIndices);
terrainVertexBuffer = new VertexBuffer(device, VertexPositionNormalTexture.SizeInBytes * terrainVertices.Length, BufferUsage.WriteOnly);
terrainVertexBuffer.SetData(terrainVertices);

Triangle类

你将创建一个Triangle类，它用来自己进行判断并作出动作。通过右击解决方案管理器中的项目并选择Add→New Item在你的项目中创建一个新类。在对话框中选择Class，命名为Triangle.cs。

首先需要定义一些变量，这些变量存储三个邻近、子和父的链接。

Triangle lNeigh;
Triangle rNeigh;
Triangle bNeigh;
Triangle parent;
Triangle lChild; 
Triangle rChild;

图2-21显示了它们之间的关系。

图2-21 三角形之间的关系

你还需要另外一些变量：

Vector3 lPos;
Vector3 apexPos;

int tInd;
int lInd;
int rInd;

public bool splitted = false;
public bool addedToMergeList = false;

两个Vector3保存left点和right点的3D位置（见图2-21），用来判断是否需要分割这个三角形。索引用来绘制三角形。Spiltted表示三角形是否分割，addedToMergeList用来确保某些计算不要在同一个三角形上重复两次。

还有一些变量在构造函数中定义，构造函数在创建一个新的Triangle对象时调用：

public Triangle(Triangle parent, Vector2 tPoint, Vector2 lPoint, Vector2 rPoint, float[,] heightData)
...{
    int resolution = heightData.GetLength(0);
    tInd = (int)(tPoint.X + tPoint.Y * resolution);
    lInd = (int)(lPoint.X + lPoint.Y * resolution);
    rInd = (int)(rPoint.X + rPoint.Y * resolution);

    lPos = new Vector3(lPoint.X, heightData[(int)lPoint.X, (int)lPoint.Y], -lPoint.Y);
    Vector2 apex = (lPoint + rPoint) / 2;
    apexPos = new Vector3(apex.X, heightData[(int)apex.X, (int)apex.Y], -apex.Y);

    this.parent = parent;
    if (Vector2.Distance(lPoint, tPoint) > 1)
    ...{
        lChild = new Triangle(this, apex, tPoint, lPoint, heightData);
        rChild = new Triangle(this, apex, rPoint, tPoint, heightData);
    }
}

如你所见，当创建一个新Triangle对象时，需要指定它的父、左上点和右上点。而且，因为三角形结构用来绘制一个地形，它的每个点都代表一个3D点。所以当创建一个Triangle对象时，你还需要指定一个包含整个地形高度值的2D数组。这个数组首先用来获取三个角的索引（可见教程5-8学习如何获取一个网格顶点的索引），然后是对应左边角和中心点的3D位置。

最后，存储指向父三角形的链接，检测当前三角形是否可以分割。如果三角形足够大，你将创建两个子三角形并存储它们的链接。注意，中心点就是两个子三角形的顶部的点，可参见图2-21。

定义两个基三角形

定义了Triangle类的通用结构后，你就做好了定义两个基三角形的准备，这两个基三角形覆盖整个屏幕。首先在第一帧绘制这两个三角形。然后，但调用Update方法时，判断是否需要分割前一帧绘制的三角形。因此，你需要保存当前绘制的三角形的集合。在代码顶部添加这行代码：

List<Triangle> triangleList; 

然后转到LoadContent方法的最后，在那里我们将创建Triangle结构。首先定义一个resolution变量，它只是一个调试变量。通常，你想绘制一个与高度图一样大小的地形，但在调试时，只使用高度图一部分是很有用的。虽然本教程使用的高度图大小为1025×1025，但现在只使用33×33。

下面的代码定义左边的三角形：

int terrainSize = 32;
Triangle leftTriangle = new Triangle(null, new Vector2(0, 0), new Vector2(terrainSize, 0), new Vector2(0, terrainSize), heightData);

基三角形没有父三角形。你将三角形的三个顶点作为第二、第三、第四个参数传递，对应整个地形的顶点。最后，传递包含高度值的2D数组。

注意当代码被执行时，Triangle类的构造函数会被调用。这意味着这个三角形会自己创建两个子三角形，这两个子三角形也会创建自己的两个子三角形。这个过程持续到所有三角形的大小小于两个创建的高度图上的点。

右边的三角形以同样的方法定义，只是顶角的位置不同：

Triangle rightTriangle = new Triangle(null, new Vector2(terrainSize, terrainSize), new Vector2(0, terrainSize), new Vector2(terrainSize, 0), heightData)

添加链接

对于所有在Triangle类中进行的判断和动作，每个Triangle都需要访问它的父、邻居和子三角形。因此，下一步就是添加它们的链接。

每个Triangle已经存储了指向父和子三角形的链接，但还需要知道邻近三角形的链接。技巧是知道三个邻近三角形就可以知道它的子三角形的三个邻近三角形。这个方法可以自动计算结构中所有三角形的邻近三角形。首先在Triangle类中添加这个方法：

public void AddNeighs(Triangle lNeigh, Triangle rNeigh, Triangle bNeigh)
...{
    this.lNeigh = lNeigh;
    this.rNeigh = rNeigh;
    this.bNeigh = bNeigh;
}

Triangle需要你将链接传递到三个邻近三角形中并存储。然后，如果Triangle拥有子，你想找到子三角形的邻近三角形，这样你可以将调用传递到子三角形中，然后依次传递到它们的子三角形的邻近三角形中，直到整个结构的Triangles都存储了指向三个邻近三角形的链接。

if (lChild != null)
...{
    Triangle bNeighRightChild = null; 
    Triangle bNeighLeftChild = null;
    Triangle lNeighRightChild = null;
    Triangle rNeighLeftChild = null;

    if (bNeigh != null)
    ...{
        bNeighLeftChild = bNeigh.lChild;
        bNeighRightChild = bNeigh.rChild;
    }
    if (lNeigh != null)
        lNeighRightChild = lNeigh.rChild;
    if (rNeigh != null)
        rNeighLeftChild = rNeigh.lChild;
    
    lChild.AddNeighs(rChild, bNeighRightChild, lNeighRightChild);
    rChild.AddNeighs(bNeighLeftChild, lChild, rNeighLeftChild); 
}

你要做的就是通过在两个基三角形上调用这个方法初始化这个过程。在LoadContent方法的最后添加下面的代码：

leftTriangle.AddNeighs(null, null, rightTriangle); 
rightTriangle.AddNeighs(null, null, leftTriangle); 

每个基三角形是另一个的唯一邻近三角形。这两个简单的调用会遍历整个结构直到所有的Triangle都存储了正确的指向邻近三角形的链接。

TriangleList和IndexBuffer

当初始化过程结束后，你就做好了继续前进的准备。对ROAM算法的每次迭代，都从上一帧绘制的三角形集合开始。在迭代过程中，你都需要更新这个集合，将需要更高细节的三角形进行分割（被它们的两个子三角形替代），细节太高的三角形与对应的邻近三角形合并（见图2-20）。当集合中的每个Triangle将它们的索引存储到一个集合后迭代结束，然后将索引集合上传到显卡的缓冲中。因此，在Triangle中需要一个小方法可以将三角形的索引添加到一个集合中：

public void AddIndices(ref List<int> indicesList)
...{
    indicesList.Add(lInd);
    indicesList.Add(tInd);
    indicesList.Add(rInd);
}

让我们回到主程序。因为你会频繁地上传索引集合，所以需要使用一个DynamicIndexBuffer（可见教程5-5）。因此，你需要在indicesList中保存本地索引的副本。在代码顶部添加以下三个变量：

List<Triangle> triangleList;
List<int> indicesList;
DynamicIndexBuffer dynTerrainIndexBuffer;

然后，通过在集合中添加两个基三角形开始处理过程，通过将以下代码添加到LoadContent方法中将它们的索引存储到另一个集合中：

triangleList = new List<Triangle>();
triangleList.Add(leftTriangle);
triangleList.Add(rightTriangle);

indicesList = new List<int>();
foreach (Triangle t in triangleList)
t.AddIndices(ref indicesList);

现在有了索引集合，你就做好了将集合发送到DynamicsIndexBuffer的准备：

dynTerrainIndexBuffer = new DynamicIndexBuffer(device, typeof(int), indicesList.Count, BufferUsage.WriteOnly);
dynTerrainIndexBuffer.SetData(indicesList.ToArray(), 0, indicesList.Count, SetDataOptions.Discard);
dynTerrainIndexBuffer.ContentLost += new EventHandler(dynIndexBuffer_ContentLost);

如教程5-5的解释，你需要在设备丢失时调用一个指定的方法。这意味着你还需要指定dynIndexBuffer_ContentLost方法，它可以将索引从本地内存复制到显卡中：

private void dynIndexBuffer_ContentLost(object sender, EventArgs e)
...{
    dynTerrainIndexBuffer.Dispose();
    dynTerrainIndexBuffer.SetData(indicesList.ToArray(), 0, indicesList.Count, SetDataOptions.Discard);
}

绘制TriangleList中的三角形

以后，你会从triangleList中添加或移除三角形。现在，首先定义一个简单的方法绘制包含在triangleList的三角形。解释请见教程5-8。

private void DrawTerrain()
...{
    int width = heightData.GetLength(0);
    int height = heightData.GetLength(1);

    device.RenderState.FillMode = FillMode.Solid;
    device.RenderState.AlphaBlendEnable = false;

    basicEffect.World = Matrix.Identity;
    basicEffect.View = fpsCam.ViewMatrix;
    basicEffect.Projection = fpsCam.ProjectionMatrix;
    basicEffect.Texture = grassTexture;
    basicEffect.TextureEnabled = true;

    basicEffect.Begin();
    foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
...    {
        pass.Begin();
        device.Vertices[0].SetSource(terrainVertexBuffer, 0, VertexPositionNormalTexture.SizeInBytes);
        device.Indices = dynTerrainIndexBuffer;
        device.VertexDeclaration = myVertexDeclaration;
        int noTriangles = triangleList.Count;
        device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, width * height, 0, noTriangles);
        pass.End();
    }
    basicEffect.End();
}

别忘了在Draw方法中调用这个方法：

DrawTerrain(); 
device.Indices = null; 

需要最后一行代码的原因是：当在显卡上将DynamicIndexBuffer设置为active时你无法改变其中的内容。

ROAM迭代

完成了初始化三角形结构和将triangleList中的三角形绘制到屏幕后，你就做好了进入ROAM的准备。每次迭代过程中，你首先从上一个迭代中绘制的三角形开始，需要根据当前相机的位置判断三角形是否需要分割还是合并。下面是包含在ROAM迭代中的步骤。

注意在迭代开始时除了triangleList这些集合是空的，显然不包括triangleList。看起来好像可以将一些步骤合并在一起，实际上不能，理由会在下面的段落中解释。

1. 首先从前一次迭代中计算的triangleList开始。
2. 对集合中的每个三角形，检测是否需要被分割成两个子三角形，将它们添加到splitList集合中。保存不需要分割的三角形到remainderList集合。
3. 分割splitList中的三角形，每个三角形会将它的两个子三角形添加到newTriangleList中，在迭代最后newTriangleList会成为新的triangleList。
4. 检测remainderList中的三角形是否需要合并，如果是，将它的父三角形添加到mergeList中。将其他的三角形添加到leftoverList中。
5. 将mergeList中的每个父三角形添加到newTriangleList中。
6. 如果需要，将leftoverList中的每个三角形添加到newTriangleList中。
7. 在triangleList中保存newTriangleList做好用于下一次迭代的准备。
8. 将triangleList中的三角形的索引传递到DynamicIndexBuffer中，将这些三角形绘制到屏幕上。

整个过程（除了第8步）由UpdateTriangles方法处理。显然你需要编写用于UpdateTriangles方法的方法，UpdateTriangles方法需要放置在游戏主类中，因为它需要访问triangleList。

private void UpdateTriangles()
...{
    List<Triangle> splitList = new List<Triangle>();
    List<Triangle> mergeList = new List<Triangle>();
    List<Triangle> remainderList = new List<Triangle>();
    List<Triangle> leftoverList = new List<Triangle>();
    List<Triangle> newTriangleList = new List<Triangle>(triangleList.Count);

    Matrix worldViewProjectionMatrix = Matrix.Identity * fpsCam.ViewMatrix * fpsCam.ProjectionMatrix;
    BoundingFrustum cameraFrustum = new BoundingFrustum(worldViewProjectionMatrix);

    foreach (Triangle t in triangleList)
        t.CreateSplitList(ref splitList, ref remainderList, ref worldViewProjectionMatrix, ref cameraFrustum);

    foreach (Triangle t in splitList)
        t.ProcessSplitList(ref newTriangleList);

    foreach (Triangle t in remainderList)
        t.CreateMergeList(ref mergeList, ref leftoverList, ref worldViewProjectionMatrix, ref cameraFrustum);

    foreach (Triangle t in mergeList)
        t.ProcessMergeList(ref newTriangleList, ref worldViewProjectionMatrix, ref cameraFrustum);

    foreach (Triangle t in leftoverList)
        t.ProcessLeftovers(ref newTriangleList);

    triangleList = newTriangleList;
    triangleList.TrimExcess();
}

创建splitList

在创建splitList前，每个Triangle需要判断本身是否需要分割。一个Triangle是基于自己左顶点和中心点之间的屏幕距离的（见图2-21）。屏幕距离是两点间的屏幕像素大小，靠近相机的三角形这个距离会比远离相机的三角形大。只有这个屏幕距离大于某个阈值时这个三角形才需被分割，这是由ShouldSplit方法决定的，它应该放置在Triangle类中：

public bool ShouldSplit(ref Matrix wvp, ref BoundingFrustum bf)
...{
    bool shouldSplit = false;
    if (bf.Contains(apexPos) != ContainmentType.Disjoint)
...    {
        Vector4 lScreenPos = Vector4.Transform(lPos, wvp);
        Vector4 aScreenPos = Vector4.Transform(apexPos, wvp);
        lScreenPos /= lScreenPos.W;
        aScreenPos /= aScreenPos.W;

        Vector4 difference = lScreenPos - aScreenPos;
        Vector2 screenDifference = new Vector2(difference.X, difference.Y);

        float threshold = 0.1f;
        if (screenDifference.Length() > threshold)
            shouldSplit = true;
    }
    return shouldSplit;
}

首先检查中心点是否在相机视野中（见教程2-5）。如果不是，无需分割这个三角形。如果是，你找到左顶点和中心点的屏幕位置，这可以在每个3D顶点shader中进行：通过使用WorldViewProjection矩阵转换3D位置。因为结果是一个Vector4，你需要将XYZ分量除以W分量。结果中的XY坐标包含了2D屏幕位置的坐标，位于[-1,1]区间。所以，你获取了XY坐标，通过将左顶点和中心点相减获取屏幕距离，screenDifference.Length()。

只有当screenDifference.Length()大于指定的阈值时才需要分割三角形。这意味着小于threshold变量的值会增加地形的细节。

注意：在这种情况中，如果距离小于屏幕大小的1/20，三角形会分割。这个阈值还是比较高。可见教程的最后可以下关于这点的讨论。

现在，每个三角形都判断了自己是否需要分割，你几乎已经做好了创建splitList的准备了。但是，你还需记得本教程前面介绍中的讨论：当三角形需要分割时，你还需要分割它的邻近三角形和它的父三角形（见图2-19）。可以使用下面的方法做到这点，这个方法应该添加到Triangle类中：

public void PropagateSplit(ref List<Triangle> splitList)
...{
    if (!splitted)
...    {
        splitted = true;
        splitList.Add(this);
            if (bNeigh != null)
            bNeigh.PropagateSplit(ref splitList);
        if (parent != null)
            parent.PropagateSplit(ref splitList);
    }
}

这个方法将split变量设为true，将当前的三角形添加到splitList中，然后递归调用其底部三角形和父三角形。

因为递归，所以步骤CreateSplitList和ProcessSplits无法同时进行；否则，你会在newTriangleList中添加一个三角形，而因为这个三角形的底部三角形或子三角形要进行分割，导致这个三角形也会进行分割。这会导致这个三角形和它的子三角形都会被绘制。

注意：首先检查split变量是否为false，只要可能就将它设置为true是很重要的。否则，这个方法会一直循环下去，因为共享长边的两个三角形会一直互相调用这个方法。

现在，你终于做好了编写CreateSplitList方法的准备，它由程序主类中的UpdateTriangles方法调用：

public void CreateSplitList(ref List<Triangle> splitList, ref List<Triangle> remainderList, ref Matrix wvp, ref BoundingFrustum bf)
...{
    bool hasSplit = false;
    if ((lChild != null) && (!splitted))
    ...{
        if (ShouldSplit(ref wvp, ref bf))
...        {
            PropagateSplit(ref splitList);
            hasSplit = true;
        }
    }
    if (!hasSplit)
        remainderList.Add(this);
}

如果三角形还没有分割，可以被分割而且应该被分割，则调用它的PropagateSplit方法。否则将它添加到remainderList中。

处理splitList

下一步获取需要被分割的三角形的集合，编写ProcessSplitList方法很简单。每个需要分割的三角形需要将它的两个子三角形添加到newTriangleList中。但是，因为递归的缘故，可能一个或两个子三角形会被自己分割。这样的子三角形不应该被添加到newTriangleList中，因为当调用子三角形的ProcessSplitList方法时它会自己处理自己的子三角形。

在Triangle类中添加ProcessSplitList方法：

public void ProcessSplitList(ref List<Triangle> toDrawList)
...{
    if (!rChild.splitted)
        toDrawList.Add(rChild);
    if (!lChild.splitted)
        toDrawList.Add(lChild);
}

创建meigeList

接下来，在remainderList中的每个三角形需要检测它的父三角形是否需要合并。根据教程前面的介绍和图2-20，父三角形首先需要进行一些检测判断它是否可以被合并。这是由CanMerge方法决定的，要在Triangle类中添加这个方法：

public bool CanMerge()
...{
    bool cannotMerge = false;
    if (lChild != null)
        cannotMerge |= lChild.splitted;
    if (rChild != null)
        cannotMerge |= rChild.splitted;
    if (bNeigh != null)
    ...{
        if (bNeigh.lChild != null)
            cannotMerge |= bNeigh.lChild.splitted;
        if (bNeigh.rChild != null)
            cannotMerge |= bNeigh.rChild.splitted;
    }
    return !cannotMerge;
}

根据介绍中的讨论，当子三角形被分割或子三角形的底部三角形被分割时，父三角形不允许被合并。

下面的方法检查一个三角形是否可以合并：

public bool CheckMerge(ref List<Triangle> mergeList, ref Matrix wvp, ref BoundingFrustum bf)
...{
    bool shouldMerge = false;
    if (!addedToMergeList)
...    {
        if (CanMerge())
        ...{
            if (!ShouldSplit(ref wvp, ref bf))
...            {
                shouldMerge = true;
                if (bNeigh != null)
                    if (bNeigh.ShouldSplit(ref wvp, ref bf))
                        shouldMerge = false;
            }
        }
    }
}

因为实际上是子三角形决定父三角形是否可以合并，在迭代过程中这个方法会被调用两次。因此，shouldMerge变量用来表示三角形是否已经被添加到了mergeList中。

如果不是，你首先检测三角形是否可以合并，如果允许，检测它是否应该合并，换句话说，它是否不应该被分割。

最后，因为四舍五入的错误，有可能三角形决定要分割而底部三角形却没有，这会导致出现破裂。因此，你要确保两个当前三角形和它的底部三角形对合并的判断是相同的（见图2-20）。

如果三角形应该被合并，则执行下面的代码，应该把它放在CheckMerge方法的最后：

if (shouldMerge)
...{
    addedToMergeList = true;
    mergeList.Add(this);
    if (bNeigh != null)
    ...{
        bNeigh.addedToMergeList = true;
        mergeList.Add(bNeigh);
    }
}
return addedToMergeList;

开始时将addedToMergeList变量设为true，这样当三角形被它的第二个子三角形调用时就不会重复执行这个方法。然后，将三角形添加到mergeList中。之后，如果三角形有底部邻近三角形，你还要将这个邻近三角形添加到集合中以防止产生破裂。你还要将它的addedToMergeList变量设为true，这样方法才不会重复进行。

在某些情况中，你已经将addedToMergeList设为true了，但仍需要在迭代的一开始将它重置为false。理想的地方是放在CreateSplitList方法中，因为这个方法被triangleList中的所有三角形调用，将这行代码添加到CreateSplitList方法的顶部：

addedToMergeList = false; 

定义了两个方法后，很容易编写CreateMergeList的代码，它被主程序代码调用，将它添加到Triangle类中：

public void CreateMergeList(ref List<Triangle> mergeList, ref List<Triangle> leftoverList, ref Matrix wvp, ref BoundingFrustum bf)
...{
    bool cannotMerge = true;
    if (parent != null)
        cannotMerge = !parent.CheckMerge(ref mergeList, ref wvp, ref bf);
    if (cannotMerge)
        leftoverList.Add(this);
}

如果当前三角形有一个父，则调用它的CheckMerge方法。如果允许并且必须，父三角形和底部邻近三角形会被添加到MergeList中。如果不是，子三角形会被添加到leftoverList中。

处理mergeList

幸运的是，处理需要合并的父三角形要干的事不多，只需将它们的split变量重置为false，将它们添加到newTriangleList中：

public void ProcessMergeList(ref List<Triangle> toDrawList, ref Matrix wvp, ref BoundingFrustum bf)
...{
    splitted = false;
    toDrawList.Add(this);
}

处理leftoverList

处理leftoverList还要简单，因为只需将它们添加到newTriangleList中即可。但是，因为split的递归，可能会发生当前三角形同时在分割，所以首先要检查一下：

public void ProcessLeftovers(ref List<Triangle> toDrawList)
...{
    if (!splitted)
        toDrawList.Add(this);
}

更新索引

前面的部分实现了全部的ROAM功能，现在要绘制的三角形存储在triangleList中。你还需要获取它们的索引并将它们传递到显卡上的DynamicIndexBuffer中。在程序主类中添加一些代码：

private void UpdateIndexBuffer()
...{
    indicesList.Clear();
    foreach (Triangle t in triangleList)
        t.AddIndices(ref indicesList);

    if (dynTerrainIndexBuffer.SizeInBytes / sizeof(int) < indicesList.Count)
...    {
        dynTerrainIndexBuffer.Dispose();
        dynTerrainIndexBuffer = new DynamicIndexBuffer(device, typeof(int), indicesList.Count, BufferUsage.WriteOnly);
    }
    dynTerrainIndexBuffer.SetData(indicesList.ToArray(), 0, indicesList.Count, SetDataOptions.Discard);
}

第一行代码获取索引。然后，将它们传递到DynamicIndexBuffer中。但是，需要花点时间重新建立DynamicIndexBuffer。因此，首先检查当前缓冲是否可以容纳索引集合。只有当缓冲太小时才需要重新建立一个新的DynamicIndexBuffer。你将缓冲的大小除以一个整数值占据的大小知道这个缓冲可以容纳多少个整数。

注意：可参见教程5-5学习更多关于创建和使用DynamicIndexBuffer的细节。

使用方法

在Update方法中，确保调用UpdateTriangles方法更新triangleList，调用UpdateIndexBuffer方法将索引传递到显卡：

UpdateTriangles();
UpdateIndexBuffer(); 

这就是基本ROAM的实现方法。本教程余下的部分会教你如何使用正交投影矩阵调试三角形结构，还会讨论到性能。

正交投影矩阵

因为ROAM三角形比其他方法更加复杂，你需要一个强大的方法实时显示究竟发生了什么，想实现如图2-22所示的效果。

图2-22 绘制在ROAM地形之上的正交网格

在图2-22中你可以看到两样东西。首先是一个延伸到很远处的ROAM地形，靠近相机的山有一个漂亮的细节。第二，在其之上白色的三角形边框，它们是与绘制地形相同的三角形，但有两个不同：

• 它们只绘制边框
• 它们是从地形顶部观察的

看一下白色边框，你可以说出相机在地形的何处并看向何方：靠近相机的地方，绘制了大量的三角形，对应左下角的白色区域。在相机视野中的地形会随着离开相机的距离增大而减少细节。相机视野之外的地形会以尽可能少的三角形被绘制。

在本节中，你将学习如何绘制网格。因为你已经知道了三角形的索引，只需再次绘制同样的三角形即可，只不过使用一个不同的视矩阵和投影矩阵（见教程2-1）。

你只需简单地将相机的位置定义在地形中央的高处看向下方，但这样做不会获得图2-22中的效果。理由是当使用一个常规的投影矩阵时，靠近屏幕边缘的三角形会比靠近中央的三角形看起来小，这是由相机视锥体的金字塔形状导致的，如图2-23左图所示。这个投影导致物体靠近相机时会变大。在左图中的两点，靠近相机的那个点看起来会比视景体后部的那个点大。如果观察的是网格，一个常规的投影矩阵会导致靠近屏幕边缘的网格发生弯曲。

图2-23 常规相机视景体（左）和正交相机视景体（右）

你想要的视景体如图2-23的右图所示，叫做正交视景体。在这个视景体中相同大小的物体占据屏幕上的相同大小的区域：图2-23右图中的两个点在屏幕上看起来的大小是一样的。

创建视矩阵和投影矩阵

首先在代码顶部添加这两个矩阵：

Matrix orthoView; 
Matrix orthoProj; 

因为相机不会改变位置和朝向，你可以安全地在LoadContent方法中定义这两个矩阵无需改变它们：

orthoView = Matrix.CreateLookAt(new Vector3(terrainSize / 2, 100, -terrainSize / 2), new Vector3(terrainSize / 2, 0, -terrainSize / 2), Vector3.Forward);
orthoProj = Matrix.CreateOrthographic(terrainSize, terrainSize, 1, 1000);

因为实际上只改变相机的镜头，视矩阵定义与往常一样：你将相机放置在地形中央的上方，让它看向地形中央。因为你会使用一个正交投影矩阵，相机离开地形的高度无关紧要：三角形大小一样，与离开相机的位置无关。

如你所见，定义一个正交投影矩阵非常简单：只需将视景体的宽和高设置为World的大小，至于后面的两个值，你只需保证地形位于两者之间即可。

定义了两个矩阵后，准备好三角形和索引后，就可以绘制网格了。

绘制正交网格

因为绘制地形的三角形与绘制网格的三角形是一样的，你可以使用与绘制地形几乎一样的方法绘制网格，最重要的改变时你使用的是新建的视矩阵和投影矩阵。而且，将FillMode设置为WireFrame，这样你只需要绘制三角形的边框：

private void DrawOrthoGrid()
...{
    int width = heightData.GetLength(0);
    int height = heightData.GetLength(1);

    device.RenderState.FillMode = FillMode.WireFrame;
    basicEffect.World = Matrix.Identity;
    basicEffect.View = orthoView;
    basicEffect.Projection = orthoProj;
    basicEffect.TextureEnabled = false;

    device.RenderState.AlphaBlendEnable = true;
    float color = 0.4f;
    device.RenderState.BlendFactor = new Color(new Vector4(color, color, color, color));
    device.RenderState.SourceBlend = Blend.BlendFactor;
    device.RenderState.DestinationBlend = Blend.InverseBlendFactor;

    basicEffect.Begin();
    foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
...    {
        pass.Begin();
        device.Vertices[0].SetSource(terrainVertexBuffer, 0, VertexPositionNormalTexture.SizeInBytes);
        device.Indices = dynTerrainIndexBuffer;
        device.VertexDeclaration = myVertexDeclaration;
        int noTriangles = indicesList.Count / 3;
        device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, width * height, 0, noTriangles);
        pass.End();
    }
    basicEffect.End();
    device.RenderState.AlphaBlendEnable = false;
}

因为白色容易干扰视线，你想与地形进行颜色混合。这里BlendFactor渲染状态非常有用：因为你不能定义每个顶点的alpha值（或者你不得不定义一个自定义VertexFormat和顶点着色器），只能对所有三角形使用固定的alpha值。BlendFactor接受一个颜色，每个颜色都会被BlendFactor颜色添加透明效果。别忘了在Draw方法中绘制了地形之后调用这个方法：

DrawOrthoGrid(); 

代码

所有的代码前面已经写过了。

扩展阅读

关于LOD地形算法可以写一本书。虽然前面的代码已经提供了一个完整的ROAM功能，我还是可以进行大量的改进。为了让你可以思考一些东西，我会简短的讨论一些明显的性能改进。

在前面的代码中，ROAM过程开始于Update方法。这意味着整个过程每秒执行60次，这太频繁了。这有在相机移动或旋转时才需要执行ROAM，大多数情况中，这样做会将计算开销降低到一个可以忍受的水平。

而且，ROAM过程最好分成不同的步骤。在第一个周期中，你可以创建splitList，在下一个周期中处理这个splitList等。复杂的过程（例如创建splitList）可以分成多个周期。这样可以让你指定每帧用于计算的最大时间，这可以让你将资源合理分配给ROAM。

最后，因为分割的原理，ROAM算法的每一步都可以分割成多个部分，可以在不同的线程中并行处理，这样算法就可以从多核处理器中获益。

这个方法也可以和四叉树组合起来，ROAM可以用来判断地形是否以高细节还是低细节绘制。

发布时间：2009/11/13 上午11:04:40  阅读次数：8021