基于OBB包圍盒碰撞檢測算法的改進

劉 超，蔣夏軍，施慧彬

(南京航空航天大學 計算機科學與技術(shù)學院，江蘇 南京 211100)

0 引 言

近年來，隨著虛擬現(xiàn)實技術(shù)的快速發(fā)展，物體對象之間的碰撞檢測已經(jīng)成為眾多學者研究的熱點。為了滿足虛擬環(huán)境的真實性，所有參與者都必須能實時進行交互，而實時進行交互的前提是有效解決碰撞檢測問題[1-2]。在3D游戲、虛擬配裝、機器人路徑規(guī)劃等眾多領(lǐng)域，碰撞檢測也有著重要的應(yīng)用[3]。

基于層次包圍盒的碰撞檢測算法是一類應(yīng)用廣泛的碰撞檢測算法，根據(jù)包圍盒的種類不同，基于層次包圍盒的碰撞檢測算法主要有軸向包圍盒(AABB)算法、球包圍盒(sphere)算法、方向包圍盒(OBB)算法、離散方向多面體(K-DOP)算法等[4-5]。此類算法中，每一個待測的模型均對應(yīng)一個層次包圍盒樹，樹的每個節(jié)點代表模型基本組成元素的一個子集，通過檢測兩個模型的包圍盒樹節(jié)點是否相交，可以判斷模型之間相交或者分離，只有當樹的葉子節(jié)點相交時，模型之間才相交。

算法的運行時間可以用式1表示[6]:

T=Nv*Cv+Np*Cp

(1)

其中，T表示總時長；Nv表示參與測試的包圍盒數(shù)量；Cv表示測試一對包圍盒消耗的時間；Np表示參與測試的模型基本組成元素；Cp表示測試一對基本幾何元素消耗的時間。

文中主要討論剛體模型間的碰撞檢測，這些模型的基本組成元素為三角形，根據(jù)式1可以通過提高算法中三角形的相交測試的效率來提高整個算法的效率。針對方向包圍盒碰撞檢測算法，文中對其中三角形之間的相交測試算法進行了一些改進，并且設(shè)計了相關(guān)實驗來驗證改進算法的效率。

1 方向包圍盒碰撞檢測算法

在Gottschalk[6]于1996年實現(xiàn)的“RAPID”碰撞檢測系統(tǒng)中，將方向包圍盒應(yīng)用到碰撞檢測算法中。雖然OBB包圍盒之間的相交測試比較復(fù)雜，但因為其良好的緊密性，在一些環(huán)境中基于OBB包圍盒的碰撞檢測算法依然有很高的效率。

1.1 構(gòu)建方向包圍盒

OBB包圍盒是一個任意方向的長方體，可以用一個中心點、一個三階方向矩陣和三個1/2邊長表示，其中三階方向矩陣表示包圍盒三條軸的方向。通過計算包圍盒內(nèi)的全部三角形頂點的協(xié)方差矩陣C以及矩陣C三個特征向量,可以得到OBB包圍盒的三條軸的方向。

假設(shè)模型中包含n個三角形，第i個三角形的頂點分別用pi，qi，ri表示，則可以用下面公式得到這n個三角形的均值u：

(2)

然后由u得到協(xié)方差矩陣C：

(3)

通過式3得到的協(xié)方差矩陣C為一個3*3的對稱矩陣，將C的三個特征向量正規(guī)化之后得到的基即為OBB的三條軸的方向，最后計算OBB內(nèi)的三角形的頂點在這三條軸上投影的最大值和最小值即可確定OBB的三條邊長。

1.2 OBB之間的相交測試

方向的任意性使得OBB包圍盒能更緊密地包圍模型，但同時也使得OBB之間的相交測試變得更復(fù)雜，一種常見的OBB包圍盒之間的相交測試算法是基于分離軸理論(SAT)的算法。根據(jù)分離軸理論，若在三維空間中存在一條直線，任意兩個凸多面體在這條直線上的投影分離，則這條直線是這兩個凸多面體的分離軸。OBB包圍盒屬于凸多面體，因此在任意兩個OBB包圍盒之間若存在一條分離軸，則可以確定它們之間分離。對于三維空間兩個OBB包圍盒，它們之間一共存在15條潛在的分離軸需要檢測，這15條分離軸分別是兩個包圍盒的6條方向軸以及兩個包圍盒3條方向軸兩兩組合得到的9條軸，若它們在這15條軸上的投影都不分離，則這兩個包圍盒之間相交[7]。文獻[8]提出了一種采用混合層次包圍盒的算法，該算法在包圍盒測試階段并不需要檢測方向包圍盒的15條分離軸，而只需要檢測其中的5條分離軸，大大減少了包圍盒的測試時間。

雖然OBB包圍盒之間的相交測試可以排除模型之間大量不相交的三角形，但在很多情況下仍需要對大量的三角形之間進行相交測試。

1.3 三角形相交測試算法

對于空間三角形之間的碰撞檢測，存在多種算法，這些算法大致可以分為兩類:標量判別型算法和矢量判別型算法[9-10]。前者是指通過準確計算來判斷三角形之間相交情況的一類算法，這類算法中典型的有M?ller[11]算法和Tropp[12]算法；后者是指通過一系列計算值的符號來判定兩個三角形的位置關(guān)系，然后判斷其相交情況的一類算法，例如Guigue&&Deviller[13]算法。在文獻[14]中，Wei Lingyu提出了一種基于Tropp算法的改進算法，算法的核心思想是:首先判斷三角形B與三角形A所在的平面是否相交，若相交則求出它們的交線,同時根據(jù)三角形A的兩條邊所在的直線將三角形A所在的平面分為四部分，最后根據(jù)交線在這四個部分的分布情況判斷三角形A與三角形B是否相交。

在OBB包圍盒碰撞檢測算法中若使用上述幾種算法來檢測三角形之間是否相交，則這些算法的輸入值均為兩個三角形的六個頂點坐標，而在模型對象中三角形的頂點坐標是基于模型坐標系的，即用以上算法檢測兩個三角形之前，需根據(jù)兩個模型在世界坐標系中的位移信息將兩個三角形轉(zhuǎn)換到同一坐標系統(tǒng)中，大量的三角形進行坐標變換操作將會影響整個算法的效率。在OBB包圍盒之間的相交測試中，OBB包圍盒之間也有類似的坐標轉(zhuǎn)換操作，根據(jù)OBB層次包圍盒樹中葉子節(jié)點的OBB包圍三角形的特點，可以使用位于同一坐標系中的OBB包圍盒的信息來表示待測的三角形坐標，并將所得到的坐標帶入上述三角形相交算法中進行測試。對比多種算法后，發(fā)現(xiàn)Wei Lingyu的算法更適合文中改進后的算法。

2 改進的三角形相交測試算法

在Wei Lingyu的算法中，三角形之間的測試大致可以分為三個階段。第一階段，檢測三角形B和三角形A所在的平面是否相交，若相交則計算出相交的線段，下面簡稱三角形A所在的平面為平面A；第二階段，根據(jù)三角形A兩條邊所在的直線將平面A分為4部分，并根據(jù)交線在平面A的分布情況判斷兩個三角形是否分離；第三階段，進一步分析第二階段無法判斷三角形之間分離的情況，檢測交線與三角形A是否相交，若交線與三角形A相交則三角形A和B之間相交，反之三角形A和B之間分離。

2.1 計算相交線段

在OBB碰撞檢測算法中，層次包圍盒樹的葉子節(jié)點中的每個三角形的包圍盒實際上是一個三維空間矩形，如圖1所示。這個矩形可以用中心點c，矩形長l，寬d，以及三階方向矩陣[x,y,z]來表示，向量x和向量y表示矩形兩條邊的方向，向量z垂直于矩形所在的平面。

圖1 葉子節(jié)點中的包圍盒

在兩個矩形(OBB)之間的相交測試中，已經(jīng)計算出兩個矩形變換到同一坐標系的旋轉(zhuǎn)矩陣r[rx,ry,rz]以及平移向量t[t1,t2,t3],其中rx=(rx1,rx2,rx3)。

結(jié)合圖1，三角形A的坐標和三角形B的坐標可以表示為：

(1)

其中，ai是改進后需要額外計算的值，在計算三角形的包圍矩形(OBB)過程中已經(jīng)得到，即可以在預(yù)處理階段計算出ai的值。在接下來的步驟中，實際并不需要計算出兩個三角形的6個坐標值。

假設(shè)三角形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)，根據(jù)上面三角形的坐標信息，容易得到:

(4)

根據(jù)式3,只有當Di和Dj有不同的符號(或者其中的一個值為0)時能滿足0≤βij,βji≤1，即三角形B的邊和平面A存在交點。如果D1,D2,D3的符號相同則表示三角形B和平面A分離，即三角形A和三角形B不相交；如果D1,D2,D3都為0，則表示三角形A和三角形B共面，此時使用共面三角形相交測試算法進行檢測，但這種情況通常極少出現(xiàn)。當D1,D2,D3的符號不全相同時，三角形B與平面A存在兩個交點，設(shè)這兩個交點為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種結(jié)果，如表1所示。

表1 交點在平面A的分布情況

符號“+”表示ei×mi和e1×e2的方向相同，“-”表示方向相反。其中(+，+)表示Pi位于平面A的第Ⅰ部分，(-，+)表示Pi位于平面A的第Ⅱ部分，(-，-)表示Pi位于平面A的第Ⅲ部分，(+，-)表示Pi位于平面A的第Ⅳ部分，“N”表示兩個三角形分離，在Case1～Case4四種情況中，無法直接根據(jù)Pi的位置判斷待測的三角形是否分離，需要進一步檢測交線是否與三角形A相交，如圖3所示。

圖3 無法直接判斷的4種情況

2.3 測試交線與三角形是否相交

若交線P1P2與三角形A相交，則至少滿足下面其中一個條件:

(1)P1P2與e1相交；

(2)P1P2與e2相交；

(3)P1P2與e1-e2相交；

(4)P1P2位于三角形A內(nèi)部。

根據(jù)這四個條件，分別討論Case1～Case4四種情況下P1P2與三角形A相交的情況。

Case1：根據(jù)圖3中P1與P2的位置關(guān)系，條件1、4無法滿足，因此只需檢測P1P2是否滿足條件2或3。檢測P1P2與e2是否相交等價于判斷e1×e2與(m2-e2)×(m1-e2)的方向是否相同，若兩個向量的方向相同，則P1P2與e2相交，否則分離。而當P1P2與e2不相交且P1在三角形A內(nèi)時，P1P2一定與e1-e2相交。因此在P1P2與e2不相交的情況下，P1在三角形A內(nèi)部與條件3等價，而判斷P1在三角形A內(nèi)部只需確定向量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內(nèi)部。而在條件3或條件4中，P1和P2都至少有一點位于三角形A內(nèi)部，因此在Case3中，P1P2與三角形A相交等價P1和P2中至少有一點存在三角形A內(nèi)。當(e2-e1)×(mi-e1)與e1×e2方向相同時，Pi在三角形A內(nèi)部。

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的方向進行比較將不會對結(jié)果產(chǎn)生影響。同樣在2.3中，使用ni代替mi，同時將參與運算但不包含mi的項乘以Di-Dj，例如(e2-e1)×(m1-e1)與(e2-e1)×n1-e2×e1·(Di-Dj)的方向相同。

3 算法的基本運算次數(shù)

由于在仿真環(huán)境中不同模型的三角形坐標值不在同一個坐標系中，因此使用傳統(tǒng)的三角形相交測試算法時必須根據(jù)模型的位移信息將待測的三角形轉(zhuǎn)換到同一坐標系中。設(shè)A和B分別是模型1和模型2中的兩個三角形，模型1和模型2在坐標系中的位移信息分別用四階矩陣M1和M2表示，則將三角形B的三個點轉(zhuǎn)移到三角形A所在的坐標系的公式為：

(5)

在OBB碰撞檢測算法中用OBB包圍盒的信息表示待測的三角形，并結(jié)合Wei Lingyu的三角形相交測試算法進行測試，因此在改進算法中可以避免上述27次乘法操作和27次加法操作。與Wei Lingyu的算法相比，文中對算法的改進主要集中在第一階段，即計算D1，D2，D3以及e1×e2的值。在Wei Lingyu的算法中，計算以上結(jié)果一共需要進行18次減法操作、33次加法操作和42次乘法操作，其中包括將兩個三角形轉(zhuǎn)換到同一個坐標系所需要的27次乘法操作和27次加法操作[14]。而改進算法計算D1，D2，D3以及e1×e2如下：

其中，l1·d1的值只需要計算一次，而a2的值可以在OBB碰撞檢測算法的預(yù)處理階段計算得到，所以改進后的算法計算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 實驗結(jié)果

實驗使用的硬件環(huán)境:i3-4150 CPU，頻率3.5 GHz，內(nèi)存大小4 G。軟件環(huán)境：Window 7操作系統(tǒng),Microsoft visual studio 2010開發(fā)平臺。

一共設(shè)計了三組實驗來驗證改進算法的效率，模型分別選擇佛像模型、網(wǎng)格模型以及海綿模型，其中海綿和佛像模型如圖4所示。其中佛像模型由125 000

個三角形組成，網(wǎng)格和海綿模型則分別由15 360和91 328個三角形組成。分別驗證了模型之間距離為-0.02,-0.01,0.00,0.01四種情況下改進的三角形相交算法的效率，其中當距離為-0.02,-0.01,0.00時，模型之間相交，距離為0.01時，模型之間分離。

圖4 海綿、佛像模型

在仿真環(huán)境中,決定模型之間的最短距離的值為兩個模型中的三角形頂點坐標、模型坐標信息以及模型的旋轉(zhuǎn)矩陣。對于以上四個給定距離，在保持模型之間距離不變的情況下，即兩個模型之間的最短距離保持不變，坐標值和旋轉(zhuǎn)矩陣變化，對每個距離下的三組模型都進行了38 304次碰撞測試。實驗中每次碰撞測試所使用的模型坐標以及旋轉(zhuǎn)矩陣均由文獻[15]中的算法產(chǎn)生。

通過修改RAPID碰撞檢測包實現(xiàn)了文中算法，同時使用M?ller、Guigue&&Deviller以及Wei Lingyu的三角形相交測試算法來代替RAPID包中原有的基于SAT的三角形相交測試算法，并用這些修改后的RAPID碰撞包檢測所得到的結(jié)果與改進算法進行比較。

表2顯示了模型之間的距離分別為-0.02，-0.01，0.00，0.01時，38 304次碰撞測試中三角形相交測試總的消耗時間。

表2 三角形相交測試消耗的時間

s

根據(jù)表2可知，SAT算法判斷三角形相交的效率要顯著低于其他算法，因此判斷凸多面體相交的分離軸算法實際上不適于三角形之間的相交測試。上述幾種三角形相交測試算法中，Wei Lingyu的算法的效率要比Guigue&&Deviller算法以及M?ller算法的效率高10%～15%左右。對Wei Lingyu的算法進行改進后，改進算法的效率要比Guigue&&Deviller算法以及M?ller算法高出40%～45%左右,比Wei Lingyu的算法高出30%～36%左右。

5 結(jié)束語

基于傳統(tǒng)的方向包圍盒碰撞檢測算法，重復(fù)利用方向包圍盒相交測試所得到的中間值，對其中的三角形相交測試算法進行了一些改進，同時在實驗結(jié)果中發(fā)現(xiàn)基于分離軸理論的三角形相交測試算法效率很低，據(jù)此推斷基于分離軸理論的空間矩形的相交測試算法的效率可能類似于分離軸理論用于測試三角形。而在方向包圍盒碰撞檢測算法中，葉子節(jié)點中的方向包圍盒OBB之間的相交測試實際上是空間矩形之間的相交測試，因此基于現(xiàn)存的高效的三角形相交測試算法，可以在以后的工作中嘗試找出一種新的空間矩形之間的相交測試算法來代替?zhèn)鹘y(tǒng)的基于分離軸理論的算法。

參考文獻：

[1] 宋城虎，閔 林，朱 琳,等.基于包圍盒和空間分解的碰撞檢測算法[J].計算機技術(shù)與發(fā)展，2014,24(1):57-60.

[2] 李 苗.實時碰撞檢測算法分析與比較[J].計算機與現(xiàn)代化,2011(6):88-90.

[3] 潘仁宇，孫長樂，熊 偉，等.虛擬裝配環(huán)境中碰撞檢測算法的研究綜述與展望[J].計算機科學，2016，43(11A)：136-139.

[4] 趙 偉，曲慧雁.基于云計算Map-Reduce模型的快速碰撞檢測算法[J].吉林大學學報:工學版,2016,46(2):578-584.

[5] 馬登武，葉 文，李 瑛.基于包圍盒的碰撞檢測算法綜述[J].系統(tǒng)仿真學報，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．實時碰撞檢測算法技術(shù)[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] 許 強,呂曉峰,馬登武.三角形和三角形相交測試技術(shù)研究[J].計算機仿真,2006,23(8):76-78.

[10] 鄒益勝,丁國富,何 邕,等.空間三角形快速相交檢測算法[J].計算機應(yīng)用研究，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.