摘 要： 通過(guò)優(yōu)化軸向包圍盒算法（AABB），改進(jìn)并完善了視景仿真軟件VEGA的碰撞檢測(cè)功能。同時(shí)提供了一種在VEGA環(huán)境下通過(guò)Performer直接訪問(wèn)和修改物體三維模型的方法。
關(guān)鍵詞： 碰撞檢測(cè) 視景仿真 VEGA 軸向包圍盒 Performer
隨著計(jì)算機(jī)、圖形處理和圖形生成等技術(shù)的迅速發(fā)展，視景仿真已經(jīng)成為現(xiàn)代仿真技術(shù)的一個(gè)新的研究領(lǐng)域。它通過(guò)構(gòu)建逼真的視覺(jué)、聽(tīng)覺(jué)和觸覺(jué)等三維感覺(jué)環(huán)境的人機(jī)交互系統(tǒng)，改變了傳統(tǒng)的以數(shù)據(jù)和曲線表示實(shí)驗(yàn)結(jié)果的仿真形式，使實(shí)驗(yàn)人員以更加直觀、交互的形式觀察并參與仿真過(guò)程，評(píng)估仿真實(shí)驗(yàn)結(jié)果。因此，視景仿真在軍事模擬訓(xùn)練、航空航天、城市規(guī)劃仿真、影視娛樂(lè)以及教育培訓(xùn)等諸多領(lǐng)域得到了廣泛應(yīng)用。
在眾多的視景仿真應(yīng)用中，碰撞檢測(cè)及其相關(guān)問(wèn)題是最基本也是最重要的組成部分。實(shí)時(shí)、精確的碰撞檢測(cè)技術(shù)對(duì)于提高虛擬環(huán)境的真實(shí)性，增強(qiáng)虛擬環(huán)境的沉浸感起著至關(guān)重要的作用。本文通過(guò)改進(jìn)的軸向包圍盒碰撞檢測(cè)算法，對(duì)業(yè)界廣泛使用的視景仿真開(kāi)發(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)有的視景仿真開(kāi)發(fā)工具中，美國(guó)MULTIGEN-PARADIGM公司推出的VEGA平臺(tái)是實(shí)現(xiàn)虛擬現(xiàn)實(shí)、實(shí)時(shí)視景仿真和可視化計(jì)算應(yīng)用最廣的解決方案。VEGA基于GL圖形庫(kù)，是在SGI Performer視景軟件開(kāi)發(fā)包基礎(chǔ)上發(fā)展而來(lái)。VEGA軟件專門設(shè)計(jì)了Isector類處理各種碰撞檢測(cè)問(wèn)題，并提供八種碰撞檢測(cè)算法供開(kāi)發(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)行分析，如物體變形、確定破片散布等。而B(niǎo)UMP方法以及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è)。其基本思想是通過(guò)體積略大而幾何特征簡(jiǎn)單的包圍盒來(lái)近似表示復(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)建包圍樹(shù)的情況，構(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è)子樹(shù)節(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樹(shù)由2×N－1個(gè)節(jié)點(diǎn)組成，其中N是幾何體中基本圖元（通常是三角形）的數(shù)目。完全AABB樹(shù)有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樹(shù)的葉節(jié)點(diǎn)，即無(wú)需進(jìn)行包圍體間的相交測(cè)試，直接進(jìn)行基本圖元間的測(cè)試。因?yàn)槿绻緢D元相交，則包圍體間的相交測(cè)試就可以省略；如果基本圖元不相交，則改進(jìn)所付出的代價(jià)就是測(cè)試包圍體比測(cè)試基本圖元節(jié)省的時(shí)間。由于AABB樹(shù)沒(méi)有葉節(jié)點(diǎn)，由更精確的基本圖元（三角形）與包圍體間的相交測(cè)試取代較粗糙的包圍體間的測(cè)試，使得總體上進(jìn)行相交測(cè)試的次數(shù)減少。例如：包圍體間的測(cè)試結(jié)果是相交，但是由精確的基本圖元與包圍體間的測(cè)試結(jié)果表明沒(méi)有相交，這意味著相交檢測(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樹(shù)有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ù)為： 
。顯然，其中包含了大量無(wú)效測(cè)試。隨著N和M數(shù)量的增加，計(jì)算的開(kāi)銷會(huì)越來(lái)越大。為了盡可能減少進(jìn)行碰撞檢測(cè)的物體對(duì)數(shù)量，本文采用掃描－修剪算法進(jìn)行篩選處理。
掃描－修剪算法利用虛擬環(huán)境中的時(shí)間相關(guān)性，即兩幅連續(xù)畫面之間物體的位置與方向變化較小，通過(guò)動(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樹(shù)，必須獲得幾何模型的點(diǎn)、面信息。VEGA開(kāi)發(fā)環(huán)境下是以O(shè)penFlight文件加載模型的。因此，可以根據(jù)已經(jīng)公開(kāi)的Flt文件格式，通過(guò)直接讀取Flt文件獲得幾何模型信息，進(jìn)而構(gòu)建包圍樹(shù)。但是這種方式速度較慢，只能在程序初始化時(shí)加載所有需要精確碰撞檢測(cè)的模型，這極大地影響了程序的靈活性。
本文提供一種方式，可以在程序中根據(jù)需要?jiǎng)討B(tài)獲取模型幾何信息。由于封裝的原因，VEGA沒(méi)有直接提供訪問(wèn)基本幾何元素（三角形）的功能，但是VEGA是在SGI Performer基礎(chǔ)上發(fā)展起來(lái)的，可以通過(guò)嵌入Performer函數(shù)調(diào)用，獲取所需信息。如果處理時(shí)間允許，也可以對(duì)模型進(jìn)行修改。
（1）通過(guò)調(diào)用vgGetObjPfNode(VgObj?鄢obj)獲得物體的Pfnode句柄。
（2）遍歷Pfnode子樹(shù)，利用pfIsOfType(pfnode，pfGetGeodeClassType( ))得到pfGeode節(jié)點(diǎn)。
（3）在Performer中，模型的點(diǎn)、面存儲(chǔ)于pfGeoSet節(jié)點(diǎn)。調(diào)用pfGetGSet( )函數(shù)可以得到pfGeoSet句柄。
（4）調(diào)用函數(shù)pfGetGSetAttrLists( )獲得模型的點(diǎn)信息列表。通過(guò)pfGetGSetPrimType( )確定列表信息的存儲(chǔ)順序。可以使用pfGSetAttr( )修改幾何模型。
基本代碼如下：
由于這種方式是在程序中動(dòng)態(tài)讀取場(chǎng)景中模型信息，所以讀取時(shí)間將直接影響顯示的幀頻。一般情況下，正常顯示所需的刷新頻率在25幀/秒以上，VEGA平臺(tái)下開(kāi)發(fā)的程序幀頻因場(chǎng)景及物體復(fù)雜度的不同而變化。以一個(gè)由7萬(wàn)多個(gè)三角形、132個(gè)物體組成的場(chǎng)景為例，穩(wěn)定的幀頻在19.0ms至20.3ms之間。經(jīng)過(guò)多組試驗(yàn)比對(duì)，這種在程序中動(dòng)態(tài)讀取場(chǎng)景模型信息的方式，通常情況下不會(huì)超過(guò)2ms。如表1數(shù)據(jù)所示，比較復(fù)雜的模型（模型3和模型4）的讀取時(shí)間都小于2ms，且獨(dú)立部件越多，時(shí)間越長(zhǎng)。如果模型過(guò)于復(fù)雜，可以考慮在程序初始化時(shí)加載。當(dāng)然，CREATOR不提倡通過(guò)增加模型復(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方法沒(méi)有進(jìn)行優(yōu)化處理，所以無(wú)論是否發(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í)間也有顯著減少。
通過(guò)上述數(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)目，均取得了良好的效果。必須說(shuō)明，由于仿真場(chǎng)景的高度復(fù)雜性和仿真要求的不同，處理場(chǎng)景中物體間碰撞的方式也不盡相同，許多情況下需要多種方法結(jié)合使用。因此，靈活地選取不同碰撞算法組合，才能取得較好的仿真效果。
同時(shí)，本文提供了一種在VEGA環(huán)境下調(diào)用Performer訪問(wèn)、修改場(chǎng)景中物體三維模型的方法，對(duì)于希望在VEGA下進(jìn)行底層操作的開(kāi)發(fā)者具有一定的借鑒意義。
參考文獻(xiàn)
1 Tomas Akenine-Moler，Haines E.實(shí)時(shí)計(jì)算機(jī)圖形學(xué)(第2 版).北京：北京大學(xué)出版社，2004
2 王志強(qiáng).碰撞檢測(cè)問(wèn)題研究綜述.軟件學(xué)報(bào)，1999；10(5)
3 康鳳舉.現(xiàn)代仿真技術(shù)與應(yīng)用.北京：國(guó)防工業(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