lecture5游戏中的场景管理技术

1、游戏中的场景管理技术游戏中的场景管理技术三维游戏场景的组织和绘制o 三维游戏中的图形技术可分为三个方面n场景的几何组织与优化o 着重于提高绘制效率n场景的画面真实度，采用一系列特效生成技术o 包括高级纹理映射，过程式建模等n基于真实物理定律的游戏效果模拟o 主要是阴影模拟和碰撞检测o 本次课程将着重讲解三维游戏场景的几何组织，优化管理以及在此基础上的OGRE中的复杂场景的管理三维游戏场景的组织和绘制o 三维场景的组织和管理o 游戏场景的几何优化o 三维场景的快速可见性判断与消隐o 地形场景的绘制与漫游o 碰撞检测简介游戏Quake3的场景 基于场景图(Scene graph)的表达和管理o 第

2、一步n根据游戏的需要更新场景图必要的部分n 这种更新是部分的，不需要从根节点遍历o 第二步n场景图的剔除和绘制太阳系的场景图基于绘制状态的场景管理o 把场景物体按照绘制状态分类绘制状态集合A 砖块纹理 细节纹理 红色材质 无融合模式绘制状态集合B 砖块纹理 细节纹理 灰色材质 无融合模式绘制状态集合C 砖块纹理 凹凸纹理 红色材质 无融合模式绘制状态集合D 立方体纹理 无纹理 单色材质 加法融合模式 绘制状态集合实例绘制状态集合实例 绘制状态树实例 砖块纹理 细节纹理 红色材质 无融合模式 灰色材质 无融合模式 凹凸纹理 红色材质 无融合模式 立方体纹理 无纹理 单色材质 加法融合模式 基于景

3、物包围体的场景组织o 加速判断场景物体之间的空间关系，主要有两种方法n 对单个物体建立包围体，在包围体的基础上建立包围盒层次树n 场景剖分：真正与某个物体发生关系的场景物体有限，将物体在场景中的分布结构组织起来，从而消除大量无用的判断。常用的包围体技术 （1）包围球 （2）AABB （3）OBB （4）平行六面包围体 （5）k-Dop 轴平行包围盒有向包围盒包围体和包围球示例球的体积比立方体大球的体积比立方体大 OBB树的构造示意图 物体的凸包围体o 常用的类型n 增量式(incremental)n 礼包式(gift-wrapping)n 分治式(divide-and-conquer)n 快速

4、凸包算法(quick-hull)n k-dop(discreted orientation polytope,离散有向多面体)o 比上述的包围体更紧密地包围原物体,创建的层次树节点更少8-dop结构场景绘制的几何剖分技术o将场景中的几何物体通过层次性机制组织起来n优点n使用灵活，能快速剔除层次树的整个分枝o注意注意n要保持树的平衡要保持树的平衡!常用的几何剖分技术oBSP树(Binary Space Partition) （左）场景的BSP树剖分；（右）BSP树结构示意图 BSP树的构造过程 （左）一次剖分后的场景平面图；（右）一次剖分后的BSP树 （左）两次剖分后的场景平面图；（右）两次剖分

5、后的BSP树 BSP树的深度遍历和广度遍历o 不考虑相机位置n 广度遍历o 考虑相机位置n 深度遍历o 相机在左侧 （先遍历右子树-再遍历左子树-最后处理本节点数据）o 相机在右侧 （先遍历左子树-再遍历右子树-最后处理本节点数据）BSP算法处理四个嵌套遮挡的多边形o 用画家算法无法处理四个嵌套遮挡的多边形情形四叉树 （a）场景多边形； （b）第一次剖分； （c）第二次剖分 八叉树 （a） （b） （c）（a）初始节点； （b）第一次剖分； （c）第二次剖分景物包围体和场景剖分技术比较技 术 名 称适 用 场 景构建复杂度实 用 性二叉树尺寸不是特别大的室内建筑场景复杂大部分三维游戏引擎四叉树

6、室外基于高度场的地形一般仅用于地形绘制八叉树大规模三维室内、外空间场景一般复杂三维游戏引擎均匀八叉树体素表示场景、分布均匀的三维场景简单少量三维游戏引擎景物包围体和场景剖分技术比较场景包围体技术场景剖分技术表 示 方 式层次物体表示层次空间表示剖 分 方 式物体剖分场景剖分聚 类 方 式物体的层次聚类空间的层次聚类层 次 细 节物体层次细节空间层次细节主 要 作 用围绕物体将空间区域区分开来围绕区域将物体区分开来代 表 方 法包围球树OBB-树、AABB树、k-DOPS二叉树、四叉树、八叉树、均匀三维网格、kD树景物包围体和场景剖分技术比较（左）景物包围体技术（右）场景剖分技术 三维游戏场景的

7、组织和绘制o 三维场景的组织和管理o 游戏场景的几何优化o 三维场景的快速可见性判断与消隐o 地形场景的绘制与漫游o 碰撞检测简介o 距离当前观察视点越远的物体，其在成像平面上的投影面积就越小，因而对远处的物体在绘制阶段就可以用较少的等效绘制元素来表现它。o 细节层次的基本原理利用透视投影的特性。层次细节(LOD)技术o 简单取舍型LOD：计算物体投影在屏幕上的像素，如果小于某个预置则不绘制。缺点：没有减少模型的细节，要不绘制原精度模型，要不绘制空模型；当相机在场景中运动时，模型出现或消失容易出现跳跃感。o 平滑过渡型LOD：对于不绘制的物体，通过设置透明度的方式逐渐淡出视野。物体尺寸和透明度

8、建立线性函数。o 静态LOD：真正减少物体多边形的数目，设计不同物体尺寸对应的不同精度的版本。可以通过雾化避免跳跃现象。o 动态LOD：场景中根据相机的位置和物体的重要性动态的简化网格。（对采用的算法要求较高）（具体采用哪种方法根据帧率而定）LOD动态LOD中的经典简化算法o 顶点删除o 边删除n最有效!n如何选择被删除的边n另一种方法：可以通过定点合并实现o 面删除基于边删除的顶点简化 兔子模型的四个层次 LOD Models示例: SpeedTree的LOD过渡示例:SpeedTree的LOD过渡渐进网格和连续多分辨率绘制技术o 对于数据量庞大的复杂模型n LOD模型只能预先产生多个间断的

9、简化模型n 引起实时绘制时图形画面的跳跃o 为克服LOD的缺点，Huppe等人1995年提出n 渐进网格技术(Progressive Mesh)o 预计算简化过程中原顶点和新顶点的关系，顶点分裂方法来恢复模型简化时所删除的信息。o 由基本网格模型逐步恢复模型细节场景的可见性判断可见性判断算法分类场景剖分技术多边形的法线方向背向相机方向则不可见视域四棱锥自定义裁剪面利用像素的深度信息遮挡面剔除技术遮挡面剔除技术o 适用于人造建筑物少的室外场景o 代表性算法:基于阴影体技术（左）遮挡剔除之前；（右）基于阴影体的遮挡剔除 包围球加速 （左）球A 至少在一个平面之外，球B在所有平面之内，但其半径大于球

10、心到其中一个平面的距离，球C在所有平面之后且到所有平面的距离足够大。（右）一种包围球没有被完全遮挡但包围盒被完全遮挡的情形，故物体不应被绘制 真实的游戏场景当打开遮挡面剔除时，仅需绘制7,000个三角形，帧率为50fps。当遮挡面剔除关闭时，三角形绘制数目增长到17,300, 帧率下降到20 fps 地形场景的绘制与漫游 （上左）地形的基础三角网格； （上右）高度图；（下左）应用高度图后的地形网格； （下右）渲染后的地形图 室外地形表示：高度图o 室外地形表示的最初想法来自于地形的航拍图片。在游戏前，事实上这种航拍数据已经在GIS领域有了应用。其基本原理即是存储抽样点的高度数据，以大量离散的抽

11、样点高度趋近连续的地形。室外地形的表示o 高度图一般是灰度图，其每一个像素都代表一个采样点的高度，一般0（黑色）代表最低点，255（白色）代表最高点，地形的每一个顶点都来自于高度图中的像素数据。实现高度图室外地形o 第一步，读取高度图的数据，并将高度数据缓存入一个数组中。o 第二步，通过这个数组来生成室外地形的Vertex Buffer和Index Buffer。o 第三步，渲染！o 最后，别忘了删掉这个临时数组。实现高度图地形o 而在高度图生成的地形上蒙上与之相配的地形纹理，就构成了可以以假乱真的高度图室外地形。不足o 绘制速度很慢o 原因：一次渲染的顶点、索引太多，再高级的的显卡也会很慢。

12、游戏中的地形场景地形绘制o 基于四叉树的绘制方法n 利用图形硬件加速n 绘制模式o 保留模式o 立即模式o 绘制优化n 使用场景的层次剖分技术进行视域剔除n 消除对画面贡献极小的多边形地形绘制的优化o 动态层次细节算法n 缺点n 层次之间切换会产生跳跃感o 几何变形法n 具有光滑过渡的视觉效果地形绘制中的难题o 存储量大，内存消耗太多o 解决的方法n 细节纹理：小尺寸，多次重复拼接实现。o 细节纹理的拼接具有很大的挑战性!利用细节纹理技术的地形绘制实例 地形绘制总结一个例子创建地形全局配置创建地形分组创建默认的地形分块属性 创建地形分块配置需要配置一些关于地形绘制需要的东西，叫做： Ogre

13、Terrain component。在工程文件属性里分别选择debug和realese，在Configuration Properties - Linker - Input里添加OgreTerrain_d.lib和OgreTerrain.lib。绘制重点纹理高度图创建createScene函数设置相机的位置和方向voidvoid createScenecreateScene()() mCameramCamera-setPositionsetPosition( (OgreOgre:Vector3Vector3(1683, 50, 2116);(1683, 50, 2116); mCameramC

14、amera-lookAtlookAt( (OgreOgre:Vector3Vector3(1963, 50, 1660);(1963, 50, 1660); mCameramCamera-setNearClipDistancesetNearClipDistance(0.1);(0.1); mCameramCamera-setFarClipDistancesetFarClipDistance(50000);(50000); ifif( (mRootmRoot-getRenderSystemgetRenderSystem()-()-getCapabilitiesgetCapabilities()-

15、()- hasCapabilityhasCapability( (OgreOgre:RSC_INFINITE_FAR_PLANERSC_INFINITE_FAR_PLANE) mCameramCamera-setFarClipDistancesetFarClipDistance(0); (0); OgreOgre:MaterialManagerMaterialManager:getSingletongetSingleton().().setDefaultTextureFilteringsetDefaultTextureFiltering( (OgreOgre:TFO_ANISOTROPTFO_

16、ANISOTROPICIC); ); OgreOgre:MaterialManagerMaterialManager:getSingletongetSingleton().().setDefaultAnisotropysetDefaultAnisotropy(7);(7); OgreOgre:Vector3Vector3 lightdirlightdir(0.55, -0.3, 0.75);(0.55, -0.3, 0.75);lightdirlightdir. .normalisenormalise();();OgreOgre:LightLight* *lightlight = =mScen

17、eMgrmSceneMgr-createLightcreateLight( (tstLighttstLight););lightlight-setTypesetType( (OgreOgre:LightLight:LT_DIRECTIONALLT_DIRECTIONAL););lightlight-setDirectionsetDirection( (lightdirlightdir););lightlight-setDiffuseColoursetDiffuseColour( (OgreOgre:ColourValueColourValue:WhiteWhite););lightlight-

18、setSpecularColoursetSpecularColour( (OgreOgre:ColourValueColourValue(0.4, 0.4, 0.4);(0.4, 0.4, 0.4);mSceneMgrmSceneMgr-setAmbientLightsetAmbientLight( (OgreOgre:ColourValueColourValue(0.2, 0.2, 0.2);(0.2, 0.2, 0.2);设置光源引入地形相关的头文件#include #includeOgre:TerrainGlobalOptions*mTerrainGlobals;Ogre:Terrain

19、Group*mTerrainGroup;bool mTerrainsImported;void defineTerrain(long x, long y);void initBlendMaps(Ogre:Terrain*terrain);void configureTerrainDefaults(Ogre:Light*light); 添加成员变量及成员函数voidvoid configureTerrainDefaultsconfigureTerrainDefaults( (OgreOgre:LightLight* *lightlight) ) mTerrainGlobalsmTerrainGl

20、obals-setMaxPixelErrorsetMaxPixelError(8);(8);mTerrainGlobalsmTerrainGlobals-setCompositeMapDistancesetCompositeMapDistance(3000);(3000);mTerrainGlobalsmTerrainGlobals-setLightMapDirectionsetLightMapDirection( (lightlight-getDerivedDirectiongetDerivedDirection();();mTerrainGlobalsmTerrainGlobals-set

21、CompositeMapAmbientsetCompositeMapAmbient( (mSceneMgrmSceneMgr-getAmbientLightgetAmbientLight();();mTerrainGlobalsmTerrainGlobals-setCompositeMapDiffusesetCompositeMapDiffuse( (lightlight-getDiffuseColourgetDiffuseColour();(); 在地形的渲染中，Ogre提供了一种组合贴图的渲染，就是在较远的地方使用一种贴图混合简单光影的方式来代替实际的纹理，这有很多应用，如可以在较远的地方

22、不使用精细的纹理生成，提高效率；这样可以使用这个特性实现游戏中照亮与黑暗的效果。地形的渲染Configuring the Terrain/配置地形需要如下的一些private类型的类成员变量及成员函数Ogre:TerrainGlobalOptions*mTerrainGlobals;Ogre:TerrainGroup*mTerrainGroup;bool mTerrainsImported; void defineTerrain(long x, long y);void initBlendMaps(Ogre:Terrain*terrain);void configureTerrainDefau

23、lts(Ogre:Light*light);需要设置TerrainGlobalOptions，这是一个表示地形的总体特性的类，继续在createScene函数中添加如下代码：mTerrainGlobals = OGRE_NEW Ogre:TerrainGlobalOptions();/创建的TerrainGroup对象mTerrainGroup = OGRE_NEW Ogre:TerrainGroup( mSceneMgr, Ogre:Terrain:ALIGN_X_Z, 513, 12000.0); mTerrainGroup-setFilenameConvention(Ogre:Strin

24、g(terrain), Ogre:String(dat); mTerrainGroup-setOrigin(Ogre:Vector3:ZERO);/加载地图for (longx = 0;x = 0; +x) for (longy = 0;y loadAllTerrains(true);TerrainGlobalOptions是一个表示地形的总体特征的类，它可以设置地形的一些特征，MaxPixelError决定了地形的精度。在地形的渲染中，Ogre提供了一种组合贴图的渲染，就是在较远的地方使用一种贴图混合简单光影的方式来代替实际的纹理，这有很多应用，如这样可以在较远的地方不使用精细的纹理生成，提

25、高效率；这样可以使用这个特性实现游戏中照亮与黑暗的效果。Configuring the Terrain/配置地形 完成了上面这些代码，我们还需要往configureTerrainDefaults函数体中继续添加如下代码：Ogre:Terrain:ImportData& importData = mTerrainGroup-getDefaultImportSettings(); importData.terrainSize = 513; importData.worldSize = 12000.0; importData.inputScale = 600; importData.minB

26、atchSize = 33; importData.maxBatchSize = 65;importData.layerList.resize(3);importData.layerList0.worldSize = 100; importData.layerList0.textureNames.push_back( dirt_grayrocky_diffusespecular.dds); importData.layerList0.textureNames.push_back( dirt_grayrocky_normalheight.dds); importData.layerList1.w

27、orldSize = 30; importData.layerList1.textureNames.push_back( grass_green-01_diffusespecular.dds); importData.layerList1.textureNames.push_back( grass_green-01_normalheight.dds); importData.layerList2.worldSize = 200; importData.layerList2.textureNames.push_back( growth_weirdfungus-03_diffusespecular

28、.dds); importData.layerList2.textureNames.push_back( growth_weirdfungus-03_normalheight.dds);纹理混合initBlendMaps函数的实现混合的原理是这样的：对于每一个纹理层，都有一个保存每个像素的alpha混合的值，可以通过Ogre:TerrainLayerBlendMap* blendMap0 = terrain-getLayerBlendMap(1);这样的方式来获取第1层的这个混合数据，初始情况下都是0。即默认情况下第1层对第0层的混合是0，那样你就只能看到0层，可以通过修改这个数据来直接修改混

29、合方式，这就像两张图像做混合，而每张混合图像代表了整个这个地形实例的表面图片，为了得到这个图像的边长，可以使用terrain-getLayerBlendMapSize();还可以使用blendMap0-convertImageToTerrainSpace(x,y, &tx, &ty);来得到混合图像空间上(x,y)的那个像素对应的地形实例空间上的坐标，我们修改了混合值之后，还需要使用blendMap0-dirty();blendMap0-update();来更新。o 详细代码参见：o /tikiwiki/tiki-index.php?pa

30、ge=Basic+Tutorial+3&structure=TutorialsValse 2016 o 亮风台专注于AR，总部上海。o 大疆科技主要是无人机视觉跟踪，总部深圳。 o 新成立两个月的驭势科技的吴甘沙以前是英特尔中国研究院院长，演讲非常有水平，公司宣传单说送北京户口。 o 通甲优博聚焦在无人机影像方面，但是没有demo和影像资料。老总甚至给出了只要你够牛就送别墅的许诺，公司在成都。 o simple eye目前主要做人脸相关的视觉应用。负责人是一名上海交大的在读博士武俊敏，他从大三就开始加入，现在已经是该实验室负责人。 o 微软在image caption，video ca

31、ption/comment等方面的研究很吸引人。o 搜狗，交互方面很吸引人。国内计算机视觉的企业国内计算机视觉的企业o 格灵深瞳主要做智能安防监控、智能交通等，最近和北理工以及驭势科技一起搞辅助驾驶。o 三星公司主要做AR，全景相机等。碰撞检测 o 碰撞检测问题n是机器人、动画仿真、虚拟现实等领域不可回避的问题o 基本任务n确定两个或多个物体彼此之间是否发生接触或穿透。o 起源n早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。基于空间域的碰撞检测算法分类o 基于物体空间的碰撞检测算法o 基于图像空间的碰撞检测算法基于

32、空间域的碰撞检测算法分类 o 基于物体空间的碰撞检测算法n 采用一般表示模型的碰撞检测算法 n 采用空间结构的碰撞检测算法 基于空间域的碰撞检测算法分类o 基于物体空间的碰撞检测算法n采用一般表示模型的碰撞检测算法o多边形表示模型n 多边形集合，结构化表示模型o非多边形表示模型n CSG表示模型，隐函数曲面，参数曲面，体表示模型 多边形表示模型 非多边形表示模型 结构化表示模型 多边形集合 CSG 表示模型 隐函数曲面 参数曲面 几何模型 体表示模型 基于空间域的碰撞检测算法分类o 基于物体空间的碰撞检测算法n 采用一般表示模型的碰撞检测算法o 面向多边形表示模型的碰撞检测算法n Hubbar

33、d 1995Gottschalk 1996 Klosowski 1998Zachmann 1998 o 面向凸体的碰撞检测算法基于空间域的碰撞检测算法分类o 基于物体空间的碰撞检测算法n 面向凸体的碰撞检测算法o 基于特征的碰撞检测算法n Lin-Canny的“最邻近特征算法”Lin 1991, Lin1993 n Lin 1995, Cohen 1995, Chung 1996, Mirtich 1998, Ehmann 2000, Ehmann 2001 o 基于单纯形（Simplex）的碰撞检测算法 n Gilbert、Johnson和Keerthi Gilbert 1988Gilbert 1990提出的GJK算法 n Cameron 1997Bergen 1999 基于空间域的碰撞检测算法分类o基于物体空间的碰撞检测算法n 采用一般表示模型的碰撞检测算法o面向CSG表示模型n Zeiller 1993Su 1996Poutain 2001 o面向隐函数曲面表示n Farouki 1989Miller 1991Shene 1991 o面向参数曲面表示n 非均匀有理B样条曲线（NURBS） n Turnbull 1998 o体表示模型