室外大场景渲染技术研究与实现 游戏地图加载
室外大场景渲染技术研究与实现 游戏地图加载
2011年06月21日
http://nvidia.e-works.net.cn/document/200908/artic le8938.htm 第三章 室外场景地形的实时绘制技术
地形的绘制是指读取虚拟世界的地图信息，绘制出场景的地表，并实现角色在场景中实时漫游。它是室外场景实时绘制中最重要的部分，也一直是计算机图形学中一个重要的研究领域。尽管地形的绘制在不同的游戏中所采用技术会有所不同，但是他们总体上还是遵从一定的流程，如图3.1所示：
以下章节会逐步分析相关技术。需要说明的是本章探讨的"绘制"还不包括真实感的表现，可以理解为线框模式下的绘制。
3.1地形绘制所需数据
地形绘制所涉及的数据主要有：地形的高度图、缩放标尺、地表纹理图、地表纹理索引等。在游戏设计中，表现一个场景所需要的一系列数据往往打包放在一起。
3.1.1高度图
对基于三角形面片渲染的3D场景来说，地形的顶点信息就是指组成地形的所有三角形面片每个顶点的三维坐标。最简单最有效的地形顶点表示方法是使用高度图(heightmap)u利。
通常高度图是一张灰度图，它的长宽通常满足(2^n+1)。每个像素的灰度值表示地形相应位置的高度值，用连续的三角形面片来连接这些三维空间中的顶点就构成了地形的面片。高度值的值域范围0--255足以表现游戏中场景的地形起伏，如果需要也可以使用双字节，四字节或更高来描述高度值。在设计中很多游戏由于封装数据的需要，通常自定义高度图的格式，而不采用灰度图，但是其存储的数据本质上是一样的。
3.1.2缩放标尺
地形信息还应包括缩放标尺，用来表示在绘制时高度图中相邻两个灰度值之间相隔的X，Z方向上的距离值。比如一张33×33的高度图的缩放标尺是l米，则在游戏中我们可以看到一个32MX 32M大小的场景。此外，在Y方向上也有一个缩放标尺，负责地形高度的缩放。
3.1.3顶点法向量
地形网格上的各点都需要一个表面法向量。它可以用来计算光照，进行背面剔除，检测与表面的碰撞等。一个三角形的法向量可以通过三角形上两向量叉乘的方法轻松获得，而顶点级法向量可以通过共享此顶点的所有三角形的法向量求平均值来模拟，在很多情况下，这样的效果已经能够达到要求了。顶点处其实是没有法向量定义的，因为此处网格表面不连续。
3.1.4多种地表纹理及光照贴图
为了表现地形的真实感，目前游戏中的做法是通过多重纹理混合贴图来实现的。其中用到的贴图通常以各种图片格式保存。关于这种技术的讨论在真实感渲染章节会详细介绍。
3.1.5单个场景地形的数据结构
由以上的分析我们就可以得到单个场景地形的数据结构，如下所示：
3.1.6面片的构成
任何多边形模型都可以转换成三角形的集合，所以地形网格也是三角形的集合。如果三角形被各自独立地送至图形硬件进行绘制，共享的顶点数据就需要执行重复冗余的运算，并且相同的数据还被传送至少两次以上。降低这些额外开销的一个方法就是把彼此相邻的三角形构建成三角带(strip)。首先，把第一个三角形的三个顶点放至strip之中，然后将其余的三角形顶点依照相邻顺序依次放至strip中，每个三角形只需要加入二个顶点。缺省条件下，在strip中彼此相邻的顶点都构成了连接两个相邻三角形的公共边。如果连接规则(顺时针或者逆时针顺序)需要发生改变，则可以使用swap命令交换顶点顺序，或者重新将某一个顶点放入strip之中。扇形三角形带(Triangle fans)可以看作是三角带的一种退化形式，只是其中所有的三角形都共享一个公共顶点。图3.2是三角形带的表示方法：
V0，V1，V2，V3，V4五个顶点构成了表示三个三角形的三角形带。注意描述三角形带时，顶点的顺序很重要，因为是遵循一定连接规则(顺时针或逆时针)的。在OpenGL中生成最右方的三角形带的代码如下：
3.2 LOD地形网格简化算法的基本思想及意义
所谓地形网格的简化是指通过算法减少提交到显卡的顶点，以减少每帧同屏渲染的三角形数量，借以提高渲染速度。
细节层次(LOD，levels of Details)技术是一种符合人视觉特性的网格简化技术。我们知道，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个像素甚至是一个象素。我们完全没有必要为这样的物体去绘制它的全部细节，可以适当的合并一些三角形而不损失画面的视觉效果。对于一般的应用，我们通常会为同一个物体建立几个不同细节层度的模型。这样的技术应用在地形渲染中，也称之为多分辨率地形(Multi-Resolution Terrain)。下图就是一个多分辨率地形网格：
在开发3D游戏时也有不采用基于LOD的地形网格简化算法的做法。典型的游戏有韩国游戏公司开发的著名3D网游《奇迹》，每个Tile场景地形它用257×257的高度图构成，采用静态载入场景数据的方案同样产生出了美妙的场景。对于这么小的场景，当然没有必要做地形网格的简化，现在的一般显卡足以能够应付。之所以他能成功应用这种方式，是因为在设计场景时限制了地形的高低起伏，使地形趋于简单，缩放标尺取得很大，同时用纹理和光照贴图来弥补地形本质上的单调。另外，如果运用基于外存的动态数据载入算法，理论上也可以不用基于LOD的地形网格简化算法。
随着3D游戏的成熟，玩家需要有更真实的体验，因此地形变得更加复杂，场景变得更加巨大，地形的绘制需要很多数据参与，对系统资源消耗巨大。如果一点也不进行地形网格简化，试想一个1025 X1025的场景就将生成2M个三角形，渲染大的场景时显卡的处理能力很难跟上。在显卡的数据吞吐能力有限的情况下，游戏场景渲染中普遍基于LOD的思想，减小绘制多边形数目。它能在牺牲适量CPU资源的前提下大大减轻图形卡的数据负载，使CPU与GPU之间没有明显的瓶颈，从而达到实时渲染大地形的目的。
基于LOD的地形网格简化算法分为动态LOD和静态LOD算法。动态LOD算法是在每帧渲染之前都经过计算重新确定送入显卡的顶点。所有的顶点数据全部需要参与运算。ROAM算法和基于四叉树的动态LOD算法都属于此类，GeoMipMap算法则是静态LOD算法的代表。
3.3 ROAM算法
1997年，Duchaineau提出了实时优化适应性网格(ROAM，Real-timeOptimalAdaptive Meshes)算法瞳1，它是一种基于规则网格的连续LOD网格构造算法。其基本思想是在对地形进行三维显示时，依据视点的位置和视线的方向等多种因素，对表示地形表面的三角形图元进行一系列基于三角形二叉剖分分裂与合并，最终形成和原始表面近似且无缝无叠的简化连续三角形表面。
ROAM的基础是等腰直角三角形的一个性质。等腰直角三角形可以从直角顶点到斜边引一条垂线，这条垂线把这个三角形分成了两个小的等腰直角三角形，并无限制的递归分下去。而从另一个角度来看，这正好构成了一个二叉树，每个三角形都是把它分开而生成的两个小三角形的父母(parent)。根据这条性质，只要计算出哪些三角形需要被分割开、哪些三角形需要合并成为自己的父母，就可以做到控制LOD(分开就是增加LOD，合并就是减少LOD)。图3.5显示了1～4层三角形二叉树和相应的层次结构。
当把一个三角形分成两个的时候，会在斜边上增加一个顶点，是由斜边的两个端点插值求得。不过高度却不能插值。因为高度是按照相应的地图数据来的(比如heightmap)。所以，就存在一个插值以后的高度和实际高度不匹配的问题(会产生裂缝)。为了解决这个问题，就需要调整Y轴上的值来升高或者降低这个顶点，这个顶点高度的调整距离就称为误差量。
要确定一个三角形是否要被分割，就要看它是否能精确的描述地形的高度数据。如果可以的话，自然就不用分割了，多边形越少越好。如果不能的话，就细化它，也就是分割掉，直到所有的小三角形都能够精确表示地形数据为止。
通过不停的分割，三角形越来越小，每个三角形在高度图上所覆盖的面积也越来越小。那么，总会分割到足够小，使得三角形的面积和高度图上一个点的面积之比为l：l，分到这里就不用再分了。通过检查所有孩子的误差量，我们就找到了一个描述三角形是否需要分割的精确方法。当递归的遍历这棵树以后，就能够找到这棵树里面的最大误差量，就是所谓的largest error metri c。这个最大误差量如果是O那就是完全符合实际高度了，这个值越大，就越不符合。
用每个三角形的误差量和镜头到该三角形的距离比较，用以判断是否一个三角形需要分裂。用以给每个三角形做测试的值是人为定义的，这个值又叫错误容忍度(error metric tolerated)。通过错误容忍度对每个三角形做测试，小于这个容忍度的三角形就被留下(不分裂)，大于这个的就被分裂掉，然后再分别对被分裂的三角形的两个儿子做分裂。如果加入了视角依赖(view-dependence)的话，就需要通过镜头到三角形的距离来调整这个容忍度了。镜头越远，容忍度就越大，而镜头越近，容忍度就越小。'
此算法的优点在于：可动态的改变每个网格；可在渲染时控制每个网格的生成与否；可以和纹理坐标很好的结合在一起；可控制地形三角形的最大数目；可以根据坡度的不同自动调整LOD的细节程度，也就是说在地形坡度大的地方LOD细节程度高，在地形坡度小的地方LOD细节程度低；可以根据到观察点的距离自动调整LOD的细节程度，也就是说在离观察点近的地方LOD细节程度高，在离观察点远的地方LOD细节程度低。
3.4基于四叉树的动态LOD算法
3.4.1算法思想
此算法是Lindstrom提出的n劓，他用了一个叫四叉树(Ouad Tree)的结构来描述地形，先把可视范围内的地形分割成四等份矩形子块，依靠计算判定因子检测四个子块，如果检查到某个子块的网格精度达到所要求的绘制精度就不需要往下再分割；否则就把此子块再分割成四等份更小的子块，依次递归分割下去，直到所有子块中的矩形网格都达到渲染精度。
3.4.2此算法涉及的难点
●对T形裂缝的处理
由于不同层次间的采样间隔不同，在可视化过程中会出现缝隙，这种缝隙必须进行专门的处理.如图所示，上方矩形具有较高的分辨率，而下方矩形的分辨率较低，这使得矩形间的连接处出现了末被覆盖的区域(阴影处)，从而在地形绘制时就产生了"裂缝"。
每个.LOD层次区域节点均为正方形，在分辨率低的四叉树区域节点上，四个方向均可能出现缝隙，所以必须依次用自身节点的分辨率大小比较四个方向上临近节点的分辨率大小。如果前者小于后者，则必须通过在相邻边上加一条边来实现裂缝的消除。当自身节点分辨率与相邻节点的分辨率相差不止一级，那么还必须递归比较并添加边，直到完全消除裂缝。
●判定是否细分
子块离视点的距离和地形的平坦度共同确定是否需要进一步细分以达到所要求的渲染精度，从而使最终分割后的叶子节点达到最优。离观察者视点越近的地方细节越多，地形越不平坦细节越多。
子块离视点的距离d可以用公式表示如下：
其中(Xl，Y1，Z1)为视点坐标，(XO，YO，ZO)为子块的中心坐标。对一个子块区域平坦度的计算如图3.7所示：
对于图中这个子块的平坦度，先计算出高度值h卜h8，找出其中最大的高度值hMax，最小的高度值bMin，令err=hMax-hMin。err即是此子块的平坦度。
err的值越大就意味着子块越不平坦，网格细节应该越多。
最终，综合考虑距离和平坦度两个因素得出判断是否细化的标准：
如果err*r／d-k>O则继续细化，反之则不。(k为一个可变的控制值，r为子块的i／2边长，err为子块平坦度，d为子块到视点的距离)。 3.4.3算法运行步骤 (1)初始化顶点数组，建立完全四叉树并初始化，使每个节点描述清楚自己对应的区域地形。
(2)实时渲染：首先对每个四叉树节点进行视锥体裁剪，确定进行渲染的四叉树节点，再渲染这些节点。
a.对节点进行视锥体裁剪。
b.确定哪些节点需要渲染：
先计算本节点所管理的地形区域离视点的距离，再计算其平坦度，两者共同确定渲染精度值。
根据渲染精度值和判定标准来确定是否需要进一步细分，对于需要细分的就按四叉树思想递归细分，而不需要细分的就设置它的渲染标志位为真。c.遍历四叉树，渲染标志位为真的节点，并判定本节点区域网格在渲染时是否会出现T型裂缝。判定方法是通过和四周相邻的节点比较细节分辨率值，如果小于相邻节点则做修补裂缝处理。
(3)释放资源。 3.4.4算法相关代码
以下是1025×1025大的高度图用基于四叉树的LOD算法在线框模式下生成的地形网格：
3.5游戏中地形绘制更好的方案.
随着图形卡数据吞吐能力的不断提高，每秒钟处理上亿个三角形己不再困难。很多计算，比如几何变换和光栅处理都可以交给GPU去计算。所以在GPU数据吞吐量很大的情况下，如果一个算法在剔除渲染顶点的过程中占用了太多CPU资源，出现GPU等待CPU的情况，那么即使算法在剔除多余顶点方面做得很好，总体绘制效率也不是高效的。上面讨论的两种动态LOD算法(RoAM和基于四叉树的动态LOD)都存在这方面的缺陷。并且，受硬件带宽的限制，频繁地传输海量顶点数据，使得时间集中消耗在数据"迁移"过程中。过多的DP(Draw Primitive)也使得图形卡不能发挥最大功效，造成资源极大浪费。所以要适应现代图形卡的硬件架构，算法必须改进，几何多重映射(GeoMipMap，Geometrical Mipmapping)等算法由此产生。
本设计在GeoMipMap算法的基础上，改进了原算法关于抑制不同细节分辨率模型之间突变的处理方法，使得在提高绘制效率的同时，保证了绘制图形的质量。通过使用查表法的分块网格顶点数据组织方式，使得CPU的工作进一步减轻。此外，本设计还利用了现代图形卡的存储功能来优化地形的绘制。
3.5.1 GeoMipMap算法
●基本思想
GeoMipMap算法是Willem根据纹理多重映射的概念提出的H3，他把整个地形场景在XZ平面上进行分块(block)，比如用33×33的block把1025X 1025的地形表示为32×32个block。每个分块可用不同分辨率的网格模型来描述。在同一分块内，网格模型的分辨率相同。采用隔行采样的方式生成不同分辨率的网格。整个地形的模型表示和组织如图3.9所示：
不同的block之间互相拼接时，如果分辨率不同则可能产生裂缝。为了消除裂缝，在较高分辨率的block边界上，忽略一些点作为网格顶点，如图3.10所示：
每个block分辨率是通过屏幕空间误差H3来决定的。在地形数据预处理阶段，取一个屏幕误差阀值￡(一般取4个像素)，预先计算出当e等于4个像素时，视点到block的距离d和相应的block分辨率，并保存在查找表中。当实时绘制时，根据视点到每个block的距离查找表中的d，查找决定该block的网格分辨率。
●优点和不足
GeoMipMap算法的网格生成方式显然和ROAM算法以及基于四叉树的连续性LOD算法大不一样。以基于四叉树的连续性LOD算法为例，他是通过自顶向下的方式用四叉树递归地将地形分成一个个小地形块，越往下细分，地形块越小，直至不能细分。当视点发生改变时，所有的顶点都必须重新参与细分的递归运算，这种算法能根据实际情况最大程度确定整个地形的网格分辨率，但计算量很大，并且递归层次很多，CPU的负载极大。而对于GeoMipMap算法来说，当
视点改变时，只需要判断可见的每一个block的网格分辨率应该是多少，block内部的顶点并不参与计算。虽然这种做法不能最大化减少进入渲染管道的顶点，减少三角形面片，但是增加的这些渲染顶点对现代图形卡来说是不会影响绘制速度的。相反，由于他减小了实时绘制时模型简化的计算复杂度，速度得到极大提高，所以他是符合现代图形卡硬件架构的地形绘制算法。此外GeoMiaMap相对固定的三角形面片组织方式，也使得进入固定渲染管线的顶点能更好的组织成三角形带，大大减少传入图形卡的顶点个数。
但是，这种算法由于不是连续的LOD算法，也就是说LOD的粒度比较粗放，因此在block的网格分辨率发生改变时，会产生网格形状的突变，使得在地形漫游时，图形过渡不自然。虽然通过屏幕投影误差来选择block的网格分辨率可以使突变的效果有所减轻，但对用户来说仍比较明显。本设计通过线性插值的思想，使层次过渡由突变转为逐步递进，极大减小了这方面的不足。
3.5.2 GeoM i pMap优化算法
.地形数据的总体组织和表示
我们首先读入一个场景的高度图数据(heightmap)，保存在一个顶点线性表中，然后把这个场景在XZ平面上划分成均匀大小的多个block。block的大小按需求而定，其边长满足2l+l，如9×9，17×17，33×33等。如果地势总体比较平坦，我们可以选得大一点，如果对地形的细节要求较高我们可以选得小一点。本文以17×17作为block的大小。block通过顶点索引所组成的三角形带描述他负责的一片小的区域。整个场景用一棵完全四叉树把这些blocks组织起来。实时渲染时完全四叉树负责场景的裁剪，决定哪些blocks应该绘制，然后计算可见block的网格分辨率，从而得到整个地形要渲染的三角形面片。其数据组织图如下所示：
用面向对象的方式描述地形对象：
当地形是超大地形绘制时，我们采用多线程机制加上场景缓冲池的方法实现大地形数据的动态调入和管理。每一个场景Tile作为动态加载单元，用一个缓冲池来管理，用单独线程来维护。详细讨论在3.7节。
. block多分辨率网格模型的构造和数据组织
Willem在他的论文中指出当细节层次不同时block的顶点取舍方法，以及为了避免出现T型裂缝，block的边界顶点应该怎么调整。在他的思想基础上，本设计提出一种基于查找表的block三角形带生成方法。
我们把block的中心地带和边界分开对待。在预处理阶段就生成五个顶点索引表。如图3.12所示：
中心地带索引表负责生成block中心的三角形条带，其索引参数就是自身的网格分辨率。边界索引表负责生成与其他block相邻区域的三角形带(防止T型裂缝)。索引参数有三个：自身的网格分辨率，相邻的方向，相邻block的网格分辨率。
网格都使用三角形带(Triangle Strip)的方式生成，有些地方需要生成一些退化三角形，用于三角形带的连接。运用三角形带的方式比三角形扇和纯粹三角形方式更能减少顶点个数，提高绘制效率。
这五个位置的网格所关联的索引表一起就能够描述任何一个block网格所有顶点的相对位置(在block区域内的位置)。在场景渲染初始化时，我们读入block的五个LOD顶点索引表，得到block的不同分辨率网格。在实时渲染的时候，针对一个特定的block，我们可以根据这个block在场景中的起始位置，他的网格分辨率，和他四周block的网格分辨率，直接查表得到这个block完整的三角形带顶点索引，减少了CPU的判断和计算量。内存中只保存一个block网格顶点的相对索引，不是整个场景的所有block的顶点索引都保存，因此不会造成什么内存消耗。
. 用面向对象的方式来描述block
block是本算法很重要的对象，可以描述如下：
. 利用线性插值逐步过渡不同分辨率的网格模型
当block的网格分辨率次发生变化时，其网格模型可能变化较大，由于变化是在瞬间完成的，极易被观察者察觉。但如果我们把这种变化由突变改为渐变，用户就不易察觉，其视觉影响也就可以忽略不计。
我们在预处理阶段已经得到一个合适的查找表，可以查出block的网格分辨率c与block到视点的距离d之间的对应关系。我们假设d=lOOOm时c=n+l，d=2000m时c=n。
如果现在d=1500m，则网格的分辨率正处在n和n+l的过渡阶段。我们取网格顶点为c=n+l时的索引，他比c=rl时多出一些细节顶点，对这些多出的细节顶点，我们对其高度进行线性插值，使其缓慢在分辨率n+l和分辨率rl之间过渡。如图3.13，v3为高分辨率时出现的细节顶点，v4为模型在低分辨率时v3的初始点。随着网格向高分辨率过渡，v4逐步过渡到v3。v'的Y坐标由下面的公式决定：
如3.13图：
采用这种插值的手段后，只增加了很少的计算，视觉效果上却得到了很大的提高。
.利用显存保存地形的顶点表
现代图形卡已经支持把一定大小经常使用的数据直接保存在显存中，所以如果我们把经常使用不频繁变动的数据保存在显存中，可以避免大量数据在渲染时频繁从内存传输到显存。在实验中通过0penGL的VBO(Vertex Buffer Object)方式把顶点线性表数据保存在显卡中，经比较渲染速度大幅提高。
.描述算法的流程
预处理阶段：
(1)载入地形数据，初始化顶点线性表。
(2)初始化所有分辨率的block模型所对应的三角形带顶点索引表，此表保存的是组成三角形带的相对顶点索引。生成描述整个地形场景的block数组，每个block记录自身在场景中的绝对位置。
(3)构造完全四叉树，每个子节点对应管理一片区域(一个或多个block)，设置包围球半径。每个叶子节点都对应一个block索引。实时绘制阶段：
(4)遍历完全四叉树，根据空间裁剪算法，得到可见block的索引。
(5)计算这些block的网格分辨率，根据分辨率和网格的三角形带索引表，顶点表，可以得到组成地形网格的所有三角形带顶点的完整信息。
(6)根据前面介绍的线性插值方法，调整相关顶点的高度信息。
(7)送入渲染管道绘制。
(8)回到(4)。
●测试结果
我们使用大小为2049×2049的高程图作为实验数据，以Athlon2500+，DDR IG，ATI 9550，128M显存作为硬件环境对上述算法进行测试。程序用VC+OpenGL在windows平台上完成。其中分块大小为17×17，共分4个细节分辨率，以下是场景绘制的网格形式截图：
从表3.1中的技术参数统计来看，新算法的渲染效率有很大提高，能满足大规模地型的渲染要求。
3.6地形的空间管理和可见性剔除算法
我们只对地形进行分辨率上的简化是不够的，摄像机在场景中只有一个可见范围，怎么样有效的剔除不需要渲染的地形部分，这就要涉及到地形的空间管理算法，可见性裁剪算法口9|。四叉树，八叉树，Bsp树，背面剔出等很多其他方法都是针对这个目的而提出的。本设计的可见性剔除采用了如下流程：
3.6.1按距离剔除
单靠视锥体剔除已经能剔除大部分面片，但是在他之前有一步距离剔除也是有必要的，因为他的计算很简单，就是通过计算地形block的包围球心与视锥体的距离，距离大于系数k的blocks统统剔除。k的确定一般与天空盒子的大小有关。
3.6.2视锥体剔除 从3D到2D投影过程中，需要一个投影体，只有当物体处于这个投影体中的时候，我们才能看到这个物体，否则物体将被裁剪掉。这个投影体通常被称为视见体(View Frustum)。在进行正交投影的时候，投影体为一个长方体，在进行透视投影的时候，投影体则为一个平头锥体，所以也叫视锥体。
空间中物体与视锥体的关系有三种：在视锥体内，在视锥体外，与视锥体相交。只要我们排除在视锥体外的物体，也就是排除在视锥体外的三角形面片就能大幅提高渲染的效率。
.求视锥平面系数
视锥体有上、下、左、右、近、远，共6个面组成。一个平面的方程可以表示为Ax+By+Cz+D=O。首先，把视锥体变换为长方体状的裁剪空间。如图3.16所示，左图为世界空间中的视锥体。右图为经过变换后的裁剪体。
我们规定朝投影体内部的方向为平面的正方向，判断一个顶点是否在投影体内部时，只要把顶点坐标代入到六个面的方程中，通过检查结果的符号就可以判断点是不是在投影体内部（所有的符号都为正）。世界空间的投影体在经过投影变换后，会成为一个范体。我们很容易得到这个范体的六个面的方程。
我们假设这六个面中某个平面上有一个点(x0,y0,z0,1)，在进行投影变换之前的坐标为(x0",y0",z0",1)。这个平面的方程为Ax+By+Cz+D=0。投影变换前，在世界空间中的方程为A"x+B"y+C"z+D=0，则点必须满足：
如果变换矩阵为T，则投影前后的点要满足(xO'，yO'，zO'，1)XT=(xO，yO，zO，1)。通过这三个等式，我们可以得到
再根据投影空间中范体的六个面的方程，我们现在可以很容易的得到世界空间中的投影体的六个面的方程。我们已经有了裁剪体的方程，当我们需要判定一个顶点是否在视锥体中的时候，这六个方程已经足够了。在OpenGL中得到裁剪体六个面的方程系数的伪代码如下：
.用包围盒、包围球做物体的视锥体剔除
对于物体是否在视锥体区域内的判定，我们可以借助包围球或者包围盒隅1。在课题中，选用了包围球，也就是地形的外接球。
视锥体和包围球是否相交的经典算法是检查包围球的球心到视锥体每一个平面的有向距离di，i∈[0，5]，设球体半径为R，如果存在一个i∈[0，5]使得di≤一R，那么包围球是在视锥体外，如果存在一个i∈[0，5]使得di≤R，那么包围球和视锥体是相交，否则包围球是在视锥体内。代码如下：
3.6.3地形的空间管理与视锥体剔除 对地形的三角形面片而言，怎么判断哪些面片在视锥体中，我们不能把面片的所有顶点都计算判定一次，更好的算法是把整个场景分成一个个方便管理的区域，以每个区域为最小单位做视锥体剔除。由此空间管理算法出现，他的作用就是在空间上快速排除不需要渲染的面片。
. 用四叉树(Quadtree)管理空间
四叉树结构是每个父节点对应四个子节点的数据结构。我们可以把地形的三维空间近似看作XZ的二维空间，根节点表示整个正方形地形区域，其子节点分别可以表示"左上"，"右上''，"左下"和"右下"四个象限区域，那这四个子区域又可以递归划分下去，如图3.17：
四叉树中的阴影节点就是代表了地形中的阴影区域。四叉树的叶子节点代表了地形的最小可分区域。当要查找某一个区域时只需要遍历这个完全四叉树就可以了。
空间四叉树节点的数据结构可以描述如下：
.用八又树(Octree)管理空间
八叉树是在四叉树的基础上演变而来的。四叉树只可以描述二维空间，八叉树它可以描述三维空间。如图：
八叉树的空间管理一般用在有很多其他物体的场景中，比如建筑，树木等物体参与到游戏中来的时候，可以通过八叉树对这些物体进行统一管理，方便进行碰撞检测、视锥体剔除等。如果只是针对地形的裁剪，用四叉树足够了。
.用空间四叉树节点做视锥剔除
我们从上到下，依次遍历四叉树的节点，判断节点代表的区域与视锥体的位置属于哪一种：a.与视锥体相交， b.在视锥体外，c.在视锥体内。
如果是情况a，递归判断这个节点的四个子节点。
如果是情况b，剔除该节点。
如果是情况C，渲染这个节点代表的地形。
得到可渲染节点的代码如下： 3.6.4地形遮挡剔除，背面剔除 ●背面剔除
当我们在三维场景中漫游时，只能看到地形起伏的正面部分，地形的背面部分被正面部分的网格面片遮挡，因此在绘制地形网格时，这部分网格可以不绘制。背面剔除算法的目的就是将这些看不到的背面网格去除掉，实现步骤如下：
(1)计算位于一个给定网格多边形平面上的某两个向量的矢量积，得到这个网格多边形的法向量，这两个向量可以通过多边形顶点的差分来得到。在求解网格平面的法向量时必须保证两个向量的矢量积的方向朝外，否则无法得到正确的法向量值。
(2)计算视点观察方向与法向量之间标量积的符号，由此决定它们之间是否形成大于90。的角。视线与网格平面之间的关系如3.20图所示：
当视线与网格平面法向量之间夹角大于90。时，表示这个多边形位于起伏地形的背面，需要剔除，否则不被剔除。
在实际编程时，地形网格的法向量可以预先计算并存储在内存中，当漫游时，只需要直接计算视线与法向量的夹角就可以判断网格是否要被剔除。如果对每个三角形面片都去判断其是否是背面的话，计算量是很大的，这增加了CPU的负担，虽然能够最小化参与绘制的面片，但是CPU的计算很容易形成效率瓶颈，结果绘制效率有可能反而没有不剔除背面的做法高。因此，这种算法必须针对具体情况，适当选取。如果场景大多是峰峦叠嶂，这时就可以考虑使用此算法。
●遮挡剔除
遮挡剔除大致可分为两类：针对视点的遮挡剔除和针对视点单元区域的遮挡剔除。前者判断两个物体之间相对于一个视点而言的遮挡关系；后者则判断两者间相对于一个连通区域(即所谓视点单元区域)的遮挡关系，由此得到的两个物体之间是否遮挡的断言对该区域中每一视点都成立。
针对视点的遮挡剔除算法大都需要根据视点位置将挑选出的遮挡物在图像空间离散化，并将其离散表示组织成层次结构，剔除时将场景中物体的层次包围盒自顶向下地与遮挡物的层次离散表示作比较，迅速拒绝被遮挡物体。由于对遮挡物采用了离散表示，可以很容易地实现多个遮挡物的融合，但由于离散化往往需要借助于图形加速卡，而从图形加速卡中读取数据相对较慢。另一些针对视点的遮挡剔除方法直接在三维物体空间中判断遮挡关系，但这使得多个遮挡物的融合变得困难。由于针对视点的遮挡剔除不一定需要严格的可见性信息，而只需知道潜在的可视的物体集合(Potentially Visible Set，简称PV$)。由此发展出另一类以PVS计算为核心的算法。PVS的好处就是数据为静态，渲染的时候不需要计算，但它对动态物体的判断不够好。
总的来说，由于现在显卡对三角形面片的吞吐量快速增加，如果为了少量剔除遮挡和背面的面片而增加CPU很多计算，那将是不值得的。所以，目前的背面剔除和遮挡剔除算法的使用只适合于地形交叠起伏厉害的场景。 3.7用动态数据加载实现超大地形的绘制
在前面章节中涉及的场景是有限大的，我们实现了2049 X2049高度图的实时绘制。但是当游戏中虚拟世界的地图再扩大很多时，即使我们能对地形面片做很好的简化，对地形区域做很好的剔除，也不能一次把数据全部读入内存进行渲染。所以，对于整个游戏虚拟世界的表现，实际游戏引擎中往往采取地图数据的静态加载和动态加载两种方案。
我们把单个场景(Tile)看作组成整个游戏世界地图的基本单元，那么整个虚拟世界就是所有场景的集合。在物理上，通常把单个场景(Tile)的数据打包在一起。不管采用什么样的数据加载方式，都是以单个场景数据为基本单位的。在本课题中的单个场景数据主要包括高度图、纹理索引图、光照贴图、纹理贴图等。 3.7.1静态加载方案 这是最简单的办法，也是目前常用的方式。所谓静态加载是指在渲染场景前必须等待读入场景数据，读入后人物只能在这个固定的场景里漫游。在场景一定的位置设置下一个场景的开启点，使得人物一旦到达此区域就触发事件，读入下一个场景的数据，经过数据读取后，角色便切换到了这一场景中。如图3.21所示：
这种方法不要求场景间无缝衔接，通常会把单个场景设计得大一些，避免频繁的场景切换等待。对于一般游戏的渲染细节要求，一个1025 X 1025大小的场景已经能表现很开阔的场景了。
这种方法的优点是逻辑简单，系统开销小。但是由于场景的切换等待，存在不能连续漫游超大无缝场景等缺点，极大影响游戏体验。所以现在很多游戏正试图采用其他方案跳出这种限制。
3.7.2动态加载方案实现无缝连接超大场景的实时绘制
.地图数据的动态加载机制
动态加载是指在场景渲染的同时更新内存中要渲染区域的数据。本文通过维护一个区域数据缓冲池，根据角色所处位置，读入磁盘文件系统中的场景数据，使得缓冲池中始终保存有角色周围相关区域的场景数据(肯定不是整个世界的数据)，场景渲染引擎只在缓冲池中挑选要进行渲染的数据。通常单独开一个线程负责维护这个数据缓冲池，主线程负责场景的绘制。整个数据调度过程如下图所示：
渲染主线程对数据加载是透明的，他只负责从缓冲池中挑选数据。这种技术的难点在于根据单位区域的数据量大小、磁盘I／O效率来决定缓冲池的大小。缓冲池太小会引起频繁的I／0读取，影响游戏流畅；缓冲池建得太大，占用内存资源过多，预取的Tile数据也会增加。通过实验得出，如果把每个Tile的高程图大小设为256×256，缓冲池取为25个Tile大小比较合适。如果能有效的利用这种技术，那么角色可以在游戏中自由漫游，理论上游戏场景的大小只受限于磁盘的数据容量。技术的关键在于使CPU、GPU、I／O三者的效率达到一种平衡，在任何一个环节不能出现瓶颈。
.缓冲池的建立与维护
所谓动态加载必须使场景绘制和数据的取得分工协作，异步处理。所以缓冲池必须通过创建单独线程来处理。关于缓冲池具体有以下几个问题需要处理： (1)缓冲池维护线程的创建 对于缓冲池维护线程的生命周期有两种方式。一种是当绘制主线程发出更新缓冲池指令后得以创建，其生命周期在缓冲池维护工作(数据的读取和删除)后结束。第二种是在整个软件初始化时期得到创建，其生命周期一直持续到整个软件运行结束。通过与主线程共享数据区域中的一个缓冲池维护指令标记来决定是否进行I／O操作。 (2)缓冲池维护线程与主线程的协作机制和通讯 出于效率的考虑，在线程间使用异步机制。主线程只在需要重新调整缓冲池的时候向缓冲维护线程发送消息，他在使用缓冲池资源的时候不需要采用锁机制与维护线程互斥。通过为缓冲池中的每一个Tile建一个状态标记，主线程在查找数据的时候先看其对应的标记，如果标记表明可以使用，才让数据进入渲染引擎。反之，则不把这个Tile调入渲染引擎。通过在主线程发出更新缓冲池指令和维护线程从文件系统读完数据之间预留足够的时间，可以保证在最大程度上让主绘制线程取到想要的数据。这么做最大的好处是效率很高，绘制线程不需要任何等待时间。软件初始化时在内存中开辟的一块专用区域，两个线程的数据都在这里得到共享。他们的消息传递也通过改变在这块区域中的一些状态标记来实现。
在缓冲池中的每个Tile数据通过索引指针被绘制线程方便的使用。 (3)何时更新缓冲池，更新哪些 当角色在场景中移动位置超出某个距离限制时，让主线程通知缓冲池维护线程开始按主线程要求的最邻近Tiles索引表来读取新的Tiles文件，在池中删除需要丢弃的Ti les空间(或许覆盖更好)。关于何时更新，如图3.23所示：
图中的每个小格子代表一个Tile，也就是缓冲池维护线程要加载的最小单位。在本程序中每个Tile为256×256大小。当角色在点a位置时，在他周围相邻的Tiles是以TilelO---Iilel4为边长的正方形。一共25个Tiles，他们就是此时缓冲池中拥有的Tiles。角色向b点移动，假设角色现在的坐标是(X'，Y')，比较的基准位置为a点，其坐标为(X，Y)，那么
当X'-X>=Tile.Width
或者Y'-Y>=Ti le.Height 时触发缓冲区更新事件。
同时把基准位置设为b点。通知缓冲池维护线程从池中剔除TilelO-一Tilel8，从文件系统读入Tilel_Tile9。角色走过(X'一X)或者(Y'一Y)这段路程的时间就是预留给池维护线程动态读取数据的时间，在本例中为256个高程图单位，足够了。
值得注意的是，绘制主线程只从缓冲池中挑选最邻近他四周的9个Tile进入渲染引擎。如果在实际应用中我们的硬盘读取时间预留不是很足，读取数据比较频繁的话，可以通过增加进入缓冲区的Tile个数来调节。比如设置进入缓冲区的T儿e为36个。
另外，也可通过设定Tile的优先级来更合理的决定进入和退出缓冲池的Tile。Tile的优先级可以根据角色的运动方向来判定，比如人物向右移动，那右方Tile的优先级显然应该比左方的高。'
3.8本章小结
本章节讨论比较了ROAM、基于四叉树的LOD、GeoMipMap几种基于LOD思想的网格简化算法，提出一种优化的GeoMipMap算法，并讨论了其实现细节。另外，本章介绍了符合室外地形的空间管理算法一一基于四叉树的空间管理。并讨论了在其基础上实现的视锥体裁剪，背面剔除算法和遮挡剔除算法。
此外，针对超大无缝地形的渲染，本文提出通过维护数据缓冲池来实现地图数据动态加载的技术。
