融合包圍盒智能算法的虛擬場景碰撞檢測研究

惠學(xué)武，孟祥宇

(海軍大連艦艇學(xué)院，遼寧 大連 116013)

1 引言

由于圖像處理和虛擬技術(shù)的快速進步，推動了虛擬仿真的應(yīng)用普及[1]。對于場景復(fù)雜，規(guī)模龐大的現(xiàn)實模型，利用虛擬仿真便可以輕松獲得其各項參數(shù)指標(biāo)與性能驗證。在虛擬仿真技術(shù)領(lǐng)域，碰撞檢測是影響其性能的關(guān)鍵技術(shù)，會影響到虛擬仿真執(zhí)行的精度與實時性。隨著虛擬場景中模型規(guī)模和復(fù)雜度的升高，以及場景的動態(tài)變換，給碰撞檢測提出了更高的要求。當(dāng)前針對碰撞檢測，比較常見且有效的方法是GPU加速[2]和HBV[3]。其中GPU加速雖然能夠擺脫對CPU的消耗，提升圖像處理效果，但是成本較高，且靈活性和擴展性受限。HBV是層次包圍盒，它可以從策略和算法角度提高碰撞檢測的適應(yīng)性，所以受到更多的關(guān)注。如文獻[4]設(shè)計了AABB軸對稱包圍盒；文獻[5]設(shè)計了OBB質(zhì)點變換包圍盒；文獻[6]設(shè)計了混合AABB-OBB包圍盒。這些算法普遍缺乏對三角形面片和分布情況的深入分析，在性能上還有提升空間，同時還缺乏對碰撞檢測整體性能的均衡考量。

當(dāng)虛擬場景具有動態(tài)變換特征時，單一的HBV不能很好的保證檢測性能均衡，為此，本文提出了一種融合包圍盒智能算法，可以根據(jù)不同場景選擇合適的包圍盒策略。對于較為簡單的虛擬場景，采用AABB優(yōu)化包圍盒，快速進行非碰撞排除。對于較為復(fù)雜的虛擬場景，采用OBB優(yōu)化包圍盒，通過帶有方向的分離軸實現(xiàn)碰撞檢測。考慮到包圍盒的本質(zhì)是特征點的優(yōu)化，將包圍盒與粒子群算法進行融合，從而把立體碰撞變換成最優(yōu)解搜索，通過收斂計算進一步提高算法性能。

2 包圍盒碰撞檢測算法

2.1 包圍盒策略

虛擬場景變換是一個復(fù)雜的過程，很多情況對碰撞檢測算法的性能要求也不同，一些簡單場景下只需簡單算法即可滿足，而一些復(fù)雜場景下則對算法具有較高要求。另外，并非全部場景都必須采取碰撞檢測。考慮到碰撞檢測性能均衡，盡可能提高碰撞算法的場景適應(yīng)性，本文把模型向xyz坐標(biāo)平面內(nèi)投影，根據(jù)虛擬場景內(nèi)模型的傾斜角來調(diào)整包圍盒策略。通過矢量夾角求解確定場景內(nèi)模型傾斜狀態(tài)。針對投影至xoy面分析，如果x對應(yīng)的最大和最小值點分別是P1(x1，y1)、P2(x2，y2)，那么可以得到P1P2和x軸夾角為

(1)

設(shè)定矢量夾角閾值為θ0，當(dāng)夾角在[0，θ0]范圍內(nèi)時，采取AABB優(yōu)化包圍盒；當(dāng)夾角超過θ0時，采取OBB優(yōu)化包圍盒。

2.2 AABB優(yōu)化包圍盒

圖1 AABB優(yōu)化包圍盒模型

(2)

r=max(|(xc,yc,zc)-P1|，|(xc，yc，zc)-P2|，

|(xc，yc，zc)-P3|)

(3)

此時，圓形的法線表示為

(4)

假定AABB包圍盒中任意兩圓形中心依次為Oi、Oj，半徑依次為ri、rj，對應(yīng)的法線依次為ni、nj。則通過對ni、nj和圓心向量計算點積，可以得到如下結(jié)果

(5)

如果，α=±1，且β=0成立，則意味著|Oi-Oj|超過了ri+rj，此時一定不相交。如果β≠0時，進一步判斷兩圓是否相交。將兩圓所處平面依次標(biāo)記為πi、πj，為避免構(gòu)建πi、πj耗時，本文采用圓心到相交線距離方式求交。先計算πi和πj的交線L，其計算式描述如下

L=2(rinj-rjni)×n/(n·n)

(6)

其中，n=ni×nj。再分別計算出Oi、Oj至交線L的距離di和dj，如下

(7)

當(dāng)di>ri，且dj>rj成立時，代表兩圓相交；否則代表不相交。

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

OBB包圍盒較AABB包圍盒具有方向優(yōu)勢[7]，但是當(dāng)前針對OBB方向的確定大多基于三角面片計算，且缺乏對三角分布的考慮，導(dǎo)致產(chǎn)生方向傾斜，進而影響碰撞檢測精度。為此，本文針對OBB包圍盒的分布問題進行優(yōu)化。

首先需要確定模型中所有三角形形心。將模型上的任意三角形表示為Ti，設(shè)定Ti所在面為xoy，Ti法線為z軸方向。通過構(gòu)造的Ti區(qū)域坐標(biāo)，即可得到三角形Ti形心為

(8)

然后根據(jù)所有三角形形心確定整體形心。把Ti區(qū)域坐標(biāo)向世界坐標(biāo)變換，Ti形心變換后表示為Wi(xci，yci，zci)。模型整體形心計算式如下

(9)

最后得到(xc，yc，zc)即是OBB包圍盒中心。此時模型三角面片信息描述如下

(10)

其中，Sall代表模型全部三角面片面積和；C代表模型協(xié)方差。

假定三角形Ti與圓Tj所處平面依次標(biāo)記為fi、fj，則在判斷Ti與Tj是否相交時，傳統(tǒng)方法需要構(gòu)建fi、fj平面，而本文為了提高相交檢測速度，根據(jù)兩點可確定一條直線理論，先求解三角形Ti與Tj是否具有交線Li。如果沒有交線，則代表三角形Ti與Tj一定不相交；如果有交線，則進一步確定交線Li是否有落在Tj上的部分。如果Li沒有有落在Tj上的部分，則代表三角形Ti與Tj一定不相交；否則代表三角形Ti與Tj相交。

2.4 包圍盒緊密度

在采取矢量夾角調(diào)整包圍盒策略時，可能出現(xiàn)兩夾角沖突情況，從而無法確定使用AABB還是OBB包圍盒。于是，針對這種情況采用緊密度來進一步判斷。緊密度可以通過體積計算得到，式表示為

(|zmin|+|max|))

(11)

其中，V0表示模型體積。將包圍盒在矢量夾角閾值為θ0時的緊密度標(biāo)記為η0，如果η>η0，表示使用AABB包圍盒是有效的；如果η<η0，表示使用OBB包圍盒是有效的。

對于任意兩個包圍盒，假定它們的中心依次是Oi(xi，yi，zi)和Oj(xj，yj，zj)，則可以計算出它們的中心距離

(12)

2.5 樹結(jié)構(gòu)優(yōu)化

現(xiàn)有AABB包圍盒算法中，一般會在最上層采取Sphere等檢測方式[8]，來分離不存在相交的模型。再在下層采取AABB檢測來處理距離較近模型。對于相交深度大的情況而言，由于遍歷深度增加，這種算法的復(fù)雜度將急劇上升。另外，當(dāng)把AABB與OBB融合之后，具有差異的包圍盒間遍歷也會顯著拉低效率。為了提高包圍盒的檢測速度，這里設(shè)計了雙層二叉樹結(jié)構(gòu)，如圖2所示。其中x層為AABB，主要用于區(qū)分非碰撞模型，y層為OBB，主要用于近距離碰撞檢測更新。同時考慮到劃分層較少會降低檢測精度，將x層和y層內(nèi)又劃分成2個子層。

圖2 樹遍歷結(jié)構(gòu)

3 融合智能算法

(13)

其中，(ai,x,ai,y,ai,z)、(bi,x,bi,y,bi,z)分別代表模型a、b內(nèi)特征點i和j的坐標(biāo)位置。粒子群算法采用式(13)的計算來衡量特征對適應(yīng)性。于是，整個算法的碰撞檢測流程描述如下：

1)根據(jù)模型投影角度確定包圍盒策略，并根據(jù)幾何特征構(gòu)造對應(yīng)的AABB或者OBB包圍盒。

2)按層遍歷樹結(jié)構(gòu)，同時根據(jù)AABB或OBB完成各自的相交判斷。

3)當(dāng)判斷出存在碰撞時，通過隨機方式采集模型樣本。構(gòu)造特征點對，并依據(jù)包圍盒確定尋優(yōu)解范圍。

4)通過粒子群迭代計算最優(yōu)解。此外，還需要確定最優(yōu)解所在的包圍盒相交情況。

5)如果本次沒有搜索得到最優(yōu)解，或者所在包圍盒沒有檢測到相交，則繼續(xù)執(zhí)行4)。

6)得到碰撞位置信息，完成碰撞檢測。

4 仿真與結(jié)果分析

實驗平臺系統(tǒng)采用Windows10，內(nèi)存16GB，CPU為Inter Core i7-7700。仿真環(huán)境基于OpenGL和Visual Studio 2017實現(xiàn)。

實驗首先分析特征點對與碰撞檢測效果的關(guān)系。給定粒子群算法的初始規(guī)模為50，迭代計算上限為80。針對圖3所示的待測試虛擬場景，改變特征點對的規(guī)模，利用包圍盒面片規(guī)模代替特征采樣規(guī)模，通過仿真得到不同檢測率所需的時間，結(jié)果如圖4所示，其中分別描述了特征點對為1000、3000、5000時對應(yīng)的檢測效果曲線。根據(jù)結(jié)果分析可得，碰撞檢測時間受特征點對規(guī)模影響。特征點對規(guī)模增加，有助于碰撞檢測的精細(xì)，但是會損失檢測時間。當(dāng)檢測率要達(dá)到50%，特征點對為1000、3000和5000對應(yīng)的檢測時間分別是7.5ms、13.4ms和19.6ms；當(dāng)檢測率要達(dá)到90%，特征點對為1000、3000和5000對應(yīng)的檢測時間分別是13.5ms、19.9ms和26.1ms。顯然特征點對的影響還是很嚴(yán)重的，所以在實際應(yīng)用中，需要根據(jù)待測試虛擬場景的復(fù)雜程度，靈活調(diào)整包圍盒面片的規(guī)模，從而確保獲得最佳檢測性能。

圖3 待測試場景

圖4 特征點對與檢測性能關(guān)系曲線

為了更好的體現(xiàn)融合包圍盒智能算法碰撞檢測的有效性，引入文獻[6]和文獻[7]中算法作為性能對比。變換待測試虛擬場景，通過10次實驗得到碰撞檢測時間。表1為三種方法的檢測時間曲線。根據(jù)實驗結(jié)果可得，本文算法的碰撞檢測平均時間為15.69ms，而文獻[6]和文獻[7]的平均時間分別為23.64ms和23.77ms。本文算法的檢測效率顯著提高，較文獻[6]和文獻[7]分別縮短了33.62%和33.98%。

表1 不同算法的碰撞檢測時間

針對不同的碰撞檢測算法，仿真得到檢測率與檢測效率間的關(guān)系，結(jié)果如圖5所示。根據(jù)對比，在初始階段三種算法的檢測效率和檢測精度差別不大，但是后期本文算法的碰撞檢測時間和檢測率表現(xiàn)出明顯的優(yōu)勢。這是因為本文算法針對不同的投影夾角采取不同的包圍盒算法，優(yōu)化了相交檢測及遍歷樹結(jié)構(gòu)，結(jié)合智能算法后增強了算法的尋優(yōu)能力，所以顯著提高了碰撞檢測的速度和精度。

圖5 碰撞檢測率與檢測時間關(guān)系曲線

表2描述了三種碰撞檢測方法對應(yīng)的檢測數(shù)據(jù)。經(jīng)過對比，由于都采用了混合包圍盒算法，各方法在平均幀計算與更新比例上基本相似。但是本文算法的單位幀樹節(jié)點明顯少于其它方法，僅為文獻[6]的35.46%，文獻[7]的37.47%，顯著縮小了算法的空間和時間消耗。

表2 碰撞檢測數(shù)據(jù)對比

5 結(jié)束語

為了實現(xiàn)虛擬場景碰撞的快速準(zhǔn)確檢測，提出了融合包圍盒智能算法。根據(jù)虛擬場景中模型的投影角度確定包圍盒策略，針對每種包圍盒分別采取相應(yīng)優(yōu)化處理，并引入粒子群算法對包圍盒模型采樣進行尋優(yōu)計算。通過仿真可得，當(dāng)檢測率達(dá)到50%時，算法的碰撞檢測時間僅為8.45ms；當(dāng)檢測率達(dá)到90%時，算法的碰撞檢測時間也僅為15.43ms；10次碰撞檢測的平均時間為15.69ms。實驗結(jié)果充分驗證了融合包圍盒智能算法具有良好的碰撞檢測效率與準(zhǔn)確度，適用于大規(guī)模復(fù)雜虛擬場景下的碰撞檢測。