三維視景仿真的包圍盒碰撞檢測(cè)算法優(yōu)化

李成景，王 潔 ，肖強(qiáng)明，施冬健 ，2

（1.空軍工程大學(xué) 導(dǎo)彈學(xué)院，陜西 三原 710038；2.95196部隊(duì)，廣東 清遠(yuǎn) 513000）

0 引言

近年來，隨著三維視景仿真的發(fā)展，碰撞檢測(cè)問題成為一項(xiàng)重要課題，廣泛應(yīng)用于教育、國(guó)防、醫(yī)學(xué)等多個(gè)領(lǐng)域。精確的碰撞檢測(cè)對(duì)于如何準(zhǔn)確、快速地表現(xiàn)虛擬場(chǎng)景中物體的運(yùn)動(dòng)規(guī)律和相互關(guān)系，保證仿真環(huán)境的逼真度有著至關(guān)重要的作用。而虛擬環(huán)境的復(fù)雜性和實(shí)時(shí)性也要求碰撞檢測(cè)具有很高的效率。如何保證精確并短時(shí)間內(nèi)完成碰撞檢測(cè)實(shí)際上成為了實(shí)時(shí)仿真系統(tǒng)的瓶頸之一[1]。目前，國(guó)內(nèi)外研究人員已對(duì)虛擬環(huán)境下三維視景仿真的碰撞檢測(cè)進(jìn)行了深入的研究，并形成一些較為成熟的算法[2]。其中，層次包圍盒方法在碰撞檢測(cè)算法中被廣泛使用，一般分為全局搜索與局部檢測(cè)兩個(gè)階段。

層次包圍盒方法在全局搜索階段快速排除多數(shù)明顯不相交的對(duì)象對(duì)。在局部檢測(cè)階段，首先會(huì)遍歷對(duì)象對(duì)的層次包圍盒樹，逐一檢測(cè)節(jié)點(diǎn)之間是否相交，直到葉節(jié)點(diǎn)，以保證能夠精確地檢測(cè)葉節(jié)點(diǎn)中所包圍的多邊形面片是否相交。常用的包圍盒中，軸向包圍盒（Axis Aligned Bounding Boxes，AABB）的優(yōu)勢(shì)在于構(gòu)造簡(jiǎn)單，相交測(cè)試和包圍盒更新迅速，在實(shí)際中經(jīng)常被使用。目前常采用AABB的碰撞檢測(cè)庫(kù)主要有I-Collide[3]和Q-Col?lide[4]。I-Collide用于大量運(yùn)動(dòng)體間的碰撞檢測(cè)，Q-Col?lide是對(duì)其改進(jìn)，當(dāng)檢測(cè)的幾何模型復(fù)雜時(shí)，I-Collide會(huì)大大提高效率。此外，通用的碰撞檢測(cè)系統(tǒng)SOLID[5]涉及了模型變形，可適用于變形體間的碰撞檢測(cè)。I-Collide算法利用包圍盒排序法來優(yōu)化全局搜索過程，文獻(xiàn)[6]提出了對(duì)排序的改進(jìn)方法。SOLID算法的局部檢測(cè)過程采用AABB樹進(jìn)行精確的碰撞檢測(cè)。本文將利用時(shí)空相關(guān)性來改進(jìn)全局搜索過程，并從相交判斷算法的角度進(jìn)行優(yōu)化，減少執(zhí)行時(shí)間，提高算法效率。

1 碰撞檢測(cè)優(yōu)化算法

本文對(duì)全局搜索與局部檢測(cè)兩個(gè)階段分別進(jìn)行分析，在時(shí)空相關(guān)性，從相交測(cè)試算法兩方面對(duì)算法進(jìn)行優(yōu)化。

1.1 全局搜索過程

1.1.1 傳統(tǒng)包圍盒算法全局搜索過程

在虛擬現(xiàn)實(shí)仿真中，傳統(tǒng)包圍盒法[2]是把復(fù)雜的幾何對(duì)象包裹起來，在進(jìn)行碰撞檢測(cè)時(shí)，首先進(jìn)行包圍盒之間的相交測(cè)試，如果相交，則進(jìn)行幾何對(duì)象之間精確的碰撞檢測(cè)。設(shè)虛擬仿真場(chǎng)景中有N個(gè)運(yùn)動(dòng)對(duì)象和M個(gè)靜止對(duì)象，該算法實(shí)際上是對(duì)（N/2+NM）個(gè)對(duì)象對(duì)分別進(jìn)行檢測(cè)，復(fù)雜度為O(n2)，并且鑒于AABB的矩形包圍盒與包圍對(duì)象之間往往存在較大空隙，該算法搜索的結(jié)果并不是真正的相交，加大了局部檢測(cè)情況的復(fù)雜度。例如，兩個(gè)幾何對(duì)象的AABB包圍盒在XOY平面的投影如圖1所示，盡管包圍盒相交，但是兩個(gè)對(duì)象之間并沒有相交，使用基本的包圍盒算法時(shí)，將會(huì)繼續(xù)進(jìn)行精確的碰撞檢測(cè)。此時(shí)，由于誤判導(dǎo)致了無謂的計(jì)算，影響算法效率。

1.1.2 包圍盒樹的構(gòu)建

在從眾多對(duì)象中排除不可能相交的對(duì)象后，碰撞檢測(cè)算法會(huì)對(duì)可能相交的對(duì)象對(duì)進(jìn)行精確的碰撞檢測(cè)。這就需要為對(duì)象建立層次包圍盒，即包圍盒樹。一個(gè)幾何對(duì)象的包圍盒是包含該對(duì)象的一個(gè)簡(jiǎn)單的幾何體。對(duì)組成對(duì)象的基本元素（在本文研究環(huán)境下，即為三角形）的集合構(gòu)造包圍盒樹一般分為自頂向下和自底向上兩種方法。自頂向下的方法在碰撞檢測(cè)中較常使用，計(jì)算成熟，因此本文以此種劃分方法為基礎(chǔ)進(jìn)行分析。

該方法選擇根節(jié)點(diǎn)為全集S，對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行劃分以形成其子節(jié)點(diǎn)，直到到達(dá)葉節(jié)點(diǎn)（基本組成元素）。由于二叉樹的相對(duì)優(yōu)勢(shì)，在通常情況下，選擇的包圍盒樹都為二叉樹。該方法構(gòu)造包圍盒樹，實(shí)際上就是將全集的子集合SV以數(shù)目為2劃分子集，直到不可劃分的基本幾何元素為止。

1.1.3 改進(jìn)的全局搜索過程

為了改善復(fù)雜度O(n2)，就需要對(duì)場(chǎng)景中的對(duì)象進(jìn)行全局優(yōu)化搜索，排除當(dāng)前幀不可能發(fā)生碰撞的對(duì)象行，只對(duì)可能碰撞或上一幀已碰撞的情況進(jìn)行考察，提高檢測(cè)效率。針對(duì)此思路，本文在包圍盒樹的根節(jié)點(diǎn)處增加Cache字段來存放檢測(cè)結(jié)果（Cache字段包括Cache1和Cache2，分別存儲(chǔ)碰撞記錄和發(fā)生碰撞的幾何信息，Cache1以堆棧形式存儲(chǔ)固定幀數(shù)內(nèi)的碰撞信息，Cache2實(shí)時(shí)更新），在本幀的全局搜索階段，利用上一幀或前幾幀局部碰撞檢測(cè)的結(jié)果快速進(jìn)行碰撞搜索，避免了不必要的碰撞測(cè)試，優(yōu)化了全局搜索過程。

在實(shí)時(shí)繪制的虛擬環(huán)境中，幀與幀之間具有很強(qiáng)的關(guān)聯(lián)性，運(yùn)動(dòng)對(duì)象的位置和狀態(tài)不可能急劇變化，比如虛擬手的操作，這就意味著物體從一幀變化到另一幀時(shí)是相對(duì)靜止的。因此，當(dāng)兩個(gè)虛擬對(duì)象之間發(fā)生碰撞時(shí)，很可能下一幀中在這兩個(gè)對(duì)象之間發(fā)生新的碰撞。測(cè)試碰撞時(shí)可以首先測(cè)試上一幀發(fā)生碰撞的地方，同時(shí)把上一幀發(fā)生碰撞的相關(guān)信息緩存在其Cache中，供本次測(cè)試使用。改進(jìn)算法全局搜索的具體步驟為：

1）將場(chǎng)景中對(duì)象按序編號(hào)，進(jìn)行活動(dòng)對(duì)象的相交測(cè)試。若包圍盒相交，則把編號(hào)大的對(duì)象放入編號(hào)小的對(duì)象Cache1中。

2）檢查運(yùn)動(dòng)對(duì)象的Cache1字段，若為空，進(jìn)行下一對(duì)象的檢測(cè)。

3）檢測(cè)該對(duì)象Cache2中是否有相關(guān)碰撞的信息。若能檢測(cè)到對(duì)象間的碰撞信息，則直接構(gòu)造包圍盒樹，對(duì)上次發(fā)生碰撞的幾何元素及其兄弟子樹進(jìn)行檢測(cè)。否則，用傳統(tǒng)的層次包圍盒間的碰撞算法進(jìn)行檢測(cè)。若無碰撞，進(jìn)行下一對(duì)象檢測(cè)。

4）若檢測(cè)到碰撞，把碰撞信息覆蓋到Cache2中，并在Cache1中記錄當(dāng)前碰撞。返回步驟2），繼續(xù)循環(huán)。

隨著碰撞次數(shù)的增加，Cache中存放的碰撞信息將會(huì)保證能夠較早檢測(cè)到碰撞，因此減少了參與搜索的包圍盒數(shù)，節(jié)省了檢測(cè)的時(shí)間，并且如果步驟3）中檢測(cè)到精確的碰撞信息，則可省去對(duì)該對(duì)象的局部精確檢測(cè)過程。

1.2 局部檢測(cè)過程

1.2.1 傳統(tǒng)包圍盒局部檢測(cè)過程

包圍盒方法在從眾多復(fù)雜的對(duì)象中排除不可能相交的對(duì)象后，將構(gòu)造包圍盒樹，對(duì)可能相交的對(duì)象對(duì)進(jìn)行進(jìn)一步的碰撞檢測(cè)。傳統(tǒng)算法局部檢測(cè)過程的核心就是通過遍歷檢測(cè)對(duì)象的包圍盒樹，確定在當(dāng)前兩個(gè)對(duì)象是否發(fā)生碰撞。算法用一個(gè)對(duì)象的包圍盒樹的根節(jié)點(diǎn)遍歷另一個(gè)對(duì)象的包圍盒樹，若能到達(dá)葉節(jié)點(diǎn)，再用該葉節(jié)點(diǎn)遍歷第一個(gè)對(duì)象的包圍盒樹，如果同樣能到達(dá)葉節(jié)點(diǎn)，則繼續(xù)進(jìn)行基本元素的相交測(cè)試。如果兩個(gè)節(jié)點(diǎn)上的包圍盒不相交，就不需對(duì)其中的元素再做進(jìn)一步的相交測(cè)試。

1.2.2 基于垂線的相交測(cè)試算法

傳統(tǒng)包圍盒法葉節(jié)點(diǎn)的遍歷過程主要是檢測(cè)碰撞雙方的AABB樹的葉節(jié)點(diǎn)與葉節(jié)點(diǎn)、葉節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)。若是葉節(jié)點(diǎn)相交，則顯然增加了時(shí)間開銷。本文提出的基于垂線的相交測(cè)試算法即為三角形與內(nèi)部節(jié)點(diǎn)之間的快速測(cè)試算法。應(yīng)用基于垂線的相交測(cè)試算法，可直接進(jìn)行三角形與內(nèi)部節(jié)點(diǎn)間的相交測(cè)試，省去兩葉節(jié)點(diǎn)包圍盒求交的計(jì)算過程，提高檢測(cè)效率。

基于垂線的相交測(cè)試算法是將待檢測(cè)的對(duì)象坐標(biāo)平面進(jìn)行投影，通過碰撞標(biāo)志Flag（默認(rèn)為0）的值，判斷物體模型是否發(fā)生了碰撞：Flag=1，發(fā)生碰撞；Flag=0，未發(fā)生碰撞。分別記為Flag1（XOY平面），F(xiàn)lag2（XOZ平面），F(xiàn)lag3（YOZ平面），當(dāng)三者同時(shí)為1時(shí)，則Flag=1。設(shè)檢驗(yàn)對(duì)象為A和B，基本步驟為：

1）對(duì)象A的三角形遍歷B內(nèi)部節(jié)點(diǎn)包圍盒進(jìn)行相交測(cè)試，若不相交，F(xiàn)lag=0，退出循環(huán)。

2）將三角形與B包圍盒在XOY軸投影，在相交區(qū)域內(nèi)以等距作Y軸（或X軸）垂線，如圖2所示，計(jì)算等距線與物體投影線的交點(diǎn)個(gè)數(shù)。

3）若第n條垂線與兩物體的投影線只有一個(gè)交點(diǎn)，畫出兩條投影線的包圍矩形，減小區(qū)域。

4）若第n條垂線與物體A和物體B的投影線都有交點(diǎn)，分別記為PAi(x,yAi)和PBi(x,yBi)，其中i=1或2。判斷i的取值。（1）當(dāng)i=1時(shí)。若yA1

5）若有Flagi=0，F(xiàn)lag=0，結(jié)束算法。否則算法轉(zhuǎn)到尚未檢測(cè)的坐標(biāo)平面從步驟1）繼續(xù)判斷，若Flag1=Flag2=Flag3=1，F(xiàn)lag=1，結(jié)束算法。

1.2.3 優(yōu)化算法描述

節(jié)點(diǎn)之間的相交測(cè)試流程程序如下：

2 三維視景仿真結(jié)果及分析

實(shí)驗(yàn)使用通用SOLID軟件包，由Van den Bergen[5]研究并發(fā)布，采用AABB包圍盒法。將代碼修改為本文算法，在根節(jié)點(diǎn)增加Cache字段，并利用基于垂線的相交測(cè)試算法來簡(jiǎn)化計(jì)算。在PC平臺(tái)（CPU為Pentium43.0 GHz，內(nèi)存為1 Gbyte）構(gòu)造立方體在有限空間內(nèi)進(jìn)行隨機(jī)運(yùn)動(dòng)的場(chǎng)景來測(cè)試算法的有效性。其中一個(gè)場(chǎng)景如圖3所示，其三角面數(shù)16 461，紅色立方體對(duì)表示發(fā)生碰撞。將本文的改進(jìn)算法與SOLID軟件包提供的AABB包圍盒碰撞檢測(cè)算法進(jìn)行對(duì)比測(cè)試。

三角面片數(shù)與平均檢測(cè)時(shí)間變化曲線如圖4所示，可以看出，隨著三角面片數(shù)的增加，優(yōu)化算法的平均碰撞檢測(cè)時(shí)間較之傳統(tǒng)AABB算法碰撞檢測(cè)時(shí)間的上升緩慢，并且優(yōu)勢(shì)愈見明顯，并且由于利用了時(shí)空相關(guān)性原理，在多運(yùn)動(dòng)物體碰撞檢測(cè)條件下更具優(yōu)勢(shì)。實(shí)驗(yàn)結(jié)果體現(xiàn)了該算法的優(yōu)越性。

3 小結(jié)

本文針對(duì)層次包圍盒方法，利用時(shí)空關(guān)聯(lián)性，增加Cache字段存儲(chǔ)碰撞信息，優(yōu)化全局搜索階段，并利用快速相交測(cè)試減少局部檢測(cè)的時(shí)間，提高了檢測(cè)速度。在多面片多運(yùn)動(dòng)對(duì)象的復(fù)雜場(chǎng)景中，改進(jìn)效果更明顯。由仿真實(shí)驗(yàn)可知，該算法有效可行，是一種效率較高的三維視景仿真碰撞檢測(cè)算法。

[1]李芙玲，張瑾.碰撞檢測(cè)技術(shù)研究[J].華北科技學(xué)院學(xué)報(bào)，2004（2）：71-73.

[2]LI C F，F(xiàn)ENG Y T，OWEN D R J.SMB：collision detection based on temporal coherence[J].Computer Methods in Applied Mechanics and Engineering，2006，195：2252-2269.

[3]PONAMIG M，MANOCHA D，LIN M.Incremental algorithm for collision detection between polygonal models[J].IEEE Trans.Visualization and Computer Graphics，1997，3（1）：51-64.

[4]CHUNG K.An efficient collision detection algorithm for polytopes in virtual environments[EB/OL].[2011-02-21].http：//i.cs.hku.hk/GraphicsGroup/projects/collision/chung_thesis96.pdf.

[5]VAN DEN BERGEN G.Efficient collision detection of complex deformable models using AABB trees[EB/OL].[2011-02-21].http：//www.cs.cmu.edu/～djames/pbmis/etc/jgt98deform_AABB.pdf.

[6]董峰，王同洋.虛擬環(huán)境中的快速碰撞檢測(cè)算法[J].計(jì)算機(jī)工程與應(yīng)用，2003（8）：66-67.