3D游戏引擎中的室外大场景渲染技术研究与实现毕业设计.doc

3d游戏引擎中的室外大场景渲染技术研究与实现关键字: 室外场景渲染lod技术geomipmap场景管理多纹理混合3d游戏特别是网络在线游戏中，室外大场景渲染是一块非常重要的内容，它也是3d图形引擎的核心。它是图形学和图像处理理论最直接的应用，其涉及的技术还可以应用于其它领域，比如虚拟现实、3d gis、数据可视化等，其重要性不容置疑。随着硬件的不断发展，行业对渲染场景的规模和真实感提出了更高的要求。毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日第一章 绪论1.1概述众所周知，近几年以电子游戏为主的计算机互动娱乐产业迅猛发展，已成为国民经济的重要组成部分。然而，由于我国的软件业起步较晚，3d游戏的核心技术被欧美、日韩等牢牢占据。如何掌握相关核心技术已成为中国电子娱乐产业的当务之急。室外场景渲染是指对户外所有景物的真实绘制，相对于室内场景渲染，它更为复杂。在3d游戏特别是网络在线游戏中，室外大场景渲染是一块非常重要的内容，它也是3d图形引擎的核心(见图1.1)。游戏引擎中大场景的渲染技术是图形学和图像处理理论的最直接应用，其涉及的技术还可以应用于其它领域，比如虚拟现实、3d gis、数据可视化等，其重要性不容置疑。1.1.1室外场景渲染研究的内容和难点真实感的室外场景除包括地表的基本几何形状绘制，还包括地表上的生物如：草、岩石、树等的渲染以及对光影效果的表现。其中的难点主要在大规模地表的数据处理和真实感的仿真。地形场景中模型图元的数量是以场景大小平方的速度增长的。一个81938193维数的地形，如果不考虑减低细节程度和裁剪，绘制一帧将要渲染128m个三角形，这样的三角形量在pc级别的机器上目前还是远不能实现交互式帧率的。所以，如何减少渲染地形的图元数目一度成为室外场景实时渲染的关键问题。随着硬件技术的发展，每秒钟处理上亿个三角形已不再困难。很多计算如几何变换和光栅处理都可以交给gpu去计算。在gpu数据吞吐量很大的情况下，如果个算法在剔除渲染图元的过程中占用了太多cpu资源，出现gpu等待cpu的情况，那么即使算法在剔除多余顶点方面做得很好，总体绘制效率也不是高效的。所以在目前的显卡硬件架构下，能充分发挥cpu与gpu性能，消除局部效率瓶颈的算法才是最好的算法。在真实感仿真上，比如对草丛的模拟，如果全部用细节三角形面片，那即使一片草地需要渲染的三角形个数也是难以想像的。目前对物体细节的表现还主要是运用纹理贴图的方式来实现。光影效果的表现涉及局部光照模型、全局光照模型、光照贴图、阴影生成等相关算法和技术。1.1.2国内外技术发展历程和现状在国外，3d游戏中场景渲染技术的发展大致可以分为三个阶段：三维真实感场景渲染领域的研究在国外起步很早，很多相关算法在8090年代就已提出，并建立了非常严密的理论体系。比如对场景渲染非常重要的多边形lod算法，场景空间管理的bsp、四叉树、八叉树等算法，光照模型，阴影算法等。但是这些算法在资源有限的微机上受到各方面限制。当时的这些算法还仅限于在大型机和图形工作站上实现。92年，随着id soft公司一款游戏quake(雷神之锤)的发布，标志着第一款支持多边形模型、动画、粒子系统的全三维游戏在个人计算机上正式诞生。在随后发布的quakeii、unreal、half life等游戏中，场景渲染相关的lod技术、bsp空间管理技术、光照贴图、凹凸贴图、多重贴图等相继应用在3d游戏中。随后出现的quake、unrea游戏引擎，更是标志着3d游戏引擎技术走向成熟。现阶段，随着显卡技术的发展，gpu不但支持标准的(固定的)变换与光照(tl)管道线，还支持顶点着色(vertex shader)和像素着色(pixel shader) 方式，开发人员因此有了更大的自主空间，可以实现更真实的绘制功能。在此环境下，各大公司都着手开发新一代3d游戏引擎。其中商业引擎以quakeiii、unrealii最为出名。此外，软件开源社区的不断壮大，也诞生出一些比较好的开源3d引擎，比如ogre等。运用这些引擎中的场景渲染技术能生成真实感更强的水波、天气系统、茂密的森林、流熔岩的火山等效果，场景的规模也更大，顶点动态光照技术也开始在室外场景中应用。3d游戏的趋势是往超大规模场景，真实感表现的虚拟世界发展。大规模场景表现和游戏的虚拟仿真，自然也成为了世界上3d游戏行业非常热门和前沿的研究领域与方向。比如美国暴雪公司的“魔兽世界和韩国ncsoft公司的“天堂2已经在这两个方而取得了相当的突破和进展。暴雪的“魔兽世界按人的比例来计算，世界地图已达到35km35km。随着电子娱乐业的迅猛发展，国内目前从事3d引擎研究和开发的公司也多了起来。比如目标软件的gfx3d引擎，盛大公司的3d引擎，网易公司的3d引擎，锦大科技的aurora引擎等，还有一些游戏工作组的3d引擎，比如win3d系列，origo系列，tuam9系列引擎等。但总体上来说，国内还处在使用和模仿优秀引擎的阶段，很多都是在国外优秀引擎上做一些延伸。真正严格意义上自主开发产品还几乎没有，或者说自主开发产品的质量和欧美日韩还有一定差距。这种差距在一定程度上反映在3d大场景渲染技术方面，因此深入的展开这方面的研究十分必要。1.2课题研究的目的本课题希望通过剖析多款成熟3d游戏、引擎，对3d引擎的核心部分一室外场景渲染技术进行探讨，并设计和实现自己的一些方案，给我国商业游戏引擎的开发带来一些启示。1.3论文的篇章结构本文本着注重实际应用的前提，通过剖析开源3d引擎并运用推测验证的方法，对室外场景渲染的主要技术进行了研究和实现，在很多章节也提出了自己的方案和优化方法。以下对各章的内容进行简要描述。第一章绪论。介绍3d室外场景渲染的基本概念，介绍国内外在这一领域的研究现状，阐述课题的意义和研究内容。第二章介绍3d图形渲染的基础知识，包括图形渲染的原理、流程以及实现图形渲染可以应用的类库opengl。第三章研究室外超大场景地形网格的生成与简化算法，比较各种基于lod思想的网格简化算法的优劣，提出基于几何多重映射(geomipmap)的地形绘制优化方案，并得以实现。研究也涉及到地形的空间管理算法、可见性剔除算法、超大场景的数据加载方式研究等。第四章研究场景的真实感渲染技术。主要涉及应用多层纹理混合贴图模拟融合性地表技术，室外场景的光影效果处理技术，天空、树、草、雾等的渲染方案和技术。第五章描述本设计实现的室外渲染软件demo osrender，以及程序编写过程中可用的优化技术。第六章对全文进行总结，介绍开题论文的完成情况，客观评价优点和不足，并给出改进的方向。第二章 3d游戏场景渲染的基础知识室外场景渲染从基本原理上来说可以分为两类：基于体素的渲染方法和基于多边形的渲染方法。早期的3d游戏，如三角洲特种部队就是采用的体素渲染法。体素法类似光线跟踪渲染，它从屏幕空间出发，找到地形与屏幕像素发出的射线交点，然后确定该像素的颜色。这种方法不依赖具体的图形硬件，整个渲染过程完全使用cpu处理，因此它不能使用图形卡硬件来加速，并且对于一个场景来说，往往不只是地形，还有其他使用多边形描述的物体，体素法渲染的图像很难与硬件渲染的多边形进行混合，因此这种方法现在用得极少，而多边形渲染方法则成为一种主流。选择多边形来描述和渲染地形有很多优点，最主要的是它能够很好地使用硬件加速，并且能够和其他多边形对象一起统一管理。因此本课题仅对基于这种多边形面片的场景渲染技术进行研究。2.1基于多边形面片的3d渲染原理2.1.1基于多边形面片的图形绘制流程用多边形面片来建立物体的三维模型有容易表示、计算简单、容易绘制几个方面的好处，因此在游戏三维图形渲染中被广泛采用(通常是三角形面片)。从模型的顶点送入渲染管道到最后形成二维图像的过程如下图2.1所示：2.1.2变换渲染管道中大部分工作是把对象模型的顶点在一个坐标系中的表示转化为另一坐标系中的表示，一般需要经过模型变换和相机变换两个过程。通常，几何模型被保存在自身的建模空间，即每个模型拥有单独的局部坐标系统。为了建立场景几何关系，模型将统一放置到世界坐标系中，从建模坐标系变换到世界坐标系叫模型变换。几何模型的最终成像是在摄像机坐标下，将场景物体从世界坐标系变换到摄像机坐标系叫相机变换。相机的外部参数决定了相机坐标系，因此场景在屏幕上的成像位置与形状和相机的外部参数有关。模型和相机变换采用44齐次矩阵表示，其形式如下：比如平移变换可表示如下：点(x，y，z)平移(tx,ty,tz)后的坐标为(x，y，z)。此外还有旋转、缩放变换，这三种基本的变换可以合成任意几何变换。通常把模型变换和相机变换的矩阵复合成一个矩阵处理，便于提高效率。在所有的图形绘制库中，都提供了程序接口供应用程序设置模型和相机变换对应的矩阵。其中，模型变换由场景物体的平移和旋转、缩放变换组成，相机变换则通过设置相机的位置、相机方向和向上向量来决定。2.1.3裁剪相机的参数包括投影方式、近平面、远平面、视野和屏幕的长宽比率，它们决定了物体从相机坐标系投影变换到屏幕坐标系的位置。这些参数实际上定义了一个视域四棱锥，也叫做视锥体。位于视锥体之外的场景部分不需要送入后续阶段处理。因此，对完全位于规一化的设备空间之外的几何元素，可简单地舍弃。而部分位于规一化的设备空间之外的几何元素则需要进行裁剪操作。由于裁剪的面就是立方体的6个表面，实现起来非常简便。应用程序也可以定义额外的平面对场景进行裁剪。视域裁剪通常由底层图形ap自动完成。注意这里所说的裁剪是比后面章节要介绍的视锥体剔除更底层的裁剪。2.1.4投影把三维物体变为二维图形表示的过程称为投影，其又分为平行投影和透视投影。透视投影是所有投影线交于投影中心；而平行投影是投影线平行，投影中心在无穷远。在游戏虚拟场景模拟中主要应用透视投影。透视投影可分为一点透视、二点透视和三点透视。针对一点透视投影如下图：从上图p点在观察平面上的投影我们可以得到描述尸点的参数方程：2.1.5光栅化从顶点组成的几何模型变换到像素的过程称为光栅化(rasterization)。它的机理与得名来源于crt显示器的电子枪发射方式。光栅化可分为四个子阶段，即消隐、逐像素光照明计算、纹理映射和颜色融合。(1)消隐消隐的目的是解决场景的可见性问题。所谓可见性计算，是指计算物体投射到投影平面如果有交叠，观察者应该看到哪个投影点。图形学中经典的解决方案是物体空间z一缓冲器算法和图像空间的光线跟踪算法。由于z-缓冲器算法易于在图形硬件中实现，逐渐演化称标准的图形硬件消隐技术。在深度缓冲器中，每个像素上始终保留最接近视点的深度。当光栅化产生新的像素后，该像素的深度和保存在深度缓冲器的像素深度进行比较，如果小于已有的像素深度，则用像素的颜色和深度替换分别保存在颜色缓冲器的像素颜色和深度缓冲器中的像素深度，反之保持不变。在绘制之前，深度缓冲器必须初始化为最远的深度，以保证可见性计算的正确性。(2)光照计算光照计算影响物体的外观。进行光照计算的几个要素包括光源位置、光源属性、光照模型、物体表面材质属性、纹理和物体表面几何属性(包括法向、微几何结构)等。最简单的光照明计算技术是在物体建模时指定每个顶点的颜色和纹理坐标，在绘制时直接利用颜色和纹理映射融合为最终颜色。这种方法称为平坦渲染(flat shading)模式，它的速度快，但效果欠佳，是早期游戏中最常用的技术。真正意义上的光照计算必须指定每个光源本身的属性，包括光源的类型(点、线、面光源)、位置和光源的漫反射镜面反射的颜色，然后根据光照模型(分局部光照明模型和全局光照明模型，前面所述直接指定顶点颜色的方法可看作最简单的局部光照明模型)在物体的每个顶点计算每个光源对该顶点的光亮度贡献，最后在光栅化层插值顶点上的颜色。这种处理模式称为gouraud渲染模式，著名游戏guakeei就使用了gouraud渲染模式。逐顶点的光照计算对应于gouraud渲染模式，而逐像素光照计算则对应于法向渲染模式(也称为phong渲染模式)。phong模式在游戏场景渲染中也被广泛采用。在游戏三维引擎设计中，必须根据图形硬件配置和场景复杂度选择合适的光照渲染模式。(3)纹理映射纹理映射是增强场景真实感的一种简单有效的技术。它将预生成的图像直接贴在物体表面，模拟物体表面外观，因此也叫贴图法。纹理映射的扩展技术有很多，包括环境映射、光照图、球面映射、立方体映射、凹凸映射、位移映射等，是图形渲染加速中最重要的手段。在真实感渲染章节会有更详细的讨论。(4)颜色融合对于每一个像素，前面步骤可能产生光照计算和纹理映射两类颜色值。不仅如此，光照明计算的结果可能来自多个光源，而每个光源可导致漫反射和镜面反射的光亮度。此外，同一像素也可能采集来自多个纹理的值，如多通道纹理映射和单通道多重纹理映射。所有这些颜色值将根据各自的不透明度融合出最终结果。颜色融合不仅能加强场景真实感，还能产生半透明绘制、景深、基于alpha缓冲器的反走样、软阴影等特效。2.2图形绘制库opengl2.2.1 opengl的基本理解图形渲染引擎中的最底层可以自己实现，但是没有显卡硬件厂商的支持，自己实现的往往不能得到硬件加速特性。所以游戏中的图形渲染通常需要利用0pengl和directx等成熟图形库。现在很多游戏引擎对两个库都提供支持，作为学术研究opengl是更好的选择，所以本设计在实现算法时选用了opengl。opengl是一个封装了硬件图形加速器的软件接口口7|，几乎全部显卡对它都提够良好支持。它也是图形库的业界标准。opengl包括了100多个图形操作函数，开发者可以利用这些函数来构造景物模型、进行三维图形交互软件的开发。也可以说，opengl是一个高性能的图形软件开发包。opengl支持网络，在网络系统中用户可以在不同的图形终端上运行程序显示图形。opengl作为一个与硬件独立的图形接口，它不提供与硬件密切相关的设备操作函数，同时，它也不提供描述类似于飞机、汽车、分子形状等复杂形体的图形操作函数。用户必须从点、线、面等最基本的图形单元开始构造自己的三维模型。当然，象3ds max那样更高一级的基于opengl的三维图形建模开发软件包将提供方便的建模工具。所以，opengl的图形操作函数十分基本和灵活。例如opengl中的模型绘制过程就包括网格线绘图方式、反走样网格线绘图方式、平面消隐绘图方式、光滑消隐绘图方式、加阴影和纹理的绘图方式等。总的说来，opengl的功能包括以下几个层面：(1)模型绘制opengl能够绘制点、线和多边形。应用这些基本的形体，可以构造出几乎所有的三维模型。(2)模型观察在建立了三维景物模型后，需要用opengl描述如何观察所建立的三维模型。(3)颜色模式的指定opengl应用了一些专门的函数来指定三维模型的颜色。(4)光照应用用opengl绘制的三维模型必须加上光照才能与客观物体更加相似。opengl提供了管理四种光(辐射光、环境光、镜面光和漫反射光)的方法，另外还可以指定模型表面的反射特性。(5)图象效果增强通过反走样、混合和雾化等函数来增强图象的效果。(6)位图和图象处理opengl还提供了专门对位图和图象进行操作的函数。(7)纹理映射opengl提供的一系列纹理映射函数使得开发者可以十分方便地把真实图象贴到景物的多边形上，从而可以绘制逼真的三维景观。(8)实时动画为了获得平滑的动画效果，需要先在内存中生成下一幅图象，然后把已经生成的图象从内存拷贝到屏幕上，这就是opengl的双缓存技术(double buffer)。opengl提供了双缓存技术的一系列函数。(9)交互技术opengl提供了方便的三维图形人机交互接口，用户可以选择修改三维景观中的物体。2.2.2 opengl的工作流程整个opengl的基本工作流程如2.4图：其中几何顶点数据包括模型的顶点集、线集、多边形集，这些数据经过流程图的上部，包括运算器、逐个顶点操作等；图像数据包括象素集、影像集、位图集等，图像象素数据的处理方式与几何顶点数据的处理方式是不同的，但它们都经过光栅化、逐个片元(fragment)处理直至把最后的光栅数据写入帧缓冲器。在opengl中的所有数据包括几何顶点数据和象素数据都可以被存储在显示列表中或者立即可以得到处理。opengl中，显示列表技术是一项重要的技术。opengl要求把所有的几何图形单元都用顶点来描述，这样运算器和逐个顶点计算操作都可以针对每个顶点进行计算和操作，然后进行光栅化形成图形碎片；对于象素数据，象素操作结果被存储在纹理组装用的内存中，再像几何顶点操作一样光栅化形成图形片元。在整个流程操作的最后，对图形片元进行一系列的逐个片元操作，最后的象素值送入帧缓冲器实现图形的显示。2.2.3 opengl的程序结构第一部分是初始化部分。主要是设置一些opengl的状态开关，如颜色模式(rgba或alpha)的选择，是否作光照处理(若有的话，还需设置光源的特性)，深度检验，裁剪等等。第二部分设置观察坐标系下的取景模式和取景框位置大小。主要利用了三个函数：函数void glviewport(1eft，top，right，bottom)：设置在屏幕上的窗口大小，四个参数描述屏幕窗口四个角上的坐标(以象素表示)；函数void glortho(1eft，right，bottom，top，near，far)：设置投影方式为正交投影(平行投影)，其取景体积是一个各面均为矩形的六面体；函数void gluperspective(fovy，aspect，znear，zfar)：设置投影方式为透视投影，其取景体积是一个平截头体(frustum)。第三部分是opengl的主要部分，使用opengl的库函数构造几何物体对象的数学描述，包括点线面的位置和拓扑关系、几何变换、光照处理等等。以下是第三部分的一个简单例程：2.3本章小结场景渲染总的来说分为基于多边形面片和基于体素两种方法。由于基于体素的方法不适应现代硬件的渲染流程，故本设计主要研究的是基于多边形面片的场景渲染。本章从图形学原理出发，讨论了基于多边形面片的3d渲染的基本流程以及其中涉及的数学模型。另外，还介绍了应用广泛的图形库opengl，为下面章节的具体算法讨论和软件实现做基础铺垫。第三章 室外场景地形的实时绘制技术地形的绘制是指读取虚拟世界的地图信息，绘制出场景的地表，并实现角色在场景中实时漫游。它是室外场景实时绘制中最重要的部分，也一直是计算机图形学中一个重要的研究领域。尽管地形的绘制在不同的游戏中所采用技术会有所不同，但是他们总体上还是遵从一定的流程，如图3.1所示：以下章节会逐步分析相关技术。需要说明的是本章探讨的“绘制”还不包括真实感的表现，可以理解为线框模式下的绘制。3.1地形绘制所需数据地形绘制所涉及的数据主要有：地形的高度图、缩放标尺、地表纹理图、地表纹理索引等。在游戏设计中，表现一个场景所需要的一系列数据往往打包放在一起。3.1.1高度图对基于三角形面片渲染的3d场景来说，地形的顶点信息就是指组成地形的所有三角形面片每个顶点的三维坐标。最简单最有效的地形顶点表示方法是使用高度图(heightmap)u利。通常高度图是一张灰度图，它的长宽通常满足(2n+1)。每个像素的灰度值表示地形相应位置的高度值，用连续的三角形面片来连接这些三维空间中的顶点就构成了地形的面片。高度值的值域范围0-255足以表现游戏中场景的地形起伏，如果需要也可以使用双字节，四字节或更高来描述高度值。在设计中很多游戏由于封装数据的需要，通常自定义高度图的格式，而不采用灰度图，但是其存储的数据本质上是一样的。3.1.2缩放标尺地形信息还应包括缩放标尺，用来表示在绘制时高度图中相邻两个灰度值之间相隔的x，z方向上的距离值。比如一张3333的高度图的缩放标尺是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)技术是一种符合人视觉特性的网格简化技术。我们知道，当场景中的物体离观察者很远的时候，它们经过观察、投影变换后在屏幕上往往只是几个像素甚至是一个象素。我们完全没有必要为这样的物体去绘制它的全部细节，可以适当的合并一些三角形而不损失画面的视觉效果。对于一般的应用，我们通常会为同一个物体建立几个不同细节层度的模型。这样的技术应用在地形渲染中，也称之为多分辨率地形(multiresolution terrain)。下图就是一个多分辨率地形网格：在开发3d游戏时也有不采用基于lod的地形网格简化算法的做法。典型的游戏有韩国游戏公司开发的著名3d网游奇迹，每个tile场景地形它用257257的高度图构成，采用静态载入场景数据的方案同样产生出了美妙的场景。对于这么小的场景，当然没有必要做地形网格的简化，现在的一般显卡足以能够应付。之所以他能成功应用这种方式，是因为在设计场景时限制了地形的高低起伏，使地形趋于简单，缩放标尺取得很大，同时用纹理和光照贴图来弥补地形本质上的单调。另外，如果运用基于外存的动态数据载入算法，理论上也可以不用基于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显示了14层三角形二叉树和相应的层次结构。当把一个三角形分成两个的时候，会在斜边上增加一个顶点，是由斜边的两个端点插值求得。不过高度却不能插值。因为高度是按照相应的地图数据来的(比如heightmap)。所以，就存在一个插值以后的高度和实际高度不匹配的问题(会产生裂缝)。为了解决这个问题，就需要调整y轴上的值来升高或者降低这个顶点，这个顶点高度的调整距离就称为误差量。要确定一个三角形是否要被分割，就要看它是否能精确的描述地形的高度数据。如果可以的话，自然就不用分割了，多边形越少越好。如果不能的话，就细化它，也就是分割掉，直到所有的小三角形都能够精确表示地形数据为止。通过不停的分割，三角形越来越小，每个三角形在高度图上所覆盖的面积也越来越小。那么，总会分割到足够小，使得三角形的面积和高度图上一个点的面积之比为l：l，分到这里就不用再分了。通过检查所有孩子的误差量，我们就找到了一个描述三角形是否需要分割的精确方法。当递归的遍历这棵树以后，就能够找到这棵树里面的最大误差量，就是所谓的largest error metri c。这个最大误差量如果是o那就是完全符合实际高度了，这个值越大，就越不符合。用每个三角形的误差量和镜头到该三角形的距离比较，用以判断是否一个三角形需要分裂。用以给每个三角形做测试的值是人为定义的，这个值又叫错误容忍度(error metric tolerated)。通过错误容忍度对每个三角形做测试，小于这个容忍度的三角形就被留下(不分裂)，大于这个的就被分裂掉，然后再分别对被分裂的三角形的两个儿子做分裂。如果加入了视角依赖(viewdependence)的话，就需要通过镜头到三角形的距离来调整这个容忍度了。镜头越远，容忍度就越大，而镜头越近，容忍度就越小。此算法的优点在于：可动态的改变每个网格；可在渲染时控制每个网格的生成与否；可以和纹理坐标很好的结合在一起；可控制地形三角形的最大数目；可以根据坡度的不同自动调整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=hmaxhmin。err即是此子块的平坦度。err的值越大就意味着子块越不平坦，网格细节应该越多。最终，综合考虑距离和平坦度两个因素得出判断是否细化的标准：如果err*rdko则继续细化，反之则不。(k为一个可变的控制值，r为子块的i2边长，err为子块平坦度，d为子块到视点的距离)。3.4.3算法运行步骤(1)初始化顶点数组，建立完全四叉树并初始化，使每个节点描述清楚自己对应的区域地形。(2)实时渲染：首先对每个四叉树节点进行视锥体裁剪，确定进行渲染的四叉树节点，再渲染这些节点。a.对节点进行视锥体裁剪。b.确定哪些节点需要渲染：先计算本节点所管理的地形区域离视点的距离，再计算其平坦度，两者共同确定渲染精度值。根据渲染精度值和判定标准来确定是否需要进一步细分，对于需要细分的就按四叉树思想递归细分，而不需要细分的就设置它的渲染标志位为真。c.遍历四叉树，渲染标志位为真的节点，并判定本节点区域网格在渲染时是否会出现t型裂缝。判定方法是通过和四周相邻的节点比较细节分辨率值，如果小于相邻节点则做修补裂缝处理。(3)释放资源。3.4.4算法相关代码以下是10251025大的高度图用基于四叉树的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)，比如用3333的block把1025x 1025的地形表示为3232个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，如99，1717，3333等。如果地势总体比较平坦，我们可以选得大一点，如果对地形的细节要求较高我们可以选得小一点。本文以1717作为block的大小。block通过顶点索引所组成的三角形带描述他负责的一片小的区域。整个场景