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