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

林 菲,鄒 玲,張 聰

(杭州電子科技大學計算機學院,浙江 杭州 310000)

1 引言

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

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

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

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

2 混合包圍盒構造方法

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

2.1 OBB包圍盒優化

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

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

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

-mH,imH,j

(1)

(2)

(3)

2.2 AABB包圍盒計算

AABB包圍盒存在多種常見數據結構,其中中心點-邊長這種數據結構更節省存儲空間。在本文算法中,OBB包圍盒和AABB包圍盒的中心點是重合的,采用這種結構類型,只需根據已求出的OBB包圍盒計算外層AABB包圍盒在x、y、z軸上的邊長。

假設OBB包圍盒的中心點為mH,其三個基準方向分別為d1、d2、d3,其基準方向的半徑分別為r1、r2、r3,可得OBB包圍盒的定義區域:

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

(4)

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

2.3 Sphere包圍盒計算

由于OBB是采用中心點-邊長的數據結構,因此要計算它們外層的Sphere包圍盒,以OBB包圍盒中心作為球心,以OBB包圍盒頂點中最遠頂點與球心的距離為Sphere包圍盒的半徑。

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

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

3.1 Sphere包圍盒相交檢測

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

圖1 Sphere-Sphere相交檢測

|SoTo|>R1+R2

(5)

3.2 AABB包圍盒相交檢測

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

圖2 AABB-AABB相交檢測

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

|UoVo|sinα≥(lu+lv)

(6)

|UoVo|cosα≥(wu+wv)

(7)

3.3 OBB包圍盒相交檢測

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

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

圖3 OBB-OBB相交檢測

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

(8)

假設物體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 實驗結果及分析

為了驗證本文算法的有效性,實驗平臺系統采用 Windows10,內存 16GB,CPU 為 Intel(R) Xeon(R) W-2133 3.6GHz,實驗環境基于WebGL和 Microsoft Visual Studio Code。

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

表2 包圍盒構造時間和體積對比

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

表3 相交檢測時間對比

5 結論

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