基于GJK的凸体快速连续碰撞检测研究作者：刘丽等来源：《河北科技大学学报》2014年第05期摘要：针对一段时间内的多个运动物体之间的碰撞检测，提出一种基于距离算法（GilbertJohnsonKeerthialgorithm，GJK算法）的凸体快速连续碰撞检测算法，该算法主要通过判断一段时间内两物体之间的最小距离是否为零来检测碰撞发生情况。
首先利用GJK算法在有限步骤内计算得到最小距离，检测两物体是否发生碰撞；若两物体发生碰撞，进而利用raycasting算法确定发生碰撞的精确位置，根据环境要求做出相应响应，调整运动物体位置。
仿真结果表明，对多个运动物体间的连续碰撞检测，该算法有较高的实时性和准确性。
关键词：连续碰撞；GJK算法；运动物体；碰撞检测；凸体中图分类号：TP391.9文献标志码：AAbstract：This paper presents a fast continuous collision detection algorithm to dealing with moving multiple convex objects within a period of time， which is based on the GilbertJohnsonKeerthi algorithm. The algorithm is determined by whether the minimum distance between the two objects within a period of time is zero to detect the occurrence of a collision. First，the algorithm utilizes GJK algorithm to calculate the minimum distance between the two objects and to detect the collision in finite steps. If two objects collide， then， determine the precise collision position of two objects based on the raycasting algorithm， and respond according to the environmental requirements， adjust two objects' location. The simulation results show that this algorithm has high realtime and accurate characteristics for continuous collision detection between multiple moving objects.Key words：continuous collision； GilbertJohnsonKeerthi（GJK） algorithm； moving objects； collision detection； convex objects碰撞检测在计算机图形学、CAD/CAM、虚拟现实、虚拟制造、三维游戏等诸多领域都有广泛的应用，是提高虚拟场景物理真实感的关键问题之一[14]。
按照场景模式不同，碰撞检测主要分为静态检测和动态检测。
动态检测针对场景中至少存在一个运动物体的情况；根据碰撞检测方式的不同，动态检测分为离散检测和连续检测[5]。
离散碰撞检测算法是对运动物体进行取样检测，因此容易造成漏检测，进而产生穿透现象[6]。
针对两物体间的穿透现象，连续碰撞检测算法通过对一段连续时间内物体的运动过程进行建模，判断两物体之间的碰撞情况，可以很好地解决漏检测问题[6]，但计算量相对较大。
目前，虚拟环境的场景复杂度越来越高，对碰撞检测的实时性及准确性的要求也越来越高。
因此，提高检测实时性及准确性是连续碰撞检测要解决的关键问题。
经过多年发展，目前已有多种连续碰撞检测算法，主要有基于扫描实体的算法[78]，应用Minkowski和与球面高斯映射相结合的方法[9]，保守前进算法及其改进算法[10]，基于GJK的算法[1113]以及张应中等提出的线性连续碰撞检测（linear continuous collision detection，LCCD）算法[13]等。
其中，基于扫描实体的方法及应用Minkowski和与球面高斯映射相结合的方法计算量都较大，不适合实时碰撞检测；基于CA及其改进算法虽然提高了检测精度和速度，但其本质仍属于基于步长的碰撞检测；LCCD算法适用于简单凸体之间的碰撞检测。
为提高碰撞检测的快速性及精确度，针对多个凸体之间的连续碰撞检测，本文提出一种基于GJK的快速连续碰撞检测（fast continuous collision detection，FCCD）算法。
该算法以Minkowski差集为工具，可在有限步骤内计算得到两物体间的最小距离，检测两物体是否发生碰撞，加快碰撞检测速度，并利用raycasting算法计算得到凸体间第一次发生碰撞的位置，及时作出碰撞响应。
最后通过仿真对本文算法和LCCD算法进行了比较，仿真结果表明该算法具有较高的实时性和准确性。
1GJK算法概述GJK算法是本文算法的基础，下面对GJK算法涉及到的相关几何理论、概念以及GJK算法的基本理论进行介绍。
1.1相关定义定义1：d单形体是指d维空间内，仿射无关的点集形成的凸包。
如0是单形体是指一个点；1是单形体是指一条线段；2是单形体是指一个三角形；3是单形体是指一个四面体[14]。
GJK算法通过在CSO边界上降序迭代求得CSO中距离原点最近的点。
在每次迭代过程中，在CSO中生成一个单形体，并且确保其所含顶点比上一次迭代中产生的单形体更接近于原点。
定义Wk是在第k次迭代过程中生成的单形体，始终包含1到4个顶点；vk是这个单形体中距离原点最近的点，通过“距离子算法”（或Johnson算法）计算得到vk[14]。
对于凸体对象，GJK算法可通过有限步的迭代运算返回最终结果。
GJK算法的迭代过程如下。
初始条件时，W0=，v0为CSO中任意点。
1）初始化单形体Wk为CSO中一个或多个顶点（最多为4个）。
2）通过距离子算法计算得到vk。
3）若vk为原点，则原点就在CSO中，A，B两物体发生碰撞。
GJK算法结束并返回“A，B相交”。
4）针对Wk中不包含顶点vk的子单形体，将其顶点从单形体中移除。
5）令wk=SA-B（-vk）为-vk方向上的支撑点。
6）与顶点vk比较，若点wk在-vk方向上并非极值点，即‖vk‖2+SA-B（-vk）·（-vk）=0，则结束迭代过程，并返回“A和B不相交”。
由原点指向顶点vk的向量长度‖vk‖即为A和B 之间的距离。
7）否则，将wk添加至单形体Wk中并返回步骤2）。
2快速连续碰撞检测算法本文以GJK算法为基础，通过判断一段时间内2个凸体间判断一段时间内两物体之间的最小距离是否为零来检测是否发生碰撞。
如果两物体发生碰撞，则通过射线与凸体相交的方法得到碰撞发生的位置，根据环境要求做出响应。
本文算法分为2步进行，第1步为碰撞检测，快速检测碰撞是否发生；第2步为碰撞响应，计算碰撞发生的位置。
2.1检测碰撞文献[15]与文献[16]提出了应用GJK算法实时计算二维平面中2个线性运动物体之间的最小距离。
本文对其算法进行推广，应用到检测三维空间中两凸体之间是否发生碰撞。
1）问题描述本算法应用于有多个运动物体的场景，需要对场景中的物体进行两两检测。
为不失一般性，假设场景中的2个运动物体分别为A和B，在时间区间[t0，t1]内，A和B均做匀速直线运动，其速度为常量，分别为vA和vB。
在迭代过程中，若Wk包含一个点，那么，距离子算法返回a，d，Ok，O_in=false。
如果Wk包含2个点，首先检查O是否在2个点的运动轨迹之间，如果运动轨迹之间包含原点，令O_in=true，并停止迭代，返回“A和B碰撞”。
2.2碰撞响应碰撞响应的最终目的是当检测到两物体发生碰撞时，根据环境要求及时调整物体状态，避免发生穿透现象。
因此，碰撞响应需要计算得到碰撞发生时物体的位置。
在时间区间[t0，t1]内，A和B的位移向量分别为T1和T2。
由式（5）和式（6）可得，T1=Δt·vA，T2=Δt·vB。
为简化过程，令物体B处于相对静止状态，因此物体A的相对位移向量（相对于物体B）定义为T=T1-T2。
因此，T=Δt·（vA-vB）。
由定义可得，C=A-B。
在t0时刻，C0=A0-B；在t1时刻，C1=A1-B，又有A1=A0+T。
由此，可得C1=C0+T。
也就是说，在时间区间[0，1]内，CH（C）是运动的，其位移向量与物体A的相对位移向量相同，均为T[13]。
由于CH（C）是运动的，原点是静止的。
为进一步简化计算过程，考虑CH（C）是静止的，原点相对于CH（C）是运动的，其相对位移向量为-T，如图4所示。
由图4可知，碰撞发生时运动物体A的位置可由t0时刻的位置加上一个位移向量得到。
这个位移向量的大小和方向与原点相对路径所在射线与CSO的第一个交点指向原点的向量相等。
因此，在碰撞响应中，最主要的就是要确定射线与CSO的第1个交点[13]。
文献[17]提出了raycasting算法来获得射线与凸体的交点，本文将此算法进行推广，计算原点相对路径所在射线与CSO的第1个交点。
3仿真及分析本文以Microsoft Visual Studio 2010为开发平台，标准C++语言实现算法。
实验环境设置如下：操作系统为Microsoft Windows7；CPU为Intel Core i3 M 330，2.13 GHz；内存为4 GB。
为验证本文算法的有效性及实时性，建立三维场景复杂度不同的场景进行测试。
选取具有多个大小不同的正方体作为实验对象，正方体由程序生成，并且每个正方体移动方向和速度为随机生成，当2个正方体发生碰撞时，物体的颜色由绿色变为红色，当两物体分开后，物体颜色恢复绿色，如图5所示。
通过改变场景中正方体的个数来控制场景复杂度。
当场景中正方体数量为50个时，碰撞检测时间约为0.5 ms，当正方体数量增加到500个时，碰撞检测时间只有4.9 ms，能够满足实时性要求。
通过在不同复杂度下的场景的测试，对本文的快速碰撞检测算法FCCD和张应中等提出的LCCD算法[13]的碰撞检测效率进行了比较，并记录了一段时间内的平均检测时间，仿真实验结果如图6所示。