摘 要： 通過優(yōu)化軸向包圍盒算法（AABB）,，改進(jìn)并完善了視景仿真軟件VEGA的碰撞檢測(cè)功能。同時(shí)提供了一種在VEGA環(huán)境下通過Performer直接訪問和修改物體三維模型的方法,。
關(guān)鍵詞： 碰撞檢測(cè) 視景仿真 VEGA 軸向包圍盒 Performer
隨著計(jì)算機(jī),、圖形處理和圖形生成等技術(shù)的迅速發(fā)展，視景仿真已經(jīng)成為現(xiàn)代仿真技術(shù)的一個(gè)新的研究領(lǐng)域,。它通過構(gòu)建逼真的視覺,、聽覺和觸覺等三維感覺環(huán)境的人機(jī)交互系統(tǒng)，改變了傳統(tǒng)的以數(shù)據(jù)和曲線表示實(shí)驗(yàn)結(jié)果的仿真形式,，使實(shí)驗(yàn)人員以更加直觀,、交互的形式觀察并參與仿真過程，評(píng)估仿真實(shí)驗(yàn)結(jié)果,。因此,，視景仿真在軍事模擬訓(xùn)練、航空航天、城市規(guī)劃仿真,、影視娛樂以及教育培訓(xùn)等諸多領(lǐng)域得到了廣泛應(yīng)用,。
在眾多的視景仿真應(yīng)用中，碰撞檢測(cè)及其相關(guān)問題是最基本也是最重要的組成部分,。實(shí)時(shí),、精確的碰撞檢測(cè)技術(shù)對(duì)于提高虛擬環(huán)境的真實(shí)性，增強(qiáng)虛擬環(huán)境的沉浸感起著至關(guān)重要的作用,。本文通過改進(jìn)的軸向包圍盒碰撞檢測(cè)算法,，對(duì)業(yè)界廣泛使用的視景仿真開發(fā)平臺(tái)VEGA的碰撞檢測(cè)部分進(jìn)行了改進(jìn)。改進(jìn)后的系統(tǒng)不僅顯著提高了碰撞檢測(cè)的速度,，并且可以便捷地得到更為詳細(xì)的碰撞檢測(cè)信息,，滿足了進(jìn)一步進(jìn)行碰撞響應(yīng)處理的需要。
1 VEGA軟件及其碰撞功能簡(jiǎn)介
在現(xiàn)有的視景仿真開發(fā)工具中,，美國MULTIGEN-PARADIGM公司推出的VEGA平臺(tái)是實(shí)現(xiàn)虛擬現(xiàn)實(shí),、實(shí)時(shí)視景仿真和可視化計(jì)算應(yīng)用最廣的解決方案。VEGA基于GL圖形庫,，是在SGI Performer視景軟件開發(fā)包基礎(chǔ)上發(fā)展而來,。VEGA軟件專門設(shè)計(jì)了Isector類處理各種碰撞檢測(cè)問題，并提供八種碰撞檢測(cè)算法供開發(fā)者進(jìn)行選擇(VOLUME,，Z,，HAT，ZPR,，TRIPOD,，LOS，XYZHPR,，BUMP),。其中VOLUME方法用于用戶指定的體與目標(biāo)場(chǎng)景的碰撞檢測(cè)；Z,、HAT,、ZPR、TRIPOD方法用于高程查詢(功能略有不同),；XYZHPR方法用于非平面地球坐標(biāo)系交點(diǎn)及姿態(tài)計(jì)算,；LOS方法用于射線交點(diǎn)和距離查詢；BUMP方法可以用于物體間的碰撞檢測(cè)計(jì)算,。
BUMP定義了一個(gè)由六條線段組成的Segment類型內(nèi)部體,，沿物體體坐標(biāo)系的X、Y,、Z三個(gè)坐標(biāo)軸正負(fù)六個(gè)方向延伸,，長(zhǎng)度受參數(shù)Width,、Length、Height控制,。如果其中的線段與其他物體相交,，則BUMP方法將碰撞結(jié)果保存于result[24]的浮點(diǎn)數(shù)組中，按照固定格式,，從中僅可以提取三個(gè)軸向的碰撞點(diǎn)坐標(biāo)和物體相應(yīng)軸向長(zhǎng)度的碰撞信息,。而且BUMP方法非常消耗系統(tǒng)資源，以兩個(gè)由3 072個(gè)三角形組成的物體相交測(cè)試為例,，BUMP方法的平均檢測(cè)時(shí)間多達(dá)6ms,。
在大多數(shù)需要進(jìn)一步進(jìn)行碰撞響應(yīng)處理的仿真應(yīng)用中，要求得到一些基本的碰撞部位的幾何信息（點(diǎn),、面等）,，進(jìn)而對(duì)這些碰撞部位進(jìn)行處理或保存試驗(yàn)結(jié)果進(jìn)行分析，如物體變形,、確定破片散布等,。而BUMP方法以及VEGA提供的其他檢測(cè)方式都不能滿足這些要求。因此,，設(shè)計(jì)使用了一種基于層次包圍體的碰撞檢測(cè)算法,，改進(jìn)了VEGA用于物體間碰撞檢測(cè)的部分，這不僅使碰撞檢測(cè)速度獲得提高,，同時(shí)也能快捷地獲取碰撞信息并進(jìn)行碰撞響應(yīng)處理,。
2 碰撞檢測(cè)系統(tǒng)設(shè)計(jì)
幾何模型間的碰撞檢測(cè)算法大致可分為空間分解法和層次包圍盒兩類。層次包圍盒的方法應(yīng)用較為廣泛,，適用于復(fù)雜環(huán)境的物體間碰撞檢測(cè)。其基本思想是通過體積略大而幾何特征簡(jiǎn)單的包圍盒來近似表示復(fù)雜的幾何對(duì)象,，從而減少基本幾何元素（通常是三角形）兩兩相交的測(cè)試數(shù)目,，提高碰撞檢測(cè)的效率。
基于層次包圍盒的碰撞檢測(cè)算法的性能可以使用公式（1）進(jìn)行評(píng)估：
目前常用的包圍盒類型有包圍球（SPHERE）,、軸對(duì)齊包圍盒（AABB）,、方向包圍盒（OBB）和離散有向多面體（K-DOP）。包圍球由于緊密性差,，基本很少使用,。OBB和K-DOP（最佳為K=18）具有較好的擬合效果，相交測(cè)試速度快,，但需要較多的存儲(chǔ)空間,，構(gòu)造和更新包圍體都比較慢。軸對(duì)齊包圍盒（AABB）雖然對(duì)幾何體的擬合效果和相交測(cè)試速度不如OBB和K-DOP,，但其在構(gòu)造,、所需存儲(chǔ)空間,、AABB間的相交測(cè)試和包圍體的更新速度方面都比其他算法效率高，因此也是使用最為廣泛的碰撞算法,，尤其適用于多物體運(yùn)動(dòng)的大規(guī)模環(huán)境,。特別是對(duì)于需要?jiǎng)討B(tài)創(chuàng)建包圍樹的情況，構(gòu)建時(shí)間成為重要因素,。
2.1算法描述
軸向包圍盒定義：包含給定幾何體且邊平行于坐標(biāo)軸的最小正六面體,。
軸向包圍盒的構(gòu)造：采用遞歸的方式分別計(jì)算幾何體中各元素頂點(diǎn)x，y,，z的最大值和最小值,，即可構(gòu)造出該幾何體的層次包圍體。
軸向包圍盒的相交測(cè)試：兩個(gè)AABB相交當(dāng)且僅當(dāng)它們?cè)谌齻€(gè)坐標(biāo)軸上的投影分別重疊,。根據(jù)AABB定義的六個(gè)最大值和最小值在三個(gè)軸向的投影,，其兩個(gè)子樹節(jié)點(diǎn)最多僅需六次比較運(yùn)算。
偽代碼如下：
AABB_intersect(A,，B)
for each i∈{X,，Y，Z}
if(aimin>bimax or bimin>aimax) return false,；
return true,；
軸向包圍盒的旋轉(zhuǎn)和更新：根據(jù)AABB定義的六個(gè)最大值和最小值進(jìn)行組合，對(duì)得到的八個(gè)頂點(diǎn)進(jìn)行相應(yīng)旋轉(zhuǎn)后,，選出最大值和最小值即可,。而AABB節(jié)點(diǎn)的更新也遠(yuǎn)比其他算法簡(jiǎn)單，當(dāng)幾何體對(duì)象發(fā)生變形后,，對(duì)變形葉節(jié)點(diǎn)部分自底向上重新選擇最大值和最小值,，僅需六次比較運(yùn)算即可完成一個(gè)節(jié)點(diǎn)的更新。
2.2 算法改進(jìn)
(1)AABB樹由2×N－1個(gè)節(jié)點(diǎn)組成,，其中N是幾何體中基本圖元（通常是三角形）的數(shù)目,。完全AABB樹有N個(gè)葉節(jié)點(diǎn)和N－1個(gè)內(nèi)部節(jié)點(diǎn)，每一個(gè)葉節(jié)點(diǎn)包含一個(gè)指向基本圖元的指針和包圍基本圖元的包圍體,。在進(jìn)行碰撞檢測(cè)時(shí),，遇到測(cè)試兩個(gè)葉節(jié)點(diǎn)的情況，需要首先進(jìn)行包圍體間（BV/BV）的相交測(cè)試,。如果包圍體相交測(cè)試成立,，則可進(jìn)行基本圖元的相交測(cè)試，確定精確位置,。
改進(jìn)算法的基本思想是舍棄AABB樹的葉節(jié)點(diǎn),，即無需進(jìn)行包圍體間的相交測(cè)試，直接進(jìn)行基本圖元間的測(cè)試,。因?yàn)槿绻緢D元相交,，則包圍體間的相交測(cè)試就可以省略,；如果基本圖元不相交，則改進(jìn)所付出的代價(jià)就是測(cè)試包圍體比測(cè)試基本圖元節(jié)省的時(shí)間,。由于AABB樹沒有葉節(jié)點(diǎn),，由更精確的基本圖元（三角形）與包圍體間的相交測(cè)試取代較粗糙的包圍體間的測(cè)試，使得總體上進(jìn)行相交測(cè)試的次數(shù)減少,。例如：包圍體間的測(cè)試結(jié)果是相交,，但是由精確的基本圖元與包圍體間的測(cè)試結(jié)果表明沒有相交，這意味著相交檢測(cè)會(huì)更早提前結(jié)束,，從而提高算法的效率,。
碰撞檢測(cè)查詢偽代碼如下：
程序中三角形和AABB的重疊檢測(cè)采用Akenine-Moler的算法。該算法基于分離軸定理,，對(duì)13條軸線進(jìn)行測(cè)試,，即AABB的三條法線。三角形的法線n,，aij=ei×fj,，i，j∈{0,，1,，2}，其中ei為AABB的三條法線,，fj為三角形邊向量,。三角形與三角形的相交測(cè)試使用經(jīng)典ERIT算法，這兩種算法在參考文獻(xiàn)[1]中有詳細(xì)描述,。
完整的AABB樹有2×N－1個(gè)節(jié)點(diǎn),，現(xiàn)在省略了N個(gè)葉節(jié)點(diǎn)，僅需N－1個(gè)節(jié)點(diǎn),，節(jié)省了大量的存儲(chǔ)空間,。在許多視景仿真應(yīng)用中，一個(gè)場(chǎng)景可能存在許多復(fù)雜物體,，從而占用大量系統(tǒng)內(nèi)存，導(dǎo)致系統(tǒng)性能下降,。與OBB和K-dop算法相比,，改進(jìn)的AABB算法節(jié)省了近70％的存儲(chǔ)空間，顯著改善了系統(tǒng)效率,。
(2)虛擬環(huán)境中可能包含成百上千個(gè)運(yùn)動(dòng)物體,。如果場(chǎng)景中包含N個(gè)運(yùn)動(dòng)物體和M個(gè)固定物體，則窮舉的處理方法需要執(zhí)行的碰撞測(cè)試次數(shù)為： 
,。顯然,，其中包含了大量無效測(cè)試,。隨著N和M數(shù)量的增加，計(jì)算的開銷會(huì)越來越大,。為了盡可能減少進(jìn)行碰撞檢測(cè)的物體對(duì)數(shù)量,，本文采用掃描－修剪算法進(jìn)行篩選處理。
掃描－修剪算法利用虛擬環(huán)境中的時(shí)間相關(guān)性,，即兩幅連續(xù)畫面之間物體的位置與方向變化較小,，通過動(dòng)態(tài)分離軸測(cè)試方法，計(jì)算可能發(fā)生碰撞的物體對(duì),，減少進(jìn)行碰撞檢測(cè)的次數(shù),。其基本原理是：如果兩個(gè)物體重疊，則它們?cè)谌齻€(gè)主軸方向上的所有一維時(shí)間間隔必定也相互重疊,。
假設(shè)Si,、Ei分別表示在某主軸（X，Y,，Z）上的一定時(shí)間間隔,，Ii表示物體i在此時(shí)間間隔[Si，Ei]內(nèi)投影到主軸上的運(yùn)動(dòng)區(qū)間,。將[Si,，Ei]存入一個(gè)排序列表中，然后對(duì)此列表進(jìn)行掃描,，當(dāng)遇到起始點(diǎn)Si時(shí),，將其相應(yīng)的時(shí)間間隔放入一個(gè)活動(dòng)列表；當(dāng)遇到結(jié)束點(diǎn)Ei時(shí),，將相應(yīng)的時(shí)間間隔從活動(dòng)列表中清除,。如果在活動(dòng)列表中存在多個(gè)時(shí)間間隔事件，則它們一定重疊,。如圖1所示：當(dāng)S2進(jìn)入活動(dòng)列表后,，S3進(jìn)入，當(dāng)遇到E2結(jié)束點(diǎn)時(shí),，S3仍然在活動(dòng)列表中,，因此可以確定，此刻物體運(yùn)動(dòng)區(qū)間I2,、I3在該主軸上發(fā)生重疊,。考慮到隨后進(jìn)行的碰撞檢測(cè)調(diào)用中包圍盒測(cè)試也使用投影方式確定是否重疊,，因此在算法程序?qū)崿F(xiàn)上只需要在X,、Y軸上進(jìn)行排序和投影。在精確碰撞檢測(cè)的包圍盒測(cè)試中則先對(duì)Z軸投影,，這樣可以省略在一個(gè)主軸方向上的投影和排序,，提高算法的效率,。
3 VEGA程序中軸向包圍盒（AABB）的建立
構(gòu)造AABB樹，必須獲得幾何模型的點(diǎn),、面信息,。VEGA開發(fā)環(huán)境下是以O(shè)penFlight文件加載模型的。因此,，可以根據(jù)已經(jīng)公開的Flt文件格式,，通過直接讀取Flt文件獲得幾何模型信息，進(jìn)而構(gòu)建包圍樹,。但是這種方式速度較慢,，只能在程序初始化時(shí)加載所有需要精確碰撞檢測(cè)的模型，這極大地影響了程序的靈活性,。
本文提供一種方式,，可以在程序中根據(jù)需要?jiǎng)討B(tài)獲取模型幾何信息。由于封裝的原因,，VEGA沒有直接提供訪問基本幾何元素（三角形）的功能,，但是VEGA是在SGI Performer基礎(chǔ)上發(fā)展起來的，可以通過嵌入Performer函數(shù)調(diào)用,，獲取所需信息,。如果處理時(shí)間允許，也可以對(duì)模型進(jìn)行修改,。
?。?）通過調(diào)用vgGetObjPfNode(VgObj?鄢obj)獲得物體的Pfnode句柄。
?。?）遍歷Pfnode子樹,，利用pfIsOfType(pfnode，pfGetGeodeClassType( ))得到pfGeode節(jié)點(diǎn),。
?。?）在Performer中，模型的點(diǎn),、面存儲(chǔ)于pfGeoSet節(jié)點(diǎn),。調(diào)用pfGetGSet( )函數(shù)可以得到pfGeoSet句柄。
?。?）調(diào)用函數(shù)pfGetGSetAttrLists( )獲得模型的點(diǎn)信息列表,。通過pfGetGSetPrimType( )確定列表信息的存儲(chǔ)順序?？梢允褂胮fGSetAttr( )修改幾何模型。
基本代碼如下：
由于這種方式是在程序中動(dòng)態(tài)讀取場(chǎng)景中模型信息,，所以讀取時(shí)間將直接影響顯示的幀頻,。一般情況下,，正常顯示所需的刷新頻率在25幀/秒以上，VEGA平臺(tái)下開發(fā)的程序幀頻因場(chǎng)景及物體復(fù)雜度的不同而變化,。以一個(gè)由7萬多個(gè)三角形,、132個(gè)物體組成的場(chǎng)景為例，穩(wěn)定的幀頻在19.0ms至20.3ms之間,。經(jīng)過多組試驗(yàn)比對(duì),，這種在程序中動(dòng)態(tài)讀取場(chǎng)景模型信息的方式，通常情況下不會(huì)超過2ms,。如表1數(shù)據(jù)所示,，比較復(fù)雜的模型（模型3和模型4）的讀取時(shí)間都小于2ms，且獨(dú)立部件越多,，時(shí)間越長(zhǎng),。如果模型過于復(fù)雜，可以考慮在程序初始化時(shí)加載,。當(dāng)然,，CREATOR不提倡通過增加模型復(fù)雜度的方式達(dá)到提高逼真度的效果。正確的建模方式應(yīng)該是對(duì)紋理技術(shù),、LOD以及BILLBORD技術(shù)合理搭配地運(yùn)用,，使模型盡量具有真實(shí)感，進(jìn)而達(dá)到在視景驅(qū)動(dòng)時(shí)減少內(nèi)存使用,、提高渲染速度的目的,。
4 實(shí)驗(yàn)結(jié)果及分析
實(shí)驗(yàn)運(yùn)行環(huán)境為：CPU主頻——AMD2400+，內(nèi)存——1GB DDR,，顯卡——128MB,，VEGA版本為3.7。
首先對(duì)VEGA的Bump算法進(jìn)行測(cè)試,，為了屏蔽地形及場(chǎng)景等其他因素對(duì)實(shí)驗(yàn)結(jié)果的影響,，場(chǎng)景中只放置三個(gè)運(yùn)動(dòng)物體（三角形數(shù)：3 072），結(jié)果如表2,。
由實(shí)驗(yàn)數(shù)據(jù)分析可知：Bump方法沒有進(jìn)行優(yōu)化處理,，所以無論是否發(fā)生碰撞，所需的檢測(cè)時(shí)間幾乎相同,，因而非常耗費(fèi)系統(tǒng)資源,。
對(duì)于相同場(chǎng)景，采用軸向包圍盒方法對(duì)兩個(gè)運(yùn)動(dòng)物體進(jìn)行檢測(cè),，結(jié)果如圖2,。其峰值檢測(cè)時(shí)間僅為0.4ms，平均檢測(cè)時(shí)間為0.063ms。對(duì)于多物體的情況,，采用掃描－修剪算法對(duì)運(yùn)動(dòng)物體進(jìn)行排序后再進(jìn)行檢測(cè),，所需時(shí)間也有顯著減少。
通過上述數(shù)據(jù)對(duì)比可以證明,，在VEGA下使用改進(jìn)AABB算法處理物體間碰撞處理可以極大地縮短檢測(cè)時(shí)間,，系統(tǒng)性能也獲得了顯著提高。
碰撞檢測(cè)是視景仿真軟件最重要的組成部分,。本文就VEGA軟件中關(guān)于物體間碰撞檢測(cè)算法進(jìn)行改進(jìn),，將其應(yīng)用于車輛碰撞仿真試驗(yàn)、某武器系統(tǒng)殺傷效果評(píng)估等項(xiàng)目,，均取得了良好的效果,。必須說明，由于仿真場(chǎng)景的高度復(fù)雜性和仿真要求的不同,，處理場(chǎng)景中物體間碰撞的方式也不盡相同,，許多情況下需要多種方法結(jié)合使用。因此,，靈活地選取不同碰撞算法組合,，才能取得較好的仿真效果。
同時(shí),，本文提供了一種在VEGA環(huán)境下調(diào)用Performer訪問,、修改場(chǎng)景中物體三維模型的方法，對(duì)于希望在VEGA下進(jìn)行底層操作的開發(fā)者具有一定的借鑒意義,。
參考文獻(xiàn)
1 Tomas Akenine-Moler,，Haines E.實(shí)時(shí)計(jì)算機(jī)圖形學(xué)(第2 版).北京：北京大學(xué)出版社，2004
2 王志強(qiáng).碰撞檢測(cè)問題研究綜述.軟件學(xué)報(bào),，1999,；10(5)
3 康鳳舉.現(xiàn)代仿真技術(shù)與應(yīng)用.北京：國防工業(yè)出版社，2001
4 Multigen_Paradigm Inc. Vega Programmer's Guide Version 3.7 for Windows NT and Windows 2000.http：//www. multigenparadigm.com,，2001
5 Eckel G,，Jones K.OpenGL PerformerTM programmers guide. Englewood Cliffs：Prentice-Hill，2000