碰撞檢測算法研究綜述

王嘉+李孔清

摘要：碰撞檢測算法作為虛擬現(xiàn)實技術(shù)的關(guān)鍵問題之一得到了廣泛的研究和發(fā)展，并且具有重大的意義和廣闊的前景。首先，從靜態(tài)和動態(tài)兩方面介紹了碰撞檢測算法的研究現(xiàn)狀，其中，動態(tài)碰撞檢測算法是目前研究的熱點；其次，介紹了動態(tài)碰撞檢測算法中的離散碰撞檢測算法和連續(xù)碰撞檢測算法，其中，離散碰撞檢測算法是目前研究的熱點；再次，介紹了離散碰撞檢測算法中的基于物體空間的碰撞檢測算法和基于圖像空間的碰撞檢測算法，其中，著重介紹了基于物體空間的碰撞檢測算法中的空間分割法和層次包圍盒法；最后，提出了一些熱門碰撞檢測算法中存在的問題及發(fā)展建議。

關(guān)鍵詞：碰撞檢測；靜態(tài)；動態(tài)；基于物體空間；基于圖像空間；空間分割；包圍盒

1背景

近十幾年來，虛擬現(xiàn)實技術(shù)得到了快速發(fā)展，也廣泛應(yīng)用在其他行業(yè)中，比如游戲、醫(yī)療、建筑等。其中，虛擬現(xiàn)實的關(guān)鍵問題之一是碰撞檢測，由于對場景的真實性和對交互的實時性要求越來越高，使得碰撞檢測算法成為計算機仿真領(lǐng)域研究的熱點。國內(nèi)外學者做了大量的研究和實驗，提出了許多可靠的技術(shù)來提高碰撞檢測的效率。

2碰撞檢測算法分類

碰撞檢測算法總的可以分為兩類，一類是靜態(tài)碰撞檢測算法，其針對的是靜止狀態(tài)下各物體是否發(fā)生碰撞，要求精度較高；一類是動態(tài)碰撞檢測算法，其針對的是位置變化狀態(tài)下各物體是否發(fā)生碰撞，如三維游戲中人在行走時是否會與墻壁、樹木等的碰撞。動態(tài)碰撞檢測算法又可分為離散碰撞檢測算法和連續(xù)碰撞檢測算法。其中，離散碰撞檢測算存在一些問題，比如在離散的時間間隔內(nèi)，兩個物體占有了同一空間等，但由于其檢測速度快，目前仍舊是研究的重點。連續(xù)碰撞檢測算法能夠精確的建模，較好的模擬出物體之間的碰撞，但其檢測速度較慢?；诳臻g的不同，離散碰撞檢測算法可分為基于物體空間的碰撞檢測算法和基于圖像空間的碰撞檢測算法?；谖矬w空間的碰撞檢測算法應(yīng)用較為廣泛，是目前研究的重難點，其又可分為層次包圍盒法和空間分割法。

3靜態(tài)碰撞檢測算法

靜態(tài)碰撞檢測算法是指在某一時刻或者在某一位置時物體之間是否發(fā)生碰撞，該算法對精度的要求較高且計算復(fù)雜性也較高。

Uchiki，Ohashi和Tokoro等人研究了一種在運動仿真中的碰撞檢測算法，該算法被稱作空間占有法，即利用兩個物體在虛擬運動時共同占有了同一空間來模擬碰撞。

李輝提出了平面內(nèi)互不相交的兩個凸多邊形P和Q，分別有n和m個頂點。在其中一個沿任意給定的方向移動時不與另一個相撞以及一個凸多邊形相對于另一個的所有可移動方向等兩個問題，并分別給出了凸多邊形可移動性的最優(yōu)算法：0（10g（n+m））和0（n+m）。

汪嘉業(yè)引研究了平面上頂點數(shù)分別為m，n的簡單多邊形平移時確定碰撞部位的最優(yōu)算法，該算法在兩個凸多邊形不相交的條件下，利用單調(diào)折線可確定二者是否相碰，并計算出其時間復(fù)雜度為O（m+n）。

曲吉林采用平面掃描法，通過提取兩個邊數(shù)分別為n和m的多邊形的單調(diào)鏈來確定任意多邊形平移時的碰撞部位，并計算出了時間復(fù)雜度為0“m+n）log（m+n））的算法。

申靜波和唐國維等人提出了基于夾邊邊對的空間平面凸多邊形快速相交檢測算法，該算法將應(yīng)用對象從三角形擴展到任意空間平面凸多邊形，直接進行多邊形間求交計算。

靜態(tài)碰撞檢測算法不需要預(yù)處理，對平面內(nèi)凸多邊形的研究較多，而對凹多邊形研究較少。筆者認為可通過將凹多邊形分解為多個凸多邊形來進行研究。

4動態(tài)碰撞檢測算法

4.1基于物體空間的碰撞檢測算法

基于物體空間的碰撞檢測算法利用物體三維幾何特征來展開計算，主要分為空間分割法和層次包圍盒法。

4.1.1空間分割法

空間分割法是指將整個虛擬空間劃分為一系列等體積單元格，只對處于同一單元格的物體進行檢測。當空間中有物體運動時，只需要重新計算物體占有的空間即可。常見的有均勻網(wǎng)格、八叉樹和BSP樹等。均勻網(wǎng)格的關(guān)鍵是選擇適當尺寸的網(wǎng)格，使得計算準確且效率較高，均勻網(wǎng)格適合軟體對象的碰撞檢測；八叉樹的關(guān)鍵是將空間分解為八個均等立方體，將檢測到碰撞的立方體再分解為八個立方體，直到檢測出碰撞部位為止，一般用于三維空間；BSP樹是將空間分割成兩個子空間，關(guān)鍵是在物體之間找出分割平面，若存在分割平面則兩物體不相交，可用在任意維度的場景中。

Moore和Wilhelms提出了兩種碰撞檢測方法。一種算法用來處理物體的三角面片化，且其適用于柔軟或剛性表面；另一種算法基于Cyrus-Beck裁剪算法，通過檢測凸多面體頂點是否互相包含來判斷碰撞與否，對于凹多面體可將其分解為凸多面體，其適用于剛性多面體。

Ganter和Isarankura提出了空間劃分法，該技術(shù)將包含一個給定物體的空間進行細分。使用這些分區(qū)，所有的測試可以被限制在兩個物體之間的重疊的局部區(qū)域，包含在重疊區(qū)域的子空間基于最小值和最大值來排序以進一步降低檢測時間。

劉雁翎和諸昌鈐一研究出了一種適合處理動態(tài)場景的交互樹，該算法首先利用物體之間的位置關(guān)系及從屬關(guān)系將物體組織在樹狀層級結(jié)構(gòu)中，之后在關(guān)系樹的基礎(chǔ)上對葉結(jié)點進行八叉樹剖分，最終生成交互樹。該算法既保持了八叉樹優(yōu)點又可以規(guī)律地剖分對象。

王國鋒等人利用HV分割算法將三維物體分割成更小的包圍盒，當兩個物體距離相當近時可以精確檢測出是否碰撞。由于使用HV分割后可以容易地實現(xiàn)包圍盒的重構(gòu)，因此也適用于旋轉(zhuǎn)的三維物體。

空間分割法適合于物體分布均勻且稀疏的場景。對于移動的物體，只需要重新計算物體所占的單元格即可。當物體較多且分布不均勻時需要將單元格分割成更小的單元格，大量的單元格之間的相交測試降低了碰撞檢測速度并且會占用大量的存儲空間，從而導致效率降低。

4.1.2層次包圍盒法

層次包圍盒法是指用體積略大且形狀相似的盒子來包圍物體。首先檢測兩包圍盒是否相交，相交后再詳細檢測包圍盒之間的重疊部分，從而判斷出物體之間是否碰撞。該算法可減少參與測試的包圍盒的數(shù)量，提高了效率。層次包圍盒法可分為AABB、包圍球、OBB和K-DOPs包圍盒。簡單性較好的是AABB和包圍球；緊密性較好的是OBB和K-DOPs；更新性較好的是包圍球和0BB；存儲量較少的是AABB和包圍球；適用于軟體對象的是AABB和K-DOPs。其中AABB是最早使用的包圍盒。

1）AABB

Smith等人提出了一種針對物體在運動過程中變形的算法，該算法基于AABB，在每一步都重新計算物體的包圍盒，且對凹凸物體均適用。

Gino提出了一個基于AABBs的復(fù)雜模型間進行剛性運動和變形的碰撞檢測方法。該方法通過遞歸細分，自上而下構(gòu)建包圍盒樹，加速了AABBs間的重疊測試，并且在模型變形時快速更新了AABB樹。

潘振寬和李建波通過對AABB包圍盒的壓縮優(yōu)化了AABB方法，提高了測試的速度。

方彬等人在初步檢測階段采用基于時間的AABB包圍盒和間隔減半法剔除場景中不相交的物體；在詳細檢測階段通過對物體建立AABB來精確相交區(qū)域。該方法較好地處理了高速運動物體的遺漏和刺穿問題。

2）包圍球

Palmer和Grimsdale首次提出了包圍球法，該算法使用球體來包圍物體，可快速定位潛在的碰撞區(qū)域。

rru等人提出了一種計算邊界球與邊界CSG基元間距離的算法，通過將整個空間分解為相對位置和考慮球面幾何特征，得到閉式距離公式。該算法對于復(fù)雜物體的實時碰撞有較好的效果。

Benitez等人用球面結(jié)構(gòu)來近似任意非凸物體從而來檢測物體間的碰撞。該算法在預(yù)處理階段是自動的，每級的球面樹可用于產(chǎn)生近似響應(yīng)且效率較高。

靳雁霞等人-提出了一種融合R-Sphere包圍球的變形體碰撞檢測算法，該算法將有公共頂點的三角片構(gòu)造成包圍球，首先利用包圍球快速剔除不相交的物體，之后利用粒子群算法將三維問題轉(zhuǎn)換成二維問題。該算法可有效解決變形體碰撞的問題。

3）OBB

Gottschalk等人提出了方向包圍盒樹，由于該包圍盒樹方向的任意性使得它可以緊密的包圍物體，該算法可高效地檢測出復(fù)雜模型間的碰撞，且對于一般的多邊形模型均適用。

章勤等人提出了一種基于OBB的改進算法，該算法利用幀之間的關(guān)聯(lián)性，對虛擬環(huán)境中已發(fā)生的碰撞進行緩沖，同時利用預(yù)測試的方法有效提高了碰撞檢測的效率。

王鵬等人通過在三角形網(wǎng)格中增加特征元素的信息（點、邊、面）形成特征描述三角形，再結(jié)合OBB法來進行碰撞檢測。該算法可有效減少基元測試的數(shù)量。

胡詠梅研究了一種AABB和OBB相結(jié)合的碰撞檢測算法，首先通過對象投影來快速剔除不相交的物體，接著用AABB構(gòu)建剩下的物體，初步判斷出可能相交的物體，最后用OBB來精確檢測。該算法實時性較好。

4）K-DOPs

Kay和Kajiya提出了層次包圍盒技術(shù)，該技術(shù)依據(jù)物體形狀選取若干組不同方向的平行平面對來包圍物體，該包圍盒能夠更緊密地包圍物體，使測試精度更高，這就是最早的K-DOPs的概念。

Klosowski等人首次提出了基于K-DOPs的快速碰撞檢測算法。K-DOPs被定義為包含該對象且它的所有面的法向量都取自一個固定的方向（k個向量）集合的凸包。該凸包既簡單又具有良好的緊密度。

Mezger等人針對紡織品的碰撞處理的精度要求特別嚴格這一情況，設(shè)計出特別的可變形表面，并采用K-DOPs包圍盒和四叉樹來優(yōu)化碰撞檢測，從而減少了內(nèi)存和成本。

李文娟等人研究了基于K-DOPs的改進的虛擬服裝仿真系統(tǒng)碰撞檢測算法，該算法通過引人表面曲率準則及法向量錐的概念，優(yōu)化了K-DOPs算法并使服裝仿真達到了逼真效果。

使用層次包圍盒法可以快速剔除場景中不相交的物體，因此在初步檢測階段采用該方法不失為一個較好的選擇，可節(jié)省檢測時間。但是該方法不適用于大規(guī)模復(fù)雜物體之間的相交檢測，因為會增加包圍盒的數(shù)量，使得相交測試次數(shù)增多，從而降低測試速度和占用大量存儲空間?？蓪⒖臻g分割法和層次包圍盒法結(jié)合起來使用，從而在滿足實時性的同時也降低時間復(fù)雜度。

4.2基于圖像空間的碰撞檢測算法

基于圖像空間的碰撞檢測算法利用圖形硬件來判斷兩物體的相交情況。主要包括兩種：第一種是將GPU視為與CPU一樣的處理器來加速檢測碰撞，利用緩沖區(qū)的顏色值和深度值來判斷物體之間的相交情況；第二種是將三維物體投影到二維空間中，通過分析保存的緩存信息來判斷物體之間的相交，雖然該轉(zhuǎn)化過程較復(fù)雜，但是計算過程簡單。

Shinya和Forgue提出了一種新的實時干涉檢測算法。該算法利用圖形硬件技術(shù)，在繪制凸體時按照視窗口上像素的大小深度序列來排序，之后檢測凸體在像素上的最大深度值與其最小深度值是否相鄰來判別相交與否。

Naga等研究了在大型環(huán)境中使用圖形硬件技術(shù)的復(fù)雜模型間的碰撞檢測。該算法首先利用可見性查詢判斷潛在的碰撞集，然后在CPU中進行精確的檢測。

Han-Young等人提出了一種新的基于圖像空間的實時碰撞檢測算法，該算法利用GPU計算潛在的碰撞集，利用CPU執(zhí)行標準的三角形相交測試。該算法可處理動態(tài)模型，且不需要任何預(yù)處理。

Kim等人提出了一種使用CPU和GPU的混合并行連續(xù)碰撞檢測算法，即HPCCD。該算法通過使用四個CPU核心和兩個GPU實現(xiàn)了超過一個數(shù)量級的性能改進，并且解決了由三角面片組成的柔性模型之間的碰撞檢測問題。

于海軍等人利用圖形處理器的加速功能研究了基于圖像空間的快速碰撞檢測算法。該算法首先利用凸塊層次二叉樹技術(shù)和方向包圍盒快速剔除場景中不相交的凸塊，然后利用recode算法精確計算。該算法可適用于復(fù)雜環(huán)境中。

基于圖像空間的碰撞檢測算法通過將GPU視為與CPU一樣的處理器來減輕CPU的計算負荷。該算法可處理不規(guī)則形狀的物體，并且在預(yù)檢測階段有較好的平穩(wěn)性，適用于復(fù)雜體和軟體對象的碰撞檢測。但是該方法也存在一些缺點：由于其不能提供準確的碰撞信息導致檢測結(jié)果不夠精確且不太適用于大規(guī)模的場景。

5結(jié)束語

基于物體空間的碰撞檢測算法是目前研究的熱點，也產(chǎn)生了許多有效的算法。空間分割法可在物體分布均勻的環(huán)境中剔除不相交的物體。但是針對物體分布不均勻的情況，如何優(yōu)化單元格的尺寸是一個仍需研究的問題，若分割不當會造成計算量過大，降低計算效率。筆者認為可將空間分割法與其他算法結(jié)合起來使用，利用空間分割法剔除場景中分布均勻的物體，再結(jié)合其他算法精確檢測非均勻物體之間的相交情況。

層次包圍盒法由于構(gòu)造簡單、檢測快速、效率較高，使其成為應(yīng)用比較廣泛的一類算法。不同的包圍盒的算法效率和適用條件不同，需要根據(jù)對象選擇適合的包圍盒。層次包圍盒法也存在一些缺點：當場景中對象較多且較復(fù)雜時，會延長相交測試的時間和占用大量的存儲空間。筆者認為可采用混合包圍盒，即在初步檢測階段選用相交測試簡單、快速、緊密性差的包圍盒來剔除場景中不相交的物體，如包圍球和AABB等；在精確檢測階段選用相交測試復(fù)雜、緊密性好的包圍盒來進一步判斷相交情況，如0BB和K-DOPs等。也可采用與其他算法的混合使用來提高效率。

基于圖形空間的碰撞檢測算法是目前較新的算法，該類算法不需要預(yù)處理，適用于初步檢測階段。囿于圖形硬件的發(fā)展，該類算法目前還面臨著一些問題。例如：如何減輕CPU的負擔來有效平衡CPU和GPU之間的負載；如何在檢測精度和繪制速度中尋求平衡，以達到既提高檢測精度又保持較快的繪制速度；如何開展在大規(guī)模場景中的應(yīng)用等問題。筆者認為在今后的工作中應(yīng)重點研究該類算法與基于物體空間的碰撞檢測算法的結(jié)合使用。相信隨著計算機技術(shù)日新月異，該類算法會得到飛速發(fā)展。