基于OBB层次包围盒的碰撞检测算法改进

1、31962009,30(13 计算机工程与设计 Computer Engineering and Design 0引 言很多虚拟场景中, 物体间的碰撞检测是一个很普遍而且 极具挑战性的问题, 可以应用在如虚拟现实技术、 计算机动画 技术、 机器人技术等很多领域中。碰撞检测技术的基本任务 是确定虚拟空间中两个或多个物体彼此之间是否发生接触或 穿透。 目前国内外针对碰撞检测问题的研究已有了很多有价 值的研究成果。 但是随着虚拟现实等新领域的涌现以及人们 对虚拟环境真实性要求和用户交互实时性要求的不断提高, 如何有效地提高碰撞检测的速度以保持虚拟环境真实性的问 题也随之更加突出显现出来。为了加速碰撞

2、检测的查询时间, 人们提出了很多技术去 剔除并不发生真正碰撞的三角形对。 这些方法中就包括层次 包围盒 (BVHs 1-2等方法, 其中层次包围盒是将物体 (三角形网 格 用某些简单的几何形状 (即包围盒 完全包围在中间, 比如 AABB 包围盒3-4, OBB 包围盒5-6等。 在碰撞检测的最初阶段,通过对包围盒的相交测试, 可以排除不可能发生碰撞的物体, 从而起到加速检测的作用。然而如果物体的数量较多, 并且物体的运动状态多样, 这时若将所有包围盒一一进行相交测 试, 那么会带来非常巨大的计算开销, 并且这个计算开销随着 物体数量的增加明显增大。本文在基于三角形网格的模型上进行测试。在基于

3、特征 的层次结构基础上, 提出特征描述三角形的层次结构结合 OBB 包围盒技术进行碰撞检测。 利用这些层次结构, 我们在进行基 元碰撞检测之前, 选择剔除那些明显不相交的三角形对, 有效 的减少了基元测试的数量, 提高了剔除效率, 达到了加快碰撞 检测速度的目的, 增加了虚拟场景中的真实性与实时性。1相关背景1.1基元碰撞检测碰撞检测的目的是检测物体之间是否发生相交, 通常可以划分为初步检测阶段和详细检测阶段这两个阶段。 初步检 测阶段主要是应用一些优化策略或方法来快速排除明显不发 生碰撞的物体, 找出潜在的相交区域或潜在的相交物体对。 详 细检测阶段根据已经确定的潜在相交区域或潜在的相交物体

4、 对做进一步的相交测试。 这个阶段能够给出更多的碰撞信息,收稿日期:2009-03-16;修订日期:2009-05-20。开发与应用王鹏,刘旭敏,关永:基于 OBB 层次包围盒的碰撞检测算法改进2009,30(13 3197例如接触点、 穿透深度、 相邻信息等, 这些信息对后来的碰撞 响应提供支持。 其中有大量的研究集中在快速的基元相交测 试, 快速的穿透深度计算等。基元碰撞检测就是发生在详细检测阶段。 详细检测阶段 是真正计算相交, 以及提供各种碰撞信息的阶段。这个阶段 要对己经确定的潜在相交区域或潜在相交物体对做进一步碰 撞检测, 其中的重要环节就是基元碰撞检测。本文的讨论是基于三角面片,

5、 因此我们只考虑三角面片 之间的基元相交测试, 这其中包括 “点一三角形” 、 “边一三角 形” 等多种不同类型的相交测试。假设 t 0时刻两个三角形不发生碰撞, 而且我们知道三角形 上各顶点的位置与速度, 那么, 在 t 0, t 0+ t 时间间隔内的碰撞检 测任务就是检测在该时间间隔内是否存在碰撞现象。 当三角形 和三角形发生碰撞, 只有两种碰撞形式 (如图 1所示 会发生 7:“边一边” 碰撞, 一个三角形的边与另一个三角形的边相交。 1.2层次包围盒物体间的碰撞检测有很多方法, 层次包围盒法是其中常用方法之一。层次包围盒是一种典型的空间数据结构, 它的 设计理念是避免对所有几何基元进

6、行穷举碰撞测试。 碰撞检 测基本思想是先通过测试物体的包围盒是否相交来肯定排除 不可能相交的物体对, 再对已经确定相交的包围盒中的物体 对进行精确的相交测试。 这种方法是把复杂的几何对象用简 单的包围盒近似地描述, 进而构造树状层次结构进行逼近对 象的几何模型, 最后几乎完全得到对象的几何特性。目前一 些典型的包围盒类型有, 沿坐标轴的包围盒 AABB 、 任意方向 包围盒、 包围球、 离散有向多面体 K-DOP 等。包围体的选择需要考虑两个相互冲突的约束 8:包围盒的 简易性和紧密性。 包围盒的简易性指包围盒要简单于被包围 的几何对象, 要求不但几何形状要简单易于计算, 而且同样要 求碰撞相

7、交测试算法也简单快速。 包围盒的紧密性要求包围 盒要尽量贴近于被包围的对象, 这一属性很大程度决定了相 交测试所需的包围盒数目; 紧密性越好, 参与碰撞相交测试的 包围盒数目就会越少。 OBB 碰撞检测方法具有紧密性较好, 实时性程度较高等特性, 而且总体上性能要优于 AABB 和包 围球。所以, 本文采用的是 OBB 包围盒技术。2基于特征的层次结构如图 2所示, 说明了在基于特征的层次结构上, 碰撞检测最后产生基元测试的情况, 一个顶点 v1包含在 6个三角形, v1与三角形 t1相交。剔除算法会依次产生一个三角形对, 这个 三角形对由 t1和包含 v1的三角形组成。直接看来,点面 VF(

8、v1,t1 测试, 会被执行 6次, 每次产生同样的结果。 同样道理, 涉及到包含 v1的边的 EE 测试, 都会执行两次, 因为每一个边 都被两个三角形共享。这样就降低了碰撞查询的效率, 从而 就会产生重复查询的问题 9。重复查询问题的存在是因为剔除算法是基于三角形网格 的, 但是最后的基元测试是基于三角形特征的, 而且大部分被 多个三角形共有。为了改善剔除效率, 可以用特征的包围盒 去剔除非相交特征从而改善剔除效率。 于是就有了基于特征 的层次树。基于特征的层次树是一个独立的层次包围盒 (BVH 的集 合; 建立在每一个特征上的层次包围盒会被用到基元测试中。在这种碰撞检测技术中, 点的 B

9、VH (V-BVH , 边的 (E-BVH 和面 的 (F-BVH 之间的碰撞都会检测到, 从而检测 V-BVH 和 F-BVH 之间的碰撞, E-BVH 之间的自碰撞, 最后找到相交的三角形。这种方法有个优点, 那就是采用这种层次关系通过基于 特征三角形的 BV 剔除, 改善了总体的剔除效率。例如在图 3(a 中, 两个三角形的 BV 相交了, 如果基于这个信息, 我们需 要进行九次 EE 测试。 在图 3(b 中, 有两对边的 BV 相交了, 基 于这种层次关系仅仅需要两个 EE 测试就足够了 9。但是这种方法也存在着问题, 基于特征的层次结构比基 于三角形的层次结构占用空间多, 而且每个

10、结构还需要详尽 的维持工作, 更新, 重构等等, 代价很高。在此基础上采用基于特征描述三角形 (R-T 的层次结构能 很好解决这个问题。3特征描述三角形特征描述三角形包含了基于特征的层次结构的所有优点。所谓的特征描述三角形是一个基本的三角形, 再带有特 征描述的信息和特征包围盒。 特征描述三角形允许有自己的 特征集。 可以根据特征描述三角形的特征集去选择候选三角 形对, 分配三角形对进行基元测试。一个特征描述三角形也 可以带有包围盒, 但这个包围盒是基于特征的包围盒, 这些特 征包围盒可以用于改进剔除效率。 为了从网格中创造有效的图 1“点 三角形” 碰撞、 “边 边”碰撞 , , ,ttt特

11、征描述三角形, 本文总结出 3个性质:对于特征 必须分配到一个三角形中去。 对于特征Ö»ÄÜ·ÖÅäµ½Ò»¸öÈý½ÇÐÎÖÐÈ¥¡£ ¶ÔÓÚÌØÕ÷·ÖÅäµ½Èý½

12、;ÇÐÎt 中了, 那么 t 包含 和协方差矩阵 C 3计算如下3=1+1, q i =q i -都是三维向量。协方差矩阵 C 是一个对称矩阵, 根据对称矩阵特征向量互 相垂直的性质, 用 C 的 3个特征向量可以确定 OBB 的方向轴。4.2包围盒树的生成二叉树遍历方法 10是生成有向包围盒树的普遍方法:(1 二叉包围盒树的根节点选为三维实体的最外包围盒; (2 采用自顶向下方法, 将分割后所得到的子结点体积之和最小的方向作为分离轴方向, 从而确定根节点的分离轴;(3 将根结点进行划分, 形成下一级子包围盒结点。计算 每一个三角面片所属的三维空间, 如果三角面片

13、与分割平面 相交, 则计算中心位置以确定三角面片所属区间;(4 递归划分每一级节点, 直至生成最终的叶子节点, 即单 一的三角面片。5实验结果与分析实验在 CPU Intel Celeron M 1.86, 内存 DDR21G , 显卡 ATIMobility Radeon X1400环境下完成。实验完成正方体相互碰 撞的情况, 图 4中, 正方体互相碰撞后会相互弹开。图 4是实 验效果图。实验最后的结果, 如图 5、 图 6所示, 在基元测试数量上, 基于特征描述三角形的结构比通常的结构减少了将近 7倍到 8倍的数量, 大大降低了查询时间。最后的实验结果说明了, 本文在结合 OBB 包围盒技术情 况下, 与通常的基于三角形包围盒的结构相比, 基于特征描述 三角形的层次结构有效地较少了基元检测的数量, 加快了查询效率, 增强了虚拟环境真实性。(下转第 3208页图 4实验效果图 5基元测试数量比较 基本的基于三角形的结构; 基于特征描述三角形的层次结构平均基元测试数量百万86420基本的基于三角形的结构; 基于特征描述三角形的层次结构平均查询时间1.510.50图 6查询时间比较记的 XML 文件,测试结果如图 12所示。可以看到实验系统 也能够准确地得到原 XML 文件所有可见的可选标记。4结束语本文对 XML 数据模式的提取提出一种基于二叉树的方 法, 首先抽取出 X