（海軍航空工程學(xué)院青島校區(qū) 青島 266041）

1 引言

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

2 碰撞檢測的定義

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

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

3 碰撞檢測的影響因素

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

3．1 實(shí)時性

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

3．2 精確度

虛擬環(huán)境中碰撞檢測的采用近似檢測還是精確檢測取決于具體的應(yīng)用要求。如對于環(huán)境漫游系統(tǒng)，只需近似模擬碰撞情況，并不要求碰撞檢測達(dá)到100%精確，而對于如虛擬手術(shù)仿真等情況，則要求必須進(jìn)行精確檢測。

3．3 模型類別

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

3．4 檢測類別

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

3．5 場景特征

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

4 碰撞檢測算法分類

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

圖1 碰撞檢測算法分類

5 碰撞檢測算法研究

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

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

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

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

5．1 層次包圍盒法

圖2 包圍盒的類型

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

通常，可以通過代價函數(shù)（Ttotal）來對不同包圍盒的優(yōu)劣進(jìn)行初步分析：

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

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

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

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

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

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

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

5．2 空間分割法

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

傳統(tǒng)的八叉樹有空間非均勻網(wǎng)格剖分算法和層級邊界盒算法。傳統(tǒng)算法適合于靜態(tài)場景；對于動態(tài)場景，采用較多的是基于面向?qū)ο蟮膭討B(tài)八叉樹結(jié)構(gòu)，它是對原算法的改進(jìn)。動態(tài)八叉樹的構(gòu)造和碰撞檢測策略是將場景表示為等體積的規(guī)則單元格的組合。以立方體單元格為例，將單位立方體由動態(tài)八叉樹動態(tài)表示。當(dāng)單位立方體檢測到碰撞，它將被分解成八個子立方體；否則不分解。以此循環(huán)遞歸，再通過預(yù)先設(shè)定閾值，控制分解的終止。

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

空間分割法適合于物體分布較為均勻的場景，在采用均勻網(wǎng)格分割時空間分割與對象無關(guān)，使得它特別適合變形體對象。變形體對象會在運(yùn)動中發(fā)生形變，包圍盒法需要重新構(gòu)建或者更新圍體樹，重新構(gòu)建整個數(shù)據(jù)結(jié)構(gòu)的時間耗費(fèi)巨大；而均勻空間分割的關(guān)鍵問題是確定適當(dāng)?shù)膯卧癯叽?。適當(dāng)選擇單元格尺寸，可使算法的計算能保持一定的準(zhǔn)確度又不致代價太大。

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

5．3 距離跟蹤法

距離跟蹤法的基本原理是通過尋找和跟蹤兩個多面體之間的最近點(diǎn)來計算它們之間的距離，當(dāng)距離小于或等于零時，兩者就發(fā)生了碰撞。距離計算實(shí)質(zhì)上就是判斷兩個模型中距離最近的兩點(diǎn)，然后計算它們之間的距離。距離計算算法分為兩類：靜態(tài)算法和動態(tài)算法。典型的靜態(tài)算法是Dobkin-Kirkpatrick算法。它在線性時間內(nèi)對模型進(jìn)行預(yù)處理，建立Dobkin-Kirkpatrick 層次數(shù)據(jù)結(jié)構(gòu)，距離計算的復(fù)雜度就降低為O（lognlogm）［11］。

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

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

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

6 結(jié)語

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

［1］William R．Sherman，Alan B．Craig．虛擬現(xiàn)實(shí)系統(tǒng)—接口、應(yīng)用與設(shè)計［M］．魏迎梅，楊冰，等譯．北京：電子工業(yè)出版社，2004：26-46．

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

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

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

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

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

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

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

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

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

［11］趙偉，譚睿璞，李勇．復(fù)雜虛擬環(huán)境下的實(shí)時碰撞檢測算法［J］．系統(tǒng)仿真學(xué)報，2010，22（1）：125-129．