基于混合包圍盒與三角形相交的碰撞檢測優化算法

孫敬榮，盧新明

1.山東科技大學，山東 青島 266590

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

1 引言

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

2 算法原理

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

圖1 碰撞檢測流程圖

2.1 預處理檢測階段

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

2.1.1 AABB-OBB混合包圍盒構造的優化

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

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

協方差為：

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

物體的表面積為：

各個三角面片的中心為：

則協方差矩陣為：

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

2.1.2 AABB-OBB混合層次包圍盒樹的優化

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

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

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

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

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

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

步驟3把之前相交的節點重新標記為A和B，然后返回步驟2。

圖2 AABB-OBB結構圖

2.2 碰撞檢測的詳細檢測

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

2.2.1構建計算坐標系

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

圖3 構造計算坐標系

P0P1的單位向量為：

新舊兩個坐標系之間的坐標變換矩陣為：

其中根據計算坐標系原點P0求出參數d0、d1、d2的值：

2.2.2 計算坐標系下的優化檢測算法

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

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

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

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

圖4 坐標系下兩三角形相交計算

（2）判斷LA在B內的部分是否存在交線

在V面上求直線 Av與Bv交點與及其對應的參數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；

}

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

if（AH與BH是相離的）

A與B未相交，返回0；

if（AH與BH是重疊的）

A與B相交，返回1；

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

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

A與B未相交，返回0；

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

3 算法測試與分析

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

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

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

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

圖5 算法檢測時間對比圖

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

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

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

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

圖6 待測物體測試場景

表3 不同算法的時間與準確性對比

4 結束語

現階段，快速、準確的碰撞干涉檢測是虛擬現實領域的研究熱點，本文提出一種基于混合層次包圍盒與三角形相交相結合的混合碰撞檢測算法。混合層次包圍盒結合了AABB和OBB各自的優勢，同時優化任務樹，提高了遍歷的速度。然后在新坐標系下的向量計算的算法相比其他算法，在保證了檢測的準確性的前提下提高了碰撞檢測的速度。然而任何碰撞檢測算法都不可能適用于各種各樣的場景，在應對包含對象較少的場景時，該算法沒有顯著的優勢，而更適合用于較為復雜且包含對象較多的場景。下一步，將研究涉及奇異性三角形基本元的相交檢測。