虛擬環(huán)境中的軟體碰撞檢測(cè)技術(shù)綜述

1、虛擬環(huán)境中的軟體碰撞檢測(cè)技術(shù)綜述*梁小紅 劉少?gòu)?qiáng)(中南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410075摘 要 介紹軟體碰撞檢測(cè)中主要的層次包圍盒方法、空間分割、隨機(jī)方法、距離場(chǎng)和圖像空間方法,從碰撞檢測(cè)的計(jì)算效率與準(zhǔn)確性的角度,分析這些算法的優(yōu)勢(shì)和不足,指出研究的關(guān)鍵點(diǎn)和難點(diǎn)。關(guān)鍵詞 虛擬環(huán)境 碰撞檢測(cè) 算法 計(jì)算效率 準(zhǔn)確性中圖分類號(hào) TP3911 引言幾何模型間的碰撞檢測(cè)是織物仿真、計(jì)算機(jī)動(dòng)畫(huà)、機(jī)器人、CAD/CAM等多領(lǐng)域的關(guān)鍵問(wèn)題之一1?？焖俣鴾?zhǔn)確的碰撞檢測(cè)對(duì)提高與人交互的虛擬環(huán)境的真實(shí)感至關(guān)重要,尤其對(duì)于需要力觸覺(jué)感知的虛擬環(huán)境2。在虛擬環(huán)境仿真中,碰撞檢測(cè)往往是系統(tǒng)計(jì)算效率的瓶頸3。目前

2、對(duì)剛體之間的碰撞檢測(cè)算法的研究已趨向成熟47,但對(duì)軟體碰撞檢測(cè)的算法研究較少,尤其是對(duì)準(zhǔn)確性的考慮。對(duì)于虛擬外科手術(shù)訓(xùn)練、織物仿真、計(jì)算機(jī)動(dòng)畫(huà)、傷殘人力覺(jué)功能恢復(fù)等實(shí)用的虛擬環(huán)境中的交互對(duì)象,軟體對(duì)象比剛體對(duì)象更普遍。虛擬環(huán)境中的軟體對(duì)象不僅自身的復(fù)雜度高,而且會(huì)在外力的作用下發(fā)生形變,甚至發(fā)生拓?fù)浣Y(jié)構(gòu)的改變,這給碰撞檢測(cè)問(wèn)題帶來(lái)了新的挑戰(zhàn)6。2 碰撞檢測(cè)的實(shí)時(shí)性與準(zhǔn)確性就實(shí)時(shí)性而言,滿足虛擬環(huán)境中視覺(jué)再現(xiàn)的實(shí)時(shí)性要求,碰撞檢測(cè)的速度只需達(dá)到24H z以上,而要滿足人對(duì)虛擬環(huán)境中力覺(jué)再現(xiàn)的真實(shí)感知,碰撞檢測(cè)的速度要達(dá)到300H z以上才能維持交互系統(tǒng)的穩(wěn)定性8。這使得其所受的實(shí)時(shí)性約束比純視覺(jué)

3、虛擬環(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)論述較少,目前見(jiàn)到的有采用檢測(cè)報(bào)告出錯(cuò)率的方法9,而對(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í)間開(kāi)銷也更大,甚至不能承受,目前許多實(shí)際的系統(tǒng)對(duì)碰撞響應(yīng)處理只能采用近似方法10-11。因此碰撞檢測(cè)必須依據(jù)實(shí)際應(yīng)用對(duì)實(shí)時(shí)性和真實(shí)性的具體要求,在準(zhǔn)確性和實(shí)時(shí)性之間折衷。

4、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)必須頻繁且快速地更新。24 計(jì)算機(jī)與數(shù)

5、字工程 第35卷*收到本文時(shí)間:2006年7月6日基金項(xiàng)目:湖南省自然基金項(xiàng)目(編號(hào):04JJ3089作者簡(jiǎn)介:梁小紅,女,碩士研究生,研究方向:虛擬現(xiàn)實(shí)。劉少?gòu)?qiáng),男,博士,副教授,研究方向:傳感器及智能檢測(cè)技術(shù),臨場(chǎng)遙感操作機(jī)器人。3.4 需考慮自身碰撞與剛體間的碰撞檢測(cè)不同,為了逼真地仿真與軟體對(duì)象及它們之間的交互,必須考慮所有的接觸點(diǎn)并且包括自身碰撞。例如在織物仿真中,織物與織物間的碰撞經(jīng)常發(fā)生。4 軟體對(duì)象的碰撞檢測(cè)方法軟體碰撞檢測(cè)方法按照所采用的方法其基本思想的不同,主要可分為層次包圍盒、空間分割、隨機(jī)方法、距離場(chǎng)和圖像空間方法12。4.1 層次包圍盒層次包圍盒方法以三維形體的邊界表

6、示法為基礎(chǔ),其基本思想是用體積稍大且?guī)缀翁匦院?jiǎn)單的包圍盒來(lái)近似地描述復(fù)雜的幾何對(duì)象,并通過(guò)構(gòu)造樹(shù)狀層次結(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ì)于剛體通常選擇二叉樹(shù),但對(duì)于軟體對(duì)象,四叉或八叉樹(shù)總體性能更好。因?yàn)楦俚墓?jié)點(diǎn)需要更新和總的更新代價(jià)降低了。另外,重疊測(cè)試的遞歸深度更低,所以在存儲(chǔ)空間上的需求更低。層次包圍盒方法的效率和準(zhǔn)確性關(guān)鍵在于包圍盒類型的選取。包圍盒類型有多種,例如球,方向包圍盒(OBB ,DOPs ,Box tr

7、ees ,軸向包圍盒(AABB ,spherical shells 和凸包,如圖1 所示。算,當(dāng)對(duì)象發(fā)生形變時(shí)更新一個(gè)結(jié)點(diǎn)的FDH 只需要k 次比較運(yùn)算,計(jì)算效率較高。同時(shí),FDH 在很大程度上改善了AABB 的緊密性差的缺點(diǎn),因此可提高碰撞檢測(cè)的準(zhǔn)確性。論文6通過(guò)一種自底向上的方法解決了軟體變形后的FDH 樹(shù)的更新問(wèn)題。但變形后包圍盒層次的調(diào)整更新是軟體環(huán)境碰撞檢測(cè)的瓶頸,如何提高FDH 樹(shù)的更新速度仍有待進(jìn)一步研究。論文13中使用FDH 了進(jìn)行織物仿真,提出進(jìn)一步加速FDH 層次更新的方法,使碰撞檢測(cè)不再成為織物模擬系統(tǒng)的瓶頸。由于任何穿透都是可見(jiàn)的,織物的碰撞檢測(cè)的準(zhǔn)確度要求非常高。就碰

8、撞檢測(cè)和響應(yīng)的準(zhǔn)確度兩方面與采用M aya 的比較結(jié)果看,此方法可正確地檢測(cè)所有的碰撞,而采用M aya 時(shí)出現(xiàn)了穿透現(xiàn)象。層次包圍盒方法應(yīng)用非常廣泛,為復(fù)雜模型間準(zhǔn)確的碰撞檢測(cè)提供一個(gè)快速有效的方法。4.2 空間分割圖2 表示3D 空間的數(shù)據(jù)結(jié)構(gòu)基于空間分割的碰撞檢測(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所示。這種數(shù)據(jù)結(jié)構(gòu)在計(jì)算時(shí)間和存儲(chǔ)上必須是靈活的和有效率的。

9、在碰撞檢測(cè)應(yīng)用中,常用的空間分割方法包括:均勻網(wǎng)格、八叉樹(shù)和BSP 樹(shù)等。一般來(lái)說(shuō),BSP 樹(shù)、八叉樹(shù)或kd-樹(shù)都是對(duì)象相關(guān)的。八叉樹(shù)的,所以不適合在動(dòng)態(tài)環(huán)境中實(shí)時(shí)碰撞,使,適當(dāng)選擇單元格尺寸提出一種基于均勻空間分割的快速,同時(shí)依據(jù)對(duì)象的分布密度,提尺寸的優(yōu)化方法。與Cohen I-COLLI DE 算法的比較實(shí)驗(yàn)表明,在25第35卷(2007第3期 計(jì)算機(jī)與數(shù)字工程均勻分布條件下,當(dāng)物體數(shù)量較大時(shí),該算法的效率高于I-COLLI DE算法,而且其效率基本不受物體運(yùn)動(dòng)相關(guān)性的影響。論文14使用均勻網(wǎng)格的空間散列來(lái)檢測(cè)可變形四面體網(wǎng)格的碰撞和自身碰撞。提出使用哈希函數(shù)來(lái)映射3D網(wǎng)格到一個(gè)哈希表,

10、從而實(shí)現(xiàn)快速的隱式的空間分割。該方法不僅節(jié)省存儲(chǔ)空間,而且很靈活。此外,還討論了最佳的單元大小。實(shí)驗(yàn)表明最佳單元大小和單個(gè)物體幾何元的包圍盒一樣大,此時(shí)算法的計(jì)算效率最高。在20k個(gè)四面體的環(huán)境中可以實(shí)時(shí)地檢測(cè)碰撞和自身碰撞,算法給出的準(zhǔn)確的位置信息可用于正確的碰撞響應(yīng)。其性能與對(duì)象的數(shù)量無(wú)關(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ī)方法按

11、使用隨機(jī)方法的方式的不同可分為average-case方法和基于隨機(jī)選擇幾何元的碰撞檢測(cè)方法。Average-case方法使用隨機(jī)方法來(lái)估計(jì)碰撞的可能性。其主要思想是考慮層次包圍盒的內(nèi)部節(jié)點(diǎn)的多邊形集,遍歷時(shí)快速地計(jì)算一對(duì)包圍盒的多邊形間的碰撞可能性,然后把這個(gè)可能性作為優(yōu)先權(quán)來(lái)指導(dǎo)遍歷那些有更高可能性的BV樹(shù)部分。該方法可用于B VH s上,所以能擴(kuò)展許多基于層次包圍盒的碰撞檢測(cè)方法。9首次提出把一般的層次碰撞檢測(cè)算法轉(zhuǎn)換為以可控制的方式來(lái)平衡計(jì)算效率和準(zhǔn)確度的方法,并比較了擴(kuò)展AABB樹(shù)的average-case方法和基于DOP樹(shù)的算法,結(jié)果顯示前者成倍地增加計(jì)算效率而不明顯降低準(zhǔn)確性?；?/p>

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

13、衡碰撞檢測(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:R3R定義了一個(gè)曲面作為零等值面。為了區(qū)分內(nèi)部和外部,距離是有符號(hào)的。用距離場(chǎng)表示閉合曲面有不限制拓?fù)涞膬?yōu)點(diǎn)。另外,碰撞檢測(cè)和響應(yīng)所需要的距離和法線的估計(jì)非?？?而且和對(duì)象的幾何復(fù)雜性無(wú)關(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)格、八叉樹(shù)和BSP樹(shù)。論文17提出了剛體和軟體對(duì)象

14、間的快速距離計(jì)算的問(wèn)題。為了改善碰撞檢測(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ì)象通過(guò)投影繪制到圖像平面上,降維得到一個(gè)二維的圖像空間;然后分析該空間中保存在各類緩存的信息;進(jìn)而檢測(cè)出對(duì)象之間是否發(fā)生干涉18,

15、如圖5所示。圖3 利用深度緩存降維這是一類較新的碰撞檢測(cè)算法,由于它們不需要任何預(yù)處理,特別適合于包含動(dòng)態(tài)軟體對(duì)象的環(huán)境。圖像空間方法中對(duì)象是離散表示的,它不提供準(zhǔn)確的碰撞信息,碰撞檢測(cè)的準(zhǔn)確度取決于離散誤差。準(zhǔn)確度和計(jì)算效率可26 梁小紅等:虛擬環(huán)境中的軟體碰撞檢測(cè)技術(shù)綜述 第35卷以通過(guò)改變繪制過(guò)程的分辨率在一定范圍內(nèi)平衡。論文2提出虛擬外科手術(shù)的圖像空間方法。該方法依靠圖形硬件來(lái)測(cè)試虛擬可變形器官和使用者控制的剛性工具間的穿透,可以實(shí)時(shí)檢測(cè)碰撞。在四個(gè)特殊的應(yīng)用中,該方法比著名的OBB 方法運(yùn)行起來(lái)快約100倍。在許多圖像空間碰撞方法中,Layered D ep th I m age L

16、D I是基本的數(shù)據(jù)結(jié)構(gòu)。LD I數(shù)據(jù)結(jié)構(gòu)的本質(zhì)是存儲(chǔ)每個(gè)像素的多個(gè)深度值。因而,LD I 能用于近似表示對(duì)象的體積。19中的圖像空間方法可用于任意形狀軟體對(duì)象的碰撞檢測(cè),但不檢測(cè)自身碰撞。20提出了改進(jìn)的算法而且考慮自身碰撞。20給出了三種不同的產(chǎn)生Layered Depth I m age LD I的實(shí)現(xiàn)。其中兩種基于圖形硬件和一種軟件方法。結(jié)果顯示,在幾何復(fù)雜環(huán)境中圖形硬件加速了圖像空間碰撞檢測(cè),但在小型環(huán)境的情況下基于CPU的實(shí)現(xiàn)提供了更靈活和更好的性能。論文18提出的基于圖像空間的碰撞檢測(cè)算法主要采用對(duì)物體表面進(jìn)行自動(dòng)分解,將凸分解結(jié)果合理地組織成層次二叉樹(shù)結(jié)構(gòu),以及繪制加速等技術(shù),能

17、處理任意形狀的多面體。該算法在性能上有較大的提高。21給出了兩種有效的優(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ǔ)由于不同的

18、方法輸入的數(shù)據(jù)不同,提供的碰撞信息不同,環(huán)境中的對(duì)象數(shù)量不同,目前無(wú)法對(duì)所有的方法進(jìn)行完全一致的比較。軟體碰撞檢測(cè)的關(guān)鍵問(wèn)題是在實(shí)時(shí)性和準(zhǔn)確性之間確定最佳折衷。軟體碰撞檢測(cè)同時(shí)要求較高的實(shí)時(shí)性和準(zhǔn)確性,如何實(shí)現(xiàn)最佳折衷是難點(diǎn)所在。參考文獻(xiàn)1Jean-Chr i stophe Lombardo,M arie-P au le Can i,F abr i ceN eyret.R eal-ti m e co llisi on detec ti on for v irt ua l surgeryC.P ro ceedi ngs o fComputer A n i m a ti on.Sw itze rl

19、and G eneva:IEEE,1999,82912June G yu P ark,G nter N ie m ey er.H aptic R ende ri ng w it hP redicti ve R epresenta tion o f L ocal G eo m etryC.P roceedi ngs o f12th Inte rnati ona l Sy m pos i u m on H apti c In terfacesF or V i rtua l Env iron m ent and T eleoperator Sy stem s.Chicago:IEEE Co m pu

20、ter So ciety,2004,3313383李焱,盧曉軍,賀漢根.U SSCD:一個(gè)基于均勻空間分割的快速碰撞檢測(cè)算法J.中國(guó)圖象圖形學(xué)報(bào),2003,8(12:144414494G ottschalk S,L i n M C,M anocha D.OBBT ree:A h i e rarchica l structure for rapi d i nterfe rence de tecti onC.P roceedi ngs o fACM S i ggraph 96.N ew O r l eans:AC M,1996,1711805Cohen J D,L i n M C,M anocha

21、 D,et a.l I-COLL I DE:A ni n terac tive and exact co lli s i on detecti on syste m f o r largesca l e env i ron m entsC.P ro ceedings of A C M Interacti ve3DG raph i cs Con ference.Ca li:f AC M,1995,1891966魏迎梅,王涌,吳泉源,等.剛體在軟體對(duì)象環(huán)境中的碰撞檢測(cè)的研究J.計(jì)算機(jī)學(xué)報(bào),2001,24(8:802808 7Ca m eron S A.Co llisi on detection b

22、y four-di m ensi onal i ntersecti on testi ngJ.IEEE T rans R obo ti cs and A uto m at, 1990,2913028魏迎梅,王涌,吳泉源,等.虛擬手術(shù)仿真中碰撞檢測(cè)問(wèn)題的研究J.系統(tǒng)仿真學(xué)報(bào),2000,12(5:572575 9Jan K l e i n,G abr i e l Z ach m ann T i m e-Cr iti ca lCo llisi on D etecti on U si ng an A verage-Case A pproachC.P roceedi ngs o f the A C M

23、symposi um on V irt ua l rea li ty so ft ware andtechno l ogy.Japan O saka:AC M,2003,223110M urat Cenk Cavusog l u,Frank T end ick.M ultirate si m ulati on f o r high fide lity haptic i nte raction w ith defor m able ob jects i n v i rtua l env iron m entsC.P roceed i ng s-IEEE Inte rnati onal Confe

24、rence on R obo tics and A uto m ation.SanF ranc i sco:Institute of Electrical and E lectron i cs Eng ineers Inc,2000,24582465.11Jung K i m,Suvranu D e,M anday a m A.S ri n i vasan.Co m puta ti ona lly e ffi c ient techn i ques for real ti m e surg i ca l s i m u l a ti on w it h force feedbackC.P ro

25、ceedi ngs of10th Sy m p.On H aptic Interfaces F or V i rtua l Env iron m ent.&T e leop11e ra t o r Syste m s.O rlando:IEEE Co m puter Soc i e t y,2002,515712G.Z ach m ann,M.T eschne r,S.K i m m erle,B.H e i de lberger,L.R aghupa t h,i and A.Fuhr m ann.R ea l-T i m e Co llisi on D e tecti on for D yn

26、a m i c V irtual Env iron m ents z,IEEE V i rtual R ea lity2005,M a rch1216,2005,27第35卷(2007第3期 計(jì)算機(jī)與數(shù)字工程Bonn ,G er m any .Pages 132.13M ezger ,S .K i m m erle ,O.E tz mub .H i erarch ica l T echn i quesi n Co llisi on D etecti on fo r C loth A ni m ation J.Journal of W SCG 11,2003,32232914M atthias

27、T eschne r ,Bruno H e i de l berge r ,M atthiasM ller ,e t a.l Opti m ized spatial hashing for co llisi on detection of defor m able objects C .P roceedings o f V i s i on ,M odel i ng ,V isuali zati on VM V03.G er m any M unich :VM V2003,2003,475415L I N M.C.,CANNY J .F .E ffic i ent Co llisi on D

28、etecti on forAn i m ati onC.P roc .3rd Eurog raph i cs W orkshop on A ni m ation and Si m ulation .Ca m bridge ,1992.16L aks R aghupa t h,i L aurent G rison,i F ranco is Faure ,et a.lAn i n testi ne surgery si m ulator :R eal-ti m e collision pro cessi ng and v isualizati onJ.IEEE T ransacti on on V

29、 isual i zati on and Co m pute r G raph i cs ,2004,70871817A rnul ph Fuhr m ann ,G e rr it Sobottka ,C le m ens G rob .d istance fie l ds for rap i d co llisi on detecti on in physica ll y based m ode li ngC.Proceed i ng s of G raph i C on .M oscow,2003,586518范昭煒,萬(wàn)華根,高曙明.基于圖像的快速碰撞檢測(cè)算法J.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)

30、,2002,14(9:805810.19Bruno H e i delberger ,M atthias T eschner ,M arkus G ross .R ea l T i m e V o l um etr i c Intersecti ons of D efor m i ng O b j ects C .Proceed i ng s o f V isi on ,M odeli ng ,V i sualizati onVM V 03.G er m any M un i ch :VM V2003,2003,46146820Bruno H e ide l berg er ,M atth i

31、 as T eschner M arkus ,G ross .detecti on of co llisi on and se lf-co llisi ons using i m age -space techn i ques C .P roceed i ngs of W inter Schoo l o f Co m puter G raphics 04.Bohem i a :UN ION A gency -Sci ence P ress ,2004,14515221范昭煒,萬(wàn)華根,高曙明.基于流的實(shí)時(shí)碰撞檢測(cè)算法J.軟件學(xué)報(bào),2004,15(10:1505151422魏迎梅.虛擬環(huán)境中碰撞檢

32、測(cè)問(wèn)題的研究D .長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2000,556223Stephane Guy ,G illes D ebunne .M onte -C arlo collisi ondetectionR .http :/a rti s .i m ag .fr/Publi cations /2004/GD 04/,2005-11-30(上接第7頁(yè) 圖7 經(jīng)JPEG 壓縮后的載體圖像及提取的水印信息6 小結(jié)本文提出了一種結(jié)合小波變換和離散余弦變換的數(shù)字水印算法,同時(shí)對(duì)水印圖像進(jìn)行了二維混沌映射的置亂加密,增強(qiáng)了水印的安全性。而在水印的嵌入過(guò)程中,對(duì)于圖像中不同大小的變換系數(shù),采用不同的水印嵌入公式,很

33、好的增強(qiáng)了水印的不可見(jiàn)性和魯棒性。實(shí)驗(yàn)表明,在嵌入的水印信息量達(dá)到原始載體圖像的25%的時(shí)候,對(duì)載體圖像經(jīng)過(guò)各種攻擊仍然能夠很好的檢測(cè)出水印信息;如果將嵌入的水印信息量減少到載體圖像的12.5%(即32 32時(shí),將更能夠增強(qiáng)水印的不可見(jiàn)性和魯棒性。由實(shí)驗(yàn)可看出,本算法對(duì)JPEG 壓縮、噪音攻擊及剪切攻擊有比較好的魯棒性。參考文獻(xiàn)1杜華狄 趙玉華 何甲興一種基于雙正交小波變換的圖像數(shù)字水印算法J.計(jì)算機(jī)與數(shù)字工程2006,34(3:38402陳俊文 楊樹(shù)堂 倪佑生須則中基于DCT 變換的圖像類水印認(rèn)證算法J.上海交通大學(xué)學(xué)報(bào)2006,40(1:41453朱從旭陳志剛基于D W T 域的混沌置亂二

34、值圖像數(shù)字水印新算法J.小型微型計(jì)算機(jī)系統(tǒng)2005,26(7:124112454Z .H.W ei P.Q i n Y.Q.Fu P erceptual d i g ita lw ater m arki ngo f i m ages usi ng wave l e t transfor m J.I EEE T ransacti ons on Cons ume r E l ectronics ,2002,44(4:126712725Cox I J ,K ilian J ,Le i ghton T ,et a l.Secure spreadspectru m w ate r m ark i ng

35、for m ulti m edia J .IEEE T rans I m age P rocessi ng ,1997,87:1673168728虛擬環(huán)境中的軟體碰撞檢測(cè)技術(shù)綜述第35卷2 system s In th is pape r accord ing to the p rm e num ber . i rep resenta tion of Su rnam e C hen to mp rove the m e thod i o f the ca l u l ti n sa fety p rme num ber to increase speed c a o i o f the RSA

36、 and the ir RSA a lgor ithm is app lied in the TA IS, and the d i ital signature of the ne t rk t decl g wo ax a ration is ach ieved in the end. K ey word s RSA, safe ty Prm e Nu be r algo rith Taxa i m , m, tion Ad m in istr tion In fo r tion System i a ma ( Page 19 : R esearch of th e Data In tegr

37、ation in th e Con vergence of G IS and SCADA Syste s m by Zhu Y i Abstrac t Th is paper ana l ses the conve rgence o f G IS y and SCADA syste s fro the ang le o f the data i teg r m m n a tion dem onstra tes the p rincip l , way and the techn ique , e o f the interface . K ey word s Geograph i In f

38、r ation System, Supe rviso c om ry and Data A cqu isition integ rat i n conve rgence , o, ( Page 22 : Collision De tection for D efor ab le O bjects in V irtual E n m v ironm en t by L iang X iaohong Abstrac t R esearch of co llision detection for de fo r ab le ob m jects is scarce especially on the

39、 accuracy o f co llision de tec , tion T his paper summa rizes the m a in Bounding V o lum e H ier . a rchies Spa tia l Subdiv ision, S tochastic M e thods, D istance , F ields and I age- Space T echn iques of co llision detection for m defor able object Based on consideration of computational e f m

40、 . fic iency and accu racy o f co llision detection, the advantages and shortages o f all these a lgo rithm s are ana lyzed, and the key prob lem and d ifficu lty of the resea rch are po inted out . K ey word s v irtual environmen t co llisi n de tection al , o , go rith m, com putat i na l effic i

41、ncy, accuracy ( Page 24 o e : R esearch of Exam ination PoolM anage ent and R ecord A m nalysis Syste m by XueJ in Abstrac t Th is system is deve loped in V isua l Basic lan guage and Access Database The system can copy a ll . sub jects te st includ ing characte r g r , aph ics and for u la m autom

42、atica lly and gene rate d iffe ren t exam inat i n poo.l o Fu rther o re the system can browse rev ise and de lete m , , the exam i at i n question It can a lso p roduce test ques n o . tion in stipu l t i n for a o m. It can count ana lyse and ap , p raise the exam inat i n result produce test ana

43、lysis doc o , um ents in stipu l tion f r and p rint th roug h W ord. Th is a om soft re m akes gene rating test pape r and reco rd ana ly wa s is au toma tica lly be true finally. K ey word s Exam i ation poo,l V isua l Bas i l nguage Re n c a , co rd ana lys is ( Page 29 : Deve lopm en t and Futu

44、re T rend of ROC Analyz ing Tech nology by Tu Fuquan Abstrac t T h is paper e labo ra tes the concept of ROC ana lyzing technigue introduces a few of me thods about current RO C a , nalysis A to m any Tw in, HTM, I : , mproved HTM, M ossm an, the Expanded AU C ( the A rea U nde r the RO C etc It ana

45、 ly . zes ex isting shortage of these m ethods, predicts future deve lop m ent trend of the ROC. K ey words ROC, standard o f eva luation AU C , ( P ag e 33 : Th e Con tact Ana lysis and Study of Conveyor B ush- roller Chain in Cooling T ran spor ter by L iu H airong Abstract A su ite o f functions

46、to ca l u l te the stress c a b rought by the e ffects of the append i g dynam ica l l ad n o p roduced by the acce le r ting speed o f m esh be t a ween the cha in and sprocke t whee l has been p roved to be nece ssary and usab l through ana l sis and instance Fur e y . the r m o re based on I- DEA

47、S 9 0, the con t , . act streng th be t ween the ro ll r and sprocke t w hee l and the con tact e streng th between the sha ft p l g and sleeve pa rts has u been ana lyzed wh il i m eshing p rocess. e n K ey words Chain d rive, Dynam ic load Me sh cha r , acte r , Ana l sis o f contact y ( Page 38 :

48、 Analysis of Ill- posed An isotrop ic D iffusion Based on E n ergy Fun ction by J iang M in Abstract In th is pape r the behavio r o f the ill- posedn , ess o f the an isotrop ic d iffus i n is analyzed through the o ene rgy function W e choose som e p rope r coe ffi ients . c based on the we ll- po sedness and com pa re them using d iffe rent d iffusion str teg ies Expe rm enta l result shows a . i that the sta ircas i g e ffect does not ex ist using the m n i p roved coe fficien ts . K ey word s an isotrop ic d iffusion ene rgy func tion