chap7游戏中的场景管理技术

2020-03-01 202浏览

  • 1.回顾 计算机图形学：利用计算机研究图形 的表示、生成、处理、显示的学科。  几何造型技术  基本图元的生成算法  二维变换、三维变换和三维观察  真实感图形绘制
  • 2.Chap 7 游戏中的场景管理 技术
  • 3.三维游戏场景的组织和绘制 三维游戏中的图形技术可分为三个方面 ◦ 场景的几何组织与优化  着重于提高绘制效率 ◦ 场景的画面真实度 , 采用一系列特效生成技术  包括高级纹理映射 , 过程式建模等 ◦ 基于真实物理定律的游戏效果模拟  主要是阴影模拟和碰撞检测
  • 4.游戏 Quake3 的场景
  • 5.游戏中的场景管理技术 三维场景的组织和管理 三维场景的几何优化 三维场景的快速可见性判断 LOD 加速绘制技术
  • 6.三维场景的组织和管理 基于场景图 (Scenegraph) 的表达和管理  场景图是一种将场景中的各种数据以图的形式组织 在一起的场景数据管理方法。  它一般用 k 叉树表示，树的每个节点都可以有 0 ～ n 个子节点。其根节点一般是一个逻辑节点， 它代表着整个场景，根节点下的每个节点则存储着 场景中物体的数据结构。
  • 7.三维场景的组织和管理  第一步 ◦ 根据游戏的需要 更新场景图必要 的部分 ◦ 这种更新是部 分的 , 不需要从 根节点遍历  第二步 ◦ 场景图的剔除和 绘制 太阳系的场景图
  • 8.三维场景的组织和管理 基于绘制状态的场景管理  在复杂场景中不仅要对对象的集合、空间信息进行 有效管理和优化，还需要将对象的绘制属性进行统 一、有序的管理。  基本思路是将场景物体按照绘制状态分类，对于相 同状态的物体只设置一次状态并始终保存当前状态 列表。  状态切换是指任意影响画面生成的函数调用，包括 纹理、材质、光照、融合等函数，在切换状态时， 只需改变与当前状态不一样的状态。
  • 9.三维场景的组织和管理 基于绘制状态的场景管理  绘制状态集合通常包括  多个纹理，纹理的使用类型以及它们的融合方式  材质参数，包括环境光、漫射光、镜面光、自身发射光 和高光系数。  其他渲染模式，如多边形插值模式、融合函数、光照明 计算模式等。
  • 10.三维场景的组织和管理  把场景物体按照绘制状态分类 绘制状态集合 A ● 砖块纹理 ● 细节纹理 ● 红色材质 ● 无融合模式 绘 制状态 集合B ● 砖块纹理 ● 细节纹理 ● 灰色材质 ● 无融合模式 绘制状态集合 C ● 砖块纹理 ● 凹凸纹理 ● 红色材质 ● 无融合模式 绘制状态集合实例 绘制状态集合 D ● 立方体纹理 ● 无纹理 ● 单色材质 ● 加法融合模 式
  • 11.三维场景的组织和管理 绘制状态树实例 砖块纹 理 显 显 显 理 红色材质 无融合模 式 灰色材质 无融合模 式 凹凸显 理 显 红色材质 无融合模 式 立方体纹 理 无纹 理 单色材质 加法融合模
  • 12.场景绘制的几何优化 加速判断场景物体之间的空间关系 主要有两种方法 , ◦ 对单个物体建立包围体 , 在包围体的基础 上建立包围盒层次树 ◦ 场景剖分
  • 13.场景绘制的几何优化 常见的包围盒技术 （1）包围球 （2）AABB 包围盒 （3）OBB 包围盒 （4）k 对平行面包围体
  • 14.场景绘制的几何优化 包围体和包围球示例 球的体积比立方体大
  • 15.场景绘制的几何优化 OBB 树的构造示意图
  • 16.场景绘制的几何优化 8-dop 结构
  • 17.场景绘制的几何优化  几何剖分技术将场景中的几何物体通过层次性机 制组织起来 ◦ 优点  使用灵活，能快速剔除层次树的整个分枝，并加速 碰撞检测过程  注意 ◦ 要保持树的平衡 !
  • 18.场景绘制的几何优化 四叉树 （ a ）场景多边形； 分 （ b ）第一次剖分； （ c ）第二次剖 •与二维平面上的均匀剖分相比，四叉树的优点是能提 供层次剔除。
  • 19.场景绘制的几何优化 八叉树 （a） （ a ）初始节点； （b） （ b ）第一次剖分； （c） （ c ）第二次剖分
  • 20.场景绘制的几何优化 BSP 树 二元空间划分（ Binary Space Partition, BSP ）是一种 3D 空间划分算法。 显 能显 显 用在深度排序、碰撞 显显显显显显显显显显显显 、 制、节点裁剪和潜在可见集的计算中，大 大加速了三维场景的漫游。 BSP
  • 21.场景绘制的几何优化 BSP 树 （左）场景的 BSP 树剖分；（右） BSP 树结构示意图
  • 22.场景绘制的几何优化 景物包围体和场景剖分技术比较 （左）场景包围体技术（右）场景剖分技术
  • 23.场景绘制的几何优化 景物包围体和场景剖分技术比较 技术名称 适用场景 构建复杂度 实 用 性 二叉树 尺寸不是特别大的室内建筑场景 复杂 大部分三维游戏引擎 四叉树 室外基于高度场的地形 一般 仅用于地形绘制 八叉树 大规模三维室内、外空间场景 一般 复杂三维游戏引擎 均匀八叉树 体素表示场景、分布均匀的三维 场景 简单 少量三维游戏引擎
  • 24.场景绘制的几何优化 景物包围体和场景剖分技术比较 场景包围体技术 场景剖分技术 表 示 方 式 层次物体表示 层次空间表示 剖 分 方 式 物体剖分 场景剖分 聚显方式 物体的层次聚类 空间的层次聚类 层 次 细 节 物体层次细节 空间层次细节 围围 区域区分开来 围 围 围 围 围 主 要 作 用 围围物 体将空 围绕区域将物体区分开来 代 表 方 法 包围球树 OBB- 树、 AABB 树、 k-DOPS 二叉树、四叉树、八叉树、均匀三维网 格、 kD 树
  • 25.场景的可见性判断 由于视线的方向性、视野的局限性以及物体之间相 互遮挡的原因，视点所观察到的只是整个场景的一部 分，所以要进行可见性判断。
  • 26.场景的可见性判断 遮挡面剔除技术 3D 场景中，相对于视点来说，物体和物体之 间有一个前后的位置信息，就会出现遮挡。 在 遮挡剔除的主要思想是通过选择一些遮挡物体， 在绘制流水线的前期以较少的计算代价来剔除被 遮挡子所遮挡的物体，以减少绘制流水线后期的 处理负荷。 遮挡剔除大致分类两类  针对视点的遮挡剔除  针对视点单元区域的遮挡剔除
  • 27.场景的可见性判断 针对视点的遮挡剔除
  • 28.场景的可见性判断 针对视点的遮挡剔除 适用于人造建筑物少的室外场景 代表性算法 : 基于阴影体技术 （左）遮挡剔除之前；（右）基于阴影体的遮挡剔除
  • 29.场景的可见性判断 针对视点的遮挡剔除—包围盒加速 （左）球 A 至少在一个平面之外，球 B 在所有平面之内， 但其半径大于球心到其中一个平面的距离，球 C 在所有平面 之后且到所有平面的距离足够大。（右）一种包围球没有被 完全遮挡但包围盒被完全遮挡的情形，故物体不应被绘制
  • 30.场景的可见性判断 针对视点单元区域的遮挡剔除  优点 • 对于一个视点邻近区域都有效，具有可见性预测 能力，可以提供连续多帧的绘制，对于实时漫游 以及网络应用比较有效  缺点 需要较长时间的预处理计算与存储资源消耗 • 不适合处理动态场景 •
  • 31.真实的游戏场景 当打开遮挡面剔除时，仅需绘制 7,000 个三角形，帧率为 50fps 。 当遮挡面剔除关闭时，三角形绘制数目增长到 17,300, 帧率下降到 20 fps
  • 32.基于入口 (Portal) 技术的可见性判断  根据单元与单元之间的邻接图 , 通过深度遍 历建立起单元与单元的入口序列
  • 33.基于入口 (Portal) 技术的可见性判断 优点 ◦ 方便定义场景 ◦ 快速绘制 缺点 ◦ 消耗大量的内存，换取效率的提高 ◦ 不适合室外渲染
  • 34.基于入口 (Portal) 技术的可见性判断 — Cell-Portal 结构  假设单元和入口的数据结构 ◦ 数据结构类似于一个图：节点是房间，边是入口 ◦ Portals 本质的意思是两个房间的墙之间存在洞  Portal 形状一般是多边形  两个房间之间也可有多个 Portals  建筑物最合适显显 种情况 显显
  • 35.基于入口 (Portal) 技术的可见性判断 — Cell-Portal 实例 A B A B C D C D E F E F 可以是 房间的边缘 （即墙壁）  Graph 一般保 存相邻信息  Portals ◦ 每个房间保留 其外向的边 （即 portals ）
  • 36.基于入口 (Portal) 技术的可见性判断 — Cell-Portal 可见性  跟踪观察者所在的房间  然后遍历 graph 穷举所有可见的区域 ◦ 可以预处理，对每一个房间计算可能可见集合 potentially visible set (PVS) ◦ 也可以在运行之间更进一步地精确获得可见集合 ◦ 平衡：节省下的时间 vs. 计算小的可能可见集合的 代价  与所在环境有关，如房间的尺寸、房间物体的个数…
  • 37.场景的可见性判断 潜在可见集（ PVS ）方法 对于某个特定的房间，可能可以看到的房 间 / 区域 / 物体 / 多边形 PVS:◦ 一般地，保存可以看见的物体的标识号 ◦ 也要考虑内存的因素  预处理的计算过程  用法 : ◦ 可见性确定 – 对于当前房间，绘制所有 PVS 中 的多边形 ◦ 做为第一步：获得可能相关的区域，并做进一步 处理
  • 38.Cell-to-Cell PVS 在 B 的 PVS 中，当且显 当存在一根 显显显显显显 ，从 B 出发射到 A ，并且在途中与任何物体不 相交 Cell A ◦ 隔壁房间理所当然在 PVS 之中 I J F H B D C E A G I 的 PVS 包括 : B, C, E, F, H, J
  • 39.Cell-to-Cell 的用法  大多数算法比 cell-to-cell 可显显 性算法更 显 显 显 显显 ◦ 因为它过估计– 当实际上 99.6% 的模型应 该是不可见的时候，仅排除了大约 90% 的 模型 , 而更好的算法可以排除 98%  但是，保持 态物体 cell-to-cell 可见性有利于动 ◦ 当房间中有一个移动的物体  并且房间是静态的
  • 40.Cell-to-Cell 的缺点 存在的问题 : ◦ 将一个房间中的所有物体都标记为可能可 见，尽管只有一小部分是可能可见  如果我们要列出可能可见集－意味着我们要将这 个房间中的所有物体都列出来。 ◦ 并没有考虑到观察者的位置，无法报告观 察者可能看不到的物体 进一步处理可以解决这个问题
  • 41.Cell-To-Region 可见性 记录房间中某点处可能可见的某个房 间的某个区域 ◦ 因此，只绘制这个区域中的物体
  • 42.Eye-to-Region (1) View
  • 43.Eye-to-Region (2)
  • 44.细节层次 (LOD) 技术 为了更好地实现三维复杂模型的实时动态显 示，将三维物体用多种不同的精度表示（例 如用精确模型和简化模型），并且根据观察 点位置变化选择不同精度的模型来成像。这 种方法通常称为细节层次技术。 LOD 技术分类 静态 LOD  动态 LOD 
  • 45.细节层次 (LOD) 技术
  • 46.细节层次 (LOD) 技术 静态 LOD  静态 LOD 在场景建立之前，预先生成物体的多个具 有不同细节层次的模型。当用户视点在场景中进行 漫游时，根据视点参数来调用相应的细节层次模型 。 问题  在不同 LOD 模型之间切换时，会引起视觉上的突跳 ，从而造成视觉上的不连续 解决方法 增加雾化效果  在两个层次的绘制结果之间进行线性插值 
  • 47.细节层次 (LOD) 技术 动态 LOD  动态 LOD 使用原始模型和一系列简化记录，构造出 复杂度连续变化的一系列简化模型。 优点 减少了存储容量，强调了视觉过渡的连贯性  有利于网格模型的渐进式传输  核心  多边形网格简化问题
  • 48.细节层次 (LOD) 技术 多边形网格简化算法  自适应细分法  用非常简单的基模型表示初始模型，然后迭代细分 基模型，每一步向模型的局部区域增加越来越多的 细节，直到细节的模型满足用户定义的误差需求， 算法终止。  简化模型的近似度很高，但计算量太大  采样法  采样算法通过随机抽取一些点来初始化多边形模型 ，再通过较少的多边形来重建初始模型，其在采样 点处满足误差估计。  模型简化速度太慢
  • 49.细节层次 (LOD) 技术  几何元素删减法 • • 主要通过几何移去模型单元来进行简化处理。 几何移去方法包括顶点删除法、边删除法和面删除 法，其中边删除法最有效。 基于边删除的顶点简化
  • 50.细节层次 (LOD) 技术 兔子模型的四个层次
  • 51.细节层次 (LOD) 技术 LOD Models
  • 52.示例 : SpeedTree 的 LOD 过渡
  • 53.示例 : SpeedTree 的 LOD 过渡
  • 54.示例 :SpeedTree 的 LOD 过渡
  • 55.游戏特效绘制技术
  • 56.游戏特效绘制技术 三维游戏特效技术的实现是游戏空间真实感 渲染的重要技术特征，是人机交互时提供给 人们感知计算机信息的重要依据。 常用特效技术 广告牌技术  粒子系统技术  精灵动画技术  Warping 特效技术  炫目特效技术 
  • 57.游戏特效绘制技术 广告牌技术  将物体的采样图像，以纹理映射方式贴在多边形 面片上，并随着观察角度的变化，多边形面片的 方向也随之改变。  通过一个矩形图元和一幅纹理替换一个三维物体 ，在渲染矩形时启用 Alpha 混合，将矩形图片 中不包含物体的部分处理成完全透明的。  关键步骤  旋转矩形，使其面对观察者  将矩形图元移动到合适位置，并在其表面贴上纹理
  • 58.游戏特效绘制技术
  • 59.游戏特效绘制技术 粒子系统技术  粒子系统是一系列独立个体的集合 , 它们以一定的 物理规律和生命周期在场景中运动  粒子系统表示三维计算机图形学中模拟一些特定的 模糊现象的技术  可以用来模拟烟，火焰，爆炸，雨雪，流星发光等  粒子系统的核心在于对某个物理模型的理解和分析  既有随机性，又有规律性
  • 60.游戏特效绘制技术 粒子的属性  位置（坐标值）  速度  加速度  生命期：每个粒子都有着自己的生命期，随着时间的推 移，粒子的生命值不断减小，直至粒子死亡  颜色
  • 61.游戏特效绘制技术 粒子系统创建基本过程 ◦ 初始化粒子 ◦ 当程序运行时  如果粒子没有消亡  根据粒子的速度更新粒子的位置  根据粒子的加速度更新粒子的速度  修改粒子的能量  如果粒子的能量小于某一阈值  显置 粒子的状 显显显消亡 显  如果粒子击中场景物体或其他粒子  修改粒子的位置，方向，速度和能量  显示粒子 ◦ 程序结束
  • 62.游戏特效绘制技术 爆炸  最常见的就是采用粒子系统模拟，也有采用 Billboard 模拟爆炸的。  粒子分布在以爆炸点为中心的球面，从球心以 高速和巨大的能量向外发射  有遮挡的爆炸：在半球面上分布粒子
  • 63.游戏特效绘制技术 火焰  二维随机函数 ◦ 设置火源：在预期的位置生成火焰的中心 ◦ 选择随机函数生成火焰的形状和颜色 ◦ 选择正确的图像模糊算法，模拟火焰热源 扩散
  • 64.游戏特效绘制技术 精灵动画技术  精灵是指在游戏中用来实现动画效果的一组 图片，这些图片通常采用位图格式，并且有 用特定颜色填充的透明区域  精灵动画的实现方法 • 将精灵画在可见的背景页面上，然后将所画的前一 个精灵从页面上抹去，再将精灵画在页面的另一个 地方，依次类推
  • 65.游戏特效绘制技术 Warping 特效技术  利用图像变形技术将原图像变形到目标图像 ，通常是根据某个“变换”函数来将原图像的 点映射到目标图像。  图像变形的过程 • • • 为源图像分配规整化网格 指定网格坐标的变换关系 对每个顶点进行变换，生成目标图像
  • 66.游戏特效绘制技术 Warping 特效技术
  • 67.游戏特效绘制技术 Warping 特效技术
  • 68.游戏特效绘制技术 Warping 特效技术
  • 69.游戏特效绘制技术 眩光特效技术  透镜眩光是由于眼睛的晶状体或者相机的透镜直 接面对强光所产生的现象。由一圈光晕和纤毛状 的光环组成
  • 70.游戏特效绘制技术  太阳及镜头光晕的绘制  太阳用圆形物体来模拟  镜头光晕由一系列的光环组成，所有的光环排列在一条 直线上，如下图所示，这些光环的形状有多种方式。下 图显示了一组光晕的纹理图，这些图像其实是 Alpha 掩 码，白色像素表示完全不透明，黑色像素表示完全透明 。  把纹理与顶点颜色进行调制得到实际的光晕颜色，再将 光晕颜色与背景颜色进行融合得到最终的镜头光晕效果
  • 71.
  • 72.地形绘制技术 地形显显 制技 显 显显 广泛 显 显显 用于数字地球、虚 显 显 显 显 显 显 显 显显显显 、显 景漫游、虚拟战场、游戏娱乐等领域 地形可分为室内地形与室外地形。通常地形 绘制主要指室外地形绘制 地形绘制包括基本地形生成、地表纹理、地 形光照、简化加速等几个方面
  • 73.地形绘制技术 地形生成  一般采用高度数据加网格的方法，将不同的 高度值赋予各个网格的顶点 Z 坐标，便生成 了上下起伏的地形网格。  地形高度数据生成方法 随机函数生成 • 基于高度显显 生成 显 • 基于数字高程模型（ DEM ）数据生成 •
  • 74.地形绘制技术 地形生成 （上左）地形的基础三角网格； （上右）高度图； （下左）应用高度图后的地形网格； （下右）渲染后的地形图
  • 75.地形绘制技术 地表纹理  为地表添加纹理  一种方法是在地形网格上重复贴统一的纹理，视 觉效果差  一种方法是通过纹理融合技术，生成一张效果较 好的大地形纹理  细节纹理  在原地形纹理上叠加一层细节纹理，能够显著增 加地形的逼真度
  • 76.地形绘制技术 地形光照  根据太阳位置及地形信息生成地形显显 影的 显 显显 程 地形的雾化效果  能显显 模糊地形与天空的交界，增加 显 显 显 显 显 显 显 显 显 显 显 显 显显 景的真 显 显 显显 感  显化 是通 显显将 显显景的 显 显显色与 显 显显的 显显色，以随物体到 显 显显显 显显 显 察点距离增加而衰减的混合因子混合而显显显 的。 显 finalColor  f �sceneColor  (1  f ) �fogColor
  • 77.游戏中的地形场景
  • 78.碰撞检测 碰撞检测问题 ◦ 是机器人、显显 画仿真、虚 显 显 显 显 显显显显 等显显 域不可回避的 显 显 显 显 显 显显 基本任务 ◦ 确定两个或多个物体彼此之间是否发生接触或穿 透。 起源 ◦ 早期在机器人路径显 划、自 显显显显显 装配 显显显 划等 显显显 域中 显 ，为检测机器人与场景中的物体或零件与零件之 间是否发生碰撞，产生了一系列碰撞检测算法。
  • 79.碰撞检测  碰撞检测问题 基于现实生活中一个普遍存在的事实：两个不可穿 透的对象不可能共享相同的空间区域。 简单描述 ◦ 碰撞检测系统的输入模型为一个静态的环境对象和一个 动态的活动对象的几何模型，它们均为基本几何元素的 集合 ◦ 对象可以包括刚体对象，也可以包括软体对象；模型可 为面片表示的面模型，也可以是体素描述的体模型 ◦ 碰撞检测的任务是确定在某一时刻两个几何模型是否发 生干涉，即它们的交集是否不为空。如发生碰撞，确定 碰撞点
  • 80.碰撞检测 从两个角度对碰撞检测算法进行分类 ◦ 从时间域的角度来分 ◦ 从空间域的角度来分
  • 81.碰撞检测  基于时间域的碰撞检测算法分类   分为离散和连续的碰撞检测算法 离散碰撞检测算法 • 在每一时间的离散点上进行碰撞检测 • 是研究的重点和热点 • 存在问题  存在刺穿现象  显 漏显 显 显 显 显 生的碰撞 显显
  • 82.碰撞检测  连续碰撞检测算法 ◦ 连续的时间间隔内进行碰撞检测 ◦ 计算速度还太慢
  • 83.碰撞检测 基于空间域的碰撞检测算法分类  基于物体空间的碰撞检测算法  基于图象空间的碰撞检测算法
  • 84.碰撞检测  基于物体空间的碰撞检测算法 ◦ 三维图形领域中存在多种几何模型  多边形表示模型  多边形集合，结构化表示模型  非多边形表示模型  CSG 表示模型，隐函数曲面，参数曲面，体表示模型 几何模型 非多边形 表示模型 多边形表 示模型 多边形 集合 结构化表 示模型 CSG 表 示模型 隐函数 曲面 参数曲 面 体表示 模型
  • 85.碰撞检测  基于物体空间的碰撞检测算法  空间剖分法（ space decomposition ）  均匀剖分、 BSP 显、 k-d 树和八叉树（ Octre e ）等 [Samet 1989][Naylor 1990][Bourma 1991]  层次包围体树法（ hierarchical bounding volume trees ）  常显显 的包 显 显显 体包括包 显 显 显 显显 球、 AABB 显 包围盒、 OBB 包 围盒、 K-DOP 包围体等
  • 86.碰撞检测 (a) 包围球 (b) AABB 包围盒 (c)OBB 包围盒 包围体 包围体二维示意图 (d) 6-dop 包围体 (e) 凸包
  • 87.基于空间域的碰撞检测算法分类 基于图象空间的碰撞检测算法 ◦ 利用图形硬件对物体的二维图象采样和相应的 深度信息来判别两个物体之间的相交情况
  • 88.The End ！