林 菲,鄒 玲,張 聰

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

1 引言

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

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

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

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

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

混合包圍盒算法通常是在外層使用構(gòu)造簡單的包圍盒,而在內(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)軸的任意方向上包圍物體模型的最小長方體,其結(jié)構(gòu)緊湊、檢測精度高于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)-邊長這種數(shù)據(jù)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。在本文算法中,OBB包圍盒和AABB包圍盒的中心點(diǎn)是重合的,采用這種結(jié)構(gòu)類型,只需根據(jù)已求出的OBB包圍盒計(jì)算外層AABB包圍盒在x、y、z軸上的邊長。

假設(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軸上的邊長。

2.3 Sphere包圍盒計(jì)算

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

3 混合包圍盒相交檢測方法

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

3.1 Sphere包圍盒相交檢測

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

圖1 Sphere-Sphere相交檢測

|SoTo|>R1+R2

(5)

3.2 AABB包圍盒相交檢測

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

圖2 AABB-AABB相交檢測

其中,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包圍盒相交檢測

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

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

圖3 OBB-OBB相交檢測

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

(8)

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

算法1:混合包圍盒相交檢測方法

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ǒ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)造的對照實(shí)驗(yàn),結(jié)果見表2。從表中可以看出,本文提出的OBB包圍盒優(yōu)化算法在保持包圍盒緊密性的同時(shí)(包圍盒體積增長率少于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í)間和體積對比

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

表3 相交檢測時(shí)間對比

5 結(jié)論

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