1 引言
如果没有接触过涉及到细节等级（LOD）的地形生成法则，恐怕你就不能在地形可视化的世界里任意挥舞你的指挥棒了。细节等级是一种使用了一系列启发式的方法来决定地形的哪一部分需要看起来有更多的细节的技术。在这里，对于地形渲染的许多技术挑战之一是如何存储一个地形的特征。高度图是事实上的标准解决方案，简单的说他们就是保存地形每点高度的二维数组。
2 LOD地形法则概论
一个LOD地形法则的优秀概述可以被三篇论文来描述，作者分别为[1微软的Hoppe][2 Lindstrom][3 Duchaineau]。在第一位作者的论文中描绘了一个基于Progressive Meshes的法则，这是一个与增加三角形到任意网格来达到你需要的细节相关的新的和绝妙的技术。这篇论文是一篇精彩的读物但有点复杂，同时这项技术需要大量的内存。第二篇论文的作者是Lindstrom，他描述了一个叫四叉树（Quad Tree）的结构用于描绘地形碎片（PATCH），一个四叉树递归的把一个地形分割成一个一个小块（tessellates）并建立一个近似的高度图。四叉树非常简单但很有效。第三篇论文的作者是Duchaineau，他描述了一个基于二元三角树结构的法则ROAM（实时优化自适应网格）。这里每一个小片（PATCH）都是一个单独的正二等边三角形，从它的顶点到对面斜边的中点分割三角形为两个新的正等边三角形，分割是递归进行的可以被子三角形重复直到达到希望的细节等级。由于ROAM法则的简单和可扩展性吸引了我的目光。不幸的是这片论文非常短，仅仅只有少量的伪代码。但无论如何，他可以在连续的范围实现从最基本的平面到最高级的优化。而且ROAM分割成小方块非常快速，而且可以动态更新高度图。
3 ROAM执行初步
代码用Visual C++ 6.0来写的，使用OPENGL来渲染。
ROAM资源说明
让我使用一个概述来介绍这个法则，然后讨论单独的小块是如何相互影响的：
1高度图文件被载入内存并和一个Landscape类的实例相联系，多个Landscape物体连接起来产生无限的地形。
2一个新的Landscape物体把载入的高度图的一部分包裹到新的Patch类物体中，这一步的目的是：
（1）使用基于树的结构来控制随着深度而呈指数增长的内存，这样可以保持他们的深度在一个很小的有限的范围。
（2）动态更新高度图需要在变更场景时有一个完整的变更树从算操作。过大的Patch类物体在实时重新计算时非常慢。
3每一个Patch类物体被调用来建立一个MESH的近似值（分割成小块）。Patch类物体使用了一个叫二元三角树的结构来存储即将显示在屏幕上的三角的坐标。这些三角形顶点坐标被非常合理的存储，ROAM使用36字节以上的内存来存储每一个三角形。高效的坐标计算也是渲染的一部分（见下）。
4在分割完高度图后，引擎已经建立了二元三角树。树的叶节点保存了需要进入图形渲染流水线的三角形。
高度图文件格式
高度图使用一个RAW的数据格式来保存，这个格式包含了8位的高度信息。通常高度图必须从头至尾保存在内存中，在高级标题中我将讨论如何扩展法则来呈现大的数据集。
二元三角树Binary Triangle Trees
ROAM使用了二元三角树来保持三角坐标而不是存储一个巨大的三角形坐标数组来描绘地形。这个结构可以看作是一个测量员把地形切断为一个一个小三角块的结果。这些三角块逻辑上看就象一组相连的邻居一样（左右邻居）。同样的当一个三角块把土地当作遗产时，他需要平等的分给两个儿子。
用这样进行扩展，这个三角块就是二元三角树的根节点，其他三角块也是他们各自树的根节点。Landscape类如同一个局域的土地注册表，保存所有三角块的索引，同时也保存他们之间的层次关系。由于大量子三角块的产生，分割土地也成为一个沉重的负担，但是大量的细节可以被需要更好模拟的区域的种群'population'来简单的处理。看图一：
图一 二元三角树结构等级0-3
二元三角树被TriTreeNode结构保存，同时他还保存ROAM需要的五个最基本的数据，参考图二。
struct TriTreeNode {
TriTreeNode *LeftChild;
// Our Left child
TriTreeNode *RightChild;
// Our Right child
TriTreeNode *BaseNeighbor;
// Adjacent node, below us
TriTreeNode *LeftNeighbor;
// Adjacent node, to our left
TriTreeNode *RightNeighbor;
// Adjacent node, to our right
};
图二 基本的二元三角树的子和邻节点
当对高度图建立一个网格模拟值时，我们需要向二元三角树中添加子节点直到达到我们需要的细节。这一步完成后重新遍历整个树，此时把子节点中保存的三角形数据渲染到屏幕上。这就是一个最基本的引擎了但需要重新设置每一帧，这种递归的方法最大的优点是我们不需要保存每一个顶点的数据，可以释放大量的内存给其他物体。实际上，TriTreeNode结构需要多次的建立和销毁，但这种方法是非常高效的，同时我们或许需要建立几万个这样的结构，因此我们需要一个指针指向我们需要的内存，TriTreeNode结构是通过一个静态内存池来分配的，而不是动态分配，他也给了我们一个快速的重新设置状态的方法。
图三 典型的地形PATCH，从左至右依次是网格模式，光照模式，纹理模式
4
Landscape类的详解
Landscape类对地形的细节渲染进行了高级的封装，通过一些简单的函数调用我们可以在屏幕缓冲中进行从简单的点的显示到复杂的地形渲染工作。这里是Landscape类的定义。
class Landscape {
public:
void Init(unsigned char *hMap);
// Initialize the whole process
void Reset();
// Reset for a new frame
void Tessellate();
// Create mesh approximation
void Render();
// Render current mesh static
TriTreeNode *AllocateTri();
// Allocate a new node for the mesh
protected:
static int m_NextTriNode;
// Index to the next free TriTreeNode
static TriTreeNode m_TriPool[];
// Pool of nodes for tessellation
Patch m_aPatches[][];
// Array of patches to be rendered
unsigned char *m_HeightMap;
// Pointer to Height Field data
};
Landscape类管理了一个大的正三角块，同时可以和其他Landscape物体一起工作。在初始化过程中，高度图被分割成大量的可管理的小块，同时把他和一个新的Patch物体联系起来。Patch类及其它的方法我们将在下面花费更多的时间讲解。注意这些函数的简单性，Landscape物体本身是设计用于一个简单的渲染流水线的，尤其是在可以免费使用Z缓冲的今天。
5 Patch类详解
Patch类是这个引擎的灵魂，他可以分为两部分，一半是递归部分，另一半是基本函数部分，下面就是这个类的数据成员和基本函数描述：
class Patch {
public:
void Init( int heightX, int heightY, int worldX, int worldY, unsigned char *hMap);
// Initialize the patch
void Reset();
// Reset for next frame
void Tessellate();
// Create mesh
void Render();
// Render mesh void
ComputeVariance();
// Update for Height Map changes
...
protected:
unsigned char *m_HeightMap;
// Adjusted pointer into Height Field
int m_WorldX, m_WorldY;
// World coordinate offset for patch
unsigned char m_VarianceLeft[];
// Left variance tree
unsigned char m_VarianceRight[];
// Right variance tree
unsigned char *m_CurrentVariance;
// Pointer to current tree in use
unsigned char m_VarianceDirty;
// Does variance tree need updating?
TriTreeNode m_BaseLeft;
// Root node for left triangle tree
TriTreeNode m_BaseRight;
// Root node for right triangle tree
...
在上面的代码中，下面要解释的基本函数被每一个PATCH物体所调用，PATCH类的方法名类似于调用他们的Landscape类的方法，这些方法或许太单纯化这里需要详细的解释一下：
Init()函数需要高度图和世界坐标的偏移值，他们用来对地形进行缩放，指向高度图的指针已经经过调整，指向了这个PATCH物体所需要数据的第一个字节。
Reset()函数释放所有无用的TriTreeNodes结构，接着重新连接两个二元三角树成为一个PATCH，现在这些还没有被提及，但是每一个PATCH物体都有两个单独的二元三角树构成一个正方形（ROAM论文中称为'Diamond'）。如果不明白的话再看一下图二，详细的内容下一节再讨论。
Tessellate()函数简单的传递适当的高级三角形参数（每一个PATCH物体的两个根节点）给一个递归版本的函数，函数Render()和ComputeVariance()也是这样。
6 ROAM精华
讲了这么多我们只是讨
