来源：GameRes
\N第二部分：基于LOD算法的地形简化
引 言
地形渲染是一个室外渲染引擎的核心部分。而实现一个大规模的地形渲染系统的关键是如何简化地形，抛弃不必要的渲染动作（如看渲染不见的三角形和不必要的细节）来加快渲染速度。动态 LOD技术无疑是一个强有力的解决方案。
\N
\N第二章：LOD简介
\N\N
当我们要生具有相当真实感的场景的时候，由于场景本身的复杂性，要实现实时性往往时不太可能的。我们必须从场景的本身的几何特性入手，通过适当的方法来简化场景的复杂性。层次细节（Levels of Details ）技术就是在这样的情况下提出来的。
\N\N
我们知道，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个像素而已。我们完全没有必要为这样的物体去绘制它的全部细节，我们可以适当的合并一些三角形而不损失画面的视觉效果。对于一般的应用，我们通常会为同一个物体建立几个不同细节层度的模型，如下图的牛的模型，最左边的有最高的细节层度，而最右边的则经过了相当的简化。这样的技术在地形渲染中，我们也称之为多分辨率地形（Multi-Resolution Terrain）。
\N\N\N
\N
（图2.1）牛的层次细节模型，图片来自清华大学远程教育网
\N\N
\N\N
这些不同细节层度的模型可以时在程序运行前建立的。也可以是在运行时刻计算生成的。我们可以从一个全细节的模型出发，通过一系列简化操作生成底细节层度的模型，简化操作可以分成三种（见[参考文献 31]）：顶点删除，边压缩和面片收缩技术。通过这样处理后，我们可以在特定的场合下选择合适的模型，而不必每次都选用全细节的模型，这样大大的降低场景三角形数量。
\N\N
地形作为一种特殊的几何物体，我们在运用LOD法则的时候有一些特殊的技巧。因为地形通常是一个规则的矩形网格。其简化模式可以有两种：规则的简化和非规则的简化，规则的简化通常是对这个矩形网格采用自顶向下(Up-to-Down)、分而治之的策略，典型的有四叉树和二叉树，它们从场景的最低细节层度开始，按需要不断的提高细节。非规则的简化通常是采用自底向上（Down-to-Up）的方法来处理的。它的实现则通常比较少。
\N\N
\N\N
(图2.2)规则的简化（左边）和非规则的简化方式（右边）。图片来自[参考文献2，12]
\N\N
\N\N
实现LOD算法时，除了如何对几何物体进行简化以外，还有一个很重要的问题就是如何决定是否对一个物体进行简化，或者说在某个时刻该如何决定使用哪个层次细节度的模型来表示物体。我们需要建立一个评价系统，由这个评价系统来决定要对物体简化到何种层度。这种评价系统通常是视点相关的，离视点远的物体通常只需要较少的细节，反之则需要比较多的细节。除此之外，物体本身的特性也必须考虑在内。比如说，一个平坦的表面只需要很少的三角形就能较好表现出来。而一个凹凸不平的表面是理所当然的需要更多的三角形去描绘的。
\N\N
用LOD 算法渲染地形的时候，还有一个很重要的问题就是几何变形（Geomorphing）问题，由于对一些细节的丢弃，随着视点的移动，远处原来没有的细节很可能会突然出现，这种现象也称为“跳出”(“Pop”)。我们必须消除这种现象，或者至少要把它控制在可以接受的范围以内。
\N\N
由上可知，LOD算法其实并不很复杂，本文认为其关键处可概括如下：
\N\N
1 数据的存储布局。
\N\N
数据在内存中的布局必须要方便算法的实现，同时最好还要降低操作系统缺页中断的次数，也就是降低内外存之间的数据交换的次数。
\N\N
2 如何在生成连续的LOD化的地形网格
\N\N
在地形LOD化过程中，要让两个由不同层度的细节的区域之间能平滑的过度。
\N\N
3 节点评价系统。
\N\N
这个系统必须要使生成的网格能尽量的减少几何形变，尽量的使画面质量能接近全分辨率时候的地形。同时还要保证实时性。
\N\N
\N\N
第三章 相关研究
\N\N
在过去的几年中，已经由相当的数量的实用的算法被开发出来。Bryan Turner在他的论文[参考文献 32]中提到，LOD地形法则可以由三篇优秀的论文来概括，它们为[参考文献12 ，4 和 7]，在[参考文献12]中，Hoppe 描述了一个Progressive Mesh的模型，它是使用自底向上的模式。[参考文献4]作者是Lindstrom，它则使用了一种基于四叉树的数据结构，他用四叉树递归的把一个地形分割成一个一个小块（tessellates）并建立一个近似的高度图。[参考文献7]的作者是Duchaineau，他描述了一个基于二元三角树结构的法则ROAM（实时优化自适应网格）。这里每一个小片（Patch）都是一个单独的正二等边三角形，从它的顶点到对面斜边的中点分割三角形为两个新的正等边三角形，分割是递归进行的可以被子三角形重复直到达到希望的细节等级。后两篇论文采用的都是规则的简化的模式，并采用分而治之的策略。而Hoppe采用的则是一种不规则的简化模式，它可以往任何一个三角形里增加细节，也可以删除任何一个顶点和边。
\N\N
Hoppe的法则使用比较少，很难在他以外的文章以外地方见到，Lindstrom 和Duchaineau的方法则不同，它们分别代表了当前的两大主流法则：基于四叉树的LOD地形分割和基于二叉树的LOD地形分割。
\N\N
以上三篇文章是相当出色和精彩的。但是有一定的难度和复杂。本文更多的则是采用的是[参考文献2 和 13]中的技术。两者都采用了四叉树的思想，这基本上同[参考文献4]，但是更加的简单和快速，同时[参考文献2]提供的顶点评价系统非常的快速。遗憾的是两者都没有建立完善的内存数据布局来解决来地形数据的存储问题。
\N\N
作为游戏开发领域的热点问题，自然有LOD算法是源于游戏开发人员的，如上的[参考文献13]就是出自2000年的GDC。同时也已经有相当一部分游戏成功的采用了各种不同的LOD算法，如Tread Marks ，Myth ,Soul Ride等。[参考文献8]的作者Thatcher Ulrich在他的文章里以 Soul Ride游戏开发者的身份描述了应用于Soul Ride的基于四叉树的算法（详见www. Gamasutra.com）。不同于学院派的算法，游戏开发者的算法通常更加的简洁和快速。
\N\N
\N\N
第四章 LOD算法
\N\N
1. 基本思想
\N\N
在提出基本的算法之前，为了简单起见，本文必须对要渲染的地形做如下的规定：地形必须是一正方形区域。而且大小必须是 . 同时采样间隔必须均匀。
\N\N\N
\N
(图4.1)一个地形的四叉树表示，左图中每一个正方形为四叉树的一个节点，粉红色的为观察者能看到的区域。
\N\N
\N\N
如图4.1所示，我们采用四叉树的概念来描述一个多分辨率地形，图中的每一个正方形为四叉树的一个节点，每个节点保存了一定区域的信息，包括：中心点的高度，从整个完整的地形出发，我们递归的把地形不断的分割（Sub-divide）成相等的四个区域，分割的深度越大，则得到的分辨率越高。即分割深度每提高一层，采样密度提高一倍。图4.2演示了分割的过程。
\N\N\N
\N
图4.2，分割过程示意图，level 1到2时，只对两个节点进行了分割
\N\N
图4.3给出了我们在一个四叉树节点中要保存的信息。在本章的第四节中将看到，如何用这些信息渲染这个节点表示的地形区域。
\N\N\N
\N
(图4.3) 一个节点中记录的信息，红色的为中心点，黑色的为边点，蓝色的角点。一共9个点。
\N\N
\N\N
采用四叉树的概念来表示多分辨率地形有许多优点，一个最直接有效的受益就是裁剪，如图4.1所示，其中红色的区域为观察者能看到的部分。我们很容易知道观察者能看到的只是绿色的节点，白色的节点则根本不需要考虑。因此，我们可以在节点递归分割的初期只花很少的代价就可直接把这些看不到的区域简单的丢弃掉。
\N\N
有了地形的逻辑表示后，我们还要建立一个节点评价系统来判定一个节点何时需要被继续分割，何时被直接丢弃（当这个节点不能被观察者看到的时候，节点将被直接丢弃）。如果一个节点没有被丢弃，也不需要继续分割，那么这个节点将被送入渲染API进行图元渲染。
\N\N
\N\N
2. 数据存储
\N\N
地形数据通常存储在高度图里，在内存的结构即为一个二维数组。我们知道二叉树可以有顺序结构和链式结构，同理四叉树也可以采用类似的顺序结构。不同的是这里我们采用二维数组而不是一维数组。我们把全分辨率的地形数据存储在一个二维数组中，四叉树节点的信息（9个顶点的信息）可以直接通过索引在数组中读取。同时还要建立一个和这个地形数据数组大小相同的标志数组，这个标志数组指示四叉树节点的状态。如果一个节点需要被继续分割，我们则把相应的位置标记为1，否则标记为0，如图4.4，标着问号的表示没有被访问到，（注意没有被访问到的地方的数值是不确定的）。
\N\N
由图4.4的数组易知地形大小为什么要满足 。 （对于不满足大小要求的地形，我们必须把把它分割成满足要求的大小，然后进行拼接。）出于算法的简洁性，本文只考虑大小为 的地形。
\N\N
\N\N
（图4.4） 一个地形标记数组（ ）示意图，右边为用这个标记数组渲染的地形，其中黑点表示当前节点需要继续分割，空心点表示不需要继续分割。
\N\N
\N\N
二维数组的存取是按行或者按列的。考虑到观察者移动的区域性，本文尝试使用了一种按区域存储的二维数组，即在物理上把地形数据分成等大小的块，块的大小不能太大，也不能太小。考虑到Intel的CPU的内存页大小是4K，块的大小应该为64×64比较合适，本文采用了32×32的块。这样的存储结构在一定层度上能提高存储效率，降低内存缺页的次数。关于如何使存储结构更加有效的方法在很多文章都有介绍，[参考文献1]就给出了一种称为分簇的内存数据结构，能有效的降低内存缺页带来的性能影响。
\N\N
3. 节点评价系统
\N\N
首先我们要建立一个节点评价系统，决定一个何时该对一个节点进行继续分割。我们把这个评价系统分成两个部分，一是视点相关的，二是地形本身的粗糙层度。裁剪器理论上也该是节点评价系统的一部分，但是考虑到它的特殊性，我们将在单独一章中介绍。
\N\N\N
\N
(图4.5)视点距离因素示意图，l为视点离节点中心的距离。d为节点的尺寸
\N\N
①我们希望离观察者近的地方细节越多，反之则越少。将距离因素应用于一个节点的时候，还必须考虑到节点的大小。因此，结合图4.5我们如下的公式：
\N\N
（C为一个可以调节的因子）
\N\N
其中l为节点的中心位置到视点的距离，d为节点的大小，当它们满足这个公式的时候，节点需要继续分割。其中C为一个可以调节的因子，C越大，地形细节越多。反之则细节越少。
\N\N
②第二个需要考虑的因素是地形本身的粗糙程度，我们希望地形起伏比较崎岖的区域有较高的细节程度，而平坦的地方则不需要我们浪费过多的图元。
\N\N
如图4.6所示，首先我们考虑一个节点包含的9个顶点，其中中心点4个边点在节点被分割和不被分割时候会引起一定的误差，这5个误差值为图4.6左图所示的dh0 – dh4。它们的数值越大表示这个节点表示的地形越粗糙。除此之外，我们还要考虑到这个节点的所有四个子节点的粗糙程度dh5 - dh8，如图4.6右图所示。（如果这个节点达到了最高分辨率表示的地形，则不需要考虑这一步）。我们取这九个值（dh0 - dh8）中的最大的一个除以节点的大小作为这个节点粗糙度的评价值，即 r = Max(dh0,…dh8)/d。由此可见，粗糙度的计算是一个递归的过程，考虑到计算的复杂性和它值的不变性，我们需要事先把粗糙度的评价值计算出来，同样把它存储在一个二维数组中。
\N\N\N
\N
图4.6，地形粗糙程度的度量，左图表示了一个节点内部5个粗糙度信息，右图则表示了它本身的粗糙度信息和它所有子节点的粗糙度信息
\N\N
\N\N
现在我们给出第二个评价公式即粗糙度评价公式：
\N\N
（ 为粗糙度调节因子）
\N\N
为粗糙度调节因子， 越大，细节程度越高。综合以上两个公式，我们得到最终的节点评价公式：
\N\N\N
\N
公式中的字母含义同上，当满足f<1时候，节点需要继续分割。
\N\N
至此，整个节点评价系统已经建立完成，但是我还必须提一下几何形变（Geomorphing）的概念。几何形变会造成“跳出”现象，即随着视点的改变，有些细节会突然消失和出现。解决这种现象的办法是比较困难的，目前在有些文章中，通过专门的方法甚至是插值的方式来消除或者降低几何形变（[参考文献12]等），但是实现这样的系统很困难，计算代价也很大。其次的方法就是把r值进行投影变换到屏幕空间，得到的值称为Projected pixel error（[参考文献3]等）。但是通过实验，我不认为这是一种好的方法（详细原因可见[参考文献8]）。因此本文并没有采用这种pixel error的概念。其实本文并没有采用任何专门的消除几何形变的系统，但是我们可以通过适当的调节C和C2的值来降低几何形变，因为对于一个视频游戏来说，只要能把几何形变控制在一个可以接受的范围内就可以了。
\N\N
4. 网格的渲染
\N\N
地形最终也是通过一个递归的过程来实现的。我们遍历整个四叉树，当我们到达四叉树的叶子的时候，即一个节点不再被分割的时候，我们就可以把这个节点给绘制出来。
\N\N
本文采用三角形扇（Triangle Fan）的方式来绘制节点，这是一种很自然的方式，因为一个节点包含了一个中心点和若干个围绕着中心点的点，这样的排列刚好形成一个三角形扇，如图4.7a所示。
\N\N
(a) (b) (c) (d)
\N\N
图4.7
\N\N
生成网格的时候，我们还有一个注意的地方就是两个不同分辨率的节点拼接的地方会产生 T 型裂缝，如图4.7b所示。我们必须消除这种裂缝，图4.7c演示了在拼接地方增加一条边的方法来消除裂缝，图4.7d则采用了去掉一条边的方法。相对来说，第一种方法更加的复杂，但是也更加的全面，因为拼接处的两个节点的分辨率可以相差任意大。第二种方法则更加简单，它要求拼接处的两个节点的层次差距最多不超过1。本文采用第二种方法，对于如何满足这个要求在下面的网格的生成一小节中将作详细的介绍。
\N\N
结合图4.8的例子，我们详细介绍一下如何生成满足要求的三角形扇。图中灰色区域为我们当前进行渲染的部分。首先，我们保证一个节点的四个角点（Corner vertex 见图4.3）肯定被用到三角形扇中，对于剩下的四个边点（Edge vertex）我们则要检查和这个节点相邻的节点，因为边点要和其它的节点共享，如果相应的邻接节点没有被激活，我们就要跳过这个边点，如这个节点正上方邻接节点没有被分割，则我们要跳过标有X 标记的那个边点。
\N\N\N
\N
图4.8地形网格的渲染示意图其中灰色的节点为当前进行渲染的区域
\N\N
5. 网格的生成
\N\N
在渲染网格之前，我们必须更新四叉树，生成如何符合规范的四叉树，在前一小节中，我们曾给出相邻的两个节点的层次最大不能相差1，否则在拼接的地方会出现裂缝，图4.9a给出了一个符合规范的四叉树例子，图4.9b给出了一个非法的四叉树例子。
\N\N
(a) 合法 (b)非法
\N\N
图4.9符合规范的和不符合规范的四叉树的例子
\N\N
因此，我们必须要有一套规则来保证生成的四叉树的合法性
\N\N
通常，我们采用的是两次遍历四叉树的方法，我们在第一次遍历的时候，生成地形网格，第二次渲染网格，同时消除节点之间的层次差异。
\N\N
这里，我们采用一种更加有效的方法来生成四叉树----按广度优先的原则遍历四叉树。即一次生成一个层次的节点，而且只需要遍历四叉树一次。我们使用两个队列，一个队列保存着当前正在处理的层次的所有节点，另外一个队列则保存着下处理当前层次节点后生成的所有的下一个层次的节点。当处理完所有当前层次队列中的节点以后，就可以进入下一个层次（简单交换两个队列就可以了）的节点处理。对那些不要继续分割的节点和已经到达最大分辨率的节点，我们就把它们送入渲染API进行渲染。
\N\N
这样做有很多的优点。首先因为我们每检查一个节点的时候，和该节点层次相同的节点都已经生成。我们可以通过检查所有和这个节点相邻的节点，看它们是不是存在，如果它们都存在，则可以对这个节点进行继续分割，反之则不能对它进行分割。同时，我们还可以在第一遍遍历四叉树的时候有足够的信息让我们绘制三角型扇，根据本章第四节的方法，渲染一个节点的时候，我们只需要检查分辨率比该节点小的节点。而这些节点在此之前已经全部生成。
\N\N
其次，我们还不必要每次都复位四叉树的状态（清空标记数组）。这对提高速度是很有帮助的。举个例子，假如一个地形的大小是2048×2048。那么这个标记数组的大小是4M。要清空一个4M大小的数组在时间上是一个不小的开销。在本文的程序中，测试一个2048×2048的地图，清空标记数组时的FPS值为35。不清空时的FPS为78。相差一倍多！
\N\N
下面我给出生成网格的伪代码：
\N\N
Function GenerateMesh
Begin
\N\N
Push the root node to the cur_Queue
\N\N
level = 0
\N\N
Loop Not reach the Full resolution)
\N\N
{
\N\N
For Each Quad-Tree Node in Cur_Queue
\N\N
{
\N\N
If(Node is not inside the view frustum)
\N\N
{
\N\N
Simple Skip this Node
\N\N
}
\N\N
else if(level = Full Resolution level –1 )
\N\N
{
\N\N
Draw The Node
\N\N
}
\N\N
else
\N\N
{
\N\N
For Each Sub-Node in this Node
\N\N
Check dependcy
\N\N
If(SubNodeCanSubdivid() and SubNodeNeedActive())
\N\N
{
\N\N
Push this sub Node to Next_level_Queue
\N\N
Set this sub Node flag to VS_ACTIVE
\N\N
}
\N\N
Else
\N\N
{
\N\N
Set this sub Node flag to VS_Disable
\N\N
}End if
\N\N
End for
\N\N
If No sub Node is active
\N\N
{
\N\N
Disable this Node
\N\N
Set all four sub-node flag to VS_DISABLE
\N\N
Draw the Node
\N\N
}
\N\N
else if Some Sub-Node is active
\N\N
{
\N\N
Draw the Node
\N\N
}End if
\N\N
}End if
\N\N
} End for
\N\N
Swap (cur_Queue,Next_level_Queue);
\N\N
level = next level
\N\N
}End Loop
\N\N
End Function
\N\N
\N\N
Function NodeCanSubdivid as BOOL
\N\N
Begin
\N\N
Check the four Neighbor Node.
\N\N
If All Neighbor Node is Active
\N\N
return TRUE
\N\N
Else
\N\N
return FALSE
\N\N
End If
\N\N
End Function
\N\N
6. 优化
\N\N
上面介绍的算法在理论上是比较严谨的，但是稍微显的有些复杂，同时速度也不是十分的快。下面，我将对它进行一些优化和简化。
\N\N
在上面的算法中，当一个节点的四个子节点中有一部分被分割，另一部分不被分割的时候，给我们渲染带来很大的麻烦，而且每处理一个节点的时候，我们都要检查四个子节点，比较麻烦。为此参照[参考文献13]给出如下规则：当一个节点的四个子节点中任何一个需要继续分割的时候，四个子节点都进行分割。在本文的程序里，这个规则进一步成：一个节点需要分割的时候，就把其四个子节点都生成并放入到下一层次的队列中去。
\N\N
按照这种简化的思想，图4.4 中的标记数组对应的地形网格最终将如图4.10所示。对比图4.4右图，我们发现其实简化后的算法生成的地形细节更多，也就是说需要绘制更多的三角形。但是由于需要判断的条件少的多，因此在运速度上，反而是简化后的算法要更占有优势。
\N\N\N
\N
图4.10(图4.4 )中的标记数组对应地形的简化生成算法
\N\N
\N\N
下面我给出优化后的伪代码，对比上面的算法，它显得更加的简洁了。
\N\N
Function GenerateMesh
Begin
\N\N
Push the root node to the cur_Queue
\N\N
level = 0
\N\N
Loop while Not reach the Full resolution
\N\N
{
\N\N
For Each Quad-Tree Node in Cur_Queue
\N\N
{
\N\N
If(Node is not inside the view frustum)
\N\N
{
\N\N
Simple Skip this Node
\N\N
}
\N\N
else if(level = Full Resolution level –1 )
\N\N
{
\N\N
Draw The Node
\N\N
}
\N\N
else if( NodeCanSubdivid() and NodeNeedActive())
\N\N
{
\N\N
Sub Divide this Node
\N\N
Set all four sub-node flag to VS_ACTIVE
\N\N
Push the for sub-node to the next_level_Queue
\N\N
}
\N\N
else
\N\N
{
\N\N
Disable The Node
\N\N
Set all four sub-node flag to VS_DISABLE
\N\N
Draw this Node
\N\N
}End if
\N\N
} End for
\N\N
Swap (cur_Queue,Next_level_Queue);
\N\N
level = next level
\N\N
}End Loop
\N\N
End Function
\N\N
第五章：裁剪
\N\N
通常，3D API都会提供内置的裁剪系统，但是这些裁剪系统都是在经过视图、投影变换以后的。即裁剪是投影空间中进行的。因此我们需要建立一种方法，在顶点进行矩阵变换之前就进行裁剪，同时我们的裁剪系统还必须要有能力裁剪一个四叉树的节点。
\N\N
在投影过程中，有一个投影体，只有当物体处于这个投影体中的时候，我们才能看到这个物体，否则物体将被裁剪掉。因此这个投影体也通常被称为视见体（View Frustum）。在进行正交投影的时候，投影体为一个长方体，在进行透视投影的时候，投影体则为一个平头锥体。下面我们以平头锥体为例子来导出我们的裁剪系统。
\N\N
如图5.1，一个投影体由六个面组成，一个平面的方程可以表示为 。我们规定朝投影体内部的方向为平面的正方向，判断一个顶点是否在投影体内部时，我们只要把顶点坐标代入到六个面的方程中，通过检查结果的符号就可以判断点是不是在投影体内部（所有的符号都为正）。下面我们推导世界空间中的投影体的六个面的方程。
\N\N\N
\N
图5.1投影体，左图为世界空间中的投影体。右图为经过投影变换后的投影体。
\N\N
\N\N\N
\N
图5.2变换后的投影范体的尺寸。
\N\N
世界空间的投影体在经过投影变换后，会成为一个范体，如图5.1右图所示。这个范体的尺寸见图5.2。我们很容易得到这个范体的六个面的方程，它们是 。
\N\N
我们假设这六个平面中某个平面上有一个点（x0,y0,z0,1），在进行投影变换之前的坐标为（ ）。
\N\N
这个平面的方程为 。
\N\N\N
\N
投影变换前，在世界空间中的方程为 。
\N\N\N
\N
则点必须满足 和 。
\N\N
\N\N
\N\N
如果变换矩阵为T。则
\N\N
。
\N\N
结合这三个等式，我们立即就可以得到 。
\N\N\N
\N
结合投影空间中范体的六个面的方程，我们现在可以很容易的得到世界空间中的投影体的六个面的方程。
\N\N
我们已经有了裁剪体的方程，当我们需要裁剪一个顶点的时候，这六个方程已经足够了。但是我们要判断一个区域的可见性时，我们进行一些额外的计算。如图5.3所示，一个物体和投影体的关系大致可以分为：包围、被包围、相交和相离四种情况。图中最大的浅蓝色的矩形包围了整个投影体。深绿色的小矩形则完全被投影体包围。浅绿色的矩形和投影体相交。这三种情况下物体都是可以被看到的。剩下红色的矩形则和投影体相离、只有它完全不可见。
\N\N\N
\N
图5.3物体和投影体的关系。
\N\N
\N\N
当处理节点的可见性的时候，由于节点的不规则性。我们还需要引入包围体的概念。所谓的包围体，就是用一个比较简单的几何体去度量另外一个比较复杂的几何体，让它刚好能包围另外一个几何体。比较合适的包围体外形有矩形、正方形和球体。其中球体处理最为简单，但是近似度也最差。我们为每一个节点都建立一个包围体，只要测试这个包围体，我们就可以决定一个节点的可见性，由于包围体肯定大于这个节点，因此我们可以保证不会有任何可见的节点被裁剪在投影体之外。
\N\N
\N\N
第六章：性能测试
\N\N
1． 内存消耗量：本文的LOD算法的内存消耗量只和地形的大小有关，而且这种关系是线性的。对于地形中的每一个顶点，我们需要的信息如下：高度信息（1字节），粗糙度信息（浮点型，4字节）。四叉树信息（1字节）。因此每个顶点需要6个字节来保存。对于一个4097×4097的地图，我们需要96M的存储空间，这在连PC机的RAM大小都几乎要以GB来计算的今天，应该不是很大的问题。同时考虑到本文采用的都是静态的数据结构，在内存消耗方面应该还存在着很多的优化余地。
\N\N
2． 速度和图像质量：本文的算法既没有在进行恒定的速度控制，也没有进行恒定三角形数量的控制。生成三角形的数量除了和C,C2的大小有关以外，还和地形本身的起伏程度有关。本文的演示程序在一般情况下，C=3,C2=30左右就能达到比较好的效果。当C=4.5时候，就基本不存在几何形变的问题。而且FPS均在120以上（使用了细节纹理），速度完全达到要求。
\N\N
3． 实例测试：我选择的测试地图大小为2049×2049和4097×4097。地图使用PhotoShop的分层云彩功能制作，用本文演示程序的地图工具进行修改加工。纹理为区域地貌纹理加亮度图调制混合得到。细节纹理被关闭（即只进行了一遍纹理映射）。测试平台为Intel赛扬II 1.2G，nVidia GForce 2/MX400，128M RAM。操作系统为Windows 2000sp2。显卡驱动版本为4345官方发布版。注意驱动程序必须安装正确，Windows2000提供的驱动并不能很好的支持OpenGL。
\N\N
\N\N
表6.1：2049×2049地图的渲染结果。
\N\N
测试用的高度图，大小为2049×2049.
使用双色模式渲染。用来演示生成的三角形扇，三角形扇的中心红色，周围的点为白色。中心为蓝色的三角形扇表示这个地方达到了全分辨率。
C=25，C2=2.5. 三角形数量6529。视野距离600。FPS=167
C=50,C2=5.0.三角形数量11192。视野距离600。FPS=138
C=25，C2=2.5. 三角形数量2174。视野距离600。FPS=237。网格着色模式
C=50，C2=5.0. 三角形数量13221。视野距离600。FPS=124。网格着色模式
\N\N
\N\N
表6.1：4097×4097地图的渲染结果。
\N\N
用的高度图
C=35,C2=3.5.三角形数量10877。视野距离6000。FPS=137
\N\N
\N\N
本算法的速度基本上只和C,C2有关，图6.1为这两个因子和速度、三角形数量之间的关系。图中的测试数据中C=35恒定，C2从2.5到10.0。由于这两个由图可见，速度和三角形的数量和C×C2大致是先线性关系。
\N\N\N
\N
图6.1 三角形数量，FPS和C×C2之间的关系。红线为FPS值，绿线为三角形数量
\N\N
\N\N
在选择4097×4097的地图时，算法运行速度上没有任何的变化，因为需要渲染的地形区域仅限于视见体内部。当选择8193×8193的地图时候，由于内存缺页引起的丢帧就比较严重，如果在Windows98下就基本不能运行。
\N\N
第三部分：真实感场景的生成技术。
\N\N
第七章：天空体和镜头眩光
\N\N
第八章：公告板技术
\N\N
第九章：地表的细节
\N\N
第十章：景深处理
\N\N
第十一章：运动模糊
\N\N
第四部分：结论和展望
\N\N
附录
\N\N
A:地形数据的生成
\N\N
B:参考文献
