【培训课件】游戏中的场景管理技术

游戏中的场景管理技术游戏中的场景管理技术作业对游戏的评价（每个人）10%小组游戏proposal(每组)10%对其他小组游戏proposal的评价（每组）10%请用OGRE实现任意一项10%三维光照场景组织光影特效（包括阴影）大程作业40%平时点名20%作业对游戏的评价（每个人）10%2游戏Quake3的场景

游戏Quake3的场景3三维游戏场景的组织和绘制三维游戏中的图形技术可分为三个方面场景的几何组织与优化着重于提高绘制效率场景的画面真实度,采用一系列特效生成技术包括高级纹理映射,过程式建模等基于真实物理定律的游戏效果模拟主要是阴影模拟和碰撞检测本次课程将着重讲解三维游戏场景的几何组织,优化管理以及在此基础上的OGRE中的复杂场景的管理三维游戏场景的组织和绘制三维游戏中的图形技术可分为三个方面4三维游戏场景的组织和绘制三维场景的组织和管理游戏场景的几何优化三维场景的快速可见性判断与消隐地形场景的绘制与漫游碰撞检测简介三维游戏场景的组织和绘制三维场景的组织和管理5基于场景图(Scenegraph)的表达和管理第一步根据游戏的需要更新场景图必要的部分这种更新是部分的,不需要从根节点遍历第二步场景图的剔除和绘制太阳系的场景图基于场景图(Scenegraph)的表达和管理第一步太阳系的6基于绘制状态的场景管理把场景物体按照绘制状态分类绘制状态集合A●砖块纹理●细节纹理●红色材质●无融合模式绘制状态集合B●砖块纹理●细节纹理●灰色材质●无融合模式绘制状态集合C●砖块纹理●凹凸纹理●红色材质●无融合模式绘制状态集合D●立方体纹理●无纹理●单色材质●加法融合模式

绘制状态集合实例基于绘制状态的场景管理把场景物体按照绘制状态分类绘制状态集合绘制状态树实例

绘制状态树实例8基于场景包围体的场景组织加速判断场景物体之间的空间关系,主要有两种方法对单个物体建立包围体,在包围体的基础上建立包围盒层次树场景剖分基于场景包围体的场景组织加速判断场景物体之间的空间关系,主要9常用的包围体技术常用的包围体技术10包围体和包围球示例球的体积比立方体大包围体和包围球示例球的体积比立方体大11OBB树的构造示意图

OBB树的构造示意图12物体的凸包围体常用的类型增量式(incremental)礼包式(gift-wrapping)分治式(divide-and-conquer)快速凸包算法(quick-hull)k-dop(discretedorientationpolytope,离散有向多面体)比上述的包围体更紧密地包围原物体,创建的层次树节点更少物体的凸包围体常用的类型138-dop结构8-dop结构14场景绘制的几何剖分将场景中的几何物体通过层次性机制组织起来优点使用灵活,能快速剔除层次树的整个分枝注意要保持树的平衡!场景绘制的几何剖分将场景中的几何物体通过层次性机制组织起来15包围树包围树16常用的几何剖分技术BSP树

（左）场景的BSP树剖分；（右）BSP树结构示意图常用的几何剖分技术BSP树（左）场景的BSP树剖分；（右）B17BSP树的构造过程（左）一次剖分后的场景平面图；（右）一次剖分后的BSP树（左）两次剖分后的场景平面图；（右）两次剖分后的BSP树

BSP树的构造过程（左）一次剖分后的场景平面图；（右）一次18BSP算法处理四个嵌套遮挡的多边形用画家算法无法处理四个嵌套遮挡的多边形情形BSP算法处理四个嵌套遮挡的多边形用画家算法无法处理四个嵌套19四叉树

（a）场景多边形；（b）第一次剖分；（c）第二次剖分四叉树（a）场景多边形；（b）第一次剖分20八叉树（a）（b）（c）（a）初始节点；（b）第一次剖分；（c）第二次剖分八叉树（a）21景物包围体和场景剖分技术比较（左）场景包围体技术（右）场景剖分技术景物包围体和场景剖分技术比较（左）场景包围体技术（右）场景剖22景物包围体和场景剖分技术比较技术名称适用场景构建复杂度实用性二叉树尺寸不是特别大的室内建筑场景复杂大部分三维游戏引擎四叉树室外基于高度场的地形一般仅用于地形绘制八叉树大规模三维室内、外空间场景一般复杂三维游戏引擎均匀八叉树体素表示场景、分布均匀的三维场景简单少量三维游戏引擎景物包围体和场景剖分技术比较技术名称适用场景构建23景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表示方式层次物体表示层次空间表示剖分方式物体剖分场景剖分聚类方式物体的层次聚类空间的层次聚类层次细节物体层次细节空间层次细节主要作用围绕物体将空间区域区分开来围绕区域将物体区分开来代表方法包围球树OBB-树、AABB树、k-DOPS二叉树、四叉树、八叉树、均匀三维网格、kD树景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表示层次细节(LOD)技术简单取舍型LOD平滑过渡型LOD静态LOD动态LOD层次细节(LOD)技术简单取舍型LOD25LODLOD26经典的简化算法顶点删除边删除最有效!面删除基于边删除的顶点简化经典的简化算法顶点删除基于边删除的顶点简化27兔子模型的四个层次

兔子模型的四个层次28LODModelsLODModels29渐进网格和连续多分辨率绘制技术对于数据量庞大的复杂模型LOD模型只能预先产生多个间断的简化模型引起实时绘制时图形画面的跳跃为克服LOD的缺点,Huppe等人于1995年提出渐进网格技术(ProgressiveMesh)预计算简化过程中原顶点和新顶点的关系由基本网格模型逐步恢复模型细节渐进网格和连续多分辨率绘制技术对于数据量庞大的复杂模型30示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡31示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡32示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡33DemoDemo34场景的可见性判断场景的可见性判断35可见性判断算法分类可见性判断算法分类36遮挡面剔除技术遮挡面剔除技术37遮挡面剔除技术适用于人造建筑物少的室外场景代表性算法:基于阴影体技术（左）遮挡剔除之前；（右）基于阴影体的遮挡剔除遮挡面剔除技术适用于人造建筑物少的室外场景（左）遮挡剔除之前38包围球加速

（左）球A至少在一个平面之外，球B在所有平面之内，但其半径大于球心到其中一个平面的距离，球C在所有平面之后且到所有平面的距离足够大。（右）一种包围球没有被完全遮挡但包围盒被完全遮挡的情形，故物体不应被绘制

包围球加速（左）球A至少在一个平面之外，球B在所有平面之39可见性计算（适用于室内场景）可见性（Visibility）算法用于决定场景中可能可见的物体一般的：保守地指定这些物体并将他们发送到图形绘制引擎确切的可见性决定对于游戏而言是可能的，但是代价太大因此，存在平衡：在软件中进行可见性判断的时间和在硬件中绘制多余的不可见物体的代价最简单的就是绘制引擎本身自带的视域裁剪算法但是这个算法对于高度复杂性的场景并不合适，特别当很多物体位于单个象素之后比如，第一人称视角游戏中常见的建筑物具有高度的深度复杂性。可见性计算（适用于室内场景）可见性（Visibility）算40区分可见性信息Cell-to-Cell可见性告知在一个cell中的某点处是否可以看到其他的房间但是无法知道每个房间的那个部分可能是可见的，也无法知道观察者在这个房间的哪个地方可以见到另外的房间Cell-to-Region可见性可以知道某点处，其他房间的哪些部分是可见的Cell-To-Object:对于某给定的房间，告知哪些物体是可见的。Eye-To-Region可见性记录当前视点处的哪些房间的哪些部分是可见的同理，Eye-to-Cell以及Eye-To-Object区分可见性信息Cell-to-Cell可见性41基于入口(Portal)技术的可见性判断根据单元与单元之间的邻接图,通过深度遍历建立起单元与单元的入口序列基于入口(Portal)技术的可见性判断根据单元与单元之间的42基于入口结构的绘制技术分为两类精细型入口绘制方式粗略型入口绘制技术优点方便定义场景快速绘制缺点消耗大量的内存,换取效率的提高不适合室外渲染基于入口结构的绘制技术分为两类43Cell-Portal结构许多可见性算法假设单元和入口的数据结构数据结构类似于一个图：节点是房间，边是入口Portals本质的意思是两个房间的墙之间存在洞Portal形状一般是多边形两个房间之间也可有多个Portals如何建立这个数据图？Kd-trees或者BSP树用于生成cell结构以及寻找与之相关的portals自动或者手工生成建筑物最合适这种情况Cell-Portal结构许多可见性算法假设单元和入口的数44CellPortal实例Portals可以是房间的边缘（即墙壁）Graph一般保存相邻信息每个房间保留其外向的边（即portals）ABCDEFABCDEFCellPortal实例Portals可以是房间的边缘45Cell-Portal可见性跟踪观察者所在的房间然后遍历graph穷举所有可见的区域可以预处理，对每一个房间计算可能可见集合potentiallyvisibleset(PVS)Cell-to-region

可见性，或者

cell-to-object

可见性也可以在运行之间更进一步地精确获得可见集合从已知观察者的位置出发Eye-to-region

或者Eye-to-cell

可见性平衡：节省下列的时间vs.计算小的可能可见集合的代价与所在环境有关，如房间的尺寸、房间物体的个数…Cell-Portal可见性跟踪观察者所在的房间46PVS:可能可见集PVS:对于某个特定的房间，可能可以看到的房间/区域/物体/多边形一般地，保存可以看见的物体的标识号也要考虑内存的因素预处理的计算过程应该能良好地管理动态变化的物体列表用法:可见性确定–对于当前房间，绘制所有PVS中的多边形做为第一步：获得可能相关的区域，并做进一步处理PVS:可能可见集PVS:对于某个特定的房间，可能可以看到47Cell-to-CellPVSCellA在B的PVS中，当且仅当存在一根线，从B出发射到A，并且在途中与任何物体不相交隔壁房间理所当然在PVS之中IJHGACBEFDI的PVS包括:B,C,E,F,H,JCell-to-CellPVSCellA在B的PV48Stab树这个树状结构表示:当前房间的PVS一个串着的相关的portal序列在进一步的可见性处理中可以减少需要检查处理的cells/portals数目ACDEA/CC/D1C/D2C/EABCDEFDFD/FStab树这个树状结构表示:ACDEA/CC/D1C/D49Cell-to-Cell的用法大多数算法比cell-to-cell可见性算法更复杂因为它过估计–当实际上99.6%的模型应该是不可见的时候，仅排除了大约90%的模型,而更好的算法可以排除98%但是，保持cell-to-cell可见性有利于动态物体当房间中有一个移动的物体并且房间是静态的Cell-to-Cell的用法大多数算法比cell-to-c50Cell-to-Cell的缺点存在的问题:将一个房间中的所有物体都标记为可能可见，尽管只有一小部分是可能可见如果我们要列出可能可见集－意味着我们要将这个房间中的所有物体都列出来。并没有考虑到观察者的位置，无法报告观察者可能看不到的物体进一步处理可以解决这个问题Cell-to-Cell的缺点存在的问题:51Cell-To-Region可见性记录房间中某点处可能可见的某个房间的某个区域因此，只绘制这个区域中的物体关键想法视设置隔离平面（对于二维，就是隔离线):如果将左边的portal视为光源Cell-To-Region可见性记录房间中某点处可能可见52动态可见性处理PVS完全是一个预处理过程在运行时刻，只需要绘制PVS即可更进一步的优化是做进一步处理有时候由PVS指导大多数游戏不这么做一个可能的办法是观察者的位置已知,因此可以使用Eye-to-Region的可见性动态可见性处理PVS完全是一个预处理过程53Eye-to-Region(1)ViewEye-to-Region(1)View54Eye-to-Region(2)Eye-to-Region(2)55没有Cell或者Portals怎么办?很多场景并没有好的cell和portal结构场景中没有大的共面多边形去做为遮挡器或者房间的墙例如森林-你无法看到后面的场景，但是总不能设置叶子为Cell解决方案?定义一些遮挡物体，称为occluders并利用他们来剔除几何物体没有Cell或者Portals怎么办?很多场景并没有好的c56Occluders若occluder是一个多边形否则，使用物体的侧影轮廓线从视点和多边形的边构成裁剪平面也叫支撑平面：Supportingplanes所有在支撑平面内部的是不可见的Occluder自身是一个裁剪平面位于其外部的是可见的eyeoccludersupportingplanesOccluders若occluder是一个多边形eyeoc57Occluders（续）Occluders一般在预处理阶段获得选择的标准?如果它遮挡了很多物体如果大的多边形与视点很近，该方法很有效场景中的一些物体也可以融合起来形成大的occluders例如，将很多树的billboards融合occluding多边形可以任意指定，但是，每一occluder只对某一些视点区域有效问题：如果一个物体被某个occluder部分遮挡,又被另外一个部分遮挡,那么很难决定是否该物体被全部遮挡Occluders（续）Occluders一般在预处理阶段58Occluders（续）用多个occluders来隐藏一个物体是一个很有趣的问题HierarchicalZ-Buffer

方法在图像（屏幕）空间建立遮挡子需要特殊的图形硬件与软件实现张寒松的HierarchicalOcclusionMaps（层次遮挡图）将遮挡子绘制到一个纹理图中，然后将物体与纹理比较SchauflerOccluderFusion

建立一个被遮挡区域的空间数据结构Occluders（续）用多个occluders来隐藏一个物59真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形，帧率为50fps。

当遮挡面剔除关闭时，三角形绘制数目增长到17,300,帧率下降到20fps真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形60地形场景的绘制与漫游

（上左）地形的基础三角网格；（上右）高度图；

（下左）应用高度图后的地形网格；（下右）渲染后的地形图地形场景的绘制与漫游（上左）地形的基础三角网格；61游戏中的地形场景游戏中的地形场景62地形绘制基于四叉树的绘制方法利用图形硬件加速绘制模式保留模式立即模式绘制优化使用场景的层次剖分技术进行视域剔除消除对画面贡献极小的多边形地形绘制基于四叉树的绘制方法63自适应的四叉树剖分根据当前节点的误差度量判断是否需要继续剖分可能在两个相连的节点之间产生漏洞解决方法保证两个相邻节点之间最多相差1个层次保证两个相邻的边拥有相同的顶点数目自适应的四叉树剖分根据当前节点的误差度量判断是否需要继续剖分64地形绘制的优化动态层次细节算法缺点层次之间切换会产生跳跃感几何变形法具有光滑过渡的视觉效果地形绘制的优化动态层次细节算法65地形绘制中的难题存储量大,内存消耗太多解决的方法细节纹理细节纹理的拼接具有很大的挑战性!地形绘制中的难题存储量大,内存消耗太多66利用细节纹理技术的地形绘制实例

利用细节纹理技术的地形绘制实例67OGRE的场景树OGRE的场景树68OGRE中的场景管理在OGRE中场景管理器的类型有四种：ST_GENERIC普通场景ST_EXTERIOR_CLOSE室外封闭场景ST_EXTERIOR_FAR室外无限场景ST_INTERIOR 室内场景OGRE中的场景管理在OGRE中场景管理器的类型有四种：69室内场景首先读入地图包。代码如下BspApplication(){//LoadQuake3locationsfromafileConfigFilecf;cf.load("quake3settings.cfg");mQuakePk3=cf.getSetting("Pak0Location");mQuakeLevel=cf.getSetting("Map");}室内场景首先读入地图包。代码如下70选择正确的场景管理器

voidchooseSceneManager(void){mSceneMgr=mRoot->getSceneManager(ST_INTERIOR);}选择正确的场景管理器voidchooseSceneMa71最后是创建场景

voidcreateScene(void){//LoadworldgeometrymSceneMgr->setWorldGeometry(mQuakeLevel);//modifycameraforcloseworkmCamera->setNearClipDistance(4);mCamera->setFarClipDistance(4000);//Alsochangeposition,andsetQuake-typeorientation//GetrandomplayerstartpointViewPointvp=mSceneMgr->getSuggestedViewpoint(true);mCamera->setPosition(vp.position);mCamera->pitch(90);//QuakeusesX/Yhorizon,ZupmCamera->rotate(vp.orientation);//Don'tyawalongvariableaxis,causesleaningmCamera->setFixedYawAxis(true,Vector3::UNIT_Z);}最后是创建场景voidcreateScene(void)72【培训课件】游戏中的场景管理技术73【培训课件】游戏中的场景管理技术74室外场景OGRE在其引擎提供的Plugin_OctreeSceneManager.dll插件中提供了通过八叉树算法实现的ST_EXTERIOR_CLOSE室外封闭场景管理器。室外场景OGRE在其引擎提供的Plugin_OctreeSc75室外场景

室外场景76室外场景漫游

首先需要选择室外场景管理器，代码如下：virtualvoidchooseSceneManager(void){//GettheSceneManager,inthiscaseagenericonemSceneMgr=mRoot->getSceneManager(ST_EXTERIOR_CLOSE);}室外场景漫游首先需要选择室外场景管理器，代码如下：77室外场景漫游选择好室外场景管理器后，通过该场景管理器创建场景就可以了。voidcreateScene(void){//SetambientlightmSceneMgr->setAmbientLight(ColourValue(0.5,0.5,0.5));//CreatealightLight*l=mSceneMgr->createLight("MainLight");//Acceptdefaultsettings:pointlight,whitediffuse,justsetposition//NBIcouldattachthelighttoaSceneNodeifIwantedittomoveautomaticallywith//otherobjects,butIdon'tl->setPosition(20,80,50);mSceneMgr->setWorldGeometry("terrain.cfg");mSceneMgr->setFog(FOG_EXP2,ColourValue::White,.008,0,250);

mRoot->showDebugOverlay(true);}室外场景漫游选择好室外场景管理器后，通过该场景管理器创建场景78【培训课件】游戏中的场景管理技术79【培训课件】游戏中的场景管理技术80White&BlackWhite&Black81碰撞检测碰撞检测问题是机器人、动画仿真、虚拟现实等领域不可回避的问题基本任务确定两个或多个物体彼此之间是否发生接触或穿透。起源 早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。碰撞检测碰撞检测问题82碰撞检测算法分类从两个角度对碰撞检测算法进行分类从时间域的角度来分从空间域的角度来分碰撞检测算法分类从两个角度对碰撞检测算法进行分类83基于时间域的碰撞检测算法分类

分为静态、离散和连续的碰撞检测算法静态碰撞检测算法 静止状态下进行碰撞检测[Dobkin1985][Agarwal1991][Chazelle1989]离散碰撞检测算法在每一时间的离散点上进行碰撞检测是研究的重点和热点[Lin1998][Jiménez2001]

基于时间域的碰撞检测算法分类分为静态、离散和连续的碰撞检测84基于时间域的碰撞检测算法分类离散碰撞检测算法存在问题存在刺穿现象遗漏应该发生的碰撞连续碰撞检测算法连续的时间间隔内进行碰撞检测计算速度还太慢[Cameron1990][Canny1986][Redon2001][Redon2002a]基于时间域的碰撞检测算法分类离散碰撞检测算法85基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法86基于空间域的碰撞检测算法分类

基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法87基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法多边形表示模型多边形集合，结构化表示模型非多边形表示模型CSG表示模型，隐函数曲面，参数曲面，体表示模型基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向多边形表示模型的碰撞检测算法[Hubbard1995][Gottschalk1996][Klosowski1998][Zachmann1998]面向凸体的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法89基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法面向凸体的碰撞检测算法基于特征的碰撞检测算法Lin-Canny的“最邻近特征算法”[Lin1991,Lin1993][Lin1995],[Cohen1995],[Chung1996],[Mirtich1998],[Ehmann2000],[Ehmann2001]基于单纯形（Simplex）的碰撞检测算法Gilbert、Johnson和Keerthi[Gilbert1988][Gilbert1990]提出的GJK算法[Cameron1997][Bergen1999]基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法90基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向CSG表示模型[Zeiller1993][Su1996][Poutain2001]面向隐函数曲面表示[Farouki1989][Miller1991][Shene1991]面向参数曲面表示非均匀有理B样条曲线（NURBS）[Turnbull1998]体表示模型主要用于虚拟手术中可变形物体的碰撞检测[Heidelb2003][Boyles1999][魏迎梅2001]基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法91基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法空间剖分法（spacedecomposition）均匀剖分、BSP树、k-d树和八叉树（Octree）等[Samet1989][Naylor1990][Bourma1991]层次包围体树法（hierarchicalboundingvolumetrees）基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法92基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分层次包围球树[Hubbard1993][Hubbard1995][Palmer1995][O’Sullivan1999]、AABB层次树（AlignedAxisBoundingBox）[Zachmann1997][Bergen1997][Larsson2001]、OBB层次树（OrientedBoundingBox）[Gottschalk1996]k-dop层次树（DiscreteOrientationPolytope）[Klosowski1998][Zachmann1998]QuOSPO层次树(QuantizedOrientationSlabswithPrimaryOrientations)[He1999]凸块层次树[Ehmann2001]混合层次包围体树[Wan2001]等等基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法93基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分(a)包围球(b)AABB包围盒(c)OBB包围盒(d)6-dop包围体(e)凸包包围体包围体二维示意图基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法(a)基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法利用图形硬件对物体的二维图象采样相应的深度信息基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法95基于空间域的碰撞检测算法分类基于图象空间的碰撞检测算法Shinya等[Shinya1991]和Rossignac等[Rossignac1992]Myszkowski等[Myszkow1995]Baciu等[Baciu1997][Baciu1999]Hoff等[Hoff2001]，Kim等[Kim2002]，[Lombardo1999]，[Vassilev2001]，[Heidelb2003]，[Govindar2003]基于可编程图形硬件….基于空间域的碰撞检测算法分类基于图象空间的碰撞检测算法96粒子聚类的碰撞检测demo粒子聚类的碰撞检测demo97碰撞检测算法框架归纳出一个统一的碰撞检测算法框架video碰撞检测算法框架归纳出一个统一的碰撞检测算法框架vide98演讲完毕，谢谢观看！演讲完毕，谢谢观看！99游戏中的场景管理技术游戏中的场景管理技术作业对游戏的评价（每个人）10%小组游戏proposal(每组)10%对其他小组游戏proposal的评价（每组）10%请用OGRE实现任意一项10%三维光照场景组织光影特效（包括阴影）大程作业40%平时点名20%作业对游戏的评价（每个人）10%101游戏Quake3的场景

游戏Quake3的场景102三维游戏场景的组织和绘制三维游戏中的图形技术可分为三个方面场景的几何组织与优化着重于提高绘制效率场景的画面真实度,采用一系列特效生成技术包括高级纹理映射,过程式建模等基于真实物理定律的游戏效果模拟主要是阴影模拟和碰撞检测本次课程将着重讲解三维游戏场景的几何组织,优化管理以及在此基础上的OGRE中的复杂场景的管理三维游戏场景的组织和绘制三维游戏中的图形技术可分为三个方面103三维游戏场景的组织和绘制三维场景的组织和管理游戏场景的几何优化三维场景的快速可见性判断与消隐地形场景的绘制与漫游碰撞检测简介三维游戏场景的组织和绘制三维场景的组织和管理104基于场景图(Scenegraph)的表达和管理第一步根据游戏的需要更新场景图必要的部分这种更新是部分的,不需要从根节点遍历第二步场景图的剔除和绘制太阳系的场景图基于场景图(Scenegraph)的表达和管理第一步太阳系的105基于绘制状态的场景管理把场景物体按照绘制状态分类绘制状态集合A●砖块纹理●细节纹理●红色材质●无融合模式绘制状态集合B●砖块纹理●细节纹理●灰色材质●无融合模式绘制状态集合C●砖块纹理●凹凸纹理●红色材质●无融合模式绘制状态集合D●立方体纹理●无纹理●单色材质●加法融合模式

绘制状态集合实例基于绘制状态的场景管理把场景物体按照绘制状态分类绘制状态集合绘制状态树实例

绘制状态树实例107基于场景包围体的场景组织加速判断场景物体之间的空间关系,主要有两种方法对单个物体建立包围体,在包围体的基础上建立包围盒层次树场景剖分基于场景包围体的场景组织加速判断场景物体之间的空间关系,主要108常用的包围体技术常用的包围体技术109包围体和包围球示例球的体积比立方体大包围体和包围球示例球的体积比立方体大110OBB树的构造示意图

OBB树的构造示意图111物体的凸包围体常用的类型增量式(incremental)礼包式(gift-wrapping)分治式(divide-and-conquer)快速凸包算法(quick-hull)k-dop(discretedorientationpolytope,离散有向多面体)比上述的包围体更紧密地包围原物体,创建的层次树节点更少物体的凸包围体常用的类型1128-dop结构8-dop结构113场景绘制的几何剖分将场景中的几何物体通过层次性机制组织起来优点使用灵活,能快速剔除层次树的整个分枝注意要保持树的平衡!场景绘制的几何剖分将场景中的几何物体通过层次性机制组织起来114包围树包围树115常用的几何剖分技术BSP树

（左）场景的BSP树剖分；（右）BSP树结构示意图常用的几何剖分技术BSP树（左）场景的BSP树剖分；（右）B116BSP树的构造过程（左）一次剖分后的场景平面图；（右）一次剖分后的BSP树（左）两次剖分后的场景平面图；（右）两次剖分后的BSP树

BSP树的构造过程（左）一次剖分后的场景平面图；（右）一次117BSP算法处理四个嵌套遮挡的多边形用画家算法无法处理四个嵌套遮挡的多边形情形BSP算法处理四个嵌套遮挡的多边形用画家算法无法处理四个嵌套118四叉树

（a）场景多边形；（b）第一次剖分；（c）第二次剖分四叉树（a）场景多边形；（b）第一次剖分119八叉树（a）（b）（c）（a）初始节点；（b）第一次剖分；（c）第二次剖分八叉树（a）120景物包围体和场景剖分技术比较（左）场景包围体技术（右）场景剖分技术景物包围体和场景剖分技术比较（左）场景包围体技术（右）场景剖121景物包围体和场景剖分技术比较技术名称适用场景构建复杂度实用性二叉树尺寸不是特别大的室内建筑场景复杂大部分三维游戏引擎四叉树室外基于高度场的地形一般仅用于地形绘制八叉树大规模三维室内、外空间场景一般复杂三维游戏引擎均匀八叉树体素表示场景、分布均匀的三维场景简单少量三维游戏引擎景物包围体和场景剖分技术比较技术名称适用场景构建122景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表示方式层次物体表示层次空间表示剖分方式物体剖分场景剖分聚类方式物体的层次聚类空间的层次聚类层次细节物体层次细节空间层次细节主要作用围绕物体将空间区域区分开来围绕区域将物体区分开来代表方法包围球树OBB-树、AABB树、k-DOPS二叉树、四叉树、八叉树、均匀三维网格、kD树景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表示层次细节(LOD)技术简单取舍型LOD平滑过渡型LOD静态LOD动态LOD层次细节(LOD)技术简单取舍型LOD124LODLOD125经典的简化算法顶点删除边删除最有效!面删除基于边删除的顶点简化经典的简化算法顶点删除基于边删除的顶点简化126兔子模型的四个层次

兔子模型的四个层次127LODModelsLODModels128渐进网格和连续多分辨率绘制技术对于数据量庞大的复杂模型LOD模型只能预先产生多个间断的简化模型引起实时绘制时图形画面的跳跃为克服LOD的缺点,Huppe等人于1995年提出渐进网格技术(ProgressiveMesh)预计算简化过程中原顶点和新顶点的关系由基本网格模型逐步恢复模型细节渐进网格和连续多分辨率绘制技术对于数据量庞大的复杂模型129示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡130示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡131示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡132DemoDemo133场景的可见性判断场景的可见性判断134可见性判断算法分类可见性判断算法分类135遮挡面剔除技术遮挡面剔除技术136遮挡面剔除技术适用于人造建筑物少的室外场景代表性算法:基于阴影体技术（左）遮挡剔除之前；（右）基于阴影体的遮挡剔除遮挡面剔除技术适用于人造建筑物少的室外场景（左）遮挡剔除之前137包围球加速

（左）球A至少在一个平面之外，球B在所有平面之内，但其半径大于球心到其中一个平面的距离，球C在所有平面之后且到所有平面的距离足够大。（右）一种包围球没有被完全遮挡但包围盒被完全遮挡的情形，故物体不应被绘制

包围球加速（左）球A至少在一个平面之外，球B在所有平面之138可见性计算（适用于室内场景）可见性（Visibility）算法用于决定场景中可能可见的物体一般的：保守地指定这些物体并将他们发送到图形绘制引擎确切的可见性决定对于游戏而言是可能的，但是代价太大因此，存在平衡：在软件中进行可见性判断的时间和在硬件中绘制多余的不可见物体的代价最简单的就是绘制引擎本身自带的视域裁剪算法但是这个算法对于高度复杂性的场景并不合适，特别当很多物体位于单个象素之后比如，第一人称视角游戏中常见的建筑物具有高度的深度复杂性。可见性计算（适用于室内场景）可见性（Visibility）算139区分可见性信息Cell-to-Cell可见性告知在一个cell中的某点处是否可以看到其他的房间但是无法知道每个房间的那个部分可能是可见的，也无法知道观察者在这个房间的哪个地方可以见到另外的房间Cell-to-Region可见性可以知道某点处，其他房间的哪些部分是可见的Cell-To-Object:对于某给定的房间，告知哪些物体是可见的。Eye-To-Region可见性记录当前视点处的哪些房间的哪些部分是可见的同理，Eye-to-Cell以及Eye-To-Object区分可见性信息Cell-to-Cell可见性140基于入口(Portal)技术的可见性判断根据单元与单元之间的邻接图,通过深度遍历建立起单元与单元的入口序列基于入口(Portal)技术的可见性判断根据单元与单元之间的141基于入口结构的绘制技术分为两类精细型入口绘制方式粗略型入口绘制技术优点方便定义场景快速绘制缺点消耗大量的内存,换取效率的提高不适合室外渲染基于入口结构的绘制技术分为两类142Cell-Portal结构许多可见性算法假设单元和入口的数据结构数据结构类似于一个图：节点是房间，边是入口Portals本质的意思是两个房间的墙之间存在洞Portal形状一般是多边形两个房间之间也可有多个Portals如何建立这个数据图？Kd-trees或者BSP树用于生成cell结构以及寻找与之相关的portals自动或者手工生成建筑物最合适这种情况Cell-Portal结构许多可见性算法假设单元和入口的数143CellPortal实例Portals可以是房间的边缘（即墙壁）Graph一般保存相邻信息每个房间保留其外向的边（即portals）ABCDEFABCDEFCellPortal实例Portals可以是房间的边缘144Cell-Portal可见性跟踪观察者所在的房间然后遍历graph穷举所有可见的区域可以预处理，对每一个房间计算可能可见集合potentiallyvisibleset(PVS)Cell-to-region

可见性，或者

cell-to-object

可见性也可以在运行之间更进一步地精确获得可见集合从已知观察者的位置出发Eye-to-region

或者Eye-to-cell

可见性平衡：节省下列的时间vs.计算小的可能可见集合的代价与所在环境有关，如房间的尺寸、房间物体的个数…Cell-Portal可见性跟踪观察者所在的房间145PVS:可能可见集PVS:对于某个特定的房间，可能可以看到的房间/区域/物体/多边形一般地，保存可以看见的物体的标识号也要考虑内存的因素预处理的计算过程应该能良好地管理动态变化的物体列表用法:可见性确定–对于当前房间，绘制所有PVS中的多边形做为第一步：获得可能相关的区域，并做进一步处理PVS:可能可见集PVS:对于某个特定的房间，可能可以看到146Cell-to-CellPVSCellA在B的PVS中，当且仅当存在一根线，从B出发射到A，并且在途中与任何物体不相交隔壁房间理所当然在PVS之中IJHGACBEFDI的PVS包括:B,C,E,F,H,JCell-to-CellPVSCellA在B的PV147Stab树这个树状结构表示:当前房间的PVS一个串着的相关的portal序列在进一步的可见性处理中可以减少需要检查处理的cells/portals数目ACDEA/CC/D1C/D2C/EABCDEFDFD/FStab树这个树状结构表示:ACDEA/CC/D1C/D148Cell-to-Cell的用法大多数算法比cell-to-cell可见性算法更复杂因为它过估计–当实际上99.6%的模型应该是不可见的时候，仅排除了大约90%的模型,而更好的算法可以排除98%但是，保持cell-to-cell可见性有利于动态物体当房间中有一个移动的物体并且房间是静态的Cell-to-Cell的用法大多数算法比cell-to-c149Cell-to-Cell的缺点存在的问题:将一个房间中的所有物体都标记为可能可见，尽管只有一小部分是可能可见如果我们要列出可能可见集－意味着我们要将这个房间中的所有物体都列出来。并没有考虑到观察者的位置，无法报告观察者可能看不到的物体进一步处理可以解决这个问题Cell-to-Cell的缺点存在的问题:150Cell-To-Region可见性记录房间中某点处可能可见的某个房间的某个区域因此，只绘制这个区域中的物体关键想法视设置隔离平面（对于二维，就是隔离线):如果将左边的portal视为光源Cell-To-Region可见性记录房间中某点处可能可见151动态可见性处理PVS完全是一个预处理过程在运行时刻，只需要绘制PVS即可更进一步的优化是做进一步处理有时候由PVS指导大多数游戏不这么做一个可能的办法是观察者的位置已知,因此可以使用Eye-to-Region的可见性动态可见性处理PVS完全是一个预处理过程152Eye-to-Region(1)ViewEye-to-Region(1)View153Eye-to-Region(2)Eye-to-Region(2)154没有Cell或者Portals怎么办?很多场景并没有好的cell和portal结构场景中没有大的共面多边形去做为遮挡器或者房间的墙例如森林-你无法看到后面的场景，但是总不能设置叶子为Cell解决方案?定义一些遮挡物体，称为occluders并利用他们来剔除几何物体没有Cell或者Portals怎么办?很多场景并没有好的c155Occluders若occluder是一个多边形否则，使用物体的侧影轮廓线从视点和多边形的边构成裁剪平面也叫支撑平面：Supportingplanes所有在支撑平面内部的是不可见的Occluder自身是一个裁剪平面位于其外部的是可见的eyeoccludersupportingplanesOccluders若occluder是一个多边形eyeoc156Occluders（续）Occluders一般在预处理阶段获得选择的标准?如果它遮挡了很多物体如果大的多边形与视点很近，该方法很有效场景中的一些物体也可以融合起来形成大的occluders例如，将很多树的billboards融合occluding多边形可以任意指定，但是，每一occluder只对某一些视点区域有效问题：如果一个物体被某个occluder部分遮挡,又被另外一个部分遮挡,那么很难决定是否该物体被全部遮挡Occluders（续）Occluders一般在预处理阶段157Occluders（续）用多个occluders来隐藏一个物体是一个很有趣的问题HierarchicalZ-Buffer

方法在图像（屏幕）空间建立遮挡子需要特殊的图形硬件与软件实现张寒松的HierarchicalOcclusionMaps（层次遮挡图）将遮挡子绘制到一个纹理图中，然后将物体与纹理比较SchauflerOccluderFusion

建立一个被遮挡区域的空间数据结构Occluders（续）用多个occluders来隐藏一个物158真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形，帧率为50fps。

当遮挡面剔除关闭时，三角形绘制数目增长到17,300,帧率下降到20fps真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形159地形场景的绘制与漫游

（上左）地形的基础三角网格；（上右）高度图；

（下左）应用高度图后的地形网格；（下右）渲染后的地形图地形场景的绘制与漫游（上左）地形的基础三角网格；160游戏中的地形场景游戏中的地形场景161地形绘制基于四叉树的绘制方法利用图形硬件加速绘制模式保留模式立即模式绘制优化使用场景的层次剖分技术进行视域剔除消除对画面贡献极小的多边形地形绘制基于四叉树的绘制方法162自适应的四叉树剖分根据当前节点的误差度量判断是否需要继续剖分可能在两个相连的节点之间产生漏洞解决方法保证两个相邻节点之间最多相差1个层次保证两个相邻的边拥有相同的顶点数目自适应的四叉树剖分根据当前节点的误差度量判断是否需要继续剖分163地形绘制的优化动态层次细节算法缺点层次之间切换会产生跳跃感几何变形法具有光滑过渡的视觉效果地形绘制的优化动态层次细节算法164地形绘制中的难题存储量大,内存消耗太多解决的方法细节纹理细节纹理的拼接具有很大的挑战性!地形绘制中的难题存储量大,内存消耗太多165利用细节纹理技术的地形绘制实例

利用细节纹理技术的地形绘制实例166OGRE的场景树OGRE的场景树167OGRE中的场景管理在OGRE中场景管理器的类型有四种：ST_GENERIC普通场景ST_EXTERIOR_CLOSE室外封闭场景ST_EXTERIOR_FAR室外无限场景ST_INTERIOR 室内场景OGRE中的场景管理在OGRE中场景管理器的类型有四种：168室内场景首先读入地图包。代码如下BspApplication(){//LoadQuake3locationsfromafileConfigFilecf;cf.load("quake3settings.cfg");mQuakePk3=cf.getSetting("Pak0Location");mQuakeLevel=cf.getSetting("Map");}室内场景首先读入地图包。代码如下169选择正确的场景管理器

voidchooseSceneManager(void){mSceneMgr=mRoot->getSceneManager(ST_INTERIOR);}选择正确的场景管理器voidchooseSceneMa170最后是创建场景

voidcreateScene(void){//LoadworldgeometrymSceneMgr->setWorldGeometry(mQuakeLevel);//modifycameraforcloseworkmCamera->setNearClipDistance(4);mCamera->setFarClipDistance(4000);//Alsochangeposition,andsetQuake-typeorientation//GetrandomplayerstartpointViewPointvp=mSceneMgr->getSuggestedViewpoint(true);mCamera->setPosition(vp.position);mCamera->pitch(90);//QuakeusesX/Yhorizon,ZupmCamera->rotate(vp.orientation);//Don'tyawalongvariableaxis,causesleaningmCamera->setFixedYawAxis(true,Vector3::UNIT_Z);}最后是创建场景voidcreateScene(void)171【培训课件】游戏中的场景管理技术172【培训课件】游戏中的场景管理技术173室外场景OGRE在其引擎提供的Plugin_OctreeSceneManager.dll插件中提供了通过八叉树算法实现的ST_EXTERIOR_CLOSE室外封闭场景管理器。室外场景OGRE在其引擎提供的Plugin_OctreeSc174室外场景

室外场景175室外场景漫游

首先需要选择室外场景管理器，代码如下：virtualvoidchooseSceneManager(void){//GettheSceneManager,inthiscaseagenericonemSceneMgr=mRoot->getSceneManager(ST_EXTERIOR_CLOSE);}室外场景漫游首先需要选择室外场景管理器，代码如下：176室外场景漫游选择好室外场景管理器后，通过该场景管理器创建场景就可以了。voidcreateScene(void){//SetambientlightmSceneMgr->setAmbientLight(ColourValue(0.5,0.5,0.5));//CreatealightLight*l=mSceneMgr->createLight("MainLight");//Acceptdefaultsettings:pointlight,whitediffuse,justsetposition//NBIcouldattachthelighttoaSceneNodeifIwantedittomoveautomaticallywith//otherobjects,butIdon'tl->setPosition(20,80,50);mSceneMgr->setWorldGeometry("terrain.cfg");mSceneMgr->setFog(FOG_EXP2,ColourValue::White,.008,0,250);

mRoot->showDebugOverlay(true);}室外场景漫游选择好室外场景管理器后，通过该场景管理器创建场景177【培训课件】游戏中的场景管理技术178【培训课件】游戏中的场景管理技术179White&BlackWhite&Black180碰撞检测碰撞检测问题是机器人、动画仿真、虚拟现实等领域不可回避的问题基本任务确定两个或多个物体彼此之间是否发生接触或穿透。起源 早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。碰撞检测碰撞检测问题181碰撞检测算法分类从两个角度对碰撞检测算法进行分类从时间域的角度来分从空间域的角度来分碰撞检测算法分类从两个角度对碰撞检测算法进行分类182基于时间域的碰撞检测算法分类

分为静态、离散和连续的碰撞检测算法静态碰撞检测算法 静止状态下进行碰撞检测[Dobkin1985][Agarwal1991][Chazelle1989]离散碰撞检测算法在每一时间的离散点上进行碰撞检测是研究的重点和热点[Lin1998][Jiménez2001]

基于时间域的碰撞检测算法分类分为静态、离散和连续的碰撞检测183基于时间域的碰撞检测算法分类离散碰撞检测算法存在问题存在刺穿现象遗漏应该发生的碰撞连续碰撞检测算法连续的时间间隔内进行碰撞检