電子技術論文發(fā)表碰撞檢測技術研究綜述

發(fā)布時間：2014-09-25 14:43:16更新時間：2014-09-25 14:44:11 1

　　摘要：碰撞檢測在圖形學、仿真、動畫和虛擬現實等技術中得到廣泛的研究，這些研究具有十分重要的意義。文章對二維空間中多邊形等面模型間相交，以及三維空間中多面體等體模型間干涉的角度對碰撞檢測技術的研究和發(fā)展作了較為全面的論述，并對幾種常用的碰撞檢測算法進行了分析和比較，最后對碰撞檢測算法的發(fā)展方向提出了幾點建議。

　　關鍵詞： 電子技術論文發(fā)表,虛擬現實,碰撞檢測,層次包圍盒,干涉

　　A survey on collision detection technology

　　Feng Liying

　　(Information Technology Office of YanShan University， Qinhuangdao， Hebei 066004， China)

　　Abstract： The collision detection problem among objects is widely studied in graphics， simulation， animation and virtual reality technologies. A comprehensive introduction of study and development of the problem is given from the aspects of the intersection between face models in 2D， such as polygon， and the interference between body models in 3D， such as polyhedron. Some collision detection algorithms are briefly analyzed and compared. Some suggestions of development of collision detection algorithms are proposed.

　　Key words： virtual reality; collision detection; bounding volume hierarchies; interference

　　0 引言

　　數字化、信息化是當今國內外高科技發(fā)展的潮流和趨勢，隨著計算機軟硬件技術的快速發(fā)展，尤其是圖形處理器以及與之相關的三維游戲，虛擬仿真等技術的興起，碰撞檢測技術再次成為計算機仿真領域研究的熱點之一。在虛擬仿真系統(tǒng)中，如果物體間發(fā)生碰撞，系統(tǒng)必須實時而準確地檢測到這些碰撞并作出相應的碰撞響應[1]，否則物體間就會產生穿透現象，影響虛擬場景的真實性。以前在自動裝配規(guī)劃以及路徑規(guī)劃等領域中，為了檢測場景中的物體之間或零件之間是否發(fā)生碰撞，產生了許多碰撞檢測算法，而后有關專家在碰撞檢測的理論和應用方面做了一系列的實驗，并得到了許多有重要價值的研究結果。

　　近二三十年來，國內外研究人員在碰撞檢測領域中做了大量有意義的工作，經過細致的研究和實驗驗證之后，得到了許多實用的碰撞檢測算法，對虛擬現實技術的快速發(fā)展起到了積極的推動作用。本文將從二維平面和三維空間兩個方面對碰撞檢測技術進行較為詳盡的論述。

　　1 二維空間碰撞檢測問題

　　二維空間中的碰撞檢測幾乎是所有碰撞檢測算法不可回避的問題，它是指三角形、多邊形等面模型之間的求交問題，是三維空間中精確碰撞檢測的必經階段[2]。近幾十年來，許多專家學者對平面碰撞問題進行了深入的研究，并取得一些滿意的結果，提出了許多優(yōu)秀的算法。

　　Chin和Wang兩人研究了兩個多邊形的相交和最小距離問題。利用可視邊鏈和凸的頂點相對于其內部點的單調性，提出了判別凸n邊形和一個簡單非凸m邊形的相交問題的最優(yōu)算法[3]，并且研究了當兩個多邊形相交時，一個多邊形是否被另一個多邊形完全包含的問題，其時間復雜度都為O(m+n)。

　　曲吉林采用平面掃描算法，解決了平面內任意簡單多邊形平移時碰撞部位的判定問題[4]。平面內任意兩個互不相交的簡單多邊形，若其中一個多邊形沿某一方向平移時與另一個多邊形碰撞，采用平面掃描法，通過提取多邊形的單調鏈，給出了求其碰撞部位的算法。與現有的算法相比，降低了時間復雜性。

　　覃中平、張煥國研究了平面內兩個互不相交的凸多邊形，若其中一個凸多邊形沿某一方向與另一個凸多邊形相碰撞，采用折半搜索技術來確定凸多邊形相碰撞時兩者最初相碰撞的頂點和邊[5]，并且提出了時間復雜度為O(logm+logn)的優(yōu)秀算法。

　　汪嘉業(yè)利用單調折線研究了在一個多邊形的凸包和另一個多邊形不相交的條件下，確定兩個多邊形是否碰撞，并在碰撞時確定全部碰撞部位的問題[6]，提出了時間復雜度為O(m+n)的最優(yōu)算法，并且其算法還可推廣到確定包含有圓弧邊的多邊形之間的最初碰撞部位。

　　申靜波，唐國維等人提出了基于夾邊邊對的空間平面凸多邊形快速相交檢測算法[7]，并將算法的應用對象從三角形擴展到任意空間平面凸多邊形，直接進行多邊形間求交計算。該算法在確定所要檢測的兩個凸多邊形是否都存在相對于另一凸多邊形所在平面的夾邊邊對的基礎上，根據計算結果求取兩組邊對間對應夾邊的符號距離，以此判斷兩個多邊形是否相交。

　　2 三維空間中碰撞檢測問題

　　從空間域的角度來劃分，碰撞檢測算法大體可分為兩大類：一類是基于圖象空間的碰撞檢測算法;另一類是基于物體空間的碰撞檢測算法。這兩類算法的區(qū)別在于，前者是利用物體二維投影的圖象加上深度信息來進行相交分析，后者則是利用物體三維幾何特性進行求交計算。

　　2.1 基于圖像空間的碰撞檢測算法　　基于圖象空間的碰撞檢測算法的基本思想是利用圖形硬件將三維幾何對象投影到二維圖像平面，同時利用深度緩存進行深度測試，以判斷對象之間是否發(fā)生碰撞。但是基于圖象空間的碰撞檢測算法由于其檢測結果的不精確性和依賴硬件支持而一直發(fā)展較慢。近十幾年，隨著圖形硬件技術的飛速發(fā)展，圖形加速卡在性能不斷迅速提高的同時甚至出現了可編程的功能。在碰撞檢測的研究中，人們開始將三維幾何物體通過投影繪制到圖像平面上，得到一個二維的圖像空間，然后分析該空間中保存在各類緩存的信息，進而檢測出物體之間是否發(fā)生干涉[8]。這類算法優(yōu)勢在于能有效利用圖形硬件加速技術來減輕CPU的計算負擔，從而達到提高算法效率的目的。

　　Shinya和Forgue等[9]提出在繪制凸體的同時，保存視窗口中每個象素上物體的最大和最小深度序列，并將它們按大小順序排列，然后檢測物體在某一象素上的最大深度值是否與其最小深度值相鄰來判別相交情況。雖然圖形硬件可以支持物體最大/最小深度的計算，但該方法并不實用，因為它要求大量的內存來保存深度序列，而且從圖形硬件中讀取深度值本身就非常費時。

　　Gress等[10]利用GPU的可編程性，將碰撞檢測計算映射到GPU的頂點處理器和片段處理器中，通過實施繪制完成碰撞檢測計算，再通過遮擋查詢獲得碰撞檢測結果。該算法既保證了碰撞檢測的準確性，同時也充分利用了GPU強大的并行計算能力。

　　Govindaraju等[11]利用圖形硬件進行初步檢測階段，迅速剔除大規(guī)模場景中明顯不發(fā)生碰撞的物體;然后利用幾何結構下的快速相交檢測算法得到精確的碰撞檢測結果。該算法在處理虛擬場景中多物體間初期碰撞檢測方面能取得不錯的效果。

　　Heidelberger等[12]利用面向體表示的方法，提出了一種能夠處理可變形物體的碰撞檢測算法。該算法首先將兩物體的相交區(qū)域按層次深度分解為層次深度圖(layered depth image);然后通過圖形硬件繪制過程來判斷兩物體在層次深度圖的每個像素上是否有相交區(qū)間存在，從而確定物體是否發(fā)生碰撞。此算法不適合大規(guī)模物體間的碰撞檢測。

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

　　三維空間中碰撞檢測問題與二維空間碰撞檢測問題相比要復雜得多，目前，基于三維空間的碰撞檢測算法主要分為三類：距離跟蹤法、空間分解法(或空間剖分法)、層次包圍盒法。

　　2.2.1 距離跟蹤法

　　距離跟蹤法是通過尋找和跟蹤兩個多面體之間的最近點來計算它們之間的距離。當距離小于等于零時，發(fā)生碰撞;否則沒有發(fā)生碰撞。當物體的運動速度不快，相鄰幀間運動物體的位移變化很小時，可以利用幀間的連續(xù)性來增量式的計算物體間的距離。

　　最早出現的跟蹤算法是Lin-Canny算法[13]，它從上次得到的最近特征對開始，沿多面體的表面移動，直到找到新的最近特征。顯然，這種算法依賴于相鄰兩次最近特征的距離，即模型的相干性。如果相干性越高，那么算法的效率越高;相反相干性越低，算法效率就越低。

　　Enhanced GJK算法[14]是在GJK算法上改進而成。GJK算法是一個跟蹤計算兩凸多面體間的最短距離的算法，與Lin-Canny算法不同的是，GJK不是直接對兩凸多面體進行搜索和跟蹤，而是在他們的明氏距離多面體參數空間中搜索跟蹤執(zhí)行，它具有線性時間復雜度;Enhanced GJK算法將原GJK算法的時間復雜度改進為近乎常量級，達到與Lin-Canny算法的同等水平。Enhanced GJK采用了“爬山法”迭代算法求解，使時間復雜度大大降低，基本呈線性，大大減少了運算時間。

　　2.2.2 空間剖分法

　　空間剖分法是將整個虛擬空間劃分成相等體積的小單元格，只對占據同一單元格或相鄰單元格的幾何對象進行相交測試。適用于物體在空間中均勻分布的稀疏環(huán)境。

　　Ganter和Isarankura發(fā)展了單步檢測方法，提出了一種空間分割技術的方法[15]，這種空間分割技術將包含物體的空間劃分為一個個子空間，將所有的測試限制在兩個物體的重疊局部區(qū)域來進行，并且在重疊區(qū)域內的所有的子空間都按照最小、最大值來排序，從而進一步減少測試的時間。

　　Fuch和Kedem提出二叉空間分割BSP(Binary Space Partition)即空間任何一個平面，都可以將它所在的空間分割為兩個互不相交的子空間，空間中其他平面均可劃歸在某一子空間中。同樣，某一子空間中任一平面可以將該空間分為另外兩個互不相交的子空間。如此遞歸分割，將每次分割平面加入二叉樹節(jié)點，即可形成一棵描述場景層次結構的BSP樹。BSP樹碰撞檢測算法是在虛擬場景中的兩個對象間找出分割平面以判斷兩個對象是否相交。若兩個對象間存在分割平面，則沒有發(fā)生碰撞;否者，發(fā)生了碰撞。

　　2.2.3 層次包圍盒法

　　層次包圍盒算法是利用體積略大而幾何特性簡單的包圍盒來近似地描述相對復雜的虛擬對象，進而通過構造樹狀層次結構可以越來越逼近對象的幾何模型，直到幾乎完全獲得對象的幾何特性，從而只需對包圍盒重疊的部分進行進一步的相交測試。與一個物體相對應的層次結構的節(jié)點是空間上包圍該物體一部分幾何對象的幾何近似體(包圍盒)：層次結構的根節(jié)點包圍了整個物體，每個父節(jié)點包圍的幾何對象是它的所有子節(jié)點包圍的幾何對象之和，節(jié)點從上到下逐漸逼近它包圍的幾何對象。利用層次包圍盒方法進行碰撞檢測時，首先測試幾何對象的包圍盒是否相交，如果包圍盒不相交，則被包圍的對象就不相交;只有包圍盒相交時，才對其所包裹的幾何對象做進一步相交測試。

　　目前，比較典型的包圍盒類型有包圍球(Sphere)、軸向包圍盒AABB(Axis-Aligned Bounding Box)、方向包圍盒OBB(Oriented Bounding Box)以及離散有向多面體k-DOPs(Discrete Orientation Polytopes)等。　　包圍球(Sphere)[16]是簡單性好緊密性差的一類包圍盒，一個給定對象的包圍球被定義為包含該對象的最小的球體。計算給定對象的包圍球，首先需分別計算對象的基本幾何元素集合中所有元素的頂點的x、y、z坐標均值以確定包圍球的球心c，再由球心與三個最大值坐標所確定的點與點之間的距離計算半徑r。包圍球確定的區(qū)域為：R={(x，y，z)T|(x-cx)2+(y-cy)2+(z-cz)2　　軸向包圍盒AABB(axis-aligned bounding box)[17]是最早的一類包圍盒，在碰撞檢測的研究歷史中使用得最廣，一個物體的AABB被定義為包含該對象且邊平行于坐標軸的最小正六面體。對于給定的對象，它的AABB僅需六個標量描述，即組成物體基本幾何元素的頂點的x坐標、y坐標以及z坐標的最大值和最小值。AABB間的重疊測試比較簡單，兩個AABB重疊當且僅當它們在三個坐標軸上的投影區(qū)間均重疊，則它們是相交的。

　　OBB包圍盒層次(Oriented Bounding Box)是緊密型好、相交測試復雜的一類包圍盒[18]。一個給定對象的OBB被定義為包含該對象且相對于坐標軸方向任意的最小的正六面體。OBB最大特點是它的方向的任意性，這使得它可以根據被包圍對象的形狀特點盡可能緊密地包圍對象，但同時也使得它的相交測試變得復雜。OBB間的相交測試基于分離軸理論，若兩個OBB在一條軸線上(不一定是坐標軸)上的投影不重疊，則這條軸稱為分離軸，若一對OBB間存在一條分離軸，則可以判定這兩個OBB不相交，否則它們是相交的。

　　離散有向多面體k-DOPs(Discrete Orientation Polytopes)[19]是由紐約州立大學的James T、Klosowski等人提出的。一個對象的k-DOPs被定義為包含該對象且它的所有面的法向量都來自一個固定方向(k個向量)的集合的凸包，其中的方向向量為共線且方向相反的向量對。一個幾何對象的k-DOPs可以通過計算對象的頂點與固定方向集D中的各個方向的最大點積得到。D中有k/2對方向相反的向量對，k-DOPs在每對向量上的最大延伸確定了它在該對向量上的投影區(qū)間，一個k-DOPs包圍盒完全可由描述它在這些向量對上的k/2個投影區(qū)間所確定。因此，k-DOPs包圍盒間的相交測試可以通過投影區(qū)間的重疊測試來完成，只要兩個k-DOPs包圍盒在D中某一個方向對上的投影區(qū)間不重疊，就可以判定它們是不相交的;否則認為它們是相交的。

　　2.2.4 基于物體空間的碰撞檢測算法的分析比較

　　目前，在物體空間的碰撞檢測的算法中，距離跟蹤法依賴于相鄰兩次最近特征的距離，即模型的相干性。如果相干性越高，那么算法的效率越高;相反，相干性越低，算法效率就越低。這就使得算法具有了不穩(wěn)定性，其健壯性也受到影響�？臻g剖分法由于只適合于物體在空間均勻分布的稀疏環(huán)境，簡單地從大量物體中排除不相交的物體。但對于一般的環(huán)境，很難選擇一個最優(yōu)的剖分尺寸，若選擇不當，會導致空間耗費大，計算效率降低，因此空間剖分法有一定的局限性，是一種較少用到的方法。與上述兩種算法相比，層次包圍盒法是碰撞檢測算法中一種被廣泛使用的方法，在對物體進行碰撞檢測時，首先進行包圍盒間的相交測試，由于包圍盒間的求交過程比物體間求交過程簡單，所以可以盡早地排除大量不相交的物體，節(jié)省碰撞檢測的時間，提高碰撞檢測的效率。對研究人員來說，這種方法無疑是一種較好的選擇。但是，這種方法也有它的缺點，當被檢測的對象的變得越來越復雜時，構建包圍盒樹會占用大量存儲空間的同時，也會增加參與相交測試包圍盒的數量，因此會耗費大量存儲空間和相交測試的時間。

　　3 結束語

　　在虛擬環(huán)境中，碰撞問題一直是經典而關鍵的問題之一，因而得到很多專家學者的關注和研究，他們提出了各種各樣的方法來提高檢測算法的效率和魯棒性。作者認為在以后研究中可以從以下幾個方面入手。

　�、� 層次包圍盒法是一種被研究人員廣泛使用的算法，利用該方法對物體間進行相交測試時，在大多情況下都會立即產生無碰撞結論。因此節(jié)省包圍盒間相交測試的次數和相交測試的時間是提高檢測效率的有效途徑，所以研究者可以采用混合的包圍盒方法，即外層采用緊密性差、相交測試簡單的包圍盒，如包圍球，而里層采用緊密性好、相交測試復雜的包圍盒，如OBB，在解決實時碰撞檢測問題時不失為一個有效的方法。

　�、� 基于圖像的碰撞檢測算法屬于較新的一類算法。但曾經由于受到圖形硬件發(fā)展的限制，研究進展相對比較緩慢。隨著圖形硬件的發(fā)展才得以重新進入研究者的視野，國外有一批研究者正在進行該方面的研究，包含了碰撞檢測領域，國內在這方面的研究尚屬起步階段，成果較少。CPU與GPU間的負載平衡問題有待進一步研究，以提高算法效率。該類算法由于其本身的優(yōu)勢，特別是隨著圖形硬件的飛速發(fā)展，具有廣闊的研究前景和研究價值。

　�、� 利用多核CPU并行計算的功能來提高碰撞檢測的效率。隨著計算機硬件的不斷發(fā)展，雙核，四核，甚至多核CPU應運而生，通過把多核CPU并行計算，以及數據分塊思想應用到碰撞檢測算法之中，以靜態(tài)和動態(tài)任務分配策略相結合的方法來提高算法的并行度，從而達到提高碰撞檢測速度的目的。其核心問題是如何找出更好的動態(tài)任務分配策略以完全實現CPU間負載均衡，這是今后一個研究方向。

　　總之，碰撞檢測技術仍有許多方面需要進一步探討和研究，包括軟體模型、復雜模型之間的碰撞、框架與框架之間的空間一致性，以及接觸和干涉之間的區(qū)分等問題。因此，需要研究者不斷仔細鉆研，拓寬思路，設計出更高效的算法，才能滿足虛擬場景中大量復雜物體之間碰撞檢測實時性的要求。

　　參考文獻：　　[1] 何雪薇，龔光紅.虛擬人運動的動力學實現方法研究[C]. 2003全國

　　系統(tǒng)仿真年會論文集.西安：中國系統(tǒng)仿真學，2003：614-619

　　[2] 王志強，洪嘉振，楊輝.碰撞檢測問題研究綜述[J].軟件學報，1999.10

　　(5)：545-551

　　[3] F.Chin， C.A.Wang. Optimal Algorithms for the Intersection and

　　the Minimum Distance Problems between Planar Polygons. IEEE Transactions on Computers，1993.C-32(12)：1203-1207

　　[4] 曲吉林.確定任意簡單多邊形平移時碰撞部位的掃描算法[J].計算機

　　學報，2000.23(7)：692-1698

　　[5] 覃中平，張煥國.確定凸多邊形平移時最初碰撞部位的最優(yōu)算法[J].

　　計算機學報，1992.15(3)：171-177

　　[6] 汪嘉業(yè).平面上簡單多邊形平移時確定碰撞部位的最優(yōu)算法[J].計算