第5章

三维游戏场景的组织和绘制

 

 

 

 

在三维 游戏场景绘制中，往往追求用最少的处理器时间和内存耗费创造出最有视觉冲击力的艺术效果，能否保证实时高质量的画面显示是游戏图形开发成败的关键之一。对 于高度复杂的场景，简单的图形硬件加速并不能满足游戏的实时绘制需要，因而必须设计高效的数据结构和算法来加速复杂场景的漫游。与一般的真实感绘制技术不 同，三维游戏中的图形技术在追求速度的同时可以适当损失图形的绘制质量。基于这一原则，三维游戏中的图形技术大致可以从三个层面考虑：第一个层面考虑场景 的几何组织与优化，它着重于提高绘制效率，建立优化的场景表达模型，包括场景多边形网格模型的优化、场景几何组织和绘制状态优化技术、层次细节技术，以及 在此基础上的快速可见性判断与消隐技术等；第二个层面考虑场景的画面真实度，它的前提是保证绘制速度，可采用一系列特效生成技术，包括高级纹理映射、混合 式几何和图像建模与绘制技术、粒子系统、过程式建模等；第三个层面考虑基于真实物理定律的游戏效果模拟，主要包括阴影模拟和碰撞检测处理。本章将以三维游 戏场景的实时渲染为目标，着重介绍三维游戏场景的几何组织、优化管理以及在此基础上的碰撞检测，其他内容将在第6章中阐述。

5.1  三维场景的组织与管理

在实时 绘制的前提下，控制每帧画面绘制的多边形数目、检查游戏中的物理特性以及管理网络吞吐量等，这就是场景的组织和管理。在第一人称游戏中，游戏角色的视野包 括整个场景，它是一个未知的需要探索的世界，通常包含几百个房间，每个房间内有几十个物体，每个物体由几千个三角形组成，整个场景的三角形数目可达数百 万。如果没有场景优化管理，游戏的实时性根本无法保证。在多人对战游戏中，同样需要场景的组织和管理，场景中物体的运动状态必须实时地广播给其他客户端，如果运动物体过多，会带来网络阻塞。一个明显的优化措施是，对某个客户端而言，可以忽略处理不可见的物体状态。

本节首先介绍游戏场景的一个重要组织和管理方式，即场景图（Scene graph），然后介绍三维场景的绘制状态树管理方式，最后介绍三维场景的包围盒和场景剖分技术，包括BSP树、四叉树、八叉树和均匀八叉树剖分技术等。

5.1.1  基于场景图的表达和管理

场景图是一种将场景中的各种数据以图的形式组织在一起的场景数据管理方式，它是一个树状结构，根节点是整个场景，树中的每个节点可以有任意多的子节点，每个节点存储场景集成的数据结构，包括几何物体、光源、相机、声音、物体包围盒、变换和其他属性。场景图也可以被看做一个有向循环图，基于场景图表示的场景绘制分为两步进行。第一步，根据游戏的需要更新场景图必要的部分。这种更新是局部的，不需要从根节点遍历。如果某个节点的几何变换改变，状态会影响其所有子节点的状态。节点的包围盒的改变则由下向上扩散。第二步，场景图的剔除和绘制过程。对于每个节点，首先剔除不可见的部分，并保存上一节点的绘制状态，待该节点和它的子节点绘制完成后，再恢复上一节点的绘制状态。

现在以 太阳系为例来说明场景图的构造和遍历。设太阳系有一个位于中心的太阳以及两颗围绕它旋转的行星，每个行星又分别拥有两颗围绕它们旋转的卫星。如果不使用场 景图，场景中的每个模型分别被指定一个变换函数。假如要修改其中一个行星的位置，那么不仅要修改这个行星的变换函数，还必须修改围绕它旋转的两个卫星的变 换函数。如果围绕该行星旋转的卫星很多，甚至还有围绕卫星旋转的小卫星，修改将更加复杂。反之，在场景图中，要修改一个行星的位置，只需修改行星节点的属 性，而不更改任何子节点的属性。图5-1描述了太阳系的场景图。

将场景图转换为相应的代码并不复杂。若旋转节点的操作相当于保存当前的世界变换矩阵并乘以一个旋转矩阵，其他几何节点的操作采用简单的绘制方式，则场景图的绘制代码如例程5-1所示。

 

图5-1 太阳系的场景图

例程5-1  太阳系场景图绘制伪代码

绘制太阳

将当前矩阵压入矩阵堆栈

设置第一个旋转矩阵

绘制行星A

将当前矩阵压入矩阵堆栈

设置第二个旋转矩阵

绘制卫星A

绘制卫星B

从矩阵堆栈弹出顶部矩阵

绘制行星B

将当前矩阵压入矩阵堆栈

设置第三个旋转矩阵

绘制卫星C

绘制卫星D

从矩阵堆栈弹出顶部矩阵

从矩阵堆栈弹出顶部矩阵

利用场景图可以方便地创建更加复杂的场景。假如想旋转行星A，并使两个小行星以不同的速度公转，只需将上面的场景图稍加修改。修改后的伪代码如例程5-2所示。

例程5-2  改进后的太阳系场景图绘制伪代码

绘制太阳

将当前矩阵压入矩阵堆栈

应用旋转矩阵

将当前矩阵压入矩阵堆栈

对行星A进行变换

绘制行星A

将当前矩阵压入矩阵堆栈

应用第二个旋转矩阵

绘制卫星A

绘制卫星B

从矩阵堆栈弹出顶部矩阵

从矩阵堆栈弹出顶部矩阵

设置第三个旋转矩阵

绘制行星B

将当前矩阵压入矩阵堆栈

设置第四个旋转矩阵

绘制卫星C

绘制卫星D

从矩阵堆栈弹出顶部矩阵

从矩阵堆栈弹出顶部矩阵

 

接下来定义各种具体的子节点类型。场景图可以包含各种类型的节点，但是每个场景图通常包括以下类别的节点。

1．几何节点

场景几何是场景的最基本的组成要素。几何节点是各类物体的几何表示，它的成员函数主要完成绘制功能。

 

2．变换节点

变换节点包含了场景中模型的图形变换操作，将模型的平移、旋转、缩放等合成为一个变换矩阵保存在节点中。

变换节点首先保存当前的变换矩阵，再将当前的变换矩阵设为节点中存储的变换矩阵，然后调用所有子节点的Update()函数，最后恢复原先的变换矩阵。通过这样的操作模式，该节点的所有子节点都受到它的变换矩阵的影响。

3．开关节点

开关节点是一种通过当前状态对子节点进行选择的节点。假如设计一款赛车游戏，要求能够从视觉上反映车门的损坏程度。为了满足这一要求，首先根据车门的损坏程度建立不同的车门绘制模型。假设建立了无损坏、轻微损坏、较大损坏、严重损坏4种模型，需要在绘制场景时根据车门的实际情况选择其中一种模型进行绘制，这正是开关节点的作用。

5.1.2  基于景物包围体的场景组织

常用的场景物体包围体技术有5类，如图5-3所示。最简单的是包围球，它的定义就是包围物体的最小球体。任意物体的包围球的中心位于物体的重心（即物体的一阶矩），它的直径是物体表面各点之间距离的最大值。由于球的各向同性，包围球最适合圆形物体。对于长宽比例大的物体，包围球结构存在很大的冗余。

AABB（Axis Aligned Bounding Box，轴平行包围盒）结构是平行于坐标轴的包围物体的最小长方体。AABB树是基于AABB结构构建的层次结构二叉树。与其他包围体相比，AABB结构简单，内存开销少，更新快，相互之间的求交也很快捷。但由于包围物体不够松散，会产生较多的节点，导致层次二叉树的节点存在冗余。在实际应用中，出于效率的考虑，通常结合使用包围球和AABB包围体。这是因为基于包围球的简单距离测试可以进行快速的碰撞检测，但它包含的空间远大于它所表示物体的真实体积。因此，往往判断一个物体会出现在屏幕上，但其实该物体的顶点都应该被剔除。另一方面，尽管AABB包围体更逼近物体的外形，但用立方体进行测试却比包围球慢。

 

图5-3  五类典型的包围体类型（二维示例）

OBB（Oriented Bounding Box，有向包围盒）本质上还是一个最贴近物体的长方体，只不过该长方体可以根据物体的一阶矩任意旋转。OBB树结构的构建方式如图5-4所示。OBB比包围球和AABB更加逼近物体，能显著减少包围体的个数。因此，人们通常进行两个回合的碰撞/相交检测，用包围球做第一回合的快速测试，用OBB进行第二回合的测试。第一回合的测试可以剔除大多数不可见或不必裁剪的物体，这样不必进行第二回合测试的几率就会大得多。同时，OBB包围盒测试所得的结果更精确，最终要绘制的物体会更少。这种混合式的包围盒也适用于其他方面，如碰撞检测、物理/力学等。

 

图5-4  OBB树的构造示意图

物体的凸包围体是最广泛的一种有用的包围体类型。凸包 由一组平面定义，这些平面的法线由内指向外。计算凸包所需信息可以是一组三维空间点，计算时将处于凸包内但不在凸包的包围面上的冗余点剔除。构成凸包的面 的平面方程被用来进行遮挡计算，如果空间中的一个点位于凸包的所有边界面的内侧，那么它就位于凸包之内，这样就可以快速检查一个三维点是否在一个凸包之 内。现在已经有一些由一组点来计算凸包的算法，常用的几种包括增量式（incremental）、礼包式（gift-wrapping）、分治式（divide-and-conquer）和快速凸包算法（quick-hull）。

 

5.1.3  优化场景绘制的几何剖分技术

游戏引擎中最常用的场景几何剖分技术包括BSP树、四叉树、八叉树、均匀八叉树等，下面将分别予以介绍。

1．BSP树

BSP（Binary Space Partition，空间二叉剖分）树是游戏引擎中最常用的空间剖分技术，它由Schumacker于1969年首先提出，90年代初期由John Carmack和John Romero最早在第一人称视角游戏Doom中引入。自那以后，几乎所有的第一人称射击类游戏都采用BSP技术。BSP树能应用在深度排序、碰撞检测、绘制、节点裁剪和潜在可见集的计算，极 大地加速了三维场景的漫游。它基于这样一个事实：空间中的任何平面都将整个空间分割成两个半空间，位于该平面某一侧的所有点构成了一个半空间，位于另一侧 的点则定义了另一个半空间，该平面则是将两个半空间剖分开来的分割面。根据这种空间剖分的方法，可以建立起对整个几何场景和场景中各种物体几何的描述。BSP树的根节点就是整个场景，每个节点所代表的区域被平面分成两部分，一部分是平面前面（左侧）区域的子节点，另一部分是平面后面（右侧）区域的子节点。对子节点剖分，一直向下递归直到空间内部没有多边形或者剖分的深度达到指定的数值时才停止。此时，叶节点代表了场景几何分布的凸区域。图5-6（左），显示了二维平面上的BSP树结构剖分。平面P₁将空间分割成两个半空间{A, E, F}和{B, C, D}。平面P₂将空间{A, E, F}分割成两个半空间{A}和{E, F}，继而{E, F}被平面P₃剖分成两个半空间，平面P₄和P₅又分别将{B, C, D}分成独立的子空间。最后形成的二叉树结构如图5-7（右）所示。

 

图5-6  场景的BSP树剖分（左）、BSP树结构示意图（右）

一棵BSP树代表了空间的一个区域，它的子节点对应于空间的剖分方式，叶节点代表某个子区域或单个物体。图5-7显示了两个空的房间。显然，对左边的场景进行深度排序非常简单，而右边的场景则复杂得多。构建BSP树主要有两种方法：一种方法称为基于场景几何的BSP树，它的非叶节点中既包含分割平面，也包含构成场景几何的多边形列表，而叶节点则为空；另一种方法称为基于分割平面的BSP树，它的非叶节点仅包含分割平面，而叶节点包含所有的形成子凸空间边界的多边形。在游戏中，多采用第二种构造方式，下面以它为例子叙述BSP树的构造过程。

 

图5-7  立方体结构的场景平面图（左）、复杂形状的场景平面图（右）

如前所述，BSP树的组成元素是非叶节点、叶节点和场景多边形列表。在基于分割平面的BSP树中，叶节点是多边形的集合（图中的墙），非叶节点是分割平面。图5-8是对图5-7（右）的场景进行一次剖分后形成的BSP树，A代表非叶节点，它将整个房间分为两部分。

 

图5-8  一次剖分后的场景平面图（左）及BSP树（右）

第二次剖分使用平面B将左边非凸的部分剖分成两个凸的部分，因此不需要继续剖分，如图5-9所示。

 

图5-9  两次剖分后的场景平面图（左）及BSP树（右）

绘制三维场景中一个最重要的问题是多边形排序。为了正确地显示场景，需要保证所有物体按照正确的顺序绘制在当前的相机坐标系中。尽管底层图形API的深度缓冲功能可以排除不可见物体，但这还远远不够。例如，当场景中存在透明物体，就无法保证引擎的正确性。BSP树一个很强的应用是剖分多边形，避免歧义情况发生。

尽管BSP树被广泛使用在三维游戏引擎中，但仍然存在一些问题。首先，它不太合适于动态场景。如果动态物体在场景中运动，必须解决动态物体与BSP树实时融合的问题。BSP树的另外一个问题是构造时间长，因此只能以预处理方式进行。此外，BSP需要剖分多边形，从而增加了场景的多边形数目。在选择分割面时，需要考虑分割引起的新多边形数目并选择新增多边形数目最少的隔离面。为了充分利用BSP树的效率，通常可以结合PVS（潜在可见集）或其他类似的可见性预处理技术，减少实时漫游时BSP树遍历的复杂度。

2．四叉树

四 叉树是一个经典的空间剖分方法。可以转换为二维的场景可有效地使用四叉树进行管理。在地形绘制中就经常使用四叉树进行管理，尽管地形的每个点都具有一定的 高度，但是高度远远小于地形的范围，因此从宏观的角度上看，地形可以参数化或者说摊平为一个二维的网格。在四叉树的建立过程中，首先用一个包围四边形逼近 场景，然后以包围四边形做为根节点，迭代地一分为四。如果子节点中包含多个物体，那么继续剖分下去，直到剖分的层次或者子节点中包含的物体个数小于给定的 阈值为止。图5-11显示了一个四叉树的两次剖分过程。

 

图5-11  四叉树剖分示意图

3．八叉树

八叉树是另一种有效的三维数据结构，它的构建时间比BSP树短，且容易使用。八叉树的构造过程比BSP树简单。首先建立场景的长方体包围盒。长方体被均匀剖分为8个小的长方体。判断场景中每个多边形与8个小长方体的内外关系，如果某个多边形与小长方体相交或位于某个小长方体内部，将多边形加入这个小长方体的多边形列表。场景遍历完毕后，检查8个 小长方体包含的多边形数目。对于每个非空的小长方体，作为八叉树的子节点，继续递归剖分下去。如果为空，则设为叶节点，停止剖分。当递归深度达到给定的数 目或每个节点中包含的多边形数目小于某个数值时，剖分停止。在建立节点与多边形关系的过程中，如果一个多边形与两个以上的节点相交，可以将多边形添加到每 个与它相交的节点中，也可以将多边形沿节点之间的边界面剖分，并将分割出的小多边形分归各方。与BSP树方法类似，后一种增加了场景中的多边形数目，前一种则增加了处理的复杂性，即在遍历时必须保证这类多边形只被处理一次。需要注意，场景中所有多边形只保存在八叉树的叶节点中。在某个节点被剖分出8个子节点并将所有多边形添加到子节点的多边形列表后，非叶节点的多边形列表就被删除，只保留节点包含的多边形数目。图5-12为八叉树示意图。

 

图5-12  八叉树剖分示意图

 

5.1.5  景物包围体与场景剖分技术比较

大部分三维游戏使用BSP树结构组织场景中的多边形物体。对于大规模高度场的地形绘制则使用四叉树。由于BSP树的构造时间长，不适合于非常大的场景。而且，如果场景多边形与剖分平面相交，BSP树就要求沿平面分割多边形，增加了场景多边形的数目。而八叉树非常适合于大的三维空间场景，但碰撞检测功能较弱。它们的比较如表5-2所示。

表5-2  二叉树、四叉树、八叉树比较

 

场景包围体与场景剖分技术的比较如表5-3所示，两者的效果示意图如图5-13所示。不难看出，场景包围体技术紧密包围物体，不同物体的包围体可能有重合。场景剖分技术紧密贴合空间，一个物体可能会跨越几个子空间。

表5-3  场景包围体与场景剖分技术比较

5.2  游戏场景的几何优化

图形绘制的很多加速技术，包括视域裁剪、Portal技术、PVS等，都是面向静态场景的处理技术。对于动态变化的场景，大多数基于预处理的场景剖分技术和可见性算法将都失效。因此，在无法减少可见多边形的情况下，可以使用层次细节（Level of Detail，LOD）技术进行加速。

5.2.1  层次细节（LOD）技术

层次细节算法不仅能减少场景多边形数目，即场景复杂度，也可以用来控制场景的帧率。当场景速度低于某个值时，可以采用LOD算法减少细节层次。反之，当帧率很高时，意味着可以使用更高精度的模型。因此可以在速度与效果之间达到平衡。层次细节技术主要包括以下4类。

（1）简单取舍型LOD

简单取舍型LOD即最简单的LOD算法并不减少多边形的数目。简单取舍型LOD算 法计算每个物体投影在屏幕的像素个数，如果小于给定的阈值，不绘制物体。通常，人们采用物体包围盒替代物体决定物体的投影尺寸。这种方法实际上存在两个大 的缺点：一，它没有减少模型的细节，而只是简单地不绘制小的模型，这实际上为模型建立了两个层次，一个层次是原始精度模型，另一个层次是空模型；二，当相 机在场景中运动时，模型的出现和消失会造成跳跃感，从而产生视觉失真。

（2）平滑过渡型LOD

平滑过渡型LOD算法解决了屏幕尺寸LOD算法的第二个缺点。对于不应绘制的物体，算法并不简单地剔除，而是将物体逐渐地淡出视野。具体方法是，设置目标物体的透明度，并逐帧提高透明度值，直到物体消失，其中透明度的渐变快慢与模型在屏幕的投影尺寸有关。如果当前不绘制的模型重新可见，需要将透明度从0变到1，使得物体逐渐淡入视野。实际使用时，平滑过渡型LOD算法需要设置屏幕尺寸的上限和下限。当物体的投影尺寸大于给定的上限，正常绘制物体。当物体的投影尺寸小于给定的下限时，物体的绘制透明度为0（即物体不可见）。如果物体的投影尺寸位于这两个阈值之间，线性插值物体的透明度产生物体的淡入淡出效果。

值得注意的是，对于游戏中的重要角色，采用平滑过渡型LOD算法不是一个最好的选择，这是因为淡出效果将误导玩家认为游戏人物消失。因此，这种方法适用于模拟小的植被、装饰物和家具的细节等。

（3）静态LOD

静态LOD算法真正减少了物体的多边形数目。它的核心思想是预计算同一个物体的多个不同精度的版本，每个版本定义了以屏幕投影尺寸为指导的适用范围。在场景漫游过程中，根据物体的真实投影尺寸选择最合适的版本进行绘制。物体越近，选择的精度越高，反之，物体的几何模型越简单。

游戏场景中，物体的几何表示通常是网格模型，即全部由多边形（或三角形）组成，因此建立物体的层次模型需要对网格模型进行各种层次的简化。大多数三维建模软件都包含网格简化方法，方便用户创建模型的细节层次。因此，静态LOD算法的好坏取决于网格简化算法的优劣。而场景漫游的视觉效果不仅取决于网格模型的精度，还取决于两个相邻层次的网格模型的过渡是否自然。

避免相邻层次的网格模型的跳跃现象有几种方法。最简单的方法是增加雾化效果，通过雾的存在减少视觉上的不连续感。另一个办法是使用透明度融合技术生成两个相邻细节层次之间的光滑过渡，也就是在两个层次的绘制结果之间进行线性插值。

（4）动态LOD

动态LOD算法是最复杂的LOD算 法。它在场景漫游过程中根据相机位置和物体的重要性动态地简化网格。在动态的层次细节模型中，主要有两类：一类是不规则网格，另一类是规则网格。不规则网 格对于同样的地形在相同的误差下需要更少的三角形，但是规则网格构网简单快速，且能很好地读取数据。简化网格的最常用方法是边删除算法。如图5-14所示，为了简化左边模型的填充区域，边E的两个端点V_A和V_B合并为一个点V_C，因此删除了三条边和两个三角形。动态的几何变形LOD算法基本上克服了前面几种方法的帧间不连续的走样现象，但是算法是否成功极大地取决于动态几何变形的算法效率是否成功。

5.2.2  渐进网格和连续多分辨率绘制技术

以几何元素的删除实现模型的简化是层次细节模型自动生成的常用方法。但由于复杂模型庞大的数据量，使得以往的LOD模型生成方法只能预先产生多个间断的简化模型，从而引起实时绘制时图形画面的跳跃。为解决这个问题，人们相继提出了渐进网格模型概念以及三维复杂模型的实时连续的多分辨率绘制技术。

在游戏中常用的光滑过渡方法是渐进网格技术（progressive mesh）。它由Huppe等人于1995年 率先提出，首次较好地解决了模型简化方法在实际应用中所遇到的问题。该算法利用顶点分裂这一与模型简化操作（顶点合并相逆的过程），来恢复模型简化时所删 除的信息。为了得到模型细节的删除信息，算法在模型简化的预计算中需要记录下边简化为新顶点这一简化过程中原顶点与新顶点的对应关系，并由预计算中记录下 的每一简化过程得到一个由原模型的基本网格和一系列的简化信息组成的渐进网格表示模式。在实时绘制时，通过跟踪记录下的边简化为新顶点的对应关系，算法可 以根据这一跟踪线索由基本网格模型逐步恢复所删除的模型细节，实时得到原模型连续精度的简化模型。该算法以边简化所导致的模型几何误差的大小指导模型简化 的顺序，并由此生成几何误差由小到大的渐进网格模型。在Direct3D 9.0中，渐进网格技术可以使用图形硬件加速，这已经是网格模型处理和绘制的一个重要部分。

5.3  三维场景的快速可见性判断与消隐

由 于视线的方向性、视野的局限性以及物体之间相互遮挡的原因，视点所观察到的只是整个场景中的一小部分，决定这些可见，的部分称为可见性判断。所谓消隐，是 指剔除场景中被遮挡的部分，以免产生视觉失真。可见性判断与消隐密不可分，前者的本质也是消隐，但出发点是优化绘制效率，后者蕴含的所有技术都可以服务于 可见性判断。可见性判断在复杂场景的漫游中至关重要，它能减少被绘制的多边形数目，节省了图形硬件和CPU花费在不可见多边形的变换、求交上的处理时间，也减轻了显卡的存储负担。

5.3.1  可见性判断算法分类

可见性判断算法在处理层次上可以分为物体层、顶点层和像素层三大类，如图5-16所示。下面分别予以介绍。

（1）物体层算法

早期的可见性判断主要是指基于视域四棱锥的判定。这一时期的可见性判断主要是利用场景的有效组织加快位于视域体内物体的归属判定。20世纪70年代末发展起来的物体分层次表示是这一时期的典型代表。层次表示的主要方法是前面介绍的场景剖分技术，这类技术的主要特点是将场景组织成为一棵树，充分利用空间连贯性以加速场景的遍历，大大地减少了画面绘制过程的复杂度。其中典型的二叉树（BSP）方法利用已建立起来的二叉树快速决定相对视点面的前后排列，加快判断由于物体相互遮挡所产生的可见面。但该方法由于以面作为划分单元，因而会产生大量新的面片。

 

图5-16  对应图形绘制流水线不同阶段的可见性判断和消隐算法

（2）顶点层算法

最简单的顶点层可见性判断算法是背面剔除。它的基本假设是：多边形的绘制模式是单面绘制，而且场景物体是封闭的。因此，如果多边形的法向背向相机方向，它是不可见的。背面剔除是底层图形API图形流水线的一部分，因此游戏的图形引擎不需要特殊设计。为了加速，可以对物体预先分块，对每个块的所有顶点的法向计算变化范围，形成法向锥，法向锥进而被用于背面剔除的判断。这实际上可以被看做一种物体层的可见性处理算法。

第二种可见性算法是视域剔除。除了图形流水线提供的视域四棱锥外，应用程序还可以自行设定裁剪面，剔除场景中不可见的部分。

注意，这两种可见性判断算法都依赖于图形流水线的硬件处理能力，而且可见性判断需要在顶点变换之后进行，因此仍然无法避免在顶点变换之前对这些被剔除多边形的处理。

第三种可见性算法是裁剪面剔除，它引入额外的裁剪面，剔除不可见的顶点和多边形。

（3）像素层算法

无论场景剖分、包围盒或顶点剔除技术，都是利用物体空间的相关性来加快可见性的判定。传统的深度缓冲（z-buffer） 算法利用屏幕上同一像素的深度信息决定可见面的判断，有效地利用了图像空间的相关性来加快可见性的判定，但深度缓冲算法并没有利用空间的相关性。为此，人 们提出了两类层次结构，即在物体空间建立八叉树层次结构，在图像空间建立深度缓冲的四叉树层次结构的思想，很好地结合了物体空间、图像空间和时空一致性的 连贯性，但算法的实施依赖于对深度缓冲存储器的访问，因而无法使用图形硬件进行加速。

5.3.3  遮挡面剔除技术

早期的游戏直接用包含三角形列表表示场景，尽管大部分三角形对当前画面没有贡献，但每帧绘制时必须全部处理它们。考虑到游戏角色只能位于某个房间中，如果房门是关闭的，游戏角色可见的三角形全部位于当前的房间中，只占到全部三角形数目的1%。一个自然的想法是剔除那些明显不可见的99%的三角形。因此，除了场景组织外，还需要考虑遮挡面剔除的问题，剔除遮挡面的要点是不绘制当前视点不可见的场景。通常的三维游戏场景深度复杂度非常高，深度复杂度是指屏幕上的像素被场景几何覆盖的次数。为了减少场景深度复杂度，必须使用遮挡面剔除技术。物体A完全位于物体B的后面，称A被B遮挡，不需要被绘制。对于室内场景，入口技术是最佳选择方案，而遮挡面剔除则非常适用于人造建筑少的室外场景。

遮挡面剔除不同于视域裁剪和背面裁剪，它需要利用全局知识，即需要考虑同一场景中的其他绘制元素（组）和当前绘制元素（组）之间的关系。所以，相对于前两者，它更加复杂，但在深度复杂的场景中，它可为提高绘制效率提供更多的收益。所谓深度复杂度，指的是当用标准的z-buffer算法来绘制场景时，在像素上所进行的深度测试的平均次数。

在 选择好候选遮挡体后，可以在场景随机选择一些视点，测试这些遮挡体的效率，效率的衡量是它实际遮挡的多边形个数。在决定了遮挡体后，逐个生成遮挡体的阴影 体，从而剔除阴影内的多边形。如果场景中存在多个遮挡体，可以根据重要性对它们进行排序。重要性的度量主要是遮挡体在屏幕上的投影尺寸以及它到视点的距 离。法向背离视点的遮挡体应当作为背面剔除，不予考虑。此外，可以采用八叉树加速场景多边形与阴影体的相交测试。

检测长方体包围盒是否在遮挡体之内的一个简单方法是，检测世界坐标系下包围盒的8个角点是否都在遮挡体内。因此，需将局部坐标的AABB结构转换为世界坐标的OBB结构。只要有一个顶点位于遮挡包围体之外，包围盒就没有被完全遮挡。这种检测比包围球检测要多做8次乘积操作，因而效率稍低。在理想情况下，仅仅当包围球中心在遮挡体内，而包围球却没有被完全遮挡时才会用到包围盒检测。将包围球与包围盒结合使用的检测方法减少了包围盒与遮挡体之间碰撞测试的时间浪费的几率，又能获得较为精确的结果，造成最后绘制的物体更少。

5.3.4  潜在可见集（PVS）方法

在入口技术中，若场景中有n个单元，可以对每个单元设置一个n位组成的标志位。如果第i个单元相对于当前的单元是可见的，那么第i位设置为1。这种潜在可见单元方法在游戏Quake和QuakeII中都被使用。当然，算法只是一种保守的估计，某个单元可见的单元数目肯定大于某个特定视点可见的单元数目。它的一个推广版本就是潜在可见集算法（Potential Visible Set，PVS）。

PVS算法本质上是一种预处理技术，与遮挡面剔除技术在加速绘制的原理上相同，都是通过减少当前绘制所需要考虑的景物的数目来提高实时绘制的速度，但在具体的技术路线上有所不同：遮挡面剔除技术预先剔除那些肯定不可见的面或者景物，而PVS方法预先提取出那些潜在的可见面。PVS技术一般与视点区域结合，通过一个预处理过程将可能可见集（或其他的可见性表示）和视点区域联系起来。大多数PVS方法从景物空间着手，考虑由视点区域对遮挡物所形成的视线投射的本影，再根据其他物体和该本影区域的关系来求得潜在的可见集。不同的算法往往采用不同的遮挡物表示和不同的求取本影的方法。在室外场景中，为了减少PVS的存储量，往往需要预设视点的路径或区域，并只在视点的可能范围之内计算PVS，并通过一些约简的方法压缩PVS数据量。

5.4  地形场景的绘制与漫游

地形绘制是室外三维游戏中必须面对的问题。地形上的凹凸不平，如山峰和低谷可以用高度图（heightmap）表示，高度图本质上是一个灰度图像，每个像素用8位表示，记录了地形上对应点的相对于海拔的高度，高度值被保存时会由浮点数变换到0～255之间，而在使用时重新变换到浮点数。图5-21（a）显示了一个基本的地形网格，图（b）显示了一个高度图，图（c）显示了应用高度图后的地形网格，图（d） 则是地形网格的实际绘制结果。高度图除了可以采用真实的航拍或测量数据外，也可以使用随机过程式的方法生成，还可以在任意一个图像编辑软件中创造。基于图 像编辑软件的方法能够提供交互的视觉指导，而且能使用滤波算子、预设工具等获得特殊效果，因此在游戏编程中最为常用。高度图通常保存为.raw格式，它简单地将8位灰度按照先“x”再“y”的顺序记录下来，不需任何头文件。

          

（a）地形的基础三角网格                              （b）高度图

            

（c）应用高度图后的地形网格                         （d）渲染后的地形图

图5-21  地形绘制

基于四叉树的静态地形结构是利用图形硬件加速地形绘制的一种方法。由于地形的高度相比于地形的范围非常小，因此地形数据（高度图）容易参数化，从而仅需要将高度图投影（摊平）为一个大的二维纹理，地形数据进而被剖分为四叉树结构。需要注意，地形图的尺寸一般是2ⁿ，如256²、512²或1024²。 因此创建地形图的四叉树不需要额外的内存消耗。四叉树的绘制非常简单，仅需用三角形表示每个遍历的节点，然后绘制地形纹理。由于四叉树具有一定的规则性， 可以预先计算四叉树几何，转换为三角形条带、三角形索引列表或者三角形扇形表示，这样既减少内存，又减少处理的顶点数目。

为了优化地形绘制，可以采取一系列措施。第一个措施是使用场景的层次剖分技术进行视域剔除。在遍历时，根据当前视点所在的区域计算出不可见的四叉树节点，并不处理不可见节点和它的子节点。判断子节点是否可见的方法是对节点建立一个AABB包围盒，然后将AABB包围盒与视域四棱锥进行测试。AABB包围盒在预处理阶段获得，其中AABB包 围盒的上底面和下底面由节点的高度图的最低和最高值决定。第二个优化措施是消除对画面贡献极小的多边形。也就是说，可以根据多边形距离画面的远近，调整四 叉树的绘制层次。考虑当前节点的包围盒在屏幕的投影尺寸，如果它小于一定阈值，直接用当前子节点绘制。在决定四叉树的遍历层次时，需要定义地形的误差度 量。简单地说，误差度量是采用当前节点绘制时产生的地形误差。当某个节点的误差度量大于某一阈值时，节点必须继续剖分。这种与误差度量相关的地形绘制方 式，称为自适应四叉树层次剖分。它的含义是在地形平坦的区域，四叉树结构可以适当简化，反之，必须生成足够层次的四叉树结构。一个自适应剖分的四叉树实例如图5-22（a）所示。

 

 

图5-22  自适应网格简化示意及简化

大规模连续层次的地形细节绘制时，另一个改进方法是几何变形（geomorphing）法。动态层次细节算法预先计算几何细节，并在绘制时根据误差度量选择细节层次。而几何变形法则在不同的层次之间进行变形，形成光滑过渡的视觉效果，从而避免了在不同层次之间的切换时带来的跳跃感。

5.5  三维游戏场景中的碰撞检测

常 用的碰撞检测方法大体可分为两类：一类是基于物体空间的碰撞检测算法；另一类是基于图像空间的碰撞检测算法。它们的主要区别在于，是利用场景物体的三维几 何进行求交计算，还是利用场景物体在屏幕上的二维投影和深度信息来进行相交分析。在游戏引擎中，通常可结合这两类方法以获得最高的效率。本节首先介绍碰撞 检测算法的通用思路，然后重点介绍三类有代表性的碰撞检测算法，它们是经典的游戏引擎中最实用的算法。

5.5.1  碰撞检测的基本原理

碰撞检测的最直观的想法是对所有物体做两两求交判断，假设场景中有N个物体，则算法复杂度是O(N²)。 在处理复杂的游戏场景时，一个基本的策略是快速排除明显不发生碰撞的物体，确定潜在的相交区域或相交物体对，尽可能减少进行精确求交的物体对或基本几何元 素的个数。从这个策略出发，通常有两个思路。一是着眼于场景中物体之间的位置关系，快速排除明显不相交的物体对。在获得潜在可能相交的物体之后，可层次遍 历物体对的预先构建的层次包围体树，递归检测各层节点包围体之间的相交情况，直到各个层次树的叶子节点，最终获取物体对的相交检测结果。二是以场景所在的 空间为载体，通过对场景的规则剖分，加速确定可能存在物体相交的区域。随后把潜在相交区域的子空间继续剖分下去，直到找到最精细的空间层次，并取出相应的 相交物体的多边形面片。在此基础上，进行精确的相交测试，获得碰撞区域的详细信息。

对 空间进行剖分的优点和方法在前面已经做了详细描述。物体的层次包围体树本质上是一种层次细节的表示方法，但不等同于在快速绘制复杂物体或地形场景时采用的 多边形层次细节。后者使用层次细节技术的目的是为了在满足实时性的前提下，尽可能保证绘制结果与初始模型的结果近似。而在碰撞检测中，构建层次包围体树的 原则是尽量保守地逼近原物体模型，且保证包围体之间的相交检测速度。由于选择的包围体类型较物体本身远远简单和规则，彼此之间的相交测试极为简单，因而层 次包围体树能作为预处理手段，快速递归，排除不交情况。

在碰撞检测算法中，最终精确的求交计算与物体的具体几何表示方法有关，包括多边形模型表示、CSG树表示、参数曲面表示和体素模型表示。游戏场景中最常用的是多边形面片表示，且基于多边形表示的碰撞检测算法大多转化为三角形之间的相交检测。下面详细介绍基于多边形表示的碰撞检测算法。

5.5.2  基于空间剖分结构的碰撞检测算法

场景的层次剖分方法主要有均匀剖分、BSP树、k-DOP树和八叉树（Octree）等。基于空间剖分技术的碰撞检测算法的难点在于处理不同的场景和具有不同形状及复杂度的物体时如何保持一致的检测效率。

5.5.3  层次包围体树法

场景物体的层次包围体树可以根据其采用的包围体类型的不同来加以区分，主要包括层次包围球树、AABB层次树、OBB层次树、k-dop层次树、QuOSPO（Quantized Orientation Slabs with Primary Orientations）层次树、凸块层次树以及混合层次包围体树等。它们的构造详见5.1.3节。下面简单比较每一类包围体的一个代表性碰撞检测算法，并比较彼此的优缺点。

包 围球的定义是包围物体的最小球体。最简单的基于包围球的碰撞检测算法可分为三个阶段：先通过全局包围球快速确定处于同一局部区域中的物体；再依据一个基于 八叉树的层次包围球结构来进一步判断可能的相交区域；最后检测层次包围球树叶子节点中不同物体面片的相交情况。包围球结构是最简单的包围体类型，尽管基于 层次包围球的碰撞检测算法简单，但包围物体不够紧密，建构物体层次树时会产生较多的节点，导致大量冗余的包围体之间的求交计算，处理大规模场景较为困难。

AABB结构是平行于坐标轴的包围物体的最小长方体。AABB树是基于AABB结构构建的层次结构二叉树。与其他包围体相比，AABB结构比较简单，内存消耗少，更新快，相互之间的求交也很快捷，但由于在包围物体时空间上不够紧凑，会产生较多的节点，导致层次二叉树的节点存在冗余，有时会增加许多不必要的检测，反而影响算法效率。

 

5.5.4  基于图像空间的碰撞检测算法

基 于图像空间的碰撞检测算法采用物体的二维屏幕投影和相应的深度信息来判别两物体之间的相交情况，并利用图形硬件进行加速。最古老的基于图像空间的碰撞检测 算法利用深度缓存和模板缓存来辅助场景物体之间的相交检测，对物体可能相交的区域设置一系列裁剪平面，然后移动图形硬件的裁剪平面，逐个判断该平面上的每 个像素是否同时被检测物体覆盖，以确定物体是否相交。

另 外一个经典的算法是将深度缓存和模板缓存结合在一起进行相交检测。它采用模板缓存值来保存视窗口中，每个像素上所代表的射线在进入一物体前，进入和离开其 他物体的次数，并读取模板缓存中的值来判断两物体是否相交。该算法仅能处理两个凸体之间碰撞检测问题。基于图像的碰撞检测算法的实现比较简单，可以有效利 用图形硬件的高性能计算能力，缓解CPU的计算负 荷，在整体上提高碰撞检测算法效率。随着图形硬件的发展，基于图像空间的碰撞检测算法受到越来越多的关注，但是由于图形硬件绘制图像时本身固有的离散性以 及有限的精度和显存，不可避免会存在数值误差，从而无法保证检测结果的准确性。而且，目前多数基于图像的碰撞检测算法仍然只能处理凸体之间的碰撞检测。此 外，由于使用图形硬件辅助计算，基于图像的碰撞检测还需要考虑如何合理地平衡CPU和图形硬件的计算负荷。

5.6  小结

本章主 要介绍了复杂三维游戏场景中的引擎构成和几何优化处理技术。在早期的游戏中，场景图和二叉树结构是最为重要的技术。随着游戏场景复杂度的逐步增加，一些新 的技术被加入到游戏图形引擎的开发中，如多人协同、并行处理、网络处理等。在大型网络游戏的实时漫游中，需要考虑的方面更多，如负载平衡、绘制同步、网格 模型的实时压缩与解压缩、几何和图像数据的渐进传输等，因而需要在本章所介绍的技术基础上，不断地学习和提炼新的优化技巧。有兴趣的读者可以自行下载一些 开源的场景图API和小型游戏引擎，从框架上总体理解游戏场景的几何优化方法的实效。

 

习  题  5

1. 熟悉OGRE中的四种场景组织方式，体会各种方式的异同点。

2. 在OGRE基础上实现一个简单的状态管理树，要求能处理至少20个物体和20种不同状态组合的状态切换。

3. 手工创造单个几何物体的三个细节层次模型，以OGRE为基础实现平滑过渡型LOD。

4. 在OGRE基础上实现一个包含三个房间的室内场景的Portal技术。

5. 熟悉OGRE中的地形绘制程序，编程实现地形四叉树，并比较采用四叉树带来的效率优化。

 

参 考 文 献

[1]  Daniel Sánchez-Crespo Dalmau, Core Techniques and Algorithms in Game Programming, New Riders Publishing, Sep.2003

[2]  Peter Walsh. Advanced 3D Game Programming with DirectX 9.0, Wordware Publishing, 2003

[3]  Tomas Akenine-Möller and Eric Haines. Real-time rendering. A.K. Peters Ltd., 2nd edition, 2003

[4]  DirectX 9.0 SDK. Microsoft Cooperation, 2003.

[5]  http://www.ati.com

[6]  http://www.nvidia.com

[7]  http://www.gameres.com

[8]  http://www.gamedev.net

[9]  http://www.gamasutra.com

[10]  http://www.flipcode.com

[11]  刘学慧. 虚拟现实中三维复杂几何形体的层次细节模型的研究.   , 2000

[12]  华炜. 大规模场景实时绘制技术. 浙江大学博士论文，2002

[13]  范昭炜. 实时碰撞检测技术研究. 浙江大学博士论文，2003