融合包圍盒智能算法的虛擬場(chǎng)景碰撞檢測(cè)研究

惠學(xué)武，孟祥宇

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

1 引言

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

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

2 包圍盒碰撞檢測(cè)算法

2.1 包圍盒策略

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

(1)

設(shè)定矢量夾角閾值為θ0，當(dāng)夾角在[0，θ0]范圍內(nèi)時(shí)，采取AABB優(yōu)化包圍盒；當(dāng)夾角超過(guò)θ0時(shí)，采取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)

此時(shí)，圓形的法線表示為

(4)

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

(5)

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

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

(6)

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

(7)

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

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

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

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

(8)

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

(9)

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

(10)

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

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

2.4 包圍盒緊密度

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

(|zmin|+|max|))

(11)

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

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

(12)

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

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

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

3 融合智能算法

(13)

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

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

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

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

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

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

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

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

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

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

圖3 待測(cè)試場(chǎng)景

圖4 特征點(diǎn)對(duì)與檢測(cè)性能關(guān)系曲線

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

表1 不同算法的碰撞檢測(cè)時(shí)間

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

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

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

表2 碰撞檢測(cè)數(shù)據(jù)對(duì)比

5 結(jié)束語(yǔ)

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