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