3d游戏引擎中的室外大场景渲染技术研究与实现毕业设计(编辑修改稿)

3d游戏引擎中的室外大场景渲染技术研究与实现毕业设计(编辑修改稿)内容摘要：

要研究的是基于多边形面片的场景渲染。 本章从图形学原理出发，讨论了基于多边形面片的 3D 渲染的基本流程以及其中涉及的数学模型。 另外，还介绍了应用广泛的图形库 OpenGL，为下面章节的具体算法讨论和软件实现做基础铺垫。 第三 章 室外场景地形的实时绘制技术 地形的绘制是指读取虚拟世界的地图信息，绘制出场景的地表，并实现角色在场景中实时漫游。 它是室外场景实时绘制中最重要的部分，也一直是计算机图形学中一个重要的研究领域。 尽管地形的绘制在不同的游戏中所采用技术会有所不同，但是他们总体上还是遵从一定的流程，如图 所示： 以下章节会逐步分析相关技术。 需要说明的是本章探讨的 “绘制 ”还不包括真实感的表现，可以理解为线框模式下的绘制。 地形绘制所需数据 地形绘制所涉及的数据主要有：地形的高度图、缩放标尺、地表纹理图、地表纹理索引等。 在游戏设计中，表现一个场景所需要的一系列数据往往打包放在一起。 高度图 对基于三角形面片渲染的 3D 场景来说，地形的顶点信息就是指组成地形的所有三角形面片每个顶点的三维坐标。 最简单最有效的地形顶点表示方法是使用高度图 (heightmap)u 利。 通常高度图是一 张灰度图，它的长宽通常满足 (2^n+1)。 每个像素的灰度值表示地形相应位置的高度值，用连续的三角形面片来连接这些三维空间中的顶点就构成了地形的面片。 高度值的值域范围 0255 足以表现游戏中场景的地形起伏，如果需要也可以使用双字节，四字节或更高来描述高度值。 在设计中很多游戏由于封装数据的需要，通常自定义高度图的格式，而不采用灰度图，但是其存储的数据本质上是一样的。 缩放标尺 地形信息还应包括缩放标尺，用来表示在绘制时高度图中相邻两个灰度值之间相隔的 X， Z 方向上的距离值。 比如一张 3333 的 高度图的缩放标尺是 l 米，则在游戏中我们可以看到一个 32MX 32M 大小的场景。 此外，在 Y 方向上也有一个缩放标尺，负责地形高度的缩放。 顶点法向量 地形网格上的各点都需要一个表面法向量。 它可以用来计算光照，进行背面剔除，检测与表面的碰撞等。 一个三角形的法向量可以通过三角形上两向量叉乘的方法轻松获得，而顶点级法向量可以通过共享此顶点的所有三角形的法向量求平均值来模拟，在很多情况下，这样的效果已经能够达到要求了。 顶点处其实是没有法向量定义的，因为此处网格表面不连续。 多种地表纹理及 光照贴图 为了表现地形的真实感，目前游戏中的做法是通过多重纹理混合贴图来实现的。 其中用到的贴图通常以各种图片格式保存。 关于这种技术的讨论在真实感渲染章节会详细介绍。 单个场景地形的数据结构 由以上的分析我们就可以得到单个场景地形的数据结构，如下所示： 面片的构成 任何多边形模型都可以转换成三角形的集合，所以地形网格也是三角形的集合。 如果三角形被各自独立地送至图形硬件进行绘制，共享的顶点数据就需要执行重复冗余的运算，并且相同的数据还被传送至少两次以上。 降低这些额外开销的一个方法就是把彼此相邻的三角形构建成三角带 (strip)。 首先，把第一个三角形的三个 顶点放至 strip 之中，然后将其余的三角形顶点依照相邻顺序依次放至 strip 中，每个三角形只需要加入二个顶点。 缺省条件下，在 strip 中彼此相邻的顶点都构成了连接两个相邻三角形的公共边。 如果连接规则 (顺时针或者逆时针顺序 )需要发生改变，则可以使用 swap 命令交换顶点顺序，或者重新将某一个顶点放入 strip 之中。 扇形三角形带 (Triangle fans)可以看作是三角带的一种退化形式，只是其中所有的三角形都共享一个公共顶点。 图 是三角形带的表示方法： V0， V1， V2， V3， V4 五个顶点构成了表示三个三角形的三角形带。 注意描述三角形带时，顶点的顺序很重要，因为是遵循一定连接规则 (顺时针或逆时针 )的。 在 OpenGL 中生成最右方的三角形带的代码如下： LOD 地形网格简化算法的基本思想及意义 所谓地形网格的简化是指通过算法减少提交到显卡的顶点，以减少每帧同屏渲染的三角形数量，借以提高渲染速度。 细节层次 (LOD， levels of Details)技术是一种符合人视觉特性的网格简化技术。 我们知道，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个像素甚至是一个象素。 我们完全没有必要为这样的物体去绘制它的全部细节，可以适当的合并一些三角形 而不损失画面的视觉效果。 对于一般的应用，我们通常会为同一个物体建立几个不同细节层度的模型。 这样的技术应用在地形渲染中，也称之为多分辨率地形 (Multi—Resolution Terrain)。 下图就是一个多分辨率地形网格： 在开发 3D 游戏时也有不采用基于 LOD 的地形网格简化算法的做法。 典型 的游戏有韩国游戏公司开发的著名 3D 网游《奇迹》，每个 Tile 场景地形它用 257257 的高度图构成，采用静态载入场景数据的方案同样产生出了美妙的场景。 对于这么小的场景，当然没有必要做地形网格的简化，现在的一般显卡足以能够应付。 之所以他能成功应用这种方式，是因为在设计场景时限制了地形的高低起伏，使地形趋于简单，缩放标尺取得很大，同时用纹理和光照贴图来弥补地形本质上的单调。 另外，如果运用基于外存的动态数据载入算法，理论上也可以不用基于 LOD 的地形网格简化算法。 随着 3D 游戏的成熟，玩家需要有更真实的体验，因 此地形变得更加复杂，场景变得更加巨大，地形的绘制需要很多数据参与，对系统资源消耗巨大。 如果一点也不进行地形网格简化，试想一个 1025 X1025的场景就将生成 2M 个三角形，渲染大的场景时显卡的处理能力很难跟上。 在显卡的数据吞吐能力有限的情况下，游戏场景渲染中普遍基于 LOD 的思想，减小绘制多边形数目。 它能在牺牲适量 CPU 资源的前提下大大减轻图形卡的数据负载，使 CPU 与 GPU 之间没有明显的瓶颈，从而达到实时渲染大地形的目的。 基于 LOD 的地形网格简化算法分为动态 LOD 和静态 LOD 算法。 动态 LOD 算法是在每帧 渲染之前都经过计算重新确定送入显卡的顶点。 所有的顶点数据全部需要参与运算。 ROAM 算法和基于四叉树的动态LOD 算法都属于此类， GeoMipMap 算法则是静态 LOD 算法的代表。 ROAM 算法 1997 年， Duchaineau 提出了实时优化适应性网格 (ROAM， RealtimeOptimalAdaptive Meshes)算法瞳 1，它是一种基于规则网格的连续 LOD 网格构造算法。 其基本思想是在对地形进行三维显示时，依据视点的位置和视线的方向等多种因素，对表示地形表面的三角形图元进行一系列基于三角形 二叉剖分分裂与合并，最终形成和原始表面近似且无缝无叠的简化连续三角形表面。 ROAM 的基础是等腰直角三角形的一个性质。 等腰直角三角形可以从直角顶点到斜边引一条垂线，这条垂线把这个三角形分成了两个小的等腰直角三角形，并无限制的递归分下去。 而从另一个角度来看，这正好构成了一个二叉树，每个三角形都是把它分开而生成的两个小三角形的父母 (parent)。 根据这条性质，只要计算出哪些三角形需要被分割开、哪些三角形需要合并成为自己的父母，就可以做到控制 LOD(分开就是增加 LOD，合并就是减少 LOD)。 图 显示了 1～ 4 层三角形二叉树和相应的层次结构。 当把一个三角形分成两个的时候，会在斜边上增加一个顶点，是由斜边的两个端点插值求得。 不过高度却不能插值。 因为高度是按照相应的地图数据来的 (比如 heightmap)。 所以，就存在一个插值以后的高度和实际高度不匹配的问题 (会产生裂缝 )。 为了解决这个问题，就需 要调整 Y 轴上的值来升高或者降低这个顶点，这个顶点高度的调整距离就称为误差量。 要确定一个三角形是否要被分割，就要看它是否能精确的描述地形的高度数据。 如果可以的话，自然就不用分割了，多边形越少越好。 如果不能的话，就细化它，也就是分割掉，直到所有的小三角形都能够精确表示地形数据为止。 通过不停的分割，三角形越来越小，每个三角形在高度图上所覆盖的面积也越来越小。 那么，总会分割到足够小，使得三角形的面积和高度图上一个点的面积之比为 l： l，分到这里就不用再分了。 通过检查所有孩子的误差量，我们就找到了一个描述三 角形是否需要分割的精确方法。 当递归的遍历这棵树以后，就能够找到这棵树里面的最大误差量，就是所谓的 largest error metri c。 这个最大误差量如果是 O 那就是完全符合实际高度了，这个值越大，就越不符合。 用每个三角形的误差量和镜头到该三角形的距离比较，用以判断是否一个三角形需要分裂。 用以给每个三角形做测试的值是人为定义的，这个值又叫错误容忍度 (error metric tolerated)。 通过错误容忍度对每个三角形做测试，小于这个容忍度的三角形就被留下 (不分裂 )，大于这个的就被分裂掉，然后再 分别对被分裂的三角形的两个儿子做分裂。 如果加入了视角依赖 (view—dependence)的话，就需要通过镜头到三角形的距离来调整这个容忍度了。 镜头越远，容忍度就越大，而镜头越近，容忍度就越小。 ’ 此算法的优点在于：可动态的改变每个网格；可在渲染时控制每个网格的生成与否；可以和纹理坐标很好的结合在一起；可控制地形三角形的最大数目；可以根据坡度的不同自动调整 LOD 的细节程度，也就是说在地形坡度大的地方 LOD 细节程度高，在地形坡度小的地方 LOD 细节程度低；可以根据到观察点的距离自动调整 LOD 的细节程度，也就 是说在离观察点近的地方 LOD 细节程度高，在离观察点远的地方 LOD细节程度低。 基于四叉树的动态 LOD 算法 算法思想 此算法是 Lindstrom 提出的 n 劓，他用了一个叫四叉树 (Ouad Tree)的结构来描述地形，先把可视范围内的地形分割成四等份矩形子块，依靠计算判定因子检测四个子块，如果检查到某个子块的网格精度达到所 要求的绘制精度就不需要往下再分割；否则就把此子块再分割成四等份更小的子块，依次递归分割下去，直到所有子块中的矩形网格都达到渲染精度。 此算法涉及的难点 ●对 T 形裂缝的处理 由于不同层次间的采样间隔不同，在可视化过程中会出现缝隙，这种缝隙必须进行专门的处理 .如图所示，上方矩形具有较高的分辨率，而下方矩形的分辨率较低，这使得矩形间的连接处出现了末被覆盖的区域 (阴影处 )，从而在地形绘制时就产生了 “裂缝 ”。 每个 .LOD 层次区域节点均为正 方形，在分辨率低的四叉树区域节点上，四个方向均可能出现缝隙，所以必须依次用自身节点的分辨率大小比较四个方向上临近节点的分辨率大小。 如果前者小于后者，则必须通过在相邻边上加一条边来实现裂缝的消除。 当自身节点分辨率与相邻节点的分辨率相差不止一级，那么还必须递归比较并添加边，直到完全消除裂缝。 ●判定是否细分 子块离视点的距离和地形的平坦度共同确定是否需要进一步细分以达到所要求的渲染精度，从而使最终分割后的叶子节点达到最优。 离观察者视点越近的地方细节越多，地形越不平坦细节越多。 子块离视点的距离 d 可以 用公式表示如下： 其中 (Xl， Y1， Z1)为视点坐标， (XO， YO， ZO)为子块的中心坐标。 对一个子块区域平坦度的计算如图 所示： 对于图中这个子块的平坦度，先计算出高度值 h 卜 h8，找出其中最大的高度值 hMax，最小的高度值bMin，令 err=hMax—hMin。 err 即是此子块的平坦度。 err 的值越大就意味着子块越不平坦，网格细节应该越多。 最终，综合考虑距离和平坦度两个因素得出判断是否细化的标准： 如果 err*r／ d—kO 则继续细化，反之则不。 (k 为一个可变的控制值， r 为子块的 i／ 2 边长， err 为子块平坦度， d 为子块到视点的距离 )。 算法运行步 骤 (1)初始化顶点数组，建立完全四叉树并初始化，使每个节点描述清楚自己对应的区域地形。 (2)实时渲染：首先对每个四叉树节点进行视锥体裁剪，确定进行渲染的四叉树节点，再渲染这些节点。 ： 先计算本节点所管理的地形区域离视点的距离，再计算其平坦度，两者共同确定渲染精度值。 根据渲染精度值和判定标准来确定是否需要进一步细分，对于需要细分的就按四叉树思想递归细分，而不需要细分的就设置它的渲染标志位为真。 ，渲染标志位为真的节 点，并判定本节点区域网格在渲染时是否会出现 T 型裂缝。 判定方法是通过和四周相邻的节点比较细节分辨率值，如果小于相邻节点则做修补裂缝处理。 (3)释放资源。 算法相关代码 以下是 10251025 大的高度图用基于四叉树的 LOD 算法在线框模式下生成的地形网格： 游戏中地形绘制更好的方案 . 随着图形卡数据吞吐能力的不断提高，每秒钟处理上亿个三角形己不再困难。 很多计算，比如几何变换和光栅处理都可以交给 GPU 去计算。 所以在 GPU 数据吞吐量很大的情况下，如果 一个算法在剔除渲染顶点的过程中占用了。