基于混合層次包圍盒的快速碰撞檢測(cè)算法

林 菲,鄒 玲,張 聰

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院,浙江 杭州 310000)

1 引言

在虛擬現(xiàn)實(shí)環(huán)境中,碰撞檢測(cè)用來確定虛擬場(chǎng)景中的物體間是否發(fā)生接觸或穿透,增強(qiáng)人與虛擬環(huán)境之間的視覺與力覺交互體驗(yàn),從而提高虛擬環(huán)境的真實(shí)感和沉浸感[1]。因此,碰撞檢測(cè)是直接影響用戶體驗(yàn)的關(guān)鍵指標(biāo),也是虛擬現(xiàn)實(shí)領(lǐng)域研究的關(guān)鍵問題之一。隨著虛擬環(huán)境中模型規(guī)模和復(fù)雜度的升高,對(duì)碰撞檢測(cè)算法提出了更高的要求[2,3]。當(dāng)前針對(duì)碰撞檢測(cè)的國(guó)內(nèi)外研究主要包括基于圖像的碰撞檢測(cè)算法和基于圖形的碰撞檢測(cè)算法,前者需要借助圖形硬件設(shè)備,后者從策略角度和算法角度提高碰撞檢測(cè)適應(yīng)性。在基于圖形的碰撞檢測(cè)算法中,層次包圍盒算法具有存儲(chǔ)量小、靈活性高的優(yōu)點(diǎn),從而被廣泛應(yīng)用[4]。

本文主要研究基于層次包圍盒的碰撞檢測(cè)算法。該類算法的主要思想是通過體積稍大且特性簡(jiǎn)單的幾何體(稱為包圍盒)來近似地代替復(fù)雜的幾何物體,進(jìn)而構(gòu)造層次包圍盒樹來提升碰撞檢測(cè)算法的速度。常見的包圍盒類型有軸對(duì)齊包圍盒(Axis-aligned Bounding Box)[5]、包圍球(Sphere)[6]、方向包圍盒(Orient Bounding Box)[7]以及離散方向多面體(K-Dop)[8]等。表1為這四種常見包圍盒的性能比較,從中可以看出,緊密程度和相交測(cè)試難度作為包圍盒技術(shù)兩個(gè)重要指標(biāo),二者始終相互制約。為了提高包圍盒緊密性,研究者們提出使用三角面片面積加權(quán)的方法提高OBB包圍盒緊密性[9],但其在一定程度上延長(zhǎng)了包圍盒構(gòu)造時(shí)間。另一方面,為了減少相交檢測(cè)難度和次數(shù),研究者們提出了各種基于混合層次包圍盒的碰撞檢測(cè)算法來提升碰撞檢測(cè)的效率,如OBB-Sphere[10]以及AABB-OBB[11]。盡管這些算法都進(jìn)行了一定程度上的改進(jìn)和提高,但是以犧牲其它方面的性能為代價(jià),缺乏對(duì)碰撞檢測(cè)整體性能的均衡考量。

表1 常見四種包圍盒的性能比較

為了進(jìn)一步提高碰撞檢測(cè)算法整體效率,本文提出了一種基于Sphere-AABB-OBB混合層次包圍盒的快速碰撞檢測(cè)算法。該算法在構(gòu)造OBB包圍盒時(shí),首先通過預(yù)處理頂點(diǎn)提取凸體后,再利用基于三角面積加權(quán)的方法計(jì)算OBB包圍盒,來解決包圍盒方向傾斜問題,從而提高包圍盒緊密性并減少包圍盒構(gòu)造時(shí)間;同時(shí),本文綜合考慮了Shpere、AABB包圍盒相交檢測(cè)的簡(jiǎn)單性和OBB包圍盒緊密性的特點(diǎn),建立了一種新的混合層次包圍盒結(jié)構(gòu)——Sphere-AABB-OBB混合包圍盒層次樹,以減少相交檢測(cè)的次數(shù)和時(shí)間。

2 混合包圍盒構(gòu)造方法

混合包圍盒算法通常是在外層使用構(gòu)造簡(jiǎn)單的包圍盒,而在內(nèi)層使用緊密性良好的包圍盒,以加速排除不相交的物體。本文提出了一種新的Sphere-AABB-OBB混合層次包圍盒結(jié)構(gòu),自頂向下構(gòu)建層次樹,樹的每個(gè)節(jié)點(diǎn)均包含3種包圍盒,從內(nèi)到外依次構(gòu)造OBB包圍盒、AABB包圍盒以及Sphere包圍盒。

2.1 OBB包圍盒優(yōu)化

OBB包圍盒是指在坐標(biāo)軸的任意方向上包圍物體模型的最小長(zhǎng)方體,其結(jié)構(gòu)緊湊、檢測(cè)精度高于Sphere和AABB包圍盒。OBB包圍盒一般用一個(gè)中心點(diǎn)、一個(gè)旋轉(zhuǎn)矩陣以及 3 個(gè)方向上的半徑來表示,其常用的計(jì)算方法是一種基于主成分分析法(PCA)計(jì)算最小 OBB 的方法,這種方法主要通過計(jì)算模型所有三角形頂點(diǎn)的均值和協(xié)方差矩陣 C 來確定OBB 的中心點(diǎn)和方向,然后根據(jù)模型中所有三角形頂點(diǎn)在 3 條軸上的極值即可得到 OBB 的 3 條半徑。

本文考慮到只有物體模型凸包上的頂點(diǎn)才會(huì)影響其OBB包圍盒,可以忽略冗余頂點(diǎn),因此提出使用Quickhull算法[12]提取物體凸包來近似代替物體模型,以減少參與OBB包圍盒構(gòu)造的頂點(diǎn)數(shù)量,從而降低OBB包圍盒構(gòu)造的時(shí)間。為了避免OBB包圍盒向頂點(diǎn)密集方向傾斜,本文采用了一種基于三角面積加權(quán)的OBB包圍盒中心點(diǎn)計(jì)算方法,將凸體的質(zhì)心作為OBB包圍盒中心點(diǎn)。

假設(shè)物體模型為S,物體模型的凸體,模型凸體中有n個(gè)三角形(qk,pk,rk),其中1≤k≤n,則協(xié)方差矩陣為

-mH,imH,j

(1)

(2)

(3)

2.2 AABB包圍盒計(jì)算

AABB包圍盒存在多種常見數(shù)據(jù)結(jié)構(gòu),其中中心點(diǎn)-邊長(zhǎng)這種數(shù)據(jù)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。在本文算法中,OBB包圍盒和AABB包圍盒的中心點(diǎn)是重合的,采用這種結(jié)構(gòu)類型,只需根據(jù)已求出的OBB包圍盒計(jì)算外層AABB包圍盒在x、y、z軸上的邊長(zhǎng)。

假設(shè)OBB包圍盒的中心點(diǎn)為mH,其三個(gè)基準(zhǔn)方向分別為d1、d2、d3,其基準(zhǔn)方向的半徑分別為r1、r2、r3,可得OBB包圍盒的定義區(qū)域:

R={mH+ad1r1+bd2r2+ad3r3|a,b,c∈(-1,1)}

(4)

之后,分別計(jì)算R中在x、y、z軸上的最大最小值,將最大最小值相減即可得到AABB包圍盒在x、y、z軸上的邊長(zhǎng)。

2.3 Sphere包圍盒計(jì)算

由于OBB是采用中心點(diǎn)-邊長(zhǎng)的數(shù)據(jù)結(jié)構(gòu),因此要計(jì)算它們外層的Sphere包圍盒,以O(shè)BB包圍盒中心作為球心,以O(shè)BB包圍盒頂點(diǎn)中最遠(yuǎn)頂點(diǎn)與球心的距離為Sphere包圍盒的半徑。

3 混合包圍盒相交檢測(cè)方法

OBB包圍盒之間的相交檢測(cè)較為復(fù)雜,而Sphere包圍盒和AABB包圍盒的相交檢測(cè)更為簡(jiǎn)單。在本文算法中,首先對(duì)物體混合包圍盒外層的Sphere包圍盒進(jìn)行相交檢測(cè),若Sphere包圍盒之間相交,則繼續(xù)對(duì)AABB包圍盒之間進(jìn)行相交檢測(cè),若AABB包圍盒相交,則繼續(xù)對(duì)OBB包圍盒之間進(jìn)行相交檢測(cè)。

3.1 Sphere包圍盒相交檢測(cè)

假設(shè)兩個(gè)Sphere包圍盒的球心和半徑分別為:So、R1和:To、R2,如果圓心距的長(zhǎng)度大于兩個(gè)Sphere包圍盒半徑的之和,則表示兩個(gè)Sphere包圍盒不相交,否則兩個(gè)Sphere包圍盒相交,如圖1所示,不等式如下:

圖1 Sphere-Sphere相交檢測(cè)

|SoTo|>R1+R2

(5)

3.2 AABB包圍盒相交檢測(cè)

AABB包圍盒之間的相交檢測(cè),可通過將兩個(gè)包圍盒中心距離在方向軸上的投影分別與兩個(gè)包圍盒在該方向上的半徑之和進(jìn)行比較,如圖2所示。

圖2 AABB-AABB相交檢測(cè)

其中,Uo和Vo是AABB包圍盒U和AABB包圍盒V的中心點(diǎn),α是兩個(gè)包圍盒中心點(diǎn)與垂直方向之間的夾角,lu和lv分別為包圍盒U和V水平方向上的半徑,wu和wv分別為包圍盒U和V垂直方向上的半徑。當(dāng)同時(shí)滿足不等式(6)和不等式(7)時(shí),可以確定兩個(gè)AABB包圍盒不相交,否則相交,如下所示

|UoVo|sinα≥(lu+lv)

(6)

|UoVo|cosα≥(wu+wv)

(7)

3.3 OBB包圍盒相交檢測(cè)

OBB相交檢測(cè)方法一般基于分離軸定理(Separating Axis Theorem)。OBB包圍盒之間的相交檢測(cè)需要測(cè)試最多15個(gè)分離軸才能確定OBB的相交狀態(tài)。這15個(gè)分離軸包括分別對(duì)應(yīng)兩個(gè)物體的3個(gè)坐標(biāo)軸以及垂直于每一軸的9個(gè)軸。如果包圍盒之間在這15個(gè)分離軸上都不相交,則這兩個(gè)OBB包圍盒不相交;否則,只要其中任意一個(gè)分離軸產(chǎn)生相交,即可判斷包圍盒相交。

在利用分離軸檢測(cè)OBB包圍盒之間的是否相交之前,可先通過簡(jiǎn)單計(jì)算來排除不相交情況,OBB包圍盒S和OBB包圍盒T及其外層Sphere包圍盒之間的位置關(guān)系如圖3所示。

圖3 OBB-OBB相交檢測(cè)

其中l(wèi)s和ws是包圍盒S的方向上的半徑,lt和wt是包圍盒T的方向上的半徑。如果圓心距的長(zhǎng)度大于兩個(gè)OBB包圍盒半對(duì)角線之和,則兩個(gè)包圍盒不相交,可用以下不等式來判斷

(8)

假設(shè)物體1的混合包圍盒為Sphere1、AABB1、OBB1,物體2的混合包圍盒為Sphere2、AABB2、OBB2,其相交檢測(cè)算法如下

算法1:混合包圍盒相交檢測(cè)方法

Input:物體1、物體2的混合包圍盒

1) If(Sphere1和Sphere2不等式5)thenreport物體1、物體2無相交

2) else

3) If(AABB1和AABB2滿足不等式(6)、不等式(7)thenreport物體1、物體2無相交

4) else

5) If(!AABB1.intersect(AABB2))thenreport物體1、物體2無相交

6) else

7) If(OBB1和OBB2滿足不等式8)thenreport物體1、物體2無相交

8) else

9) If(!OBB1.intersect(OBB2))thenreport物體1、物體2無相交

10) else report 物體1、物體2OBB包圍盒相交

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

為了驗(yàn)證本文算法的有效性,實(shí)驗(yàn)平臺(tái)系統(tǒng)采用 Windows10,內(nèi)存 16GB,CPU 為 Intel(R) Xeon(R) W-2133 3.6GHz,實(shí)驗(yàn)環(huán)境基于WebGL和 Microsoft Visual Studio Code。

為了驗(yàn)證OBB包圍盒優(yōu)化效果,本文選擇了基于主成分分析的傳統(tǒng)OBB包圍盒構(gòu)造算法作為基準(zhǔn)算法,在不同物體模型上進(jìn)行了包圍盒構(gòu)造的對(duì)照實(shí)驗(yàn),結(jié)果見表2。從表中可以看出,本文提出的OBB包圍盒優(yōu)化算法在保持包圍盒緊密性的同時(shí)(包圍盒體積增長(zhǎng)率少于6%),大幅度減少了OBB包圍盒構(gòu)造時(shí)間,尤其是在模型面片數(shù)量多的情況下。這是因?yàn)樵搩?yōu)化算法只提取物體凸體頂點(diǎn)集來參與OBB包圍盒構(gòu)造的計(jì)算,頂點(diǎn)數(shù)量的減少使得構(gòu)造時(shí)間顯著縮短。

表2 包圍盒構(gòu)造時(shí)間和體積對(duì)比

為了更好地體現(xiàn)本文提出的混合包圍盒結(jié)構(gòu)在相交檢測(cè)上的改進(jìn)效果,在固定虛擬場(chǎng)景空間大小的情況下,將提出的Sphere-AABB-OBB(SAO)與OBB-Sphere算法(OS)、AABB-OBB算法(AO)在不同物體數(shù)量的虛擬場(chǎng)景中進(jìn)行相交檢測(cè)實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表3所示。由實(shí)驗(yàn)結(jié)果可知,在平均相交檢測(cè)時(shí)間上,本文算法始終優(yōu)于其它兩個(gè)對(duì)比算法。其關(guān)鍵在于,本文算法利用外層Sphere、AABB包圍盒排除一定不相交的包圍盒,從而能顯著減少物體相交檢測(cè)時(shí)間。

表3 相交檢測(cè)時(shí)間對(duì)比

5 結(jié)論

為了提高虛擬場(chǎng)景中碰撞檢測(cè)的效率,本文提出了一種基于混合包圍盒的快速碰撞檢測(cè)算法。本文算法對(duì)OBB包圍盒構(gòu)造進(jìn)行優(yōu)化處理,同時(shí)在OBB包圍盒外層構(gòu)造Sphere包圍盒以及AABB包圍盒,以更快地排除不相交物體,并對(duì)OBB包圍盒相交檢測(cè)進(jìn)行改善,這使得相交檢測(cè)過程得到了進(jìn)一步優(yōu)化。最后,通過對(duì)比實(shí)驗(yàn),證明了相對(duì)于其它基準(zhǔn)混合包圍盒的碰撞檢測(cè)算法,本文算法在包圍盒構(gòu)造方面和包圍盒相交檢測(cè)方面都進(jìn)行了有效優(yōu)化,碰撞檢測(cè)的效率得到了顯著提高。