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

游戏中的场景管理技术作业◦对游戏的评价（每个人）10%◦小组游戏proposal(每组)10%◦对其他小组游戏proposal的评价（每组）10%◦请用OGRE实现任意一项10%三维光照场景组织光影特效（包括阴影）◦大程作业40%◦平时点名20%游戏Quake3的场景三维游戏场景的组织和绘制三维游戏中的图形技术可分为三个方面◦场景的几何组织与优化着重于提高绘制效率◦场景的画面真实度,采用一系列特效生成技术包括高级纹理映射,过程式建模等◦基于真实物理定律的游戏效果模拟主要是阴影模拟和碰撞检测本次课程将着重讲解三维游戏场景的几何组织,优化管理以及在此基础上的OGRE中的复杂场景的管理三维游戏场景的组织和绘制三维场景的组织和管理游戏场景的几何优化三维场景的快速可见性判断与消隐地形场景的绘制与漫游碰撞检测简介基于场景图(Scenegraph)的表达和管理第一步◦根据游戏的需要更新场景图必要的部分◦这种更新是部分的,不需要从根节点遍历第二步◦场景图的剔除和绘制星旋转行星A旋转卫星A卫星B行星B旋转卫星C卫星D太阳系的场景图基于绘制状态的场景管理把场景物体按照绘制状态分类绘制状态集合A●砖块纹理●细节纹理●红色材质●无融合模式绘制状态集合B●砖块纹理●细节纹理●灰色材质●无融合模式绘制状态集合C●砖块纹理●凹凸纹理●红色材质●无融合模式绘制状态集合D●立方体纹理●无纹理●单色材质●加法融合模式绘制状态集合实例绘制状态树实例砖块纹理细节纹理红色材质无融合模式灰色材质无融合模式凹凸纹理红色材质无融合模式立方体纹理无纹理单色材质加法融合模式基于场景包围体的场景组织加速判断场景物体之间的空间关系,主要有两种方法◦对单个物体建立包围体,在包围体的基础上建立包围盒层次树◦场景剖分常用的包围体技术（1）包围球（2）AABB包围盒（3）OBB包围盒（4）平行六面包围体（5）k对平行面包围体包围体和包围球示例球的体积比立方体大OBB树的构造示意图物体的凸包围体常用的类型◦增量式(incremental)◦礼包式(gift-wrapping)◦分治式(divide-and-conquer)◦快速凸包算法(quick-hull)◦k-dop(discretedorientationpolytope,离散有向多面体)比上述的包围体更紧密地包围原物体,创建的层次树节点更少8-dop结构场景绘制的几何剖分将场景中的几何物体通过层次性机制组织起来◦优点使用灵活,能快速剔除层次树的整个分枝注意◦要保持树的平衡!包围树常用的几何剖分技术BSP树ABCDEFP1P2P3P4P5P1P2P5AP3FEDP4CB（左）场景的BSP树剖分；（右）BSP树结构示意图BSP树的构造过程（左）一次剖分后的场景平面图；（右）一次剖分后的BSP树（左）两次剖分后的场景平面图；（右）两次剖分后的BSP树BSP算法处理四个嵌套遮挡的多边形用画家算法无法处理四个嵌套遮挡的多边形情形四叉树（a）场景多边形；（b）第一次剖分；（c）第二次剖分八叉树（a）（b）（c）（a）初始节点；（b）第一次剖分；（c）第二次剖分景物包围体和场景剖分技术比较（左）场景包围体技术（右）场景剖分技术景物包围体和场景剖分技术比较技术名称适用场景构建复杂度实用性二叉树尺寸不是特别大的室内建筑场景复杂大部分三维游戏引擎四叉树室外基于高度场的地形一般仅用于地形绘制八叉树大规模三维室内、外空间场景一般复杂三维游戏引擎均匀八叉树体素表示场景、分布均匀的三维场景简单少量三维游戏引擎景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表示方式层次物体表示层次空间表示剖分方式物体剖分场景剖分聚类方式物体的层次聚类空间的层次聚类层次细节物体层次细节空间层次细节主要作用围绕物体将空间区域区分开来围绕区域将物体区分开来代表方法包围球树OBB-树、AABB树、k-DOPS二叉树、四叉树、八叉树、均匀三维网格、kD树层次细节(LOD)技术简单取舍型LOD平滑过渡型LOD静态LOD动态LODLOD经典的简化算法顶点删除边删除◦最有效!面删除VAVBVC基于边删除的顶点简化兔子模型的四个层次LODModels渐进网格和连续多分辨率绘制技术对于数据量庞大的复杂模型◦LOD模型只能预先产生多个间断的简化模型◦引起实时绘制时图形画面的跳跃为克服LOD的缺点,Huppe等人于1995年提出◦渐进网格技术(ProgressiveMesh)预计算简化过程中原顶点和新顶点的关系由基本网格模型逐步恢复模型细节示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡示例:SpeedTree的LOD过渡Demo场景的可见性判断可见性判断算法分类物体层：场景聚类技术二叉树和八叉树入口技术潜在可见集顶点层：顶点剔除技术背面剔除视域剔除裁剪面剔除像素层：图像空间排序深度缓冲消隐层次缓冲消隐时空连贯性单物体分块遮挡面剔除技术遮挡面剔除技术适用于人造建筑物少的室外场景代表性算法:基于阴影体技术场景物体基于阴影体的遮挡剔除（左）遮挡剔除之前；（右）基于阴影体的遮挡剔除包围球加速（左）球A至少在一个平面之外，球B在所有平面之内，但其半径大于球心到其中一个平面的距离，球C在所有平面之后且到所有平面的距离足够大。（右）一种包围球没有被完全遮挡但包围盒被完全遮挡的情形，故物体不应被绘制可见性计算（适用于室内场景）可见性（Visibility）算法用于决定场景中可能可见的物体◦一般的：保守地指定这些物体并将他们发送到图形绘制引擎◦确切的可见性决定对于游戏而言是可能的，但是代价太大◦因此，存在平衡：在软件中进行可见性判断的时间和在硬件中绘制多余的不可见物体的代价最简单的就是绘制引擎本身自带的视域裁剪算法◦但是这个算法对于高度复杂性的场景并不合适，特别当很多物体位于单个象素之后比如，第一人称视角游戏中常见的建筑物具有高度的深度复杂性。区分可见性信息Cell-to-Cell可见性◦告知在一个cell中的某点处是否可以看到其他的房间◦但是无法知道每个房间的那个部分可能是可见的，也无法知道观察者在这个房间的哪个地方可以见到另外的房间Cell-to-Region可见性◦可以知道某点处，其他房间的哪些部分是可见的◦Cell-To-Object:对于某给定的房间，告知哪些物体是可见的。Eye-To-Region可见性◦记录当前视点处的哪些房间的哪些部分是可见的◦同理，Eye-to-Cell以及Eye-To-Object基于入口(Portal)技术的可见性判断场景房间之间的连接关系根据单元与单元之间的邻接图,通过深度遍历建立起单元与单元的入口序列基于入口结构的绘制技术分为两类◦精细型入口绘制方式◦粗略型入口绘制技术优点◦方便定义场景◦快速绘制缺点◦消耗大量的内存,换取效率的提高◦不适合室外渲染Cell-Portal结构许多可见性算法假设单元和入口的数据结构◦数据结构类似于一个图：节点是房间，边是入口◦Portals本质的意思是两个房间的墙之间存在洞Portal形状一般是多边形两个房间之间也可有多个Portals如何建立这个数据图？◦Kd-trees或者BSP树用于生成cell结构以及寻找与之相关的portals◦自动或者手工生成建筑物最合适这种情况CellPortal实例Portals可以是房间的边缘（即墙壁）Graph一般保存相邻信息◦每个房间保留其外向的边（即portals）ABCDEFABCDEFCell-Portal可见性跟踪观察者所在的房间然后遍历graph穷举所有可见的区域◦可以预处理，对每一个房间计算可能可见集合potentiallyvisibleset(PVS)Cell-to-region可见性，或者cell-to-object可见性◦也可以在运行之间更进一步地精确获得可见集合从已知观察者的位置出发Eye-to-region或者Eye-to-cell可见性◦平衡：节省下列的时间vs.计算小的可能可见集合的代价与所在环境有关，如房间的尺寸、房间物体的个数…PVS:可能可见集PVS:对于某个特定的房间，可能可以看到的房间/区域/物体/多边形◦一般地，保存可以看见的物体的标识号◦也要考虑内存的因素预处理的计算过程◦应该能良好地管理动态变化的物体列表用法:◦可见性确定–对于当前房间，绘制所有PVS中的多边形◦做为第一步：获得可能相关的区域，并做进一步处理Cell-to-CellPVSCellA在B的PVS中，当且仅当存在一根线，从B出发射到A，并且在途中与任何物体不相交◦隔壁房间理所当然在PVS之中IJHGACBEFDI的PVS包括:B,C,E,F,H,JStab树这个树状结构表示:◦当前房间的PVS◦一个串着的相关的portal序列在进一步的可见性处理中◦可以减少需要检查处理的cells/portals数目ACDEA/CC/D1C/D2C/EABCDEFDFD/FCell-to-Cell的用法大多数算法比cell-to-cell可见性算法更复杂◦因为它过估计–当实际上99.6%的模型应该是不可见的时候，仅排除了大约90%的模型,而更好的算法可以排除98%但是，保持cell-to-cell可见性有利于动态物体◦当房间中有一个移动的物体并且房间是静态的Cell-to-Cell的缺点存在的问题:◦将一个房间中的所有物体都标记为可能可见，尽管只有一小部分是可能可见如果我们要列出可能可见集－意味着我们要将这个房间中的所有物体都列出来。◦并没有考虑到观察者的位置，无法报告观察者可能看不到的物体进一步处理可以解决这个问题Cell-To-Region可见性记录房间中某点处可能可见的某个房间的某个区域◦因此，只绘制这个区域中的物体关键想法视设置隔离平面（对于二维，就是隔离线):如果将左边的portal视为光源动态可见性处理PVS完全是一个预处理过程◦在运行时刻，只需要绘制PVS即可更进一步的优化是做进一步处理◦有时候由PVS指导◦大多数游戏不这么做一个可能的办法是观察者的位置已知,因此可以使用Eye-to-Region的可见性Eye-to-Region(1)ViewEye-to-Region(2)没有Cell或者Portals怎么办?很多场景并没有好的cell和portal结构◦场景中没有大的共面多边形去做为遮挡器或者房间的墙◦例如森林-你无法看到后面的场景，但是总不能设置叶子为Cell解决方案?◦定义一些遮挡物体，称为occluders并利用他们来剔除几何物体Occluders若occluder是一个多边形◦否则，使用物体的侧影轮廓线从视点和多边形的边构成裁剪平面◦也叫支撑平面：Supportingplanes所有在支撑平面内部的是不可见的◦Occluder自身是一个裁剪平面◦位于其外部的是可见的eyeoccludersupportingplanesOccluders（续）Occluders一般在预处理阶段获得选择的标准?◦如果它遮挡了很多物体如果大的多边形与视点很近，该方法很有效场景中的一些物体也可以融合起来形成大的occluders◦例如，将很多树的billboards融合◦occluding多边形可以任意指定，但是，每一occluder只对某一些视点区域有效问题：如果一个物体被某个occluder部分遮挡,又被另外一个部分遮挡,那么很难决定是否该物体被全部遮挡Occluders（续）用多个occluders来隐藏一个物体是一个很有趣的问题◦HierarchicalZ-Buffer方法在图像（屏幕）空间建立遮挡子需要特殊的图形硬件与软件实现◦张寒松的HierarchicalOcclusionMaps（层次遮挡图）将遮挡子绘制到一个纹理图中，然后将物体与纹理比较◦SchauflerOccluderFusion建立一个被遮挡区域的空间数据结构真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形，帧