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

惠學武，孟祥宇

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

1 引言

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

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

2 包圍盒碰撞檢測算法

2.1 包圍盒策略

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

(1)

設定矢量夾角閾值為θ0，當夾角在[0，θ0]范圍內時，采取AABB優化包圍盒；當夾角超過θ0時，采取OBB優化包圍盒。

2.2 AABB優化包圍盒

圖1 AABB優化包圍盒模型

(2)

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

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

(3)

此時，圓形的法線表示為

(4)

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

(5)

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

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

(6)

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

(7)

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

2.3 OBB優化包圍盒

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

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

(8)

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

(9)

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

(10)

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

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

2.4 包圍盒緊密度

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

(|zmin|+|max|))

(11)

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

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

(12)

2.5 樹結構優化

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

圖2 樹遍歷結構

3 融合智能算法

(13)

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

1)根據模型投影角度確定包圍盒策略，并根據幾何特征構造對應的AABB或者OBB包圍盒。

2)按層遍歷樹結構，同時根據AABB或OBB完成各自的相交判斷。

3)當判斷出存在碰撞時，通過隨機方式采集模型樣本。構造特征點對，并依據包圍盒確定尋優解范圍。

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

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

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

4 仿真與結果分析

實驗平臺系統采用Windows10，內存16GB，CPU為Inter Core i7-7700。仿真環境基于OpenGL和Visual Studio 2017實現。

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

圖3 待測試場景

圖4 特征點對與檢測性能關系曲線

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

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

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

圖5 碰撞檢測率與檢測時間關系曲線

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

表2 碰撞檢測數據對比

5 結束語

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