摘要：介紹軟體碰撞檢測(cè)中主要的層次包圍盒方法、空間分割、隨機(jī)方法、距離場(chǎng)和圖像空問方法，從碰撞檢測(cè)的計(jì)算效率與準(zhǔn)確性的角度，分析這些算法的優(yōu)勢(shì)和不足，指出研究的關(guān)鍵點(diǎn)和難點(diǎn)。

1 引言

幾何模型間的碰撞檢測(cè)是織物仿真、計(jì)算機(jī)動(dòng)畫、機(jī)器人、CAD/CAM 等多領(lǐng)域的關(guān)鍵問題之一?？焖俣鴾?zhǔn)確的碰撞檢測(cè)對(duì)提高與人交互的虛擬環(huán)境的真實(shí)感至關(guān)重要，尤其對(duì)于需要力觸覺感知的虛擬環(huán)境 。在虛擬環(huán)境仿真中，碰撞檢測(cè)往往是系統(tǒng)計(jì)算效率的瓶頸 。目前對(duì)剛體之間的碰撞檢測(cè)算法的研究已趨向成熟 ～ ，但對(duì)軟體碰撞檢測(cè)的算法研究較少，尤其是對(duì)準(zhǔn)確性的考慮。對(duì)于虛擬外科手術(shù)訓(xùn)練、織物仿真、計(jì)算機(jī)動(dòng)畫、傷殘人力覺功能恢復(fù)等實(shí)用的虛擬環(huán)境中的交互對(duì)象，軟體對(duì)象比剛體對(duì)象更普遍。虛擬環(huán)境中的軟體對(duì)象不僅自身的復(fù)雜度高，而且會(huì)在外力的作用下發(fā)生形變，甚至發(fā)生拓?fù)浣Y(jié)構(gòu)的改變，這給碰撞檢測(cè)問題帶來了新的挑戰(zhàn) 。

2 碰撞檢測(cè)的實(shí)時(shí)性與準(zhǔn)確性

就實(shí)時(shí)性而言，滿足虛擬環(huán)境中視覺再現(xiàn)的實(shí)時(shí)性要求，碰撞檢測(cè)的速度只需達(dá)到24Hz以上，而要滿足人對(duì)虛擬環(huán)境中力覺再現(xiàn)的真實(shí)感知，碰撞檢測(cè)的速度要達(dá)到300Hz以上才能維持交互系統(tǒng)的穩(wěn)定性 。這使得其所受的實(shí)時(shí)性約束比純視覺虛擬環(huán)境的要嚴(yán)厲得多。就準(zhǔn)確性而言，包括時(shí)間準(zhǔn)確性和空間準(zhǔn)確性，對(duì)于環(huán)境漫游系統(tǒng)，一般只要粗略地計(jì)算碰撞時(shí)刻和位置。而對(duì)于虛擬手術(shù)仿真、虛擬裝配等應(yīng)用，就要求實(shí)時(shí)而準(zhǔn)確地檢測(cè)碰撞發(fā)生的時(shí)刻和部位。對(duì)于準(zhǔn)確性的評(píng)價(jià)方法現(xiàn)有文獻(xiàn)論述較少，目前見到的有采用檢測(cè)報(bào)告出錯(cuò)率的方法 ，而對(duì)出錯(cuò)的判定則與具體應(yīng)用及要求相關(guān)。

虛擬現(xiàn)實(shí)系統(tǒng)對(duì)虛擬環(huán)境的實(shí)時(shí)性和準(zhǔn)確性要求往往相互抵觸，真實(shí)性越高，要求模型越準(zhǔn)確精細(xì)，相應(yīng)的數(shù)據(jù)量越大，碰撞檢測(cè)的時(shí)間開銷也更大，甚至不能承受，目前許多實(shí)際的系統(tǒng)對(duì)碰撞響應(yīng)處理只能采用近似方法 。因此碰撞檢測(cè)必須依據(jù)實(shí)際應(yīng)用對(duì)實(shí)時(shí)性和真實(shí)性的具體要求，在準(zhǔn)確性和實(shí)時(shí)性之間折衷。

3 軟體對(duì)象碰撞檢測(cè)的特點(diǎn)

3.1 計(jì)算效率高

對(duì)軟體對(duì)象的物理模型的力和變形等計(jì)算比剛體要復(fù)雜得多，這導(dǎo)致了對(duì)碰撞檢測(cè)算法的計(jì)算效率和準(zhǔn)確性的高要求。

3.2 提供準(zhǔn)確的碰撞信息

剛體物理模型為集中式參數(shù)，而軟體對(duì)象的物理模型往往具有分布式參數(shù)，軟體發(fā)生碰撞的部位不同，其隨后的碰撞響應(yīng)不同。準(zhǔn)確的碰撞時(shí)刻和位置信息是計(jì)算隨后的逼真的碰撞響應(yīng)所必須的。

3.3 要求數(shù)據(jù)結(jié)構(gòu)更新快

對(duì)于剛體碰撞檢測(cè)算法可在預(yù)處理階段建立對(duì)象的表示，例如層次包圍盒、距離場(chǎng)、或其它空間分割方式等空間數(shù)據(jù)結(jié)構(gòu)，這樣做效率很高。但是，對(duì)于軟體對(duì)象，由于在交互中會(huì)產(chǎn)生變形，這些預(yù)處理的數(shù)據(jù)結(jié)構(gòu)必須頻繁且快速地更新。

3.4 需考慮自身碰撞

與剛體間的碰撞檢測(cè)不同，為了逼真地仿真與軟體對(duì)象及它們之間的交互，必須考慮所有的接觸點(diǎn)并且包括自身碰撞。例如在織物仿真中，織物與織物間的碰撞經(jīng)常發(fā)生。

4 軟體對(duì)象的碰撞檢測(cè)方法

軟體碰撞檢測(cè)方法按照所采用的方法其基本思想的不同，主要可分為層次包圍盒、空間分割、隨機(jī)方法、距離場(chǎng)和圖像空間方法。

4.1 層次包圍盒

層次包圍盒方法以三維形體的邊界表示法為基礎(chǔ)，其基本思想是用體積稍大且?guī)缀翁匦院?jiǎn)單的包圍盒來近似地描述復(fù)雜的幾何對(duì)象，并通過構(gòu)造樹狀層次結(jié)構(gòu)逐漸逼近對(duì)象的幾何特性。進(jìn)行重疊測(cè)試時(shí)只需對(duì)包圍盒重疊的部分進(jìn)行進(jìn)一步的相交測(cè)試，從而可大大減少參與相交測(cè)試的包圍盒的數(shù)目，提高碰撞檢測(cè)的效率。

層次包圍盒方法中每個(gè)節(jié)點(diǎn)的孩子數(shù)量的選擇也是一個(gè)關(guān)鍵點(diǎn)。對(duì)于剛體通常選擇二叉樹，但對(duì)于軟體對(duì)象，四叉或八又樹總體性能更好。因?yàn)楦俚墓?jié)點(diǎn)需要更新和總的更新代價(jià)降低了。另外，重疊測(cè)試的遞歸深度更低，所以在存儲(chǔ)空間上的需求更低。

層次包圍盒方法的效率和準(zhǔn)確性關(guān)鍵在于包圍盒類型的選取。包圍盒類型有多種，例如球，方向包圍盒(OBB)，DOPs，Boxtrees，軸向包圍盒(AABB)，spherical shells和凸包，如圖1所示。

 
圖1 各種包圍盒類型

其中方向包圍盒OBB和k—DOP這兩種值得注意。OBB是比較常用的一種類型。在大多數(shù)情況下其總體性能要優(yōu)于AABB和包圍球，但因?qū)ο笞冃魏驩BB樹的更新太慢不適合用于包含軟體對(duì)象的復(fù)雜環(huán)境中。k—DOP又稱為固定方向凸包FDH(在此我們也稱其為FDH)。在軟體對(duì)象環(huán)境中，F(xiàn)DH的使用最為常見。實(shí)際上，AABB是k—DOP中k=6時(shí)的一個(gè)特例。包含k個(gè)固定方向向量的兩個(gè)FDH間的相交測(cè)試最多只需k次比較運(yùn)算，當(dāng)對(duì)象發(fā)生形變時(shí)更新一個(gè)結(jié)點(diǎn)的FDH只需要k次比較運(yùn)算，計(jì)算效率較高。同時(shí)，F(xiàn)DH在很大程度上改善了AABB的緊密性差的缺點(diǎn)，因此可提高碰撞檢測(cè)的準(zhǔn)確性。

論文[6]通過一種自底向上的方法解決了軟體變形后的FDH樹的更新問題。但變形后包圍盒層次的調(diào)整更新是軟體環(huán)境碰撞檢測(cè)的瓶頸，如何提高FDH樹的更新速度仍有待進(jìn)一步研究。

論文[13]中使用FDH了進(jìn)行織物仿真，提出進(jìn)一步加速FDH層次更新的方法，使碰撞檢測(cè)不再成為織物模擬系統(tǒng)的瓶頸。由于任何穿透都是可見的，織物的碰撞檢測(cè)的準(zhǔn)確度要求非常高。就碰撞檢測(cè)和響應(yīng)的準(zhǔn)確度兩方面與采用Maya的比較結(jié)果看，此方法可正確地檢測(cè)所有的碰撞，而采用Maya時(shí)出現(xiàn)了穿透現(xiàn)象。

層次包圍盒方法應(yīng)用非常廣泛，為復(fù)雜模型間準(zhǔn)確的碰撞檢測(cè)提供一個(gè)快速有效的方法。

4.2 空間分割

基于空間分割的碰撞檢測(cè)基本思想是，對(duì)整個(gè)場(chǎng)景空間△，沿X、Y、z軸進(jìn)行分割，形成一系列單元格。只對(duì)同處于一個(gè)單元格內(nèi)對(duì)象之間進(jìn)行碰撞檢測(cè)。空間分割可用于檢測(cè)碰撞和自身碰撞，對(duì)象拓?fù)淇梢愿淖儯幌拗埔匀切巫鳛閷?duì)象的基本幾何元?？臻g分割方法中于用于表示3D空間數(shù)據(jù)結(jié)構(gòu)選擇很重要，如圖2所示。

 
圖2 表示3D空間數(shù)據(jù)結(jié)構(gòu)

這種數(shù)據(jù)結(jié)構(gòu)在計(jì)算時(shí)間和存儲(chǔ)上必須是靈活的和有效率的。

在碰撞檢測(cè)應(yīng)用中，常用的空間分割方法包括：均勻網(wǎng)格、八叉樹和BSP樹等。一般來說，BSP樹、八叉樹或kd一樹都是對(duì)象相關(guān)的。八叉樹的建立很耗時(shí)間，所以不適合在動(dòng)態(tài)環(huán)境中實(shí)時(shí)碰撞檢測(cè)。而使用均勻網(wǎng)格的空間分割與對(duì)象無關(guān)，使得它特別適合軟體對(duì)象。均勻空間分割的關(guān)鍵問題是確定適當(dāng)?shù)膯卧癯叽纾m當(dāng)選擇單元格尺寸大小，可使算法的計(jì)算能保持一定的準(zhǔn)確度又不致開銷太大。

論文[3]提出一種基于均勻空間分割的快速多體碰撞檢測(cè)算法，同時(shí)依據(jù)對(duì)象的分布密度，提出了一個(gè)計(jì)算單元格尺寸的優(yōu)化方法。與Cohen等人提出的I—COLLIDE算法的比較實(shí)驗(yàn)表明，在均勻分布條件下，當(dāng)物體數(shù)量較大時(shí)，該算法的效率高于I—COLLIDE算法，而且其效率基本不受物體運(yùn)動(dòng)相關(guān)性的影響。

論文[14]使用均勻網(wǎng)格的空間散列來檢測(cè)可變形四面體網(wǎng)格的碰撞和自身碰撞。提出使用哈希函數(shù)來映射3D網(wǎng)格到一個(gè)哈希表，從而實(shí)現(xiàn)快速的隱式的空間分割。該方法不僅節(jié)省存儲(chǔ)空間，而且很靈活。此外，還討論了最佳的單元大小。實(shí)驗(yàn)表明最佳單元大小和單個(gè)物體幾何元的包圍盒一樣大，此時(shí)算法的計(jì)算效率最高。在20k個(gè)四面體的環(huán)境中可以實(shí)時(shí)地檢測(cè)碰撞和自身碰撞，算法給出的準(zhǔn)確的位置信息可用于正確的碰撞響應(yīng)。

其性能與對(duì)象的數(shù)量無關(guān)，只與對(duì)象幾何元的數(shù)量有關(guān)。所以該方法可用于多個(gè)對(duì)象的環(huán)境中。

當(dāng)對(duì)象較少且均勻分布于空間時(shí)，空間分割方法效率較高；當(dāng)對(duì)象較多且距離很近時(shí)，需進(jìn)行單元格的進(jìn)一步遞歸分割，并需要大量的單元格相交測(cè)試和存儲(chǔ)空間，效率明顯降低?？臻g分割由于存儲(chǔ)量大及靈活性不好，使用不如包圍盒層次法廣泛。

4.3 隨機(jī)方法

隨機(jī)方法按使用隨機(jī)方法的方式的不同可分為average—case方法和基于隨機(jī)選擇幾何元的碰撞檢測(cè)方法。

Average—case方法使用隨機(jī)方法來估計(jì)碰撞的可能性。其主要思想是考慮層次包圍盒的內(nèi)部節(jié)點(diǎn)的多邊形集，遍歷時(shí)快速地計(jì)算一對(duì)包圍盒的多邊形問的碰撞可能性，然后把這個(gè)可能性作為優(yōu)先權(quán)來指導(dǎo)遍歷那些有更高可能性的BV樹部分。

該方法可用于BVHs上，所以能擴(kuò)展許多基于層次包圍盒的碰撞檢測(cè)方法。 首次提出把一般的層次碰撞檢測(cè)算法轉(zhuǎn)換為以可控制的方式來平衡計(jì)算效率和準(zhǔn)確度的方法，并比較了擴(kuò)展AABB樹的average—case方法和基于DOP樹的算法，結(jié)果顯示前者成倍地增加計(jì)算效率而不明顯降低準(zhǔn)確性。

基于隨機(jī)選擇幾何元的碰撞檢測(cè)方法在碰撞對(duì)象內(nèi)通過隨機(jī)取樣作為初始的潛在的交互區(qū)域的猜測(cè)。準(zhǔn)確的碰撞區(qū)域通過使用時(shí)空一致性來縮小。該方法與任何層次無關(guān)，可直接用于幾何元對(duì)。如果相鄰兩次最近特征的距離，即模型的相干性高，那么算法的效率較高，相反相干性越低，算法效率就越低。Lin和Canny提出的解決方法 考慮了時(shí)空一致性。如果特征對(duì)在上一個(gè)時(shí)間步上足夠近，它很可能是下一個(gè)時(shí)間步上交互的特征對(duì)。J 利用了時(shí)間一致性，提出了一個(gè)分兩步來計(jì)算曲面結(jié)構(gòu)的局部距離最小值的更新方法，把時(shí)間復(fù)雜度從O(mn)減/J,N O(m+n)，m和n是鄰近幾何元的數(shù)目。

雖然兩種隨機(jī)方法各不相同，但它們有共同的特點(diǎn)，即都可以平衡碰撞檢測(cè)的計(jì)算效率和準(zhǔn)確性，能獲得有意義的接觸信息用于處理碰撞，但不能用于精確的碰撞檢測(cè)。對(duì)于時(shí)間關(guān)鍵的碰撞檢測(cè)，隨機(jī)方法具有較大的發(fā)展前景。

4.4 距離場(chǎng)

距離場(chǎng)定義了場(chǎng)中所有點(diǎn)到閉合曲面的最小距離。距離場(chǎng)D：R3一R定義了一個(gè)曲面作為零等值面。為了區(qū)分內(nèi)部和外部，距離是有符號(hào)的。用距離場(chǎng)表示閉合曲面有不限制拓?fù)涞膬?yōu)點(diǎn)。另外，碰撞檢測(cè)和響應(yīng)所需要的距離和法線的估計(jì)非?？?，而且和對(duì)象的幾何復(fù)雜性無關(guān)。為了降低存儲(chǔ)需求或距離場(chǎng)生成時(shí)間，可以減少距離場(chǎng)的求解，降低準(zhǔn)確度。所以距離場(chǎng)方法能平衡計(jì)算效率和準(zhǔn)確度。表示距離場(chǎng)的數(shù)據(jù)結(jié)構(gòu)有多種，例如均勻3D網(wǎng)格、八叉樹和BSP樹。

論文[17]提曲了剛體和軟體對(duì)象問的快速距離計(jì)算的問題。為了改善碰撞檢測(cè)的準(zhǔn)確度，對(duì)可變形網(wǎng)格上每條邊的中心均進(jìn)行了測(cè)試。實(shí)驗(yàn)顯示，該方法能以交互的速度仿真織物，準(zhǔn)確地檢測(cè)復(fù)雜非凸對(duì)象的碰撞。

距離場(chǎng)方法提供了很健壯的碰撞檢測(cè)，因?yàn)樗鼈儼芽臻g嚴(yán)格地分成內(nèi)部和外部。距離場(chǎng)方法用于在非交互應(yīng)用中檢測(cè)碰撞和自身碰撞。盡管最近提出了高效率的計(jì)算距離場(chǎng)的算法，但由于變形幾何體距離場(chǎng)必須在運(yùn)行時(shí)間內(nèi)更新，所以相對(duì)于交互應(yīng)用的要求，距離場(chǎng)方法仍不夠快。

4.5 圖像空間方法

基于圖像空間的碰撞檢測(cè)算法一般將三維幾何對(duì)象通過投影繪制到圖像平面上，降維得到一個(gè)二維的圖像空間；然后分析該空間中保存在各類緩存的信息；進(jìn)而檢測(cè)出對(duì)象之間是否發(fā)生干涉 ，如圖3所示。

 
圖3 利用深度緩存降維

這是一類較新的碰撞檢測(cè)算法，由于它們不需要任何預(yù)處理，特別適合于包含動(dòng)態(tài)軟體對(duì)象的環(huán)境。圖像空間方法中對(duì)象是離散表示的，它不提供準(zhǔn)確的碰撞信息，碰撞檢測(cè)的準(zhǔn)確度取決于離散誤差。準(zhǔn)確度和計(jì)算效率可以通過改變繪制過程的分辨率在一定范圍內(nèi)平衡。

論文[2]提出虛擬外科手術(shù)的圖像空間方法。該方法依靠圖形硬件來測(cè)試虛擬可變形器官和使用者控制的剛性工具間的穿透，可以實(shí)時(shí)檢測(cè)碰撞。在四個(gè)特殊的應(yīng)用中，該方法比著名的OBB方法運(yùn)行起來快約100倍。

在許多圖像空間碰撞方法中，Layered DepthImage LDI是基本的數(shù)據(jù)結(jié)構(gòu)。LDI數(shù)據(jù)結(jié)構(gòu)的本質(zhì)是存儲(chǔ)每個(gè)像素的多個(gè)深度值。因而，LDI能用于近似表示對(duì)象的體積。_1 中的圖像空間方法可用于任意形狀軟體對(duì)象的碰撞檢測(cè)，但不檢測(cè)自身碰撞。提出了改進(jìn)的算法而且考慮自身碰撞。_2。。給出了三種不同的產(chǎn)生LayeredDepth Image LDI的實(shí)現(xiàn)。其中兩種基于圖形硬件和一種軟件方法。結(jié)果顯示，在幾何復(fù)雜環(huán)境中圖形硬件加速了圖像空間碰撞檢測(cè)，但在小型環(huán)境的情況下基于CPU的實(shí)現(xiàn)提供了更靈活和更好的性能。

論文[18]提出的基于圖像空間的碰撞檢測(cè)算法主要采用對(duì)物體表面進(jìn)行自動(dòng)分解，將凸分解結(jié)果合理地組織成層次二叉樹結(jié)構(gòu)，以及繪制加速等技術(shù)，能處理任意形狀的多面體。該算法在性能上有較大的提高。_2 給出了兩種有效的優(yōu)化技術(shù)以提升算法效率。與常規(guī)圖象空間碰撞檢測(cè)算法相比，除了在性能上的優(yōu)勢(shì)之外，其準(zhǔn)確性不取決于繪制視窗的分辨率的大小，而與基于幾何的碰撞檢測(cè)算法精度一致；其通用性更好，可處理任意三角形網(wǎng)格物體而不限于凸體。但將算法應(yīng)用于軟體對(duì)象間的實(shí)時(shí)碰撞檢測(cè)和進(jìn)一步提高算法效率，仍有待進(jìn)一步研究。

圖像空間方法的優(yōu)點(diǎn)是不需要耗時(shí)的預(yù)處理，能檢測(cè)碰撞和自身碰撞，對(duì)象的拓?fù)淇梢愿淖?，這些使得它特別適合于動(dòng)態(tài)軟體對(duì)象。缺點(diǎn)是圖像空間方法不提供準(zhǔn)確的碰撞信息，而這些信息在基于物理特性的仿真環(huán)境中用于進(jìn)一步計(jì)算碰撞響應(yīng)是必需的。

5 結(jié)束語(yǔ)

由于不同的方法輸入的數(shù)據(jù)不同，提供的碰撞信息不同，環(huán)境中的對(duì)象數(shù)量不同，目前無法對(duì)所有的方法進(jìn)行完全一致的比較。軟體碰撞檢測(cè)的關(guān)鍵問題是在實(shí)時(shí)性和準(zhǔn)確性之間確定最佳折衷。

軟體碰撞檢測(cè)同時(shí)要求較高的實(shí)時(shí)性和準(zhǔn)確性，如何實(shí)現(xiàn)最佳折衷是難點(diǎ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：一個(gè)基于均勻空間分割的快速碰撞檢測(cè)算法[J].中國(guó)圖象圖形學(xué)報(bào)，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]魏迎梅，王涌，吳泉源，等.剛體在軟體對(duì)象環(huán)境中的碰撞檢測(cè)的研究[J].計(jì)算機(jī)學(xué)報(bào)，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ù)仿真中碰撞檢測(cè)問題的研究[J].系統(tǒng)仿真學(xué)報(bào)，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]范昭煒，萬華根，高曙明.基于圖像的快速碰撞檢測(cè)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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]范昭煒，萬華根，高曙明.基于流的實(shí)時(shí)碰撞檢測(cè)算法[J].軟件學(xué)報(bào)，2004，15(10)：1505—1514

[22]魏迎梅.虛擬環(huán)境中碰撞檢測(cè)問題的研究[D].長(zhǎng)沙：國(guó)防科學(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