碰撞檢測中的KDOPS演算法論文

碰撞檢測中的KDOPS演算法論文

　　摘 要 K_DOPS碰撞檢測演算法是一類重要的碰撞檢測演算法，本文從K_DOPS的定義、包圍盒的選擇與計算、包圍盒樹的構造等幾個方面對K_DOPS演算法進行研究，並給出一種快速碰撞檢測演算法並對該演算法進行改進，提高演算法的效率。

　　關鍵詞 碰撞檢測；K_DOPS；包圍盒樹

　　1 引言

　　碰撞檢測問題在計算機圖形學中有很長的研究歷史，近年來，隨著虛擬現實，分佈互動模擬等技術的興起，碰撞檢測再一次成為研究的熱點，精確的碰撞檢測對提高虛擬環境的真實性、增強虛擬環境的沉浸感起著至關重要的作用，而虛擬環境自身的複雜性和實時性對碰撞檢測提出了更高的要求。

　　包圍盒樹[7]是解決碰撞檢測問題的一種有效的方法，碰撞檢測對包圍盒樹的構造有以下幾方面的要求：儘可能平衡以使得樹的高度比較低；樹的所有結點的包圍盒體積儘可能小；每個結點的所有子結點的包圍盒的交集儘可能小。但虛擬環境中物件進入的自由性和不可預測性以及碰撞檢測的實時性又不允許我們在構造樹時進行太複雜的最佳化，因此如何構造包圍盒樹將直接影響到碰撞檢測的效率。

　　K_DOPS可以看作是AABB[5]的擴充套件，它不再是用三對平面來包圍物件，而是使用了k/2對平面，正是因這這種擴充套件，它彌補了AABB緊密性差的缺點。因此，K_DOPS是一種很好的包圍盒型別。

　　2 K_DOPS (Discrete Orientation Polytopes)的定義

　　Discrete Orientation Polytopes(K_DOPS)包圍盒是一種多面體，它的面由一組半空間 所確定，這些半空間的外法向是從 k 個固定的方向（D1，D2，...Dk）中選取的[2] [5]。

　　設固定方向集K（D1，D2，...Dk） ，一元組 （d1，d2，...dk）∈Rk

　　其中：

　　半空間

　　在設計K_DOPS時，為使相關的耗費盡量小，通常只選擇那些共線但方向完全相反的向量作為固定法向，因此，每個K_DOPS實際上只用到k/2個方向，即

　　K_DOPS是一組半空間的集合，無論是在表示、儲存還是計算中都是十分不方便的，構成K_DOPS的任何一半空間都可以表示成不等式形式：

　　由於集合D 是固定不變的，可以用一個 k×n矩陣來表示集合 D，從而可以把k_dops表示成如下形式：

　　其中由於 方向是可預知的，所以儲存每個K_DOPS時無需儲存方向，只需儲存K個值即可，每個值對應一個平面的位置。而且當對兩個K_DOPS做重疊測試時，只需要進行 次測試，這種測試遠比兩個OBB或凸包間的重疊測試簡單。

　　3 K_DOPS的選擇與計算3 .1 固定方向集的選擇

　　K_DOPS最簡單的例子是6_DOPS，其中6個面的法向分別由3個座標軸的正負軸所決定，三維空間AABB軸向包圍實際上是一種6_DOPS的特例。

　　對於14_DOPS，其中除了沿用AABB的六個方向外，還增加了8個對角線的方向，以消除這些方向上可能存在的空缺。

　　對於18_DOPS，其中除了沿AABB的6個方向外，還加入了指向AABB的12條邊的方向，以消除這些方向上可能存在的空缺。

　　對於26_DOPS，則沿14_DOPS和18_DOPS合起來的26個方向。

　　圖1中分別列舉了6_DOPS、8_DOPS、14_DOPS和18_DOPS。

　　3.2 K_DOPS的計算

　　一個幾何物件X的K_DOPS的包圍盒的計算可以透過X的頂點與固定方向集D中的各個方向的最大點積得到。使用這個蠻力計算法計算有n個頂點的多面體物件的K_DOPS可以在O(kn)時間內完成。

　　為了說明如何計算K_DOPS，我們來考慮一個如圖2所示的二維三角形。

　　圖2給出了一個簡單的二維空間中的例子，設D = {±(1，0)，±(0，1)，±(1，1)，±(1，-1) }，X是一個三角形，頂點座標分別為(2，1)，(6，2)和(4，6)。我們可以透過依次計算三角形三個頂點和D中的方向向量的點積計算這個三角形的K_DOPS。例如，為找到方向(1，1)上的最大延伸，我們計算下面三個點積。

　　(1， 1) . (2， 1) = 3

　　(1， 1) . (4， 6) = 10

　　(1， 1) . (6， 2) = 8

　　最大值為10，故X在(1，1)上的最大延伸為10，值得注意的是，(-1，-1)是D中和(1，1)方向相反的向量，故X的頂點與(1，1)的點積的最小值即為X在(-1，-1)上的最大延伸。透過計算其它方向上的點積，可以得到X的K_DOPS為(6，2，6，1，10，3，6，-2)。這個過程可以很容易地修改為用於計算複雜的物件的K_DOPS。

　　4 構造BV-tree包圍盒樹

　　由K_DOPS的定義和計算可知，固定方向凸包是一類比較簡單的幾何體，它從k個方向上形成對物件的較為緊密的包圍。一個複雜的物件是由成千上萬個基本幾何元素組成的，透過把它們的包圍盒組織成層次結構可以逐漸逼近物件，以獲得儘可能完善的幾何特性。

　　4.1 包圍盒樹

　　對給定的 n個基本幾何元素的集合S ，定義 S上的包圍盒層次結構BVT(S )為一棵樹，簡稱包圍盒樹，它具有以下性質[1] [3] [4] [6]：

　　①樹中的每個結點v 對應於 S的一個子集Sv(Sv∈S) ；

　　②與每個結點v 相關聯的還有集合 Sv的包圍盒 b（Sv）；

　　③根結點對應全集S 和 S的包圍盒b（S）；

　　④樹中的每個內部結點（非葉結點）有兩個以上的子結點，內部結點的最大子結點數稱作度，記為 δ；

　　⑤結點ν 的所有子結點所對應的基本幾何元素的子集合構成了對 ν所對應的基本幾何元素的子集Sv 的一個劃分。

　　4.2 構造方法

　　從輸入幾何元集合S上構造一棵BV_ tree可採用兩種方法：自頂向下和自底向上。

　　1）自底向上方法

　　該方法是從集合S的基本幾何元素出發，每個元素對應一個葉節點，然後利用任何區域性資訊遞迴地對它們進行分組歸併，形成父節點，直到得到一個單一的根節點(即集合 S)，這一方法就是如何把若干個集合歸併為一個父集。這個方法的一個典型的例子是Barequet等人的“BOXTREE”。

　　2）自頂向下方法

　　自頂向下方法是從一個逼近S的節點開始，利用整個集合的性質遞迴的劃分節點，直至到達葉結點，OBBTree是這個方法的一個典型的例子。

　　自頂向下方法的核心是如何把一個集合劃分成若干個不相交的子集，而自底向上方法的核心是如何把若干個集合歸併為一個父集。很難說得出這兩種方法有什麼優劣之分，相對而言，自頂向下的方法在碰撞檢測中使用得較多，技術更成熟一些，也比自底向上的方法更為健壯更易實現，故我們採用這一方法構造包圍盒樹。

　　5 碰撞檢測演算法及改進措施

　　假定已分別為一靜態環境物件E和一活動物件F建立了包圍盒樹狀層次模型（簡稱為包圍盒樹）。在包圍盒樹中，每個結點上的包圍盒都對應於組成該物件的基本幾何元素集合的一個子集，根結點為整個物件的包圍盒。碰撞檢測演算法的核心就是透過有效的遍歷這兩棵樹，以確定在當前位置下，活動物件的某些部分是否與環境物件的某些部分發生碰撞。這是一個雙重遍歷的過程。演算法首先用活動物件包圍盒樹的根結點遍歷環境物件包圍盒樹，如果能到達葉結點，再用該葉結點遍歷活動物件的包圍盒樹。如果能到達活動物件的葉結點，則進一步進行基本幾何元素的相交測試[7] 。其基本思想是利用幾何特性簡單的包圍盒代替複雜的幾何物件進行相交測試，如果兩個結點上的包圍盒不相交，則它們所包圍的物件的基本幾何元素的子集必定不相交，從而不需要對子集中的元素做進一步的相交測試。

　　下面我們簡單給出基於包圍盒樹的碰撞檢測演算法[8]。它主要由一個遞迴呼叫函式 Traverse(vE，vF)組成，vF為活動物件包圍盒樹中的當前結點，vE為環境物件包圍盒樹中的當前結點。演算法的原始輸入為活動物件包圍盒樹的根結點F和環境物件包圍盒樹的根結點E。

　　和 分別為結點vE和vF所對應的`基本幾何元素的子集， 和 分別為它們的包圍盒。

　　演算法1：Traverse(vE，vF)

　　1） If then

　　2） If vE是葉結點 then

　　3） If vF是葉結點 then

　　4） For 中的每一個基本元素

　　5） For 中的每一個基本元素

　　6） If then

　　7） Return 碰撞

　　8） End If

　　9） End For

　　10） End For

　　11） Else

　　12） For vF中的每一個結點vF

　　13） Traverse(vE，vF)

　　14） End For

　　15） End If

　　16） Else

　　17） For vE中的每一個結點ve

　　18） Traverse(ve，vF)

　　19） End for

　　20） End If

　　21） End If

　　演算法的開銷主要在於包圍盒 b（SE）和 b（SF）間的相交測試，如果它們不相交，則可以結束本次呼叫。否則，如果 vE不是葉結點，則我們在環境物件樹中繼續向下一層，為 vE的每個孩子 ve遞迴呼叫Traverse(vE，vF)。如果 vE是葉結點，則我們檢查 vF是否為葉結點，如果是，則我們在 vE的每個基本幾何元素和 vF的每個基本幾何元素間進行基本幾何元素間的相交測試（如，三角形與三角形間的相交測試、三角形與四面體間的相交測試等）；否則，我們在活動物件樹中繼續向下一層，為 vF的每個孩子vf 遞迴呼叫Traverse( vf， vE)。

　　在這裡，我們之所以先用活動物件的根結點遍歷環境物件樹，主要是因為通常情況下環境物件比活動物件更大更復雜一些（例如手術刀無論是大小還是複雜度都小於人體組織），這樣做可以快速地定位活動物件在環境中的位置，較早地排除與活動物件不相交的部分；如果先用環境物件的根結點遍歷活動物件樹，往往會增加包圍盒相交測試的次數。考慮下面這種極端情況，當活動物件完全置身於一個很大的環境物件中時，則當環境物件的根結點遍歷活動物件樹時，不會有任何包圍盒不相交的機會。

　　下面對上述演算法的改進，對17，18，19進行修改

　　17) If vF是葉結點 then

　　18) ForvE 的每一個子結點ve

　　19) Traverse( ve，vF)

　　20) End for

　　21) else

　　22) For 的每一個子結點 ve

　　23) For 的每一個子結點 vf

　　24) Traverse( ve，vf)

　　25) End for

　　26) End for

　　27) End if

　　這種演算法的優點是在遍歷過程中環境物件樹和活動物件樹能同時到達葉結點，降低了縱向搜尋的深度，但同時也加大的橫向搜尋的幅度。對於環境物件與活動物件大小接近且碰撞密集的情況，其效能有明顯的提高。

　　6 結論

　　基於K_DOPS包圍盒層次結構的碰撞檢測方法，其關鍵是K_DOPS的計算及BV_ TREE的構造，還有就是對環境物件包圍盒樹和活動物件包圍盒樹的遍歷過程中，對傳統的碰撞檢測演算法進行了改進，使環境物件樹和活動物件樹能同時到達葉結點，降低了縱向搜尋的深度，明顯地提高了搜尋效率。

　　參考文獻

　　[1] J.Canny. Collision Detection for Moving Polyhedra. IEEE Trans. Pattern Anal. Mach. Intel. 1986，8(2)： 200-209

　　[2] A .Smith，Y.Kitamura，H.Takemura，F.Kishino. A Simple Efficient Method for Accurate Collision Detection Among Deformable Polyhedral Objects in Arbitrary Motion. Proceedings of the IEEE Virtual Reality Annual International Symposium，pp.136-145，1995.2

　　[3] MyszKowski K，et al。Fast collision detection between computer solids using rasterizing graphics hardware [J]The Visual Computer，1995 1l(9)；497-511

　　[4]Hubbard，P. M. Approximating polyhedral with spheres for time critical collision detection. ACM Transactions on Graphics，1996，15(3)：179210

　　[5]Van Den Bergen，Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools .1997，2 (4)：1-14

　　[6]James T.Klosowiski. Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops，IEEE Transactions on Visualization and Computer Graphics，Vol. 4，No. 1，1998

　　[7]王志強，洪嘉振，楊輝.碰撞檢測問題研究綜述.軟體學報，1999，10 (5)： 545-551

　　[8]魏迎梅，吳泉源，石教英..碰撞檢測中的固定方向凸殼包圍盒的研究.軟體學報，2001