摘要：介紹軟體碰撞檢測中主要的層次包圍盒方法、空間分割、隨機方法、距離場和圖像空問方法，從碰撞檢測的計算效率與準確性的角度，分析這些算法的優勢和不足，指出研究的關鍵點和難點。
1 引言
幾何模型間的碰撞檢測是織物仿真、計算機動畫、機器人、CAD/CAM 等多領域的關鍵問題之一?？焖俣鴾蚀_的碰撞檢測對提高與人交互的虛擬環境的真實感至關重要，尤其對于需要力觸覺感知的虛擬環境 。在虛擬環境仿真中，碰撞檢測往往是系統計算效率的瓶頸 。目前對剛體之間的碰撞檢測算法的研究已趨向成熟 ～ ，但對軟體碰撞檢測的算法研究較少，尤其是對準確性的考慮。對于虛擬外科手術訓練、織物仿真、計算機動畫、傷殘人力覺功能恢復等實用的虛擬環境中的交互對象，軟體對象比剛體對象更普遍。虛擬環境中的軟體對象不僅自身的復雜度高，而且會在外力的作用下發生形變，甚至發生拓撲結構的改變，這給碰撞檢測問題帶來了新的挑戰 。
2 碰撞檢測的實時性與準確性
就實時性而言，滿足虛擬環境中視覺再現的實時性要求，碰撞檢測的速度只需達到24Hz以上，而要滿足人對虛擬環境中力覺再現的真實感知，碰撞檢測的速度要達到300Hz以上才能維持交互系統的穩定性 。這使得其所受的實時性約束比純視覺虛擬環境的要嚴厲得多。就準確性而言，包括時間準確性和空間準確性，對于環境漫游系統，一般只要粗略地計算碰撞時刻和位置。而對于虛擬手術仿真、虛擬裝配等應用，就要求實時而準確地檢測碰撞發生的時刻和部位。對于準確性的評價方法現有文獻論述較少，目前見到的有采用檢測報告出錯率的方法 ，而對出錯的判定則與具體應用及要求相關。
虛擬現實系統對虛擬環境的實時性和準確性要求往往相互抵觸，真實性越高，要求模型越準確精細，相應的數據量越大，碰撞檢測的時間開銷也更大，甚至不能承受，目前許多實際的系統對碰撞響應處理只能采用近似方法 。因此碰撞檢測必須依據實際應用對實時性和真實性的具體要求，在準確性和實時性之間折衷。
3 軟體對象碰撞檢測的特點
3.1 計算效率高
對軟體對象的物理模型的力和變形等計算比剛體要復雜得多，這導致了對碰撞檢測算法的計算效率和準確性的高要求。
3.2 提供準確的碰撞信息
剛體物理模型為集中式參數，而軟體對象的物理模型往往具有分布式參數，軟體發生碰撞的部位不同，其隨后的碰撞響應不同。準確的碰撞時刻和位置信息是計算隨后的逼真的碰撞響應所必須的。
3.3 要求數據結構更新快
對于剛體碰撞檢測算法可在預處理階段建立對象的表示，例如層次包圍盒、距離場、或其它空間分割方式等空間數據結構，這樣做效率很高。但是，對于軟體對象，由于在交互中會產生變形，這些預處理的數據結構必須頻繁且快速地更新。
3.4 需考慮自身碰撞
與剛體間的碰撞檢測不同，為了逼真地仿真與軟體對象及它們之間的交互，必須考慮所有的接觸點并且包括自身碰撞。例如在織物仿真中，織物與織物間的碰撞經常發生。
4 軟體對象的碰撞檢測方法
軟體碰撞檢測方法按照所采用的方法其基本思想的不同，主要可分為層次包圍盒、空間分割、隨機方法、距離場和圖像空間方法。
4.1 層次包圍盒
層次包圍盒方法以三維形體的邊界表示法為基礎，其基本思想是用體積稍大且幾何特性簡單的包圍盒來近似地描述復雜的幾何對象，并通過構造樹狀層次結構逐漸逼近對象的幾何特性。進行重疊測試時只需對包圍盒重疊的部分進行進一步的相交測試，從而可大大減少參與相交測試的包圍盒的數目，提高碰撞檢測的效率。
層次包圍盒方法中每個節點的孩子數量的選擇也是一個關鍵點。對于剛體通常選擇二叉樹，但對于軟體對象，四叉或八又樹總體性能更好。因為更少的節點需要更新和總的更新代價降低了。另外，重疊測試的遞歸深度更低，所以在存儲空間上的需求更低。
層次包圍盒方法的效率和準確性關鍵在于包圍盒類型的選取。包圍盒類型有多種，例如球，方向包圍盒(OBB)，DOPs，Boxtrees，軸向包圍盒(AABB)，spherical shells和凸包，如圖1所示。
圖1 各種包圍盒類型
其中方向包圍盒OBB和k—DOP這兩種值得注意。OBB是比較常用的一種類型。在大多數情況下其總體性能要優于AABB和包圍球，但因對象變形后OBB樹的更新太慢不適合用于包含軟體對象的復雜環境中。k—DOP又稱為固定方向凸包FDH(在此我們也稱其為FDH)。在軟體對象環境中，FDH的使用最為常見。實際上，AABB是k—DOP中k=6時的一個特例。包含k個固定方向向量的兩個FDH間的相交測試最多只需k次比較運算，當對象發生形變時更新一個結點的FDH只需要k次比較運算，計算效率較高。同時，FDH在很大程度上改善了AABB的緊密性差的缺點，因此可提高碰撞檢測的準確性。
論文[6]通過一種自底向上的方法解決了軟體變形后的FDH樹的更新問題。但變形后包圍盒層次的調整更新是軟體環境碰撞檢測的瓶頸，如何提高FDH樹的更新速度仍有待進一步研究。
論文[13]中使用FDH了進行織物仿真，提出進一步加速FDH層次更新的方法，使碰撞檢測不再成為織物模擬系統的瓶頸。由于任何穿透都是可見的，織物的碰撞檢測的準確度要求非常高。就碰撞檢測和響應的準確度兩方面與采用Maya的比較結果看，此方法可正確地檢測所有的碰撞，而采用Maya時出現了穿透現象。
層次包圍盒方法應用非常廣泛，為復雜模型間準確的碰撞檢測提供一個快速有效的方法。
4.2 空間分割
基于空間分割的碰撞檢測基本思想是，對整個場景空間△，沿X、Y、z軸進行分割，形成一系列單元格。只對同處于一個單元格內對象之間進行碰撞檢測?？臻g分割可用于檢測碰撞和自身碰撞，對象拓撲可以改變，不限制以三角形作為對象的基本幾何元。空間分割方法中于用于表示3D空間數據結構選擇很重要，如圖2所示。
圖2 表示3D空間數據結構
這種數據結構在計算時間和存儲上必須是靈活的和有效率的。
在碰撞檢測應用中，常用的空間分割方法包括：均勻網格、八叉樹和BSP樹等。一般來說，BSP樹、八叉樹或kd一樹都是對象相關的。八叉樹的建立很耗時間，所以不適合在動態環境中實時碰撞檢測。而使用均勻網格的空間分割與對象無關，使得它特別適合軟體對象。均勻空間分割的關鍵問題是確定適當的單元格尺寸，適當選擇單元格尺寸大小，可使算法的計算能保持一定的準確度又不致開銷太大。
論文[3]提出一種基于均勻空間分割的快速多體碰撞檢測算法，同時依據對象的分布密度，提出了一個計算單元格尺寸的優化方法。與Cohen等人提出的I—COLLIDE算法的比較實驗表明，在均勻分布條件下，當物體數量較大時，該算法的效率高于I—COLLIDE算法，而且其效率基本不受物體運動相關性的影響。
論文[14]使用均勻網格的空間散列來檢測可變形四面體網格的碰撞和自身碰撞。提出使用哈希函數來映射3D網格到一個哈希表，從而實現快速的隱式的空間分割。該方法不僅節省存儲空間，而且很靈活。此外，還討論了最佳的單元大小。實驗表明最佳單元大小和單個物體幾何元的包圍盒一樣大，此時算法的計算效率最高。在20k個四面體的環境中可以實時地檢測碰撞和自身碰撞，算法給出的準確的位置信息可用于正確的碰撞響應。
其性能與對象的數量無關，只與對象幾何元的數量有關。所以該方法可用于多個對象的環境中。
當對象較少且均勻分布于空間時，空間分割方法效率較高；當對象較多且距離很近時，需進行單元格的進一步遞歸分割，并需要大量的單元格相交測試和存儲空間，效率明顯降低。空間分割由于存儲量大及靈活性不好，使用不如包圍盒層次法廣泛。
4.3 隨機方法
隨機方法按使用隨機方法的方式的不同可分為average—case方法和基于隨機選擇幾何元的碰撞檢測方法。
Average—case方法使用隨機方法來估計碰撞的可能性。其主要思想是考慮層次包圍盒的內部節點的多邊形集，遍歷時快速地計算一對包圍盒的多邊形問的碰撞可能性，然后把這個可能性作為優先權來指導遍歷那些有更高可能性的BV樹部分。
該方法可用于BVHs上，所以能擴展許多基于層次包圍盒的碰撞檢測方法。 首次提出把一般的層次碰撞檢測算法轉換為以可控制的方式來平衡計算效率和準確度的方法，并比較了擴展AABB樹的average—case方法和基于DOP樹的算法，結果顯示前者成倍地增加計算效率而不明顯降低準確性。
基于隨機選擇幾何元的碰撞檢測方法在碰撞對象內通過隨機取樣作為初始的潛在的交互區域的猜測。準確的碰撞區域通過使用時空一致性來縮小。該方法與任何層次無關，可直接用于幾何元對。如果相鄰兩次最近特征的距離，即模型的相干性高，那么算法的效率較高，相反相干性越低，算法效率就越低。Lin和Canny提出的解決方法 考慮了時空一致性。如果特征對在上一個時間步上足夠近，它很可能是下一個時間步上交互的特征對。J 利用了時間一致性，提出了一個分兩步來計算曲面結構的局部距離最小值的更新方法，把時間復雜度從O(mn)減/J,N O(m+n)，m和n是鄰近幾何元的數目。
雖然兩種隨機方法各不相同，但它們有共同的特點，即都可以平衡碰撞檢測的計算效率和準確性，能獲得有意義的接觸信息用于處理碰撞，但不能用于精確的碰撞檢測。對于時間關鍵的碰撞檢測，隨機方法具有較大的發展前景。
4.4 距離場
距離場定義了場中所有點到閉合曲面的最小距離。距離場D：R3一R定義了一個曲面作為零等值面。為了區分內部和外部，距離是有符號的。用距離場表示閉合曲面有不限制拓撲的優點。另外，碰撞檢測和響應所需要的距離和法線的估計非?？?，而且和對象的幾何復雜性無關。為了降低存儲需求或距離場生成時間，可以減少距離場的求解，降低準確度。所以距離場方法能平衡計算效率和準確度。表示距離場的數據結構有多種，例如均勻3D網格、八叉樹和BSP樹。
論文[17]提曲了剛體和軟體對象問的快速距離計算的問題。為了改善碰撞檢測的準確度，對可變形網格上每條邊的中心均進行了測試。實驗顯示，該方法能以交互的速度仿真織物，準確地檢測復雜非凸對象的碰撞。
距離場方法提供了很健壯的碰撞檢測，因為它們把空間嚴格地分成內部和外部。距離場方法用于在非交互應用中檢測碰撞和自身碰撞。盡管最近提出了高效率的計算距離場的算法，但由于變形幾何體距離場必須在運行時間內更新，所以相對于交互應用的要求，距離場方法仍不夠快。
4.5 圖像空間方法
基于圖像空間的碰撞檢測算法一般將三維幾何對象通過投影繪制到圖像平面上，降維得到一個二維的圖像空間；然后分析該空間中保存在各類緩存的信息；進而檢測出對象之間是否發生干涉 ，如圖3所示。
圖3 利用深度緩存降維
這是一類較新的碰撞檢測算法，由于它們不需要任何預處理，特別適合于包含動態軟體對象的環境。圖像空間方法中對象是離散表示的，它不提供準確的碰撞信息，碰撞檢測的準確度取決于離散誤差。準確度和計算效率可以通過改變繪制過程的分辨率在一定范圍內平衡。
論文[2]提出虛擬外科手術的圖像空間方法。該方法依靠圖形硬件來測試虛擬可變形器官和使用者控制的剛性工具間的穿透，可以實時檢測碰撞。在四個特殊的應用中，該方法比著名的OBB方法運行起來快約100倍。
在許多圖像空間碰撞方法中，Layered DepthImage LDI是基本的數據結構。LDI數據結構的本質是存儲每個像素的多個深度值。因而，LDI能用于近似表示對象的體積。_1 中的圖像空間方法可用于任意形狀軟體對象的碰撞檢測，但不檢測自身碰撞。提出了改進的算法而且考慮自身碰撞。_2。。給出了三種不同的產生LayeredDepth Image LDI的實現。其中兩種基于圖形硬件和一種軟件方法。結果顯示，在幾何復雜環境中圖形硬件加速了圖像空間碰撞檢測，但在小型環境的情況下基于CPU的實現提供了更靈活和更好的性能。
論文[18]提出的基于圖像空間的碰撞檢測算法主要采用對物體表面進行自動分解，將凸分解結果合理地組織成層次二叉樹結構，以及繪制加速等技術，能處理任意形狀的多面體。該算法在性能上有較大的提高。_2 給出了兩種有效的優化技術以提升算法效率。與常規圖象空間碰撞檢測算法相比，除了在性能上的優勢之外，其準確性不取決于繪制視窗的分辨率的大小，而與基于幾何的碰撞檢測算法精度一致；其通用性更好，可處理任意三角形網格物體而不限于凸體。但將算法應用于軟體對象間的實時碰撞檢測和進一步提高算法效率，仍有待進一步研究。
圖像空間方法的優點是不需要耗時的預處理，能檢測碰撞和自身碰撞，對象的拓撲可以改變，這些使得它特別適合于動態軟體對象。缺點是圖像空間方法不提供準確的碰撞信息，而這些信息在基于物理特性的仿真環境中用于進一步計算碰撞響應是必需的。
5 結束語
由于不同的方法輸入的數據不同，提供的碰撞信息不同，環境中的對象數量不同，目前無法對所有的方法進行完全一致的比較。軟體碰撞檢測的關鍵問題是在實時性和準確性之間確定最佳折衷。
軟體碰撞檢測同時要求較高的實時性和準確性，如何實現最佳折衷是難點所在。
參考文獻
[1]Jean—Christophe Lombardo，Marie—Paule Cani。FabriceNeyret.Real—time collision detection for virtual surgery[C].Proceedings of Computer Animation.Switzerland Ge.neva：IEEE，1999，82～9l
[2]June Gyu park，Ginter Niemeyer.Haptic Rendering withPredictive Representation of Local Geometry[C].Proceedirigsof 12th International Symposium on Haptie InterfacesFor VirtuM Environment and Teleoperator Systems.Chicago：IEEE Computer Society，2004，331—338
[3]李焱，盧曉軍，賀漢根.USSCD：一個基于均勻空間分割的快速碰撞檢測算法[J].中國圖象圖形學報，2003，8(12)：1444～1449
[4]Gottschalk S，Lin M C，Manocha D.OBBTree：A hierARChi—cal structure for rapid interference detection[C].Proceed.ings of ACM Siggraph’96.New Orleans：ACM ，1996，171～180
[5]Cohen J D，Lin M C，Manocha D，et a1.I—COLLIDE：Aninteractive and exact collision detection system for largescaleenvironments[C].Proceedings of ACM Interactive 3DGraphics Conference.Calif：ACM ，1995，1 89～196
[6]魏迎梅，王涌，吳泉源，等.剛體在軟體對象環境中的碰撞檢測的研究[J].計算機學報，2001，24(8)：802～808
[7] Cameron S A.Collision detection by four—Dimensional in.tersection testing[J].IEEE Trans Robotics and Automat，1990，291—302
[8]魏迎梅，王涌，吳泉源，等.虛擬手術仿真中碰撞檢測問題的研究[J].系統仿真學報，2000，12(5)：572～575
[9]Jan Klein，Gabriel Zachmann Time—Critical Collision DetectionUsing an Average—Case Approach[C].Proceedingsof the ACM symposium on Virtual reality software an dtechnology.Japan Osaka：ACM，2003，22—31
[10]Murat Cenk Cavusoglu，Frank Tendick.Muhirate simulationfor high fidelity haptic interaction with deformable objectsin virtual environments[C].Proceedings— IEEEInternational Conference on R0botics and Automation.SanFrancisco：Institute of Electrical and Electronics EngineersInc，2000，2458～2465.
[11]Jung Kim，Suvranu De，Mandayam A.Srinivasan.Computationallyeficient techniques for real time surgical simulationwith force foedback[C].Proceedings of 10th Symp.On Haptic Interfaces For Virtual Environment.＆ Teleop[11]erator Systems.Orlando：IEEE Computer Society，2002.51～57
[12]G.Zachmann，M.Teschner，S.Kimmerle，B.Heidelberger，L.Raghupathi，and A.Fuhrm ann.Real —TimeCollision Detection for Dynamic Virtual Environments[z]，IEEE Virtual Reality 2005，MARCh 12～16，2005，Bonn，Germany.Pages 1—32.
[13]Mezger，S.Kimmerle，O.Etzmub.HierARChical Techniquesin Collision Detection for Cloth Animation『J].Journal ofWSCG 11，2003，322—329
[14]Matthias Teschner，Bruno Heidelberger，Matthias Mtiller，et a1.Optimized spatial hashing for collision detection ofdeformable objects[C].Proceedings of Vision，Model—ing， Visualization VMV ’ 03. Germ any Munich ：VMV2003，2003.47 —54
[15]LIN M.C.，CANNY J.F.Efficient Collision Detection forAnimation[C].Proc.3rd Eurographics Workshop on Ani—mation and Simulation.Cambridge.1992.
[16][aks Raghupathi，Laurent Grisoni，Francois Faure，et a1.An intestine surgery simulator：Real—time collision pro—cessing and visualization[J].IEEE Transaction on Visual—ization and Computer Graphics，2004，708～7 1 8
[17]Amulph Fuhrmann，Gerrit Sobottka，Clemens Grob.dis—tan ce fields for rapid collision detection in physicallybased modeling[C].Proceedings of GraphiCon.Moscow，2003.58—65
[18]范昭煒，萬華根，高曙明.基于圖像的快速碰撞檢測算法[J].計算機輔助設計與圖形學學報，2002，14(9)：805—810.
[19]Bruno Heidelberger，Matthias Teschner，Markus Gross.Real — Time Volumetric Intersections of Deforming Ob—jects[C].Proceedings of Vision，Modeling，VisualizationVMV ’03.Germ any Munich：VMV2003。2003，461 468
[20]Bruno Heidelberger，Matthias Teschner Markus，Gross.detection of collision and self——collisions using image——space techniques[C].Proceedings of Winter School ofComputer Graphics 04.Bohemia：UNION Agency—Sci—ence Press，2004，145—152
[21]范昭煒，萬華根，高曙明.基于流的實時碰撞檢測算法[J].軟件學報，2004，15(10)：1505—1514
[22]魏迎梅.虛擬環境中碰撞檢測問題的研究[D].長沙：國防科學技術大學，2000，55—62
[23]Stephane Guy，Gilles Debunne.Monte—Carlo collisiondetection[R].http：//artis.imag.fr/Publications/2004/GD04/，2005— 11—30
