基于OBB包圍盒碰撞檢測(cè)算法的改進(jìn)

劉 超，蔣夏軍，施慧彬

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

0 引 言

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

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

算法的運(yùn)行時(shí)間可以用式1表示[6]:

T=Nv*Cv+Np*Cp

(1)

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

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

1 方向包圍盒碰撞檢測(cè)算法

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

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

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

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

(2)

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

(3)

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

1.2 OBB之間的相交測(cè)試

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

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

1.3 三角形相交測(cè)試算法

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

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

2 改進(jìn)的三角形相交測(cè)試算法

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

2.1 計(jì)算相交線段

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

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

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

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

(1)

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

假設(shè)三角形B的邊和平面A之間存在交點(diǎn)，如圖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ù)上面三角形的坐標(biāo)信息，容易得到:

(4)

根據(jù)式3,只有當(dāng)Di和Dj有不同的符號(hào)(或者其中的一個(gè)值為0)時(shí)能滿(mǎn)足0≤βij,βji≤1，即三角形B的邊和平面A存在交點(diǎn)。如果D1,D2,D3的符號(hào)相同則表示三角形B和平面A分離，即三角形A和三角形B不相交；如果D1,D2,D3都為0，則表示三角形A和三角形B共面，此時(shí)使用共面三角形相交測(cè)試算法進(jìn)行檢測(cè)，但這種情況通常極少出現(xiàn)。當(dāng)D1,D2,D3的符號(hào)不全相同時(shí)，三角形B與平面A存在兩個(gè)交點(diǎn)，設(shè)這兩個(gè)交點(diǎn)為P1,P2，m1=P1-A3,m2=P2-A3。

圖2 三角形B與平面A相交

2.2 計(jì)算交點(diǎn)在平面中的位置

在圖2中，平面A被向量e1向量e2所在的直線分為4部分，通過(guò)比較ei×mi和e1×e2的方向，可以確定Pi在平面A中的位置。例如當(dāng)e1×m1與e1×e2方向相同且e2×m1與e1×e2方向相反時(shí)，P1點(diǎn)位于平面A的第Ⅳ部分，通過(guò)同樣方法可以確定P2的位置。比較ei×mi與e1×e2的方向后，一共可以得到16種結(jié)果，如表1所示。

表1 交點(diǎn)在平面A的分布情況

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

圖3 無(wú)法直接判斷的4種情況

2.3 測(cè)試交線與三角形是否相交

若交線P1P2與三角形A相交，則至少滿(mǎn)足下面其中一個(gè)條件:

(1)P1P2與e1相交；

(2)P1P2與e2相交；

(3)P1P2與e1-e2相交；

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

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

Case1：根據(jù)圖3中P1與P2的位置關(guān)系，條件1、4無(wú)法滿(mǎn)足，因此只需檢測(cè)P1P2是否滿(mǎn)足條件2或3。檢測(cè)P1P2與e2是否相交等價(jià)于判斷e1×e2與(m2-e2)×(m1-e2)的方向是否相同，若兩個(gè)向量的方向相同，則P1P2與e2相交，否則分離。而當(dāng)P1P2與e2不相交且P1在三角形A內(nèi)時(shí)，P1P2一定與e1-e2相交。因此在P1P2與e2不相交的情況下，P1在三角形A內(nèi)部與條件3等價(jià)，而判斷P1在三角形A內(nèi)部只需確定向量e1×e2與向量(e2-e1)×(m1-e1)同向。

Case2：若交線P1P2與三角形A相交，則P1P2一定至少與e1和e2中一個(gè)向量相交。因此只需檢測(cè)P1P2是否滿(mǎn)足條件1或條件2即可判斷交線與三角形A是否相交。類(lèi)似Case1中的判斷方法，P1P2與ei相交等價(jià)(m2-ei)×(m1-ei)、e1×e2、m1×m2三者的方向相同。

Case3：若P1P2與三角形A相交，則P1P2只可能滿(mǎn)足條件3或者條件4，即P1P2與e1-e2相交或者P1P2位于三角形A內(nèi)部。而在條件3或條件4中，P1和P2都至少有一點(diǎn)位于三角形A內(nèi)部，因此在Case3中，P1P2與三角形A相交等價(jià)P1和P2中至少有一點(diǎn)存在三角形A內(nèi)。當(dāng)(e2-e1)×(mi-e1)與e1×e2方向相同時(shí)，Pi在三角形A內(nèi)部。

Case4：與Case2類(lèi)似，P1P2只可能與e1和e2相交，但在Case4中，首先比較m1×m2與e1×e2的方向，若兩個(gè)向量的方向相同，則P1P2只可能與e2相交，方向相反則P1P2只可能與e1相交。

2.4 消除算法中的除法運(yùn)算

在計(jì)算機(jī)中，一次除操作所消耗的時(shí)間遠(yuǎn)遠(yuǎn)高于加法、乘法、減法等運(yùn)算的時(shí)間，因此合理地減少算法中的除法運(yùn)算能提高整個(gè)算法的效率。下面討論如何避免算法中的除法運(yùn)算。

整個(gè)三角形相交測(cè)試的算法中，只有在求三角形B與平面A的交點(diǎn)P1和P2時(shí)需要進(jìn)行除法運(yùn)算:

令ni=(Di-Dj)，mi=Dirj-Djri,因?yàn)镈i與Dj異號(hào)，可以交換二者的值使Di>Dj，因此mi與ni的方向相同。故在2.2中用ei×ni代替ei×mi與e1×e2的方向進(jìn)行比較將不會(huì)對(duì)結(jié)果產(chǎn)生影響。同樣在2.3中，使用ni代替mi，同時(shí)將參與運(yùn)算但不包含mi的項(xiàng)乘以Di-Dj，例如(e2-e1)×(m1-e1)與(e2-e1)×n1-e2×e1·(Di-Dj)的方向相同。

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

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

(5)

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

其中，l1·d1的值只需要計(jì)算一次，而a2的值可以在OBB碰撞檢測(cè)算法的預(yù)處理階段計(jì)算得到，所以改進(jìn)后的算法計(jì)算D1，D2，D3以及e1×e2的值只需要6次乘法操作和3次加法操作。與Wei Lingyu的算法相比少了36次乘法操作、30次加法操作以及18次減法操作。改進(jìn)算法最終一共需要51～57次基本運(yùn)算操作，這些運(yùn)算包括加減法、乘法以及比較兩個(gè)值的大小。而Wei Lingyu的算法一共需進(jìn)行135～141次基本運(yùn)算操作[14]，Guigue&&Deviller的算法需要進(jìn)行168～198次基本運(yùn)算操作[13]，M?ller的算法需要進(jìn)行178～200次基本運(yùn)算操作[11]。

4 實(shí)驗(yàn)結(jié)果

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

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

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

圖4 海綿、佛像模型

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

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

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

表2 三角形相交測(cè)試消耗的時(shí)間

s

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

[5] 馬登武，葉 文，李 瑛.基于包圍盒的碰撞檢測(cè)算法綜述[J].系統(tǒng)仿真學(xué)報(bào)，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í)時(shí)碰撞檢測(cè)算法技術(shù)[M]．劉天慧，譯．北京：清華大學(xué)出版社，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] 許 強(qiáng),呂曉峰,馬登武.三角形和三角形相交測(cè)試技術(shù)研究[J].計(jì)算機(jī)仿真,2006,23(8):76-78.

[10] 鄒益勝,丁國(guó)富,何 邕,等.空間三角形快速相交檢測(cè)算法[J].計(jì)算機(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.