|
基于LOD的大规模真实感室外场景实时渲染技术的初步研究 part II&III(1)
第二章：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
| 
