阅读: 15 评论: 0 作者: Maxice 发表于 2010-02-24 10:45 原文链接
摘要：
制作一个3-D游戏引擎并不是一件很简单的任务，因为现在的游戏玩家常常要求在游戏中有着高性能和高质量的输出。在这篇文章中，我们向大家展示了多种实时渲染的算法如何用来在一个实际的3-D游戏引擎中提高性能。我们探究了一个通用的3-D游戏引擎的结构并且讨论了在3-D游戏引擎中的视景图像的任务。我们将从软件工程的角度来研究视景图像，我们将向你展示一种面向对象的和可以方便的通过不同渲染引擎来设计的视景图像。接下来，我们解释了在我们的3-D游戏引擎中用来提高引擎性能的算法。我们在视景图像和物体几何层面上对我们的3-D游戏引擎进行了优化。我们提出的算法在静态和动态的场景中表现的都是相当的好。最后，我们用多处理器在视景图像方面用并行处理的方式来建立个3-D游戏引擎方面作了一下简单的展望。
一、介绍：
在过去的十年里面，计算机游戏行业经历了巨大的增长的黄金时期。在过去的几年里，随着3-D加速硬件设备的飞快的进步，游戏制造行业都将焦点集中在用创新的思想来生产交互式的3-D游戏。3-D游戏引擎是驱动这些游戏的核心技术。简单的来讲，一个3-D擎获得游戏中的3-D物体的几何数据并将这些数据展示在显示设备上，典型的显示设备就是显示器。这个过程就是我们通常所知的渲染。3-D物体的几何数据通常通过一系列的顶点来定义，物体的具体特性（象漫射的颜色，镜面反射以及发射出的颜色等），纹理图，纹理匹配以及一些常用的向量。所有的这些数据在3-D游戏引擎处理途径中经历不同的阶段来决定着这些3-D 物体的最终显示的效果。
图1 一个完整的3-D引擎的处理过程。高层的视景图像给用户一种直觉的方式来模拟一个场景，优化的场景保证了场景对于渲染的高效率。
高层视景图像规定了在游戏中的物体之间的关系，它对于游戏开发者来讲也是在游戏中操纵这些物体的一个应用程序接口（API）。在一个场景被渲染之前，视景图像必须为了渲染而被优化。这种优化处理就是典型的将高层视景图像转变成（编译成）优化的视景图像，这种被优化的视景图像就是用了一种非常适用于渲染的数据结构。这就要求开发者去详细的确定每个物体的“线索”：比如这个物体是静止的还是移动的，物体的结构是否随着时间的变化而变化等等。视景物体剔除就是将观察者不能看到的物体丢弃掉的处理过程，尽管细节层次控制可以将相对于观察着者比较远的一些无关紧要的物体给删除掉。所有这些思想的背后就是减少渲染那些你看不见的东西以及减少远端物体几何数据，为了是将送往最终渲染管线的数据减到最少，这些将会明显的提高渲染性能。这些就是一个3-D游戏引擎为了提高它的性能而所要完成的主要任务。
后续的任务，诸如灯光，视角转换，裁减，投影变换以及光栅化，都是渲染引擎为了完成渲染流程所需要承担的任务。渲染引擎，就是经常提及的立即模式渲染引擎，往往都可以被3-D加速硬件支持。两种主要的适用于PC机的渲染引擎就是微软的Direct3D和Silicon Graphics 公司的 OpenGL。在这种渲染引擎上开发游戏往往是枯燥和耗费时间的，这些引擎所给的程序接口都是些程序性的和面向硬件的。在接下来的部分，我们将在集中在建立3-D游戏引擎的三个主要的模块：（1）为我们的3-D引擎建立高层场景图像；（2）为了建立优化的场景图像的算法；（3）如何丢弃不在观察者视野范围内的物体，并且适当的控制细节层次控制物体。
2.在3-D引擎中的设计问题
视景图像设计由于它直接牵扯到整个3-D引擎的性能所以显得非常重要。它定义了一种让程序员来模拟视景的方式。一个好的视景图像设计应该允许程序员将更多的视景（诸如物体和它们的排列）包含在视景中，并且想到用最好的方式来展现它们，并且可以忽略掉渲染管线的复杂的控制。程序员将通过视景图像的API来设计3-D引擎。
视景图像设计
在视景图像设计中的第一个问题就是要考虑物体的表现。就像我们上面提到的一样，象Direct3D和OpenGl这样的立即模式的渲染引擎均倾向于拥有自己的面向图形硬件的渲染程序功能函数。很显然，这种面向渲染的设计并不适合于完成我们的视景图像的设计的目标。一个面向对象的视景图像设计明显的是一种比较好的程序模式，在这种模式中允许程序员在视景中用对象的概念来设计3-D游戏。我们将所有的游戏对象都当作视景中的3-D对象来对待。Strauss和 Carey已经介绍了完全面向对象的视景图像框架。这个框架的基本的思想就是将3-D视景描述为物体的图像，这种图像成为节点。有很多种类型的节点并且每一个节点都有不同的相关属性。比如说，圆柱形状的节点包含两个参数：半径和高度，但是球状物体仅仅包含一个参数，那就是半径。有一些特定的节点可以包含属于它们的子节点的一些参数。例如，在图2中，描绘了一个汽车的一部分的视景图像。节点组命名为“Body”，它拥有4个子节点来组成汽车的车身。纹理节点包含了定义汽车车身纹理图像的参数。这些参数同样会被命名为“门”的一组节点继承，这些节点用来组成汽车车身的车门。因此，汽车车门将会拥有和车身一样的纹理。通过应用这种方式，我们不仅可以增加资源的可重复利用度，而且也是简单的模拟场景的方式，尤其当我们处理一些视景物体的相对位置时，这种方式显得更有效。变换节点用来描述在父节点下的对象的位置和方向的变换。这些都是相对于父节点的变换。为了得到这些节点的绝对变换（相对于整个场景的变换），当前的这些节点将和它们的父节点的变换相结合（通过矩阵相乘）起来。这样就可以很轻松和简单的一个对象相对与父节点的位置和方向了。这种模型就是通常我们所说的等级场景模型并且是骨骼动画的基础，这种模型通常用来在游戏中的动画的运动部分。
2.2 可移植的视景图形
为了保证我们的游戏能满足尽可能多的玩家的要求，我们必须保证我们的3-D游戏引擎可以在不同的平台和不同的操作系统上运行。因此可移植性是我们设计视景图形的另外一个问题。一个视景图形必须能够在各种目标平台上运行渲染引擎，而且游戏的代码还不能做任何的改动。一个可移植的视景图形必须设计成为不依赖于特殊的渲染引擎才能运行。D鰈lner and Hinrichs 已经讨论了一些实用的方法来归纳不同渲染引擎的特性，并且提议一种可以支持这些系统的通用的视景图形结构。他们确信通过应用一种通用的视景图形，大多数的实时渲染设备都能被整合为单一的不会被凌驾于或是受到一些特殊的渲染引擎的视景图形表示方法。可移植性通过分离的渲染对象和渲染引擎来共同完成。图3就是一个用来证明这种观点简化了的原始的视景图形结构。和前面我们讨论的 Strauss and Carey的工作相类似，一个渲染对象就是在视景图形中的一个节点。多个渲染对象在视景中组织起来就形成了一个完整的视景。D鰈 lner and Hinrichs 将渲染对象扩展到包括不被任何渲染函数支持的2-D和3-D几何对象，除了它们的几何描述；属性包括外观属性（颜色，材质，纹理），变换属性（方向和位置），以及光照属性（不同的光源），这些都是要渲染的细节。在渲染的过程中，渲染引擎将会研究和解释视景图形的内容，计算每个被渲染对象的属性并且将它们转换为与目标渲染引擎相匹配的算法。因此，渲染引擎是唯一的能包含细化一个可移植渲染系统的代码的地方，这些渲染引擎的特殊的算法在整个执行过程中被称为句柄，即每个属性的特例。在渲染的时候渲染引擎将会调用这些句柄的方法。特殊的渲染引擎可以提供优化的引擎执行方法用来扩展底层渲染引擎的特殊的功能函数。在一张大的图片、一些视景图形被描述为可以满足特定规范的参数化的视景。一个视景结构紧紧能为给定的渲染引擎而计算。它的内容可以被不同的渲染引擎解释为不同的目的。
3.在3-D引擎中的优化技术
在这一章中的优化专门的是指用来加速我们3-D引擎的渲染速度的加速技术。优化技术获得视景图形中的对象，并且构建一种特别有利于渲染的数据结构来存储物体的几何数据。这个过程就是通常所说的视景图形编辑。一个完整的优化视景图形应该能够提供对于感光输出结果。Sudarsky and Gotsman 定义了一个在每一祯的运行时间为O(n+f (N))的条件下的感光输出算法，在这里N是在场景里所有对象，n是所有的可见物体，而且f(N)远远小于N。举个简单的例子， 也就是说一个光敏感输出算法的运行时间和可见物体的数量成线性正比关系，而不是和场景中的所有物体成正比。目前共有两种技术能达到这个目的。在物体的几何层次，细节层次控制试图在越远的物体上渲染的越少的数据（也就是物体包含越少的数据）。然而，越靠近观察者的物体越会清晰的呈现它们的完整特性，反之越远的物体看起来越粗糙因为很多精细的细节数据被移除掉了。在场景结构层次，可见性删除技术可以避免渲染观察着看不见的部分。这些物体在渲染之前就被丢弃掉了以便于不把这些数据送到渲染硬件中去。可见性删除技术可以更深层次的分成背面剔除法，视锥体剔除法和遮挡剔除法。简单的讲，背面剔除法就是将背对于观察者的物体的表面被丢弃；视锥体剔除法就是将观察者视角外的物体忽略掉；遮挡剔除法就是试图将从观察者视线内的被其他物体完全遮挡的物体丢弃掉（如图4）。
图4（a）视锥体剔除法将观察者视线外的物体丢弃掉。
(b)遮挡剔除法将被其他物体挡住的物体丢弃掉。
3.1场景结构优化
为了实现在可见性剔除算法的光敏感输出，它们不能简单的重复计算整个场景中的物体并且决定哪一个是可见的。我们应用一种特定的数据结构来将场景中的物体分组，这样的话，用一个简单的查询，算法就可以一下子决定是接受还是丢弃一组物体。我们还可以建议使用分等级的数据结构来根据物体的位置来将场景中的物体归成几个区域。通过这种方式，如果一个特定的区域被发现是相对于观察者来讲是不可见的或是隐藏的那么大部分的物体将不会被渲染。为了得到这些分级的数据结构场景必须要被预处理。假设这个预处理是非常耗费时间的，那么它必须在初始化阶段被完成。
我们应用混合式八叉树作为空间数据结构来存储3-D引擎中的物体。我们选择八叉树的主要原因是基于我们回顾其他的优化技术，我们优化的场景结构的可适应性可以扩展到不同的算法。八叉树模型用一个立方体顺着三个纬度来一次性的划分空间物体。在每一个阶段，用八个相等的立方体沿着三个轴面上均匀的划分整个场景（xz,xy和yz面）。图5证明在2维视角上验证了这个过程。
图5 一个二维版本的八叉树的四方块的构建。每个面上再递归的划分为四个相等的小的相等的四方块，直到里面的物体为空或是一整个物体。
这样就可以创建一个每个节点都包含有八个字节点的树。通过划分每个物体都会和它所嵌套子节点的的相应的立方体相关联。如果一个物体恰好被一个面所划分（图5 的c）,那么这个物体就可以用几种方法来处理。一种方法就是根据与划分面的关系来划分物体，根据物体在他的子节点的所关联的立方体的空间尺度来关联部分物体。分裂算法有点复杂并且这种方法同时也会增加场景中物体的数量。另外一种方法就是将原始的物体既可以与它的父节点相关联也可以与它的装入的子节点相关联。当立方体为空时，或是一整个物体都包含在立方体时就停止向下划分（图5的d）。当算法结束时，实际的物体都会包含在八叉树的叶节点内，每个叶节点会包含少于或是等于指定的物体的数量。
3.2物体的可见性剔除
视锥体剔除法是通过执行观察者视角与装入最大立方体的一系列物体的交集测试来运行的，如果测试失败则将这些物体在最初的阶段裁减掉，否则进行与最小的立方体进行一次最终的测试。八叉树不仅可以很好的应用在静态的场景，同时它也可以方便的应用于动态的场景中。遮挡剔除法算法可以紧接着应用于丢弃掉其他的一大部分不在观察者视线内的物体，尤其对于场景内物体密度比较大的情况更加有效。张提出了一种比较新颖的应用分级的空间图形遮挡地图的遮挡剔除算法。这个算法有两部分测试组成：一个在Z轴方向上的一维度深度测试和两维度的空间图形的交迭测试来共同决定一个物体是否被遮挡住。
对于两维度的交迭测试，一个遮挡表示就是被渲染一系列潜在的很好的遮光板而构建的，这个遮挡在场景结构完成时就被确定了。张还建议一些大的或比较靠近观察者的物体当作比较好的遮光板。这些遮光板被渲染成没有纹理，灯光和开启Z-buffering的一块在黑背景下的一块白颜色的脱离屏幕的图形缓冲。这些操作允许将一些列小的遮光板拼成一块大的遮光板。这个被渲染过的图像就是最高分辨率的遮挡地图，这个方案是基于分级的遮挡地图的。这个层级是通过从最高分辨率向下到最小分辨率一层层递归取样形成的，象图6所示。图形硬件可以用缩小倍率的过滤的双线性插补的纹理映射来加速这个过程。
图6 a 接近建立一个遮挡图的遮光板
（b）在不同级别的分层次的遮挡图
交集测试是通过测试物体是否投影在屏幕空间的范围内，这一点和分层次的遮挡图形的同尺寸的像素对应于相同尺度的边框内的尺寸是不一样的。如果边框内所有的元素与映射的交集为不透明（全白），那么这个算法就认为这个物体是被遮挡的。然而，这个算法会递归的检查比它低一层次的不透明的像素。这个算法独特的一点是比较接近可见性剔除，也就是忽略掉对那些仅通过小洞或是透过遮光物体才能见到的物体的渲染。对于这点，在遮挡映射里像素并不完全等同于全部透明，而是相对于一个透明的阈值（灰度）。这个值越小那么这个算法就越接近于剔除，场景内物体会由于被忽略渲染而导致部分可见。张已经得出了一个计算在层次中的不同等级的阈值的公式。这个特征就好像是增加剔除率，当场景不需要物体被看见事可以通过一些遮挡物的一些小的和一些不是特别清醒的图来代替这个物体。
一维度的Z-depth 是用来检查一个物体是否在遮挡物体的后面。张提议用深度估计缓冲来将屏幕分成一系列的小的矩形区域。对于每个区域，所有的遮挡物体的视线内的最远的顶点的z-value被加入缓冲。深度估计缓冲在每一帧祯都需要建立。在渲染是，如果一个物体的所占的体积的最近的顶点的Z-value要比这个物体所能覆盖的区域的所存储的Z-value都大的话，这个物体才会通过深度测试。为了使一个物体被遮挡，这个物体必须同时能通过用分级的遮挡映射的交集测试和用深度估计缓冲的深度测试才行。
3.3动态物体的优化
为了处理八叉树内的动态物体，最直接的方法就是每次当物体运动是，就在八叉树内把它删除掉，接下来通过插入它的新位置。这并不是最佳的处理方法，因为这样会使我们陷入到频繁修改八叉树的结构。举个例子来说，删除八叉树的节点有时会合并刚刚分开的节点，就像图7所示。另外，它还经常需要一个很长的路径来寻找物体的相对于根节点的插入的新节点。为了避免因为删除和建立节点而频繁更新八叉树，Sudarsky建议仅更新那些具有最少共同祖先的子树的物体的新老位置。（图8）对于一个八叉树很深的大场景，这种方法会很明显的减少更新八叉树的时间，因为LCA要比根节点更加接近叶节点。
为了避免对每个动态物体的每一帧都要更新八叉树的结构，Sudarsky用了一个懒惰计算技术，即我们在一个物体是绝对需要的之前不计算任何事情。这就需要一个与每个动态物体相关联的临时的边界体（TBV）。这个TBV是一个保证在某些特定时间内能包含一个动态物体的边界体。这段时间就是指TBV的有效时间，失效其就是这个时间的最后时刻。现在比较流行的TBV的构建方法往往基于一些物体运动和行为的前期知识。举个例子，sweep曲面可以用作TBV的物体上的边界；如果最大的速度和加速度已知的话，球形也是可以用的。应用这种技术，动态物体的TBV可以用在上述视锥体剔除法的交集测试中。在下列情况下一个运动的物体可以被认为是个隐藏的或是不可见的：(1)它的TBV是可见的，也就意味着物体本身可能是可见的；(2)它的TBV过期了,意味着这个TBV不再保证包含一个物体了。一个优先队列用来存储所有的TBV的过期的数据。为了得到更适宜的性能，我们所关心的有效期必须被关闭。一个适当的算法在大多数环境下都能很好的应对这种情况。如果一个物体在确实被看见之前它的TBV就过期了，也就意味着它的有效期太短并且在下一个TBV中将赋予它更长的有效期。相比之下，如果一个 TBV在它过期之前就被看见了，那么在下一个TBV中将赋予它更短的有效期。
图8）当动态物体被更新是八叉树的节点经常被删掉和建立。
（a）最初有两个物体的八叉树
(b)一个动态物体从八叉树内被删除
(c)动态物体又被重新插入到新的位置
3.4物体的几何优化
场景物体的几何数据可以通过试图产生代表从不同观察者的距离的物体的不同层次细节（LOD）进一步的优化。这种情况的背后的原因是我们不需要展现所有的完整的物体的数据因为物体距离我们比较远并且在图形上看起来很小。我们只需要展现那些距离观察者比较近的物体的完整数据，这些物体的精细的数据都可以被展现出来。这样就可以明显的减少物体的数据，因为我们只需要发送那些最需要物体到渲染引擎里去。图9证明了一个Stanford兔子在LOD控制下在两个相对于观察者不同的距离下的显示情况。
图9（a）最高细节的原始的兔子模型（35947个顶点，69451个三角形）
（b）相对于观察者比较远的距离情况下同样的减少了LOD的兔子模型
(c)一个扩大（b）的版本，展示给我们一个粗糟的兔子模型（359个顶点，508个三角形）
通过简化物体的LOD控制是一种为了提高我们3-D引擎性能的必须的技术。LOD两个比较出名的简化技术是分数倍采样和聚类方法。分数被采样是在分类的基础上减少顶点、边或是三角形。那些对于整个显示贡献比较少的顶点将被标注为候选顶点。当一个最不重要的顶点被刈除后，剩下的漏洞将被补上。这个过程一直到达到预期的目的后才会结束。在聚类方法中，一组高权重的顶点将被预决定了。靠近这些顶点的周围的一些顶点将被聚类。只有那些权重高的顶点被送到渲染引擎中去，这些顶点都关联着网格的形成。这种方法非常快但是这种简化的方法的质量比较差。
简化算法的保真度可以通过在简化过程中瞄准那些小的共面的网格来得以提高。为了得到这些网格，可以用长度，面积，体积，角度等，来测量每个顶点的其他临近的顶点。当这些共面的顶点被刈除或是被大的三角形代替，多边形的数量减少了，但是物体的形状仍和原来物体相差不多。这样原来的物体将被尽可能多的保留下来。
4.将来3-D游戏引擎
上面我们讨论的所有的算法都是串行的，都是设计运行在一个处理器的计算机上。尽管今天主流的游戏者都在用这种配置，多处理器的计算机是未来工业的一种趋势。现在在多处理器上的3-D引擎算法方面作了很多的研究工作。Rohlf and Helman解释了3-D引擎的不同构件之间如何用不同的并行散发进行优化。他们研究的3-D引擎用多处理技术来划分多个处理器之间的工作，并且用管道来管理数据。他们同时也证明了处理器如何同步在不同环境下它们之间的操作。
Igehy介绍了一个感兴趣的方向将OpenGL程序接口扩展到并行处理上。他的扩展允许多个绘图设备同时来画一张图。最初所包括的同步化是允许并行横行一个明确的有序的场景。在一个24处理器的系统上应用这个程序接口的运行证明了它的有效性。
5.总结
我们已经介绍了一些主要的方面来执行一个实际的3-D游戏引擎。这个引擎的设计是轻便的和有效的，因为它允许游戏程序有效的构建和控制场景对象。我们也强调了很多3-D引擎应用的优化技术。光敏感输出是我们在3-D引擎中所用算法的必要部分。在场景和物体层面为了将对静态和动态物体的渲染性能提高到最大优化是必须要做的。最后，简单讨论了一些额外的用来提高并行处理的3-D引擎性能的源码。
评论: 0 查看评论 发表评论
找优秀程序员，就在博客园
最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)
编辑推荐：史上最强女游戏程序员
网站导航：博客园首页 个人主页 新闻 闪存 小组 博问 社区 知识库