三維物體碰撞檢測包圍盒算法分析

摘要:隨著計算機技術的發展，人們對虛擬現實、分布式交互仿真的需求大大推動了計算機圖形學的發展。碰撞檢測，特別是軟體碰撞檢測問題開始成為研究的熱點。主要介紹AABB(沿坐標軸的包圍盒)和OBB(方向包圍盒)算法兩種常用包圍盒技術，并從效率、難易程度等方面對其進行比較，結合AABB算法和OBB算法，提出一種改進算法，在一個具有大量靜態對象的場景中，先利用AABB算法測試靜態物體和動態物體的碰撞，然后通過AABB算法過濾后的動態物體則使用OBB算法進行碰撞檢測。試驗結果表明，該方法在進行精確的碰撞檢測時，性能有明顯的提高。

關鍵詞:虛擬現實;碰撞檢測;AABB;OBB;包圍盒

中圖分類號:TP391.9 文獻標識碼:A 文章編號:1672-3198(2010)02-0266-02

1 算法思想

包圍盒算法是目前三維交互軟件中常用的碰撞檢測算法，其優點是能夠實現快速碰撞檢測。在這里最具代表性的就是AABB算法和OBB算法。

1.1 軸平行包圍盒AABB 算法

AABB(Axis-Aligned Bounding Box)是進行碰撞檢測的三維幾何體的外接平行六面體，它的每條邊都平行于坐標軸。因此描述一個AABB包圍盒只需要六個標量，在構造AABB時，要沿著物體的局部坐標系的軸向進行構造。故由AA BB構造的包圍盒具有一致的方向。圖1給出了一個使用AABB包圍盒的例子，它可以很簡單確定包圍盒的尺寸，AABB內的任意一點P(x，y，z)都需滿足:

從AABB包圍盒的構造過程分析，它的優點有以下幾點:

(1)構造難度低。因為只需分別計算物體各個元素頂點的x、y、z坐標的最大值和最小值，如果一個頂點的個數為n，只需6n次比較運算。

(2)存儲量很小。只需6個浮點數。

(3)相交測試復雜度低。由于立方體有六個面，所以只需在xy、xz、yz 三個面投影兩個物體6個面，故只需計算6次即可。

(4)變形物體碰撞適用度較大。與OBB算法相比其缺點是緊密性較差，尤其是對具有凹凸面的多面體，用AABB將留下很大空隙，導致大量的冗余包圍盒相交測試。

1.2 任意方向包圍盒OBB算法

OBB(Oriented Bounding Box)是最貼近三維幾何體的平行六面體。其最大的特點是方向的任意性，這使得它可以根據三維對象的形狀來包圍該對象。雖然該算法實現復雜，但不會對場景的運行速度產生很大的影響。它的計算相對復雜，需要對包圍盒的方向、中心位置、尺寸分別進行計算。其中，中心位置和方向是用均值和協方差矩陣統計量來計算的。尺寸是通過位置和方向兩個量進行計算。需要進行碰撞檢測的幾何體是由很多三角形面片組成，設三角形集的第i個三角形的頂點矢量為pi、qi和ri組成的包圍盒包圍對象的三角面片數為n，則包圍盒的中心位置m為:

協方差矩陣Cjk的三個特征向量是正交的，規范化后可以作為一個基底，用于確定OBB方向。分別計算物體所包含的各個元素的頂點在該基底的三個軸上投影的最大值和最小值，以確定該OBB大小。如圖2 OBB包圍盒:

從OBB包圍盒的構造過程分析，它主要得優點是緊密性好，因為其方向的任意性，可根據被包圍對象的形狀盡可能緊密地包圍對象;物體在旋轉時包圍盒更新計算量小。當幾何對象發生旋轉運動后，只要對OBB的基底進行同樣的旋轉即可。因此比較適用于剛體的碰撞。其缺點是構造難度大，構造給定物體的OBB 的計算復雜;存儲量相對于AABB較大，存儲一個OBB需要15個浮點數。如果兩個OBB包圍盒在一條軸線上的投影不重疊，那么可以判定這兩個包圍盒不相交;兩個OBB的相交測試最多需要15次比較運算、60次加減運算、81次乘法運算和24次絕對值運算;變形體碰撞適用度小，當幾何體對象發生旋轉運動后，只要對OBB的基底進行同樣的旋轉即可。因此適用于剛體的碰撞檢測。

通過對AABB算法和OBB算法的分析比較(表1)可知，在三維場景中可以根據不同類型三維物體使用適當算法去進行碰撞檢測。

2 算法改進

對于虛擬場景中某段時間內的不活躍模型，如果采用OBB相交判斷算法檢測它們之間是否相交，會浪費很多時間。為了提高虛擬場景碰撞檢測的實時性能，可以按照AABB和OBB的優點對場景中的對象進行分類，即將碰撞檢測分為兩個階段進行:第一階段用簡單的AABB算法排除不可能相交的模型對，第二階段運用OBB算法對未被排除并且在該時間活躍的模型對進行精確的OBB相交判斷。其流程如圖3所示。

2.1 AABB相交對的計算

因為AABB的三邊與該幾何對象的局部坐標軸分別平行，所以兩個AABB包圍盒相交當且僅當它們在三個坐標軸的投影都相交。

傳統的AABB算法在物體發生碰撞時，對所有的AABB兩兩進行相交判斷，這樣將會浪費很多計算時間。一般而言，模型的空間位置以及模型間的空間位置關系在連續的兩次檢測之間變化不會很大，因此AABB相交對的集合在兩次檢測之間的變化也不會很大。那么可以在計算AABB相交對時利用緩沖區中上次計算結果，將會節省很多計算時間。

組織2條鏈表，一條鏈表存儲由AABB算法計算發生碰撞的一對幾何體，其節點的數據結構如下:

幾何對象發生碰撞的次數:其作用是為了防止緩沖區過大，采用最近最少使用算法將碰撞頻率最低的幾何體從鏈表中刪除。

2.2 OBB相交對的計算

相對于AABB緩沖鏈表來說，OBB的緩沖鏈表的設計要復雜些。在三維場景中，通常在幀和幀之間都會有很強的關聯性，這就意味著虛擬環境中物體從一幀變化到另一幀時是相對靜止的。假設新的碰撞總是會在上一次碰撞的多邊形處發生，那么應該把上次碰撞的相關信息存入緩沖區供當前碰撞檢測使用。

該鏈表節點的數據結構如下:

StructOBBNode

{

幾何體信息1，

幾何體信息2，

碰撞時幾何信息

}

其中幾何體信息1、幾何體信息2是存放運動物體的幾何信息。

碰撞時的幾何信息包含兩個幾何體發生碰撞時三角形的信息、標志物體是否發生過碰撞的邏輯變量、標志該幾何信息是否被反問過、時間標識。其數據結構如下:

Struct 碰撞幾何信息

{

發生碰撞的位置(三角形位置)，

Bool bCollide，//是否發生了碰撞

Bool bUse， //碰撞幾何信息是否使用過

DateDtime//發生碰撞的時間

}

每當需要檢測該物體的碰撞情況時，系統先檢測該物體的碰撞幾何信息字段中存放的三角形的碰撞情況，如果發生碰撞，則直接將結果返回;如果沒有發生碰撞，那么該緩沖區中的三角形此時也未發生碰撞，此時需要重新檢測該物體的方向包圍盒，如果新的碰撞發生，那么將發生碰撞的三角形的幾何信息返回給系統，并將緩沖區幾何信息字段中的所有值全部更新。

試驗采用VC基于OpenGL實現以上改進算法。試驗用例為10個球體、4個墻壁和一個地面。在物體與墻壁或者是地面發生碰撞，則建立AABB包圍盒并將碰撞幾何體存入AABB緩沖鏈表，當球體和球體進行碰撞時，則建立OBB包圍盒，將碰撞的球體以及碰撞的幾何信息存入到OBB緩沖鏈表中。

改進前與改進后的碰撞檢測算法所用時間的平均值如圖4所示。由圖4可見，改進后的算法在效率上優于傳統的算法，時間減少大約10%。

碰撞的效果如圖5所示，雖然在三維場景中運動的球體比較多，但是程序能夠準確判斷球體之間和球體與墻壁和地面所發生的碰撞。

3 結語

通過對三維場景中的不同類型三維模型分別建立AABB包圍盒和OBB包圍盒緩沖鏈表，通過遍歷兩條鏈表來對當前幾何體進行重疊測試，最后確定兩個幾何體是否相交，并進行相應的碰撞響應。通過對AABB和OBB方法的理論分析和算法實現，在OpenGL接口環境下實現了三維模型的顯示、包圍盒的計算、AABB緩沖鏈表和OBB緩沖鏈表的建立，實現了對多個靜態物體與動態物體、動態物體與動態物體的實時碰撞檢測，實驗結果表明改進算法的可行性和有效性。