孫敬榮，盧新明

1.山東科技大學(xué)，山東 青島 266590

2.山東科技大學(xué) 山東省智慧礦山信息技術(shù)省級重點實驗室，山東 青島 266590

1 引言

碰撞檢測（Collision Detection，CD）是虛擬網(wǎng)絡(luò)游戲、物理仿真[1]、虛擬仿真技術(shù)[2]、機(jī)器人技術(shù)[3]、數(shù)控加工等的關(guān)鍵技術(shù)?，F(xiàn)階段在碰撞檢測領(lǐng)域的研究方法主要有：基于物體空間的碰撞檢測算法和圖像空間的碰撞檢測算法[4]。層次包圍盒是一類經(jīng)典的碰撞檢測算法，同時三角形相交檢測也是一類在碰撞檢測中應(yīng)用廣泛的算法。隨著虛擬現(xiàn)實應(yīng)用內(nèi)容的復(fù)雜化以及應(yīng)用領(lǐng)域的日益擴(kuò)大，應(yīng)用環(huán)境的實時性以及復(fù)雜性對碰撞干涉檢測的要求越來越高，單一的基于層次包圍盒或傳統(tǒng)三角形相交已經(jīng)很難滿足人們對碰撞檢測準(zhǔn)確性與速度的需求。并且，近幾年國內(nèi)外對三角形相交測試的研究十分的活躍，但基本都過度重視了算法的速度，而忽視了穩(wěn)定性。該研究旨在通過結(jié)合并優(yōu)化包圍盒算法與三角形相交算法以保證碰撞檢測的速度與準(zhǔn)確性。

2 算法原理

基于對碰撞檢測的研究，將碰撞干涉檢測分為預(yù)處理檢測和詳細(xì)檢測兩階段，在預(yù)處理階段，將待測空間均勻劃分，然后算法基于混合層次包圍盒樹，對處在同一網(wǎng)格區(qū)域內(nèi)的相鄰對象構(gòu)造混合層次包圍盒樹。當(dāng)兩個待測物體的AABB-OBB混合層次包圍盒樹建成后，通過遍歷兩棵混合包圍盒樹，進(jìn)行包圍盒之間的相交測試：當(dāng)兩個包圍盒未相交時，該節(jié)點停止檢測；當(dāng)包圍盒相交時，對該節(jié)點的子節(jié)點進(jìn)行檢測；當(dāng)葉節(jié)點包圍盒相交時，則轉(zhuǎn)入詳細(xì)檢測，在詳細(xì)檢測階段，針對傳統(tǒng)三角形相交算法過度追求速度而穩(wěn)定性不足的特點，對算法進(jìn)行了優(yōu)化改進(jìn)，其流程圖如圖1所示。

圖1 碰撞檢測流程圖

2.1 預(yù)處理檢測階段

預(yù)處理階段經(jīng)過對空間的均分確定了相鄰對象，然后只對相鄰的對象構(gòu)造AABB-OBB混合層次包圍盒，常用的包圍盒有以下幾種：軸向包圍盒（Axis-Aligned Bounding Box，AABB）[5]、方向包圍盒（Oriented Bounding Box，OBB）[6]、k-DOPs和Sphere-OBB[7]等，其中AABB的優(yōu)勢在于構(gòu)造簡單，相交測試的更加簡單速度，它直接將三維的相交運算轉(zhuǎn)化為一維上的6次比較運算，只要在3個坐標(biāo)軸上的投影均相交，則判定兩個物體發(fā)生碰撞。但其緊密性不足，需要構(gòu)造的層數(shù)較多，增加了計算量。而OBB緊密性更好，甚至一度視為碰撞檢測算法的重要標(biāo)準(zhǔn)，它優(yōu)勢在于包圍盒方向，可以根據(jù)待測物體的形狀盡可能包圍該物體，但這使得OBB的構(gòu)造過程更為復(fù)雜，所以采用了AABB-OBB混合包圍層次盒，其總體性能優(yōu)于其他包圍盒。

2.1.1 AABB-OBB混合包圍盒構(gòu)造的優(yōu)化

針對OBB包圍盒，構(gòu)造算法進(jìn)行了優(yōu)化，在此之前Gottschalk等人已經(jīng)提出了一種通過計算三角形網(wǎng)格的方法來構(gòu)建幾何多面體的OBB包圍盒。他將三角形的頂點集合看成3個變量的概率分布函數(shù)，再通過計算均值和協(xié)方差矩陣的特征向量來計算OBB包圍盒的位置與方向[8]。其中設(shè)包圍盒中三角形個數(shù)為n，xi、yi、zi為第i個三角形的3個頂點。則有：

三角形各個頂點的均值為：

協(xié)方差為：

通過計算可以得出矩陣C的特征向量并將其單位化，同時，由于C的特征向量是相互垂直的，即方向軸，然后將各點投影到方向軸上，確定包圍盒的大小，但這種構(gòu)造方法當(dāng)三角形基本元不均勻時，包圍盒整體會偏向基本元尺寸較小且密集的部分，可能會造成包圍盒與待測物體偏差過大，使得包圍緊密性變差。為了提高檢查的效率與準(zhǔn)確性，對原有算法進(jìn)行優(yōu)化，選擇三角面片的面積為權(quán)值，給各個三角形進(jìn)行加權(quán)，即設(shè)三角形面積為S，則：

物體的表面積為：

各個三角面片的中心為：

則協(xié)方差矩陣為：

通過這種方法可以看作兩個包圍盒中的一個是否完全在另一個的外邊，除去第一層AABB外，下層的OBB包圍盒的檢測利用了Gottschalk等基于分離軸定理提出的檢測方法，如果它們之間存在著一條分離軸，則判定它們未相交的。

2.1.2 AABB-OBB混合層次包圍盒樹的優(yōu)化

預(yù)處理檢測的核心在于遍歷兩個待測對象的混合層次包圍盒樹，將遍歷過程定義一個任務(wù)樹，各項任務(wù)為各個節(jié)點間的碰撞檢測，所以只需要對任務(wù)樹進(jìn)行單重遍歷即可完成對兩棵樹的同步深度優(yōu)先遍歷，同層的子任務(wù)之間為或的關(guān)系，若其中一個子任務(wù)檢測結(jié)果為相交，則兩個包圍盒碰撞。

基于二叉樹的思想，第一層采用AABB，下層都采用了OBB，因為AABB的結(jié)構(gòu)相較于其他包圍盒是最簡單，通過第一層的檢測，快速排除大量的無關(guān)信息，接下來通過下層的OBB進(jìn)一步檢測處理，采用OBB可以更加緊密的包圍待測物體，減少相交檢測的層數(shù)，同時對任務(wù)樹結(jié)構(gòu)進(jìn)行優(yōu)化，只對每一層相交的數(shù)據(jù)進(jìn)行存儲，然后下邊的每一層對上一層存儲信息構(gòu)造包圍盒進(jìn)行碰撞檢測，形成如圖2所示的結(jié)構(gòu)。預(yù)處理檢測具體步驟如下：

步驟1通過空間剖分，對空間內(nèi)相鄰的兩個對象的根節(jié)點A和B進(jìn)行碰撞檢測。檢測根節(jié)點的兩個AABB是否相交，若未發(fā)生相交，則直接判定未發(fā)生碰撞，否則進(jìn)入步驟2。

步驟2若A和B均為枝節(jié)點，同時并行進(jìn)行4個子任務(wù)，即A、B同時向左，A向左B向右，A向右B向左，AB同時向右的4種并行的相交測試，如果以上4種都未發(fā)生相交，則判定未發(fā)生碰撞，否則進(jìn)入步驟3；

若A為葉節(jié)點、B為枝節(jié)點，或者A為枝節(jié)點、B為葉節(jié)點，并行進(jìn)行AB同時向左和向右相交測試兩個子任務(wù)，如果以上兩種都未發(fā)生相交，則直接判定未發(fā)生碰撞，否則進(jìn)入步驟3；

若A和B均為葉節(jié)點，則轉(zhuǎn)入詳細(xì)檢測，即對三角形基本元進(jìn)行相交測試，如果相交，則判定發(fā)生了碰撞并返回碰撞的詳細(xì)信息，否則判定兩個對象之間并未發(fā)生碰撞。

步驟3把之前相交的節(jié)點重新標(biāo)記為A和B，然后返回步驟2。

圖2 AABB-OBB結(jié)構(gòu)圖

2.2 碰撞檢測的詳細(xì)檢測

碰撞檢測的根本即簡單幾何形狀之間的關(guān)系測試。高效的三角形對相交測試對于提高碰撞檢測算法速度和準(zhǔn)確性以及增強虛擬場景的展現(xiàn)起至關(guān)重要的作用[9]。目前，矢量判別型算法和標(biāo)量判別型算法是針對三角形快速相交檢測的兩種主要算法。其中矢量判別法主要是通過三角形各個頂點構(gòu)成的行列式，然后行列式的正負(fù)幾何意義來判斷兩個三角形的點、線、面之間的相對位置關(guān)系，進(jìn)而判斷兩個三角形是否相交[10]；而標(biāo)量判別算法核心思想是通過準(zhǔn)確向量計算來判斷兩個三角形之間相交關(guān)系，標(biāo)量判別算法典型的有M?ller[11]、Trop[12]算法。本文提出的詳細(xì)檢測是在M?ller算法基礎(chǔ)上，加入坐標(biāo)系變換而提出了一種優(yōu)化算法，通過坐標(biāo)變換求得新的計算坐標(biāo)系，在新的計算坐標(biāo)系下進(jìn)行向量之間的運算，在保證檢測準(zhǔn)確性的前提下，提高了檢測速度。

2.2.1構(gòu)建計算坐標(biāo)系

針對待測三角形，需要構(gòu)造新的計算坐標(biāo)系，使得其中的一個待測三角形在新的坐標(biāo)系平面上。設(shè)三角形A的P0、P1、P2頂點已經(jīng)給出，構(gòu)建基于這個三角形的計算坐標(biāo)系O*，如圖3所示，然后通過以下三步形成以P0為原點，以及n0、n1、n2為單位向量的計算坐標(biāo)系O*。

圖3 構(gòu)造計算坐標(biāo)系

P0P1的單位向量為：

新舊兩個坐標(biāo)系之間的坐標(biāo)變換矩陣為：

其中根據(jù)計算坐標(biāo)系原點P0求出參數(shù)d0、d1、d2的值：

2.2.2 計算坐標(biāo)系下的優(yōu)化檢測算法

根據(jù)M?ller算法原理，設(shè)兩個三角形A和B所在的平面分別為ΠA、ΠB。如果三角形A、B分別與平面ΠA、ΠB平面相交于LA、LB，則LA、LB必定在兩平面ΠA、ΠB的交線L上；若LA、LB有重疊部分，則兩三角形相交，否則判定為相離。通過求出B的頂點與A所在平面ΠA之間的距離以及A的頂點與B所在平面ΠB之間的距離，通過距離關(guān)系快速的排除基本元集合中不相交的三角形。但M?ller算法需要建立各個三角形所在的平面，計算時需要2次“求交”，這樣無法保證檢測的速度。

在算法相交判斷原理的基礎(chǔ)上進(jìn)行優(yōu)化，基于投影降低緯度的方式，通過引入新的計算坐標(biāo)系，在新坐標(biāo)系下簡化了運算，原本空間中三角形的運算轉(zhuǎn)化為二維平面問題，這樣能更容易判定兩個三角形的“相交”或者“不相交”的狀態(tài)。通過投影，在新計算坐標(biāo)系的xy以及xz面，求取三角形A、B頂點的正投影，然后在判斷兩個三角形投影關(guān)系時將三角形相交檢測分為共面與異面兩種情況，在新坐標(biāo)系下進(jìn)行邊向量之間的運算，通過向量運算的結(jié)果判斷三角形基本元之間的相交情況。

（1）判斷A與ΠB的是否存在交線段LA

從圖4可知，三角形A與ΠB的交線LA(P0P1)在H面上(z=0)?？臻g直線可以通過兩個點用參數(shù)式表示為：由A與Av所形成的梯形A0'A1'A1A0可以得到，P′0在A0'A1'上的參數(shù)t0'跟P0在A0A1上的參數(shù)t0相等；同理P0'在A0'A2'上的參數(shù)t1'跟P1在A0A2上的參數(shù)t1相等。而且P0'與P1'都有z=0，y=0，那么只需要判斷x即可。

圖4 坐標(biāo)系下兩三角形相交計算

（2）判斷LA在B內(nèi)的部分是否存在交線

在V面上求直線 Av與Bv交點與及其對應(yīng)的參數(shù)t，然后在H面上判斷0，如果或者 Q0=Q1，則兩個三角形碰撞。

算法偽代碼判斷流程描述如下：

輸入：第k層中A，B兩物體所包含的三角形Ai和Bj。

輸出：0未碰撞；1碰撞。

if（三角形B與平面H平行）

{

判定 A與 B是共面，goto（1）；

判定A與B是異面的，即A與B未相交，返回0；

}

else

{

if（AVandBV存在交點）

{

if(Q0Q1=φ)

A與B未相交，返回0；

if（Q0=Q1）

A與B相交，返回1；

if（Q0Q1與BH的某條邊重疊）

A與B相交，返回1；

}

else

A與B未相交，返回0；

}

當(dāng)A與B共面時，則判斷AH與BH兩個三角形位置關(guān)系的偽代碼如下：

if（AH與BH是相離的）

A與B未相交，返回0；

if（AH與BH是重疊的）

A與B相交，返回1；

if（AH與BH存在一個相交點）A與B相交，返回1；

if（AH與BH存在一條相交線）

A與B未相交，返回0；

詳細(xì)檢測階段算法除坐標(biāo)系的轉(zhuǎn)換外，其他算法均為二維平面上的運算，為了加速運算，在算法中加入拒絕判定，達(dá)到快速判斷Av與Bv是否相離目的。即在新的計算坐標(biāo)系的z方向，如果在Av上的3個z坐標(biāo)的符號相同，那么表明Av在Bv的上方或下方，則兩者是分離的，即兩個三角形未發(fā)生碰撞。

3 算法測試與分析

實驗是在CPU I5-2450M 2.50 GHz，內(nèi)存4 GB，獨立顯卡1 GB環(huán)境，應(yīng)用VB6.0的筆記本上實現(xiàn)。實驗完成2個對象相互碰撞的情況，對象由3dt格式（山東藍(lán)光軟件有限公司）的三角形基本元組成。在測試時插入2個定時計算器，記錄碰撞檢測時間，然后在相同的環(huán)境下分別應(yīng)用文獻(xiàn)[5-6，13]中的算法進(jìn)行了碰撞檢測，對比這幾種算法在相同的情況下得到相同正確的檢測結(jié)果所需的時間。提高及實驗場景的復(fù)雜度，三角形對數(shù)隨著場景復(fù)雜度的增加而增加，重復(fù)的進(jìn)行上述實驗，總共10組實驗，實驗結(jié)果如表1所示，算法效率對比如圖5所示。

通過表1與圖5可以發(fā)現(xiàn)，在三角形重疊數(shù)目相同時，在預(yù)處理階段提出的算法相比文獻(xiàn)[6]、[7]、[8]中提出的算法，碰撞檢測的時間明顯縮短。

在詳細(xì)檢測時，算法計算量的多少決定了算法運行的速度，算法中包括加減、乘除、比較以及絕對值等運算，將以上幾種運算所需要運行的時間看作是相同，則算法的計算量可以看作是幾種運算相加的總和。通過與經(jīng)典的M?ller、Tropp算法以及文獻(xiàn)[14]、[15]、[16]等提出的算法對比，各算法計算量的對比如表2所示。

表1 算法檢測時間對比表 ms

圖5 算法檢測時間對比圖

表2 不同算法間計算量的比較

盡管計算坐標(biāo)系的變換在本算法中占用了一定的時間份額，但經(jīng)過綜合的測試分析后，本算法坐標(biāo)系變換的開銷利大于弊，通過表2可以發(fā)現(xiàn)該算法的計算量要小于其他算法，即改進(jìn)算法檢測效率優(yōu)于其他算法。最后進(jìn)行算法的實際性能檢測：

測試內(nèi)容為待測物體分別應(yīng)用本文算法以及文獻(xiàn)[11]和[15]提出的算法進(jìn)行檢測，進(jìn)行時間與準(zhǔn)確性進(jìn)行對比，其中每次測試的預(yù)處理檢測階段均采用了該文提出的算法；測試是在lionking平臺（山東藍(lán)光軟件有限公司）進(jìn)行，圖6為測試場景，圓圈內(nèi)為相交區(qū)域。測試在相同的條件下進(jìn)行，每組重復(fù)測試5次求取平均值。

實驗結(jié)果如表3所示，詳細(xì)檢測階段的三角形相交檢測保證了檢測的準(zhǔn)確性，而且通過整體的時間對比可以發(fā)現(xiàn)，相比較其他兩個算法，本文提出的算法在保證碰撞檢測準(zhǔn)確性的前提下檢測速度大幅提高。

圖6 待測物體測試場景

表3 不同算法的時間與準(zhǔn)確性對比

4 結(jié)束語

現(xiàn)階段，快速、準(zhǔn)確的碰撞干涉檢測是虛擬現(xiàn)實領(lǐng)域的研究熱點，本文提出一種基于混合層次包圍盒與三角形相交相結(jié)合的混合碰撞檢測算法?；旌蠈哟伟鼑薪Y(jié)合了AABB和OBB各自的優(yōu)勢，同時優(yōu)化任務(wù)樹，提高了遍歷的速度。然后在新坐標(biāo)系下的向量計算的算法相比其他算法，在保證了檢測的準(zhǔn)確性的前提下提高了碰撞檢測的速度。然而任何碰撞檢測算法都不可能適用于各種各樣的場景，在應(yīng)對包含對象較少的場景時，該算法沒有顯著的優(yōu)勢，而更適合用于較為復(fù)雜且包含對象較多的場景。下一步，將研究涉及奇異性三角形基本元的相交檢測。