談虛擬現(xiàn)實(shí)中的碰撞檢測(cè)問(wèn)題(打)_圖文

1、第17卷第6期 2009年11月河南機(jī)電高等專(zhuān)科學(xué)校學(xué)報(bào)Jou r n al ofH enan M echan ical and E lectricalE ngi neeri ng C oll egeV o. l 17! . 6N ov . 2009談虛擬現(xiàn)實(shí)中的碰撞檢測(cè)問(wèn)題鐘 帥(揚(yáng)州職業(yè)大學(xué), 江蘇揚(yáng)州225009*摘要:虛擬現(xiàn)實(shí)環(huán)境中的碰撞檢測(cè)是計(jì)算機(jī)圖形學(xué)、計(jì)算幾何、仿真建模和機(jī)器人路徑規(guī)劃等領(lǐng)域的重要問(wèn)題。文章討論了碰撞檢測(cè)過(guò)程中的算法和包圍盒樹(shù)的交疊測(cè)試時(shí)間以及碰撞檢測(cè)的優(yōu)化手段, 進(jìn)一步提高了碰撞檢測(cè)的效率。關(guān)鍵詞:虛擬現(xiàn)實(shí); 碰撞檢測(cè); 包圍盒; 交疊測(cè)試中圖分類(lèi)號(hào):TP 33

2、3. 96 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1008-2093(2009 06-0107-031 引言虛擬現(xiàn)實(shí)(V irtual R ea lity , 簡(jiǎn)稱(chēng)VR 是指通過(guò)人的多種感知通道(視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)、嗅覺(jué)、味覺(jué)等 進(jìn)1行實(shí)時(shí)模擬與交互的高級(jí)人機(jī)交互系統(tǒng)。虛擬現(xiàn)實(shí)又可稱(chēng)為人工現(xiàn)實(shí)(A rtificia l R ea lity 、虛擬環(huán)境(Virtua lEnviron m ent 等。VR 技術(shù)的主要目標(biāo)之一是允許用戶(hù)以盡可能自然的方式與虛擬世界直接交互。因此VR 系統(tǒng)的用戶(hù)希望虛擬物體給人的感覺(jué)是 物理存在 。當(dāng)參與者伸手去拿一個(gè)杯子, 系統(tǒng)必須能檢測(cè)到手和杯子之間有接觸后, 才能進(jìn)一步仿真

3、拿起一個(gè)杯子的情景。因此VR 中動(dòng)態(tài)物體與靜態(tài)物體之間或動(dòng)態(tài)物體與動(dòng)態(tài)物體之間的交互基礎(chǔ)是碰撞檢測(cè)。在虛擬現(xiàn)實(shí)技術(shù)中, 把這種用戶(hù)與虛擬物體或虛擬物體之間的接觸、碰撞關(guān)系的建立稱(chēng)為碰撞檢測(cè)(Co llision Detecti o n 。碰撞檢測(cè)是虛擬場(chǎng)景實(shí)時(shí)漫游和人機(jī)交互必不可少2的一部分, 是仿真物體間進(jìn)行交互的先行步驟。2 碰撞檢測(cè)的實(shí)現(xiàn)方法最原始簡(jiǎn)單的碰撞檢測(cè)方法是一種蠻力的計(jì)算方法, 即對(duì)兩個(gè)幾何模型中的所有幾何元素進(jìn)行兩兩相交測(cè)試, 盡管這種方法可以得到正確的結(jié)果, 但當(dāng)模型的復(fù)雜度增大時(shí), 它的計(jì)算量很大, 測(cè)試將十分緩慢。碰撞檢測(cè)一直是虛擬交互技術(shù)研究的關(guān)鍵問(wèn)題。許多學(xué)者在碰撞

4、檢測(cè)方面進(jìn)行了廣泛、深入的研究, 并提出了多碰撞檢測(cè)的算法。現(xiàn)有的碰撞檢測(cè)算法主要為兩大類(lèi):層次包圍盒法和空間分解法。2. 1 層次包圍盒層次包圍盒是碰撞檢測(cè)算法中廣泛使用的一種算法, 它是解決碰撞檢測(cè)問(wèn)題固有時(shí)間復(fù)雜性的一種有效的方法。它的基本思想是利用體積略大而幾何特征簡(jiǎn)單的包圍盒來(lái)近似地描述復(fù)雜的幾何對(duì)象(如2圖1 , 由于包圍盒形狀比較簡(jiǎn)單, 計(jì)算容易, 一旦發(fā)現(xiàn)包圍盒沒(méi)有碰撞就可以排除兩物體之間的碰撞, 比直接用兩物體進(jìn)行計(jì)算節(jié)省了大量的時(shí)間, 所以提高了碰撞檢測(cè)的效率, 當(dāng)然檢測(cè)到包圍盒發(fā)生了碰撞, 并不意味著物體之間一定發(fā)生了碰撞, 若此時(shí)系統(tǒng)欲得到精度更高的檢測(cè)結(jié)果, 還需對(duì)物

5、體之間的位置關(guān)系進(jìn)一步計(jì)算, 即進(jìn)行碰撞的精確檢測(cè)。采用包圍盒進(jìn)行碰撞檢測(cè)的最大好處是可以實(shí)現(xiàn)快速碰撞檢測(cè), 包圍盒樹(shù)可以按照自下而上的方式或者自上而下的方式構(gòu)造, 這要取決于包圍盒的種類(lèi)和算法的意圖。大多數(shù)層次結(jié)構(gòu)都采用自上而下的方式, 即首先建立模型的包圍盒, 作為包圍盒樹(shù)的根節(jié)點(diǎn); 然后按照一定的規(guī)則將模型分成兩個(gè)或者多個(gè)部分, 建立每個(gè)部分的包圍盒和相應(yīng)的節(jié)點(diǎn), 將這些新節(jié)點(diǎn)作為根節(jié)點(diǎn)的子節(jié)點(diǎn); 依次按照第二步的方法分裂每個(gè)子節(jié)點(diǎn)對(duì)應(yīng)的模型, 遞歸地建立包圍盒樹(shù)。比較典型的包圍盒類(lèi)型有沿坐標(biāo)軸的包圍盒AABB 、包圍球、方向包圍盒、固定方向凸包等。層次包圍盒方法應(yīng)用得較為廣泛, 適用復(fù)

6、雜環(huán)境中的碰撞檢測(cè)。*收稿日期:2009 04 16作者簡(jiǎn)介:鐘帥(1981 , 男, 江蘇泰州人, 助教, 本科, 主要從事計(jì)算機(jī)應(yīng)用研究。 河南機(jī)電高等專(zhuān)科學(xué)校學(xué)報(bào) 2009年6期圖1 包裝盒結(jié)構(gòu)層次示例2. 2 空間分解法空間分解法是將整個(gè)虛擬空間劃分成相等體積的單元格, 只對(duì)占據(jù)同一單元格或相鄰單元格的幾何圖2 層次包圍盒的交疊測(cè)試3. 2 交疊測(cè)試的算法使用層次OBB 進(jìn)行碰撞檢測(cè), 其目的是通過(guò)兩個(gè)對(duì)象進(jìn)行相交測(cè)試。首先利用空間區(qū)域劃分, 迅速剔對(duì)象的包圍盒樹(shù)中各結(jié)點(diǎn)所對(duì)應(yīng)的OBB 包圍盒之間除不相鄰的物體, 這一點(diǎn)能有效地解決時(shí)空相關(guān)性對(duì)的重疊測(cè)試, 盡可能早地排除所有不可能相交

7、的基本存在高速運(yùn)動(dòng)物體的情況不適用的問(wèn)題, 同時(shí)找出可圖元對(duì), 僅對(duì)有可能相交的基本圖元對(duì)進(jìn)行精確的相能發(fā)生碰撞的物體對(duì); 然后在物體的內(nèi)部結(jié)構(gòu)中增加交測(cè)試。因此, 包圍盒之間的交疊測(cè)試的速度直接影一個(gè)鏈表, 用于存放與此物體相鄰的需要與其進(jìn)行碰響到碰撞檢測(cè)的速度。撞檢測(cè)的其他物體; 在碰撞檢測(cè)的時(shí)候, 設(shè)置一個(gè)閾OBB 包圍盒間的重疊測(cè)試是基于分離軸理論的。值, 這個(gè)閾值可以使得在最有效的情況下利用時(shí)空相若一對(duì)OBB 間存在一條分離軸, 則可以判定這兩個(gè)關(guān)性來(lái)檢測(cè)碰撞。比較典型的方法有K -D 樹(shù)、八叉OBB 不重疊。對(duì)任何兩個(gè)不相交的凸三維多面體, 其樹(shù)和BSP 樹(shù)、四面體網(wǎng)、規(guī)則網(wǎng)等?？?/p>

8、間分解法通常分離軸要么垂直于任何一個(gè)多面體的某一個(gè)面, 要么適用于稀疏的環(huán)境中分布比較均勻的幾何對(duì)象的碰同時(shí)垂直于每個(gè)多面體的某一條邊。因此, 對(duì)于一對(duì)撞檢測(cè)3。3 包圍盒樹(shù)的交疊測(cè)試3. 1 交疊測(cè)試的時(shí)間OBB , 只需測(cè)試15條可能是分離軸的軸(每個(gè)OBB 的3個(gè)面方向再加上每個(gè)OBB 的3個(gè)邊方向的兩兩組合, 只要找到一條這樣的分離軸, 就可以判定這兩個(gè)OBB 是不重疊的, 如果這15條軸都不能將這兩個(gè)5, L 是OBB 包圍使用包圍盒法進(jìn)行碰撞檢測(cè)的時(shí)間主要由三部OBB 分離, 則它們是重疊的, 如圖3分組成:包圍盒構(gòu)造時(shí)間Tc , 包圍盒更新時(shí)間T r , 交疊盒A 和B 的分離軸

9、。測(cè)試時(shí)間T t 。交疊測(cè)試時(shí)間T t 是指在實(shí)時(shí)碰撞檢測(cè)過(guò)程中測(cè)試物體的包圍盒對(duì)是否發(fā)生碰撞的時(shí)間。例如測(cè)試手術(shù)刀的包圍盒是否與被切割組織的包圍盒是否發(fā)生交疊的時(shí)間。交疊測(cè)試時(shí)間是實(shí)時(shí)檢測(cè)效率的決定因素, 是衡量層次包圍盒法進(jìn)行碰撞檢測(cè)性能優(yōu)劣的關(guān)鍵。交疊測(cè)試的時(shí)間可以由如下公式(1 來(lái)計(jì)算4:包圍盒法采用的基本思想是使用簡(jiǎn)單的幾何體來(lái)代替復(fù)雜的幾何體, 這樣可以排除大量不可能相交參與測(cè)試的包圍盒對(duì)的總數(shù)目; C v 是測(cè)試一對(duì)包圍盒的幾何體, 可以大大地提高碰撞檢測(cè)的效率?；趯有枰臅r(shí)間; N p 是待檢測(cè)包圍盒對(duì)數(shù); C p 是檢測(cè)一次包圍盒的算法核心就是:通過(guò)遍歷這兩棵樹(shù), 確定對(duì)包

10、圍盒是否發(fā)生碰撞的時(shí)間; N u 是發(fā)生形變的包圍在當(dāng)前位置下, 兩個(gè)對(duì)象是否發(fā)生碰撞。這是一個(gè)雙盒數(shù)目; C u 是更新一個(gè)發(fā)生形變的包圍盒的平均時(shí)重遍歷的過(guò)程, 算法首先用一個(gè)對(duì)象的根節(jié)點(diǎn)遍歷另間(如圖2 。我們可以看到, 對(duì)于固定的待檢測(cè)對(duì)一個(gè)對(duì)象的包圍盒樹(shù), 如果能到達(dá)葉節(jié)點(diǎn), 再用該葉象, N v 是一個(gè)定值。提高包圍盒的復(fù)雜度, 也就是加節(jié)點(diǎn)遍歷第一個(gè)對(duì)象的包圍盒樹(shù), 如果也能到達(dá)該對(duì)強(qiáng)包圍盒的緊密性能使得C v 增大, 而相反減小了N p 。象的葉節(jié)點(diǎn), 則進(jìn)一步進(jìn)行三角形的相交測(cè)試。如果T t =N v C v +N p C p +N u C u 公式(1 如式(1 中, T

11、t 是交疊測(cè)試的總時(shí)間, N v 是需要圖3 OBB 包圍盒示意鐘帥:談虛擬現(xiàn)實(shí)中的碰撞檢測(cè)問(wèn)題兩個(gè)節(jié)點(diǎn)上的包圍盒不相交, 則它們所包圍的三角形的子集必定不相交, 從而不需要對(duì)子集中的元素作進(jìn)一步的相交測(cè)試。其偽代碼如下:F i n dFirst H it C D (A,B Retur n(TRUE , F ALSE 1:if(isLea f(A and isLeaf(B /A、B 都是葉節(jié)點(diǎn)2:fo r 每一個(gè)三角形對(duì)TA #AC 并且TB #BC 3:if(overlap(TA, TB TRUE ; 4:e lse if(is No t L eaf(A and is Not L eaf(B

12、 /A、B 都不是葉節(jié)點(diǎn)5:if(Volu m e(A >Vo l u m e (B /為了獲得更好的性能6:fo r 每個(gè)子節(jié)點(diǎn)CA #AC 7:F i n dF irst H itCD(CA, B 8:e lse 9:fo r 每個(gè)子節(jié)點(diǎn)CB #BC 10:F i n dFirst H it C D (A,CB 11:else if(isLeaf(A and is NotLeaf(B /A是葉節(jié)點(diǎn), B 不是12:for 每個(gè)子節(jié)點(diǎn)CB #BC 13:F i n dFirst H it C D (CB , A 14:else15:for 每個(gè)子節(jié)點(diǎn)C A #AC 16:F i n d

13、First H it C D (C A, B /B是葉節(jié)點(diǎn), A 不是17:retur n FALSE ;要的字節(jié)數(shù)。在VR M L 中默認(rèn)情況下, 碰撞檢測(cè)是打開(kāi)的, 為了提高渲染的速度, 對(duì)于用戶(hù)沒(méi)有可能接觸到的幾何節(jié)點(diǎn)可以關(guān)閉碰撞檢測(cè)。如瀏覽者的瀏覽方式被定為EXAM I N E 時(shí), 可以將場(chǎng)景中的物體的碰撞檢測(cè)關(guān)閉。瀏覽方式為WALK 時(shí), 瀏覽者不能離開(kāi)地面, 對(duì)于位置較高的物體也應(yīng)該關(guān)閉碰撞檢測(cè)。要關(guān)閉一個(gè)幾何節(jié)點(diǎn)的碰撞檢測(cè), 可以將幾何節(jié)點(diǎn)放入Co lli sion 的chil d ren 域中, 將co lli d e 設(shè)為false 即可。在必須保留碰撞檢測(cè)的情況下, 可以

14、對(duì)復(fù)雜的節(jié)點(diǎn)使用碰撞代理。直接的碰撞檢測(cè)是依據(jù)幾何體的外形進(jìn)行的, 如果幾何體過(guò)于復(fù)雜, 碰撞檢測(cè)效率將變得很低。碰撞代理利用一個(gè)簡(jiǎn)單的幾何體, 如box 、sphere 作為碰撞檢測(cè)的邊界。利用碰撞代理作碰撞檢測(cè)要快得多。使用碰撞代理只要在proxy 域中指定一個(gè)能將ch il d ren 域中所有的節(jié)點(diǎn)包圍的簡(jiǎn)單幾何體就可以了。5 結(jié)束語(yǔ)虛擬現(xiàn)實(shí)場(chǎng)景的碰撞檢測(cè)是虛擬現(xiàn)實(shí)系統(tǒng)的關(guān)鍵問(wèn)題, 在虛擬場(chǎng)景中的實(shí)現(xiàn)有效的碰撞檢測(cè)也是當(dāng)今虛擬現(xiàn)實(shí)研究的一個(gè)重點(diǎn)和熱點(diǎn)。碰撞檢測(cè)應(yīng)用范圍相當(dāng)廣泛, 特別是在各種仿真模擬試驗(yàn)中, 起著十分重要的作用。而精確的結(jié)果往往需要引入連續(xù)碰撞檢測(cè)算法。如何加速連續(xù)碰撞

15、檢測(cè), 實(shí)現(xiàn)快速精確的碰撞仿真模擬成為眾多研究者關(guān)注的領(lǐng)域之一。(責(zé)任編輯 呂春紅參考文獻(xiàn):1汪成為, 高文, 王行仁著. 靈境(虛擬現(xiàn)實(shí) 技術(shù)的理論、實(shí)現(xiàn)及應(yīng)用M.北京:清華大學(xué)出版社, 1996.2魏迎梅, 吳泉源, 石教英. 碰撞檢測(cè)中的固定方向凸殼包圍盒的研究J.軟件學(xué)報(bào), 2001, (7.3劉惠義, 邱云, 張春紅. 虛擬視景交互漫游系統(tǒng)的實(shí)時(shí)碰撞檢測(cè)方法研究J.河海大學(xué)學(xué)報(bào)(自然科學(xué)版. 2005, (3.4丁佳. 大型復(fù)雜場(chǎng)景中快速碰撞檢測(cè)技術(shù)的研究D .成都電子科技大學(xué), 2007.5丁志磊. 基于OBB 包圍盒的快速碰撞檢測(cè)D .蘭州理工大學(xué),2006.4 碰撞檢測(cè)的優(yōu)化措

16、施層次包圍盒結(jié)構(gòu)是最常使用的碰撞檢測(cè)結(jié)構(gòu)。雖然在任意幾何體之間進(jìn)行碰撞檢測(cè)時(shí), 使用層次包圍盒結(jié)構(gòu)的效率較高, 但它仍舊有一個(gè)較大的問(wèn)題就是內(nèi)存需求。隨著模型復(fù)雜度的加大, 層次包圍盒樹(shù)所需要的內(nèi)存空間也迅速增加。減少內(nèi)存需求的常用方法有兩種, 一是讓葉節(jié)點(diǎn)包含多個(gè)圖元, 這樣就可以使BV 樹(shù)的深度比完全樹(shù)的深度小; 第二種方法是減少每個(gè)內(nèi)部節(jié)點(diǎn)需要的字節(jié)數(shù)和每個(gè)葉節(jié)點(diǎn)需Disc ussi on on So me Proble ms of t he Collision Exa m i nes i n t he V irtualRealit yZ HONG Shuai(Yangzhou Poly

17、techn ic Co llege , Y angzhou 225009, Ch i n aAbst ract :I n the v irtual reality env iron m ent co llision exa m inati o n is do m a i n and so on co m puter graph ics , co m putation geo m etry , si m ulation m ode li n g and robotw ay plan i m portant questi o ns . This paper d iscussed the co llision to exa m i n e the opti m ized m ethod w hich i n the process the alg