三维视景仿真的包围盒碰撞检测算法优化

李成景，王 洁 ，肖强明，施冬健 ，2

（1.空军工程大学 导弹学院，陕西 三原 710038；2.95196部队，广东 清远 513000）

0 引言

近年来，随着三维视景仿真的发展，碰撞检测问题成为一项重要课题，广泛应用于教育、国防、医学等多个领域。精确的碰撞检测对于如何准确、快速地表现虚拟场景中物体的运动规律和相互关系，保证仿真环境的逼真度有着至关重要的作用。而虚拟环境的复杂性和实时性也要求碰撞检测具有很高的效率。如何保证精确并短时间内完成碰撞检测实际上成为了实时仿真系统的瓶颈之一[1]。目前，国内外研究人员已对虚拟环境下三维视景仿真的碰撞检测进行了深入的研究，并形成一些较为成熟的算法[2]。其中，层次包围盒方法在碰撞检测算法中被广泛使用，一般分为全局搜索与局部检测两个阶段。

层次包围盒方法在全局搜索阶段快速排除多数明显不相交的对象对。在局部检测阶段，首先会遍历对象对的层次包围盒树，逐一检测节点之间是否相交，直到叶节点，以保证能够精确地检测叶节点中所包围的多边形面片是否相交。常用的包围盒中，轴向包围盒（Axis Aligned Bounding Boxes，AABB）的优势在于构造简单，相交测试和包围盒更新迅速，在实际中经常被使用。目前常采用AABB的碰撞检测库主要有I-Collide[3]和Q-Col⁃lide[4]。I-Collide用于大量运动体间的碰撞检测，Q-Col⁃lide是对其改进，当检测的几何模型复杂时，I-Collide会大大提高效率。此外，通用的碰撞检测系统SOLID[5]涉及了模型变形，可适用于变形体间的碰撞检测。I-Collide算法利用包围盒排序法来优化全局搜索过程，文献[6]提出了对排序的改进方法。SOLID算法的局部检测过程采用AABB树进行精确的碰撞检测。本文将利用时空相关性来改进全局搜索过程，并从相交判断算法的角度进行优化，减少执行时间，提高算法效率。

1 碰撞检测优化算法

本文对全局搜索与局部检测两个阶段分别进行分析，在时空相关性，从相交测试算法两方面对算法进行优化。

1.1 全局搜索过程

1.1.1 传统包围盒算法全局搜索过程

在虚拟现实仿真中，传统包围盒法[2]是把复杂的几何对象包裹起来，在进行碰撞检测时，首先进行包围盒之间的相交测试，如果相交，则进行几何对象之间精确的碰撞检测。设虚拟仿真场景中有N个运动对象和M个静止对象，该算法实际上是对（N/2+NM）个对象对分别进行检测，复杂度为O(n2)，并且鉴于AABB的矩形包围盒与包围对象之间往往存在较大空隙，该算法搜索的结果并不是真正的相交，加大了局部检测情况的复杂度。例如，两个几何对象的AABB包围盒在XOY平面的投影如图1所示，尽管包围盒相交，但是两个对象之间并没有相交，使用基本的包围盒算法时，将会继续进行精确的碰撞检测。此时，由于误判导致了无谓的计算，影响算法效率。

1.1.2 包围盒树的构建

在从众多对象中排除不可能相交的对象后，碰撞检测算法会对可能相交的对象对进行精确的碰撞检测。这就需要为对象建立层次包围盒，即包围盒树。一个几何对象的包围盒是包含该对象的一个简单的几何体。对组成对象的基本元素（在本文研究环境下，即为三角形）的集合构造包围盒树一般分为自顶向下和自底向上两种方法。自顶向下的方法在碰撞检测中较常使用，计算成熟，因此本文以此种划分方法为基础进行分析。

该方法选择根节点为全集S，对这个节点进行划分以形成其子节点，直到到达叶节点（基本组成元素）。由于二叉树的相对优势，在通常情况下，选择的包围盒树都为二叉树。该方法构造包围盒树，实际上就是将全集的子集合SV以数目为2划分子集，直到不可划分的基本几何元素为止。

1.1.3 改进的全局搜索过程

为了改善复杂度O(n2)，就需要对场景中的对象进行全局优化搜索，排除当前帧不可能发生碰撞的对象行，只对可能碰撞或上一帧已碰撞的情况进行考察，提高检测效率。针对此思路，本文在包围盒树的根节点处增加Cache字段来存放检测结果（Cache字段包括Cache1和Cache2，分别存储碰撞记录和发生碰撞的几何信息，Cache1以堆栈形式存储固定帧数内的碰撞信息，Cache2实时更新），在本帧的全局搜索阶段，利用上一帧或前几帧局部碰撞检测的结果快速进行碰撞搜索，避免了不必要的碰撞测试，优化了全局搜索过程。

在实时绘制的虚拟环境中，帧与帧之间具有很强的关联性，运动对象的位置和状态不可能急剧变化，比如虚拟手的操作，这就意味着物体从一帧变化到另一帧时是相对静止的。因此，当两个虚拟对象之间发生碰撞时，很可能下一帧中在这两个对象之间发生新的碰撞。测试碰撞时可以首先测试上一帧发生碰撞的地方，同时把上一帧发生碰撞的相关信息缓存在其Cache中，供本次测试使用。改进算法全局搜索的具体步骤为：

1）将场景中对象按序编号，进行活动对象的相交测试。若包围盒相交，则把编号大的对象放入编号小的对象Cache1中。

2）检查运动对象的Cache1字段，若为空，进行下一对象的检测。

3）检测该对象Cache2中是否有相关碰撞的信息。若能检测到对象间的碰撞信息，则直接构造包围盒树，对上次发生碰撞的几何元素及其兄弟子树进行检测。否则，用传统的层次包围盒间的碰撞算法进行检测。若无碰撞，进行下一对象检测。

4）若检测到碰撞，把碰撞信息覆盖到Cache2中，并在Cache1中记录当前碰撞。返回步骤2），继续循环。

随着碰撞次数的增加，Cache中存放的碰撞信息将会保证能够较早检测到碰撞，因此减少了参与搜索的包围盒数，节省了检测的时间，并且如果步骤3）中检测到精确的碰撞信息，则可省去对该对象的局部精确检测过程。

1.2 局部检测过程

1.2.1 传统包围盒局部检测过程

包围盒方法在从众多复杂的对象中排除不可能相交的对象后，将构造包围盒树，对可能相交的对象对进行进一步的碰撞检测。传统算法局部检测过程的核心就是通过遍历检测对象的包围盒树，确定在当前两个对象是否发生碰撞。算法用一个对象的包围盒树的根节点遍历另一个对象的包围盒树，若能到达叶节点，再用该叶节点遍历第一个对象的包围盒树，如果同样能到达叶节点，则继续进行基本元素的相交测试。如果两个节点上的包围盒不相交，就不需对其中的元素再做进一步的相交测试。

1.2.2 基于垂线的相交测试算法

传统包围盒法叶节点的遍历过程主要是检测碰撞双方的AABB树的叶节点与叶节点、叶节点与内部节点、内部节点与内部节点。若是叶节点相交，则显然增加了时间开销。本文提出的基于垂线的相交测试算法即为三角形与内部节点之间的快速测试算法。应用基于垂线的相交测试算法，可直接进行三角形与内部节点间的相交测试，省去两叶节点包围盒求交的计算过程，提高检测效率。

基于垂线的相交测试算法是将待检测的对象坐标平面进行投影，通过碰撞标志Flag（默认为0）的值，判断物体模型是否发生了碰撞：Flag=1，发生碰撞；Flag=0，未发生碰撞。分别记为Flag1（XOY平面），Flag2（XOZ平面），Flag3（YOZ平面），当三者同时为1时，则Flag=1。设检验对象为A和B，基本步骤为：

1）对象A的三角形遍历B内部节点包围盒进行相交测试，若不相交，Flag=0，退出循环。

2）将三角形与B包围盒在XOY轴投影，在相交区域内以等距作Y轴（或X轴）垂线，如图2所示，计算等距线与物体投影线的交点个数。

3）若第n条垂线与两物体的投影线只有一个交点，画出两条投影线的包围矩形，减小区域。

4）若第n条垂线与物体A和物体B的投影线都有交点，分别记为PAi(x,yAi)和PBi(x,yBi)，其中i=1或2。判断i的取值。（1）当i=1时。若yA1

5）若有Flagi=0，Flag=0，结束算法。否则算法转到尚未检测的坐标平面从步骤1）继续判断，若Flag1=Flag2=Flag3=1，Flag=1，结束算法。

1.2.3 优化算法描述

节点之间的相交测试流程程序如下：

2 三维视景仿真结果及分析

实验使用通用SOLID软件包，由Van den Bergen[5]研究并发布，采用AABB包围盒法。将代码修改为本文算法，在根节点增加Cache字段，并利用基于垂线的相交测试算法来简化计算。在PC平台（CPU为Pentium43.0 GHz，内存为1 Gbyte）构造立方体在有限空间内进行随机运动的场景来测试算法的有效性。其中一个场景如图3所示，其三角面数16 461，红色立方体对表示发生碰撞。将本文的改进算法与SOLID软件包提供的AABB包围盒碰撞检测算法进行对比测试。

三角面片数与平均检测时间变化曲线如图4所示，可以看出，随着三角面片数的增加，优化算法的平均碰撞检测时间较之传统AABB算法碰撞检测时间的上升缓慢，并且优势愈见明显，并且由于利用了时空相关性原理，在多运动物体碰撞检测条件下更具优势。实验结果体现了该算法的优越性。

3 小结

本文针对层次包围盒方法，利用时空关联性，增加Cache字段存储碰撞信息，优化全局搜索阶段，并利用快速相交测试减少局部检测的时间，提高了检测速度。在多面片多运动对象的复杂场景中，改进效果更明显。由仿真实验可知，该算法有效可行，是一种效率较高的三维视景仿真碰撞检测算法。

[1]李芙玲，张瑾.碰撞检测技术研究[J].华北科技学院学报，2004（2）：71-73.

[2]LI C F，FENG Y T，OWEN D R J.SMB：collision detection based on temporal coherence[J].Computer Methods in Applied Mechanics and Engineering，2006，195：2252-2269.

[3]PONAMIG M，MANOCHA D，LIN M.Incremental algorithm for collision detection between polygonal models[J].IEEE Trans.Visualization and Computer Graphics，1997，3（1）：51-64.

[4]CHUNG K.An efficient collision detection algorithm for polytopes in virtual environments[EB/OL].[2011-02-21].http：//i.cs.hku.hk/GraphicsGroup/projects/collision/chung_thesis96.pdf.

[5]VAN DEN BERGEN G.Efficient collision detection of complex deformable models using AABB trees[EB/OL].[2011-02-21].http：//www.cs.cmu.edu/～djames/pbmis/etc/jgt98deform_AABB.pdf.

[6]董峰，王同洋.虚拟环境中的快速碰撞检测算法[J].计算机工程与应用，2003（8）：66-67.