空間三角形快速相交檢測(cè)算法

收稿日期：2007-10-15；修回日期：2007-12-27

基金項(xiàng)目：國(guó)家自然科學(xué)杰出青年基金資助項(xiàng)目(50525518)；國(guó)家“973”計(jì)劃資助項(xiàng)目（2007CB714701）

作者簡(jiǎn)介：鄒益勝（1980-），男，浙江文成人，博士研究生，主要研究方向?yàn)閂P/VM、可視化(zysapple@sina.com)；丁國(guó)富（1972-），男，四川樂至人，教授，博導(dǎo)，主要研究方向?yàn)閂P/VM/VR、先進(jìn)制造技術(shù)、開放式數(shù)控技術(shù)、可視化；何邕（1983-），男，四川達(dá)州人，博士研究生，主要研究方向?yàn)閂P/VM、可視化；許明恒（1947-），男，陜西漢中人，教授，博導(dǎo)，主要研究方向?yàn)橄冗M(jìn)制造技術(shù).*

(西南交通大學(xué) 機(jī)械工程學(xué)院， 成都 610031)

摘 要：綜述了典型的快速穩(wěn)定的三角形相交檢測(cè)算法的原理及實(shí)現(xiàn)方法，并根據(jù)算法原理將其分為標(biāo)量判別型和矢量判別型算法。從計(jì)算量角度對(duì)各種算法的適用場(chǎng)合和性能進(jìn)行了分析比較及驗(yàn)證，結(jié)果顯示矢量判別型算法中的Olivier Devillers Philippe Guigue算法整體性能最優(yōu)，而標(biāo)量判別型算法中的Oren Tropp算法最適合于三角形相交率較高的場(chǎng)合。

關(guān)鍵詞：空間三角形；相交檢測(cè)；標(biāo)量判別；矢量判別

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)10-2906-05

Fast intersection algorithm between spatial triangles

ZOU Yi-sheng，DING Guo-fu，HE Yong，XU Ming-heng

(College of Mechanical Engineering， Southwest Jiaotong University， Chengdu 610031，China)

Abstract:This paper surveyed the principle and implementation of typically fast and robust triangle-triangle intersection algorithms， which was classified into scalar discrimination algorithm and vector discrimination algorithm according to their principle. Discussed the applicable occasions and performance of every algorithm by analyzing their calculation amount. The results of analysis and test show that the overall performance of the algorithm proposed by Olivier Devillers Philippe Guigue， one of the vector discrimination algorithms， is optimal， and the algorithm proposed by Oren Tropp， one of the scalar discrimination algorithms， is most suitable for the occasions with high triangle-triangle intersection ration.

Key words:spatial triangle; intersection; scalar discrimination; vector discrimination

碰撞檢測(cè)是機(jī)器人運(yùn)動(dòng)規(guī)劃、計(jì)算機(jī)仿真、虛擬現(xiàn)實(shí)、游戲等領(lǐng)域不可回避的問題之一。隨著三維幾何模型越來越逼真、越來越復(fù)雜，虛擬環(huán)境的場(chǎng)景規(guī)模越來越大，這對(duì)碰撞檢測(cè)的實(shí)時(shí)性提出了巨大挑戰(zhàn)。提高碰撞檢測(cè)的實(shí)時(shí)性一般從兩方面處理：減少參與檢測(cè)的圖元數(shù)，如采用層次樹等；減少圖元間相交檢測(cè)的時(shí)間，在基于圖形的碰撞檢測(cè)算法中，最終都要進(jìn)行基本圖元（如三角形等）的相交檢測(cè)。三角形是最常用的基本圖元，因此，對(duì)快速的三角形相交檢測(cè)算法的研究有著重要意義。本文綜述了國(guó)內(nèi)外研究者提出的典型的空間三角形快速碰撞檢測(cè)算法，以供相關(guān)領(lǐng)域的研究者交流和借鑒。

1 典型算法原理及實(shí)現(xiàn)方法

三角形和三角形相交測(cè)試方法很多，傳統(tǒng)的有brute-force（蠻力）方法。其基本原理為通過求解方程組檢測(cè)一個(gè)三角形的每一條邊與另一三角形的每一條邊是否相交；如果出現(xiàn)相交，則兩三角形相交。顯然該方法檢測(cè)效率較低[1]。為此研究者們采用不同的方法進(jìn)行研究，提出了以下幾種典型的快速三角形相交檢測(cè)算法。

11 標(biāo)量判別型算法

標(biāo)量判別型算法是通過準(zhǔn)確計(jì)算來獲知兩三角形相交關(guān)系的一類算法。這里介紹典型的Mller、Held和Tropp算法。其中Mller和Held算法從幾何的角度對(duì)命題進(jìn)行化簡(jiǎn)，最終分別化簡(jiǎn)成兩線段的相交問題和線段與三角形的相交問題；Tropp算法從代數(shù)的角度出發(fā)，充分利用求解過程中的中間值及矩陣操作的線性關(guān)系加速問題的解決。標(biāo)量判別式可以直接求解出交點(diǎn)，但由于計(jì)算的累積誤差，對(duì)其精度有一定的影響。

111 Mller算法[2~8]

設(shè)有兩個(gè)三角形T1和T2，構(gòu)造三角形所在的平面分別為π1、π2，通過計(jì)算T1的頂點(diǎn)與平面π2的距離以及T2的頂點(diǎn)與平面π1的距離來判斷三角形與平面的關(guān)系，從而快速排除部分不相交的三角形。如果兩個(gè)三角形都分別與另外的三角形所在的平面相交，則其交線l1、l2必定在兩平面的交線L上；若l1、l2相交則兩三角形相交。如果判斷為共面，則通過適當(dāng)?shù)赝队斑M(jìn)行降維，轉(zhuǎn)換為二維三角形相交的方法另行處理。二維三角形間的碰撞檢測(cè)算法比較成熟，在此不再介紹。

具體描述如下：設(shè)有兩個(gè)三角形T1和T2，頂點(diǎn)分別為V10、V11、V12和V20、V21、V22，三角形所在的平面分別為π1、π2，其法向量分別為N1、N2。

a)計(jì)算平面π2的方程:

N2×x+d2＝0 （1）

其中：x為π2上任意一點(diǎn)；N2=(V20-V21)×(V22-V21)；d2＝-N2×V21。

b)將三角形T1的三個(gè)頂點(diǎn)分別代入平面方程π2，可得各頂點(diǎn)到平面π2的距離為

dV1i＝N2×V1i＋d2；i=0，1，2（2）

(a)如果dV1i＝0(i=0，1，2)，那么兩三角形共面，轉(zhuǎn)而執(zhí)行二維三角形和三角形相交測(cè)試。(b)如果dV1i≠0(i=0，1，2)且同號(hào)， 那么T1位于π2的同側(cè)，則不相交。這種早期的相交測(cè)試避免了大量三角形對(duì)的相交計(jì)算。

c）計(jì)算平面π1的方程。

d）將三角形T2的三個(gè)頂點(diǎn)分別代入平面方程π1，排除頂點(diǎn)在π1同側(cè)的三角形。

e）經(jīng)過前面的排除，可以判定π1、π2相交于一直線L，且L必與兩三角形相交。如果交線重疊，則兩三角形相交，如圖1(a)所示;否則不相交，如圖1(b)所示。直線方程為

L=O＋tD（3）

其中:D為直線方向，D=N1×N2;O為L(zhǎng)上一點(diǎn);t為L(zhǎng)上點(diǎn)的標(biāo)量值。定義L與兩三角形交線的端點(diǎn)在L上的標(biāo)量值分別為t1、t2、t3、t4，通過三角形相交邊與L的投影關(guān)系（圖2）及相似三角形的性質(zhì)，求出t1、t2、t3、t4。

f）判斷間隔t1、t2和t3、t4是否重疊，如果是，則兩三角形相交。

112 Held算法[5，6，9]

Held與Mller算法類似，首先判斷三角形T2的各個(gè)頂點(diǎn)是否位于平面π1的同側(cè)進(jìn)行早期排除。如果T2的三個(gè)頂點(diǎn)位于π1的兩側(cè)， 則可以構(gòu)造線段s=T2∩π1。測(cè)試線段s是否與T1相交來判斷三角形對(duì)的相交與否，此相交測(cè)試可降維為二維的線段與三角形相交測(cè)試。

113 Tropp算法[10]

Tropp算法與前面提到的幾種方法最大的不同之處在于：前者致力于從幾何角度解決問題，后者的核心在于代數(shù)方法上。Tropp采用蠻力算法的思路求解線性方程組，指出方程組是強(qiáng)烈相關(guān)的，并充分利用方程組中的共同單元以及矩陣操作中的線性關(guān)系來加速問題的解決。其算法的基本原理及實(shí)現(xiàn)過程如下：

設(shè)有A、B兩個(gè)空間三角形，如果A和B相交，則其中的一個(gè)三角形至少有一條邊穿過另外一個(gè)三角形，如圖3所示。其中：P為p1、p2的起始點(diǎn)；Qi為qi的起始點(diǎn)，則可得出

P+α1×p1+α2×p2=Qi+βi×qi；i=1，2，3 （4）

為保證交點(diǎn)在三角形內(nèi)，式(4)需滿足約束條件：0≤βi≤1，α1，α2≥0且α1+α2≤1。顯然，這需要求解六個(gè)方程。算法的主要貢獻(xiàn)在于：

a)重復(fù)利用方程組中的共同單元，這樣只需進(jìn)行一次計(jì)算，將其值保存供其他計(jì)算使用。

b）利用矩陣計(jì)算的線性特性。算法的實(shí)施步驟如下（返回結(jié)果為“真”表示兩三角形相交，“假”為不相交）：

(a)部分求解方程組，求得βi的值。

將式（4）寫成矩陣形式，并令ri=Qi-P，則

(p1|p2|qi)(α1α2-βi)T=(ri)（5）

定義A(v)=(p1|p2|v)，則式（5）可寫成

A(qi)xi=ri;i=1，2，3(6)

其中：xi=(α1，α2，-βi)T。

采用克萊姆法則求解式（6）容易得到

βi=-|A(ri)|/|A(qi)|(7)

可以發(fā)現(xiàn)，A(ri)、A(qi)中含有相同的前兩列p1、p2，因此A(ri)，A(qi)可以按第三列展開，則其子式只需計(jì)算一次。

由圖3容易得出如下向量關(guān)系：

q3=q2-q1，Q3=Q1+q1

r3=Q3-P=(Q1+q1)-P=r1+q1（8）

根據(jù)矩陣和行列式的計(jì)算性質(zhì)，有

|A(q3)|=|A(q2-q1)|=|A(q2)|-|A(q1)|

|A(r3)|=|A(r1+q1)|=|A(r1)|+|A(q1)|（9）

這樣，只需要有較少的計(jì)算量就能完成βi的計(jì)算。由此可見，通過重利用方程組中的共同單元及矩陣的線性操作可以大大減少計(jì)算量。

(b)如果βi的值不滿足約束條件，則返回測(cè)試結(jié)果為“假”，測(cè)試結(jié)束。其目的是快速排除兩三角形不相交的情況。如果所有|A(qi)|值為零，則表示兩三角形共面，采用Mller算法中的共面計(jì)算方法。

（c）構(gòu)造三角形A與B所在的平面間的相交線段。如圖3所示，假設(shè)三角形A與B所在平面的交線為T+t，其中T為三角形A的一邊與三角形所在平面的交點(diǎn)，由前面的計(jì)算容易得到

T=Q1+β1q1

t=β2q2-β1q1（10）

(d)如果線段與三角形B相交，則返回結(jié)果為“真”；否則返回為“假”。線段與三角形B的相交有兩種情況：與三角形的邊相交；線段在三角形內(nèi)部。由此可以列出以下關(guān)系式：

P+δ1p1=T+γ1t

P+δ2p2=T+γ2t

(P+p1)+δ3(p2-p1)=T+γ3t（11）

其計(jì)算采用步驟中所述的方法。對(duì)于第一種相交情況，當(dāng)0≤δi≤1且0≤γi≤1時(shí)，表明線段與三角形相交；對(duì)于第二種相交情況，如果存在兩個(gè)δ∈[0，1]，且其所對(duì)應(yīng)的γ值符號(hào)相反，則表明線段包含在三角形中，即兩者相交。

12 矢量判別型算法

矢量判別型算法是通過一系列計(jì)算值的符號(hào)來判定兩個(gè)三角形的位置關(guān)系，繼而判別其相交情況的一類算法。這里介紹典型的Devillers Guigue算法和Shen算法。其中Devillers Guigue算法通過三角形的各頂點(diǎn)構(gòu)成的行列式正負(fù)的幾何意義來判斷三角形中點(diǎn)、線、面之間的相對(duì)位置關(guān)系；而Shen算法則是采用一種基于分離平面的方法，即將一個(gè)三角形的三條邊擴(kuò)展，將其所在的平面分為七部分，再通過計(jì)算帶符號(hào)的線線距離來判別另一個(gè)三角形的邊落在分離平面的哪個(gè)區(qū)域，從而判別兩個(gè)三角形的相交情況。總體上，矢量判別型算法對(duì)計(jì)算的精度要求較低，因此也具有比標(biāo)量判別型算法更好的穩(wěn)定性，但這類算法對(duì)于交點(diǎn)的求解往往需要另外進(jìn)行處理。

121 Devillers Guigue[5，6，11，12]算法

Devillers Guigue算法（簡(jiǎn)稱Devillers算法）通過三角形各頂點(diǎn)構(gòu)成的行列式正負(fù)的幾何意義來判斷三角形中點(diǎn)、線、面之間的相對(duì)位置關(guān)系，從而判斷兩三角形是否相交。其基本原理如下：

給定四個(gè)空間點(diǎn)：a=(ax，ay，az)，b=(bx，by，bz)c=(cx，cy，cz)，d=(dx，dy，dz) ，定義行列式：

[a，b，c，d]=axayaz1

bxbybz1

cxcycz1

dxdydz1=ax-dxay-dyaz-dz

bx-dxby-dybz-dz

cx-dxcy-dycz-dz(12)

[a，b，c，d]采用右手螺旋法則定義了四個(gè)空間點(diǎn)的位置關(guān)系。[a，b，c，d]>0表示d在a、b、c按逆時(shí)針順序所組成的三角形的正法線方向（即上方）；[a，b，c，d]＜0表示d在△abc的下方；[a，b，c，d]=0表示四點(diǎn)共面。

設(shè)兩個(gè)三角形T1和T2，頂點(diǎn)分別為V¹0、V¹1、V¹2和V²0、V²1、V²2，三角形所在的平面分別為π1、π2，其法向量分別為N1、N2。

算法先判別三角形和另一個(gè)三角形所在的平面的相互位置關(guān)系，提前排除不相交的情況。通過計(jì)算[V²0，V²1，V²2，V¹i](i=0，1，2)來判斷T1和π2的關(guān)系：如果所有行列式的值都不為零且同號(hào)，則T1和T2不相交；否則T1和π2相交。相交又分為以下幾種情況：

a)如果所有行列式的值為零，則T1和T2共面；

b)如果其中一個(gè)行列式的值為零，而其他兩個(gè)行列式同號(hào)，則只有一點(diǎn)在平面內(nèi)，測(cè)試頂點(diǎn)是否在T2內(nèi)部，是則相交，否則不相交；

c)否則，T1的頂點(diǎn)位于平面π2的兩側(cè)(包含T1的一條邊在平面π2中的情況)。

再按照類似的方法對(duì)T2和π1作進(jìn)一步的測(cè)試。如果通過測(cè)試，則每個(gè)三角形必有確定的一點(diǎn)位于另一個(gè)三角形所在平面的一側(cè)，而另外兩點(diǎn)位于其另一側(cè)。算法分別循環(huán)置換每個(gè)三角形的頂點(diǎn)，以使V¹0(V²0)位于π2（π1）的一側(cè)，另兩點(diǎn)位于其另一側(cè)；同時(shí)對(duì)頂點(diǎn)V²1、V²2（V¹1、V¹2）進(jìn)行交換操作，以確保V¹0(V²0)位于π2（π1）的上方，即正法線方向。經(jīng)過以上的預(yù)排除和置換操作，V¹0的鄰邊V¹0V¹1、V¹0V¹2和V²0的鄰邊V²0V²1、V²0V²2與兩平面的交線L相交于固定形式的點(diǎn)上，分別記為i， j，k，l（i

[V¹0，V¹1，V²0，V²1]≤0∩[V¹0，V¹2，V²2，V²0]≤0（13）

122 Shen[1]算法

Shen算法是對(duì)Mller算法的改進(jìn)。算法改進(jìn)體現(xiàn)在提出了一種基于分離平面來判別兩三角形位置關(guān)系的新方法，重點(diǎn)是針對(duì)兩個(gè)交叉的三角形，且三角形的頂點(diǎn)沒有落在另一個(gè)三角形所在平面的情況。算法描述如下：

對(duì)于兩條非平行直線L1和L2，其方向向量分別為D1和D2，N=D1×D2同時(shí)垂直于L1和L2。每條直線都包含在平面N×U=ci。其中每條直線中的常量ci=N×Pi，Pi為直線Li上的任一點(diǎn)。則有向的線線距離定義為dL1L2=c1-c2。算法采用左手法則判定符號(hào)，如圖6所示。P1P1′平行于N，從L1到L2的有向距離就是從平面π到P1的距離，圖中表示為正向。

設(shè)有兩個(gè)三角形T1和T2，頂點(diǎn)分別為V¹0、V¹1、V¹2和V²0、V²1、V²2，三角形所在的平面分別為π1、π2，其法向量分別為N1、N2。如圖7所示，以T1為例，直線Li分別為T1三條邊的擴(kuò)展，將T1所在的平面π1劃分成七個(gè)區(qū)域。三元組(SLL0，SLL1，SLL2)用于判別直線L與平面π1相交于哪個(gè)區(qū)域。其中SLLi為dLLi(i=1，2，3)的符號(hào)。

與Devillers Guigue算法類似，該算法也要判別獨(dú)點(diǎn)(即單獨(dú)位于另一個(gè)三角形所在平面π一側(cè)的點(diǎn))。如果三角形有一點(diǎn)位于另一個(gè)角形所在的平面π內(nèi)，則位于平面兩側(cè)的任一點(diǎn)都可作為獨(dú)點(diǎn)。由于獨(dú)點(diǎn)的鄰邊都不與π平等，這兩條鄰邊到π內(nèi)的任何一條線的線線距離都不為零。根據(jù)前面“一個(gè)三角形是否在另一個(gè)三角形一側(cè)”的計(jì)算很容易獲得獨(dú)點(diǎn)。不失一般性，記V¹0為三角形T1的獨(dú)點(diǎn)，V²0為三角形T2的獨(dú)點(diǎn)，Vi1、Vi2(i=1，2)的順序影響Ni的方向，繼而影響平面πi到點(diǎn)的距離的符號(hào)。不失一般性，約定為：調(diào)整Vi1、Vi2(i=1，2)的順序，使得從V¹0到π2的距離以及V²0到π1的距離為正。

兩個(gè)邊對(duì){LV¹2V¹0，LV²2V²0}和{LV¹0V¹1，LV²0V²1}的線線距離決定了兩個(gè)三角形是否相交。如果LV²0V²1到LV¹0V¹1的線線距離為負(fù)或者LV²2V²0到LV¹2V¹0的線線距離為正，則兩三角形不相交；否則相交。

算法的實(shí)現(xiàn)可歸納為以下幾步：

a)通過計(jì)算排除一個(gè)三角形在另一個(gè)三角形同一側(cè)的情況；

b)獲得獨(dú)點(diǎn)，并根據(jù)需要對(duì)其他兩個(gè)點(diǎn)進(jìn)行重排序；

c)計(jì)算LV²0V²1到LV¹0V¹1的線線距離，如果為負(fù)則不相交；

d)計(jì)算LV²2V²0到LV¹2V¹0的線線距離，如果為正則不相交；

e)否則判斷兩三角形相交。

2 算法分析及測(cè)試

算法的時(shí)間消耗主要包括開辟內(nèi)存和數(shù)學(xué)運(yùn)算兩部分，涉及的運(yùn)算包括四則運(yùn)算、比較運(yùn)算、絕對(duì)值運(yùn)算和賦值運(yùn)算。對(duì)于現(xiàn)行的主流計(jì)算機(jī)來說，加減法、乘法與比較的計(jì)算時(shí)間可以認(rèn)為是相同的，除法計(jì)算時(shí)間大約是加法計(jì)算時(shí)間的4~8倍[11，12]，因此算法一般都避免除法以提高效率，而賦值計(jì)算的時(shí)間相對(duì)而言可以忽略。Tropp算法是在Mller和Held算法基礎(chǔ)上的改進(jìn)，具有比它們更快的速度，但它們都屬于數(shù)值計(jì)算型，其精度會(huì)受到機(jī)器誤差和累積誤差的影響，這對(duì)算法的穩(wěn)定性和準(zhǔn)確性會(huì)有一定的影響。如果系統(tǒng)對(duì)算法的準(zhǔn)確性要求較高，可以采用double數(shù)值類型，適當(dāng)?shù)貭奚稽c(diǎn)速度來保證精度。相對(duì)來說，Devillers和Shen算法在這方面作了改進(jìn)，機(jī)器誤差對(duì)其影響較小，也降低了計(jì)算要求，提高了算法的效率和穩(wěn)定性。另外，Tropp算法另辟蹊徑從代數(shù)的角度對(duì)算法進(jìn)行加速，有一定的借鑒意義。

通過對(duì)各種算法及其實(shí)現(xiàn)代碼進(jìn)行研究，分析如下(由于沒能獲取Held算法源碼，此處主要針對(duì)文中提及的另四種算法進(jìn)行分析和驗(yàn)證)：

a)內(nèi)存開辟分析。Mller使用的變量數(shù)為55；Devillers使用的變量數(shù)為18，Shen使用的變量數(shù)為38；Tropp使用的變量數(shù)為51。Devillers算法最優(yōu)。

b)判定兩三角形相交時(shí)各算法的計(jì)算量分析。如表1所示，Tropp最優(yōu)，其總計(jì)算量為103/121，其次為Devillers。

表1 判定兩三角形相交時(shí)各算法的計(jì)算量比較

算法加減乘法比較絕對(duì)值除法賦值計(jì)算量合計(jì)Mller(no div)5763/6512/243069135/149Devillers765210/180064138/146Shen7056/5812/820062138/210Tropp(no div)42/4551/5710/190046/52103/121

c)排除不相交情況的計(jì)算量分析。四種算法都通過排除不相交的情況，最后判定為相交，這種方式可以有效提高檢測(cè)的效率。各算法的排除次數(shù)和各次排除的計(jì)算量如表2所示。其中，Devillers和Shen算法都采用四次排除，對(duì)于相交率較低的三角形對(duì)集合的測(cè)試具有一定的優(yōu)勢(shì)；Mller算法次之；而Tropp算法只采用兩次排除，不利于計(jì)算過程中對(duì)于不相交情況的提前排除，需要較大的計(jì)算代價(jià)。再對(duì)各次排除的計(jì)算量比較發(fā)現(xiàn)，在第一次排除中，Tropp算法的計(jì)算量相對(duì)較大；Mller、Devillers和Shen算法的前兩次排除的計(jì)算量相同；第三、四次排除中的計(jì)算量，Devillers優(yōu)于Shen算法。

表2 排除兩三角形不相交情況的計(jì)算量比較

算法第一次排除第二次排除第三次排除第四次排除確認(rèn)相交Mller(no div)4385/86135/149/135/149Devillers4385/86114/122138/146138/146Shen4385/86114/186138/210138/210Tropp(no div)47/53103/121//103/121

綜上分析，由于Devillers算法的內(nèi)存開辟時(shí)間消耗少、較為適中的相交判別計(jì)算量，再加上四次計(jì)算過程中不相交情況的排除，整體上最優(yōu)；Shen算法次之，其在相交率較低的場(chǎng)合可以發(fā)揮更大的作用；Tropp算法則適用于相交率較高的三角形對(duì)集合。

為了測(cè)試各種算法的實(shí)際性能，并驗(yàn)證分析結(jié)果，按如下規(guī)則構(gòu)造測(cè)試環(huán)境[1]：

a)隨機(jī)生成三維點(diǎn)V∈[0，1];

b)構(gòu)成三角形的三個(gè)點(diǎn)不共線 (有的算法不能處理退化的三角形);

c)一個(gè)三角形對(duì)由兩個(gè)三角形T1和T2組成，記為{T1，T2}；

d)如果{T1，T2}相交(采用Mller算法判別)，寫入相交集，否則寫入分離集；

e)根據(jù)設(shè)定的相交率分別從相交集和分離集中取數(shù)據(jù)，混合排序，構(gòu)成新的數(shù)據(jù)集。

測(cè)試條件為：Intel Core2 6300， 1.86 GHz，內(nèi)存1 GB，Windows XP系統(tǒng)。取11種相交率，對(duì)每種相交率取5個(gè)數(shù)據(jù)集樣本，每個(gè)樣本由5 000個(gè)三角形對(duì)構(gòu)成(循環(huán)測(cè)試1 000次)，5個(gè)樣本測(cè)試完成后取均值得到一種相交率的測(cè)試時(shí)間，測(cè)試數(shù)據(jù)如表3所示。表3中的數(shù)據(jù)顯示：算法的時(shí)間開銷隨著相交率的降低而降低，同時(shí)也驗(yàn)證了表1、2中對(duì)算法的理論分析。

表3 測(cè)試不同相交率下各算法檢測(cè)所用的平均時(shí)間/ms

相交率MllerDevillersShenTropp1.01 548.9891 305.7141 435.6371 243.6840.91 489.3671 261.6281 375.5211 225.5310.81 438.3091 220.2271 324.6741 213.6230.71 386.6391 176.2651 275.7581 191.0480.61 347.7361 147.0571 243.0611 178.5760.51 268.7911 089.6381 161.4171 164.1000.41 214.9761 044.1071 098.8611 137.9730.31 148.476994.8221 043.8271 115.0290.21 090.416940.628983.8061 085.1270.11 030.905886.870931.1151 065.6620.0958.573830.989865.6141 032.559

通過前面分析可知，各算法對(duì)于三角形不相交的情況的排除能力不盡相同。以相交率為0.5的一組數(shù)據(jù)為例，表4顯示了各算法在各次不相交三角形排除計(jì)算中所排除的三角形數(shù)對(duì)算法時(shí)間消耗的影響。

表4 相交率為0.5的各算法排除三角形數(shù)及檢測(cè)所用的時(shí)間

算法第一次排除第二次排除第三次排除第四次排除總排除數(shù)時(shí)間消耗/msMller(no div)1 325 000582 000593 000/250 0001 272.358Devillers1 324 000583 000284 000309 000250 0001 087.816Shen1 324 000583 000298 000295 000250 0001 165.851Tropp(no div)1 325 0001 175 000//250 0001 169.7213 結(jié)束語

綜上分析和驗(yàn)證可以得出結(jié)論：Devillers算法總體上最優(yōu)；Tropp算法最適合于高相交率場(chǎng)合；Shen算法比較適合中低相交率場(chǎng)合；Mller算法雖然整體性能稍弱，但它是其他算法的基礎(chǔ)，且應(yīng)用廣泛；從相關(guān)材料分析結(jié)果看，Held算法的整體性能還略遜于Mller算法，但其與Mller算法類似，也起著基礎(chǔ)的作用，其算法思想為其他算法所借鑒。以上算法的共同點(diǎn)都是在著力追求算法的快速性，分別采用幾何方法和代數(shù)方法實(shí)現(xiàn)，同時(shí)從測(cè)試結(jié)果來看，各算法也有較好的精度和穩(wěn)定性。隨著場(chǎng)景規(guī)模的大型化和復(fù)雜化，檢測(cè)速度是算法追求的主要指標(biāo)之一。圖形處理器（GPU）的數(shù)據(jù)處理能力比CPU強(qiáng)很多，因此許多研究者開始嘗試著將GPU數(shù)據(jù)處理能力應(yīng)用到通用計(jì)算領(lǐng)域，并獲得了成功，特別是在流體計(jì)算領(lǐng)域，展現(xiàn)了其強(qiáng)大的計(jì)算能力。這是一個(gè)新的領(lǐng)域，有著巨大的潛力，越來越多的研究者開始關(guān)注這一領(lǐng)域，在三角形相交測(cè)試方面[13，14]以及相關(guān)的碰撞檢測(cè)領(lǐng)域[15~20]的研究工作也已開展。GPU以比CPU更快的速度發(fā)展，并進(jìn)一步考慮了其在通用計(jì)算領(lǐng)域的應(yīng)用。以NVIDIA公司為例，其推出的新一代GeForce 8系列和Quadro系列GPU都采用了新的統(tǒng)一渲染構(gòu)架，取消了原來的頂點(diǎn)著色器和像素著色器，取而代之的是統(tǒng)一的可編程流處理器，增加了對(duì)GPU的利用率，GeForce 8系列最多可擁有128個(gè)流處理器。為進(jìn)一步挖掘GPU的通用計(jì)算性能，NVIDIA公司推出了CUDA技術(shù)，一種用于在NVIDIA GPU上進(jìn)行計(jì)算的全新體系架構(gòu)，這是該領(lǐng)域內(nèi)的首個(gè)GPU用的C編譯器開發(fā)環(huán)境，此舉被譽(yù)為是揭開GPU計(jì)算革命的序幕。由此可見，基于GPU的計(jì)算及其算法研究將逐漸成為研究的熱點(diǎn)。由于GPU本身在處理上的并行性特點(diǎn)，對(duì)更適合于在GPU上運(yùn)行的三角形相交檢測(cè)算法以及基于它的實(shí)時(shí)碰撞檢測(cè)算法的研究將有著重要的科研和實(shí)踐價(jià)值。

參考文獻(xiàn)：

[1]SHEN Hao， HENG P A， TANG Z. A fast triangle-triangle overlap test using signed distances[J].Journal of Graphics Tools，2003，8(1):3-15.

［2］MLLER T.A fast triangle-triangle intersection test[J].Journal of Graphics Tools，1997，2(2):25-30.

[3]羅楓，陳志楊，張三元，等.基于OBB樹層次關(guān)系的相交體特征計(jì)算[J].計(jì)算機(jī)應(yīng)用研究，2005，22(10):23-25，29.

[4]王志強(qiáng)，洪嘉振，楊輝.碰撞檢測(cè)問題研究綜述[J].軟件學(xué)報(bào)，1999，10(5):545-551.

[5]門曉鵬，呂曉峰，馬登武，等.虛擬場(chǎng)景中基本幾何元素相交測(cè)試技術(shù)[J].海軍航空工程學(xué)院學(xué)報(bào)，2006，21(3):379-382.

[6]許強(qiáng)，呂曉峰，馬登武.三角形和三角形相交測(cè)試技術(shù)研究[J].計(jì)算機(jī)仿真，2006，23(8):76-78，145.

[7]高明向， 陳昆， 陳定方.射線算法在碰撞檢測(cè)中的應(yīng)用[J].湖北工學(xué)院學(xué)報(bào)，2004，19(3):94-97.

[8]陳學(xué)文，劉靜華，丑武勝，等.快速計(jì)算虛擬物體之間精確接觸位置的算法[J].北京航空航天大學(xué)學(xué)報(bào)，2005，31(7):799-804.

[9]HELD M.ERIT: a collection of efficient and reliable intersection tests[J].Journal of Graphics Tools，1997，2(4):25-44.

[10]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.

[11]DEVILLERS O，GUIGUE P.Faster triangle-triangle intersection tests， TR 4488[R]. [S.l.]: INRIA，2002.

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

[13]范昭煒，萬華根，高曙明.基于流的實(shí)時(shí)碰撞檢測(cè)算法[J].軟件學(xué)報(bào)，2004，15(10):1505-1514.

[14]于永彥，夏宜蕃.一種基于流計(jì)算的實(shí)時(shí)碰撞檢測(cè)算法的研究與實(shí)現(xiàn)[J].北京聯(lián)合大學(xué)學(xué)報(bào):自然科學(xué)版，2005，19(4):73-79.

[15]柳有權(quán)，劉學(xué)慧，吳恩華.基于GPU帶有復(fù)雜邊界的三維實(shí)時(shí)流體模擬[J].軟件學(xué)報(bào)，2006，17(3):568-576.

[16]FERNANDO R.GPUGems: programming techniques， tips， and tricks for real-time graphics[M].Boston:Addison Wesley， 2004:637-666.

[17]PHARR M.GPUGems:programming techniques for high-performance and general-purpose computation[M]. Boston: Addison Wesley，2005.

[18]GOVINDARAJU N K， LIN Ming C， MANOCHA D.Quick-CULLIDE: fast inter- and intra-object collision culling using graphics hardware[C]//Proc of IEEE Virtual Reality Conference. Washington DC: IEEE Computer Society， 2005:59-66，319.

[19]HOFF KE ZAFERAKIS A， LIN Ming，et al.Fast 3D geometric proxi-mity queries between rigid and deformable models using graphics hardware acceleration，TR02-004[R]. Chapel Hill: University of North Carolina， 2002.

[20]PABST H F， SPRINGER J P， SCHOLLMEYER A. Ray casting of trimmed NURBS surfaces on the GPU[C]//Proc of IEEE Symposium on Interactive Ray Tracing. Washington DC: IEEE Computer Society， 2006:151-160.

[21]謝凱， 楊杰. 一種基于虛擬手術(shù)的三維碰撞檢測(cè)算法[J].上海交通大學(xué)學(xué)報(bào)，2007，41(6):866-869.

[22]金漢均，王曉榮，王萌.基于層次包圍盒的碰撞檢測(cè)算法的存儲(chǔ)優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用， 2007，43(16):61-63.

[23]KENSLER J，SHIRLEY P.Optimizing ray-triangle intersection via automated search[C]//Proc of IEEE Symposium on Interactive Ray Tracing.Washington DC: IEEE Computer Society， 2006:33-38.

[24]GOTTSCHALK S，LIN Ming C.Collision detection between geometric models: a survey[C]//Proc of IMA Conference on Mathematics of Surfaces.1998:3-15.

[25]KLOSOWSKI J T，HELD M，MITCHELL J S B.Efficient collision detection using bounding volume hierarchies of k-DOPs[J].IEEE Trans on Visualization and Computer Graphics，1998，4(1):21-36.

[26]SHEWCHUK J R.Adaptive precision floating-point arithmetic and fast robust geometric predicates[J].Discrete Computational Geometry， 1997，18(3):305-363.