【文章內(nèi)容簡(jiǎn)介】 上改變實(shí)體的運(yùn)動(dòng)狀態(tài)。在虛擬現(xiàn)實(shí)系統(tǒng)中一般通過(guò)檢測(cè)兩個(gè)實(shí)體所占的幾何空間是否相交 來(lái)判斷是否發(fā)生碰撞。在現(xiàn)實(shí)世界中，每個(gè)實(shí)體都占有一定幾何空間，而且不可能出現(xiàn)兩個(gè)實(shí)體相互穿透的現(xiàn)象。當(dāng)虛擬現(xiàn)實(shí)系統(tǒng)中兩個(gè)實(shí)體所占有的幾何空間試圖相互穿透時(shí)，系統(tǒng)就認(rèn)為這兩個(gè)實(shí)體發(fā)生了碰撞。 如果有四維空間來(lái)描述運(yùn)動(dòng)實(shí)體，前三維是通常意義上的三維空間，第四維是時(shí)間，那末一個(gè)實(shí)體就可以用四維空間中的點(diǎn)集來(lái)描述，即： ? ?( , ) | ( )( )x t x L t S? 其中 ： S 是構(gòu)成實(shí)體的三維空間點(diǎn)集， L(t)是確定實(shí)體 t 時(shí)刻空間位置的函數(shù)。通過(guò)L(t)(S)可以給出三維空間點(diǎn)集中每個(gè)點(diǎn) t 時(shí)刻的位置。假設(shè) 用四維空間中的點(diǎn)集 S1*和S2 *來(lái)描述兩個(gè)實(shí)體 S1 和 S2 以及它們的運(yùn)動(dòng)，則碰撞檢測(cè)可以描述為在某時(shí)刻某兩個(gè)實(shí)體所占空間位置的關(guān)系，即： 對(duì)于 ( , )xt ,有 ( , )xt? S1*和 ( , )xt? S2*，當(dāng)且僅當(dāng) S1* ? S2* ? ? 時(shí)，發(fā)生碰撞。 碰撞檢測(cè)的模型類別 虛擬環(huán)境中的物體所用的模型大體分為面模型和體模型兩大類。面模型用物體的邊界來(lái)表示物體，而不包括物體內(nèi)部信息。體模型采用體元來(lái)表示物體，可描述物體的內(nèi)部信息。體模型所耗存儲(chǔ)量大，計(jì)算量也大。而面模型的研究和應(yīng)用比體模型的成熟多。由于凸多面體有很好的性質(zhì)，因而可以獲得較高效率的基于凸多面體的碰撞檢測(cè)算法。對(duì)于一般的 體 ，由于處理相對(duì)比較復(fù)雜，往往采用將一般的體分解成幾個(gè)凸多面體再進(jìn)行逐個(gè)碰撞檢測(cè)。 所以碰撞檢測(cè)的研究工作大多是基于面模型的，少數(shù)是基于體模型的。 面模 型又可進(jìn)一步分為很多種，如多面體模型、 CSG、隱式曲面、參數(shù)化曲面等。 9 其中，最常用的一種是多面體模型，特別是三角形模型。多面體模型是一種簡(jiǎn)潔，通用的表示方法，幾乎應(yīng)用于表示任何形狀的物體，而且便于操作，易于實(shí)現(xiàn)硬件加速。 多面體模型又有多種形式，碰撞檢測(cè)算法也可能對(duì)模型的形式有要求，如很多 算法要求輸入模型是實(shí)體，即可表示成閉合曲面，其中，不少算法利用物體的凸性來(lái)加速，因而進(jìn)一步要求輸入模型是凸多面體，對(duì)非凸多面體則做特殊處理；另一些算法對(duì)輸入模型則不做特殊處理要求，輸入模型被表示成一組無(wú)拓?fù)浼s束的三角片，這 類算法通用性比較好。本論文輸入模型便是一組無(wú)拓?fù)浼s束的三角片。 碰撞檢測(cè)的場(chǎng)景特征 [2] 場(chǎng)景可按物體的運(yùn)動(dòng)狀態(tài)分為靜態(tài)部分和動(dòng)態(tài)部分，靜態(tài)部分間的碰撞檢測(cè)可離線計(jì)算，而動(dòng)態(tài)部分如果事先能知道物體的運(yùn)動(dòng)軌跡，其碰撞檢測(cè)可離線計(jì)算。但是虛擬環(huán)境是一個(gè)實(shí)時(shí)交互系統(tǒng)，物體的運(yùn)動(dòng)軌跡一般是未知的，故碰撞檢測(cè)要實(shí)時(shí)地進(jìn)行。在虛擬環(huán)境中有些物體是靜態(tài)的，有些物體是動(dòng)態(tài)的，動(dòng)態(tài)物體越多，碰撞發(fā)生的概率越大，其碰撞檢測(cè)的復(fù)雜程度越高。 場(chǎng)景中的運(yùn)動(dòng)物體還可分為剛體和柔體，剛體物體在運(yùn)動(dòng)中不改變物體形狀，其運(yùn)動(dòng)形式局限 于平移和旋轉(zhuǎn)；柔體 物體在運(yùn)動(dòng)中會(huì)改變物體的形狀，其運(yùn)動(dòng)形式除了平移、旋轉(zhuǎn)還有變形，如心臟的跳動(dòng)。 故柔體物體的碰撞檢測(cè)比剛體要復(fù)雜得多。在本論文中我們只針對(duì)剛體物體進(jìn)行碰撞檢測(cè)。 碰撞檢測(cè)技術(shù)的基本原理 如果兩個(gè)安全封閉的多面體發(fā)生相互碰撞時(shí)，其中一個(gè)多面體至少會(huì)有一個(gè)面與另一個(gè)多面體的至少一個(gè)面發(fā)生相交。若能在碰撞發(fā)生時(shí)，立刻檢測(cè)到相交，然后將兩個(gè)物體的位置稍做調(diào)整，可消除碰撞現(xiàn)象。如下是碰撞檢測(cè)基本算法描述： 設(shè)在一虛擬環(huán)境中要仿真 n 個(gè)物體： A1,A2……,An, 其對(duì)物體的仿真過(guò)程是逐幀計(jì)算的，從 T0 到 T1 按時(shí)間步長(zhǎng) dT 進(jìn)行計(jì)算。 //在虛擬環(huán)境中調(diào)用碰撞檢測(cè)過(guò)程 [2] Simulation() { … 10 for (T=T0 to T1,步長(zhǎng)為 dT) do { 獲得用戶的輸入； 更新 A1,A2…,An 各物體的行為； if (collisionDetect(T,{A1,A2…,An} 找到了碰撞 ) then 計(jì)算碰撞反應(yīng)； 繪制 n 個(gè)物體 A1,A2…,An } } //碰撞檢測(cè)過(guò)程， Tprev 為全局變量，初值為（ T0dT） ,dt 為碰撞檢測(cè)的步長(zhǎng)， collisionDetect（ Tcurr, {A1,A2…,An} ） { for (t=Tprev to Tcurr,步長(zhǎng)為 dt) do { for ({A1,A2…,An} 中每個(gè)物體 Ai) do 移動(dòng) Ai 到其在時(shí)間 t 的位置 。 for({A1,A2…,An} 中每個(gè)物體 Ai) do for({Ai+1,…An} 中每個(gè)物體 Oj) do if (Oi 與 Oj 相交 ) then 報(bào)告在時(shí)間 t 發(fā)生了碰撞； } Tprev = Tcurr； } 以上是碰撞檢測(cè)思想的一種最基本的方法，在實(shí)際應(yīng)用過(guò)程中可以根據(jù)需要對(duì)該方法進(jìn)一步改進(jìn)，以得到更高效的碰撞檢測(cè)算法。 11 第三章 碰撞檢測(cè)算法 由于碰撞檢測(cè)的重要應(yīng)用，人們對(duì)它進(jìn)行了廣泛而深入的研究，算法種類也很多。在很多時(shí)候，對(duì)碰撞檢測(cè)實(shí)時(shí)性要求很強(qiáng)，需要碰撞檢測(cè)的幾何模型集合中模型復(fù)雜且很多，在這種情況下，一般是針對(duì)虛擬場(chǎng)景的特點(diǎn)、幾何模型的幾何與運(yùn)動(dòng)等特點(diǎn)設(shè)計(jì)可高效應(yīng)用于該虛擬場(chǎng)景的算法，如有些算法適用于凸多面體幾何模型、有些適用于可運(yùn)動(dòng)模型少的虛擬場(chǎng)景。 然而 還沒(méi)有能夠滿足所有情況的通用碰撞檢測(cè)算法。 空間剖分法 空間剖分法通常將空間剖分成均勻的單元，每個(gè)物體對(duì)應(yīng)一個(gè)或多個(gè)單元中，只有當(dāng)物體處于同一單元空間中才 可能相交，這時(shí)應(yīng)該對(duì)該單元空間進(jìn)行精確的碰撞檢測(cè)。采用空間剖分思想 [19]的算法一般用樹(shù)的方式逐步分割空間，可以進(jìn)一步加速碰撞檢測(cè)。常用的空間剖分方法是 BSP[4]、八叉樹(shù) [5]（如圖 31）、 均勻網(wǎng)格 [6]、 3d 樹(shù) [7]。八叉樹(shù)用樹(shù)的結(jié)構(gòu)表示空間的分解情況，根是整個(gè)空間，將每個(gè)父結(jié)點(diǎn)空間用三個(gè)分別與 坐標(biāo)軸垂直的分割面分成大小相等的八份，每一份作為它的一個(gè)子結(jié)點(diǎn)， 分割不斷進(jìn)行直到與子結(jié)點(diǎn)相交的三角形數(shù)目小于一個(gè)閾值或者與子結(jié)點(diǎn)相交的三角形屬于同一模型，該子結(jié)點(diǎn)成為一個(gè)葉結(jié)點(diǎn)；如果來(lái)自兩個(gè)模型的三角形與同一 個(gè)葉結(jié)點(diǎn)相交，那末需要對(duì)這兩個(gè)模型進(jìn)行碰撞檢測(cè)。 BSP 樹(shù)與八叉樹(shù)相似，但是二叉樹(shù)。 3d 樹(shù)是一種特殊的 BSPs樹(shù)，用來(lái)分割空間的分割面都是與某一個(gè)坐標(biāo)軸垂直的。一般，空間剖分算法在每次碰撞檢測(cè)時(shí)都需要確定每個(gè)模型占有的空間單元，如果場(chǎng)景中不可動(dòng)的模型很多，可以預(yù)先劃分好空間單元并計(jì)算出每個(gè)模型占有的空間單元，當(dāng)有模型運(yùn)動(dòng)時(shí)，只要重新計(jì)算運(yùn)動(dòng)模型占有的空間單元就可以。所以空間剖分算法比較適合用于 稀疏的環(huán)境中分布比較均勻的幾何對(duì)象間的碰撞檢測(cè) ，如圖 32。 12 圖 31 八叉樹(shù) 圖 32 空間剖分法在 場(chǎng)景中的應(yīng)用 包圍盒層次樹(shù)法 另一種常用方法是包圍盒，包圍盒方法 被廣泛應(yīng)用于對(duì)光 線 跟蹤和求交運(yùn)算的加速 。其基本思路是用體積略大而幾何特性簡(jiǎn)單的 包圍盒將復(fù)雜的幾何形體圍住，當(dāng)對(duì)兩個(gè)物體做碰撞檢測(cè)時(shí)，首先檢測(cè)包圍盒是否相交，若不相交，則兩個(gè)物體不相交。反之，需要進(jìn)一步對(duì)兩個(gè)物體進(jìn)行精確檢測(cè)，此方法可以快速排除不相交的物體，加速了算法。與一個(gè)物體相對(duì)應(yīng)的層次樹(shù)的結(jié)點(diǎn)是空間上包圍該物體一部分幾何結(jié)構(gòu)的幾何近似 體 ：層次樹(shù)的根結(jié)點(diǎn)是包圍了整個(gè)物體，每個(gè)父結(jié)點(diǎn)包圍的幾何結(jié)構(gòu)是它所有子結(jié)點(diǎn)包圍的幾何結(jié)構(gòu)之和；結(jié)點(diǎn)從上 到下逐漸逼近它包圍的幾何結(jié)構(gòu)。判斷兩個(gè)模型是否相交時(shí)， 13 首先判斷兩個(gè)層次樹(shù)的根結(jié)點(diǎn)是否相交；如果兩個(gè)父結(jié)點(diǎn)相交，那末將它們的子結(jié)點(diǎn)分別進(jìn)行相交判斷；如果最后有相交的葉結(jié)點(diǎn) 對(duì) ，判斷每對(duì)葉結(jié)點(diǎn)包圍的幾何結(jié)構(gòu)是否相交，如果有相交的幾何結(jié)構(gòu) 對(duì) ，則模型相交，反之不相交。 比較典型的包圍盒類型有 包圍球（ spheres） [8] 、 沿坐標(biāo)軸的 包圍盒 AABB（ axis aligned bounding box） [9]、方向包圍盒 OBB(oriented bounding box)等。 層次包圍盒法則應(yīng)用于復(fù)雜環(huán)境中的碰撞檢測(cè)。 選擇哪種形狀的包圍盒通常取決于應(yīng)用領(lǐng)域及其蘊(yùn)含的不同約束條件。例如 在 光線跟蹤算法中，包圍盒應(yīng)能緊密包圍物體，同時(shí)又便于高效地對(duì)一條光線和包圍盒做求交測(cè)試。 對(duì)于碰撞檢測(cè)算法，可借助一個(gè)耗費(fèi) 函數(shù)來(lái)分析 T N v x C v N p x C p N u x C u? ? ?[2] 其中： T 是碰撞檢測(cè)的總耗費(fèi)； Nv 是參與重疊測(cè)試的包圍盒的對(duì)數(shù)， Cv 是一對(duì)包圍盒做重疊測(cè)試的耗費(fèi)； Np 是參與求交測(cè)試的幾何元的對(duì)數(shù)， Cp 是一對(duì)幾何元做求交測(cè)試的耗費(fèi)； Nu 是物體運(yùn)動(dòng)后包圍盒 層次 需要修改的結(jié)點(diǎn)個(gè)數(shù) ， Cu 是修改一個(gè)結(jié)點(diǎn)的耗費(fèi)； 根據(jù) T 這一耗費(fèi)函數(shù)，可以推測(cè)理想的包圍盒應(yīng)滿足如下要求： ? 在各層次上緊湊地逼近 輸入模型及其子部分，以減少 Nv 、 Np ； ? 支持快速為一對(duì)包圍盒做重疊測(cè)試，以減少 Cv ； ? 當(dāng)物體旋轉(zhuǎn)或平移時(shí)，支持對(duì)其包圍盒層次中結(jié)點(diǎn)的快速修改，以減少 Cu 從上節(jié)知道選擇不同類型的包圍盒直接影響到碰撞檢測(cè)算法的效率。本節(jié)將詳細(xì)介紹一些常用的包圍盒類型 [20]， 并分析各自的優(yōu)缺點(diǎn) 。 1） 沿坐標(biāo)軸 的包圍盒 AABB（ axis aligned bounding boxes） AABB 在碰撞檢測(cè)的研究歷史中使用最悠久，一個(gè) AABB 被定義為包含該對(duì)象且邊 平行于坐標(biāo)軸的最小正六面體。 如圖 33所示，基于 AABB碰撞檢測(cè)系統(tǒng)的有 Icollide[10]、 14 SOLID[11]等。 AABB 間的相交測(cè)試比較簡(jiǎn)單，兩個(gè) AABB 相交當(dāng)且僅當(dāng)在三個(gè)坐標(biāo)軸投影區(qū)間均重疊。但是 AABB 緊密性比較差，尤其是對(duì)于沿斜對(duì)角線放置的瘦長(zhǎng)物體，用 AABB 將留下很大 邊角 空 隙，從而導(dǎo)致大量冗余的包圍盒相交測(cè)試。這樣的話，減少 Cv 、 Cu ， 同時(shí)可能增加 Np 。 圖 33 AABB包圍盒 2） 包圍球（ spheres） 包圍球類似 AABB,是一種簡(jiǎn)單性好緊湊性差的一類包圍盒，包圍球被定義為 包含該對(duì)象的最小球體。如圖 34 所示 圖 34 包圍球包圍盒 包圍球間的相交測(cè)試也相對(duì)比較簡(jiǎn)單。對(duì)于兩個(gè)包圍球 (ｃ 1,ｒ 1)和 (ｃ 2,ｒ 2),如果球心距離小于半徑之和 ,即 |ｃ 1ｃ 2| ＜（ ｒ 1+ｒ 2） ,則兩包圍球相交 ,可進(jìn)一步簡(jiǎn)化為判斷(ｃ 1ｃ 2)(ｃ 1ｃ 2) ＜ (ｒ 1+ｒ 2)2。故包圍球間的相交測(cè)試需要 4 次加減運(yùn)算、 4 次乘法運(yùn)算和 1 次比較運(yùn)算。 包圍球的緊密性在所有包圍盒類型中是比較差的 ,它除了對(duì)在三個(gè)坐標(biāo)軸上分布 的比較均勻的幾何體外 ,幾乎都會(huì)留下很大的空隙 ,通常需要花費(fèi)大量的預(yù)處理時(shí)間以構(gòu)造一個(gè)好的層次結(jié)構(gòu)逼近對(duì)象 ,這在 Hubbard 的工作中得到驗(yàn)證。相對(duì)于 AABB 而言 ,在大多數(shù)情況下包圍球無(wú)論是緊密性還是簡(jiǎn)單性都有所不如 ,因此 ,它是使用得比較少的一種包圍盒。當(dāng)對(duì)象發(fā)生旋轉(zhuǎn)運(yùn)動(dòng)時(shí) ,包圍球不需要 做任何更新 ,這是包圍球比較優(yōu)秀的一個(gè) 15 特性 ,當(dāng)幾何對(duì)象進(jìn)行頻繁的旋轉(zhuǎn)運(yùn)動(dòng)時(shí) ,采用包圍球可能得到較好的結(jié)果。當(dāng)對(duì)象發(fā)生變形時(shí) ,很難從子結(jié)點(diǎn)的包圍球合成父結(jié)點(diǎn)的包圍球 ,只能重新計(jì)算。 3） 方向包圍盒 OBB(oriented bounding box) OBB 是 Gottschalk在 1996 年 實(shí)現(xiàn)的 RAPID 系統(tǒng)中首先使用的 [13],當(dāng)時(shí)該系統(tǒng)聲稱是最快的碰撞檢測(cè)系統(tǒng) ,曾一度作為評(píng)價(jià)碰撞檢測(cè)算法的標(biāo)準(zhǔn)。一個(gè)給定對(duì)象的 OBB 被定義為包含該對(duì)象且相對(duì)于坐標(biāo)軸方向任意的最小的正六面體。 OBB 最大特點(diǎn)是它的方向的任意性 ,這使得 它可以根據(jù)被包圍對(duì)象的形狀特點(diǎn)盡可能緊密地包圍對(duì)象 (如圖 35),但同時(shí)也使得它的相交測(cè)試變得復(fù)雜。 圖 35 OBB方向包圍盒 OBB 的計(jì)算相對(duì)復(fù)雜一些 ,其關(guān)鍵是尋找最佳方向 ,并確定在該方向上包圍對(duì)象的 包圍盒的最小尺寸。 OBB 間的相交測(cè)試基于分離軸理論 。 若兩個(gè) OBB 在一條軸線上 (不一定是坐標(biāo)軸 )上的投影不重疊 ,則這條軸稱為分離軸。若一對(duì) OBB 間存在一條分離軸 ,則可以判定這兩個(gè) OBB 不相交。對(duì)任何兩個(gè)不相交的凸三維多面體 ,其分離軸要么與任一多面 體的某一個(gè)面 垂直 ,要么同時(shí)垂直于每個(gè)多面體的某一條邊。