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