基于形狀分類的包圍盒碰撞檢測優化算法

孫勁光　吳素紅　周積林

1(遼寧工程技術大學電子與信息工程學院　遼寧 葫蘆島 125105)

2(遼寧工程技術大學研究生學院　遼寧 葫蘆島 125105)

?

基于形狀分類的包圍盒碰撞檢測優化算法

孫勁光1吳素紅2周積林2

1(遼寧工程技術大學電子與信息工程學院遼寧 葫蘆島 125105)

2(遼寧工程技術大學研究生學院遼寧 葫蘆島 125105)

摘要由于現有的包圍盒不能足夠緊密地包圍所有待檢測的物體，剔除不相交物體的效果差導致了碰撞檢測效率低。針對這個問題，提出一種基于形狀分類的包圍盒碰撞檢測優化算法。算法根據每個物體的偏球率將它們進行分類，形狀接近球體的，采用球包圍盒；形狀與球體偏離大的，采用OBB包圍盒，這能夠更加逼近真實的物體。同時，加入時空相關性和區域劃分策略來優化遍歷過程。實驗結果表明，該算法縮短了相交測試的時間，提高了碰撞檢測的效率。

關鍵詞碰撞檢測層次包圍盒形狀分類區域劃分時空相關性

OPTIMISATION ALGORITHM FOR BOUNDING BOX COLLISION DETECTION BASED ON SHAPE CLASSIFICATION

Sun Jinguang1Wu Suhong2Zhou Jilin2

1(School of Electronics and Information Engineering,Liaoning Technical University,Huludao 125105,Liaoning, China)2(Institute of Graduate,Liaoning Technical University,Huludao 125105,Liaoning, China)

AbstractSince current bounding boxes cannot sufficiently close to surround all the objects to be detected,the poor effect of weeding out disjoint objects leads to low efficiency in collision detection. In view of this,we propose a shape classification-based optimisation algorithm for bounding box collision detection. This algorithm classifies objects according to the similar-to-sphere rate of each object. For those similar to sphere in shape,it uses the sphere bounding box,and those deviating a lot from sphere in shape,the oriented bounding box will be used,in this way it can better approach real objects. At the same time,the spatiotemporal correlation and space division strategy are added to optimise the process of traversal. Experimental results show that the algorithm shortens the time of intersection test and improves the efficiency of collision detection.

KeywordsCollision detectionHierarchical bounding boxShape classificationSpace divisionSpatiotemporal correlation

0引言

碰撞檢測是一項用來檢測虛擬環境中的物體在某一時間點上是否占據了同一空間的技術，它可以應用在計算機動畫、計算機輔助設計、虛擬現實等各個領域。

由于碰撞檢測的應用極其廣泛，國內外的專家們已經對其研究多年，并已形成了比較經典的兩類算法：空間分割法[1]和層次包圍盒法。其中層次包圍盒算法由于構造簡單且檢測更精確，所以更常用。它的核心思想是用體積略大而幾何特性簡單的包圍盒來代替復雜的幾何對象，通過構造層次樹并對其進行遍歷來確定物體的相交狀態。

在層次包圍盒算法中，需要用緊密性比較好的包圍盒來逼近真實的物體，通過檢測包圍盒間的相交情況來剔除那些沒有碰撞上的物體。包圍盒的選取是碰撞檢測算法的重點，緊密性的好壞將直接影響檢測的效率。在早期，算法大多采用單一且結構簡單的包圍盒，如包圍球(sphere)[2]、軸向包圍盒(AABB)[3]、任意方向包圍盒(OBB)[4,5]、離散方向包圍盒(K-Dop)[6]。近幾年，專家們紛紛對包圍盒的結構進行了改進。在2010年，出現了雙層樹[1]結構，它是將層次包圍盒樹的每個節點分成內外兩層，分別采用不同的包圍盒。在2014年，出現了分層樹結構[7]，這是將每個物體的層次包圍盒樹分成幾個層次，分別采用不同的包圍盒。這些算法在一定程度上都提高了算法的效率，但是分成層結構造成了不同層內節點的相交，一定程度上會增加復雜性，而多層結構的存儲難免會造成數據的冗余。

現有的算法都是對每一個物體采用統一的包圍盒結構，而現實中的物體大多都形狀各異，同一種包圍盒結構很難適應所有的物體。所以本文考慮每個物體形狀上的差異，提出一種基于形狀分類的包圍盒碰撞檢測算法?？紤]到包圍盒的緊密性，將形狀近似球體的一類，采用球包圍盒，而形狀與球體相差大的一類，采用OBB包圍盒。此外，加入區域劃分策略和時間相關性理論，對碰撞檢測過程進行優化，從而整體提高了碰撞檢測的效率。

1算法的基本思想

算法分三個階段：區域劃分階段、物體分類階段和遍歷優化階段。

在物體分類階段，所有物體將在形狀上進行分類，分類的依據為本文定義的偏球率的大小。物體將被分為兩類，第一類的物體形狀逼近球體，在各坐標軸上的分布均勻，在包圍盒構造時，采用球包圍盒;第二類的物體形狀與球體相差較大，往往比較細長，在包圍盒構造時，采用OBB包圍盒。這一分類的操作是本文的一個重點，它能夠增加包圍盒對物體的擬合程度，從而更加精確地將不相交的物體剔除掉，減少基本三角形間的測試次數

在區域劃分階段，要將虛擬空間劃分成一個個小的長方體區域，只對同處于一個小區域的物體兩兩組合進行碰撞檢測。這一步可以減少大量的待檢測的物體對。

最后，在包圍盒遍歷優化階段，加入時間相關性理論，利用上一時刻存儲的關鍵節點信息來為這一時候判斷它們的碰撞情況提供線索，減少冗余的遍歷路徑，從而達到優化效果。

2基于形狀分類的包圍盒碰撞檢測優化算法

2.1物體在形狀上的分類

虛擬空間中的幾何物體都是有一個個三角面片構成，構成三角面片的點集完全能夠顯示出物體的特性，分析點集的分布可以確定物體的大致形狀。

定義1偏球率：物體與其所構成的包圍球之間的差異率。公式如下：

(1)

其中，n表示點集中點的個數，(xi,yi,zi)表示點集中第i個點的坐標，(ox,oy,oz)表示包圍球的中心坐標，r表示包圍球的半徑。

偏球率的大小反映出物體偏離其包圍球體的程度。數值越小越接近球，數值越大越偏離球體。

根據物體的形狀將物體分類的過程如下：

(1) 根據每個物體的點集計算出最小包圍球。

包圍球的球心坐標為各點的x、y和z坐標的均值，包圍球的半徑為球心與三個最大值坐標所確定的點間的距離。

(2) 根據式(1)計算每個物體的偏球率。

(3) 根據偏球率將物體分類。在這里需要設定一個偏球閾值，如果物體的偏球率超過該值說明這個物體偏離球的程度很大，那么就對其采用OBB包圍盒；如果物體的偏球率小于該值說明它十分逼近球體，那么就采用球對其包圍。

2.2包圍盒間的相交測試

層次包圍盒算法在實時檢測時，需要進行三類包圍盒間的相交測試，即Sphere-sphere、OBB-OBB、OBB-Sphere。

2.2.1Sphere-Sphere

判斷是否相交的依據為兩球心的距離是否大于兩球半徑之和，為減少計算的復雜度，采用平方形式：

|o1o2|2>(r1+r2)2

(2)

其中，o1、o2為兩個包圍球的球心，r1、r2為兩個包圍球的半徑，|o1o2|為兩球心的距離。

式(2)成立，這兩個包圍球是相離的，否則，這兩個包圍球被判定為相交。

2.2.2OBB-OBB

1) 接觸情況的預判斷

在檢測兩個OBB包圍盒是否相交之前，先對它們的接觸情況進行預測[8]，這樣可以避免一些不必要的相交測試過程。

有2個待檢測的OBB包圍盒Bi和Bj，oi(xi,yi,zi)，oj(xj,yj,zj)分別表示兩個包圍盒的中心。oi.max和oi.min分別是包圍盒Oi到其中心的最大距離和最小距離，oj.max和oj.min分別是包圍盒Oj到其中心的最大距離和最小距離，D表示Oi到Oj的距離。通過下面不等式預測兩個OBB間的相交情況。

(3)

D

(4)

D>Oi.max+Oj.max

(5)

若式(4)成立，兩個OBB必相交，返回碰撞檢測結果為未碰撞；若式(5)成立，這兩個OBB必定不相交，返回碰撞檢測結果為碰撞；否則，需要繼續繼續執行OBB間的基本相交測試。

2) 相交測試

采用分離軸理論[9]來實現OBB的相交測試。如圖1所示，對于某一軸L，若兩個包圍體投影半徑之和小于中心點之間的投影距離，即|T·L|>r1+r2，那么它們就是相離的。

圖1　分離軸理論

最多需要測試15個潛在分離軸來確定OBB的相交狀態。這些軸包括B1的三個坐標軸，B2的三個坐標軸以及垂直于每一軸的9個軸。若在上述軸上的任一軸上沒有產生重疊，那么這兩個OBB是分離的，若檢測完所有軸，每個軸上都產生重疊，那么這兩個OBB就是相交的。

2.2.3Sphere-OBB

類似于OBB-OBB間的相交測試，判斷Sphere-OBB是否相交的依據同樣是不等式|T·L|>r1+r2。假設有包圍球O和OBB包圍盒B，r為O的半徑，bi為B的長寬高長度的一半(i=1,2,3)，Bi是平行于B的軸單位向量(i=1,2,3)，T為兩包圍盒中心的距離，L為平行于OBB分離軸的單位向量。r1為r在L上的投影，r2為bi在L上的投影之和。那么得到公式如下：

r1=r

(6)

(7)

(8)

若式(8)成立，則兩個包圍盒不相交，否則繼續計算它們在其他2個分離軸上的投影是否重疊，若三個軸上的投影都不滿足該不等式，那么判斷這兩個包圍盒相交。

2.3算法的優化

2.3.1區域劃分策略

虛擬環境中的物體眾多，如果將所有物體兩兩組合進行檢測，那么系統每秒鐘的測試量將是巨大的。很可能會造成“刺穿”[10]甚至“遺漏”現象，這嚴重影響了碰撞檢測的實時性。

為了及時檢測出物體對間的碰撞，本文在構造層次包圍盒之前加入區域劃分策略[14]。該策略是將整個虛擬空間劃分為一個個小的長方體區域，只對同處于一個小區域內的物體們執行包圍盒碰撞檢測算法。在這里，將每個物體的相鄰物體(同處于一個小區域的)存起來，針對每個物體實現碰撞檢測的并行化。

現空間中有n個物體，它們的標識依次為O1，O2，…，On，為每一個物體的數據結構中都添加一個相鄰鏈表AdList，用來存儲該物體的相鄰物體。算法的具體過程如下：

(1) 將整個空間分割成小的長方體單元。在這里將所有物體長寬高的均值作為長方體單元的大小。

(2) 創建一個數組Array，用于存放空間中的所有物體。

(3) 遍歷數組Array并對其中的每一個物體構造AdList鏈表，鏈表中存放與該物體占據同一個單元的比自身標識序號大的其他物體的標識。

(4) 為每個AdList鏈表不為空的物體分配一個線程[11]，并行地執行與其相鄰的物體間的碰撞檢測，實現檢測的并行化。

2.3.2時間相關性

在虛擬環境中物體雖然都在隨機運動，但是它們的運動卻是連續的，而不是每一個時刻都在瞬移。那么在相鄰時間采樣點上，物體的位置和狀態往往變化很小。也就是說，當前時間點兩物體的相交狀態與上一時間采樣點是關聯的。如果兩個物體碰撞了，那么在下個時間采樣點物體也很有可能是碰撞的，并且碰撞的位置是相近的；如果兩個物體沒碰撞，那么在下個時間采樣點也很可能不發生碰撞[12]，這就是時間相關性理論。

引入時空相關性，可以通過記錄上一時間采樣點兩物體的相交測試狀態，為下一時間采樣點判斷它們的相交狀態提供方便，從而來優化遍歷過程。在這里，記錄一些關鍵節點[13](未發生碰撞的內部節點和遍歷到的葉節點)，在下一個時間采樣點就可以不必從樹根開始向下遍歷，而是從這些關鍵節點開始向下遍歷，減少重復的遍歷路徑。由于這些關鍵節點所包含的子樹的交集是空集，并集是全集，所以整個遍歷過程是正確完整的。

下面是一個用二叉樹表示的對象，它在兩個相鄰時間采樣點(t，t+1時刻)與其他對象發生碰撞的情況如圖2和圖3所示。其中灰色節點表示與其他對象發生了碰撞，白色節點表示與其他對象未發生碰撞，右側list表存儲當前采樣點的關鍵節點。

圖2　t時刻物體的碰撞情況以及對應的關鍵點表

圖3　t+1時刻物體的碰撞情況以及對應的關鍵點表

根據圖2和圖3可知，在t時刻，需要存儲的關鍵節點為：(a2,a7,a10,a11)，在t+1時刻，需要存儲的關鍵節點為：(a4,a5,a10,a11,a12,a13)。在t+1時刻進行層次樹遍歷時，如果按傳統的遍歷過程(a1,a2,a4,a5,a3,a6,a10,a11,a7,a12,a13),將執行11次相交測試。如果有了t時刻的list表，就可以從關鍵節點開始向下遍歷(a2,a4,a5,a10,a11,a7,a12,a13)，將簡化執行8次相交測試。層次包圍盒樹的高度越高，時間相關性對遍歷過程的優化效果越好。

2.4算法的偽程序

CollisionDetection(Array)

描述：該函數依次執行物體分類，區域劃分，包圍盒遍歷優化函數操作，得到每個物體對的碰撞結果。其中Array為存儲所有物體的數組，Array.length表示數組的大小，Oi表示Array數組中第i個物體，Oi.Adlist.length表示第i個物體的相鄰鏈表的大小。

輸入：Array

輸出：Result

//對物體進行分類

For i=0 To Array.length

{

If(Oi的偏球率<=0.143)

//1/7約等于0.143

{//物體Oi劃分到第一類，對其構造球包圍盒

CreateSphere(Oi);

}

Else

{//物體Oi劃分到第二類，對其構造OBB包圍盒

CreateOBB(Oi);

}

}

//區域劃分并執行包圍盒碰撞檢測算法

For i=0 To Array.length

{ For j=0 To Array.length

{//構造每個物體的相鄰鏈表AdList

CreateAdList(Oj)

}

If(Oi.AdList不為空)

{//創建線程

CreateThread()

For k=0 To Oi.Adlist.length

{ //并行執行包圍盒遍歷優化算法

Traverse(Oi,Ok,result)

//更新兩物體的關鍵點表List

UpdateList(Oi,Ok)

}

}

}

3實驗

本文算法在Win 7系統下，在具有CPU 2.2 GHz，四核處理器的PC機上應用VS2010和OpenGL實現。實驗場景中，有40個形狀各異的物體進行隨機運動，三角面片的個數多達9000個，如圖4所示。

圖4　碰撞場景

為了證實本文算法的優越性，我們做了兩個實驗。

實驗一偏球閾值對本算法的影響

通過逐步變化偏球閾值的大小來統計本文算法運行1000步的平均碰撞檢測時間(ms)。實驗結果如圖5所示。

圖5　偏球閾值的設定對本文算法的影響

由圖可以看出，偏球閾值的大小在一定程度上會影響本文算法的效果。我們發現，當偏球閾值大約等于1/7時，運行1000步的平均碰撞檢測時間達到最小。

實驗二各算法與本文算法的比較

實驗分別采用包圍球，OBB和本文采用的分類包圍盒進行物體間的碰撞檢測，在這里，偏球閾值設為1/7。統計運行1000步的平均碰撞檢測時間(ms)和幀頻(frame/s)如表1所示。

表1　各算法在碰撞檢測時間和幀頻上的對比

從表1可以看出，采用形狀分類的包圍盒方法的碰撞檢測算法的平均碰撞檢測時間比采用統一包圍盒的碰撞檢測時間要小，并且幀頻也稍有提高。在加入時間相關性和區域劃分策略后，算法得到了進一步的優化，平均碰撞檢測時間縮小到37.206 ms，場景繪制速度達到了38.42 frame/s。

4結語

本文提出了一種基于物體形狀分類的包圍盒碰撞檢測優化算法。算法根據每個物體的偏球率將物體分成了兩類，對不同類別的物體采用不同的包圍盒，從而增加了包圍盒的緊密性，達到了很好的碰撞剔除效果。除此之外，使用時空相關性來簡化遍歷過程，利用區域劃分策略來減少待檢測的物體對，這使碰撞檢測過程得到了優化。最后，通過對比實驗，證明了相對于其他基于統一包圍盒的碰撞檢測算法，本文算法所需的碰撞時間更少，碰撞檢測的效率在一定程度上得到了提高。

參考文獻

[1] Chang J W,Wang W,Kim M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2010,42(1):50-57.

[2] Jiménez P,Thomas F,Torras C.3D collision detection: a survey[J].Computers & Graphics,2001,25(2): 269-285.

[3] Zhang L.The research and realization of collision detection in virtual reality[J].Journal of Communication and Computer,2011,8(8): 693-696.

[4] Stüvel S A,Magnenat Thalmann N,Thalmann D,et al.Hierarchical structures for collision checking between virtual characters[J].Computer Animation and Virtual Worlds,2014,25(3-4): 333-342.

[5] Seiler C,Pennec X,Reyes M.Geometry-aware multiscale image registration via OBBTree-based polyaffine log-demons[M]//Medical Image Computing and Computer-Assisted Intervention-MICCAI 2011.Springer Berlin Heidelberg,2011: 631-638.

[6] Klosowski J T,Held M,Mitchell J S B,et al.Efficient collision detection using bounding volume hierarchies of k-DOPs[J].Visualization and Computer Graphics,IEEE Transactions on,1998,4(1):21-36.

[7] Ding X J.Research on Collision Detection Algorithm Based on Combined Bounding Box[J].Advanced Materials Research,2014,912(2):1353-1356.

[8] 郭凌云,鄭延斌,劉晶晶.基于時空相關性的快速碰撞檢測算法[J].計算機應用與軟件,2013,30(5):174-176.

[9] 張應中,范超,羅曉芳.凸多面體連續碰撞檢測的運動軌跡分離軸算法[J].計算機輔助設計與圖形學學報,2013,25(1):7-14.

[10] 方彬,王竹林,郭希維.基于完AABB的四維時空層次包圍盒碰撞檢測方法[J].計算機測量與控制,2014,22(12),397-420.

[11] 趙建斌,李靈巧,楊輝華.線程級并行計算在圖形渲染引擎中的研究[J].計算機工程與設計,2011,32(12):4143-4146.

[12] 裴嵩.面向虛擬維修的實時碰撞技術研究[D].南京:南京航空航天大學,2012.

[13] 蔣健勛,方志剛,徐潔,等.基于 Sphere-OBB 的改進碰撞檢測算法及其應用[J].計算機工程與應用,2011,47(17):172-174.

[14] 水泳.虛擬現在中連續碰撞檢測算法研究[D].合肥:中國科技大學,2013.

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.056

收稿日期：2014-08-12。國家科技支撐計劃項目(013bah120 f00)。孫勁光，教授，主研領域：圖形圖像處理與人臉識別。吳素紅，碩士生。周積林，碩士生。