孫勁光　吳素紅　周積林

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

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

?

基于形狀分類的包圍盒碰撞檢測優(yōu)化算法

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

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

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

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

關(guān)鍵詞碰撞檢測層次包圍盒形狀分類區(qū)域劃分時(shí)空相關(guān)性

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引言

碰撞檢測是一項(xiàng)用來檢測虛擬環(huán)境中的物體在某一時(shí)間點(diǎn)上是否占據(jù)了同一空間的技術(shù)，它可以應(yīng)用在計(jì)算機(jī)動畫、計(jì)算機(jī)輔助設(shè)計(jì)、虛擬現(xiàn)實(shí)等各個領(lǐng)域。

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

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

現(xiàn)有的算法都是對每一個物體采用統(tǒng)一的包圍盒結(jié)構(gòu)，而現(xiàn)實(shí)中的物體大多都形狀各異，同一種包圍盒結(jié)構(gòu)很難適應(yīng)所有的物體。所以本文考慮每個物體形狀上的差異，提出一種基于形狀分類的包圍盒碰撞檢測算法。考慮到包圍盒的緊密性，將形狀近似球體的一類，采用球包圍盒，而形狀與球體相差大的一類，采用OBB包圍盒。此外，加入?yún)^(qū)域劃分策略和時(shí)間相關(guān)性理論，對碰撞檢測過程進(jìn)行優(yōu)化，從而整體提高了碰撞檢測的效率。

1算法的基本思想

算法分三個階段：區(qū)域劃分階段、物體分類階段和遍歷優(yōu)化階段。

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

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

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

2基于形狀分類的包圍盒碰撞檢測優(yōu)化算法

2.1物體在形狀上的分類

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

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

(1)

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

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

根據(jù)物體的形狀將物體分類的過程如下：

(1) 根據(jù)每個物體的點(diǎn)集計(jì)算出最小包圍球。

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

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

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

2.2包圍盒間的相交測試

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

2.2.1Sphere-Sphere

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

|o1o2|2>(r1+r2)2

(2)

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

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

2.2.2OBB-OBB

1) 接觸情況的預(yù)判斷

在檢測兩個OBB包圍盒是否相交之前，先對它們的接觸情況進(jìn)行預(yù)測[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的距離。通過下面不等式預(yù)測兩個OBB間的相交情況。

(3)

D

(4)

D>Oi.max+Oj.max

(5)

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

2) 相交測試

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

圖1　分離軸理論

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

2.2.3Sphere-OBB

類似于OBB-OBB間的相交測試，判斷Sphere-OBB是否相交的依據(jù)同樣是不等式|T·L|>r1+r2。假設(shè)有包圍球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)成立，則兩個包圍盒不相交，否則繼續(xù)計(jì)算它們在其他2個分離軸上的投影是否重疊，若三個軸上的投影都不滿足該不等式，那么判斷這兩個包圍盒相交。

2.3算法的優(yōu)化

2.3.1區(qū)域劃分策略

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

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

現(xiàn)空間中有n個物體，它們的標(biāo)識依次為O1，O2，…，On，為每一個物體的數(shù)據(jù)結(jié)構(gòu)中都添加一個相鄰鏈表AdList，用來存儲該物體的相鄰物體。算法的具體過程如下：

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

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

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

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

2.3.2時(shí)間相關(guān)性

在虛擬環(huán)境中物體雖然都在隨機(jī)運(yùn)動，但是它們的運(yùn)動卻是連續(xù)的，而不是每一個時(shí)刻都在瞬移。那么在相鄰時(shí)間采樣點(diǎn)上，物體的位置和狀態(tài)往往變化很小。也就是說，當(dāng)前時(shí)間點(diǎn)兩物體的相交狀態(tài)與上一時(shí)間采樣點(diǎn)是關(guān)聯(lián)的。如果兩個物體碰撞了，那么在下個時(shí)間采樣點(diǎn)物體也很有可能是碰撞的，并且碰撞的位置是相近的；如果兩個物體沒碰撞，那么在下個時(shí)間采樣點(diǎn)也很可能不發(fā)生碰撞[12]，這就是時(shí)間相關(guān)性理論。

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

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

圖2　t時(shí)刻物體的碰撞情況以及對應(yīng)的關(guān)鍵點(diǎn)表

圖3　t+1時(shí)刻物體的碰撞情況以及對應(yīng)的關(guān)鍵點(diǎn)表

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

2.4算法的偽程序

CollisionDetection(Array)

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

輸入：Array

輸出：Result

//對物體進(jìn)行分類

For i=0 To Array.length

{

If(Oi的偏球率<=0.143)

//1/7約等于0.143

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

CreateSphere(Oi);

}

Else

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

CreateOBB(Oi);

}

}

//區(qū)域劃分并執(zhí)行包圍盒碰撞檢測算法

For i=0 To Array.length

{ For j=0 To Array.length

{//構(gòu)造每個物體的相鄰鏈表AdList

CreateAdList(Oj)

}

If(Oi.AdList不為空)

{//創(chuàng)建線程

CreateThread()

For k=0 To Oi.Adlist.length

{ //并行執(zhí)行包圍盒遍歷優(yōu)化算法

Traverse(Oi,Ok,result)

//更新兩物體的關(guān)鍵點(diǎn)表List

UpdateList(Oi,Ok)

}

}

}

3實(shí)驗(yàn)

本文算法在Win 7系統(tǒng)下，在具有CPU 2.2 GHz，四核處理器的PC機(jī)上應(yīng)用VS2010和OpenGL實(shí)現(xiàn)。實(shí)驗(yàn)場景中，有40個形狀各異的物體進(jìn)行隨機(jī)運(yùn)動，三角面片的個數(shù)多達(dá)9000個，如圖4所示。

圖4　碰撞場景

為了證實(shí)本文算法的優(yōu)越性，我們做了兩個實(shí)驗(yàn)。

實(shí)驗(yàn)一偏球閾值對本算法的影響

通過逐步變化偏球閾值的大小來統(tǒng)計(jì)本文算法運(yùn)行1000步的平均碰撞檢測時(shí)間(ms)。實(shí)驗(yàn)結(jié)果如圖5所示。

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

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

實(shí)驗(yàn)二各算法與本文算法的比較

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

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

從表1可以看出，采用形狀分類的包圍盒方法的碰撞檢測算法的平均碰撞檢測時(shí)間比采用統(tǒng)一包圍盒的碰撞檢測時(shí)間要小，并且?guī)l也稍有提高。在加入時(shí)間相關(guān)性和區(qū)域劃分策略后，算法得到了進(jìn)一步的優(yōu)化，平均碰撞檢測時(shí)間縮小到37.206 ms，場景繪制速度達(dá)到了38.42 frame/s。

4結(jié)語

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

參考文獻(xiàn)

[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] 郭凌云,鄭延斌,劉晶晶.基于時(shí)空相關(guān)性的快速碰撞檢測算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(5):174-176.

[9] 張應(yīng)中,范超,羅曉芳.凸多面體連續(xù)碰撞檢測的運(yùn)動軌跡分離軸算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,25(1):7-14.

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

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

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

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

[14] 水泳.虛擬現(xiàn)在中連續(xù)碰撞檢測算法研究[D].合肥:中國科技大學(xué),2013.

中圖分類號TP391

文獻(xiàn)標(biāo)識碼A

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

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