基于混合包圍盒與三角形相交的碰撞檢測(cè)優(yōu)化算法

孫敬榮，盧新明

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

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

1 引言

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

2 算法原理

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

圖1 碰撞檢測(cè)流程圖

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

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

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

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

三角形各個(gè)頂點(diǎn)的均值為：

協(xié)方差為：

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

物體的表面積為：

各個(gè)三角面片的中心為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P0P1的單位向量為：

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

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

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

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

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

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

從圖4可知，三角形A與ΠB的交線LA(P0P1)在H面上(z=0)?？臻g直線可以通過兩個(gè)點(diǎn)用參數(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)系下兩三角形相交計(jì)算

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

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

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

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

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

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

{

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

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

}

else

{

if（AVandBV存在交點(diǎn)）

{

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共面時(shí)，則判斷AH與BH兩個(gè)三角形位置關(guān)系的偽代碼如下：

if（AH與BH是相離的）

A與B未相交，返回0；

if（AH與BH是重疊的）

A與B相交，返回1；

if（AH與BH存在一個(gè)相交點(diǎn)）A與B相交，返回1；

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

A與B未相交，返回0；

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

3 算法測(cè)試與分析

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

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

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

表1 算法檢測(cè)時(shí)間對(duì)比表 ms

圖5 算法檢測(cè)時(shí)間對(duì)比圖

表2 不同算法間計(jì)算量的比較

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

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

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

圖6 待測(cè)物體測(cè)試場(chǎng)景

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

4 結(jié)束語

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