虛擬漫游的混合碰撞檢測算法

王建民，殷 宏，許繼恒，黃 瑛，田 凌，李 寧

(解放軍理工大學工程兵工程學院信息技術系軍事仿真教研室，江蘇南京，210007)

在虛擬場景漫游中，由于用戶與物體的移動，物體之間經常會發(fā)生碰撞。為了保持虛擬場景漫游的真實性，需要及時檢測這些碰撞的發(fā)生。碰撞檢測是指空間中任意兩個不可刺穿的物體，不能存在于相同位置的空間區(qū)域［1］。精確的碰撞檢測對于提高虛擬場景漫游的擬真度和速度有著很重要的作用。虛擬漫游碰撞檢測的關鍵問題是如何在有著大量復雜實體的虛擬環(huán)境中，達到一種實時和精確的碰撞檢測，提高虛擬漫游的效率。近幾年，一些快速碰撞算法逐漸應用于虛擬環(huán)境下的碰撞檢測問題取得了很好的效果，其中運用較為廣泛的是包圍盒層次法和空間分解法。李苗［2］對常見的包圍盒層次法進行了分析比較，針對虛擬環(huán)境中比較多的是凸型模型的特點提出了OBB包圍盒算法理論上的改進。馮波等［3］提出一種面向路徑規(guī)劃的連續(xù)碰撞檢測算法。運用層次包圍盒中的AABB包圍盒和投影技術相結合，顯著降低了虛擬環(huán)境路徑規(guī)劃中計算復雜度，但是AABB包圍盒在每次物體轉向時必須重構，增加了系統(tǒng)的負擔?？涤碌龋?］提出基于空間分解和包圍盒層次的混合碰撞檢測算法，但是碰撞檢測主要針對可變性的物體，對含有大量剛性實體的虛擬場景具有一定局限性。

虛擬漫游中的碰撞檢測技術主要涉及以人或者車輛等動態(tài)視線載體與虛擬靜態(tài)實體之間的碰撞檢測，防止漫游過程中發(fā)生動態(tài)視線載體穿過虛擬靜態(tài)實體的現象發(fā)生，大部分虛擬場景中虛擬漫游視線的唯一性就決定了動態(tài)物體的唯一性。針對這些特點和上述的一些方法，筆者提出了一種混合碰撞檢測算法，綜合運用空間分解法、包圍盒層次法和投影技術，在某虛擬場景漫游中取得了良好的效果。

1 碰撞算法預處理

在本次研究中，針對虛擬場景的特點首先進行場景空間的分割，然后進行包圍盒的構造，最后綜合利用包圍盒和投影技術進行碰撞檢測。

1.1 虛擬場景空間的分割

空間分割的方法有很多種，其中一類有效的方法就是用均勻網格對空間實施覆蓋，將空間劃分成多個均等的局域，其中每個網格單元與其中的對象相關聯。這樣就把碰撞檢測局限到了一個網格之中，減少個碰撞檢測的數量。

設虛擬空間為S，把S劃分為邊長均為一定的空間網格。同時對虛擬場景靜態(tài)實體基于空間網格進行均勻劃分，如果某實體同時位于幾個網格之中，則對實體按照網格邊進行分割(圖1)。在劃分結束后，只需要利用世界坐標值除以單元網格長度就可獲得網格單元的坐標。

虛擬場景均勻分解作為混合碰撞檢測的子過程，它的分解深度的確定需要衡量以下2個因素［5］:

(1)網格空間不易過小，加速其構建以及遍歷的過程。

(2)網格空間包含的實體盡可能少，以加速混合包圍盒的構建，以及每一步碰撞的檢測。

空間網格劃分不能過大或者過小，過大的每一步的空間碰撞檢測中檢測物體過多。劃分過小，則使減緩算法的遍歷，這些都會加大算法的復雜度。

1.2 混合包圍盒構建

針對虛擬場景漫游和場景中實體特點，在此選擇構建基于包圍球［6］和OBB包圍盒［7］的混合包圍盒。

OBB包圍盒和包圍球在物體轉向重新建立坐標系的時候，不需要對包圍盒進行重構，同時利用包圍球相交測試復雜度低和OBB包圍盒緊密性好的特點，可以大大提高算法的有效性和實時性。

圖1 虛擬場景空間分割

首先針對實體形狀構建OBB包圍盒，然后在OBB包圍盒的外層再構造一個球體包圍盒，其球體包圍盒的球心直接采用OBB包圍盒的中心，半徑則根據OBB包圍盒的大小來確定。

對于OBB包圍盒的中心位置和方向利用均值μ和協(xié)方差矩陣C來確定［8］。設第i個三角形的頂點是pi，qi，ri，則有包圍盒中心位置:

協(xié)方差矩陣:

其中，n是三角片的個數，每一個都是3×1矩陣。

將C的3個特征根歸一化，由于3個特征根是正交的，可作為一個基底，也就確定了包圍盒的方向。把將要包圍的幾何體頂點向方向軸上投影，找出各方向軸的投影區(qū)間，各投影區(qū)間的長度即為包圍盒的尺寸(圖2)。

圖2 混合包圍盒

2 碰撞檢測算法描述

2.1 虛擬環(huán)境投影檢測原理

三維環(huán)境中投影檢測原理可以描述為:在三維空間的直線運動中，如果在運動區(qū)間內物體與障礙物發(fā)生碰撞，則兩物體在運動方向的投影一定相交。如果物體與運動區(qū)間內的障礙物在運動方向的投影相交，則在運動區(qū)間內兩物體一定發(fā)生碰撞［3］。投影檢測的核心將三維空間的對象相交轉化為二維空間來處理，通過降低緯度來提高檢測的效率。

2.2 算法描述

步驟1 投影坐標系的確立。在碰撞檢測中，首先將空間單元中的物體投影到投影坐標系，然后進行逐步的碰撞檢測分析。所以必須首先確立坐標系。在本次研究中以運動實體的運動方向為Z軸，以Z軸與空間單元交點處確定坐標原點O，然后確定垂直于Z軸的XOY平面(圖3)。

圖3 碰撞檢測中的投影坐標系

步驟2 建立待檢測物體序列表。所有物體的包圍球首先投影到XOY平面，按照被投影的順序，為待檢測物體建立序列。

步驟3 待檢測物體序列檢測。按照序列進行檢測，可以在最先發(fā)生的碰撞的物體之間進行規(guī)避，防止不必要的碰撞檢測。設定序列初值為i=1，序列表最大值為j。如果i≤j，則轉入下一步，否則則證明進入下一空間，轉入步驟1。

步驟4 包圍球碰撞檢測。按照待檢測物體序列表，對物體逐個進行碰撞檢測(圖4)。首先計算包圍球與運動實體包圍球的中心點距離，如果

則不發(fā)生碰撞，繼續(xù)前進，進入步驟3。否則則進行OBB包圍盒碰撞檢測。

步驟5 OBB包圍盒碰撞檢測。OBB包圍盒碰撞在XOY平面上的投影必為矩形，如果兩個矩形的中心點在X方向距離的絕對值小于等于矩形寬度之和的二分之一，并且Y方向距離的絕對值小于等于矩形高度之和的二分之一，那么包圍盒發(fā)生碰撞(圖5)。如果不發(fā)生碰撞，繼續(xù)前進，對下一物體進行檢測，否則則進行精確碰撞。

步驟6 基于等分線的精確碰撞檢測。將多邊形投影到XOY平面，得到一個平面多邊形。如果多邊形相交，必然有一條直線同時與兩個多邊形都相交。根據這個原理，基于兩個中心點投影點做兩條平行的軸線，如果相交則必然發(fā)生在兩條軸線之間。由于能十分準確的得到相交點算法難度多大，就可以設一個誤差值ρ。在此設定當兩個多邊形的距離小于ρ時，發(fā)生碰撞(圖6)。在兩條軸線做n條等分線，如果存在第m條等分線與其中兩個多邊形相交于點(X1，Y1)和點(X1，Y2)。如果|Y1－Y2|＜ρ，則發(fā)生碰撞，需要進行障礙物規(guī)避。否則不發(fā)生碰撞，繼續(xù)前進，轉入步驟3。

步驟7 障礙物的規(guī)避。如果會發(fā)生碰撞，則在第一個碰撞實體之前，按照預定的設定距離、方向角進行轉向。然后轉入步驟1。

圖4 包圍球碰撞

圖5 OBB包圍盒碰撞

圖6 基于等分線的精確碰撞

3 應用實例與分析

將算法運用與虛擬設備巡檢之中，測試內容主要包括:不同場景規(guī)模對算法性能的影響、不同相交率下的算法平穩(wěn)性的影響(圖7)。并與經典的OBB算法和k-dops算法進行比較。

圖7 虛擬設備巡檢下的碰撞檢測

使用本次研究提出的混合碰撞算法在虛擬場景實體模型較少的時候，算法效能并不突出(圖8)。但是隨著模型的增多效能逐漸提高，而且虛擬場景實體模型越多，算法性能得到較大的提高。在算法的平穩(wěn)性上，雖然相交的三角形對數在提高，但是混合碰撞算法仍然表現出了很大的平穩(wěn)性(圖9)。

圖8 場景規(guī)模對算法性能的影響

圖9 相交率對算法性能的影響

4 結論與討論

針對大多數情況下虛擬場景漫游視點的唯一性，筆者提出一種混合碰撞檢測算法。通過引入空間分割縮小了碰撞檢測的空間，同時運用包圍盒層次法和投影技術來簡化碰撞檢測的復雜度。實例表明，該算法能夠有效地支持虛擬環(huán)境下場景漫游中的碰撞檢測。

當然混合碰撞算法也存在著一些不足，以下兩點是下一步研究的重點:

①在場景空間分割上，如何隨著場景模型的變化，達到劃分深度與網格空間體積的平衡。

②等分線和誤差值的運用上使得碰撞檢測存在一定的誤差，如何使得算法在精確性和實時性上更進一步也是研究的重點。

［1］ 魏迎梅，王涌，吳泉源，等.碰撞檢測中的固定方向凸包包圍盒的研究［J］.軟件學報，2001，12(7):1 056-1 063.

［2］ 李苗.實時碰撞檢測算法分析與比較［J］.計算機與現代化，2011(6):88-90.

［3］ 馮波，賈曉亮，王佩，等.面向路徑規(guī)劃的碰撞檢測算法研究［J］.機械設計與制造，2011(2):44-46.

［4］ 康勇，熊岳山，費先宏，等.基于空間分解和包圍盒層次的混合碰撞檢測算法［J］.計算機仿真，2010，27(6):191-194.

［5］ TURK G.Interactive collision detection for molecular graphics.Technical Report TR90-014［R］.University of North Carolina at Chapel Hill，1990.

［6］ SPLLMANN J，BECKER M，TESCHNER M.Efficient updates of bounding sphere hierarchies for geometrically deformable models［C］//The 3rd Workshop in Virtual Reality Interactions and Physical Simulation.Madrid:［s.n.］，2008:53-60.

［7］ CHANG J-W，WANGWENPING，KIMM-S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy［J］.Computer-Aided Design，2008，42(1):50-57.

［8］ CHRISTER Ericson.實時碰撞檢測算法［M］.劉天慧，譯.北京:清華大學出版社，2010.