第二章：LOD简介
第三章：相关的研究
第四章：LOD算法
第一节：基本思想
第二节：数据存储
第三节：节点评价系统
第四节：网格的渲染
第五节：网格的生成
第六节：优化。
第五章：裁剪
第六章：性能测试
第二部分：基于LOD算法的地形简化
引 言
地形渲染是一个室外渲染引擎的核心部分。而实现一个大规模的地形渲染系统的关键是如何简化地形，抛弃不必要的渲染动作（如看渲染不见的三角形和不必要的细节）来加快渲染速度。动态 LOD技术无疑是一个强有力的解决方案。
第二章：LOD简介
当我们要生具有相当真实感的场景的时候，由于场景本身的复杂性，要实现实时性往往时不太可能的。我们必须从场景的本身的几何特性入手，通过适当的方法来简化场景的复杂性。层次细节（Levels of Details ）技术就是在这样的情况下提出来的。
我们知道，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个像素而已。我们完全没有必要为这样的物体去绘制它的全部细节，我们可以适当的合并一些三角形而不损失画面的视觉效果。对于一般的应用，我们通常会为同一个物体建立几个不同细节层度的模型，如下图的牛的模型，最左边的有最高的细节层度，而最右边的则经过了相当的简化。这样的技术在地形渲染中，我们也称之为多分辨率地形（Multi-Resolution Terrain）。
（图2.1）牛的层次细节模型，图片来自清华大学远程教育网
这些不同细节层度的模型可以时在程序运行前建立的。也可以是在运行时刻计算生成的。我们可以从一个全细节的模型出发，通过一系列简化操作生成底细节层度的模型，简化操作可以分成三种（见[参考文献 31]）：顶点删除，边压缩和面片收缩技术。通过这样处理后，我们可以在特定的场合下选择合适的模型，而不必每次都选用全细节的模型，这样大大的降低场景三角形数量。
地形作为一种特殊的几何物体，我们在运用LOD法则的时候有一些特殊的技巧。因为地形通常是一个规则的矩形网格。其简化模式可以有两种：规则的简化和非规则的简化，规则的简化通常是对这个矩形网格采用自顶向下(Up-to-Down)、分而治之的策略，典型的有四叉树和二叉树，它们从场景的最低细节层度开始，按需要不断的提高细节。非规则的简化通常是采用自底向上（Down-to-Up）的方法来处理的。它的实现则通常比较少。
(图2.2)规则的简化（左边）和非规则的简化方式（右边）。图片来自[参考文献2，12]
实现LOD算法时，除了如何对几何物体进行简化以外，还有一个很重要的问题就是如何决定是否对一个物体进行简化，或者说在某个时刻该如何决定使用哪个层次细节度的模型来表示物体。我们需要建立一个评价系统，由这个评价系统来决定要对物体简化到何种层度。这种评价系统通常是视点相关的，离视点远的物体通常只需要较少的细节，反之则需要比较多的细节。除此之外，物体本身的特性也必须考虑在内。比如说，一个平坦的表面只需要很少的三角形就能较好表现出来。而一个凹凸不平的表面是理所当然的需要更多的三角形去描绘的。
用LOD 算法渲染地形的时候，还有一个很重要的问题就是几何变形（Geomorphing）问题，由于对一些细节的丢弃，随着视点的移动，远处原来没有的细节很可能会突然出现，这种现象也称为“跳出”(“Pop”)。我们必须消除这种现象，或者至少要把它控制在可以接受的范围以内。
由上可知，LOD算法其实并不很复杂，本文认为其关键处可概括如下：
1 数据的存储布局。
数据在内存中的布局必须要方便算法的实现，同时最好还要降低操作系统缺页中断的次数，也就是降低内外存之间的数据交换的次数。
2 如何在生成连续的LOD化的地形网格
在地形LOD化过程中，要让两个由不同层度的细节的区域之间能平滑的过度。
3 节点评价系统。
这个系统必须要使生成的网格能尽量的减少几何形变，尽量的使画面质量能接近全分辨率时候的地形。同时还要保证实时性。
第三章 相关研究
在过去的几年中，已经由相当的数量的实用的算法被开发出来。Bryan Turner在他的论文[参考文献 32]中提到，LOD地形法则可以由三篇优秀的论文来概括，它们为[参考文献12 ，4 和 7]，在[参考文献12]中，Hoppe 描述了一个Progressive Mesh的模型，它是使用自底向上的模式。[参考文献4]作者是Lindstrom，它则使用了一种基于四叉树的数据结构，他用四叉树递归的把一个地形分割成一个一个小块（tessellates）并建立一个近似的高度图。[参考文献7]的作者是Duchaineau，他描述了一个基于二元三角树结构的法则ROAM（实时优化自适应网格）。这里每一个小片（Patch）都是一个单独的正二等边三角形，从它的顶点到对面斜边的中点分割三角形为两个新的正等边三角形，分割是递归进行的可以被子三角形重复直到达到希望的细节等级。后两篇论文采用的都是规则的简化的模式，并采用分而治之的策略。而Hoppe采用的则是一种不规则的简化模式，它可以往任何一个三角形里增加细节，也可以删除任何一个顶点和边。
Hoppe的法则使用比较少，很难在他以外的文章以外地方见到，Lindstrom 和Duchaineau的方法则不同，它们分别代表了当前的两大主流法则：基于四叉树的LOD地形分割和基于二叉树的LOD地形分割。
以上三篇文章是相当出色和精彩的。但是有一定的难度和复杂。本文更多的则是采用的是[参考文献2 和 13]中的技术。两者都采用了四叉树的思想，这基本上同[参考文献4]，但是更加的简单和快速，同时[参考文献2]提供的顶点评价系统非常的快速。遗憾的是两者都没有建立完善的内存数据布局来解决来地形数据的存储问题。
作为游戏开发领域的热点问题，自然有LOD算法是源于游戏开发人员的，如上的[参考文献13]就是出自2000年的GDC。同时也已经有相当一部分游戏成功的采用了各种不同的LOD算法，如Tread Marks ，Myth ,Soul Ride等。[参考文献8]的作者Thatcher Ulrich在他的文章里以 Soul Ride游戏开发者的身份描述了应用于Soul Ride的基于四叉树的算法（详见www. Gamasutra.com）。不同于学院派的算法，游戏开发者的算法通常更加的简洁和快速。
第四章 LOD算法
1. 基本思想
在提出基本的算法之前，为了简单起见，本文必须对要渲染的地形做如下的规定：地形必须是一正方形区域。而且大小必须是 . 同时采样间隔必须均匀。
(图4.1)一个地形的四叉树表示，左图中每一个正方形为四叉树的一个节点，粉红色的为观察者能看到的区域。
如图4.1所示，我们采用四叉树的概念来描述一个多分辨率地形，图中的每一个正方形为四叉树的一个节点，每个节点保存了一定区域的信息，包括：中心点的高度，从整个完整的地形出发，我们递归的把地形不断的分割（Sub-divide）成相等的四个区域，分割的深度越大，则得到的分辨率越高。即分割深度每提高一层，采样密度提高一倍。图4.2演示了分割的过程。
图4.2，分割过程示意图，level 1到2时，只对两个节点进行了分割
图4.3给出了我们在一个四叉树节点中要保存的信息。在本章的第四节中将看到，如何用这些信息渲染这个节点表示的地形区域。
(图4.3) 一个节点中记录的信息，红色的为中心点，黑色的为边点，蓝色的角点。一共9个点。
采用四叉树的概念来表示多分辨率地形有许多优点，一个最直接有效的受益就是裁剪，如图4.1所示，其中红色的区域为观察者能看到的部分。我们很容易知道观察者能看到的只是绿色的节点，白色的节点则根本不需要考虑。因此，我们可以在节点递归分割的初期只花很少的代价就可直接把这些看不到的区域简单的丢弃掉。
有了地形的逻辑表示后，我们还要建立一个节点评价系统来判定一个节点何时需要被继续分割，何时被直接丢弃（当这个节点不能被观察者看到的时候，节点将被直接丢弃）。如果一个节点没有被丢弃，也不需要继续分割，那么这个节点将被送入渲染API进行图元渲染。
2. 数据存储
地形数据通常存储在高度图里，在内存的结构即为一个二维数组。我们知道二叉树可以有顺序结构和链式结构，同理四叉树也可以采用类似的顺序结构。不同的是这里我们采用二维数组而不是一维数组。我们把全分辨率的地形数据存储在一个二维数组中，四叉树节点的信息（9个顶点的信息）可以直接通过索引在数组中读取。同时还要建立一个和这个地形数据数组大小相同的标志数组，这个标志数组指示四叉树节点的状态。如果一个节点需要被继续分割，我们则把相应的位置标记为1，否则标记为0，如图4.4，标着问号的表示没有被访问到，（注意没有被访问到的地方的数值是不确定的）。
由图4.4的数组易知地形大小为什么要满足 。 （对于不满足大小要求的地形，我们必须把把它分割成满足要求的大小，然后进行拼接。）出于算法的简洁性，本文只考虑大小为 的地形。
（图4.4） 一个地形标记数组（ ）示意图，右边为用这个标记数组渲染的地形，其中黑点表示当前节点需要继续分割，空心点表示不需要继续分割。
二维数组的存取是按行或者按列的。考虑到观察者移动的区域性，本文尝试使用了一种按区域存储的二维数组，即在物理上把地形数据分成等大小的块，块的大小不能太大，也不能太小。考虑到Intel的CPU的内存页大小是4K，块的大小应该为64×64比较合适，本文采用了32×32的块。这样的存储结构在一定层度上能提高存储效率，降低内存缺页的次数。关于如何使存储结构更加有效的方法在很多文章都有介绍，[参考文献1]就给出了一种称为分簇的内存数据结构，能有效的降低内存缺页带来的性能影响。
3. 节点评价系统
首先我们要建立一个节点评价系统，决定一个何时该对一个节点进行继续分割。我们把这个评价系统分成两个部分，一是视点相关的，二是地形本身的粗糙层度。裁剪器理论上也该是节点评价系统的一部分，但是考虑到它的特殊性，我们将在单独一章中介绍。
(图4.5)视点距离因素示意图，l为视点离节点中心的距离。d为节点的尺寸
①我们希望离观察者近的地方细节越多，反之则越少。将距离因素应用于一个节点的时候，还必须考虑到节点的大小。因此，结合图4.5我们如下的公式：
（C为一个可以调节的因子）
其中l为节点的中心位置到视点的距离，d为节点的大小，当它们满足这个公式的时候，节点需要继续分割。其中C为一个可以调节的因子，C越大，地形细节越多。反之则细节越少。
②第二个需要考虑的因素是地形本身的粗糙程度，我们希望地形起伏比较崎岖的区域有较高的细节程度，而平坦的地方则不需要我们浪费过多的图元。
如图4.6所示，首先我们考虑一个节点包含的9个顶点，其中中心点4个边点在节点被分割和不被分割时候会引起一定的误差，这5个误差值为图4.6左图所示的dh0 – dh4。它们的数值越大表示这个节点表示的地形越粗糙。除此之外，我们还要考虑到这个节点的所有四个子节点的粗糙程度dh5 - dh8，如图4.6右图所示。（如果这个节点达到了最高分辨率表示的地形，则不需要考虑这一步）。我们取这九个值（dh0 - dh8）中的最大的一个除以节点的大小作为这个节点粗糙度的评价值，即 r = Max(dh0,…dh8)/d。由此可见，粗糙度的计算是一个递归的过程，考虑到计算的复杂性和它值的不变性，我们需要事先把粗糙度的评价值计算出来，同样把它存储在一个二维数组中。
图4.6，地形粗糙程度的度量，左图表示了一个节点内部5个粗糙度信息，右图则表示了它本身的粗糙度信息和它所有子节点的粗糙度信息
现在我们给出第二个评价公式即粗糙度评价公式：
（ 为粗糙度调节因子）
为粗糙度调节因子， 越大，细节程度越高。综合以上两个公式，我们得到最终的节点评价公式：
公式中的字母含义同上，当满足f<1时候，节点需要继续分割。
至此，整个节点评价系统已经建立完成，但是我还必须提一下几何形变（Geomorphing）的概念。几何形变会造成“跳出”现象，即随着视点的改变，有些细节会突然消失和出现。解决这种现象的办法是比较困难的，目前在有些文章中，通过专门的方法甚至是插值的方式来消除或者降低几何形变（[参考文献12]等），但是实现这样的系统很困难，计算代价也很大。其次的方法就是把r值进行投影变换到屏幕空间，得到的值称为Projected pixel error（[参考文献3]等）。但是通过实验，我不认为这是一种好的方法（详细原因可见[参考文献8]）。因此本文并没有采用这种pixel error的概念。其实本文并没有采用任何专门的消除几何形变的系统，但是我们可以通过适当的调节C和C2的值来降低几何形变，因为对于一个视频游戏来说，只要能把几何形变控制在一个可以接受的范围内就可以了。
4. 网格的渲染
地形最终也是通过一个递归的过程来实现的。我们遍历整个四叉树，当我们到达四叉树的叶子的时候，即一个节点不再被分割的时候，我们就可以把这个节点给绘制出来。
本文采用三角形扇（Triangle Fan）的方式来绘制节点，这是一种很自然的方式，因为一个节点包含了一个中心点和若干个围绕着中心点的点，这样的排列刚好形成一个三角形扇，如图4.7a所示。
(a) (b) (c) (d)
图4.7
生成网格的时候，我们还有一个注意的地方就是两个不同分辨率的节点拼接的地方会产生 T 型裂缝，如图4.7b所示。我们必须消除这种裂缝，图4.7c演示了在拼接地方增加一条边的方法来消除裂缝，图4.7d则采用了去掉一条边的方法。相对来说，第一种方法更加的复杂，但是也更加的全面，因为拼接处的两个节点的分辨率可以相差任意大。第二种方法则更加简单，它要求拼接处的两个节点的层次差距最多不超过1。本文采用第二种方法，对于如何满足这个要求在下面的网格的生成一小节中将作详细的介绍。
结合图4.8的例子，我们详细介绍一下如何生成满足要求的三角形扇。图中灰色区域为我们当前进行渲染的部分。首先，我们保证一个节点的四个角点（Corner vertex 见图4.3）肯定被用到三角形扇中，对于剩下的四个边点（Edge vertex）我们则要检查和这个节点相邻的节点，因为边点要和其它的节点共享，如果相应的邻接节点没有被激活，我们就要跳过这个边点，如这个节点正上方邻接节点没有被分割，则我们要跳过标有X 标记的那个边点。
图4.8地形网格的渲染示意图其中灰色的节点为当前进行渲染的区域
5. 网格的生成
在渲染网格之前，我们必须更新四叉树，生成如何符合规范的四叉树，在前一小节中，我们曾给出相邻的两个节点的层次最大不能相差1，否则在拼接的地方会出现裂缝，图4.9a给出了一个符合规范的四叉树例子，图4.9b给出了一个非法的四叉树例子。
(a) 合法 (b)非法
图4.9符合规范的和不符合规范的四叉树的例子
因此，我们必须要有一套规则来保证生成的四叉树的合法性
通常，我们采用的是两次遍历四叉树的方法，我们在第一次遍历的时候，生成地形网格，第二次渲染网格，同时消除节点之间的层次差异。
这里，我们采用一种更加有效的方法来生成四叉树----按广度优先的原则遍历四叉树。即一次生成一个层次的节点，而且只需要遍历四叉树一次。我们使用两个队列，一个队列保存着当前正在处理的层次的所有节点，另外一个队列则保存着下处理当前层次节点后生成的所有的下一个层次的节点。当处理完所有当前层次队列中的节点以后，就可以进入下一个层次（简单交换两个队列就可以了）的节点处理。对那些不要继续分割的节点和已经到达最大分辨率的节点，我们就把它们送入渲染API进行渲染。
这样做有很多的优点。首先因为我们每检查一个节点的时候，和该节点层次相同的节点都已经生成。我们可以通过检查所有和这个节点相邻的节点，看它们是不是存在，如果它们都存在，则可以对这个节点进行继续分割，反之则不能对它进行分割。同时，我们还可以在第一遍遍历四叉树的时候有足够的信息让我们绘制三角型扇，根据本章第四节的方法，渲染一个节点的时候，我们只需要检查分辨率比该节点小的节点。而这些节点在此之前已经全部生成。
其次，我们还不必要每次都复位四叉树的状态（清空标记数组）。这对提高速度是很有帮助的。举个例子，假如一个地形的大小是2048×2048。那么这个标记数组的大小是4M。要清空一个4M大小的数组在时间上是一个不小的开销。在本文的程序中，测试一个2048×2048的地图，清空标记数组时的FPS值为35。不清空时的FPS为78。相差一倍多！
下面我给出生成网格的伪代码：
Function GenerateMesh
Begin
Push the root node to the cur_Queue
level = 0
Loop Not reach the Full resolution)
{
For Each Quad-Tree Node in Cur_Queue
{
If(Node is not inside the view frustum)
{
Simple Skip this Node
}
else if(level = Full Resolution level –1 )
{
Draw The Node
}
else
{
For Each Sub-Node in this Node
Check dependcy
If(SubNodeCanSubdivid() and SubNodeNeedActive())
{
Push this sub Node to Next_level_Queue
Set this sub Node flag to VS_ACTIVE
}
Else
{
Set this sub Node flag to VS_Disable
}End if
End for
If No sub Node is active
{
Disable this Node
Set all four sub-node flag to VS_DISABLE
Draw the Node
}
else if Some Sub-Node is active
{
Draw the Node
}End if
}End if
} End for
Swap (cur_Queue,Next_level_Queue);
level = next level
}End Loop
End Function
Function NodeCanSubdivid as BOOL
Begin
Check the four Neighbor Node.
If All Neighbor Node is Active
return TRUE
Else
return FALSE
End If
End Function
6. 优化
上面介绍的算法在理论上是比较严谨的，但是稍微显的有些复杂，同时速度也不是十分的快。下面，我将对它进行一些优化和简化。
在上面的算法中，当一个节点的四个子节点中有一部分被分割，另一部分不被分割的时候，给我们渲染带来很大的麻烦，而且每处理一个节点的时候，我们都要检查四个子节点，比较麻烦。为此参照[参考文献13]给出如下规则：当一个节点的四个子节点中任何一个需要继续分割的时候，四个子节点都进行分割。在本文的程序里，这个规则进一步成：一个节点需要分割的时候，就把其四个子节点都生成并放入到下一层次的队列中去。
按照这种简化的思想，图4.4 中的标记数组对应的地形网格最终将如图4.10所示。对比图4.4右图，我们发现其实简化后的算法生成的地形细节更多，也就是说需要绘制更多的三角形。但是由于需要判断的条件少的多，因此在运速度上，反而是简化后的算法要更占有优势。
图4.10(图4.4 )中的标记数组对应地形的简化生成算法
下面我给出优化后的伪代码，对比上面的算法，它显得更加的简洁了。
Function GenerateMesh
Begin
Push the root node to the cur_Queue
level = 0
Loop while Not reach the Full resolution
{
For Each Quad-Tree Node in Cur_Queue
{
If(Node is not inside the view frustum)
{
Simple Skip this Node
}
else if(level = Full Resolution level –1 )
{
Draw The Node
}
else if( NodeCanSubdivid() and NodeNeedActive())
{
Sub Divide this Node
Set all four sub-node flag to VS_ACTIVE
Push the for sub-node to the next_level_Queue
}
else
{
Disable The Node
Set all four sub-node flag to VS_DISABLE
Draw this Node
}End if
} End for
Swap (cur_Queue,Next_level_Queue);
level = next level
}End Loop
End Function
第五章：裁剪
通常，3D API都会提供内置的裁剪系统，但是这些裁剪系统都是在经过视图、投影变换以后的。即裁剪是投影空间中进行的。因此我们需要建立一种方法，在顶点进行矩阵变换之前就进行裁剪，同时我们的裁剪系统还必须要有能力裁剪一个四叉树的节点。
在投影过程中，有一个投影体，只有当物体处于这个投影体中的时候，我们才能看到这个物体，否则物体将被裁剪掉。因此这个投影体也通常被称为视见体（View Frustum）。在进行正交投影的时候，投影体为一个长方体，在进行透视投影的时候，投影体则为一个平头锥体。下面我们以平头锥体为例子来导出我们的裁剪系统。
如图5.1，一个投影体由六个面组成，一个平面的方程可以表示为 。我们规定朝投影体内部的方向为平面的正方向，判断一个顶点是否在投影体内部时，我们只要把顶点坐标代入到六个面的方程中，通过检查结果的符号就可以判断点是不是在投影体内部（所有的符号都为正）。下面我们推导世界空间中的投影体的六个面的方程。
图5.1投影体，左图为世界空间中的投影体。右图为经过投影变换后的投影体。
图5.2变换后的投影范体的尺寸。
世界空间的投影体在经过投影变换后，会成为一个范体，如图5.1右图所示。这个范体的尺寸见图5.2。我们很容易得到这个范体的六个面的方程，它们是 。
我们假设这六个平面中某个平面上有一个点（x0,y0,z0,1），在进行投影变换之前的坐标为（ ）。
这个平面的方程为 。
投影变换前，在世界空间中的方程为 。
则点必须满足 和 。
如果变换矩阵为T。则
。
结合这三个等式，我们立即就可以得到 。
结合投影空间中范体的六个面的方程，我们现在可以很容易的得到世界空间中的投影体的六个面的方程。
我们已经有了裁剪体的方程，当我们需要裁剪一个顶点的时候，这六个方程已经足够了。但是我们要判断一个区域的可见性时，我们进行一些额外的计算。如图5.3所示，一个物体和投影体的关系大致可以分为：包围、被包围、相交和相离四种情况。图中最大的浅蓝色的矩形包围了整个投影体。深绿色的小矩形则完全被投影体包围。浅绿色的矩形和投影体相交。这三种情况下物体都是可以被看到的。剩下红色的矩形则和投影体相离、只有它完全不可见。
图5.3物体和投影体的关系。
当处理节点的可见性的时候，由于节点的不规则性。我们还需要引入包围体的概念。所谓的包围体，就是用一个比较简单的几何体去度量另外一个比较复杂的几何体，让它刚好能包围另外一个几何体。比较合适的包围体外形有矩形、正方形和球体。其中球体处理最为简单，但是近似度也最差。我们为每一个节点都建立一个包围体，只要测试这个包围体，我们就可以决定一个节点的可见性，由于包围体肯定大于这个节点，因此我们可以保证不会有任何可见的节点被裁剪在投影体之外。
第六章：性能测试
1． 内存消耗量：本文的LOD算法的内存消耗量只和地形的大小有关，而且这种关系是线性的。对于地形中的每一个顶点，我们需要的信息如下：高度信息（1字节），粗糙度信息（浮点型，4字节）。四叉树信息（1字节）。因此每个顶点需要6个字节来保存。对于一个4097×4097的地图，我们需要96M的存储空间，这在连PC机的RAM大小都几乎要以GB来计算的今天，应该不是很大的问题。同时考虑到本文采用的都是静态的数据结构，在内存消耗方面应该还存在着很多的优化余地。
2． 速度和图像质量：本文的算法既没有在进行恒定的速度控制，也没有进行恒定三角形数量的控制。生成三角形的数量除了和C,C2的大小有关以外，还和地形本身的起伏程度有关。本文的演示程序在一般情况下，C=3,C2=30左右就能达到比较好的效果。当C=4.5时候，就基本不存在几何形变的问题。而且FPS均在120以上（使用了细节纹理），速度完全达到要求。
3． 实例测试：我选择的测试地图大小为2049×2049和4097×4097。地图使用PhotoShop的分层云彩功能制作，用本文演示程序的地图工具进行修改加工。纹理为区域地貌纹理加亮度图调制混合得到。细节纹理被关闭（即只进行了一遍纹理映射）。测试平台为Intel赛扬II 1.2G，nVidia GForce 2/MX400，128M RAM。操作系统为Windows 2000sp2。显卡驱动版本为4345官方发布版。注意驱动程序必须安装正确，Windows2000提供的驱动并不能很好的支持OpenGL。
表6.1：2049×2049地图的渲染结果。
测试用的高度图，大小为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。网格着色模式
表6.1：4097×4097地图的渲染结果。
用的高度图
C=35,C2=3.5.三角形数量10877。视野距离6000。FPS=137
本算法的速度基本上只和C,C2有关，图6.1为这两个因子和速度、三角形数量之间的关系。图中的测试数据中C=35恒定，C2从2.5到10.0。由于这两个由图可见，速度和三角形的数量和C×C2大致是先线性关系。
图6.1 三角形数量，FPS和C×C2之间的关系。红线为FPS值，绿线为三角形数量
在选择4097×4097的地图时，算法运行速度上没有任何的变化，因为需要渲染的地形区域仅限于视见体内部。当选择8193×8193的地图时候，由于内存缺页引起的丢帧就比较严重，如果在Windows98下就基本不能运行。
第三部分：真实感场景的生成技术。
第七章：天空体和镜头眩光
第八章：公告板技术
第九章：地表的细节
第十章：景深处理
第十一章：运动模糊
第四部分：结论和展望
附录
A:地形数据的生成
B:参考文献
第三部分
真实感场景的生成技术
引 言
一个室外场景渲染引擎必须要具有真实感的渲染能力，这些能力包括让地形表面有更多的细节、渲染地表植被等，甚至各种天气效果。所有的这些都能让场景看起来更加的自然，更加的逼真。在下面的几章中，本文将实现其中几种主要的项。
第七章：天空体和镜头眩光
1．天空体：如果一个室外场景中看不到天空是不可想象的。蓝天白云的天空能让视野中的变的清朗。而布满了乌云的天空则能让场景看起来更加的压抑。通常天空体的实现有圆形的和盒状的。圆形的天空体有很多的优点，但是比较复杂，尤其是映射纹理的时候。盒状的天空体则非常的简单，它的主要缺点是离天空边缘近的时候天空会有非常明显的变形。关于天空体几何模型的生成很多文章都有介绍，如[参考文献33]就是一篇很好的天空体制作教程。
图7.1圆形天空体示意图。左边为半球状天空体，右边弧顶状天空体。图片来自[参考文献33]
天空体最难的是纹理的生成，当然你可以找一张天空的照片，但是这样天空是静态的。其次是用算法动态生成天空的纹理，生成这种纹理的算法通常是使用Perlin Noise。关于生成天空的精彩文章在http://freespace.virgin.net/hugo.elias可以找到。这种方法生成的云彩真实性非常的好，但是致命的缺点生成大纹理的时候速度不够快，虽然能达到一定的实时性，但是应用到整个引擎中的时候，速度就非常的慢。最后的方法是用天空的视频文件做纹理，这种方法虽然速度还不是十分的快，但是它比用Perlin Noise生成纹理的速度还是要快的多。（本文的演示程序附带了一个演示视频纹理的程序，它使用DirectShow来播放视频文件，将播放结果作为纹理映射到几何体上。）
2．镜头眩光：稍微有一点摄影经验的人都知道，当我们把摄影机的镜头对准发光物体的时候，会有光晕现象产生，这种光晕也称为镜头眩光。光晕的大小和镜头有关。当我们在场景中放置一个太阳的时候，如果实现了这种光晕现象会有很惊人的效果。
太阳的模拟非常的简单。只要在场景的特定位置放置一个圆形物体就可以了。镜头光晕则需要一些额外的处理。首先我们来看一个眩光体的位置的。如图7.2所示。
图7.2镜头眩光示意图，左图为用Photoshop生成的效果图，右图为其组成部分示意图。
镜头光晕由一系列的光环组成，所有的光环排列在一条直线上。这条直线由发光物体位置和屏幕中心确定。这些光环的形状则有多中方式，通常用一张放射线状的图用来作为发光物体的光芒，另外的则用不同厚度的环状图像。
我们组合这些光环的时候需要使用Alpha Blending功能把这些光环叠加起来自然的融合到场景中去。通常我们采用的Alpha Blending公式为
所有的光环都是作为二维物体绘制到场景中去的。因此，发光物体在屏幕上的位置需要通过自己计算得到，在计算发光物体在屏幕上的位置的同时我们还可以得到这个位置的Z-Buffer的信息来判断是否能看到发光物体，当发光物体不可见的时候，光晕自然也不可见。下图为一个用上面算法生成的镜头光晕的例子。
图7.3，镜头光晕示意图，左图为独立效果，右图为组合到场景中后的效果图。图片来自本文的Demo
最后必须注意的是，眩光体必须在场景中所有的物体都绘制完毕后才绘制。
第八章：公告板技术
公告板（Billboard）是一种始终朝着观察者的一个物体。通常它是一个多边形。室外场景中通常有一些物体，比如说树木，柱子一类的物体，要么是细节非常的多以至无法用模型来表示，要么是从任何一个方向都一样（如柱子）。我们就简单的把这些物体用一个多边形加纹理映射来近似的表示。
用Billboard来表示树木非常的有效，著名的模拟驾驶游戏Need for Speed 5中的树木就是用这种技术实现的。我们所看到的树木其实只是一个矩形，如图8.1所示，矩形可以绕着一根轴旋转，使矩形始终对着观察者。因此无论你从哪一个角度去看，你都只能看到矩形的正面，而不会看到扁的一面。
图8.1Billboard模拟树木的示意图
除此之外，Billboard通常还用在粒子系统之中，因为3D场景中的粒子要始终正对着观察者。这种应用的典型例子就是Quake III和Unreal中绚丽的子弹光焰。
Billboard的实现关键在两个地方，其一是纹理贴图的模式，对于像绘制树木这一类形状不规则的物体，通常是采用透明贴图的模式，在OpenGL/Direct3D里我们可以采用Alpha test的功能。对于想粒子系统则一般采用Alpha Blending的功能。第二个关键的地方就是如何让多边形的一个面始终朝着观察者，如图8.2所示。
图8.2Billboard旋转角度的计算，其中红的箭头为摄影机的朝向，蓝色的箭头为Billboard原来的朝向，z为转动的中心轴
我们只要把多边形旋转一个角度r就可以了。角度r的大小可以用如下的公式去计算: 。转动的中心轴则可以通过如下公式计算： 。
第九章：地表的细节
地表细节涉及的方面非常的多，主要的有如下的方面：地面纹理，地面阴影（亮度图）。
1. 地面纹理 由于室外的场景比较大，通常需要一个很大的纹理来表达地面的细节信息。但是太大的地表纹理一来要占用很大的纹理内存，二来图形卡也不一定能支持。
解决这个问题的方法通常有两种，一是把大纹理分割成小的单位，动态加载需要的纹理（这种技术也称为Texture Tiling，详见[参考文献24]）。另一种方法是采用多遍纹理映射（Multi-Stage Texture mapping），它用一个较大一点纹理来表达地形的大概特征，然后再用一个小的纹理来和第一个地形调制（Texture blending）再一起，第二个纹理通常采用循环贴图（即贴图的u,v坐标大于1）。不同的细节纹理可以表达不同的地貌。
相比之下，第二种方法更加的简单，效果也更好，唯一需要注意的是不同细节纹理过渡的地方。要事先混合好过渡处的纹理，不然在不同的细节纹理过渡处的地貌变化会非常的生硬，十分的难看。
图9.1细节纹理示意图，左图为没有使用细节纹理，右图为使用了细节纹理。图片来自本文的Demo
2亮度图 在一个3维场景中增加光照和阴影效果可以更加提高场景的真实程度。
光照的计算需要为各个三角形指定法向量，动态计算法向量速度太慢，事先计算好法向量则需要大量的额外存储空间，而且在LOD算法中存储法向量也不是一件容易的事情。另一个问题是阴影问题，实时阴影的生成一直是图形学中的一个难点。何况在室外大场景下，实时动态生成的阴影基本是不可能的。
解决以上两个问题的一个折中方法是使用亮度图，然后把亮度图和地面的纹理进行调制，得到最终的地面纹理图，这种方法在运行时刻不需要额外的计算，也不需要额外的存储空间。
计算亮度图的时候，我们需要给场景指定一个光源的位置，这个位置通常是镜头光晕的发光体（太阳）的位置。一个点的亮度由所有共享这顶点的三角形决定。其中任何一个三角形的亮度计算如下图：
图9.2。亮度图的计算,其中r 为三角形法向量和光线方向的夹角
根据常识，只有朝着光源的面才会被照亮。假设全场景的环境光的强度为Ie，则这个如图9.2中三角形的亮度I由下面的算法决定：
if cos (r) > 0
I = cos (r) × (1 – Ie) + Ie;
Else
I = Ie;
阴影的计算则如下图所示：
图9.3，阴影的示意图，其中A点在阴影区内，B直接被照亮
确定一个顶点是否在阴影区内的时候，我们需要逐个检查这个顶点和光源之间的顶点，验证是否由顶点挡住了光源的光线，如图9.3，很明显光源的光线不能直接照到A，所以A在阴影区内。如果一个点在阴影区内，则它的亮度就直接等于环境光的亮度Ie。否则它的亮度由图9.2导出的算法决定。
最后我们还需要把计算得到的亮度图和纹理调制到一起，本文采用最简单的方式，就是把亮度值（0-1.0）乘纹理图上对应点的各个颜色的分量即可。
第十章：景深处理
通常使用计算机渲染得到的图像都非常的犀利，不管远的还是近的的物体看上去都是很清晰。但是事实并不是这样的，离观察者远的东西看上去会显得模糊一些，而不是处于两只眼睛观察的焦点上的物体也会模糊一些。
实现第二现象的方法在[参考文献24]的4.2和9.2节由详细介绍，而且实现这种效果也不是十分的必要，对渲染速度的影响也很大。这里就不作介绍。至于第一种现象，最简单有效的方法就是使用雾。关于雾的详细内容在几乎所有的OpenGL,Direct3D的书籍上都有介绍。
雾的计算方程通常有三种，本文推荐采用的公式为 。使用了雾效果的另外一个好处就是可以把远处的（位于视见体外部的）三角形裁剪掉也不至于产生“跳出”现象，因为远处的景物已经完全成为雾的颜色。它能提供一种无限远视野的假象。下图是使用了雾效果和没有使用雾效果的图例。
图10.1左图为开启了雾效果，右图为关闭了雾效果。图片来自本文的Demo
第十一章：运动模糊
运动模糊一种动态的效果，它是由于摄影机的底片的曝光需要一定时间，如果在曝光过程种场景发生改变，就会在底片上产生模糊效果，这种效果称为运动模糊。运动模糊现象在电影、摄影上非常的常见。
运动模糊在运动的场景中非常重要，你会发现如果缺少了运动模糊会带来严重的失真，看一下没有采用运动模糊的计算机动画，你会发现物体快速移动时，画面缺乏连贯性和真实感。在前面提到过的模拟驾驶游戏Need for Speed中，地面在赛车高速运动的时候就会变的模糊，给人一种扑面而来的感觉。
图11.1运动模糊示意图。图片来自[参考文献19]
实现运动模糊的方法在[参考文献19]里有详细的介绍，在这篇文章里作者采用了时间过采样的方式来实现运动模糊，这是一种精确的运动模糊的实现方式，通常这种方法要使用“累积缓存”（Accumulation Buffer）来实现，关于累积缓存的使用方法在OpenGL,Direct3D的书籍中均可以找到。一般情况下，我们只要累积3到5次就可以达到比较理想的运动效果了，但是这种有一个很大的缺点就是严重降低运行速度，当我们进行n次累积的时候，运行速度就是没有进行运动模糊时的1/n。这样的代价在一个游戏程序里是不能被接受的。
作为一种其次的解决方案，我们可以把先前的渲染结果保存起来，然后按一定的比例削弱以后混合到当前的渲染结果中去。假设当前的渲染结果为P1，先前的帧为 P2,最后得到的当前帧为P。混合的公式如下：P=(1-f)×P1+f×P2。其中f为模糊因子，f越大，运动模糊越明显。这种方法只需要渲染一次场景，对运行速度影响不是很大。下面给出这种方法在OpenGL下的实现步骤：
1． 首先建立一个足够大的纹理，
2． 渲染场景到帧缓冲区中。
3． 把保存先前帧内容的纹理设置为当前纹理。
4． 绘制一个和视口一样大的矩形，把这个矩形按上面给出的公式和步骤3中渲染结果混合在一起。
5． 把混合结果拷贝到纹理对象中（glCopySubTexImage）。
6． 重复步骤2-5绘制下一帧。
由于有些OpenGL的驱动不支持直接渲染到纹理的操作，因此用OpenGL实现起来比较麻烦而且速度受到的影响也比较大一些。在Direct3D中可以通过直接改变渲染目标来把场景渲染到纹理中，在速度上受到的影响要小一些，在实现上也要简单一些，但是基本原理还是相同的，这里不再赘述。下图是一个使用了这种方法的例子。
图11.2运动模糊。图片来自本文的Demo
第四部分：结论和展望
本文已经基本上实现了一个室外3D游戏引擎的渲染核心部分。虽然提供的算法不是十分的精确，但是速度非常的快，用本文算法实现的Demo可以在当前流行的个人电脑上非常流畅的运行。加上本文第三部分的技术后，画面质量得到很大幅度的提升。下图为本文的演示程序的屏幕截图。所有的效果都已经开启。
但是急待解决的问题还很多，主要有以下几个：
1. 内存管理 本文采用的内存数据结构虽然在一定的程度上考虑了内存缺页的问题，但是效果不是很好。由于地图是作为一个二维数组加载的，采用的是线性结构。数据的冗余比较大。可以考虑采用链式的数据结构来改善。
2. 几何形变。
3. 无限重复地图 一个地图再大也有一定的限度，当前许多的主流游戏采用的都是地图循环的方式，即沿着一个方向走到地图的边缘以后会返回到开始的地方，观察者永远也走不到地图的尽头。
4. 水面的模拟 室外的场景中水的存在是很正常的，比如说湖面，小河等。水面应该倒影四周的场景，绘制倒影一般借助于模板缓冲区绘制两次场景，但是这对于室外大场景的开销非常大而且实现也很困难。我们需要一种更加有效的模拟水面的方法。
5. 各种天气效果 本文只是简单的实现了天空体，真实的自然界中还有很多现象，比如下雨，闪电，下雪，刮风等。加上这些天气效果会使场景看上去更加的多变。
第五部分：附录
A地形数据的生成
生成地形数据的方法主要有两种：
一是使用使称为Perlin Noise的随机函数来生成高低起伏不平地形。Perlin Noise用来生成地形特别有效，关于这种方法在[参考文献14]里有详细的介绍。
第二种方法是分形，通常也叫Diamond—Square算法。这种方法则在用来生成几座山的时比较有效。关于这种算法可以在www.fractal3d.com上找到详细的介绍。
B参考文献和资源
参考文献
[1]. XiaoHong Bao and Renato Pajarola LOD-based Clustering Techniques for Optimizing Large-scale Terrain Storage and Visualization” Department of Information & Computer Science University of California .Irvine.
[2]. Stefan R?ttger , Wolfgang Heidrich and Philipp Slusalleck,Hans-Peter Seidel Real-Time Generation of Continuous Levels of Detail for Height Fields University Erlangen-Nürnberg
[3] P Lindstrom and V.Pascucci Visualization of Large Terrains Made Easy Lawrence Livermore National Laboratory August 7, 2001
[4] P.Lindstrom and V.Pascucci Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Lawrence Livermore National Laboratory May 8, 2002
[5] P.Lindstrom , David Koller , William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner Real-Time, Continuous Level of Detail Rendering of Height Fields In SIGGRAPH 96 Conference Proceedings, pp. 109-118, Aug 1996.
[6] Reinhard Klein and Andreas Schilling Efficient Multi-resolution Models for progressive Terrain Rendering
[7] Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller, Charles Aldrich and Mark B. Mineev-Weinstein. ROAMing Terrain: Real-time, Optimally Adapting Meshes. Proceedings of the Conference on Visualization '97, pp. 81-88, Oct 1997
[8] Thatcher Ulrich Continuous LOD Terrain Meshing Using Adaptive Quad-trees www. Gamasutra.com
[9] Luis Sempé, Terrain Rendering using Heightmaps March 2002, http://www.sphergames.com/
[10] Renato Pajarola, ETH Zürich Large Scale Terrain Visualization Using The Restricted Quadtree Triangulation
[11] 王宏武 董士海 《一个视点相关的动态多分辨率地形模型》 北京大学计算机图形研究所
[12] Hugues Hoppe Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering Microsoft Research
[13] Louis Castle, Jonathan Lanier and James McNeill Real-time continuous level of detail (LOD) for PCs and Consoles Technical Presentation GDC 2000
[14] Hugo Perlin Noise
[15] 中国游戏开发者网络 《BillBoard 技术详解》
[16] 中国游戏开发者网络 《BillBoard》
[17] 中国游戏开发者网络 《基于视锥包含的不可见物体消除算法》
[18] 中国游戏开发者网络 《OpenGL的渲染成纹理技术》（OpenGL Render-to-Texture）
[19] 中国游戏开发者网络 《运动模糊》（Motion Blur 原文见Hugo的主页）
[20] Michael Tanczos The Art of Modeling Lens Flares http://www.gamedev.net/
[21] Alan Gordie Lens Flare Tutorial http://www.gamedev.net/
[22]Jackie Neider ,Tom Davis and Mason Woo 《OpenGL编程权威指南》(OpenGL Programming Guide) OpenGL ARB Addsion-Weslly
[23]《OpenGL 超级宝典》人民邮电出版社
[24] Tom McReynolds Programming with OpenGL: Advanced Rendering SGI SIGGRAPH `97 Course
[25] Microsoft DirectX SDK Document
[26] Mesa Lib 4.03 Source Code
[27] Microsoft MSDN –OpenGL section
[28] OpenGL Specification (version 1.1 ,version 1.2,version 1.3 version 1.4)
[29]《计算机图形学算法基础》机械工业出版社
[30] 孙家广等 《计算机图形学》 清华大学出版社
[31] 清华大学远程教育 《计算机图形学》 第4章 第7节 《实时真实感图形学技术》
[32] Bryan Turner （Dreams Woo翻译）《ROAM实时动态LOD地形渲染》
[33] Luis R. Sempé, Sky Demo http://www.spheregames.com/
资源
NeHe's OpenGL Tutorials Nehe.gamedev.net
FlipCode www.flipcode.com
GameTutorials: http://www.gametutorials.net/
nVidia: Developer.nvidia.com
OpenGL: www.opengl.org/
Mesa: www.mesa3d.org
DirectX: www.microsoft.com/directX/
GameDev: www.gamedev.net
中国游戏开发者：Mays.soage.com
中国游戏资源网：www.gameres.com
