东北大学计算机图形学11

第11章 碰撞检测碰撞检测(Collision Detection, CD) 碰撞检测是计算机图形学和虚拟现实中最基本 且非常重要的组成部分。应用广泛，可用于 ü 虚拟制造 üCAD/CAMü计算机动画 ü物理建模 ü三维游戏 ü飞机和汽车驾驶模拟 ü机器人 ü路径和运动规划 ü装配碰撞处理 碰撞检测(Collision Detection)返回两个或多个物体是否发生碰撞的布尔判断 碰撞确定(Collision Determination) 找到物体之间的实际相交位置 碰撞响应 (Collision Response) 针对两个物体之间的碰撞决定采取何种操作本章内容 使用射线进行碰撞检测用线条来表示复杂物体，然后对线条和环境中的图 元进行相交测试。主要用于游戏。 使用BSP 树进行动态碰撞检测 一般层次碰撞检测 uOBBTree （层次碰撞检测的具体实现之一） uk-DOPTree （层次碰撞检测的具体实现之二）ü 无论模型的大小、距离，均能取得实时交互速度 ü 可以处理多边形黏体(Polygon Soup), 如凹体、非流形ü 模型可以进行刚体运动（旋转、平移） ü 可以提供高效的紧凑包围体本章内容 多物体碰撞检测系统ü一个好的碰撞检测系统应能处理包含成百上千的运 动物体的场景。 ü随着n、m的增大，计算开销越来越大，因此需要一 种巧妙的方法来处理这些情形！（这正是本节需解 决的问题） 其它主题 Front tracking, Time-critical collision detection, 最短距离计算使用射线进行碰撞检测 是一种特定环境下的快速碰撞检测技术，实际 应用效果非常好。 例子：一辆小汽车沿着斜坡向上行驶，可利用 路上的信息（路面形成的图元）来引导汽车向 上行驶。但对于游戏等应用，并不需要这种复 杂的碰撞检测。可使用一组射线来近似运动物 体。使用射线进行碰撞检测 假设小汽车一开始在一个平面上，4个轮子是小汽车唯 一与环境接触的地方。可在4个轮子上各生成一条射线 ，射线的起始点位于轮子和环境之间的接触点上，然 后对轮子上的射线与环境进行相交测试。 如果从射线原点到环境的距离为0，则轮子在地面上； 如果这个距离大于0，则轮子和环境没有接触；如果距 离为负，则轮子陷在环境中。 可用这些值来计算碰撞响应：负距离可使小汽车（所 在轮子处）向上运动，正距离可使小汽车向下运动。 相交测试加速技术：层次表示、BSP树等。 为了避免射线在两个方向进行搜索，可将测试射线的 原点向后移动直到它在环境包围盒的外面，然后再对 这条射线和环境进行相交测试。不是计算整辆测车子与环境（路面）之 间的碰撞，而是在每个轮子上引出一条射 线，然后对这些射线与环境进行相交测试 。使用BSP树进行动态碰撞检测 Melax的碰撞检测算法： 对用BSP树描述的几何体进行碰撞检测，其中 碰撞体可以是 ü球体 ü圆柱体（可以用来近似人物几何体） ü物体凸包 算法可以进行动态碰撞检测 已经用于商业游戏球体碰撞体几何体一个点从p0移动到p1，可以用线段p0 p1表示。线段和标 准的BSP树之间的相交测试可以高效地进行。这里可能 会有多个交点，但只有第一个相交点表示这个点与几何 体之间的碰撞。 扩展到球体：将BSP树向外扩展园的半径 长度 对p和扩展后的BSP树进行相交测试 拐角应该是圆形，因此是这种算法引入 的一种近似形式 测试平面从：n.x+d0调整为：n.x+d±r0（±符号取决于 碰撞搜索在平面的哪一侧）平面/圆柱体的相交测试 在游戏中，球体往往不能很好地对人物 进行近似 人物的凸包或包围人物的圆柱体相对来 说更好 目标：对BSP树和由一组顶点S形成的运 动凸包进行相交测试 圆柱体在游戏中更接近人体，对圆柱体 进行的相交测试也较快平面/圆柱体的相交测试对平面移动 使其刚好接触 到圆柱体，计 算从p0到移动 之后平面的距 离e半径为r高为hp0为参照点希望解决的 问题：圆柱 体和平面进 行相交测试用距离e将平 面移动到 新位置最终结果：将平面与圆柱体之间的相交测试转 换为点p0与新平面之间的测试例外情形方法会产生不精确性 引入额外的倒角面来解决 如果相邻平面间的外角大于90度，就插入一个额外平面 不能去掉所有的错误 缺点：所花费的代价要比不使用调整平面高出2.5至3.5倍 。但由于碰撞检测所耗费的时间(66us)相对于绘制画面的时 间(33000us)并不多，因此由此引入的代价可以忽略。额外的倒角面引起的BSP树变化一个正常的单元和对应 的BSP树在单元中增加了倒角面， BSP树相应发生了改变一般层次碰撞检测 一般层次碰撞检测算法的三个特点 ü 使用包围体为每个模型创建一个层 次表示形式 ü 不论采用何种包围物体，用于碰撞 检测的高层代码总是类似的 ü 可用一个简单的代价函数(Cost Function)对性能进行修剪、计算、 比较层次创建 模型是由很多图元表示的。超过3个顶点的多 边形可以转化为三角形。 在碰撞检测算法中，模型常用的层次结构为k 叉树数据结构，每个节点最多有k个子节点。 很多算法采用最简单的二叉树数据结构。每个 内部子节点有一个包围体，它包含所有的子节 点；在每个叶节点，存在一个或多个图元（三 角形）。 将任意节点的包围体A（内部节点或叶节点） 表示为Abv，将属于A的子节点表示为Ac 。层次创建的三种形式 为了创建一个高效紧凑的结构，需尽可 能将包围体的体积最小化。层次创建有 的三种形式:ü自下而上 ü渐进树插(Incremental Tree-insertion)ü自上而下自下而上方式 首先将大量图元组合起来并找到它们的 包围体，图元应紧密地靠在一起，可利 用图元之间的距离来确定。 然后，用同样的方法创建一个新的包围 体，或者组合现有的包围体。 直到只剩下唯一的包围盒，把它作为根 节点。Incremental Tree-insertion方式从一棵空树开始，然后将所有图元和相 应的包围体逐个加入到这棵树上。为了使得树的效率比较高，必须在树中 找到使得整棵树体积增加量最小的插入点 。自上而下方式 这是大多数层次构造算法所采用的方法。主要 步骤1.首先找到包含模型所有图元的包围体，并把 其作为根节点。2.然后，采用分而治之的策略，将BV分割成k 个部分。3.采用递归方式，对于每部分进行类似的分割潜在优点：可以根据需要创建层次。层次结构的好坏衡量准则 对于平衡树，遍历每个叶子节点所耗费 的时间几乎相等，所以平衡树的性能最 好 ！ 但并非对于所有输入，平衡树都是最好 的。例如，如果模型的某个部分很少或 从来不用于碰撞查询，则这部分可以位 于一棵不平衡树的深层部分，而保证经 常查询的部分尽可能靠近根节点。层次间的碰撞检测 用户通常需要的碰撞检测情形1.用户只对两个模型是否碰撞感兴趣，只要确 定两个三角形发生重叠，测试过程即可终止。碰撞检测(collision detection)2.用户希望得到所有的重叠三角形。碰撞确定(collision determination)代价函数 代价函数：t = nvcv+ npcp+ nucu ü nv: BV/BV重叠测试的数目 ücv:BV/BV重叠测试的开销 ünp:有重叠的图元对数目 ücp: 测试两个图元是否有重叠的开销 ü nu:由于模型运动的原因需要更新的BV数目 ücu: 更新一个BV的开销 比较好的模型层次分解会产生较低的nv,np,nu。 比较好的重叠测试方法会降低cv和cp的值。但 这又会与上面的目标冲突，因为快的重叠测试 意味着不是很紧凑的包围体。OBBTree 在Siggraph1996年会上，Gottschalk等人的论 文“OBBTree: A Hierarchical Structure for Rapid Interference Detection”对碰撞检测算法 的深入研究具有很大的影响。 设计OBBTree的目的：针对碰撞检测中两个表 面非常靠近而且几乎平行时的情形。 针对这这种情形，OBBTree要比k-DOPTree要 好 可用于公差分析和虚拟原型中层次创建 基本的数据结构为一棵二叉树，每个内部节点 为一个OBB，每个叶节点为一个三角形。 自上而下：为多边形Soup建立一个紧密贴合的 OBB，然后沿着OBB的一个轴对这个OBB进行 分割，把三角形也相应分成两组；对于每一组 ，计算一个新的OBB Gottschalk的分割策略：将包围盒的最长轴分 割为长度相同的两部分。处理刚体运动 在OBBTree层次中，每个OBB可以和刚体变换 矩阵MA存贮在一起，这个矩阵含有OBB对其 父节点的相对位置和方向。 现在要对两个OBB进行测试（分别为A和B） ，则应在一个OBB所在的坐标系中进行A和B 之间的重叠测试，不仿在A所在的坐标系中进 行测试。这样，A就是中心位于原点的AABB ，然后将B变换到A所在的坐标系中。变换矩阵 为：TAB=MA-1MBk-DOPTree 之所以选择k-DOP为碰撞检测层次中的包围体： ü重叠相交测试速度快（因为k-DOP的平面方向是固 定的） ü包围盒逼近效果比较好 随着k的增大，k-DOP与物体的凸包越来越相似 测试表明，选k18时具有最好的效率 AABB的法向可以给出6个平面，两个法向之和给出了 另外12个平面，这样就生成了一个18-DOP。 好的法向选择可使顶点在法向上投影的计算开销非常 小，只需要进行加法和减法运算。（原因：非归一化 法向的分量要么是0，要么是1）物体旋转后k-DOP的近似计算一个茶杯的8-DOP前一个8-DOP茶杯旋转后，一个好的8- DOP拟合，但计算量较大近似方法：对前一 个8-DOP进行变换层次创建 k-DOPTree采用二叉树结构 k-DOPTree与OBBTree的主要区别：k-DOPTree的叶 子节点可以包含任意多的三角形。对于静态模型，每 个叶子节点所允许的最大三角形数目为1；对于动态模 型，每个叶子节点所允许的最大三角形数目为40。原 因：对k-DOPTree进行变换的计算开销比较大。 采用自上而下的方法进行层次创建。 当需要将k-DOP分割为两个子体时，对于如何在x、y 、z中进行选择，主要采取四种方法：ü 最小和方法：使子体之和最小 ü最小最大法：使两个子体中较大一个最小化 ü泼溅方法：计算三角形质心在每个轴上的投影变化 ，选择其中一个差异最大的轴。（最好的方法） ü最长边方法：在所选轴的方向上，包围体的长度最 长通过刚体运动对k-DOPTree进行更新 由于k-DOP的平面方向是固定的，因此物体的刚体运 动会使得层次结构变得无效(可以处理平移，但不能处 理旋转)，必须使用某种方法对层次结构进行更新。 Klosowski提出的两种高效更新方法(可保持层次结构不 变): ü 近似方法：避免为变换之后的几何体重新计算一个新的k -DOP，而是通过变换和使用原始的k-DOP拐角处的顶点 位置。（前提：k-DOP 的顶点比几何体的顶点少。缺点 ：更新后的k-DOP 逼近几何体的效果不好） ü 上山方法：利用当前节点包含的几何体凸包。测试沿k- DOP 法线方向的最远顶点是否依然保持最远，如果不是 ，则用其邻近的最远点更新。（优点：逼近效果好一些 。缺点：计算开销较大。）多物体碰撞检测系统 前面介绍的方法主要用于测试两个实体之间的 碰撞检测。如果要在不同的物体之间进行成百 上千的碰撞检测，若采用逐个测试的策略，则 执行效率上非常低，在实际应用中不可行。 将介绍两级碰撞检测系统：主要针对大规模场 景中多个物体的运动。 ü 第一级主要找到环境中所有物体之间的可能碰撞，并将 结