宋濤，舒濤，梅朝，張衛(wèi)東

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安710051）

基于空間分解與混合包圍盒的碰撞檢測算法*

宋濤，舒濤，梅朝，張衛(wèi)東

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安710051）

針對如何提高碰撞檢測效率的問題，提出一種基于空間分解法和混合包圍盒的碰撞檢測算法。首先利用均勻剖分法確定相鄰對象，然后只對相鄰對象構(gòu)建混合層次包圍盒樹，最后引入任務(wù)樹的概念加速包圍盒樹的遍歷過程。在包圍盒碰撞檢測中，提出了一種頂層采用AABB，其他層采用OBB的混合層次包圍盒結(jié)構(gòu)。實驗結(jié)果表明，該算法有效提高了碰撞檢測的效率和實時性。

碰撞檢測，空間分解，包圍盒，任務(wù)樹

0 引言

碰撞檢測（Collision Detection，CD）也稱為干涉檢測或者接觸檢測，是系統(tǒng)仿真、虛擬現(xiàn)實技術(shù)等領(lǐng)域中的關(guān)鍵性問題。顧名思義，其任務(wù)就是根據(jù)現(xiàn)實中一對或多對對象不能在同一時刻占有相同區(qū)域的事實來檢測虛擬場景中的對象是否發(fā)生碰撞或穿透現(xiàn)象，這對于虛擬場景的真實感和實時性有著重大作用。空間分解法和層次包圍盒法是兩類經(jīng)典的碰撞檢測算法［1］?？臻g分解法是將空間劃分為不同的區(qū)域，找到占據(jù)同一區(qū)域的相鄰對象，只對相鄰對象進(jìn)行檢測，常用的空間分解方法有樹、均勻網(wǎng)格和空間排序等；層次包圍盒的思想是用體積略大而幾何特征簡單的包圍盒來代替復(fù)雜的幾何對象進(jìn)行碰撞檢測，只需對包圍盒重疊的對象進(jìn)行進(jìn)一步碰撞檢測，常用的包圍盒有Spheres，AABB，OBB和k-DOPs等［2］。

隨著人們的認(rèn)知水平對計算機虛擬世界復(fù)雜度、真實感要求的提高和虛擬場景中模型的數(shù)量和復(fù)雜度急劇增大，單純基于空間分解或?qū)哟伟鼑械呐鲎矙z測法的精確性和實時性已經(jīng)難以滿足需求，本文提出了一種將空間分解和層次包圍盒相結(jié)合的算法，首先利用空間均勻剖分法確定相鄰對象，然后利用層次包圍盒法對相鄰對象進(jìn)行精確碰撞檢測，在層次包圍盒的構(gòu)造上選取上層為AABB，下層為OBB的混合包圍盒結(jié)構(gòu)，在保證算法精度的前提下，有效減少了構(gòu)造層次包圍盒樹的數(shù)量和深度以及包圍盒相交測試的次數(shù)，提高了檢測效率。

1 相關(guān)理論

1.1空間分解

空間分解法是將空間剖分為鄰接區(qū)域并將場景對象與其交疊的全部區(qū)域關(guān)聯(lián)，僅對位于同一區(qū)域的對象執(zhí)行組合測試，可以盡快排除明顯不相交的對象，大大降低了組合測試的數(shù)量。均勻網(wǎng)格是一種常用的空間分割方法，將整個空間劃分為大小均勻的網(wǎng)格，每個對象對應(yīng)一個或多個網(wǎng)格單元，只有處于同一網(wǎng)格單元中的對象才可能相交，因而只需對這些空間單元進(jìn)行進(jìn)一步的精確碰撞檢測，本文采用這種空間分解方法。

1.2AABB

軸向包圍盒（Axis-Aligned Bounding Box，AABB）被定義為包含對象且邊平行于坐標(biāo)軸的最小正六面體［3］。對于給定的對象，僅需得到對象基本幾何元素各頂點的x坐標(biāo)、y坐標(biāo)以及z坐標(biāo)的最大值和最小值就可構(gòu)造AABB。包含的區(qū)域為：

AABB最大的特點是相交測試簡單快速：能夠直接將三維求交降為一維求交問題，只需做6次比較運算。只有當(dāng)兩個AABB在3個坐標(biāo)軸上的投影區(qū)間均相交時AABB才相交。

1.3OBB

方向包圍盒（Oriented Bounding Box，OBB）定義為包含該對象且相對于坐標(biāo)軸方向任意的最小長方體［4］。其最大的特點是包圍盒方向的任意性，可以根據(jù)對象的形狀特點盡可能緊密地包圍對象，但這也同時增加了其相交測試的復(fù)雜性。

采用“分離軸測試”的方法檢測兩個OBB之間是否相交，只需得出兩個OBB是否存在一條分離軸即可。其相交測試需要存儲兩個OBB的6個軸向和3個軸向與另3個軸向叉乘得到的9個向量總共15個軸。依次在這些軸上，檢查兩個OBB的投影區(qū)間是否相交。判斷兩個OBB相交即判斷它們在15個方向上的投影區(qū)間是否均相交，最多只要做15次比較運算。構(gòu)造OBB的關(guān)鍵問題是找到最佳方向并確定該方向上包圍對象的包圍盒的最小尺寸。

1.4任務(wù)樹

碰撞檢測的核心就是遍歷兩個對象的層次包圍盒樹，本文引入任務(wù)樹的概念改進(jìn)傳統(tǒng)的遍歷方法，加速遍歷過程。

這里把遍歷兩棵層次包圍盒樹定義為一棵任務(wù)樹，任務(wù)為兩對象包圍盒樹節(jié)點間的碰撞檢測，從而只需對該任務(wù)樹進(jìn)行單重遍歷即可完成對兩棵包圍盒樹同步深度優(yōu)先遍歷［5］。子任務(wù)樹之間是或的關(guān)系，只要其中一個子任務(wù)樹檢測出相交，則兩對象一定發(fā)生碰撞，遍歷完整棵任務(wù)樹都沒有相交，則兩對象沒有碰撞。因為各子任務(wù)是相互獨立的，所以各層次上的子任務(wù)可以并行處理，從而加快了處理速度。假設(shè)對對象A、B進(jìn)行碰撞檢測，其任務(wù)樹如圖1所示，a和b是兩棵待檢測的包圍盒二叉樹的根節(jié)點，a→left與a→right分別表示節(jié)點a的左右兩個子節(jié)點。

圖1 A，B兩個對象的碰撞檢測任務(wù)樹

2 算法實現(xiàn)

2.1算法概述

算法主要包括空間分解和混合層次包圍盒碰撞檢測兩個階段。首先，通過均勻剖分法將空間劃分為均勻網(wǎng)格，找到占據(jù)同一網(wǎng)格的相鄰對象。然后，對相鄰對象構(gòu)造AABB-OBB混合層次包圍盒樹，利用任務(wù)樹的方法遍歷這些包圍盒樹，得到可能相交的基本幾何元素對。最后，對這些基本幾何元素對進(jìn)行幾何間的相交測試，最終獲得詳細(xì)的碰撞信息，算法流程如圖2所示。

圖2 算法流程圖

2.2空間分解階段

利用均勻剖分法將空間劃分為大小為a的正方體空間單元，并進(jìn)行編號。假設(shè)場景空間中有n個對象，分別標(biāo)記為O1，O2，…，On，求出每個對象所在的空間單元，然后在對象的數(shù)據(jù)結(jié)構(gòu)中增加一個list鏈表，用于存儲與該對象相鄰的對象標(biāo)識，在list中僅記錄對象標(biāo)識比自身標(biāo)識大的相鄰對象，從而防止重復(fù)檢測。

空間分解的目的是為了快速排除距離較遠(yuǎn)的對象，確定相鄰對象，從而大大減少層次包圍盒檢測階段需要構(gòu)造包圍盒樹的數(shù)量，在復(fù)雜多對象的虛擬場景中效果顯著。如果直接將對象的基本幾何元素映射到空間單元中，計算較為復(fù)雜，本文先求出整個對象的AABB，近似表示對象所在的空間單元。取3個整數(shù)（i，j，k）依次代表x，y，z軸上的標(biāo)識來唯一的標(biāo)識一個空間單元。

假設(shè)對象的AABB包圍盒的主對角線上兩個頂點分別是p1（x1，y1，z1），p2（x2，y2，z2）。p1所在的空間單元（i1，j1，k1）可由式（2）得到：

同理可得p2所在的空間單元（i2，j2，k2）。那么該對象所占的空間單元可以近似表示為（i1，j1，k1）和（i2，j2，k2）之間所有的連續(xù)空間單元。占據(jù)同一單元的稱為相鄰對象。

2.3碰撞檢測階段

采用自頂向下的方法對相鄰對象構(gòu)造AABB-OBB混合層次包圍盒二叉樹，包圍盒樹設(shè)計為兩層結(jié)構(gòu)，上層根節(jié)點采用AABB，下層采用OBB。因為包圍盒樹的遍歷每次都是從頂層開始，所以上層采用結(jié)構(gòu)簡單的AABB可以大大減少計算量，并能迅速排除相鄰單元明顯不相交的對象。下層采用緊密性好的OBB可以及時進(jìn)入精確的碰撞檢測階段，避免過多的冗余計算，并能保證檢測精度。由于AABB可以看作特殊方向的OBB，則此設(shè)計結(jié)構(gòu)實際上只需進(jìn)行頂層之間的AABB-AABB相交測試和其他層的OBB-OBB兩種相交測試，解決了混合層次包圍樹相交測試復(fù)雜的問題。AABB-OBB混合層次包圍盒二叉樹結(jié)構(gòu)如圖3所示。

圖3 AABB-OBB結(jié)構(gòu)圖

遍歷對象的list鏈表，檢測各對象與其list表中的相鄰對象是否發(fā)生碰撞，采用任務(wù)樹的方法遍歷對象包圍盒樹之間的相交情況，具體步驟如下：

步驟1：對兩個對象的根節(jié)點a和b進(jìn)行碰撞檢測。檢測兩個根節(jié)點的AABB是否相交，若不相交，則直接判定兩對象之間未發(fā)生碰撞，否則進(jìn)入步驟2。

步驟2：若a和b均為非葉子節(jié)點，同時并行進(jìn)行a→left與b→left，a→left與b→right，a→right與b→left，a→right與b→right相交測試的4個子任務(wù)，如果都不相交，則判定兩對象之間未發(fā)生碰撞，否則進(jìn)入步驟3；

若a為葉子節(jié)點，b為非葉子節(jié)點，并行進(jìn)行a與b→left和a與b→right相交測試兩個子任務(wù)，如果都不相交，則判定兩對象之間未發(fā)生碰撞，否則進(jìn)入步驟3；

若b為葉子節(jié)點，a為非葉子節(jié)點，并行進(jìn)行a→left與b和a→right與b相交測試兩個子任務(wù)，如果都不相交，則判定兩對象之間未發(fā)生碰撞，否則進(jìn)入步驟3；

若a和b均為葉子節(jié)點，則進(jìn)行基本幾何元素之間的精確碰撞檢測，如果相交，則判定兩對象之間發(fā)生碰撞，返回碰撞詳細(xì)信息，否則可最終判定兩對象不相交。

步驟3：把相交的節(jié)點重新記為a和b，返回步驟2。

3 實驗結(jié)果與分析

實驗在CPU I5-4590 3.3 GHz、內(nèi)存4 G、獨立顯卡1G的PC機上應(yīng)用VC 6.0平臺實現(xiàn)。每組實驗在相同的場景，相同的運動軌跡下，分別利用基于OBB的碰撞檢測算法RAPID［6］，基于k-DOPs的Quick CD［7］算法，Sphere-OBB［8］混合包圍盒算法以及本文算法進(jìn)行碰撞檢測，對比不同算法在得到相同正確的檢測結(jié)果（三角形重疊數(shù)目相同）下的碰撞檢測時間。提高場景的復(fù)雜度和包含對象的個數(shù)，重復(fù)上述實驗，實驗結(jié)果如表1所示，三角形重疊數(shù)隨著場景復(fù)雜度的增加而增加，總共10組實驗，算法效率對比如圖4所示。

圖4 算法碰撞檢測時間對比圖

由圖4可以直觀地看出，在三角形重疊數(shù)目相同時，本文提出的算法相比RAPID、Quick CD、Sphere-OBB算法，縮短了碰撞檢測的時間，提高了碰撞檢測的實時性，并且隨著空間復(fù)雜程度的增加優(yōu)勢更加明顯。這是由于本文提出的算法在復(fù)雜多對象的場景中結(jié)合空間分解法盡早排除了相距較遠(yuǎn)的對象，大大減少了需要構(gòu)造的混合層次包圍盒樹的數(shù)量，從而減少算法的計算量。

表1 碰撞檢測時間對比

4 結(jié)論

本文提出一種基于空間分解與混合層次包圍盒相結(jié)合的碰撞檢測算法。首先利用均勻剖分法排除了場景中相距較遠(yuǎn)的對象，找到相鄰對象，然后對相鄰對象進(jìn)行混合層次包圍盒碰撞檢測。在混合層次包圍盒樹的構(gòu)造中采用一種上層AABB，下層OBB的結(jié)構(gòu)，充分利用了AABB和OBB的優(yōu)點。在包圍盒樹的遍歷中引入任務(wù)樹的概念，提高了遍歷的速度。實驗結(jié)果表明，該算法相比其他傳統(tǒng)算法提高了碰撞檢測的速度和實時性。但是任一碰撞檢測算法都不可能適用于所有場景，在包含對象較少的場景中，本文算法的優(yōu)勢并不明顯，更適用于包含對象較多、較為復(fù)雜的虛擬場景。

［1］LIN M，GOTTSCHALK S.Collision detection between geometric models：a survey［M］.Birmingham：Euro Graphics Association，1998.

［2］鄧乾旺，高禮坤，起重機吊裝仿真中事實碰撞檢測的研究與應(yīng)用［J］.計算機仿真，2013，30（12）：214-218.

［3］李煜一，李夢怡，王俊彥.碰撞檢測中各種包圍盒比較研究［J］.信息通信，2014，134（2）：20-21.

［4］史旭升，喬立紅，朱作為.基于改進(jìn)OBB包圍盒的碰撞檢測算法［J］.湖南大學(xué)學(xué)報，2014，41（5）：26-31

［5］范昭煒，萬華根，高曙明.基于并行的快速碰撞檢測算法［J］.系統(tǒng)仿真學(xué)報，2000，12（5）：548-552.

［6］GOTTSCHALK S，LIN M C，MANOCHA D.OBB Tree：A hierarchical structure for rapid interference detection［C］//Proc of SIGGRAPH’96，1996：171-180.

［7］KLOSOWSKI J，HELA M，MITCHELL J，et al.Efficient collisiondetectionusingboundingvolumehierarchiesof k-DOPs［J］.IEEE Transactions on Visualization and Computer Graphics，1998，4（1）：21-37.

［8］王立文，劉壁瑤.基于OBB的混合包圍盒碰撞檢測算法研究［C］∥第六屆全國仿真器學(xué)術(shù)會議論文集.北京：中國系統(tǒng)仿真學(xué)會，2007.

A Collision Detection Algorithm Based on Spatial Partitioning and Hybrid Bounding Box

SONG Tao，SHU Tao，MEI Zhao，ZHANG Wei-dong
（Air Defense and Antimissile Institute，Air Force Engineering University，Xi’an 710051，China）

Aiming at the problem of how to improve the efficiency of collision detection，the paper comes up with a collision detection algorithm based on spatial partitioning and hybrid bounding box. Firstly，the adjacent objects with the method of uniform subdivision is determined.Then，hybrid bounding box trees is only built on them.At last，the task tree is introduced to accelerate the process of traveling bounding boxes.In the bounding box collision detection，this paper puts forward a kind of top using AABB，other layer using OBB hybrid bounding box structure.The experimental results show that the proposed algorithm effectively improves the efficiency and real-time performance of collision detection.

collision detection，spatial partitioning，bounding boxes，task trees

TP391

A

1002-0640（2016）11-0094-04

2015-09-25

2015-11-07

國家自然科學(xué)基金資助項目（61273156）

宋濤（1990-），男，山東棗莊人，在讀碩士。研究方向：武器裝備虛擬訓(xùn)練。