實時碰撞檢測算法綜述

摘要：介紹了常用的基于圖形的實時碰撞檢測算法適用場合及實施策略，重點從構造難度、數據存儲量、相交測試復雜度、緊密性、物體旋轉時包圍盒更新計算量、變形體碰撞適用度等方面分析了基于包圍盒的碰撞檢測算法，并進行了橫向比較；介紹了基于圖像的碰撞檢測方法的特點、實施策略及研究現狀。最后總結提出了算法研究中存在的問題及新的發展方向。

關鍵詞：碰撞檢測；綜述；基于圖形；基于圖像；包圍盒

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)01－0008－05



碰撞檢測用于判定一對或多對物體在給定時間域內的同一時刻是否占有相同區域。它是機器人運動規劃、計算機仿真、虛擬現實、游戲等領域不可回避的問題之一。在機器人研究中，機器人與障礙物間的碰撞檢測是機器人運動規劃和避免碰撞的基礎；在計算機仿真和游戲中，對象必須能夠針對碰撞檢測的結果如實作出合理的響應，反映出真實動態效果等[1]。

隨著計算機軟硬件及網絡等技術的日益成熟，尤其是計算機動畫仿真、虛擬現實等技術的快速發展，人們迫切希望能對現實世界進行真實模擬。其中急需的關鍵技術之一即是實時碰撞檢測[2]。目前，三維幾何模型越來越復雜，虛擬環境的場景規模越來越大；同時人們對交互實時性、場景真實性的要求也越來越高。嚴格的實時性和真實性要求在向研究者們提出巨大挑戰的同時，也令實時碰撞檢測再度成為研究熱點。

1碰撞檢測算法的分類

近二十多年來，研究人員在碰撞檢測領域中做了相當多有意義的工作，提出了一些較成熟的算法，并開發了相應的軟件包。研究人員根據不同的研究對象，采用了不同的研究方法，也由此提出多種多樣的碰撞檢測算法。從總體上將這些算法歸為兩類：a）靜態干涉檢測算法。主要用于檢測靜止狀態中各物體之間是否發生干涉的算法，如機械零件裝配過程中的干涉檢查等。這類算法對實時性要求不高，但對精度要求較高。b）動態碰撞檢測算法。針對的是場景中物體的相對位置不斷隨時間變化的情況，如機械零件的加工過程以及機械系統的運動仿真等。動態碰撞檢測算法又分為離散碰撞檢測算法和連續碰撞檢測算法。

從本質上說，離散碰撞檢測算法在每一時間離散點上可以通過類似于靜態干涉檢測算法的方法來實現，但它更注重算法效率。雖然這類算法自身還存在一些問題，如檢測中的刺穿現象和遺漏情況等，但由于其檢測過程的實時性能較好地迎合多數應用的需求，目前仍是碰撞檢測算法研究的重點和熱點[3， 4]。此外，通過采用自適應步長技術[5， 6]等可以在一定程度上減少離散碰撞檢測算法的不足。 

連續碰撞檢測算法[7]的研究一般涉及到四維時空問題或結構空間精確的建模。這類算法能較好地解決離散碰撞檢測算法存在的問題，但通常計算速度較慢，需要作進一步的研究才能適用于大規模場景中的實時碰撞檢測。研究人員在實時碰撞檢測方面展開了一系列研究，取得了一些成果。 

目前，大部分實時性好的碰撞檢測算法都屬于離散碰撞檢測算法。縱觀這些算法，大致可分為基于圖形和基于圖像的碰撞檢測算法。這兩類算法的主要區別在于是利用物體三維幾何特性進行求交計算，還是利用物體二維投影的圖像及深度信息來進行相交分析。其中在基于圖形的碰撞檢測上，研究人員已經做了大量的工作，形成了層次包圍盒法和空間分割法等成熟算法[3， 4， 8~10]。基于圖像的碰撞檢測算法能有效利用圖形硬件的繪制加速功能來提高碰撞檢測算法的效率，特別是近幾年圖形硬件技術的飛速發展，圖形硬件在性能不斷提高的同時還具備了可編程的功能，使得基于圖像的碰撞檢測算法進入了一個新的發展階段[11]。 

2實時碰撞檢測算法分析

2．1基于圖形的實時碰撞檢測算法 

基于圖形的實時碰撞檢測算法主要分為層次包圍盒法(hierarchical bounding bolumes)和空間分割法(space decomposition)兩類。這兩類算法都使用了層次結構模型。其目標都是盡可能地減少需進行相交測試的幾何對象的數目以提高算法的實時性。空間分割法由于存儲量大、靈活性差， 通常適用于稀疏環境中分布比較均勻的幾何對象間的碰撞檢測;層次包圍盒法則應用得更為廣泛，適用于復雜環境中的碰撞檢測[12]。

2．1．1層次包圍盒法

層次包圍盒方法的核心思想是用體積略大而幾何特性簡單的包圍盒來近似地描述復雜的幾何對象，從而只需對包圍盒重疊的對象進行進一步的相交測試。此外通過構造樹狀層次結構可以越來越逼近對象的幾何模型，直到幾乎完全獲得對象的幾何特性。典型的層次結構樹主要包括AABB（ aligned axis bounding box）層次樹、包圍球(spheres)層次樹、OBB（oriented bounding box）層次樹和kDOPs（discrete orientation polytope）層次樹等。其他還包括混合層次包圍體樹[13]等。

1）AABB[1，3，4，9，12，14]AABB在碰撞檢測的研究歷史中使用得最久最廣。一個給定對象的AABB 被定義為包含該對象且邊平行于坐標軸的最小的長方體。基于AABB 的碰撞檢測系統有SOLID等。

a)構造難度低。只需分別計算物體中各個元素頂點的x、y和z 坐標的最大值和最小值即可。計算一個物體的AABB只需6m次比較運算。其中m為物體頂點數。

b）存儲量較小。存儲一物體的AABB只需6 個浮點數。 

c)相交測試復雜度低。兩個AABB相交定義為當且僅當它們在三個坐標軸上的投影區間均重疊。AABB間的相交測試最多只需要6次比較運算。

d）緊密性較差。尤其是對于沿斜對角方向放置的瘦長形對象，用AABB 將留下很大的邊角空隙，從而導致大量冗余的包圍盒相交測試。

e)物體旋轉時包圍盒更新計算量中等。當對象發生旋轉后，根據定義AABB的六個最大最小值的組合，可以得到AABB的八個頂點；對這八個頂點進行相應的旋轉，并根據旋轉后的頂點計算新的AABB。

f）變形體碰撞適用度大。當物體變形時，更新包圍盒有一定的計算量，可通過自底向上由子節點的AABB合成父節點的AABB以減小計算量，只需要6次比較運算即完成一個節點的更新，效率較高。

2）包圍球[1，3，4，9，12，14]一個給定對象的包圍球被定義為包含該對象的最小的球體。相對于AABB 而言，在大多數情況下，包圍球無論是緊密性還是簡單性都有所不如。因此它是使用得較少的一種包圍盒。

a)構造難度低。先分別計算物體中各個元素頂點的x、y和z坐標均值，以確定包圍球的球心c；再由球心與三個最大值坐標所確定的點間的距離計算半徑r。構造時計算時間略多于AABB。

b)存儲量小。存儲一個包圍球只需兩個浮點數。

c)相交測試復雜度低。對于兩個包圍球(c1 ，r1)和(c2 ，r2)，如果球心距離小于兩球半徑之和，即|c1-c2|

d）緊密性差。除了在三個坐標軸上分布得比較均勻的幾何體外，幾乎都會留下很大的空隙。因此通常需要花費大量的預處理時間以構造一個好的層次結構逼近對象。

e)物體旋轉時包圍盒更新計算量無。這是包圍球比較顯著的一個特性。對于進行頻繁旋轉運動的剛體，采用包圍球可能得到較好的結果。

f)變形體碰撞適用度中等。當對象發生變形時，很難從子節點的包圍球合成父節點的包圍球，只能重新計算。

3）OBB [1，3，4，9，12，14~16]一個給定對象的OBB被定義為包含該對象且相對于坐標軸方向任意的最小的長方體。OBB間相交測試的代價較大，但其緊密性好，參與相交測試的包圍盒數目和基本幾何元素的數目可以成倍地減少。在大多數情況下其總體性能要優于AABB和包圍球。基于OBB的碰撞檢測系統有RAPID[16]等。

a)構造難度較大。構造給定物體的OBB的計算相對復雜。其關鍵是找出最佳方向，并確定該方向上包圍對象的包圍盒的最小尺寸。假設給定物體中的基本幾何元素為三角形，第i個三角形的頂點用xi，yi和zi表示，則可計算出物體的均值μ和協方差矩陣C。協方差矩陣C的三個特征向量是正交的，規范化后可作為一個基底，用于確定OBB的方向。分別計算物體所包含的各個元素的頂點在該基底的三個軸上投影的最大值和最小值，以確定該OBB的大小。

b)存儲量中。存儲一個OBB 需要15個浮點數。包括表示方向的3個基底向量共9個浮點數和表示范圍的6個浮點數。

c)相交測試復雜度較大。OBB間的相交測試基于分離軸理論。若兩個OBB在一條軸線 (不一定是坐標軸)上的投影不重疊，則這條軸稱為分離軸；若一對OBB間存在一條分離軸，則可以判定這兩個OBB不相交。對任何兩個不相交的凸三維多面體，其分離軸要么與任一多面體的某一個面垂直，要么同時垂直于每個多面體的某一條邊。因此，對于一對OBB，需測試15條可能是分離軸的軸(每個OBB 的3個面方向再加上每個OBB的3個邊方向的兩兩組合)，只要找到一條這樣的分離軸，就可以判定這兩個OBB是不相交的。兩個OBB的相交測試最多需要15次比較運算、60次加減運算、81次乘法運算和24 次絕對值運算。

d)緊密性好。因為其方向的任意性特點，可根據被包圍對象的形狀盡可能緊密地包圍對象。

e）物體旋轉時包圍盒更新計算量小。當幾何對象發生旋轉運動后，只要對OBB的基底進行同樣的旋轉即可。因此，較適用于剛體間的碰撞檢測。

f)變形體碰撞適用度小。迄今為止，還沒有一種有效解決對象變形后OBB樹更新問題的方法，而重新計算每個節點的OBB的代價又太大，故OBB不適用于軟體對象環境中的碰撞檢測。

4）kDOPs[1，3，4，9，12，14，17]一個對象的kDOPs被定義為包含該對象，且它的所有面的法向量均來自一個固定的方向(k個向量)集合的凸包。其中的方向向量為共線且方向相反的向量對，術語上稱為FDH(fixed direction hull)。其最簡單的特例是固定方向集中包含坐標軸方向，這時便成為AABB。因此它也可以看做是AABB的擴展。另外，當k值取無限大時，它即成為對象的凸包。因此它不但繼承了凸包緊密性好的優點，同時也繼承了AABB簡單性好的優點。基于kDOPs的碰撞檢測系統有QuickCD等。

a)構造難度中等。一個幾何對象的FDH可以由它在固定方向集D中的各個方向向量上的最大延伸所確定，即通過計算對象的頂點與固定方向集中的各個方向的最大點積得到。這樣計算有n個頂點的對象FDH可以在O(kn)時間內完成(k為固定方向集中的向量個數)。

b)存儲量隨k值變化而變。存一個kDOPs需要k個值，每個面一個。

c)相交測試復雜度較低。FDH間的相交測試與AABB相似，可以依次對它們在固定方向集D中的k/2個方向軸上的范圍區間進行重疊測試。如果找到了一對不重疊的區間，則可判斷這兩個FDH包圍盒不相交。盡管這一判斷方法不是很精確，但它不會影響檢測結果。從檢測速度方面考慮，這種方法還是可行的。因此，兩個FDH的相交測試最多只需k次比較運算，盡管它比AABB間的相交測試(6次比較)略微復雜，但與OBB相比較，其復雜度已經大大降低了。

d）緊密性好。它繼承了凸包緊密性好的特點，通過調整固定方向集合的大小和取值，可以在緊密性與簡單性之間取得平衡。k的取值越大，緊密性越好，但計算復雜度也越大。因此如何取得合適的k值還有待進一步的研究。

e）物體旋轉時包圍盒更新計算量較大。當對象發生旋轉時，如果僅簡單地對FDH進行同樣的旋轉，得到的將是基于另一個固定方向集的FDH，這就違背了用FDH做包圍盒的初衷。兩個來自不同方向集合的FDH間的相交測試不能使用區間重疊測試方法，其代價要比來自同一個方向集的FDH的相交測試代價大得多。與AABB一樣，它需要計算旋轉后的FDH，但計算一個FDH的頂點坐標的代價仍然是很大的。可以通過引入線性規劃的一些基本原理進行優化，這樣無須計算FDH頂點而得到旋轉后的FDH在方向集D中各個方向向量上的最大延伸，其中大部分計算可以提前完成。更新一個節點上的FDH只需要3k次乘法運算[14]。

f）變形體碰撞適用度較大。當對象發生變形時，可以重新計算FDH 樹中發生變形的葉節點上的FDH，然后嚴格按自底向上的順序，由子節點的FDH合成父節點的FDH。更新一個節點的FDH只需要k次比較運算。所以基于FDH的碰撞檢測不但可以應用于剛體對象間的碰撞檢測，還可應用于剛體與軟體間的碰撞檢測，適用于包含軟體對象的復雜環境模型中。但軟體對象的FDH更新有待進一步優化。

圖1所示為幾種典型包圍盒在二維平面上的構造方式；表1是一般情況下典型包圍盒在各個測試項上的比較結果。

2．1．2空間分割法

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

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

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

2．2基于圖像的碰撞檢測算法 

基于圖像的碰撞檢測算法一般利用圖形硬件對物體的二維圖像采樣和相應的深度信息來判別兩物體之間的相交情況。圖形硬件有時也稱為圖形處理單元（graphics process unit，GPU）。這類算法主要有四點優勢：

a）能有效利用圖形硬件加速技術來減輕CPU的計算負荷，從而達到提高算法效率的目的；

b）算法本身對于場景的復雜性不敏感，適合于復雜體間的碰撞檢測；

c）對同一復雜度的場景而言，碰撞檢測時間變化不大，具有較高的平穩性，有利于預測碰撞檢測過程；

d）圖形硬件技術發展快速，算法有良好的發展前景。

基于圖像的碰撞檢測算法由于其檢測結果的不精確性和依賴硬件支持而一直發展較慢，而且對其在大規模場景中的應用有待進一步研究。近年來，隨著圖形硬件計算性能的迅速提高，基于圖像的碰撞檢測算法進入了一個新的快速發展階段。

Shinya[23]和Rossignac[24]等人開創性地提出了圖形硬件輔助碰撞檢測方法。Shinya等人提出在繪制凸體的同時，保存視窗中每個像素上物體的最大和最小深度序列，并將它們按大小順序排列；然后檢測物體在某一像素上的最大深度值是否與其最小深度值相鄰來判別相交情況。圖形硬件可以支持物體最大最小深度的計算。但該方法并不實用，因為它需要大量的內存來保存深度序列，而且從圖形硬件中讀取深度值本身就非常費時。Rossignac等人利用深度緩存和模板緩存來輔助進行機械零件之間的相交檢測。他們通過移動圖形硬件的裁剪平面，判斷平面上的每個像素是否同時在兩個實體之內確定物體是否相交。

Myszkowski等人[25]利用模板緩存（stencil buffer）檢測每幀的變化狀況，提出了一種有效的改進算法。他們將深度緩存和模板緩存結合在一起進行相交檢測：用模板緩存值來保存視窗中每個像素上所代表的射線進入一物體前，進入和離開其他物體的次數，并讀取模板緩存中的值來判斷兩物體是否相交。該算法有較大的實用意義，但僅能處理兩個凸體之間的碰撞檢測問題。

Baciu等人[26]進一步利用深度緩存和模板緩存的組合功能，提高圖像空間碰撞檢測算法的效率，并使算法可在常規圖形工作站甚至是普通個人臺式電腦上運行。他們先用幾何方法確定兩物體包圍盒的相交區域；然后在相交區域中利用圖形硬件的加速繪制進行相交檢測。他們分析了兩物體的各種相交情況，并將這些相交情況按深度值位置進行了分類，同時用模板緩存值來表示這些分類，然后通過檢查模板緩存值來判別兩物體之間是否發生碰撞。算法的主要缺點是僅能處理凸多面體或由凸多面體組成的多面體。

Hoff[27]和Kim[28]等人將圖像空間碰撞檢測算法和物體空間碰撞檢測算法結合起來，先利用基于物體空間的方法快速查找出兩物體對潛在的相交區域；再利用基于圖像的方法快速求出兩個物體的分離距離或刺穿深度。通過這種負載平衡策略，在CPU與GPU間進行合理調配來保證算法的整體效率。

Govindaraju等人[29]利用圖形硬件快速剔除大規模場景中明顯不發生相交的物體，即進行初步檢測階段的物體剔除；然后利用幾何的快速相交檢測算法得到碰撞檢測的結果。該算法在多物體碰撞檢測初期階段利用圖形硬件加速檢測過程。一般的基于圖像的物體對碰撞檢測在檢測階段才利用圖形硬件加速計算。

Heidelberger等人[30]提出了一種面向體表示、能處理可變形物體的碰撞檢測算法。該算法首先將兩物體的相交區域按層次深度分解為層次深度圖(layered depth image)；然后通過圖形硬件繪制過程來判斷兩物體在層次深度圖的每個像素上是否有相交區間存在，從而確定物體是否發生碰撞。

范昭煒等人[2]采用Baciu等人提出的基于圖像的碰撞檢測算法，并對物體表面進行自動凸分解，將凸分解結果合理地組織成層次二叉樹結構，以及采用基于三角形帶的繪制加速技術，有效提高了算法的效率，可以處理非凸體。采用類似方法的還有哈爾濱工程學院的霍濱焱[31]。宋永軍等人[32]利用凸包計算共享軟件Qhull（http：//www.geom.umn.edu/software/qhull）先對剛體進行凸分解；再利用深度緩存和模板緩存的組合功能對剛體的碰撞檢測作了研究。

3結束語

基于圖形的碰撞檢測算法發展相對成熟，形成了一系列典型的算法，如層次包圍盒法和空間分解法等，但算法本身受場景復雜度的影響較大。在保證算法精確度高的前提下，進一步提高算法的實時性一直是研究者追求的目標。所以算法的研究一方面要優化其本身的構造；另一方面要充分利用如圖形硬件GPU加速處理技術和并行計算方法的優勢。目前基于圖形硬件加速計算正在開創一個新的時代。國外有一批研究者正在進行該方面的研究，包含了碰撞檢測領域；國內在這方面的研究尚屬起步階段，成果較少。

基于圖像的碰撞檢測算法屬于一類較新的算法。雖起步較早，但由于受到圖形硬件發展的限制，曾在很長的一段時間被邊緣化。20世紀90年代隨著圖形硬件的發展才得以重新進入研究者的視野，但研究進展相對比較緩慢，檢測精度一直是限制其發展的重要原因之一。提高分辨率可在一定程度上解決這個問題，但會影響繪制速度；算法對于非凸體及大規模場景的適用性研究有待進一步開展；CPU與GPU間的負載平衡問題有待進一步研究，以提高算法效率。該類算法由于其本身的優勢，特別是隨著圖形硬件的飛速發展，具有廣闊的研究前景和研究價值。

參考文獻：

［1］潘振寬，崔樹娟，張繼萍，等.基于層次包圍盒的碰撞檢測方法[J].青島大學學報：自然科學版，2005，18(1):71 76.

[2]范昭煒，萬華根，高曙明.基于圖像的快速碰撞檢測算法[J].計算機輔助設計與圖形學學報，2002，14(9):805－810.

[3]LIN M C，GOTTSCHALK S.Collision detection between geometric models:a survey[C]//Proc of IMA Conference on Mathematics of Surfaces.1998:37－56.

[4]JIMNEZ P，THOMAS F，TORRAS C.3D collision detection: a survey[J].Computers and Graphics，2001，25(2):269－285.

[5]DINGLIANA J，O’SULLIVAN C.Graceful degradation of collision handling in physically based animation[J].Computer Graphics Forum，2000，19(3):239－247.

[6]O’SULLIVAN C，DINGLIANA J.Real time collision detection and response using sphere trees[C]//Proc of Spring Conference on Computer Graphics.Bratislava:[s.n.]，1999:83－92.

[7]REDON S，KHEDDAR A，COQUILLART S.CONTACT:arbitrary in between motions for continuous collision detection[C]//Proc of IEEE ROMAN’.2001.

[8]王志強，洪嘉振，楊輝.碰撞檢測問題研究綜述[J].軟件學報，1999，10(5):545－551.

[9]陳學文，丑武勝，劉靜華，等.基于包圍盒的碰撞檢測算法研究[J].計算機工程與應用，2005，41(5):46－50.

[10]李芙玲，張瑾.碰撞檢測技術研究[J].華北科技學院學報，2006，1(2):71 73.

[11]LIN M C，MANOCHA D.Interactive geometric computations using graphics hardware[C]//Proc of SIGGRAPH’02.2002.

[12]范昭煒.實時碰撞檢測技術研究[D].杭州：浙江大學，2003.

[13]蔡文軍，陳虎.基于混合模型的碰撞檢測優化算法研究[J].計算機與現代化，2006(7): 49－52.

[14]魏迎梅.虛擬環境中碰撞檢測問題的研究[D].長沙：國防科學技術大學，2000.

[15]丁志磊.基于OBB包圍盒的快速碰撞檢測[D].蘭州：蘭州理工大學，2006.

[16]GOTTSCHALK S.Collision queries using oriented bounding boxes[D].[S.l.]:The University of North Carolina at Chapel Hill， 2000.

[17]KLOSOWSKI J，HELD M，MITCHELL J S B，et al.Efficient collision detection using bounding volume hierarchies of kDOPs[J].IEEE Trans on Visualization and Computer Graphics，1998，4(1): 21－37.

[18]劉雁翎，諸昌鈐.一種適合處理動態場景的交互[J].計算機應用， 2001，21(11):7 9.

[19]李焱，盧曉軍，賀漢根.USSCD:一個基于均勻空間分割的快速碰撞檢測算法[J].中國圖象圖形學報，2003，8(12):1444 1449.

[20]王國鋒，王太勇，秦旭達，等.基于HV分割的精確碰撞檢測及其應用[J].天津大學學報，2004，37(6):485－488.

[21]涂超，顏輝武.碰撞檢測技術研究[J].計算機工程與應用，2001，37（19）:142 143，174.

[22]羅亞波，陳定方，肖田元.虛擬加工環境中的工件動態建模方法研究[J].武漢大學學報：信息科學版， 2003，28(2):238－241.

[23]SHINYA M，FORGUE M.Interference detection through rasterization[J].Journal of Visualization and Computer Animation，1991，4（2）:131 134.

[24]ROSSIGNAC J，MEGAHED A，SCHNEIDER B O.Interactive inspection of solids:cross section and interferences [J].Computer Gra phics，1992，26(2):353－360.

[25]MYSZKOWSKI K，OKUNEV O G，KUNII T L.Fast collision detection between computer solids using rasterizing graphics hardware[J].The Visual Computer，1995，11(9):497－511.

[26]BACIU G，WONG S K W，SUN H.RECODE:an image based collision detection algorithm[J].Journal of Visualization and Computer Animation，1999，10(4): 181 192.

[27]HOFF I K E，ZAFERAKIS A，LIN M，et al.Fast 3D geometric proxi mity queries between rigid deformable models using graphics hardware acceleration，TR02 004[R] .[S.l.]:University of North Carolina at Chapel Hill，2002.

[28]KIM Y J，LIN M，MANOCHA D.Fast penetration depth estimation using rasterization hardware and hierarchical refinement[C]//Proc of Symposium on Computational Geometry.2003:386－387.

[29]GOVINDARAJU N K，LIN M C，MANOCHA D.Quick CULLIDE:fast interand intra object collision culling using graphics hardware[C]//Proc ofIEEE Virtual Reality.2005:59－66.

[30]HEIDELBERGER B，TESCHNER M，GROSS M.Volumetric collision detection for derformable objects，TR395[R].Zurich， Switzerland:Computer Science Department ETH，2003.

[31]霍濱焱.基于圖像空間的碰撞檢測算法[D].哈爾濱:哈爾濱工程大學，2005.

[32]宋永軍，蘇鴻根.一種基于圖像的剛體碰撞檢測[J].計算機應用與軟件，2004，21(5):82－84.

[33] YU Chun yan，YE Dong yi，WU Ming hui，et al.A new horizonal collision detection scheme for avatar with avatar in collaborative virtual environment[C]//Proc of the 4th International Conference on Machine Learning and Cybernetics.2005:4961－4966.

[34]RAABE A，BARTYZEL B，ANLAUF J K，et al.Hardware accelerated collision detection:an architecture and simulation results[C]//Proc ofDesign Automation and Test (DATE).2005:130 135.

[35]VASSILEV T，SPANLANG B，CHRYSANTHOU Y.Fast cloth animation on walking avatars[J].Computer Graphics Forum，2001，20(3):260－267.

[36]FNFZIG C，ULLRICH T，FELLNER D W.Hierarchical spherical distance fields for collision detection[J].IEEE Computer Graphics and Applications，2006，1(2):64 74.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”