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

劉 昭，李 偉，趙魯陽，單聯(lián)海

（中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 上海200050）

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

劉 昭，李 偉，趙魯陽，單聯(lián)海

（中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 上海200050）

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

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

隨著計(jì)算機(jī)仿真技術(shù)的發(fā)展，以三維場景為基礎(chǔ)的虛擬現(xiàn)實(shí)技術(shù)和對自然環(huán)境的渲染技術(shù)已成為重要研究方向，可廣泛應(yīng)用于城市規(guī)劃、軍事模擬、突發(fā)事件模擬等領(lǐng)域[1-2]。隨著三維模型復(fù)雜性的增加和人們對于場景真實(shí)感要求的提高，碰撞檢測的實(shí)時(shí)性與高效性成為當(dāng)前研究熱點(diǎn)。

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

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

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

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

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

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

2）對占用同一子空間的物體進(jìn)行碰撞檢測時(shí)，構(gòu)造Sphere-OBB混合層次包圍盒；

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

1 算法描述

1.1 空間剖分

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

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

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

1.2 混合層次包圍盒

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

表1 幾種包圍盒特性比較

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

在上述公式中，可以通過構(gòu)造更緊湊的包圍盒來降低NV和NP的值，通過實(shí)現(xiàn)快速檢測降低CV和CP的值。但是這兩組值之間存在一個(gè)矛盾關(guān)系，當(dāng)包圍盒更加緊湊時(shí)，相交測試代價(jià)會(huì)越大，但是會(huì)降低相交測試的數(shù)量，所以需要在兩者之間實(shí)現(xiàn)一個(gè)平衡。

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

1.3 層次包圍盒的遍歷

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

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

其中BAi表示樹A中節(jié)點(diǎn)i的平衡因子；BBi表示樹B中與A中節(jié)點(diǎn)i相同位置節(jié)點(diǎn)的平衡因子；Di表示節(jié)點(diǎn)i的平衡因子差值。當(dāng)Di都不大于1時(shí)表示兩個(gè)樹結(jié)構(gòu)相似，否則就不相似。

圖1 a、b、c三棵樹結(jié)構(gòu)

圖2 平衡因子差樹

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

對于改進(jìn)單一下降深度優(yōu)先遍歷過程，首先選擇額外細(xì)節(jié)較多的樹a進(jìn)行遍歷，當(dāng)下降到樹a的結(jié)點(diǎn)的平衡因子差值大于1時(shí)，轉(zhuǎn)而對樹b進(jìn)行遍歷，如果樹b中出現(xiàn)平衡因子差值大于1時(shí)，再轉(zhuǎn)回對樹a進(jìn)行遍歷，如此循環(huán)，直到完成碰撞檢測。

2 實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)程序運(yùn)行的硬件環(huán)境是Windows 7系統(tǒng)，CPU 2.4 GHz的PC機(jī)，軟件環(huán)境是Visual Studio 2010和OpenGL開發(fā)。實(shí)驗(yàn)場景分為兩種，一種是模擬場景，另一個(gè)是軟件應(yīng)用場景。

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

圖3 物體數(shù)量與碰撞檢測時(shí)間關(guān)系

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

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

圖4 消防滅火場景

在上述3種消防救援場景中，分別對3個(gè)場景下的幀數(shù)變化進(jìn)行統(tǒng)計(jì)，以10秒為一個(gè)時(shí)間間隔，統(tǒng)計(jì)10秒幀數(shù)的平均值作為當(dāng)前幀數(shù)，統(tǒng)計(jì)結(jié)果如圖5所示。

圖5 復(fù)雜場景下幀數(shù)隨時(shí)間變化情況

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

3 結(jié) 論

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

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

[1]趙沁平.虛擬現(xiàn)實(shí)綜述[J].中國科學(xué)，2009（39）:2-46.

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

[3]卞鋒，江漫清，桑永英.虛擬現(xiàn)實(shí)及其應(yīng)用進(jìn)展[J].計(jì)算機(jī)仿真，2007，24（6）:1-4.

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

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

[6]姜曉路，劉淵.一種新的基于混合層次包圍盒的碰撞檢測算法[J].計(jì)算機(jī)工程與應(yīng)用，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]王文璽，肖世德，孟文，等.一種基于八叉樹空間剖分技術(shù)的光線跟蹤算法[J].計(jì)算機(jī)應(yīng)用，2008，28（3）:656-658.

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

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

[14]譚同德，吳強(qiáng)，趙紅領(lǐng)，等.OBB層次包圍盒構(gòu)造方法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（5）:79-81.

[15]孫勁光，吳素紅.基于分類遍歷的碰撞檢測優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，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

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

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