碰撞檢測中的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
【碰撞檢測中的KDOPS算法論文】相關文章：
關于描述CRP模型中的聚類算法的論文06-16
最短路徑算法在線路搶修中的應用論文02-20
計數查找算法研究精選論文04-05
算法設計與分析課程論文04-22
智能計算的經典算法解析論文06-16
作業成本的計算法論文06-16
近場聲源定位算法研究論文06-18