摘要：介紹軟體碰撞檢測中要緊的層次包圍盒方法、空間分割、隨機方法、距離場和圖像空問方法，從碰撞檢測的計算功效與準(zhǔn)確性的角度，分析這些算法的優(yōu)勢和不足，指出研究的關(guān)鍵點和難點。
1 引言
幾何模型間的碰撞檢測是織物仿真、計算機動畫、機器人、CAD/CAM 等多土地的關(guān)鍵問題之一？焖俣鴾(zhǔn)確的碰撞檢測對提高與人交互的虛擬環(huán)境的真實感至關(guān)重要，特別關(guān)于需要力觸覺感知的虛擬環(huán)境 。在虛擬環(huán)境仿真中，碰撞檢測往往是系統(tǒng)計算功效的瓶頸 。目前對剛體之間的碰撞檢測算法的研究已趨向成熟 ～ ，但對軟體碰撞檢測的算法研究較少，特別是對準(zhǔn)確性的考慮。關(guān)于虛擬外科手術(shù)訓(xùn)練、織物仿真、計算機動畫、傷殘人力覺功能恢復(fù)等實用的虛擬環(huán)境中的交互對象，軟體對象比剛體對象更普遍。虛擬環(huán)境中的軟體對象不僅自身的龐大度高，同時會在外力的作用下產(chǎn)生形變，甚至產(chǎn)生拓?fù)浣Y(jié)構(gòu)的轉(zhuǎn)變，這給碰撞檢測問題帶來了新的挑戰(zhàn) 。
2 碰撞檢測的實時性與準(zhǔn)確性
就實時性而言，滿足虛擬環(huán)境中視覺再現(xiàn)的實時性要求，碰撞檢測的速度只需達(dá)成24Hz以上，而要滿足人對虛擬環(huán)境中力覺再現(xiàn)的真實感知，碰撞檢測的速度要達(dá)成300Hz以上才能堅持交互系統(tǒng)的穩(wěn)定性 。這使得其所受的實時性約束比純視覺虛擬環(huán)境的要嚴(yán)厲得多。就準(zhǔn)確性而言，包括時間準(zhǔn)確性和空間準(zhǔn)確性，關(guān)于環(huán)境漫游系統(tǒng)，一般只要粗略地計算碰撞時刻和位置。而關(guān)于虛擬手術(shù)仿真、虛擬裝配等應(yīng)用，就要務(wù)實時而準(zhǔn)確地檢測碰撞產(chǎn)生的時刻和部位。關(guān)于準(zhǔn)確性的評價方法現(xiàn)有文獻論述較少，目前見到的有采用檢測報告鑄錯率的方法 ，而對鑄錯的判定則與的確應(yīng)用及要求相關(guān)。
虛擬現(xiàn)實系統(tǒng)對虛擬環(huán)境的實時性和準(zhǔn)確性要求往往相互抵牾，真實性越高，要求模型越準(zhǔn)確精細(xì)，相應(yīng)的數(shù)據(jù)量越大，碰撞檢測的時間開銷也更大，甚至不能承擔(dān)，目前許多實際的系統(tǒng)對碰撞響應(yīng)處置只能采用相近方法 。因此碰撞檢測必須依據(jù)實際應(yīng)用對實時性和真實性的的確要求，在準(zhǔn)確性和實時性之間折衷。
3 軟體對象碰撞檢測的特點
3.1 計算功效高
對軟體對象的物理模型的力和變形等計算比剛體要複雜得多，這導(dǎo)致了對碰撞檢測算法的計算功效和準(zhǔn)確性的高要求。
3.2 提供準(zhǔn)確的碰撞信息
剛體物理模型爲(wèi)集中式參數(shù)，而軟體對象的物理模型往往具有分布式參數(shù)，軟體發(fā)生碰撞的部位不同，其隨後的碰撞響應(yīng)不同。準(zhǔn)確的碰撞時刻和位置信息是計算隨後的逼確實碰撞響應(yīng)所必須的。
3.3 要求數(shù)據(jù)結(jié)構(gòu)更新快
對于剛體碰撞檢測算法可在預(yù)處理階段建立對象的表達(dá)，例如層次包圍盒、距離場、或其它空間分割方法等空間數(shù)據(jù)結(jié)構(gòu)，這樣做功效很高。但是，對于軟體對象，由于在交互中會産生變形，這些預(yù)處理的數(shù)據(jù)結(jié)構(gòu)必須頻繁且快速地更新。
3.4 需考慮自身碰撞
與剛體間的碰撞檢測不同，爲(wèi)了逼真地仿真與軟體對象及它們之間的交互，必須考慮所有的接觸點並且包括自身碰撞。例如在織物仿真中，織物與織物間的碰撞經(jīng)常發(fā)生。
4 軟體對象的碰撞檢測方法
軟體碰撞檢測方法比照所采用的方法其基本思想的不同，要緊可分爲(wèi)層次包圍盒、空間分割、隨機方法、距離場和圖像空間方法。
4.1 層次包圍盒
層次包圍盒方法以三維形體的邊界表達(dá)法爲(wèi)基礎(chǔ)，其基本思想是用體積稍大且?guī)缀翁卣骱唵蔚陌鼑衼硐嘟孛枋鲅}雜的幾何對象，並通過構(gòu)造樹狀層次結(jié)構(gòu)逐漸靠近對象的幾何特征。進行重疊測試時只需對包圍盒重疊的部分進行進一步的相交測試，從而可大大減少參與相交測試的包圍盒的數(shù)目，提高碰撞檢測的功效。
層次包圍盒方法中每個節(jié)點的小孩數(shù)量的選擇也是一個關(guān)鍵點。對于剛體通常選擇二叉樹，但對于軟體對象，四叉或八又樹總體性能更好。因爲(wèi)更少的節(jié)點需要更新和總的更新代價降低了。另外，重疊測試的遞歸深度更低，因此在存儲空間上的需求更低。
層次包圍盒方法的功效和準(zhǔn)確性關(guān)鍵在于包圍盒類型的選取。包圍盒類型有多種，例如球，方向包圍盒(OBB)，DOPs，Boxtrees，軸向包圍盒(AABB)，spherical shells和凸包，如圖1所示。
圖1 各種包圍盒類型
其中方向包圍盒OBB和k—DOP這兩種值得注重。OBB是比較常用的一種類型。在大多數(shù)情況下其總體性能要優(yōu)于AABB和包圍球，但因?qū)ο笞冃吾酧BB樹的更新太慢不適合用于包含軟體對象的複雜環(huán)境中。k—DOP又稱爲(wèi)固定方向凸包FDH(在此我們在線也稱其爲(wèi)FDH)。在軟體對象環(huán)境中，F(xiàn)DH的使用最爲(wèi)常見。實際上，AABB是k—DOP中k=6時的一個特例。包含k個固定方向向量的兩個FDH間的相交測試最多只需k次比較運算，當(dāng)對象發(fā)生形變時更新一個結(jié)點的FDH只需要k次比較運算，計算功效較高。同時，F(xiàn)DH在很大程度上改善了AABB的緊密性差的缺點，因此可提高碰撞檢測的準(zhǔn)確性。
論文[6]通過一種自底向上的方法解決了軟體變形後的FDH樹的更新問題。但變形後包圍盒層次的調(diào)整更新是軟體環(huán)境碰撞檢測的瓶頸，如何提高FDH樹的更新速度仍有待進一步研究。
論文[13]中使用FDH了進行織物仿真，提出進一步加速FDH層次更新的方法，使碰撞檢測不再成爲(wèi)織物模擬系統(tǒng)的瓶頸。由于任何穿透基本上可見的，織物的碰撞檢測的準(zhǔn)確度要求非常高。就碰撞檢測和響應(yīng)的準(zhǔn)確度兩方面與采用Maya的比較結(jié)果看，此方法可正確地檢測所有的碰撞，而采用Maya時出現(xiàn)了穿透現(xiàn)象。
層次包圍盒方法應(yīng)用非常廣泛，爲(wèi)複雜模型間準(zhǔn)確的碰撞檢測提供一個快速有效的方法。
4.2 空間分割
基于空間分割的碰撞檢測基本思想是，對整個場景空間△，沿X、Y、z軸進行分割，形成一系列單元格。只對同處于一個單元格內(nèi)對象之間進行碰撞檢測？臻g分割可用于檢測碰撞和自身碰撞，對象拓?fù)淇梢愿淖，不限制以三角形作?wèi)對象的基本幾何元？臻g分割方法中于用于表達(dá)3D空間數(shù)據(jù)結(jié)構(gòu)選擇很重要，如圖2所示。
圖2 表達(dá)3D空間數(shù)據(jù)結(jié)構(gòu)
這種數(shù)據(jù)結(jié)構(gòu)在計算時間和存儲上必須是靈活的和有功效的。
在碰撞檢測應(yīng)用中，常用的空間分割方法包括：均勻網(wǎng)格、八叉樹和BSP樹等。一般來說，BSP樹、八叉樹或kd一樹基本上對象相關(guān)的。八叉樹的建立很耗時間，因此不適合在動態(tài)環(huán)境中實時碰撞檢測。而使用均勻網(wǎng)格的空間分割與對象無關(guān)，使得它特別適合軟體對象。均勻空間分割的關(guān)鍵問題是確定適當(dāng)?shù)膯卧癯叽纾m當(dāng)選擇單元格尺寸大小，可使算法的計算能保全一定的準(zhǔn)確度又不致開銷太大。
論文[3]提出一種基于均勻空間分割的快速多體碰撞檢測算法，同時依據(jù)對象的分布密度，提出了一個計算單元格尺寸的優(yōu)化方法。與Cohen等人提出的I—COLLIDE算法的比較實驗表明，在均勻分布條件下，當(dāng)物體數(shù)量較大時，該算法的功效高于I—COLLIDE算法，同時其功效基本不受物體運動相關(guān)性的影響。
論文[14]使用均勻網(wǎng)格的空間散列來檢測可變形四面體網(wǎng)格的碰撞和自身碰撞。提出使用哈希函數(shù)來映射3D網(wǎng)格到一個哈希表，從而實現(xiàn)快速的隱式的空間分割。該方法不僅節(jié)省存儲空間，同時很靈活。另外，還討論了最佳的單元大小。實驗表明最佳單元大小和單個物體幾何元的包圍盒一樣大，此時算法的計算功效最高。在20k個四面體的環(huán)境中可以實時地檢測碰撞和自身碰撞，算法給出的準(zhǔn)確的位置信息可用于正確的碰撞響應(yīng)。
其性能與對象的數(shù)量無關(guān)，只與對象幾何元的數(shù)量有關(guān)。因此該方法可用于多個對象的環(huán)境中。
當(dāng)對象較少且均勻分布于空間時，空間分割方法功效較高；當(dāng)對象較多且距離很近時，需進行單元格的進一步遞歸分割，並需要大批的單元格相交測試和存儲空間，功效明顯降低。空間分割由于存儲量大及靈活性不行，使用不如包圍盒層次法廣泛。
4.3 隨機方法
隨機方法按使用隨機方法的方法的不同可分爲(wèi)average—case方法和基于隨機選擇幾何元的碰撞檢測方法。
Average—case方法使用隨機方法來估計碰撞的也許性。其要緊思想是考慮層次包圍盒的內(nèi)部節(jié)點的多邊形集，遍曆時快速地計算一對包圍盒的多邊形問的碰撞也許性，然後把這個也許性作爲(wèi)優(yōu)先權(quán)來指導(dǎo)遍曆那些有更高也許性的BV樹部分。
該方法可用于BVHs上，因此能擴展許多基于層次包圍盒的碰撞檢測方法。 首次提出把一般的層次碰撞檢測算法轉(zhuǎn)換為以可控制的方法來平穩(wěn)計算功效和準(zhǔn)確度的方法，并比較了擴展AABB樹的average—case方法和基于DOP樹的算法，結(jié)果顯示前者成倍地增加計算功效而不明顯降低準(zhǔn)確性。
基于隨機選擇幾何元的碰撞檢測方法在碰撞對象內(nèi)通過隨機取樣作為初始的潛在的交互區(qū)域的猜測。準(zhǔn)確的碰撞區(qū)域通過使用時空一致性來縮小。該方法與任何層次無關(guān)，可直接用于幾何元對。如果相鄰兩次最近特征的距離，即模型的相干性高，那么算法的功效較高，相反相干性越低，算法功效就越低。Lin和Canny提出的解決方法 考慮了時空一致性。如果特征對在上一個時間步上足夠近，它很也許是下一個時間步上交互的特征對。J 使用了時間一致性，提出了一個分兩步來計算曲面結(jié)構(gòu)的局部距離最小值的更新方法，把時間龐大度從O(mn)減/J,N O(m+n)，m和n是鄰近幾何元的數(shù)目。
雖然兩種隨機方法各不雷同，但它們有協(xié)同的特點，即都可以平穩(wěn)碰撞檢測的計算功效和準(zhǔn)確性，能獲得有意義的接觸信息用于處理碰撞，但不能用于精確的碰撞檢測。對于時間關(guān)鍵的碰撞檢測，隨機方法具有較大的發(fā)展前景。
4.4 距離場
距離場定義了場中所有點到閉合曲面的最小距離。距離場D：R3一R定義了一個曲面作爲(wèi)零等值面。爲(wèi)了區(qū)分內(nèi)部和外部，距離是有符號的。用距離場表達(dá)閉合曲面有不限制拓?fù)涞膬?yōu)點。另外，碰撞檢測和響應(yīng)所需要的距離和法線的估計非？，同時和對象的幾何複雜性無關(guān)。爲(wèi)了降低存儲需求或距離場生成時間，可以減少距離場的求解，降低準(zhǔn)確度。因此距離場方法能平穩(wěn)計算功效和準(zhǔn)確度。表達(dá)距離場的數(shù)據(jù)結(jié)構(gòu)有多種，例如均勻3D網(wǎng)格、八叉樹和BSP樹。
論文[17]提曲了剛體和軟體對象問的快速距離計算的問題。爲(wèi)了改善碰撞檢測的準(zhǔn)確度，對可變形網(wǎng)格上每條邊的中心均進行了測試。實驗顯示，該方法能以交互的速度仿真織物，準(zhǔn)確地檢測複雜非凸對象的碰撞。
距離場方法提供了很健壯的碰撞檢測，因爲(wèi)它們把空間嚴(yán)格地分成內(nèi)部和外部。距離場方法用于在非交互應(yīng)用中檢測碰撞和自身碰撞。盡管最近提出了高功效的計算距離場的算法，但由于變形幾何體距離場必須在運行時間內(nèi)更新，因此相對于交互應(yīng)用的要求，距離場方法仍不夠快。
4.5 圖像空間方法
基于圖像空間的碰撞檢測算法一般將三維幾何對象通過投影繪制到圖像平面上，降維獲得一個二維的圖像空間；接著分析該空間中保存在各類緩存的信息；進而檢測出對象之間是否產(chǎn)生干涉 ，如圖3所示。
圖3 使用深度緩存降維
這是一類較新的碰撞檢測算法，由于它們不需要任何預(yù)處理，特別適合于包含動態(tài)軟體對象的環(huán)境。圖像空間方法中對象是離散表達(dá)的，它不提供準(zhǔn)確的碰撞信息，碰撞檢測的準(zhǔn)確度取決于離散誤差。準(zhǔn)確度和計算功效可以通過改變繪制過程的辨別率在一定範(fàn)圍內(nèi)平穩(wěn)。
論文[2]提出虛擬外科手術(shù)的圖像空間方法。該方法依靠圖形硬件來測試虛擬可變形器官和使用者控制的剛性工具間的穿透，可以實時檢測碰撞。在四個特殊的應(yīng)用中，該方法比著名的OBB方法運行起來快約100倍。
在許多圖像空間碰撞方法中，Layered DepthImage LDI是基本的數(shù)據(jù)結(jié)構(gòu)。LDI數(shù)據(jù)結(jié)構(gòu)的實質(zhì)是存儲每個像素的多個深度值。因而，LDI能用于相近表達(dá)對象的體積。_1 中的圖像空間方法可用于任意外形軟體對象的碰撞檢測，但不檢測自身碰撞。提出了改進的算法同時考慮自身碰撞。_2。。給出了三種不同的產(chǎn)生LayeredDepth Image LDI的實現(xiàn)。其中兩種基于圖形硬件和一種軟件方法。結(jié)果顯示，在幾何龐大環(huán)境中圖形硬件加速了圖像空間碰撞檢測，但在小型環(huán)境的情況下基于CPU的實現(xiàn)提供了更靈活和更好的性能。
論文[18]提出的基于圖像空間的碰撞檢測算法要緊采用對物體外表進行自動分解，將凸分解結(jié)果有理地組織成層次二叉樹結(jié)構(gòu)，以及繪制加速等技術(shù)，能處置任意外形的多面體。該算法在性能上有較大的提高。_2 給出了兩種有效的優(yōu)化技術(shù)以提升算法功效。與常規(guī)圖象空間碰撞檢測算法相比，除了在性能上的優(yōu)勢之外，其準(zhǔn)確性不取決于繪制視窗的辨別率的大小，而與基于幾何的碰撞檢測算法精度一致；其通用性更好，可處置任意三角形網(wǎng)格物體而不限于凸體。但將算法應(yīng)用于軟體對象間的實時碰撞檢測和進一步提高算法功效，仍有待進一步研究。
圖像空間方法的優(yōu)點是不需要耗時的預(yù)處理，能檢測碰撞和自身碰撞，對象的拓?fù)淇梢愿淖，這些使得它特別適合于動態(tài)軟體對象。缺點是圖像空間方法不提供準(zhǔn)確的碰撞信息，而這些信息在基于物理特征的仿真環(huán)境中用于進一步計算碰撞響應(yīng)是必須的。
5 結(jié)束語
由于不同的方法輸入的數(shù)據(jù)不同，提供的碰撞信息不同，環(huán)境中的對象數(shù)量不同，目前無法對所有的方法進行完全一致的比較。軟體碰撞檢測的關(guān)鍵問題是在實時性和準(zhǔn)確性之間確定最佳折衷。
軟體碰撞檢測同時要求較高的實時性和準(zhǔn)確性，如何實現(xiàn)最佳折衷是難點所在。
參考文獻
[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].中國圖象圖形學(xué)報，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]魏迎梅，王湧，吳泉源，等.剛體在軟體對象環(huán)境中的碰撞檢測的研究[J].計算機學(xué)報，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]魏迎梅，王湧，吳泉源，等.虛擬手術(shù)仿真中碰撞檢測問題的研究[J].系統(tǒng)仿真學(xué)報，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，F(xiàn)rank 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，F(xiàn)rancois 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]範(fàn)昭煒，萬華根，高曙明.基于圖像的快速碰撞檢測算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，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]範(fàn)昭煒，萬華根，高曙明.基于流的實時碰撞檢測算法[J].軟件學(xué)報，2004，15(10)：1505—1514
[22]魏迎梅.虛擬環(huán)境中碰撞檢測問題的研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2000，55—62
[23]Stephane Guy，Gilles Debunne.Monte—Carlo collisiondetection[R].http：//artis.imag.fr/Publications/2004/GD04/，2005— 11—30
