空間三角形快速相交檢測算法

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

基金項目：國家自然科學杰出青年基金資助項目(50525518)；國家“973”計劃資助項目（2007CB714701）

作者簡介：鄒益勝（1980-），男，浙江文成人，博士研究生，主要研究方向為VP/VM、可視化(zysapple@sina.com)；丁國富（1972-），男，四川樂至人，教授，博導，主要研究方向為VP/VM/VR、先進制造技術、開放式數控技術、可視化；何邕（1983-），男，四川達州人，博士研究生，主要研究方向為VP/VM、可視化；許明恒（1947-），男，陜西漢中人，教授，博導，主要研究方向為先進制造技術.*

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

摘 要：綜述了典型的快速穩定的三角形相交檢測算法的原理及實現方法，并根據算法原理將其分為標量判別型和矢量判別型算法。從計算量角度對各種算法的適用場合和性能進行了分析比較及驗證，結果顯示矢量判別型算法中的Olivier Devillers Philippe Guigue算法整體性能最優，而標量判別型算法中的Oren Tropp算法最適合于三角形相交率較高的場合。

關鍵詞：空間三角形；相交檢測；標量判別；矢量判別

中圖分類號：TP391

文獻標志碼：A

文章編號：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

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

1 典型算法原理及實現方法

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

11 標量判別型算法

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

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

設有兩個三角形T1和T2，構造三角形所在的平面分別為π1、π2，通過計算T1的頂點與平面π2的距離以及T2的頂點與平面π1的距離來判斷三角形與平面的關系，從而快速排除部分不相交的三角形。如果兩個三角形都分別與另外的三角形所在的平面相交，則其交線l1、l2必定在兩平面的交線L上；若l1、l2相交則兩三角形相交。如果判斷為共面，則通過適當地投影進行降維，轉換為二維三角形相交的方法另行處理。二維三角形間的碰撞檢測算法比較成熟，在此不再介紹。

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

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

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

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

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

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

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

c）計算平面π1的方程。

d）將三角形T2的三個頂點分別代入平面方程π1，排除頂點在π1同側的三角形。

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

L=O＋tD（3）

其中:D為直線方向，D=N1×N2;O為L上一點;t為L上點的標量值。定義L與兩三角形交線的端點在L上的標量值分別為t1、t2、t3、t4，通過三角形相交邊與L的投影關系（圖2）及相似三角形的性質，求出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的各個頂點是否位于平面π1的同側進行早期排除。如果T2的三個頂點位于π1的兩側， 則可以構造線段s=T2∩π1。測試線段s是否與T1相交來判斷三角形對的相交與否，此相交測試可降維為二維的線段與三角形相交測試。

113 Tropp算法[10]

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

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

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

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

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

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

(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)

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

由圖3容易得出如下向量關系：

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）

根據矩陣和行列式的計算性質，有

|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）

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

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

（c）構造三角形A與B所在的平面間的相交線段。如圖3所示，假設三角形A與B所在平面的交線為T+t，其中T為三角形A的一邊與三角形所在平面的交點，由前面的計算容易得到

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

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

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

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

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

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

其計算采用步驟中所述的方法。對于第一種相交情況，當0≤δi≤1且0≤γi≤1時，表明線段與三角形相交；對于第二種相交情況，如果存在兩個δ∈[0，1]，且其所對應的γ值符號相反，則表明線段包含在三角形中，即兩者相交。

12 矢量判別型算法

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

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

Devillers Guigue算法（簡稱Devillers算法）通過三角形各頂點構成的行列式正負的幾何意義來判斷三角形中點、線、面之間的相對位置關系，從而判斷兩三角形是否相交。其基本原理如下：

給定四個空間點：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]采用右手螺旋法則定義了四個空間點的位置關系。[a，b，c，d]>0表示d在a、b、c按逆時針順序所組成的三角形的正法線方向（即上方）；[a，b，c，d]＜0表示d在△abc的下方；[a，b，c，d]=0表示四點共面。

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

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

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

b)如果其中一個行列式的值為零，而其他兩個行列式同號，則只有一點在平面內，測試頂點是否在T2內部，是則相交，否則不相交；

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

再按照類似的方法對T2和π1作進一步的測試。如果通過測試，則每個三角形必有確定的一點位于另一個三角形所在平面的一側，而另外兩點位于其另一側。算法分別循環置換每個三角形的頂點，以使V¹0(V²0)位于π2（π1）的一側，另兩點位于其另一側；同時對頂點V²1、V²2（V¹1、V¹2）進行交換操作，以確保V¹0(V²0)位于π2（π1）的上方，即正法線方向。經過以上的預排除和置換操作，V¹0的鄰邊V¹0V¹1、V¹0V¹2和V²0的鄰邊V²0V²1、V²0V²2與兩平面的交線L相交于固定形式的點上，分別記為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算法是對Mller算法的改進。算法改進體現在提出了一種基于分離平面來判別兩三角形位置關系的新方法，重點是針對兩個交叉的三角形，且三角形的頂點沒有落在另一個三角形所在平面的情況。算法描述如下：

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

設有兩個三角形T1和T2，頂點分別為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三條邊的擴展，將T1所在的平面π1劃分成七個區域。三元組(SLL0，SLL1，SLL2)用于判別直線L與平面π1相交于哪個區域。其中SLLi為dLLi(i=1，2，3)的符號。

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

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

算法的實現可歸納為以下幾步：

a)通過計算排除一個三角形在另一個三角形同一側的情況；

b)獲得獨點，并根據需要對其他兩個點進行重排序；

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

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

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

2 算法分析及測試

算法的時間消耗主要包括開辟內存和數學運算兩部分，涉及的運算包括四則運算、比較運算、絕對值運算和賦值運算。對于現行的主流計算機來說，加減法、乘法與比較的計算時間可以認為是相同的，除法計算時間大約是加法計算時間的4~8倍[11，12]，因此算法一般都避免除法以提高效率，而賦值計算的時間相對而言可以忽略。Tropp算法是在Mller和Held算法基礎上的改進，具有比它們更快的速度，但它們都屬于數值計算型，其精度會受到機器誤差和累積誤差的影響，這對算法的穩定性和準確性會有一定的影響。如果系統對算法的準確性要求較高，可以采用double數值類型，適當地犧牲一點速度來保證精度。相對來說，Devillers和Shen算法在這方面作了改進，機器誤差對其影響較小，也降低了計算要求，提高了算法的效率和穩定性。另外，Tropp算法另辟蹊徑從代數的角度對算法進行加速，有一定的借鑒意義。

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

a)內存開辟分析。Mller使用的變量數為55；Devillers使用的變量數為18，Shen使用的變量數為38；Tropp使用的變量數為51。Devillers算法最優。

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

表1 判定兩三角形相交時各算法的計算量比較

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

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

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

算法第一次排除第二次排除第三次排除第四次排除確認相交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算法的內存開辟時間消耗少、較為適中的相交判別計算量，再加上四次計算過程中不相交情況的排除，整體上最優；Shen算法次之，其在相交率較低的場合可以發揮更大的作用；Tropp算法則適用于相交率較高的三角形對集合。

為了測試各種算法的實際性能，并驗證分析結果，按如下規則構造測試環境[1]：

a)隨機生成三維點V∈[0，1];

b)構成三角形的三個點不共線 (有的算法不能處理退化的三角形);

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

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

e)根據設定的相交率分別從相交集和分離集中取數據，混合排序，構成新的數據集。

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

表3 測試不同相交率下各算法檢測所用的平均時間/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

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

表4 相交率為0.5的各算法排除三角形數及檢測所用的時間

算法第一次排除第二次排除第三次排除第四次排除總排除數時間消耗/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 結束語

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

參考文獻：

[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樹層次關系的相交體特征計算[J].計算機應用研究，2005，22(10):23-25，29.

[4]王志強，洪嘉振，楊輝.碰撞檢測問題研究綜述[J].軟件學報，1999，10(5):545-551.

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

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

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

[8]陳學文，劉靜華，丑武勝，等.快速計算虛擬物體之間精確接觸位置的算法[J].北京航空航天大學學報，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]范昭煒，萬華根，高曙明.基于流的實時碰撞檢測算法[J].軟件學報，2004，15(10):1505-1514.

[14]于永彥，夏宜蕃.一種基于流計算的實時碰撞檢測算法的研究與實現[J].北京聯合大學學報:自然科學版，2005，19(4):73-79.

[15]柳有權，劉學慧，吳恩華.基于GPU帶有復雜邊界的三維實時流體模擬[J].軟件學報，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]謝凱， 楊杰. 一種基于虛擬手術的三維碰撞檢測算法[J].上海交通大學學報，2007，41(6):866-869.

[22]金漢均，王曉榮，王萌.基于層次包圍盒的碰撞檢測算法的存儲優化[J].計算機工程與應用， 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.