999碰撞检测总纲

重建组件三维模型 建立组件根节点包围盒 对不同物体的包围盒 进行碰撞检测 对不同物体进行 精确地碰撞检测 详细的碰撞情况 Y N 碰撞 Y N 运动 碰撞 运动 子节点 1子节点 2子节点 3 根节点 子节点 1子节点 1子节点 1 包围盒树空间剖分方法 表示方式层次物体表示层次空间表示 剖分方式物体剖分空间剖分 层次细节物体层次细节空间层次细节 主要作用围绕物体将空间区分开来围绕空间将物体区分开来 代表方法包围球树 OBB 树 AABB 树 BSP 树 四叉树 八叉树 均匀网格 包围球AABB 包围盒OBB 包围盒 构造简单简单相对复杂 紧凑性差 适合形状均匀物体较差 不适合细长物体较好 求交测试简单较简单复杂 旋转后更新无方向 不需更新需要更新包围盒树 比较复杂需要更新包围盒树 复杂 是否适合变形适合一般 需更新包围盒树变形后更新 OBB 树问题比较大 PPTPPT 内容 内容 一 国内外研究情况一 国内外研究情况 二 本课题研究的主要内容和方法二 本课题研究的主要内容和方法 课题需要解决的问题有 课题需要解决的问题有 拟采取的研究方法拟采取的研究方法 流程流程 具体实现具体实现 三 预期成果三 预期成果 四 可能的创新点四 可能的创新点 五 进度安排五 进度安排 虚拟现实技术中的碰撞检测技术 一种方法一种方法直接计算两个实体顶点 边和面之间的关系 另一种方法另一种方法是使用 点积来判断一个点是否进入另一个实体内部 碰撞检测碰撞检测 碰撞检测 Collide Detection CD 作为虚拟现实技术的重要组成部分 其主要任务是检测虚拟现实场景中各种物体模型之间是否发生碰撞 如果发生 碰撞则给出碰撞信息 如碰撞时间点 发生碰撞的三角形编号 碰撞深度等 同时指导虚拟现实系统进行下一步的操作 如发生碰撞则触发碰撞响应 没有 发生碰撞则仿真模型继续运动等 在虚拟现实环境中 仿真模型之间发生碰撞 必不可免 因此 如何有效地避免仿真模型之间出现 穿透 这种在现实环境 中不可能出现的情况 从而既实现虚拟现实仿真系统的真实性 同时又满足碰 撞检测的实时性要求 使得碰撞检测成为目前研究的热点 目前在对于三维图形的碰撞检测对于三维图形的碰撞检测应用较多的是层次包围盒方法和空间分割层次包围盒方法和空间分割 法法 空间分割法是对图形网格划分 然后对物体间进行相交测试 最大的缺点 是灵活性差 存储量大 包围盒即把物体包围 构造包围盒 当物体的包围盒 相交时 才进一步对物体间进行相交测试 优点为相交测试和构造相对简单 典型的包围盒算法有 包围球 AABB 包围盒 OBB 包围盒和 k DOPs 目的 检测组件之间是否发生渗透 如果渗透 则判断有几个点渗透 并 给出其中渗透距离最大的点 若组件自动运行 则以该物体平移方向算 如果 是接触 则判断接触形式 点边接触 边边接触 面面接触 如果没有接触 则给出平移方向上的距离 以上有平移的 也有转动的 先实现手动移动组件进行碰撞检测 再实现 组件自动运动进行碰撞检测 先两个简单物体的碰撞检测 再复杂多物体的碰 撞检测 先采样然后进行静态碰撞检测先采样然后进行静态碰撞检测 采样方式有距离预测法 更广泛 和时间 预测法 目前碰撞检测算法主要有两种碰撞检测算法主要有两种 一种是转化为判断线面的相交相交问题 另一种 是建立在包围盒包围盒基础上 并对其不断完善的算法 层次数据结构层次数据结构表示模型 对模型进行不同层次的近似 距离远则用粗略的 模型 距离小于一定限度则采用比较精确的模型 OBBOBB OrientedOriented BoundingBounding BoxBox 有向包围盒 有向包围盒 本质上还是一个最贴近物体 的长方体 只不过该长方体可以根据物体的一阶矩任意旋转 OBB 比包围球和 AABB 更加逼近物体 能显著减少包围体的个数 因此 人们通常进行两个回合 的碰撞 相交检测 用包围球做第一回合的快速测试 用 OBB 进行第二回合的测 试 三维点集 S 快速碰撞检测方法 当进行碰撞检测时 你会发现常常需要在速度和精确度之间进行衡量 在 大多数情况中 你会进行组合检测 在第一轮检测中 使用快速检测遍历所有 对象 之后对快速检测中可能发生碰撞的物体进行精确检测 本教程展示了两个方法处理两个模型间的碰撞检测 快速检测方法是找到 模型的全局包围球 并通过调用一个包围球的 Intersect 方法检测是否相交 你可以改进这个方法以增加精确度 由几个 ModelMeshes 组成的模型存储 了模型不同部分的几何信息 每个 ModelMeshes 都能生成各自的包围球 所以 你可以检测第一个模型和第二个模型的每个包围球 显然 这样做提高了精度 但计算量也随之加大 2 22 2 碰撞检测的模型类别碰撞检测的模型类别 虚拟环境中的物体所用的模型大体分为面模型和体模型两大类 虚拟环境中的物体所用的模型大体分为面模型和体模型两大类 面模型用物体的边界 来表示物体 而不包括物体内部信息而不包括物体内部信息 体模型采用体元来表示物体 可描述物体的内部信可描述物体的内部信 息息 体模型所耗存储量大 计算量也大 而面模型的研究和应用比体模型的成熟多 由于 凸多面体有很好的性质 因而可以获得较高效率的基于凸多面体的碰撞检测算法 对于一 般的体 由于处理相对比较复杂 往往采用将一般的体分解成几个凸多面体再进行逐个碰 撞检测 所以碰撞检测的研究工作大多是基于面模型的 少数是基于体模型的 大多是基于面模型的 少数是基于体模型的 面模型面模型又可进一步分为很多种 如多面体模型 CSG 隐式曲面 参数化曲面等 其 中 最常用的一种是多面体模型最常用的一种是多面体模型 特别是三角形模型 多面体模型是一种简洁 通用的表 示方法 几乎应用于表示任何形状的物体 而且便于操作 易于实现硬件加速 多面体模型又有多种形式 碰撞检测算法也可能对模型的形式有要求 如很多算法要 求输入模型是实体 即可表示成闭合曲面 其中 不少算法利用物体的凸性来加速 因而 进一步要求输入模型是凸多面体 对非凸多面体则做特殊处理 另一些算法对输入模型则 不做特殊处理要求 输入模型被表示成一组无拓扑约束的三角片 这类算法通用性比较好 本论文输入模型便是一组无拓扑约束的三角片本论文输入模型便是一组无拓扑约束的三角片 场景中的运动物体还可分为刚体和柔体 刚体物体在运动中不改变物体形状 其运动 形式局限于平移和旋转 柔体物体在运动中会改变物体的形状 其运动形式除了平移 旋 转还有变形 如心脏的跳动 故柔体物体的碰撞检测比刚体要复杂得多 在本论文中我们 只针对刚体物体进行碰撞检测只针对刚体物体进行碰撞检测 2 42 4 碰撞检测技术的基本原理碰撞检测技术的基本原理 如果两个安全封闭的多面体发生相互碰撞时 其中一个多面体至少会有一个面与另一 个多面体的至少一个面发生相交 若能在碰撞发生时 立刻检测到相交 然后将两个物体 的位置稍做调整 可消除碰撞现象 如下是碰撞检测基本算法描述 设在一虚拟环境中要仿真 n 个物体 A1 A2 An 其对物体的仿真过程是逐帧计算的 从 T0 到 T1 按时间步长按时间步长 dTdT 进行计算 在虚拟环境中调用碰撞检测过程 2 Simulation for T T0 to T1 步长为 dT do 获得用户的输入 更新 A1 A2 An 各物体的行为 if collisionDetect T A1 A2 An 找到了碰撞 then 计算碰撞反应 绘制 n 个物体 A1 A2 An 碰撞检测过程 Tprev 为全局变量 初值为 T0 dT dt 为碰撞检测的步长 collisionDetect Tcurr A1 A2 An for t Tprev to Tcurr 步长为 dt do for A1 A2 An 中每个物体 Ai do 移动 Ai 到其在时间 t 的位置 for A1 A2 An 中每个物体 Ai do for Ai 1 An 中每个物体 Oj do if Oi 与 Oj 相交 then 报告在时间 t 发生了碰撞 Tprev Tcurr 以上是碰撞检测思想的一种最基本的方法以上是碰撞检测思想的一种最基本的方法 在实际应用过程中可以根据需要对该方法 进一步改进 以得到更高效的碰撞检测算法 3 13 1 空间剖分法空间剖分法 空间剖分法通常将空间剖分成均匀的单元 每个物体对应一个或多个单元中 只有当 物体处于同一单元空间中才可能相交 这时应该对该单元空间进行精确的碰撞检测 采用 空间剖分思想 19 的算法一般用树的方式逐步分割空间 可以进一步加速碰撞检测 常用的 空间剖分方法是 BSP 4 八叉树 5 如图 3 1 均匀网格 6 3 d 树 7 八叉树用树的结 构表示空间的分解情况 根是整个空间 将每个父结点空间用三个分别与坐标轴垂直的分 割面分成大小相等的八份 每一份作为它的一个子结点 分割不断进行直到与子结点相交 的三角形数目小于一个阈值或者与子结点相交的三角形属于同一模型 该子结点成为一个 叶结点 如果来自两个模型的三角形与同一个叶结点相交 那末需要对这两个模型进行碰 撞检测 BSP 树与八叉树相似 但是二叉树 3 d 树是一种特殊的 BSPs 树 用来分割空间 的分割面都是与某一个坐标轴垂直的 一般 空间剖分算法在每次碰撞检测时都需要确定 每个模型占有的空间单元 如果场景中不可动的模型很多 可以预先划分好空间单元并计 算出每个模型占有的空间单元 当有模型运动时 只要重新计算运动模型占有的空间单元 就可以 所以空间剖分算法比较适合用于稀疏的环境中分布比较均匀的几何对象间的碰撞 检测 如图 3 2 图 3 1 八叉树 图 3 2 空间剖分法在场景中的应用 3 23 2 包围盒层次树法包围盒层次树法 另一种常用方法是包围盒 包围盒方法被广泛应用于对光线跟踪和求交运算的加速 其基本思路是用体积略大而几何特性简单的包围盒将复杂的几何形体围住 当对两个物体 做碰撞检测时 首先检测包围盒是否相交 若不相交 则两个物体不相交 反之 需要进 一步对两个物体进行精确检测 此方法可以快速排除不相交的物体 加速了算法 与一个 物体相对应的层次树的结点是空间上包围该物体一部分几何结构的几何近似体 层次树的 根结点是包围了整个物体 每个父结点包围的几何结构是它所有子结点包围的几何结构之 和 结点从上到下逐渐逼近它包围的几何结构 判断两个模型是否相交时 首先判断两个 层次树的根结点是否相交 如果两个父结点相交 那末将它们的子结点分别进行相交判断 如果最后有相交的叶结点对 判断每对叶结点包围的几何结构是否相交 如果有相交的几 何结构对 则模型相交 反之不相交 比较典型的包围盒类型有包围球 spheres 8 沿坐标轴的包围盒 AABB axis aligned bounding box 9 方向包围盒 OBB oriented bounding box 等 层次包围盒法 则应用于复杂环境中的碰撞检测 3 2 13 2 1 包围盒形状的设计准则包围盒形状的设计准则 选择哪种形状的包围盒通常取决于应用领域及其蕴含的不同约束条件 例如在光线跟 踪算法中 包围盒应能紧密包围物体 同时又便于高效地对一条光线和包围盒做求交测试 对于碰撞检测算法 可借助一个耗费函数来分析 2 TNvxCvNpxCpNuxCu 其中 是碰撞检测的总耗费 T 是参与重叠测试的包围盒的对数 是一对包围盒做重叠测试的耗费 NvCv 是参与求交测试的几何元的对数 是一对几何元做求交测试的耗费 NpCp 是物体运动后包围盒层次需要修改的结点个数 是修改一个结点的耗费 NuCu 根据这一耗费函数 可以推测理想的包围盒应满足如下要求 T 在各层次上紧凑地逼近输入模型及其子部分 以减少 NvNp 支持快速为一对包围盒做重叠测试 以减少 Cv 当物体旋转或平移时 支持对其包围盒层次中结点的快速修改 以减少Cu 3 2 23 2 2 包围盒类型包围盒类型 从上节知道选择不同类型的包围盒直接影响到碰撞检测算法的效率 本节将详细介绍 一些常用的包围盒类型 20 并分析各自的优缺点 1 1 沿坐标轴的包围盒沿坐标轴的包围盒 AABBAABB axisaxis alignedaligned boundingbounding boxesboxes AABB 在碰撞检测的研究历史中使用最悠久 一个 AABB 被定义为包含该对象且边 平行于坐标轴的最小正六面体 如图 3 3 所示 基于 AABB 碰撞检测系统的有 I collide 10 SOLID 11 等 AABB 间的相交测试相交测试比较简单 两个 AABB 相交当且仅当在三个坐标轴投影区间均重叠 但 是 AABB 紧密性比较差 尤其是对于沿斜对角线放置的瘦长物体 用 AABB 将留下很大边角 空隙 从而导致大量冗余的包围盒相交测试 这样的话 减少 同时可能增加 CvCuNp 可以注意到 AABBAABB 对物体的方向很敏感 对物体的方向很敏感 同一物体的不同方向 AABB 也可能不同 由于球体只有一个自由度 所以检测球对物体方向不检测球对物体方向不 敏感 敏感 当物体在场景中移动时 它的 AABB 也需要随之移动 当物体发生当物体发生 旋转时 有两种选择旋转时 有两种选择 用变换后的物体来重新计算 AABB 或者对 AABB 做和物体同样的变换 如果物体没有发生扭曲 可以通过 变换后的 AABB 重新计算 因 为该方法要比通过 变换后的物体 计算快得多 因为 AABB 只有 8 个 顶点 变换变换 AABBAABB 得出新的 AABB 要比变换物体的运算量小 但是也会带带 来一定的误差来一定的误差 如图 10 33 所示 比较图中原 AABB 灰色部分 和新 AABB 右边比较大的方框 它是通过旋转后的 AABB 计算得到的 新 AABB 几乎是原来 AABB 的两倍 注意 如果从旋转后的物体而不是旋转后的 AABB 来计算新 AABB 它的 大小将和原来的 AABB 相同 图 3 3 AABB 包围盒 2 2 包围球 包围球 spheresspheres 不共线的三个点唯一确定一个圆 不共面的四个点唯一确定一个球 包围球类似 AABB 是一种简单性好紧凑性差的一类包围盒 包围球被定义为 包含该对象的最小球体 如图 3 4 所示 图 3 4 包围球包围盒 包围球间的相交测试相交测试也相对比较简单 对于两个包围球 1 1 和 2 2 如果球 心距离小于半径之和 即 1 2 1 2 则两包围球相交 可进一步简化为判断 1 2 1 2 1 2 2 故包围球间的相交测试需要 4 次加减运算 4 次乘 法运算和 1 次比较运算 考虑由球心c1 c2和半径r1 r2定义的两个球 如图 10 26 所示 设d为球心间的距离 很明显 当d r1 r2时相交 在实践中通过比较 d2 r1 r2 2 可以避免包括计算d在内的平方根运算 3d 碰撞检测技 术 包围球的紧密性包围球的紧密性在所有包围盒类型中是比较差的 它除了对在三个坐标轴上分布的比较比较 均匀的几何体均匀的几何体外 几乎都会留下很大的空隙 通常需要花费大量的预处理时间以构造一个好 的层次结构逼近对象 这在 Hubbard 的工作中得到验证 相对于 AABB 而言 在大多数情况下 包围球无论是紧密性还是简单性都有所不如 因此因此 它是使用得比较少的一种包围盒它是使用得比较少的一种包围盒 当对 象发生旋转运动发生旋转运动时 包围球不需要做任何更新 这是包围球比较优秀的一个特性 当几何对象 进行频繁的旋转运动时 采用包围球可能得到较好的结果 当对象发生变形时当对象发生变形时 很难从子结 点的包围球合成父结点的包围球 只能重新计算 3 3 方向包围盒方向包围盒 OBB orientedOBB oriented boundingbounding box box OBB 是 Gottschalk 在 1996 年实现的 RAPID 系统中首先使用的 13 当时该系统声称是最 快的碰撞检测系统 曾一度作为评价碰撞检测算法的标准 一个给定对象的 OBB 被定义为包 含该对象且相对于坐标轴方向任意的最小的正六面体 OBB 最大特点是它的方向的任意性 这使得它可以根据被包围对象的形状特点尽可能紧密地包围对象 如图 3 5 但同时也使得但同时也使得 它的相交测试变得复杂它的相交测试变得复杂 图 3 5 OBB 方向包围盒 OBB 的计算相对复杂一些 其关键是寻找最佳方向 并确定在该方向上包围对象的 包围盒的最小尺寸 OBB 间的相交测试基于分离轴理论 若两个 OBB 在一条轴线上 不一定 是坐标轴 上的投影不重叠 则这条轴称为分离轴 若一对 OBB 间存在一条分离轴 则可以判 定这两个 OBB 不相交 对任何两个不相交的凸三维多面体 其分离轴要么与任一多面体的某 一个面垂直 要么同时垂直于每个多面体的某一条边 因此 对一对 OBB 只需测试 15 条可 能是分离轴的轴 每个 OBB 的 3 个面方向再加上每个 OBB 的 3 个边方面的两两组合 只要找 到一条这样的分离轴 就可以判定这两个 OBB 是不相交的 如果这 15 条轴都不能将这两个 OBB 分离 则它们是相交的 两个 OBB 的相交测试最多需要 15 次比较运算 60 次加减运算 81 次乘法运算和 24 次绝对值运算 尽管 OBB 间相交测试的代价比较大 但它的紧密性是最 好的 可以成倍地减少参与相交测试的包围盒的数目和基本几何元素的数目 在大多数情况 下其总体性能要优于 AABB 和包围球 此外 当几何对象发生旋转运动后 只要对 OBB 的基底 进行同样的旋转即可 因此 对于刚体间的碰撞检测 OBB 不失为一种较好的选择 但迄今 为止 还没有一种有效的方法解决对象变形对象变形后 OBBOBB 树的更新问题树的更新问题 而重新计算每个结点的 OBB 的代价又太大 故而故而 OBBOBB 不适用于软体对象环境中的碰撞检测不适用于软体对象环境中的碰撞检测 OBB 算法采用任意方向的包围盒作为物体及子部分的包围盒 组成 OBB 树 该算法的 主要特点是采用了一个 分离轴 方法来检测两个包围盒是否相交 此方法大大加速了包 围盒测试过程 从而从整体上加速了算法 此外 该算法力图使包围盒与物体很紧凑 以 提高包围盒的检测命中效率 为一个物体创建为一个物体创建 OBBOBB 树的过程可分为两部分 树的过程可分为两部分 1 为表示该物体的多边形集合计算一个 OBB 包围盒 首先将所有多于三条边的多边形分割成三角片 即把物体表面三角化 然后采用一阶 和二阶方法对构成物体的所有三角形的所有三角片的顶点进行统计 分别求得均值 U 协 方差矩阵 C 设第 i 个三角片的顶点是 pi qi ri 则有 0 0 1 3 1 1