基于VR的碰撞檢測(cè)算法研究＊

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

1 引言

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

2 碰撞檢測(cè)的定義

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

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

3 碰撞檢測(cè)的影響因素

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

3．1 實(shí)時(shí)性

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

3．2 精確度

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

3．3 模型類(lèi)別

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

3．4 檢測(cè)類(lèi)別

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

3．5 場(chǎng)景特征

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

4 碰撞檢測(cè)算法分類(lèi)

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

圖1 碰撞檢測(cè)算法分類(lèi)

5 碰撞檢測(cè)算法研究

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

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

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

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

5．1 層次包圍盒法

圖2 包圍盒的類(lèi)型

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

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

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

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

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

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

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

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

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

5．2 空間分割法

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

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

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

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

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

5．3 距離跟蹤法

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

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

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

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

6 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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