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

刘 超，蒋夏军，施慧彬

(南京航空航天大学 计算机科学与技术学院，江苏 南京 211100)

0 引 言

近年来，随着虚拟现实技术的快速发展，物体对象之间的碰撞检测已经成为众多学者研究的热点。为了满足虚拟环境的真实性，所有参与者都必须能实时进行交互，而实时进行交互的前提是有效解决碰撞检测问题[1-2]。在3D游戏、虚拟配装、机器人路径规划等众多领域，碰撞检测也有着重要的应用[3]。

基于层次包围盒的碰撞检测算法是一类应用广泛的碰撞检测算法，根据包围盒的种类不同，基于层次包围盒的碰撞检测算法主要有轴向包围盒(AABB)算法、球包围盒(sphere)算法、方向包围盒(OBB)算法、离散方向多面体(K-DOP)算法等[4-5]。此类算法中，每一个待测的模型均对应一个层次包围盒树，树的每个节点代表模型基本组成元素的一个子集，通过检测两个模型的包围盒树节点是否相交，可以判断模型之间相交或者分离，只有当树的叶子节点相交时，模型之间才相交。

算法的运行时间可以用式1表示[6]:

T=Nv*Cv+Np*Cp

(1)

其中，T表示总时长；Nv表示参与测试的包围盒数量；Cv表示测试一对包围盒消耗的时间；Np表示参与测试的模型基本组成元素；Cp表示测试一对基本几何元素消耗的时间。

文中主要讨论刚体模型间的碰撞检测，这些模型的基本组成元素为三角形，根据式1可以通过提高算法中三角形的相交测试的效率来提高整个算法的效率。针对方向包围盒碰撞检测算法，文中对其中三角形之间的相交测试算法进行了一些改进，并且设计了相关实验来验证改进算法的效率。

1 方向包围盒碰撞检测算法

在Gottschalk[6]于1996年实现的“RAPID”碰撞检测系统中，将方向包围盒应用到碰撞检测算法中。虽然OBB包围盒之间的相交测试比较复杂，但因为其良好的紧密性，在一些环境中基于OBB包围盒的碰撞检测算法依然有很高的效率。

1.1 构建方向包围盒

OBB包围盒是一个任意方向的长方体，可以用一个中心点、一个三阶方向矩阵和三个1/2边长表示，其中三阶方向矩阵表示包围盒三条轴的方向。通过计算包围盒内的全部三角形顶点的协方差矩阵C以及矩阵C三个特征向量,可以得到OBB包围盒的三条轴的方向。

假设模型中包含n个三角形，第i个三角形的顶点分别用pi，qi，ri表示，则可以用下面公式得到这n个三角形的均值u：

(2)

然后由u得到协方差矩阵C：

(3)

通过式3得到的协方差矩阵C为一个3*3的对称矩阵，将C的三个特征向量正规化之后得到的基即为OBB的三条轴的方向，最后计算OBB内的三角形的顶点在这三条轴上投影的最大值和最小值即可确定OBB的三条边长。

1.2 OBB之间的相交测试

方向的任意性使得OBB包围盒能更紧密地包围模型，但同时也使得OBB之间的相交测试变得更复杂，一种常见的OBB包围盒之间的相交测试算法是基于分离轴理论(SAT)的算法。根据分离轴理论，若在三维空间中存在一条直线，任意两个凸多面体在这条直线上的投影分离，则这条直线是这两个凸多面体的分离轴。OBB包围盒属于凸多面体，因此在任意两个OBB包围盒之间若存在一条分离轴，则可以确定它们之间分离。对于三维空间两个OBB包围盒，它们之间一共存在15条潜在的分离轴需要检测，这15条分离轴分别是两个包围盒的6条方向轴以及两个包围盒3条方向轴两两组合得到的9条轴，若它们在这15条轴上的投影都不分离，则这两个包围盒之间相交[7]。文献[8]提出了一种采用混合层次包围盒的算法，该算法在包围盒测试阶段并不需要检测方向包围盒的15条分离轴，而只需要检测其中的5条分离轴，大大减少了包围盒的测试时间。

虽然OBB包围盒之间的相交测试可以排除模型之间大量不相交的三角形，但在很多情况下仍需要对大量的三角形之间进行相交测试。

1.3 三角形相交测试算法

对于空间三角形之间的碰撞检测，存在多种算法，这些算法大致可以分为两类:标量判别型算法和矢量判别型算法[9-10]。前者是指通过准确计算来判断三角形之间相交情况的一类算法，这类算法中典型的有Möller[11]算法和Tropp[12]算法；后者是指通过一系列计算值的符号来判定两个三角形的位置关系，然后判断其相交情况的一类算法，例如Guigue&&Deviller[13]算法。在文献[14]中，Wei Lingyu提出了一种基于Tropp算法的改进算法，算法的核心思想是:首先判断三角形B与三角形A所在的平面是否相交，若相交则求出它们的交线,同时根据三角形A的两条边所在的直线将三角形A所在的平面分为四部分，最后根据交线在这四个部分的分布情况判断三角形A与三角形B是否相交。

在OBB包围盒碰撞检测算法中若使用上述几种算法来检测三角形之间是否相交，则这些算法的输入值均为两个三角形的六个顶点坐标，而在模型对象中三角形的顶点坐标是基于模型坐标系的，即用以上算法检测两个三角形之前，需根据两个模型在世界坐标系中的位移信息将两个三角形转换到同一坐标系统中，大量的三角形进行坐标变换操作将会影响整个算法的效率。在OBB包围盒之间的相交测试中，OBB包围盒之间也有类似的坐标转换操作，根据OBB层次包围盒树中叶子节点的OBB包围三角形的特点，可以使用位于同一坐标系中的OBB包围盒的信息来表示待测的三角形坐标，并将所得到的坐标带入上述三角形相交算法中进行测试。对比多种算法后，发现Wei Lingyu的算法更适合文中改进后的算法。

2 改进的三角形相交测试算法

在Wei Lingyu的算法中，三角形之间的测试大致可以分为三个阶段。第一阶段，检测三角形B和三角形A所在的平面是否相交，若相交则计算出相交的线段，下面简称三角形A所在的平面为平面A；第二阶段，根据三角形A两条边所在的直线将平面A分为4部分，并根据交线在平面A的分布情况判断两个三角形是否分离；第三阶段，进一步分析第二阶段无法判断三角形之间分离的情况，检测交线与三角形A是否相交，若交线与三角形A相交则三角形A和B之间相交，反之三角形A和B之间分离。

2.1 计算相交线段

在OBB碰撞检测算法中，层次包围盒树的叶子节点中的每个三角形的包围盒实际上是一个三维空间矩形，如图1所示。这个矩形可以用中心点c，矩形长l，宽d，以及三阶方向矩阵[x,y,z]来表示，向量x和向量y表示矩形两条边的方向，向量z垂直于矩形所在的平面。

图1 叶子节点中的包围盒

在两个矩形(OBB)之间的相交测试中，已经计算出两个矩形变换到同一坐标系的旋转矩阵r[rx,ry,rz]以及平移向量t[t1,t2,t3],其中rx=(rx1,rx2,rx3)。

结合图1，三角形A的坐标和三角形B的坐标可以表示为：

(1)

其中，ai是改进后需要额外计算的值，在计算三角形的包围矩形(OBB)过程中已经得到，即可以在预处理阶段计算出ai的值。在接下来的步骤中，实际并不需要计算出两个三角形的6个坐标值。

假设三角形B的边和平面A之间存在交点，如图2所示。

其中，ri=Bi-A3,i=1,2,3，ej=Aj-A3,j=1,2，因此可以得到等式：

α1e1+α2e2=βijri+βjirj

(2)

其中，βij+βji=1,i

(3)

其中，Di=ri·(e1×e2)，根据上面三角形的坐标信息，容易得到:

(4)

根据式3,只有当Di和Dj有不同的符号(或者其中的一个值为0)时能满足0≤βij,βji≤1，即三角形B的边和平面A存在交点。如果D1,D2,D3的符号相同则表示三角形B和平面A分离，即三角形A和三角形B不相交；如果D1,D2,D3都为0，则表示三角形A和三角形B共面，此时使用共面三角形相交测试算法进行检测，但这种情况通常极少出现。当D1,D2,D3的符号不全相同时，三角形B与平面A存在两个交点，设这两个交点为P1,P2，m1=P1-A3,m2=P2-A3。

图2 三角形B与平面A相交

2.2 计算交点在平面中的位置

在图2中，平面A被向量e1向量e2所在的直线分为4部分，通过比较ei×mi和e1×e2的方向，可以确定Pi在平面A中的位置。例如当e1×m1与e1×e2方向相同且e2×m1与e1×e2方向相反时，P1点位于平面A的第Ⅳ部分，通过同样方法可以确定P2的位置。比较ei×mi与e1×e2的方向后，一共可以得到16种结果，如表1所示。

表1 交点在平面A的分布情况

符号“+”表示ei×mi和e1×e2的方向相同，“-”表示方向相反。其中(+，+)表示Pi位于平面A的第Ⅰ部分，(-，+)表示Pi位于平面A的第Ⅱ部分，(-，-)表示Pi位于平面A的第Ⅲ部分，(+，-)表示Pi位于平面A的第Ⅳ部分，“N”表示两个三角形分离，在Case1～Case4四种情况中，无法直接根据Pi的位置判断待测的三角形是否分离，需要进一步检测交线是否与三角形A相交，如图3所示。

图3 无法直接判断的4种情况

2.3 测试交线与三角形是否相交

若交线P1P2与三角形A相交，则至少满足下面其中一个条件:

(1)P1P2与e1相交；

(2)P1P2与e2相交；

(3)P1P2与e1-e2相交；

(4)P1P2位于三角形A内部。

根据这四个条件，分别讨论Case1～Case4四种情况下P1P2与三角形A相交的情况。

Case1：根据图3中P1与P2的位置关系，条件1、4无法满足，因此只需检测P1P2是否满足条件2或3。检测P1P2与e2是否相交等价于判断e1×e2与(m2-e2)×(m1-e2)的方向是否相同，若两个向量的方向相同，则P1P2与e2相交，否则分离。而当P1P2与e2不相交且P1在三角形A内时，P1P2一定与e1-e2相交。因此在P1P2与e2不相交的情况下，P1在三角形A内部与条件3等价，而判断P1在三角形A内部只需确定向量e1×e2与向量(e2-e1)×(m1-e1)同向。

Case2：若交线P1P2与三角形A相交，则P1P2一定至少与e1和e2中一个向量相交。因此只需检测P1P2是否满足条件1或条件2即可判断交线与三角形A是否相交。类似Case1中的判断方法，P1P2与ei相交等价(m2-ei)×(m1-ei)、e1×e2、m1×m2三者的方向相同。

Case3：若P1P2与三角形A相交，则P1P2只可能满足条件3或者条件4，即P1P2与e1-e2相交或者P1P2位于三角形A内部。而在条件3或条件4中，P1和P2都至少有一点位于三角形A内部，因此在Case3中，P1P2与三角形A相交等价P1和P2中至少有一点存在三角形A内。当(e2-e1)×(mi-e1)与e1×e2方向相同时，Pi在三角形A内部。

Case4：与Case2类似，P1P2只可能与e1和e2相交，但在Case4中，首先比较m1×m2与e1×e2的方向，若两个向量的方向相同，则P1P2只可能与e2相交，方向相反则P1P2只可能与e1相交。

2.4 消除算法中的除法运算

在计算机中，一次除操作所消耗的时间远远高于加法、乘法、减法等运算的时间，因此合理地减少算法中的除法运算能提高整个算法的效率。下面讨论如何避免算法中的除法运算。

整个三角形相交测试的算法中，只有在求三角形B与平面A的交点P1和P2时需要进行除法运算:

令ni=(Di-Dj)，mi=Dirj-Djri,因为Di与Dj异号，可以交换二者的值使Di>Dj，因此mi与ni的方向相同。故在2.2中用ei×ni代替ei×mi与e1×e2的方向进行比较将不会对结果产生影响。同样在2.3中，使用ni代替mi，同时将参与运算但不包含mi的项乘以Di-Dj，例如(e2-e1)×(m1-e1)与(e2-e1)×n1-e2×e1·(Di-Dj)的方向相同。

3 算法的基本运算次数

由于在仿真环境中不同模型的三角形坐标值不在同一个坐标系中，因此使用传统的三角形相交测试算法时必须根据模型的位移信息将待测的三角形转换到同一坐标系中。设A和B分别是模型1和模型2中的两个三角形，模型1和模型2在坐标系中的位移信息分别用四阶矩阵M1和M2表示，则将三角形B的三个点转移到三角形A所在的坐标系的公式为：

(5)

在OBB碰撞检测算法中用OBB包围盒的信息表示待测的三角形，并结合Wei Lingyu的三角形相交测试算法进行测试，因此在改进算法中可以避免上述27次乘法操作和27次加法操作。与Wei Lingyu的算法相比，文中对算法的改进主要集中在第一阶段，即计算D1，D2，D3以及e1×e2的值。在Wei Lingyu的算法中，计算以上结果一共需要进行18次减法操作、33次加法操作和42次乘法操作，其中包括将两个三角形转换到同一个坐标系所需要的27次乘法操作和27次加法操作[14]。而改进算法计算D1，D2，D3以及e1×e2如下：

其中，l1·d1的值只需要计算一次，而a2的值可以在OBB碰撞检测算法的预处理阶段计算得到，所以改进后的算法计算D1，D2，D3以及e1×e2的值只需要6次乘法操作和3次加法操作。与Wei Lingyu的算法相比少了36次乘法操作、30次加法操作以及18次减法操作。改进算法最终一共需要51～57次基本运算操作，这些运算包括加减法、乘法以及比较两个值的大小。而Wei Lingyu的算法一共需进行135～141次基本运算操作[14]，Guigue&&Deviller的算法需要进行168～198次基本运算操作[13]，Möller的算法需要进行178～200次基本运算操作[11]。

4 实验结果

实验使用的硬件环境:i3-4150 CPU，频率3.5 GHz，内存大小4 G。软件环境：Window 7操作系统,Microsoft visual studio 2010开发平台。

一共设计了三组实验来验证改进算法的效率，模型分别选择佛像模型、网格模型以及海绵模型，其中海绵和佛像模型如图4所示。其中佛像模型由125 000

个三角形组成，网格和海绵模型则分别由15 360和91 328个三角形组成。分别验证了模型之间距离为-0.02,-0.01,0.00,0.01四种情况下改进的三角形相交算法的效率，其中当距离为-0.02,-0.01,0.00时，模型之间相交，距离为0.01时，模型之间分离。

图4 海绵、佛像模型

在仿真环境中,决定模型之间的最短距离的值为两个模型中的三角形顶点坐标、模型坐标信息以及模型的旋转矩阵。对于以上四个给定距离，在保持模型之间距离不变的情况下，即两个模型之间的最短距离保持不变，坐标值和旋转矩阵变化，对每个距离下的三组模型都进行了38 304次碰撞测试。实验中每次碰撞测试所使用的模型坐标以及旋转矩阵均由文献[15]中的算法产生。

通过修改RAPID碰撞检测包实现了文中算法，同时使用Möller、Guigue&&Deviller以及Wei Lingyu的三角形相交测试算法来代替RAPID包中原有的基于SAT的三角形相交测试算法，并用这些修改后的RAPID碰撞包检测所得到的结果与改进算法进行比较。

表2显示了模型之间的距离分别为-0.02，-0.01，0.00，0.01时，38 304次碰撞测试中三角形相交测试总的消耗时间。

表2 三角形相交测试消耗的时间

s

根据表2可知，SAT算法判断三角形相交的效率要显著低于其他算法，因此判断凸多面体相交的分离轴算法实际上不适于三角形之间的相交测试。上述几种三角形相交测试算法中，Wei Lingyu的算法的效率要比Guigue&&Deviller算法以及Möller算法的效率高10%～15%左右。对Wei Lingyu的算法进行改进后，改进算法的效率要比Guigue&&Deviller算法以及Möller算法高出40%～45%左右,比Wei Lingyu的算法高出30%～36%左右。

5 结束语

基于传统的方向包围盒碰撞检测算法，重复利用方向包围盒相交测试所得到的中间值，对其中的三角形相交测试算法进行了一些改进，同时在实验结果中发现基于分离轴理论的三角形相交测试算法效率很低，据此推断基于分离轴理论的空间矩形的相交测试算法的效率可能类似于分离轴理论用于测试三角形。而在方向包围盒碰撞检测算法中，叶子节点中的方向包围盒OBB之间的相交测试实际上是空间矩形之间的相交测试，因此基于现存的高效的三角形相交测试算法，可以在以后的工作中尝试找出一种新的空间矩形之间的相交测试算法来代替传统的基于分离轴理论的算法。

参考文献：

[1] 宋城虎，闵 林，朱 琳,等.基于包围盒和空间分解的碰撞检测算法[J].计算机技术与发展，2014,24(1):57-60.

[2] 李 苗.实时碰撞检测算法分析与比较[J].计算机与现代化,2011(6):88-90.

[3] 潘仁宇，孙长乐，熊 伟，等.虚拟装配环境中碰撞检测算法的研究综述与展望[J].计算机科学，2016，43(11A)：136-139.

[4] 赵 伟，曲慧雁.基于云计算Map-Reduce模型的快速碰撞检测算法[J].吉林大学学报:工学版,2016,46(2):578-584.

[5] 马登武，叶 文，李 瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报，2006,18(4):1058-1061.

[6] GOTTSCHALK S,LIN M C,MANOCHA D.OBB-tree:a hierarchical structure for rapid interference detection[C]//Proceedings of the 23rd annual conference on computer graphics and interactive techniques.New York:ACM,1996:170-181.

[7] ERICSON C．实时碰撞检测算法技术[M]．刘天慧，译．北京：清华大学出版社，2010.

[8] CHANG J W,WANG Wenping,KIM M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design，2010,42(1):50-57.

[9] 许 强,吕晓峰,马登武.三角形和三角形相交测试技术研究[J].计算机仿真,2006,23(8):76-78.

[10] 邹益胜,丁国富,何 邕,等.空间三角形快速相交检测算法[J].计算机应用研究，2008,25(10):2906-2910.

[11] MÖLLER T.A fast triangle-triangle intersection test[J].Journal of Graphic Tools,1997,2(2):25-30.

[12] TROPP O,TAL A,SHIMSHONI I.A fast triangle to triangle intersection test for collision detection[J].Computer Animation and Virtual Worlds,2006,17(5):527-535.

[13] GUIGUE P,DEVILLERS O.Fast and robust triangle-triangle overlap test using orientation predicates[J].Journal of Graphics Tools,2003,8(1):25-32.

[14] WEI Lingyu.A faster triangle-to-triangle intersection test algorithm[J].Computer Animation and Virtual Worlds,2014,25(5-6):553-559.

[15] TRENKEL S,WELLER R,ZACHMANN G.A benchmarking suite for static collision detection algorithms[C]//International conference in central European computer graphics,visualization & computer vision.[s.l.]:[s.n.],2007:265-270.