于海燕， 何援軍

（1. 東華大學(xué)機械工程學(xué)院，上海 201620；2. 上海交通大學(xué)計算機系，上海 200240）

空間兩三角形的相交問題

于海燕1， 何援軍2

（1. 東華大學(xué)機械工程學(xué)院，上海 201620；2. 上海交通大學(xué)計算機系，上海 200240）

重點考慮幾何奇異問題，同時兼顧算法的效率。運用“分而治之”的方法從一維解得到二維解，進而得到三維解，將空間問題變?yōu)槠矫鎲栴}、線性問題?；趲缀未鷶?shù)化依賴于坐標系，引入“計算坐標系”，簡化了幾何的表述與關(guān)系的類型，使“幾何奇異”狀態(tài)最后歸結(jié)為平面上線段被三角形裁剪時的共點、共線問題，簡單而明晰，從而可從理論上保證算法的魯棒性，以平面處理的形式給出了兩個空間三角形求交的完整解決方案。測試證明，幾何關(guān)系、幾何奇異類型與計算的簡化足以彌補因“變換”而增加的額外開銷。算法的速度也能達到實用要求——在筆記本電腦上也能達到每秒100萬對三角形的相交計算。

幾何計算；三角形相交；降維；幾何奇異；計算坐標系

計算機構(gòu)造的虛擬對象往往由成千上萬個簡單幾何形狀（如四邊形面片，特別是三角形面片）組成。因此，碰撞檢測算法歸根結(jié)底是對這類簡單幾何形狀的關(guān)系測試。高效的三角形與三角形測試對于提高碰撞檢測算法效率，增強虛擬場景的展現(xiàn)起至關(guān)重要的作用。

近年國內(nèi)外對三角形與三角形求交測試的研究較為活躍，但通常將主要工作集中在如何加速算法的速度上。

Christer Ericson對這種只偏重速度、忽視穩(wěn)定性的研究方法表示擔(dān)心：“They do reduce the number of floating-point operations compared to previous methods, but I don’t care.（這些算法與以前的算法相比是減少了浮點運算，但是我不感興趣。）”他指出： “Frequently they test the primitives in some large number of random configurations and report the average time it took to do a test.（大都采用一些大規(guī)模隨機產(chǎn)生的三角形間的相交計算的測試手段）”，“This kind of testing is very unlikely to hit the cases where the tests fail due to robustness issues.（這種測試很難檢測到影響算法魯棒性的狀況）”[1]。

實際上，兩個三角形邊的平行、共面、相交于某一個點、某一條邊的幾何奇異現(xiàn)象在“隨機”產(chǎn)生的測試例子中常常不會被碰到，因此，檢測出現(xiàn)遺漏。而在應(yīng)用中，對一個幾何奇異的處理錯誤往往導(dǎo)致系統(tǒng)的崩潰。

本文重點考慮兩個空間三角形位置的幾何奇異情況，將幾何奇異的現(xiàn)象歸結(jié)為平面上少數(shù)幾種簡單情況，從理論上解決幾何奇異對穩(wěn)定性的影響。在此基礎(chǔ)上追求算法的效率，達到應(yīng)用要求。

1 研究現(xiàn)狀

如圖1所示，空間兩三角形的關(guān)系通常為4種情況：

1） 相交，如圖1(a)所示，公共部分為一直線段；此時，兩三角形所在平面相交。

2） 相疊，公共部分為一面區(qū)域，如圖1(b)所示，此時兩三角形共面；

3） 相離，無公共部分，如圖1(c)所示，不論兩個三角形所在平面是相交、平行或重疊，兩三角形都可能相離。

4） 碰撞，兩三角形處于接觸的臨界狀態(tài)，包括共點和共邊界兩種狀態(tài)，如圖1(d)所示；也可以看作是相交或相疊的奇異狀態(tài)。

直接計算空間兩三角形的公共部分（交點、交線段或共面區(qū)域）的過程一般比較復(fù)雜，計算復(fù)雜度較大。迅速排除兩個三角形不相交是判斷空間兩三角形關(guān)系的常用策略，因為在實際應(yīng)用中真正相關(guān)的三角形數(shù)目在整個模型中占的比例常較小。

已經(jīng)有多種關(guān)于三角形求交的算法，比較著名的有以下幾種。

M?ller算法[2]原理，如圖2所示，設(shè)兩個三角形A和B所在的平面分別為ΠA、ΠB。如果三角形A、B分別與平面ΠB、ΠA平面相交于LA、LB，則LA、LB必定在兩平面ΠA、ΠB的交線L上；若 LA、LB有重疊部分，則兩三角形相交，如圖2(a)所示，否則就相離，如圖 2(b)所示。通過計算三角形A的頂點與平面ΠB的距離以及三角形B的頂點與平面 ΠA的距離來判斷三角形與平面的關(guān)系，從而快速排除部分不相交的三角形。這種方法需要建立兩個三角形所在的平面。進行三角形分別與對方所在平面的2次“求交”及最后交線“重疊”部分的求取。

圖2 兩三角形空間求交的基本原理

Held[3]與M?ller算法類似，首先判斷三角形B的各個頂點是否位于平面 ΠA的同側(cè)進行早期排除。如果B的3個頂點位于ΠA的兩側(cè)，則構(gòu)造線段s=B∩ΠA。通過測試線段s是否與A相交來判斷三角形對的相交與否。這種方法將空間三角形的相交測試降維為二維的線段與三角形的相交測試。

Tropp算法[4]與已有算法的重大不同是不用幾何方法而采用代數(shù)方法，求解線性方程組，通過重利用方程組中的共同單元及矩陣的線性操作的策略減少計算量。

國內(nèi)外學(xué)者在以上典型的三角形與三角形相交測試算法的基礎(chǔ)上，提出了一些改進算法。張忠祥和王士同提出了基于 Ayellet 算法的改進算法[5]。首先快速排除掉兩三角形不相交或共面的兩種情況，然后分別計算一個三角形與另一個三角形所在平面相交線段，最后檢測這兩條線段是否有公共點。如果有公共點則三角形對相交，反之則不相交。鄒益勝等對三角形求交的主要算法作了較為詳細的描述并給出了測試結(jié)果[6]。

對于算法本身，很多改進算法都是在M?ller和 Held算法基礎(chǔ)上進行的。在算法的穩(wěn)定性方面，大多算法采用代數(shù)的方式描述，很難從理論上闡明對各種奇異狀態(tài)的處理；在算法評估方面，重點在于算法速度的測試，包括不同相交率對算法性能影響的測試，以及計算量的統(tǒng)計等。而對于穩(wěn)定性的測試方面缺少詳細的分析與測試。

本文將M?ller相交判斷原理加以改進，并首次提出一種基于投影降維的方法，將各種空間狀態(tài)的幾何奇異降為平面問題；并建立基于視圖的幾何表述與求解機制，在理論上保證算法的穩(wěn)定性。

2 算法原理與策略

本文將 M?ller求交判斷的基本原理改造為以下兩步（標識如圖2所示），減少計算量。

1） 先求取B與ΠA的交線段得到LB；

2） 再求取LB在A內(nèi)的部分得到交線。

首先，建立一個合適的計算坐標系，使其中一個三角形在坐標平面上。再基于兩面正投影原理，將空間兩三角形的問題歸結(jié)為平面上直線段與三角形（或直線段）的位置關(guān)系問題。最后，求交與重疊判定兩項工作也在平面上解決。

實施中采用以下策略，使相交計算與測試更快速、穩(wěn)定、精確：

1） 幾何代數(shù)化依賴于坐標系，選取合適的標系，簡化幾何的表述與計算。

2） 盡可能利用簡單的比較和計算，例如利用包圍球、盒來排除無關(guān)的計算對象，盡量減少主計算。

3） 降低維數(shù)，如把三維降為二維、二維降為一維。

4） 能處理各種特殊情況，盡可能充分利用標準的算法，提高算法的魯棒性。

5） 盡量避免那些開銷量大的計算，如三角函數(shù)、平方根、除法等。

3 計算坐標系

一個合適的坐標系可以簡化幾何的表述與代數(shù)運算，本算法將建立一個計算坐標系。計算坐標系的構(gòu)造方法如下：設(shè)有兩三角形A(A0, A1, A2)與B(B0, B1, B2)，以A所在的平面作為xy坐標平面，該平面的法向作為z軸，并以A的一條邊（例子中選取邊向量A1A2）作為x軸，如圖3所示。（詳見后面的“基本算法1”）。

圖3 計算坐標系

記xy坐標平面為H面，zx坐標平面為V面，A與B在V面與H面上的投影分別為AV、AH與BV、BH。

在這個計算坐標系下，三角形A與B的表述與關(guān)系具有下列7項性質(zhì)：

1） AH=A，即A所在平面就是xy坐標平面（V面），且A只占y≥0半平面。

2） AV積聚成一條x軸上的線段，即其中，

3） B在V、H面上的投影雖不定，但只可能是三角形或直線段2種。

4） 如果BV的3個z坐標值同號，那么B與A相離（圖4的①、⑤、⑥，有0值時是碰撞關(guān)系）。

5） 如果BV的3個z坐標值相同，B與A所在平面平行；如果此時有1個z為0，兩平面就重疊，即在平行條件下只要有1個BV的|z|＞0，B與A就不重疊。

6） 如果 BV與 AV相交，那么交點坐標為(x0,0,0)與(x1,0,0)，交點可通過BV每條邊向量端點的z坐標值求得（詳見后面“基本算法2”）。如果兩個交點滿足max(x0, x1)≤XL或者min(x0, x1)≥XR，那么B與A相離（圖4的③、⑦，等于0時是碰撞關(guān)系）。

6） 在V面，A與B的位置關(guān)系只有如下2種情況：

（1） 水平直線段與直線段的關(guān)系，如圖4(a)所示；（2）水平直線段與三角形的關(guān)系，如圖4(b)所示。

圖4 計算坐標系下空間兩三角形在V面投影的關(guān)系

圖4(a)中的V面上列出了A與B的線-線關(guān)系，其中①、③、⑤3種情況顯出AV與BV是相離的，因而空間的A與B也相離，只需對②、④兩種情況作進一步的檢測。同樣，在圖4(b)中列出了V面上A與B的線-三角形關(guān)系，其中⑥、⑦兩種情況也顯出AV與BV是相離的，A與B也就相離，只需對⑧作進一步的檢測。因此，A與B在①、⑤、⑥與③、⑦分布狀態(tài)下的相離可以迅速予以排除，只需對②、④及⑧狀態(tài)作進一步的檢測，而這些檢測均是在平面上進行的，后面會詳細闡述對這些狀態(tài)奇異性的解決策略。

引入計算坐標系不僅使得基于投影的兩個空間三角形間的計算變得十分簡單，更重要的是將空間幾何奇異完全歸結(jié)為平面問題，例如，能準確區(qū)分兩個三角形“碰撞”與“相交”狀態(tài)，使算法的穩(wěn)定性和正確性大幅度提高。

4 總體算法設(shè)計與實現(xiàn)

4.1 兩三角形計算的總體框架

在計算坐標系下，選取zx(V)與xy(H)投影面，求取兩三角形頂點的兩面正投影；根據(jù)兩三角形的投影關(guān)系判斷其空間位置關(guān)系，總體框架如圖5所示。

圖5 算法的總體框架

算法的主要步驟只需 3步（標識如圖 3所示）。

1） 建立計算坐標系

（1） 過A(A0, A1, A2)的3個頂點建立平xy(H)平面，其法向作為 z軸，并以 A的一條邊向量A1A2作為x軸，建立計算坐標系。（2）將A與B的頂點均變換到此坐標系下。

2） 在計算坐標系下求交計算：

（1） 求取B與A所在平面ΠA的交線段LB。

（2）求取LB在A內(nèi)的部分Q0Q1。

Q0Q1就是B與A在計算坐標系下的交線。

3） 變換回原坐標系

如果A與B有交線，將其端點變換回原坐標系，得到A與B在原坐標系下的交線段。

4.2 計算坐標系下兩三角形交線的計算

根據(jù)計算坐標系下兩三角形表述與關(guān)系性質(zhì)，其交線必定在xy平面上，如圖6所示。這可以簡化求取B與ΠA的交線段LB及求取LB在A內(nèi)的部分這兩步工作，具體分析如下：

圖6 計算坐標系下兩三角形交線的計算

Step 1 求取三角形B與ΠA的交線段LB。

因此，求取三角形B與ΠA的交線段LB簡化為線性問題：

先在zx坐標平面上求取AV所在直線（在x軸上）與BV的交線，即LB在zx坐標平面上投影的兩個端點其中ti為交點在BV邊上參數(shù)，xi為交點的x坐標(i=0,1)，xi在AV與BV上是相同的，而zi為0；然后通過ti在B的相應(yīng)三維邊上插出第三維坐標yi，最后得到B與H面(ΠA)的交線P0P1。

Step 2 求取LB在A內(nèi)的部分。

LB本身就在xy平面上，因此，這項工作在xy平面上進行：

計算Q0Q1=P0P1∩AH，如果Q0Q1=Φ，A與B相離；如果Q0=Q1，A與B是碰撞關(guān)系（1點接觸）；如果Q0Q1≠Φ，那么Q0Q1就是三角形A與B的交線。

下面是本文提出的計算坐標系下兩個三角形求交算法。

計算坐標系下空間兩三角形求交算法（標識見圖4）

輸入：A，B 被檢測的2個三角形

輸出：*L Line3D 交線

返回值：0 三角形A與B 空間相離1 三角形A與B 空間相交2 三角形A與B 空間點碰撞點3 三角形A與B 空間線碰撞線-1三角形A與B 共面 重疊-2 三角形A與B 共面 相離-3 三角形A與B 共面 點碰撞-4 三角形A與B 共面 線碰撞-5 三角形A與B 平行 但非共面相離

說明：本算法針對A與B均為空間三角形，需先排除A

與B退化成空間直線段的情況

本算法在計算坐標系下進行，即已實施了以下操作：

(1)過三角形A的3個頂點建立平面作為xy（H）面，其法向作為z軸，首邊向量作為x軸，建立新坐標系;

(2)三角形A與B均已變換到此坐標系下; //both AVand AWare line segments

int IntTwoTriangles3D(TRiangle A, TRiangle B, Line3D

*L)

{

//B∥H，both Bv and Bw are lines，①、②、③

//根據(jù)B的3點z坐標是否相同檢測B∥H

if (B∥H ) { //B∥H

if (B與A共面) { //根據(jù)B的z坐標是否為0檢測B與A的共面性

判斷AH與BH兩個三角形的關(guān)系；

if (AH與BH重疊) k=-1; //B與A共面重疊

if (AH與BH相離) k=-2; //B與A共面相離

if (AH與BH相交于一點) k=-3; //點碰撞

if (AH與BH相交于一線) k=-4; //線碰撞

}

else k=-5; //A與B平行但非共面=相離

return k;

} //B∥H

//B與A不平行，利用V、H平面計算

在V面上求取AV（直線）與BV邊上交點與及對應(yīng)的參數(shù)t0,A;

if (無交點) return 0; //③、⑤、⑥、⑦

根據(jù)交點在BV邊上參數(shù)t0,A在B上插出y三維坐標，得到P0(x0,y0,0)與P1(x1,y1,0); //⑧

//x0、x1的值在三角形A與B上是相同的，不必重算。z0、z1在H面上，為0。

在H面上求取Q0Q1=P0P1∩AH;

if (Q0Q1=Φ) return 0; //三角形A與B不相交

if (Q0=Q1) return 2; //三角形A與B共面點碰撞

if (Q0Q1與AH某邊重疊) return 3; //線碰撞

將Q0、Q1變換回原坐標系；//Q0Q1即為交線。

return 1;

}

5 基本算法的實現(xiàn)

下面給出兩空間三角形求交時用到的一些基本算法，除變換算法以外，其余算法均在平面上進行。

5.1 構(gòu)筑基于三角形的計算坐標系

基本算法1 設(shè)三角形由P1、P2、P3三點給出，構(gòu)筑基于這三點的計算坐標系x*y*z*，如圖7所示：

圖7 以三角形構(gòu)筑計算坐標系

1） P1P2單位向量作為n1(a1b1c1)

2） 通過P1、P2、P3三點求取三角形的單位法向量為n3(a3b3c3)。

上述以 P1為原點而互相垂直的三個單位向量n1、n2與n3構(gòu)成計算坐標系x*y*z*，其中，n1、n2在三角形所在平面上，n3為平面的法向。新舊兩坐標系間的坐標變換矩陣為：

和

其中，參數(shù)d1，d2，d3與D1、D2、D3根據(jù)新坐標系原點通過點P1求得：

變換公式為：

5.2 V面上交點的計算

在計算坐標系下，AV是x軸上的一段線段[XL, XR], BV可能是直線段或三角形。

1） 交點參數(shù)

基本算法2 設(shè)BV某個邊的兩端點為P0(x0, 0, z0)與P1(x1, 0, z1)，由于AV在x軸上，若邊P0P1與AV有交點，則P0與P1必定一個在x軸上方，另一個在x軸下方，而交點的z=0，如圖8所示。有：

如果z0與z1的符號相同，邊P0P1與x軸不相交；

（1） 如果z0與z1的符號相反，邊與x軸相交，交點為Pt=P0+t(P1-P0)，式中t=|z0|/(|z0|+|z1|)。

（2） 如果z0與z1中有一個或兩個為0，則邊與與x軸相交，交點為z坐標為零的端點。

（3） AH上的三維交點坐標(x, y, 0): x=x0+ t(x1-x0), y=y0+t(y1-y0)。

圖8 V面上交點的計算

2） AV與BV的求交計算

基本算法 3 如果 BV是三角形，如圖 9(a)所示，根據(jù)z=0的原則依次求取BV的3條邊與x軸的交點，一般情況下，這樣的交點有2個。設(shè)交點的參數(shù)為ti(i=0,1)，根據(jù)ti插出它的xi坐標，得到交點的參數(shù)(ti, xi, ni)，這里，ni是該交點在BV上的邊號，因為三角形有3條邊，ni可能的值為0、1、2。參數(shù)(ti, ni)將用于在H面上計算該交點的y值。

如果BV是直線段，實際上是B的3邊在V面的積聚投影，如圖9(b)所示，仍應(yīng)作為3條邊分別計算。雖然兩交點的(ti, xi)參數(shù)是一樣的，但是所在邊號ni不一樣，用(ti, ni)去求交點在空間的y時就會得到2個不同的值。

圖9 V面上求交的統(tǒng)一

這樣，不管 BV是三角形還是直線段，在本算法中在V面上求取交點的計算方式是統(tǒng)一的。

3） 排除AV與BV相離

基本算法4 為加速算法，可用拒絕判定快速排除AV與BV的相離。在計算坐標系下，排除計算也十分簡單。

在z方向，如果BV的3個z坐標全為正或全為負，表明BV完全在AV的上方或下方，兩者就無重疊關(guān)系（圖10①）；

在x軸上，如果2個交點均位于AV右端點的右邊（max(x0, x1)＞XR）或均位于AV左端點的左邊（min(x0, x1)＜XL），那么AV與BV就相離（圖10③）。

圖10 水平線段與三角形的位置分布圖

5.3 H面上直線段與三角形的交集的求取

基本算法 5 求取LB在A內(nèi)的部分就是在H面上求取LB與AH的交集。線段與三角形的交集可借用任何一種凸多邊形裁剪算法，這里借用Cyrus-Beck參數(shù)化裁剪算法[7]，將Cyrus-Beck對凸多邊形參數(shù)化裁剪算法改造成 Cyrus-Beck三角形參數(shù)化裁剪算法，并增加了被裁剪線的端點或其本身在三角形邊界上的奇異情況的處理（參見7.2 H面上線段與三角形的交集的幾何奇異）。

6 幾何奇異處理

6.1 V面求交時的幾何奇異

在 V面上是直線段(AV)與三角形(BV)的三條邊的求交，交點數(shù)可能是1、2、3個。

1） 交點數(shù)為1

表示交點在AV的左端點（x=0，圖11④）或右端點（x=XR，圖 11⑧），BV位于 AV的左側(cè)或右側(cè)。進一步對交點作 AH的包容性測試，如果交點在AH的內(nèi)部或邊界上，則A與B為“碰撞”關(guān)系，否則為相離關(guān)系；

2） 交點數(shù)為2

此時可能是正常交點（圖11⑤）、共邊（圖11⑥）及共點（圖 11⑦），前兩者（⑤、⑥）進一步進行AH的裁剪測試，所得結(jié)果即為A與B的交線；后者（⑦）的交點數(shù)為1的處理方法相同；

3） 交點數(shù)為3

此時必有一個交點通過 BV的一個頂點（圖11①、②、③），解決方法為刪除通過頂點的一個交點。因為參數(shù)ti是基于BV的邊向量的，因此，通過 BV的一個頂點的交點的參數(shù) ti必有一個為0，另一個為1，如果不計ti=0的交點（也可不計ti=1的交點），交點就減為正常的2個。設(shè)3個交點的排列為0、1、2，處理方法是：

if (t0=0) t0=t2; n0=n2; //圖11②

else if (t1=0) t1=t2; n1=n2; //圖11①

n--; //n為交點計數(shù)，原來為3，現(xiàn)在為2

6.2 H面上線段與三角形的交集的幾何奇異

H面上線段與三角形的交集的求取系借用Cyrus-Beck參數(shù)化裁剪算法，分為以下5種情況，奇異情況比較好處理，如圖(12)所示。

1）正常的裁剪，如圖12(a)所示；

2）直線穿越三角形的一個頂點，使得線段與三角形有3個交點，破壞了直線進出三角形的奇偶性，如圖12(b)所示；

3）是直線通過頂點，但不“穿越”三角形，如圖12(c)所示。

圖12 三角形裁剪的奇異情況

4） 直線與三角形的某一邊重合，在平面是共線，反映到空間是兩三角形“共線”碰撞，如圖12(d)所示。

5） 直線段的一個端點在三角形的邊界上，反映到空間是兩三角形“共點”碰撞，如圖(e)所示。

上述(1)、(2)空間兩三角形有交線，(3)、(4)、(5)“碰撞”。

最后，當H面上的線段退化為一點時，需要檢測該點是否在 AH的內(nèi)部，如果是，空間兩三角形“共點”碰撞，否則，兩三角形空間相離。

6.3 兩三角形共面時的幾何奇異

當兩個三角形共面時，可能出現(xiàn)相離、碰撞（共點、共線）、重疊（包括內(nèi)含）等關(guān)系。

不能簡單地用“判斷B(A)的頂點是否在A(B)的內(nèi)部”，因為，即使兩個三角形的頂點均在對方之外，兩者仍可能是相交關(guān)系。

本文采用“如果B各邊與A有交集，那就有重疊（反之也然）”的策略判定平面上兩三角形的重疊關(guān)系。將兩個三角形的重疊關(guān)系的問題降為“一線段與一三角形的重疊關(guān)系”的判定。最后也歸結(jié)到前節(jié)“線段被三角形裁剪”算法中的一些奇異情況。

1) B中任一邊被A三角形裁剪后如果有顯示部分，兩三角形為重疊關(guān)系；

2) B中三邊被A三角形裁剪后均無顯示部分，兩三角形為相離關(guān)系；

3) B中任一邊被A三角形裁剪后只顯示1點，兩三角形為點重疊關(guān)系；

4) B中任一邊與A三角形的某邊界重合，兩三角形為邊重疊關(guān)系。

需要注意的是，4)比3)的優(yōu)先級高。

因為平面上2個三角形重疊時可能多達6個交點，最多可產(chǎn)生六邊形，因此，“準確重疊部分的求取”并非一個簡單的問題?？紤]到大多數(shù)空間三角形關(guān)系處理的目標是判定他們的相離、碰撞和重疊關(guān)系等，只有在“曲面求交”等一類應(yīng)用中才追究“準確重疊部分的求取”，因此，本算法不展開對它進一步討論。而且這是一個平面問題，也可以參考文獻[8]，用“兩個平面多邊形的布爾運算”方法解決。

7 測試與分析

7.1 奇異測試

兩個空間三角形的奇異情況可在共面、相交情況下出現(xiàn)。共面情況下可能有共點、共線、內(nèi)含等；相交情況下可能有共點、共線等。

本算法根據(jù)這些情況構(gòu)造了相應(yīng)的奇異測試例子。測試樣本根據(jù)兩三角形所位平面的關(guān)系分為平面平行、重合和相交3大類，如圖13所示。

圖13 測試樣本的分類

測試樣本中，先將一個三角形A固定，變換另一三角形B的位置實現(xiàn)各種空間位置關(guān)系。對一個A，設(shè)計了包括圖1、圖4、圖10、圖11以及圖12中描述位置關(guān)系在內(nèi)的23種與A位置呈現(xiàn)含奇異狀態(tài)的三角形B。此外，還設(shè)計了其它30種空間位置關(guān)系的三角形，包含了各種直接分離、H面檢測等情況（圖14）。測試結(jié)果是本算法均能正確處理。

圖14 三視圖表達的測試樣本舉例

7.2 速度測試

用40對三角形，重復(fù)100萬次相交計算，分別在筆記本電腦與臺式電腦兩類機器上進行測試，測試結(jié)果如表1所示。

表1 本算法對40×1000000對空間三角形進行相交測試的時間表(sec)

計算坐標系下的測試，在筆記本電腦上，0.95秒(38/40)可處理100萬對三角形的相交計算，在臺式電腦上，0.7秒(28/40)可處理100萬對三角形的相交計算。

在一般坐標系下測試，在筆記本電腦上，1.2秒(47/40)可處理100萬對三角形的相交計算，在臺式電腦上，0.775秒(31/40)可處理100萬對三角形的相交計算。

7.3 算法分析

在粗略排除階段，可以采用直接三維空間判斷和投影判斷相結(jié)合的方法。例如，圖4中的①、⑤、⑥狀態(tài)也可直接在三維空間進行判斷：對三角形A建立一個平面，ax+by+cz+d=0，將三角形B的3個頂點代入A的這個平面方程，得到3個數(shù)：如果全部同號，則三角形B與A分離。而對于排除圖4中的③、⑦狀態(tài)用投影辦法較好。

本算法需要進行“計算坐標系的建立”、“A與B三個頂點的齊次變換”以及“交點變換回原坐標系”等變換計算。因此，我們專門考察了變換在本算法中所占時間的份額——最高為 16%左右。

實際上，在大規(guī)模的三角形求交計算中不需要對每對求交的三角形進行計算坐標系的建立與變換計算，例如，對每一個A建立計算坐標系，變換1次A，而只對與A相關(guān)的（一系列）B進行變換即可。

經(jīng)計算坐標系下的投影降維，A與B的關(guān)系可以直接用圖形在平面上“畫”出來，將空間幾何關(guān)系降解為視圖中直線段與三角形（或直線段）的關(guān)系，能嚴格區(qū)分兩個三角形的“碰撞”、“相交”“相離”與“重疊”的關(guān)系，便于發(fā)現(xiàn)處理各種幾何奇異情況；同時這種變換使算法變得更清晰，計算更簡單，例如“兩線段求交的參數(shù)求取只需1次加法，1次除法”。因此，綜合分析，本算法的變換開銷利大于弊。

在計算策略上，充分利用直線的參數(shù)表述，采用分而治之的辦法將空間問題變?yōu)槠矫鎲栴}、線性問題，使得幾何表述更簡單、幾何間的關(guān)系更清晰，可以使用更多的“通用”的算法，例如，凸多邊形裁剪算法，使算法更為規(guī)范。

8 總 結(jié)

本文給出了一種基于投影降維的空間兩三角形求交檢測方法的詳細方案和算法。這是一種幾何化的全新思路，能從理論上嚴格保各種奇異情況的發(fā)現(xiàn)與正確處理。也為其它基本幾何元求交、碰撞檢測等提供了一種新的解題思路。

[1] Christer Ericson. Triangle-triangle tests, plus the art of benchmarking [EB/OL]. http://realtimecollisiondetection. net/blog/?p=29.

[2] M?ller T. A fast triangle-triangle intersection test [J]. Journal of Graphics Tools, 1997, 2(2): 25-30.

[3] Held M. Erit: a collection of efficient and reliable intersection tests [J]. Journal of Graphics Tools, 1997, 2(4): 25-44.

[4] Tropp O Tala, Shimshoni I. A fast triangle to triangle intersection test for collision etection [J]. Computer Animation and Virtual Worlds, 2006, 17(5): 527-535.

[5] 張忠祥, 王士同. 三角形對的快速相交測試[J]. 計算機工程與設(shè)計, 2010, 3(4): 869-875.

[6] 鄒益勝, 丁國富, 何 邕, 等. 空間三角形快速相檢測算法[J]. 計算機應(yīng)用研究, 2008, 25(10): 2907-2909.

[7] CYRUS M, BECK J. Generalized two-and three-dimensional clip-ping [J]. Computers and Graphics, 1978, 3(1): 23-28.

[8] 何援軍. 計算機圖形學(xué)(第 2版)[M]. 北京: 機械工業(yè)出版社, 2009.

Testing the Intersection Status of Two Triangles

Yu Haiyan1, He Yuanjun2
( 1. College of Mechanical Engineering, Donghua University, Shanghai 201620, China; 2. Dept. of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China )

This paper focuses on geometric singularity and algorithm speed. In our algorithm, a 3D problem is reduced to planes and is further divided to a linear problem. In order to simplify the representation of geometric problem, a computational coordinate system is constructed. Thus, the geometric singularity of two triangles is reduced to planar problems between a line and a triangle, which limits the singularity to co-points and co-lines. Consequently, the complex spatial geometric singularity can be represented by planar drawings simply and visually and the robustness of our algorithm can be certificated theoretically. This paper gives the whole algorithm and detailed schemes. Experiment tests show that the priority in simplifying geometric relations, geometric singularity and calculations is sufficient to make up for the cost of transformation. The speed is 1 million pairs of triangles per second on a notebook computer.

geometric computing; triangles intersection; dimension reduction; geometric singularity; computational coordinates

TP 391.72

A

2095-302X (2013)04-0054-09

2013-04-29；定稿日期：2013-05-03

國家自然基金資助項目（61073083）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助

于海燕（1974-），女，黑龍江海林人，副教授，博士，主要研究方向為CAD/CG。E-mail：yuhy@dhu.edu.cn