基于VR的碰撞檢測算法研究＊

（海軍航空工程學院青島校區 青島 266041）

1 引言

隨著VR（Virtual Reality）技術在日常生活中應用的日漸深入，用戶對VR 系統的真實性（即：實時性、精確度）提出了更高的要求［1］。而且，三維幾何模型越來越復雜，虛擬環境的場景規模也越來越大。VR 中動態物體與靜態物體之間或動態物體與動態物體之間的交互基礎是碰撞檢測。若想實現自然、精確的人機交互，就必須解決碰撞檢測等關鍵技術問題。

2 碰撞檢測的定義

假設三維空間中有n個運動模型，每個運動模型都隨著時間改變自身的位置和姿態，那么碰撞檢測就是判斷是否存在一對或多對模型占有的空間發生重疊［2］。從計算幾何的角度可以這樣定義碰撞檢測：設三維幾何空間為R，用三維幾何坐標系統FW表示，在FW中用FA表示模型A所占的集合，顯然FA是FW的子集。那么FW隨著時間的變化構成了一個四維空間坐標系統CW，模型A沿著一定軌跡運動就形成了CW的子集CA，碰撞檢測就是判斷C1∩C2∩…∩Cn≠Φ是否成立。

定義從理論上給出了碰撞檢測的精確方法，但計算的復雜度和時效性在工程實際中是不能接受的，其中的瓶頸問題就是四維集合CA的計算。在實現過程中，必須采用折中的方法進行運算，具體來說就是通過犧牲計算精度的方法來提高計算速度，從而滿足實際應用需求［3］。

3 碰撞檢測的影響因素

簡單的說，碰撞檢測就是檢測虛擬場景中不同對象之間是否發生了碰撞。從幾何上講，碰撞檢測表現為兩個多面體的求交測試問題；按對象所處的空間可分為二維平面碰撞檢測和三維空間碰撞檢測。歸納起來，影響碰撞檢測的因素主要包括實時性、精確度、模型類別、檢測類別、場景特征五個方面［4］。

3．1 實時性

虛擬環境中通常包含大量物體，加上物體的形狀復雜，檢測這些物體間的碰撞情況是一項非常耗時的工作。同時，VR 要求系統能夠與用戶實時交互，不僅要求實時繪制，而且要求實時碰撞檢測。碰撞檢測實際上已經成為虛擬仿真系統的一大瓶頸。因此，碰撞檢測的研究目標是如何在滿足實時交互的要求下完成對大量復雜物體的碰撞檢測，而最根本的是降低算法的復雜度。

3．2 精確度

虛擬環境中碰撞檢測的采用近似檢測還是精確檢測取決于具體的應用要求。如對于環境漫游系統，只需近似模擬碰撞情況，并不要求碰撞檢測達到100%精確，而對于如虛擬手術仿真等情況，則要求必須進行精確檢測。

3．3 模型類別

虛擬環境中的物體模型主要分為面模型和體模型兩大類。面模型用物體邊界來表示物體，而不包括物體內部信息。體模型采用體元來表示物體，可描述物體的內部信息。不同的模型類別決定了采用不同的方法進行檢測。如很多算法要求輸入模型是實體，即可表示成閉合曲面。

3．4 檢測類別

虛擬環境中碰撞檢測的類別主要包括四種情況：1）檢測是否有碰撞；2）檢測碰撞發生的位置；3）檢測物體間的距離；4）檢測下一次碰撞將在何時發生。最常見的情況是要求得到前兩個檢測結果，但后兩個結果也可運用于檢測碰撞，預測碰撞和避免碰撞。

3．5 場景特征

按物體的運動狀況，場景可分為靜態部分和動態部分。動態物體越多，碰撞發生的概率越大，碰撞檢測的復雜程度也就越高。場景中的運動物體還可分為剛性和柔性（或稱可變形物體）兩種，而柔體的碰撞檢測比剛體的要復雜的多。

4 碰撞檢測算法分類

平面空間中的碰撞檢測相對簡單，已經有較為成熟的檢測算法，而三維空間碰撞檢測則要復雜得多。按照場景中物體的運動狀態劃分，三維空間中的碰撞檢測可分為靜態檢測算法和動態檢測算法［5］。從時間軸考慮，動態檢測算法可分為連續算法和離散算法。當前應用于虛擬仿真系統的算法大部分屬于離散型檢測算法。離散型算法又可分為基于圖形和基于圖像的算法，取得的研究成果也較多。兩者的區別在于前者利用物體三維幾何特征進行分析計算；后者利用二維投影及深度信息進行求交計算。離散型算法中，基于圖形的層次包圍盒算法、空間分割算法和距離跟蹤算法應用比較廣泛，是本文的研究重點。

圖1 碰撞檢測算法分類

5 碰撞檢測算法研究

最常見的碰撞檢測要求確定是否發生碰撞和碰撞發生的位置，而不對碰撞發生的時間和位置進行預測。而且場景中動態物體的數量是有限的，碰撞檢測的復雜程度不是很高。因此，在虛擬仿真系統中，主要是如何解決碰撞檢測的實時性和精確性的矛盾。

由于碰撞檢測的研究工作大多是基于面模型進行的，三維模型一般采用多面體造型的方式來表達，精確的碰撞檢測需要在面片的層次上才能實現。也就是說，精確判斷兩者之間是否發生了碰撞，需要檢測兩者的面片是否發生了碰撞（在實際的操作中一般選用三角面片）。如果虛擬環境中有很多運動物體，若直接進行精確的碰撞檢測則非常復雜，系統的計算量大，對操作的實時反應性就很差。例如，在有N個零件的虛擬環境中，要檢驗每個實體是否與其它N-1個實體發生碰撞，其時間復雜度為N×（N-1）［6］。由于這一過程的干涉檢驗的分析非常復雜，當N比較大的時候，這種計算的復雜度在實際中是不能接受的，必須采取折中的方法來調和實時性和精確性的矛盾，即適度犧牲計算精度，提高計算速度，達到兩者間的協調統一。選擇合適的碰撞檢測算法就顯得非常重要，要求算法既不能過于復雜，又能滿足系統的要求。

從本質上說，離散碰撞檢測算法在每一時間離散點上可以通過類似于靜態干涉檢測算法的方法來實現，通過時間步長dt來確定計算的頻率，運算效率得到顯著提高。但也存在著一些問題，在物體運動速度過快的場景中，在某時間段T到T＋dt中兩物體很可能發生碰撞，因此而發生漏檢和穿刺現象。通過采用自適應步長技術，在一定程度上減少離散碰撞檢測算法的不足。連續碰撞檢測算法不僅涉及到三維空間問題，還要考慮第四維時間t。該類算法能較好地解決離散碰撞檢測算法存在的刺穿和漏檢等問題，但計算速度較慢，無法滿足大規模場景中多物體的碰撞檢測。

因此，采用何種算法要根據對碰撞檢測模型精度的要求，顯然精度要求越高，模型越復雜，需要的計算資源也越多。總的來說，虛擬環境中幾何模型間的碰撞檢測算法主要包括層次包圍盒（hierarchical bounding boxes）法、空間分解（space decomposition）法和距離跟蹤（distance tracking）法三種［7］。

5．1 層次包圍盒法

圖2 包圍盒的類型

層次包圍盒法的核心思想是用體積略大而幾何特性簡單的包圍盒來近似地描述復雜的幾何對象。在進行碰撞檢測時首先進行包圍盒之間的相交測試。如果包圍盒相交，再進行幾何對象之間精確的碰撞檢測，適用于復雜環境中的碰撞檢測。由于實時性的要求，在虛擬場景中遍歷所有基本幾何元素的兩個凸多面體的碰撞檢測很難應用。一般是用相對簡單的包圍盒包裹虛擬對象，并用包圍盒代替虛擬對象進行碰撞檢測。包圍盒的簡單性和它包裹虛擬對象的緊密性是一對矛盾，包圍盒越簡單它對虛擬對象的包裹緊密性越差。所以如何更好地兼顧簡單性和緊密性成為包圍盒法的關鍵。經典的包圍盒主要有軸向包圍盒（axis aligned bounding box，AABB）、包圍球（sphere）、方向包圍盒（oriented bounding box，OBB）、離散方向多面體（discrete orientation polytope，K-Dops）盒等［8］，如圖2所示。

通常，可以通過代價函數（Ttotal）來對不同包圍盒的優劣進行初步分析：

其中：Ttotal為一對幾何體相交測試的總代價；Nb為參與相交測試的包圍盒對數：Cb為一對包圍盒相交測試的代價；Np為參與相交測試的幾何元素對數；Cp為一對幾何元素相交測試的代價；Nu為包圍對象移動后需要更新節點的包圍盒個數；Cu為更新一個移動后的包圍盒所需代價；Nv為包圍盒旋轉后需要更新的包圍盒個數；Cv為更新一個包圍盒旋轉后需要的代價；Cd為對象發生變形后更新節點的包圍盒所需代價。

從式（1）可以得到某種包圍盒相交測試的代價，包圍盒移動、旋轉后包圍和更新需要的代價，以及物體發生變形后更新節點需要的代價。但是，還不能將式（1）作為評判包圍盒性能的優劣或選擇包圍盒的依據，還要把包圍盒的構造復雜度、占用存儲空間、包圍盒的緊密程度、算法的實時性與精確性需求等因素考慮進去才可以。充分考慮上述因素，表1給出了對不同包圍盒進行定量分析得到的結果，圖3給出了不同包圍盒相交測試的復雜度比較關系。

表1 典型包圍盒的性能比較

由表1可以看出，每一種包圍盒都存在著優勢和不足。因此，在實際應用中選擇算法時，一是要分析場景中物體的幾何特征、運動狀態、數量大小，有無變形體；二是要考慮算法實時性與精確性之間的平衡等諸多因素。

圖3 不同的包圍盒相交測試復雜度比較

由圖3可知，AABB 法緊密性差，但AABB 之間的相交測試簡單。AABB 法另一個突出優點是適應于變形對象的碰撞檢測。OBB 法緊密性好，但由于OBB的方向任意性，使得OBB間的相交測試復雜。凸包是包裹對象最緊密的包圍盒，但相交測試最復雜。K-DOPs其實是介于AABBs和凸包之間的包圍盒，它的突出特點是只要合理地選取平行平面對的個數和方向，就可以在碰撞檢測的簡單性和包裹物體的緊密性之間靈活取舍，即緊密性要優于AABBs，而相交測試的復雜度要小于OBBs。分析表明，兩個K-DOPs相交測試只需K次比較運算，而兩個OBB 的相交測試則需15 次比較運算、60次加法運算、81次乘法運算和24次絕對值運算［9］。顯然，K-DOPs相交測試的算法復雜度遠低于OBB。

目前，大部分碰撞檢測算法都是針對具體的應用場合設計的，沒有一種算法適用于所有的情形，且主要集中于在靜態環境下兩個包圍盒樹之間碰撞檢測效率的研究，而對于動態環境下復雜虛擬場景中多虛擬對象之間的碰撞檢測問題，高效率的檢測算法還不多。研究表明，復雜場景中對象雖然數量眾多，但在某一時刻真正發生碰撞的對象并不多。若在每一時刻都要對所有對象進行包圍盒樹之間的兩兩相交測試，會浪費許多檢測時間［10］。如果虛擬場景中有N個運動對象和M個靜止對象，則必須在每一時刻對（C2N＋NM）對包圍盒樹進行動態跟蹤和檢測。當N、M變得很大時，這一過程非常耗時，不能滿足實時交互的要求。針對復雜虛擬場景的特點，高效的碰撞檢測算法應該根據不同的碰撞概率采用不同的包圍盒；根據對碰撞檢測精度要求的不同采用不同的檢測深度，以提高整個動態系統的檢測效率。基本思想是把碰撞檢測分為兩個階段：預處理階段和動態檢測階段。在預處理階段為待檢測對象建立不同的包圍盒，最外層用簡單的包圍盒（如包圍球、AABB 等），內層用緊密性好的包圍盒（如OBB，K-DOP 等）。在動態檢測階段實時跟蹤對象之間的距離，由于外層的包圍盒具有緊密性差但相交測試簡單的特點，可以迅速地排除相距較遠不可能碰撞的對象。只有對那些外層包圍盒相交的對象，才進一步進行內層包圍盒之間的相交測試。為了對檢測精度進行控制，可根據不同對象碰撞的特點檢測到不同的深度，進而得出是否發生碰撞的結論，并引入相應的碰撞響應。

5．2 空間分割法

空間分割法是將整個虛擬空間劃分成等體積的規則單元格，以此將場景中的物體分割成更小的群組，并只對占據了同一單元格或相鄰單元格的幾何對象進行相交測試。一般來說，空間分割法在每次碰撞檢測時都需要確定每個模型占有的空間單元。如果場景中不可動的模型很多，可以預先劃分好空間單元格并確定每個模型占有的空間單元。當有模型運動時，只需要重新計算運動模型所占有的空間就可以了。所以該類方法通常適用于機床的加工仿真、飛行器避障飛行模擬等虛擬場合。空間分割法中采用層次樹的方法進一步提高算法的速度，比較典型的有八叉樹、BSP（binary space partitioning）樹等。

傳統的八叉樹有空間非均勻網格剖分算法和層級邊界盒算法。傳統算法適合于靜態場景；對于動態場景，采用較多的是基于面向對象的動態八叉樹結構，它是對原算法的改進。動態八叉樹的構造和碰撞檢測策略是將場景表示為等體積的規則單元格的組合。以立方體單元格為例，將單位立方體由動態八叉樹動態表示。當單位立方體檢測到碰撞，它將被分解成八個子立方體；否則不分解。以此循環遞歸，再通過預先設定閾值，控制分解的終止。

BSP樹包含的是平面的層級，其每一個平面都將一個區域的空間分割成兩個子空間。可將實體表面的一部分作為葉節點的平面。該平面的一個子空間代表實體的內部，另一個子空間代表實體的外部。BSP的碰撞檢測策略為：在兩個對象間找出分割平面以確定兩個對象是否相交，若存在分割平面，則無碰撞發生。為了提高效率，可先遍歷整個場景樹檢測分割平面是否與包圍盒相交；當有相交時再與包圍盒中對象的多邊形進行精確檢測。具有n個節點的二叉樹可在O（logn）次內完成搜索。

空間分割法適合于物體分布較為均勻的場景，在采用均勻網格分割時空間分割與對象無關，使得它特別適合變形體對象。變形體對象會在運動中發生形變，包圍盒法需要重新構建或者更新圍體樹，重新構建整個數據結構的時間耗費巨大；而均勻空間分割的關鍵問題是確定適當的單元格尺寸。適當選擇單元格尺寸，可使算法的計算能保持一定的準確度又不致代價太大。

與包圍盒法相比，空間分割法在計算效率上具有一定優勢，但當場景中的物體密集，分布不均時，單元格需要進一步分割，單元格之間的交測和存儲都需要較大空間，計算效率急劇下降。由于存儲量的敏感，使它不如包圍盒應用廣泛。

5．3 距離跟蹤法

距離跟蹤法的基本原理是通過尋找和跟蹤兩個多面體之間的最近點來計算它們之間的距離，當距離小于或等于零時，兩者就發生了碰撞。距離計算實質上就是判斷兩個模型中距離最近的兩點，然后計算它們之間的距離。距離計算算法分為兩類：靜態算法和動態算法。典型的靜態算法是Dobkin-Kirkpatrick算法。它在線性時間內對模型進行預處理，建立Dobkin-Kirkpatrick 層次數據結構，距離計算的復雜度就降低為O（lognlogm）［11］。

處理動態距離計算的一般方法是將時間離散化，根據模型當前的位置和方向計算距離。如果時間間隔足夠小，那么兩個模型的最近特征（頂點、邊或者面）可能就在上次最近特征的附近（假設是凸多面體）。利用這種運動連續性就可以用跟蹤模型的最近特征的方法取代靜態距離計算。

最早出現的跟蹤算法是Lin-Canny算法，它從上次得到的最近特征開始，沿多面體表面移動，直到找到最近特征。顯然這種算法依賴于相鄰兩次最近特征距離，即模型的相干性。如果相干性高，那么算法的效率就較高；反之，如果相干性越低，算法效率就越低。在最壞情況下，算法需要執行Ω（n2）步才能找到最近特征。這是第一類跟蹤算法：基于特征的遞增算法。

第二類跟蹤算法是基于層次數據結構的層次算法。其中提出一種層次算法（H-Walk），是建立在Dobkin-Kirkpatrick層次數據結構基礎上的，能夠根據需要在不同層次上尋找最近特征，這樣即使在相干性較低時也能保證算法的效率比較高。從上次得到的一對最近特征開始執行兩步搜索。首先在開始層次中移動固定的步長s，如果在這個過程中找不到最近特征，那么兩個模型中同時降低一層，直到找到某一層中的最近距離或者到達最低層；然后從最低層向上移動，當到達最上層時就得到兩個模型的最近特征。

6 結語

目前，基于圖形的碰撞檢測算法發展相對成熟，形成了一系列典型的算法，如層次包圍盒法、空間分解法和距離跟蹤法等。在保證算法較高精確度的前提下，進一步提高算法的實時性一直是研究者追求的目標。綜合運用層次包圍盒、空間分割和距離跟蹤算法，在保證碰撞檢測精確度的前提下，可以有效降低運算的復雜度，提高碰撞檢測的實時性，而且已在某型飛機彈射救生設備虛擬維修訓練系統的開發中得到應用，實踐證明是可行的。

［1］William R．Sherman，Alan B．Craig．虛擬現實系統—接口、應用與設計［M］．魏迎梅，楊冰，等譯．北京：電子工業出版社，2004：26-46．

［2］劉金林，曾凡明．艦船動力裝置虛擬維修訓練軟件的開發［J］．計算機仿真，2009，26（5）：324-327．

［3］屈宏偉，張琦，焦玉民．基于EON Studio的虛擬維修訓練系統研究［J］．制造業信息化，2009（6）：37-38．

［4］李芙玲，張瑾．碰撞檢測技術研究［J］．華北科技學院學報，2006，1（2）：71-73．

［5］潘振寬，崔樹娟．基于層次包圍盒的碰撞檢測方法［J］．青島大學學報，2005，18（1）：71-76．

［6］鄒益勝，丁國富．實時碰撞檢測算法綜述［J］．計算機應用研究，2008，25（1）：8-12．

［7］Christer Ericson．實時碰撞檢測算法技術［M］．劉天慧，譯．北京：清華大學出版社，2010．

［8］王曉榮，王盟，李春貴．基于AABB 包圍盒的碰撞檢測算法的研究［J］．計算機工程與科學，2010，32（4）：59-61．

［9］王偉，馬峻，劉偉．基于OBB 包圍盒的碰撞檢測算法與研究［J］．計算機仿真，2009，26（9）：180-183．

［10］孫曉光，王明強．碰撞檢測中的層次包圍盒算法研究［J］．現代制造工程，2009（4）：87-91．

［11］趙偉，譚睿璞，李勇．復雜虛擬環境下的實時碰撞檢測算法［J］．系統仿真學報，2010，22（1）：125-129．