海戰場環境中基于射線的碰撞檢測算法研究＊

許宏泉 明 芳

（武漢市74223信箱1） 武漢 430074）（武漢數字工程研究所2） 武漢 430074）

1 引言

在海戰場環境中，相對運動的物體之間可能會發生碰撞，通常分為有目標的碰撞和無目標的碰撞兩類［1］。有目標的碰撞檢測，例如射擊導彈通常是針對某個目標的，需要判斷目標與導彈等是否發生碰撞以及后果如何。無目標的碰撞檢測，例如低空飛行的飛機需要判斷飛機與地形、地物、艦艇是否發生碰撞。實時性、精確性是檢驗碰撞檢測成敗的兩個關鍵因素。包圍盒是廣泛應用的碰撞檢測技術，本文根據海戰場環境中運動物體的特點選擇不同包圍盒，對基于射線的相交測試方法進行研究。

2 碰撞檢測算法的分類

碰撞檢測算法種類繁多，主要是從時間域的角度和空間域的角度來進行劃分。

從時間域的角度，碰撞檢測算法可分為靜態碰撞檢測算法、離散碰撞檢測算法和連續碰撞檢測算法三類［2］。

基于空間域的碰撞檢測算法可分為基于物體空間的碰撞檢測算法和基于圖像空間的碰撞檢測算法。

基于物體空間的碰撞檢測算法又可以進一步劃分為：基于物體的不同表示模型；基于不同的空間結構。物體空間的碰撞檢測算法可采用不同的空間結構來提高效率，根據所用空間結構的不同可將它們分為兩類：空間剖分法（Space Decomposition）和層次包圍體樹法（Hierarchical Bounding Volume Trees）。空間剖分法采用對整個場景的層次剖分技術來實現，而層次包圍體樹法則是通過對場景中每個物體建構合理的層次包圍體樹來實現。

空間剖分法：場景的層次剖分方法主要有均勻剖分、BSP樹、k-dop樹和八叉樹（Octree）等。在處理不同的場景和具有不同形狀及復雜度的物體時，這類算法較難保持比較一致的檢測效率。

層次包圍體樹法：物體的層次包圍體樹可以根據其所采用包圍體類型的不同來加以區分，包圍體類型主要包括包圍球、AABB、OBB、k-dop等等。

3 包圍盒的選擇原則

判斷兩個多面體物體間是否發生碰撞，實質上是判斷一個物體的一邊是否穿過另一個物體的一個面。這種算法對N個物體測試的平均計算時間是O（N2EF），其中E和F分別是物體平均的邊數和面數，并且隨著物體的數量和復雜性的增加，測試量成平方的增加。因此包圍盒的選擇是提高檢測精度、降低計算量的關鍵。

3.1 運動物體的分類

從空間分布角度進行劃分，海戰場環境可以分為空中環境和水面環境，相應的運動物體可以分為空中物體和水面物體。

·海戰場中的空中物體主要是指各類作戰飛機。空中物體一般都形狀不規則，表面特征復雜，具有范圍很廣的立體作戰領域，且運動速度快，機動性高。

·海戰場中的水面物體主要是指艦艇、潛艇等武器的運載和發射工具。水面物體一般形狀較為規則，近似于立方體，作戰領域為平面，且范圍相對較小，運動速度慢，機動性較低。

3.2 包圍盒的選擇

常用的包圍盒有四種：包圍球、AABB軸向包圍盒、OBB軸向包圍盒、k-dop包圍盒。

包圍球是包圍物體的最小球體。此類包圍盒簡單，易于計算，非常易于做重疊測試和節點修改，但是與物體的逼近程度較差。

AABB軸向包圍盒是一個六面盒狀長方體，且其面方向性劃分按如下方式進行：面法線皆平行于給定的坐標軸，最大的特點是能夠實現快速的相交測試。

OBB軸向包圍盒是三維空間的一個任意方向的長方體包圍盒。此類包圍盒可提供非常緊湊的逼近效果，修改OBB軸向包圍盒較為簡單，只需將兩個變換矩陣相乘，但是重疊測試的耗費比AABB高一個數量級。

k-dop包圍盒是一種凸多面體，它的面由一些半空間所確定，這些半空間的外法向是從k個固定方向選取的。與包圍球和AABB包圍盒相比，kdop包圍盒對物體的逼近程度相對較好，與OBB包圍盒相比，k-dop包圍盒的重疊測試和節點修改耗費相對較低。

空中物體形狀不規則，表面特征復雜，但是其速度快，機動性高，因此可以選擇簡單的包圍盒進行碰撞檢測，如包圍球或AABB軸向包圍盒。

形狀規則，表面特征復雜的水面物體，特別是具有較為突出的可活動組件的水面物體，例如載有雷達、炮彈的艦艇，可選擇復雜的包圍盒，如OBB包圍盒或k-dop包圍盒。

4 基于射線的相交測試

4.1 “射線／體”相交測試

海戰場環境中物體數量多，采用兩兩相交測試的方法進行碰撞檢測，計算量龐大。本文采用基于“射線／體”相交測試的方法進行碰撞檢測，運動物體起點即是射線的起點，物體的運動方向即是射線的方向。體即是海戰場環境中某一區域中物體的包圍體，通常用包圍盒或包圍球作為該區域的包圍體。在相交測試的過程中，如果射線與包圍體發生相交，則認為射線與包圍體發生了碰撞。

碰撞檢測的基本原理就是利用相交檢測的方法判斷空間物體是否相交，某些情況下還需要求出相交的部分。在實際情況中，相對位置較遠的兩個物體在很長一段時間內可能都是不會相交的，兩個相對靜止的物體也不可能相交。碰撞檢測流程圖如圖1所示。

圖1 碰撞檢測流程圖

為了提高碰撞檢測效率，快速排除不相交的物體，采用的加速算法通常有以下幾種：

1）背向剔除［3］：背向運動的物體基本不可能發生碰撞。

2）區域剔除［4］：相隔較遠的物體不可能發生碰撞。

3）類型剔除：地面上的物體不可能與水下的物體發生碰撞。

4）閾值剔除［5］：檢測導彈與地物是否發生碰撞時，設置高度或距離閾值，當導彈高度或距離到達閾值以內時，才進行碰撞檢測。

4.2 相交測試分類

海戰場環境中的所有物體分為兩種：靜態物體和動態物體。靜態物體的位置是固定不變的，因此不需要對靜態物體間進行碰撞檢測。動態物體在三維地形場景中進行旋轉或平移運動時可能與場景中的物體發生相交的情況，因此，本文碰撞檢測分為兩種情況：運動物體和靜止物體之間碰撞檢測、運動物體之間碰撞檢測［6］。

1）運動物體和靜止物體相交測試

如圖2所示的原理，黑色三角形代表對象運動之前的起始位置，白色五邊形代表對象以一定速度方向運動之后的新位置，然后通過連接這兩個點產生一條線段，通過判斷線段與包圍體是否有交點。如果這個包圍體代表的是地面，如果物體運動后的新位置與地面有一個交點，則該運動不能執行，只能保持在原地，否則會穿過地面到達地底下去；如果這個包圍體代表的是場景物體，則該運動會發生碰撞。

圖2 運動物體和靜止物體相交測試示意圖

2）運動物體之間相交測試

海戰場環境中通常需要判斷是兩個動態物體間是否發生碰撞檢測的問題，例如飛行的導彈能否命中運動的目標。動態相交測試是判斷兩個運動的物體是否相交，以及相交的時間點。兩個物體都有自己的運動參數，從單個物體的角度處理問題，相對而言比較簡單。通常情況下物體可假定為分段性運動［7］，即在兩點間實現位移，并在初始點或終點即刻進行旋轉操作。因此對于兩個物體A和B，可從A的運動中“減去”物體B的運動，則物體B相對靜止，且相交測試可視作運動的物體A與靜止的物體B之間的計算，即兩物體之間的彼此相對運動［8］。最后，如果交點已計算完畢，需要將B的運動狀態最終作用于交點之上，從而獲取正確的世界坐標而非物體的相對坐標。

圖3 采用區間二分法計算運動球體與靜止球體碰撞測試步驟示意圖

通常采用基于遞歸的二分搜索算法［10］計算碰撞時刻（若存在），即對物體的運動路徑實施采樣，并在位移過程中執行多次靜態物體測試。如果在運動路徑上測試全部n個采樣點，即時間復雜度為O（n）。球體S高速掠過一個靜止物體，S的初始位置為A且運動方向以向量v表示。首先，構造一個包圍球且完全包含位置A及位置A＋v的球體，并利用該包圍球與其他物體執行碰撞測試。若不存在碰撞，則S直接到達終點。然而，若其中未檢測到碰撞，則二分計算位移量并以同一方式遞歸地測試前半部分。如果其中未檢測到碰撞，則對后半部分執行相同的遞歸測試。若受測位移量在趨于某個最小預定值時碰撞檢測過程仍未結束，則可假定該碰撞存在且遞歸結束。

圖3（a）顯示了區間二分法的測試過程［11］，其中，根據總位移量構造了一個球體，并在某一點處檢測到與另一物體發生碰撞。這里需要計算位移的中點，而后分別對各半部分執行遞歸調用。在首次遞歸調用過程中，由起始點至中點形成的球體B1中并未發現任何碰撞，且該遞歸調用退出并返回“未碰撞”信息；該過程繼續執行并開始第二次遞歸調用，同時，檢測到包圍后半程的球體B2與物體發生碰撞。因此，在當前二分區間內生成新的中點并針對該二分區間再次執行遞歸計算，如圖3（b）所示。同理，球體B3中發生且執行遞歸調用。在本例中，由于產生了碰撞相交，因而遞歸調用最終退出，算法如下：

5 結語

在海戰場環境中，對各種運動物體進行碰撞檢測要兼顧效率和精度。本文采用的基于射線的碰撞檢測技術可以通過碰撞檢測加速算法排除大部分明顯不可能發生碰撞的物體，減少參與碰撞檢測的物體數量，從而提高碰撞檢測的效率。對可能發生碰撞的物體，則采用較為復雜的OBB包圍盒或k-dop包圍盒進行碰撞檢測，從而提高碰撞檢測的精度。

［1］萬剛，夏青，武志強.虛擬視景仿真中實體行為建模技術的研究［J］.信息工程大學測繪學院學報，2002，19（3）：3～4

［2］范昭煒.實時碰撞檢測技術研究［D］.杭州：浙江大學，2003：30～40

［3］Akenine-Moller T，Haines E.實時計算機圖形學［M］.普建濤，譯.北京：北京大學出版社，2004：50～60

［4］王海.林木場景漫游關鍵技術的研究與實現［D］.北京：北京林業大學碩士學位論文，2007，6：42

［5］李芙玲，張謹.碰撞檢測技術研究［J］.華北科技學院學報，2004，1（2）：71～73

［6］高麗娜，馬堯海.虛擬漫游中的碰撞檢測問題的解決方法［J］.計算機仿真，2006，23（2）：189～191

［7］魏迎梅.虛擬環境中碰撞檢測問題的研究［D］.長沙：國防科學技術大學，2000：80～90

［8］王海.林木場景漫游關鍵技術的研究與實現［D］.北京林業大學大學，2007：40～42

［9］宗美玲，童小念.虛擬現實環境下的碰撞檢測實現［J］.計算機與數字工程，2011，39（4）

［10］Jeschke S.Wimmer M，Purgathofer W.Image-based Representations for Accelerated Rendering of Complex Scenes［C］／／Proceedings of EUROGRAPHICS，Dublin，2005：1～20

［11］Mantler S，Robert F，Tobler，et al.The State of the Art in Realtime Rendering of Vegetation［R］.Vienna：VRVis Research Center for Virtual Reality and Visualization，2003：20～30