基于空間剖分和分類遍歷的碰撞檢測算法

劉 昭，李 偉，趙魯陽，單聯海

（中國科學院上海微系統與信息技術研究所 上海200050）

基于空間剖分和分類遍歷的碰撞檢測算法

劉 昭，李 偉，趙魯陽，單聯海

（中國科學院上海微系統與信息技術研究所 上海200050）

針對碰撞檢測實時性與精確性不高的問題，提出一種基于空間剖分和分類遍歷的碰撞檢測算法。首先在空間剖分階段利用八叉樹空間剖分剔除不相交的物體對，在剖分子空間內構建混合層次包圍盒，利用分類遍歷的方法對層次包圍盒進行遍歷，有效減少了相交測試的次數。實驗表明，該算法有效縮短了碰撞檢測所需時間，在復雜環境下算法優勢明顯。

碰撞檢測；空間剖分；混合層次包圍盒；分類遍歷

隨著計算機仿真技術的發展，以三維場景為基礎的虛擬現實技術和對自然環境的渲染技術已成為重要研究方向，可廣泛應用于城市規劃、軍事模擬、突發事件模擬等領域[1-2]。隨著三維模型復雜性的增加和人們對于場景真實感要求的提高，碰撞檢測的實時性與高效性成為當前研究熱點。

從空間角度對碰撞檢測算法進行分類，可以分為基于圖像空間的碰撞檢測算法和基于物體空間的碰撞檢測算法[4]。

基于圖像空間的碰撞檢測算法是利用三維模型在二維平面上的投影圖像和相關的深度信息判斷是否存在碰撞，這類算法主要是利用硬件輔助和模板緩存來加速碰撞檢測的過程，對計算機性能的要求比較高[3]。

基于物體空間的碰撞檢測算法是利用三維模型的幾何特性來判斷是否存在碰撞。這類算法又可分為空間剖分法和層次包圍盒法。空間剖分法是按照某種劃分規則將空間剖分成若干個子空間，對同一子空間內的物體進行相交測試。常用的空間剖分算法分為3種：網格、樹以及空間排序算法[5]。層次包圍盒法是利用一個簡單的體空間實現對一個具有復雜形狀的物體的包圍，通過體空間的碰撞檢測代替物體的碰撞檢測。常用的層次包圍盒算法有包圍球（Sphere）、軸向包圍盒（Axis-Aligned Bounding Box AABB）、方向包圍盒（oriented bounding box，OBB）和固定方向凸包（Discrete Orientation Polytopes，k-Dops）等[6]。

國內外學者已經對碰撞檢測進行了較為深入的研究。Gottschalk等人提出了基于OBB包圍盒的碰撞檢測算法，稱為RAPID算法[7]，有效提高了剛體間碰撞檢測速度。Govindaraju等人提出了一種基于圖形硬件加速的碰撞檢測算法[8]，通過計算潛在碰撞集，實現了可形變物體間的快速碰撞檢測。S Katz等人將模糊聚類分割思想應用到空間剖分中，很好的避免了過分割和分割不完全的情況[9]。JW Chang等提出一種基于Sphere-OBB的混合包圍盒碰撞檢測算法[10]，充分利用了Sphere包圍盒構造簡單和OBB包圍盒檢測精確的特性。

隨著碰撞檢測精確性和實時性要求的提高，單一的空間剖分法或者層次包圍盒法難以滿足要求，文中提出了二者結合的快速碰撞檢測算法，算法優勢如下：

1）使用八叉樹空間劃分來快速排除不相交的物體，使碰撞檢測集中到每一個子空間中；

2）對占用同一子空間的物體進行碰撞檢測時，構造Sphere-OBB混合層次包圍盒；

3）對混合層次包圍盒采用基于分類的深度優先遍歷算法，提高遍歷速度。

1 算法描述

1.1 空間剖分

空間剖分法提供了粗略的碰撞檢測方案：將檢測空間劃分為多個區域，并在同一空間內測試物體是否相交，降低了相交測試的次數。文中選用八叉樹作為空間剖分樹。

八叉樹空間剖分[11]是基于樹型結構的空間劃分方法，在三維空間的層次結構劃分中效果良好。樹的每一個父節點包括8個子節點，而且每一個子節點代表一個子空間，其根節點是包含全部物體的最小立方體，將這一立方體沿3個坐標軸均勻分割得到8個子空間節點。

如果剖分后的子空間內物體數量仍然較多，則再次對子空間進行八叉樹劃分，直到子空間內的物體數量滿足要求為止。

1.2 混合層次包圍盒

混合層次包圍盒選取的依據是平衡碰撞檢測的實時性和精確性。對于包圍盒優劣的評價一般從相交測試復雜度、緊密性以及更新計算量3個方面入手[12]，幾種經典的包圍盒的比較結果如表1所示。

表1 幾種包圍盒特性比較

Gottschalk提出了層次包圍盒性能的計算公式[7]，如下所示：

在上述公式中，可以通過構造更緊湊的包圍盒來降低NV和NP的值，通過實現快速檢測降低CV和CP的值。但是這兩組值之間存在一個矛盾關系，當包圍盒更加緊湊時，相交測試代價會越大，但是會降低相交測試的數量，所以需要在兩者之間實現一個平衡。

因此選取Sphere和OBB包圍盒來構建混合層次包圍盒，利用Sphere包圍盒更新簡單以及相交測試復雜度低的優勢進行初步碰撞檢測，利用OBB包圍盒緊密性好的優勢進行精確的碰撞檢測[13]，整體按照自頂向下[14]的方式構造混合層次包圍盒。

1.3 層次包圍盒的遍歷

傳統的碰撞檢測包圍盒樹遍歷方法有單一下降深度優先遍歷法和同步下降深度優先遍歷法。單一下降深度優先遍歷法是先將一棵樹遍歷到葉子節點，再對另一棵樹進行遍歷；同步下降深度優先遍歷法是同時對兩棵樹進行遍歷，直至下降到葉子節點。研究表明，對兩棵包含n個葉子節點的層次包圍盒樹A和B進行碰撞檢測，如果采用單一下降深度優先遍歷法，最多需要執行22n-1-1次相交測試；如果采用同步下降深度優先遍歷法，最多需要執行（22n-1）3次相交測試[15]。單一下降深度優先遍歷的劣勢在于它不能發揮二叉樹結構的優勢；同步下降深度優先遍歷的劣勢在于當待遍歷物體對的結構差異較大時，不能有效縮減搜索空間。

基于以上分析，文中提出一種基于分類的層次包圍盒遍歷方法：對于結構相似的待檢測物體對，采用同步下降深度優先遍歷法；對于結構不相似的待檢測物體對，提出一種改進單一下降深度優先遍歷法。我們通常用二叉樹節點的左右子樹的深度差表示該節點的平衡因子。通過定義兩個層次包圍盒樹對應節點的平衡因子差值的絕對值來判斷結構相似性，定義分類公式:

其中BAi表示樹A中節點i的平衡因子；BBi表示樹B中與A中節點i相同位置節點的平衡因子；Di表示節點i的平衡因子差值。當Di都不大于1時表示兩個樹結構相似，否則就不相似。

圖1 a、b、c三棵樹結構

圖2 平衡因子差樹

如圖1表示3個樹結構a、b、c各個結點的平衡因子，圖2表示樹結構a、b、c兩兩之間的平衡因子差樹，從圖2中可以看出a樹和b樹結構不相似，a樹和c樹結構不相似，b樹和c樹結構相似。樹a的平衡性和樹b、樹c都不相同，說明樹a存在細節較為精細的部分需要額外處理。

對于改進單一下降深度優先遍歷過程，首先選擇額外細節較多的樹a進行遍歷，當下降到樹a的結點的平衡因子差值大于1時，轉而對樹b進行遍歷，如果樹b中出現平衡因子差值大于1時，再轉回對樹a進行遍歷，如此循環，直到完成碰撞檢測。

2 實驗結果及分析

本實驗程序運行的硬件環境是Windows 7系統，CPU 2.4 GHz的PC機，軟件環境是Visual Studio 2010和OpenGL開發。實驗場景分為兩種，一種是模擬場景，另一個是軟件應用場景。

實驗場景1在Visual Studio2010中利用OpenGL搭建模擬場景，場景中有多個大小形狀各不相同的物體在隨機移動，為了驗證算法性能，將本文算法和經典的I-COLLIDE算法進行對比，比較不同物體密度的情況下碰撞檢測時間的變化情況，結果如圖3所示。

圖3 物體數量與碰撞檢測時間關系

從圖3看出，空間中物體數量越多，本算法的優勢越明顯，這說明本文算法的空間剖分直接減少了不相交物體的檢測次數，再通過Sphere包圍盒初步篩選，在OBB包圍盒的碰撞檢測階段通過分類遍歷的方法進一步加快了檢測速度，從而有效改善了碰撞檢測效率。

實驗場景2在Visual Studio 2010中，基于虛幻引擎搭建一個消防演練場景，將本文提出的碰撞檢測算法應用到水流和火焰的碰撞檢測中，測試場景運行的流暢性。在實時系統中畫面最低的流暢度要求是30幀/秒的刷新頻率。文中分別在單個消防員單個著火點、多個消防員多個著火點以及多個消防員單個著火點的情況下測試幀數變化，場景環境如圖4所示。

圖4 消防滅火場景

在上述3種消防救援場景中，分別對3個場景下的幀數變化進行統計，以10秒為一個時間間隔，統計10秒幀數的平均值作為當前幀數，統計結果如圖5所示。

圖5 復雜場景下幀數隨時間變化情況

從圖5中可以看出幀數隨著運行時間的增加和碰撞檢測復雜度的增加并沒有顯著的降低，都能滿足實時性的要求。

3 結 論

針對碰撞檢測的實時性和精確性不足的問題，文中提出一種基于空間剖分和分類遍歷的混合層次包圍盒碰撞檢測算法。文中首先對物體空間進行八叉樹剖分，在子空間內構建Sphere-OBB混合層次包圍盒進行碰撞檢測，減少了不相交物體的檢測，在碰撞檢測的初級階段，利用Sphere包圍盒進一步篩選不相交物體對，再進行OBB包圍盒的精確碰撞檢測，在OBB包圍盒的碰撞檢測中采用分類遍歷法進行快速碰撞檢測，這種方法在保證精確性的情況下提高了碰撞檢測的實時性。

碰撞檢測算法在虛擬裝配系統仿真中發揮著重要作用，為了實現用戶和系統的友好交互，需要快速給出碰撞物體的位置信息，對碰撞檢測提出了更高的要求，而本算法有效提高了碰撞檢測的實時性和精確性，為虛擬裝配系統的應用研究提供了一個行之有效的解決方案。

[1]趙沁平.虛擬現實綜述[J].中國科學，2009（39）:2-46.

[2]Burdea G，Coiffet P.Virtual Reality Technology[J].Presence Teleoperators&Virtual Environments，2003，12（6）:663-664.

[3]卞鋒，江漫清，桑永英.虛擬現實及其應用進展[J].計算機仿真，2007，24（6）:1-4.

[4]陳承收.基于云模型與GPU緩存技術的快速碰撞檢測算法研究[D].長春工業大學，2011.

[5]Ericson C.實時碰撞檢測算法技術[M].劉天慧譯.北京:清華大學出版社，2010.

[6]姜曉路，劉淵.一種新的基于混合層次包圍盒的碰撞檢測算法[J].計算機工程與應用，2012，48（6）:143-145.

[7]Gottschalk S，Lin M C，Manocha D.OBB-Tree:a Hierarchical structure for rapid interference detection[C]// Proceedings of Computer Graphics Conference.New York：ACM，1996：171-180.

[8]Govindaraju N K，Redon S，Lin M C，et al.Cullide: Interactive Collision Detection Between Complex Models In Large Environments Using Graphics Hardware [J]. Proceedingsofthe Siggraph/eurographicsWorkshop on Graphics Hardware，2003:25-32.

[9]Katz S，Tal A.Hierarchical mesh decomposition using fuzzy clustering and cuts[M]//ACM Transactions on Graphics（TOG）.ACM，2003:954-961.

[10]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.

[11]王文璽，肖世德，孟文，等.一種基于八叉樹空間剖分技術的光線跟蹤算法[J].計算機應用，2008，28（3）:656-658.

[12]鄒益勝，丁國富，許明恒，等.實時碰撞檢測算法綜述[J].計算機應用研究，2008（1）:8-12.

[13]王鵬，劉旭敏，關永.基于OBB層次包圍盒的碰撞檢測算法改進[J].計算機工程與設計，2009，30（13）:3196-3198.

[14]譚同德，吳強，趙紅領，等.OBB層次包圍盒構造方法的改進[J].計算機工程與應用，2008，44（5）:79-81.

[15]孫勁光，吳素紅.基于分類遍歷的碰撞檢測優化算法[J].計算機應用，2015，35（1）:194-197.

Collision detection algorithm based on space subdivision and classified traversal

LIU Zhao，LI Wei，ZHAO Lu-yang，SHAN Lian-hai
（Chinese Academy of Science Shanghai Institute of Microsystem and Information Technology，Shanghai 200050，China）

In order to solve the shortcoming of real-time and accuracy in collision detection，a novel collision detection algorithm based on space subdivision and classified traversal was proposed.In the space subdivision stage，the octree division was used to get rid of object pairs without intersecting.Then Create hybrid bounding box in the subspace and use classified traversal method to traverse them，aim to reduce the times of intersect tests efficiently.Experimental analyses show that this algorithm can reduce the time cost of collision detection，especially in complex situation.

collision detection；space subdivision；hybrid bounding box；classified traversal

TN919.82

A

1674－6236（2016）24-0151-03

2015-12-09 稿件編號：201512100

上海市青年科技啟明星計劃（14QB1404400）

劉 昭（1990—），男，河北廊坊人，碩士研究生。研究方向：計算機仿真、數字信號處理。