碰撞检测技术研究综述

冯立颖

摘 要： 碰撞检测在图形学、仿真、动画和虚拟现实等技术中得到广泛的研究，这些研究具有十分重要的意义。文章对二维空间中多边形等面模型间相交，以及三维空间中多面体等体模型间干涉的角度对碰撞检测技术的研究和发展作了较为全面的论述，并对几种常用的碰撞检测算法进行了分析和比较，最后对碰撞检测算法的发展方向提出了几点建议。

关键词： 虚拟现实； 碰撞检测； 层次包围盒； 干涉

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2014）08-07-04

A survey on collision detection technology

Feng Liying

（Information Technology Office of YanShan University， Qinhuangdao， Hebei 066004， China）

Abstract： The collision detection problem among objects is widely studied in graphics， simulation， animation and virtual reality technologies. A comprehensive introduction of study and development of the problem is given from the aspects of the intersection between face models in 2D， such as polygon， and the interference between body models in 3D， such as polyhedron. Some collision detection algorithms are briefly analyzed and compared. Some suggestions of development of collision detection algorithms are proposed.

Key words： virtual reality； collision detection； bounding volume hierarchies； interference

0 引言

数字化、信息化是当今国内外高科技发展的潮流和趋势，随着计算机软硬件技术的快速发展，尤其是图形处理器以及与之相关的三维游戏，虚拟仿真等技术的兴起，碰撞检测技术再次成为计算机仿真领域研究的热点之一。在虚拟仿真系统中，如果物体间发生碰撞，系统必须实时而准确地检测到这些碰撞并作出相应的碰撞响应[1]，否则物体间就会产生穿透现象，影响虚拟场景的真实性。以前在自动装配规划以及路径规划等领域中，为了检测场景中的物体之间或零件之间是否发生碰撞，产生了许多碰撞检测算法，而后有关专家在碰撞检测的理论和应用方面做了一系列的实验，并得到了许多有重要价值的研究结果。

近二三十年来，国内外研究人员在碰撞检测领域中做了大量有意义的工作，经过细致的研究和实验验证之后，得到了许多实用的碰撞检测算法，对虚拟现实技术的快速发展起到了积极的推动作用。本文将从二维平面和三维空间两个方面对碰撞检测技术进行较为详尽的论述。

1 二维空间碰撞检测问题

二维空间中的碰撞检测几乎是所有碰撞检测算法不可回避的问题，它是指三角形、多边形等面模型之间的求交问题，是三维空间中精确碰撞检测的必经阶段[2]。近几十年来，许多专家学者对平面碰撞问题进行了深入的研究，并取得一些满意的结果，提出了许多优秀的算法。

Chin和Wang两人研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸n边形和一个简单非凸m边形的相交问题的最优算法[3]，并且研究了当两个多边形相交时，一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为O（m+n）。

曲吉林采用平面扫描算法，解决了平面内任意简单多边形平移时碰撞部位的判定问题[4]。平面内任意两个互不相交的简单多边形，若其中一个多边形沿某一方向平移时与另一个多边形碰撞，采用平面扫描法，通过提取多边形的单调链，给出了求其碰撞部位的算法。与现有的算法相比，降低了时间复杂性。

覃中平、张焕国研究了平面内两个互不相交的凸多边形，若其中一个凸多边形沿某一方向与另一个凸多边形相碰撞，采用折半搜索技术来确定凸多边形相碰撞时两者最初相碰撞的顶点和边[5]，并且提出了时间复杂度為O（logm+logn）的优秀算法。

汪嘉业利用单调折线研究了在一个多边形的凸包和另一个多边形不相交的条件下，确定两个多边形是否碰撞，并在碰撞时确定全部碰撞部位的问题[6]，提出了时间复杂度为O（m+n）的最优算法，并且其算法还可推广到确定包含有圆弧边的多边形之间的最初碰撞部位。

申静波，唐国维等人提出了基于夹边边对的空间平面凸多边形快速相交检测算法[7]，并将算法的应用对象从三角形扩展到任意空间平面凸多边形，直接进行多边形间求交计算。该算法在确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对的基础上，根据计算结果求取两组边对间对应夹边的符号距离，以此判断两个多边形是否相交。

2 三维空间中碰撞检测问题

从空间域的角度来划分，碰撞检测算法大体可分为两大类：一类是基于图象空间的碰撞检测算法；另一类是基于物体空间的碰撞检测算法。这两类算法的区别在于，前者是利用物体二维投影的图象加上深度信息来进行相交分析，后者则是利用物体三维几何特性进行求交计算。

2.1 基于图像空间的碰撞检测算法

基于图象空间的碰撞检测算法的基本思想是利用图形硬件将三维几何对象投影到二维图像平面，同时利用深度缓存进行深度测试，以判断对象之间是否发生碰撞。但是基于图象空间的碰撞检测算法由于其检测结果的不精确性和依赖硬件支持而一直发展较慢。近十几年，随着图形硬件技术的飞速发展，图形加速卡在性能不断迅速提高的同时甚至出现了可编程的功能。在碰撞检测的研究中，人们开始将三维几何物体通过投影绘制到图像平面上，得到一个二维的图像空间，然后分析该空间中保存在各类缓存的信息，进而检测出物体之间是否发生干涉[8]。这类算法优势在于能有效利用图形硬件加速技术来减轻CPU的计算负担，从而达到提高算法效率的目的。

Shinya和Forgue等[9]提出在绘制凸体的同时，保存视窗口中每个象素上物体的最大和最小深度序列，并将它们按大小顺序排列，然后检测物体在某一象素上的最大深度值是否与其最小深度值相邻来判别相交情况。虽然图形硬件可以支持物体最大/最小深度的计算，但该方法并不实用，因为它要求大量的内存来保存深度序列，而且从图形硬件中读取深度值本身就非常费时。

Gress等[10]利用GPU的可编程性，将碰撞检测计算映射到GPU的顶点处理器和片段处理器中，通过实施绘制完成碰撞检测计算，再通过遮挡查询获得碰撞检测结果。该算法既保证了碰撞检测的准确性，同时也充分利用了GPU强大的并行计算能力。

Govindaraju等[11]利用图形硬件进行初步检测阶段，迅速剔除大规模场景中明显不发生碰撞的物体；然后利用几何结构下的快速相交检测算法得到精确的碰撞检测结果。该算法在处理虚拟场景中多物体间初期碰撞检测方面能取得不错的效果。

Heidelberger等[12]利用面向体表示的方法，提出了一种能够处理可变形物体的碰撞检测算法。该算法首先将两物体的相交区域按层次深度分解为层次深度图（layered depth image）；然后通过图形硬件绘制过程来判断两物体在层次深度图的每个像素上是否有相交区间存在，从而确定物体是否发生碰撞。此算法不适合大规模物体间的碰撞检测。

2.2 基于物体空间的碰撞检测算法

三维空间中碰撞检测问题与二维空间碰撞检测问题相比要复杂得多，目前，基于三维空间的碰撞检测算法主要分为三类：距离跟踪法、空间分解法（或空间剖分法）、层次包围盒法。

2.2.1 距离跟踪法

距离跟踪法是通过寻找和跟踪两个多面体之间的最近点来计算它们之间的距离。当距离小于等于零时，发生碰撞；否则没有发生碰撞。当物体的运动速度不快，相邻帧間运动物体的位移变化很小时，可以利用帧间的连续性来增量式的计算物体间的距离。

最早出现的跟踪算法是Lin-Canny算法[13]，它从上次得到的最近特征对开始，沿多面体的表面移动，直到找到新的最近特征。显然，这种算法依赖于相邻两次最近特征的距离，即模型的相干性。如果相干性越高，那么算法的效率越高；相反相干性越低，算法效率就越低。

Enhanced GJK算法[14]是在GJK算法上改进而成。GJK算法是一个跟踪计算两凸多面体间的最短距离的算法，与Lin-Canny算法不同的是，GJK不是直接对两凸多面体进行搜索和跟踪，而是在他们的明氏距离多面体参数空间中搜索跟踪执行，它具有线性时间复杂度；Enhanced GJK算法将原GJK算法的时间复杂度改进为近乎常量级，达到与Lin-Canny算法的同等水平。Enhanced GJK采用了“爬山法”迭代算法求解，使时间复杂度大大降低，基本呈线性，大大减少了运算时间。

2.2.2 空间剖分法

空间剖分法是将整个虚拟空间划分成相等体积的小单元格，只对占据同一单元格或相邻单元格的几何对象进行相交测试。适用于物体在空间中均匀分布的稀疏环境。

Ganter和Isarankura发展了单步检测方法，提出了一种空间分割技术的方法[15]，这种空间分割技术将包含物体的空间划分为一个个子空间，将所有的测试限制在两个物体的重叠局部区域来进行，并且在重叠区域内的所有的子空间都按照最小、最大值来排序，从而进一步减少测试的时间。

Fuch和Kedem提出二叉空间分割BSP（Binary Space Partition）即空间任何一个平面，都可以将它所在的空间分割为两个互不相交的子空间，空间中其他平面均可划归在某一子空间中。同样，某一子空间中任一平面可以将该空间分为另外两个互不相交的子空间。如此递归分割，将每次分割平面加入二叉树节点，即可形成一棵描述场景层次结构的BSP树。BSP树碰撞检测算法是在虚拟场景中的两个对象间找出分割平面以判断两个对象是否相交。若两个对象间存在分割平面，则没有发生碰撞；否者，发生了碰撞。

2.2.3 层次包围盒法

层次包围盒算法是利用体积略大而几何特性简单的包围盒来近似地描述相对复杂的虚拟对象，进而通过构造树状层次结构可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性，从而只需对包围盒重叠的部分进行进一步的相交测试。与一个物体相对应的层次结构的节点是空间上包围该物体一部分几何对象的几何近似体（包围盒）：层次结构的根节点包围了整个物体，每个父节点包围的几何对象是它的所有子节点包围的几何对象之和，节点从上到下逐渐逼近它包围的几何对象。利用层次包围盒方法进行碰撞检测时，首先测试几何对象的包围盒是否相交，如果包围盒不相交，则被包围的对象就不相交；只有包围盒相交时，才对其所包裹的几何对象做进一步相交测试。

目前，比较典型的包围盒类型有包围球（Sphere）、轴向包围盒AABB（Axis-Aligned Bounding Box）、方向包围盒OBB（Oriented Bounding Box）以及离散有向多面体k-DOPs（Discrete Orientation Polytopes）等。

包围球（Sphere）[16]是简单性好紧密性差的一类包围盒，一个给定对象的包围球被定义为包含该对象的最小的球体。计算给定对象的包围球，首先需分别计算对象的基本几何元素集合中所有元素的顶点的x、y、z坐标均值以确定包围球的球心c，再由球心与三个最大值坐标所确定的点与点之间的距离计算半径r。包围球确定的区域为：R={（x，y，z）T|（x-cx）2+（y-cy）2+（z-cz）2

轴向包围盒AABB（axis-aligned bounding box）[17]是最早的一类包围盒，在碰撞检测的研究历史中使用得最广，一个物体的AABB被定义为包含该对象且边平行于坐标轴的最小正六面体。对于给定的对象，它的AABB仅需六个标量描述，即组成物体基本几何元素的顶点的x坐标、y坐标以及z坐标的最大值和最小值。AABB间的重叠测试比较简单，两个AABB重叠当且仅当它们在三个坐标轴上的投影区间均重叠，则它们是相交的。

OBB包围盒层次（Oriented Bounding Box）是紧密型好、相交测试复杂的一类包围盒[18]。一个给定对象的OBB被定义为包含该对象且相对于坐标轴方向任意的最小的正六面体。OBB最大特点是它的方向的任意性，这使得它可以根据被包围对象的形状特点尽可能紧密地包围对象，但同时也使得它的相交测试变得复杂。OBB间的相交测试基于分离轴理论，若两个OBB在一条轴线上（不一定是坐标轴）上的投影不重叠，则这条轴称为分离轴，若一对OBB间存在一条分离轴，则可以判定这两个OBB不相交，否则它们是相交的。

离散有向多面体k-DOPs（Discrete Orientation Polytopes）[19]是由纽约州立大学的James T、Klosowski等人提出的。一个对象的k-DOPs被定义为包含该对象且它的所有面的法向量都来自一个固定方向（k个向量）的集合的凸包，其中的方向向量为共线且方向相反的向量对。一个几何对象的k-DOPs可以通过计算对象的顶点与固定方向集D中的各个方向的最大点积得到。D中有k/2对方向相反的向量对，k-DOPs在每对向量上的最大延伸确定了它在该对向量上的投影区间，一个k-DOPs包围盒完全可由描述它在这些向量对上的k/2个投影区间所确定。因此，k-DOPs包围盒间的相交测试可以通过投影区间的重叠测试来完成，只要两个k-DOPs包围盒在D中某一個方向对上的投影区间不重叠，就可以判定它们是不相交的；否则认为它们是相交的。

2.2.4 基于物体空间的碰撞检测算法的分析比较

目前，在物体空间的碰撞检测的算法中，距离跟踪法依赖于相邻两次最近特征的距离，即模型的相干性。如果相干性越高，那么算法的效率越高；相反，相干性越低，算法效率就越低。这就使得算法具有了不稳定性，其健壮性也受到影响。空间剖分法由于只适合于物体在空间均匀分布的稀疏环境，简单地从大量物体中排除不相交的物体。但对于一般的环境，很难选择一个最优的剖分尺寸，若选择不当，会导致空间耗费大，计算效率降低，因此空间剖分法有一定的局限性，是一种较少用到的方法。与上述两种算法相比，层次包围盒法是碰撞检测算法中一种被广泛使用的方法，在对物体进行碰撞检测时，首先进行包围盒间的相交测试，由于包围盒间的求交过程比物体间求交过程简单，所以可以尽早地排除大量不相交的物体，节省碰撞检测的时间，提高碰撞检测的效率。对研究人员来说，这种方法无疑是一种较好的选择。但是，这种方法也有它的缺点，当被检测的对象的变得越来越复杂时，构建包围盒树会占用大量存储空间的同时，也会增加参与相交测试包围盒的数量，因此会耗费大量存储空间和相交测试的时间。

3 结束语

在虚拟环境中，碰撞问题一直是经典而关键的问题之一，因而得到很多专家学者的关注和研究，他们提出了各种各样的方法来提高检测算法的效率和鲁棒性。作者认为在以后研究中可以从以下几个方面入手。

⑴ 层次包围盒法是一种被研究人员广泛使用的算法，利用该方法对物体间进行相交测试时，在大多情况下都会立即产生无碰撞结论。因此节省包围盒间相交测试的次数和相交测试的时间是提高检测效率的有效途径，所以研究者可以采用混合的包围盒方法，即外层采用紧密性差、相交测试简单的包围盒，如包围球，而里层采用紧密性好、相交测试复杂的包围盒，如OBB，在解决实时碰撞检测问题时不失为一个有效的方法。

⑵ 基于图像的碰撞检测算法属于较新的一类算法。但曾经由于受到图形硬件发展的限制，研究进展相对比较缓慢。随着图形硬件的发展才得以重新进入研究者的视野，国外有一批研究者正在进行该方面的研究，包含了碰撞检测领域，国内在这方面的研究尚属起步阶段，成果较少。CPU与GPU间的负载平衡问题有待进一步研究，以提高算法效率。该类算法由于其本身的优势，特别是随着图形硬件的飞速发展，具有广阔的研究前景和研究价值。

⑶ 利用多核CPU并行计算的功能来提高碰撞检测的效率。随着计算机硬件的不断发展，双核，四核，甚至多核CPU应运而生，通过把多核CPU并行计算，以及数据分块思想应用到碰撞检测算法之中，以静态和动态任务分配策略相结合的方法来提高算法的并行度，从而达到提高碰撞检测速度的目的。其核心问题是如何找出更好的动态任务分配策略以完全实现CPU间负载均衡，这是今后一个研究方向。

总之，碰撞检测技术仍有许多方面需要进一步探讨和研究，包括软体模型、复杂模型之间的碰撞、框架与框架之间的空间一致性，以及接触和干涉之间的区分等问题。因此，需要研究者不断仔细钻研，拓宽思路，设计出更高效的算法，才能满足虚拟场景中大量复杂物体之间碰撞检测实时性的要求。

参考文献：

[1] 何雪薇，龚光红.虚拟人运动的动力学实现方法研究[C]. 2003全国

系统仿真年会论文集.西安：中国系统仿真学，2003：614-619

[2] 王志强，洪嘉振，杨辉.碰撞检测问题研究综述[J].软件学报，1999.10

（5）：545-551

[3] F.Chin， C.A.Wang. Optimal Algorithms for the Intersection and

the Minimum Distance Problems between Planar Polygons. IEEE Transactions on Computers，1993.C-32（12）：1203-1207

[4] 曲吉林.确定任意简单多边形平移时碰撞部位的扫描算法[J].计算机

学报，2000.23（7）：692-1698

[5] 覃中平，张焕国.确定凸多边形平移时最初碰撞部位的最优算法[J].

计算机学报，1992.15（3）：171-177

[6] 汪嘉业.平面上简单多边形平移时确定碰撞部位的最优算法[J].计算

机学报，1992.15（8）：582-588

[7] 申静波，唐国维，李井辉.基于夹边边对的凸多边形间快速相交检测

算法[J].计算机工程与科学，2007.29（12）：93-94

[8] N.K. Govindaraju， M.C. Lin， D. Manocha. Fast and reliable

collision culling using graphics hardware[J].IEEE Transactions on Visuallization and Computer Graphics，2006.12（2）：143-154

[9] M. Shinya， M. Forgue. Interference Detection through Rasteriza-

tion. Journal of Visua-lization and Computer Animation，1997.2（8）：131-134

[10] A. Gress， G. Zachmann. Object-space interference detection on

programmable graphics hardware[C]. SIAM Conference on Geometric Design and Computing Washington. DC： Nashboro Press，2006：13-17

[11] GOVINDARAJU N K， LINM C， MANOCHA D.Quick-

CULLIDE： fast inter-and intra-object collision culling using graphics hardware[C] //Proc of IEEE Virtual Reality，2005：59-66

[12] HEIDELBERGER B， TESCHNER M， GROSS M.Volumetric

collision detection for derformable objects， TR395[R].Zurich， Switzerland： Computer Science Department ETH，2003.

[13] M. C. Lin， J. F. Canny. A Fast Algorithm for Incremental

Distance Calculation. In Proceedings of the IEEE International Conference on Robotics and Automation， Sacramento， CA，1991：1008-1014

[14] V. Gino， B. Den. A Fast and Robust GJK Implementation for

Collision Detection of Convex Objects. http：//www.win.tue.nl/cs/tt/gino/solid/index.html，1999.8（4）：11-17

[15] M. A. Ganter， B. P. Isarankura. Dynamic Collision Detection

Using Space Partitioning. Journal of Mechanical Design， Transactions of the ASME，1993.115（1）：150-155

[16] I. J. Palmer， R. L. Grimsdale. Collision Detection for Animation

Using Sphere-Trees. Computer Graphics Forum，1995.14（2）：105-116

[17] 馬登武，叶文，李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学

报，2006.18（4）：1058-1061

[18] S. Gottschalk， M. C. Lin， D. Manocha. OBB-Tree： A

Hierarchical Structure for Rapid Interference Detection. In Proc. the ACM of SIGGRAPH'96，1996：171-180

[19] J. T. Klosowski， M. Held， J. S. B. Mitchell， et al. Efficient

Collision Detection Using Bounding Volume Hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics，1998.4（1）：21-36

[20] YU Chun-yan， YE Dong-yi， WU Ming-hui， et al. A new

horizonal collision detection scheme for avatar with avatar in collaborative virtual environment[C] //Proc of the 4th International Conference on Machine Learning and Cybernetics，2005：4961-4966

[21] 邹益胜，丁国富，许明恒.实时碰撞检测算法综述[J].计算机应用研

究，2008.5（1）：8-11