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'来简单的处理。看图一：
一文秒懂 | 什么是云MSP？
