碰撞檢測中的KDOPS算法論文
摘 要 K_DOPS碰撞檢測算法是一類(lèi)重要的碰撞檢測算法，本文從K_DOPS的定義、包圍盒的選擇與計算、包圍盒樹(shù)的構造等幾個(gè)方面對K_DOPS算法進(jìn)行研究，并給出一種快速碰撞檢測算法并對該算法進(jìn)行改進(jìn)，提高算法的效率。
關(guān)鍵詞 碰撞檢測；K_DOPS；包圍盒樹(shù)
1 引言
碰撞檢測問(wèn)題在計算機圖形學(xué)中有很長(cháng)的研究歷史，近年來(lái)，隨著(zhù)虛擬現實(shí)，分布交互仿真等技術(shù)的興起，碰撞檢測再一次成為研究的熱點(diǎn)，精確的碰撞檢測對提高虛擬環(huán)境的真實(shí)性、增強虛擬環(huán)境的沉浸感起著(zhù)至關(guān)重要的作用，而虛擬環(huán)境自身的復雜性和實(shí)時(shí)性對碰撞檢測提出了更高的要求。
包圍盒樹(shù)[7]是解決碰撞檢測問(wèn)題的一種有效的方法，碰撞檢測對包圍盒樹(shù)的構造有以下幾方面的要求：盡可能平衡以使得樹(shù)的高度比較低；樹(shù)的所有結點(diǎn)的包圍盒體積盡可能��；每個(gè)結點(diǎn)的所有子結點(diǎn)的包圍盒的交集盡可能小。但虛擬環(huán)境中對象進(jìn)入的自由性和不可預測性以及碰撞檢測的實(shí)時(shí)性又不允許我們在構造樹(shù)時(shí)進(jìn)行太復雜的優(yōu)化，因此如何構造包圍盒樹(shù)將直接影響到碰撞檢測的效率。
K_DOPS可以看作是AABB[5]的擴展，它不再是用三對平面來(lái)包圍對象，而是使用了k/2對平面，正是因這這種擴展，它彌補了AABB緊密性差的缺點(diǎn)。因此，K_DOPS是一種很好的包圍盒類(lèi)型。
2 K_DOPS (Discrete Orientation Polytopes)的定義
Discrete Orientation Polytopes(K_DOPS)包圍盒是一種多面體，它的面由一組半空間 所確定，這些半空間的外法向是從 k 個(gè)固定的方向（D1，D2，...Dk）中選取的[2] [5]。
設固定方向集K（D1，D2，...Dk） ，一元組 （d1，d2，...dk）∈Rk
其中：
半空間
在設計K_DOPS時(shí)，為使相關(guān)的耗費盡量小，通常只選擇那些共線(xiàn)但方向完全相反的向量作為固定法向，因此，每個(gè)K_DOPS實(shí)際上只用到k/2個(gè)方向，即
K_DOPS是一組半空間的集合，無(wú)論是在表示、存儲還是計算中都是十分不方便的，構成K_DOPS的任何一半空間都可以表示成不等式形式：
由于集合D 是固定不變的，可以用一個(gè) k×n矩陣來(lái)表示集合 D，從而可以把k_dops表示成如下形式：
其中由于 方向是可預知的，所以存儲每個(gè)K_DOPS時(shí)無(wú)需保存方向，只需保存K個(gè)值即可，每個(gè)值對應一個(gè)平面的位置。而且當對兩個(gè)K_DOPS做重疊測試時(shí)，只需要進(jìn)行 次測試，這種測試遠比兩個(gè)OBB或凸包間的重疊測試簡(jiǎn)單。
3 K_DOPS的選擇與計算3 .1 固定方向集的選擇
K_DOPS最簡(jiǎn)單的例子是6_DOPS，其中6個(gè)面的法向分別由3個(gè)坐標軸的正負軸所決定，三維空間AABB軸向包圍實(shí)際上是一種6_DOPS的特例。
對于14_DOPS，其中除了沿用AABB的六個(gè)方向外，還增加了8個(gè)對角線(xiàn)的方向，以消除這些方向上可能存在的空缺。
對于18_DOPS，其中除了沿AABB的6個(gè)方向外，還加入了指向AABB的12條邊的方向，以消除這些方向上可能存在的空缺。
對于26_DOPS，則沿14_DOPS和18_DOPS合起來(lái)的26個(gè)方向。
圖1中分別列舉了6_DOPS、8_DOPS、14_DOPS和18_DOPS。
3.2 K_DOPS的計算
一個(gè)幾何對象X的K_DOPS的包圍盒的計算可以通過(guò)X的頂點(diǎn)與固定方向集D中的各個(gè)方向的最大點(diǎn)積得到。使用這個(gè)蠻力計算法計算有n個(gè)頂點(diǎn)的多面體對象的K_DOPS可以在O(kn)時(shí)間內完成。
為了說(shuō)明如何計算K_DOPS，我們來(lái)考慮一個(gè)如圖2所示的二維三角形。
圖2給出了一個(gè)簡(jiǎn)單的二維空間中的例子，設D = {±(1，0)，±(0，1)，±(1，1)，±(1，-1) }，X是一個(gè)三角形，頂點(diǎn)坐標分別為(2，1)，(6，2)和(4，6)。我們可以通過(guò)依次計算三角形三個(gè)頂點(diǎn)和D中的方向向量的點(diǎn)積計算這個(gè)三角形的K_DOPS。例如，為找到方向(1，1)上的最大延伸，我們計算下面三個(gè)點(diǎn)積。
(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的頂點(diǎn)與(1，1)的點(diǎn)積的最小值即為X在(-1，-1)上的最大延伸。通過(guò)計算其它方向上的點(diǎn)積，可以得到X的K_DOPS為(6，2，6，1，10，3，6，-2)。這個(gè)過(guò)程可以很容易地修改為用于計算復雜的對象的K_DOPS。
4 構造BV-tree包圍盒樹(shù)
由K_DOPS的定義和計算可知，固定方向凸包是一類(lèi)比較簡(jiǎn)單的幾何體，它從k個(gè)方向上形成對對象的較為緊密的包圍。一個(gè)復雜的對象是由成千上萬(wàn)個(gè)基本幾何元素組成的，通過(guò)把它們的包圍盒組織成層次結構可以逐漸逼近對象，以獲得盡可能完善的幾何特性。
4.1 包圍盒樹(shù)
對給定的 n個(gè)基本幾何元素的集合S ，定義 S上的包圍盒層次結構BVT(S )為一棵樹(shù)，簡(jiǎn)稱(chēng)包圍盒樹(shù)，它具有以下性質(zhì)[1] [3] [4] [6]：
�、贅�(shù)中的每個(gè)結點(diǎn)v 對應于 S的一個(gè)子集Sv(Sv∈S) ；
�、谂c每個(gè)結點(diǎn)v 相關(guān)聯(lián)的還有集合 Sv的包圍盒 b（Sv）；
�、鄹Y點(diǎn)對應全集S 和 S的包圍盒b（S）；
�、軜�(shù)中的每個(gè)內部結點(diǎn)（非葉結點(diǎn)）有兩個(gè)以上的子結點(diǎn)，內部結點(diǎn)的最大子結點(diǎn)數稱(chēng)作度，記為 δ；
�、萁Y點(diǎn)ν 的所有子結點(diǎn)所對應的基本幾何元素的子集合構成了對 ν所對應的基本幾何元素的子集Sv 的一個(gè)劃分。
4.2 構造方法
從輸入幾何元集合S上構造一棵BV_ tree可采用兩種方法：自頂向下和自底向上。
1）自底向上方法
該方法是從集合S的基本幾何元素出發(fā)，每個(gè)元素對應一個(gè)葉節點(diǎn)，然后利用任何局部信息遞歸地對它們進(jìn)行分組歸并，形成父節點(diǎn)，直到得到一個(gè)單一的根節點(diǎn)(即集合 S)，這一方法就是如何把若干個(gè)集合歸并為一個(gè)父集。這個(gè)方法的一個(gè)典型的例子是Barequet等人的“BOXTREE”。
2）自頂向下方法
自頂向下方法是從一個(gè)逼近S的節點(diǎn)開(kāi)始，利用整個(gè)集合的性質(zhì)遞歸的劃分節點(diǎn)，直至到達葉結點(diǎn)，OBBTree是這個(gè)方法的一個(gè)典型的例子。
自頂向下方法的核心是如何把一個(gè)集合劃分成若干個(gè)不相交的子集，而自底向上方法的核心是如何把若干個(gè)集合歸并為一個(gè)父集。很難說(shuō)得出這兩種方法有什么優(yōu)劣之分，相對而言，自頂向下的方法在碰撞檢測中使用得較多，技術(shù)更成熟一些，也比自底向上的方法更為健壯更易實(shí)現，故我們采用這一方法構造包圍盒樹(shù)。
5 碰撞檢測算法及改進(jìn)措施
假定已分別為一靜態(tài)環(huán)境對象E和一活動(dòng)對象F建立了包圍盒樹(shù)狀層次模型（簡(jiǎn)稱(chēng)為包圍盒樹(shù)）。在包圍盒樹(shù)中，每個(gè)結點(diǎn)上的包圍盒都對應于組成該對象的基本幾何元素集合的一個(gè)子集，根結點(diǎn)為整個(gè)對象的包圍盒。碰撞檢測算法的核心就是通過(guò)有效的遍歷這兩棵樹(shù)，以確定在當前位置下，活動(dòng)對象的某些部分是否與環(huán)境對象的某些部分發(fā)生碰撞。這是一個(gè)雙重遍歷的過(guò)程。算法首先用活動(dòng)對象包圍盒樹(shù)的根結點(diǎn)遍歷環(huán)境對象包圍盒樹(shù)，如果能到達葉結點(diǎn)，再用該葉結點(diǎn)遍歷活動(dòng)對象的包圍盒樹(shù)。如果能到達活動(dòng)對象的葉結點(diǎn)，則進(jìn)一步進(jìn)行基本幾何元素的相交測試[7] 。其基本思想是利用幾何特性簡(jiǎn)單的包圍盒代替復雜的幾何對象進(jìn)行相交測試，如果兩個(gè)結點(diǎn)上的包圍盒不相交，則它們所包圍的對象的基本幾何元素的子集必定不相交，從而不需要對子集中的元素做進(jìn)一步的相交測試。
下面我們簡(jiǎn)單給出基于包圍盒樹(shù)的碰撞檢測算法[8]。它主要由一個(gè)遞歸調用函數 Traverse(vE，vF)組成，vF為活動(dòng)對象包圍盒樹(shù)中的當前結點(diǎn)，vE為環(huán)境對象包圍盒樹(shù)中的當前結點(diǎn)。算法的原始輸入為活動(dòng)對象包圍盒樹(shù)的根結點(diǎn)F和環(huán)境對象包圍盒樹(shù)的根結點(diǎn)E。
和 分別為結點(diǎn)vE和vF所對應的`基本幾何元素的子集， 和 分別為它們的包圍盒。
算法1：Traverse(vE，vF)
1） If then
2） If vE是葉結點(diǎn) then
3） If vF是葉結點(diǎn) then
4） For 中的每一個(gè)基本元素
5） For 中的每一個(gè)基本元素
6） If then
7） Return 碰撞
8） End If
9） End For
10） End For
11） Else
12） For vF中的每一個(gè)結點(diǎn)vF
13） Traverse(vE，vF)
14） End For
15） End If
16） Else
17） For vE中的每一個(gè)結點(diǎn)ve
18） Traverse(ve，vF)
19） End for
20） End If
21） End If
算法的開(kāi)銷(xiāo)主要在于包圍盒 b（SE）和 b（SF）間的相交測試，如果它們不相交，則可以結束本次調用。否則，如果 vE不是葉結點(diǎn)，則我們在環(huán)境對象樹(shù)中繼續向下一層，為 vE的每個(gè)孩子 ve遞歸調用Traverse(vE，vF)。如果 vE是葉結點(diǎn)，則我們檢查 vF是否為葉結點(diǎn)，如果是，則我們在 vE的每個(gè)基本幾何元素和 vF的每個(gè)基本幾何元素間進(jìn)行基本幾何元素間的相交測試（如，三角形與三角形間的相交測試、三角形與四面體間的相交測試等）；否則，我們在活動(dòng)對象樹(shù)中繼續向下一層，為 vF的每個(gè)孩子vf 遞歸調用Traverse( vf， vE)。
在這里，我們之所以先用活動(dòng)對象的根結點(diǎn)遍歷環(huán)境對象樹(shù)，主要是因為通常情況下環(huán)境對象比活動(dòng)對象更大更復雜一些（例如手術(shù)刀無(wú)論是大小還是復雜度都小于人體組織），這樣做可以快速地定位活動(dòng)對象在環(huán)境中的位置，較早地排除與活動(dòng)對象不相交的部分；如果先用環(huán)境對象的根結點(diǎn)遍歷活動(dòng)對象樹(shù)，往往會(huì )增加包圍盒相交測試的次數�？紤]下面這種極端情況，當活動(dòng)對象完全置身于一個(gè)很大的環(huán)境對象中時(shí)，則當環(huán)境對象的根結點(diǎn)遍歷活動(dòng)對象樹(shù)時(shí)，不會(huì )有任何包圍盒不相交的機會(huì )。
下面對上述算法的改進(jìn)，對17，18，19進(jìn)行修改
17) If vF是葉結點(diǎn) then
18) ForvE 的每一個(gè)子結點(diǎn)ve
19) Traverse( ve，vF)
20) End for
21) else
22) For 的每一個(gè)子結點(diǎn) ve
23) For 的每一個(gè)子結點(diǎn) vf
24) Traverse( ve，vf)
25) End for
26) End for
27) End if
這種算法的優(yōu)點(diǎn)是在遍歷過(guò)程中環(huán)境對象樹(shù)和活動(dòng)對象樹(shù)能同時(shí)到達葉結點(diǎn)，降低了縱向搜索的深度，但同時(shí)也加大的橫向搜索的幅度。對于環(huán)境對象與活動(dòng)對象大小接近且碰撞密集的情況，其性能有明顯的提高。
6 結論
基于K_DOPS包圍盒層次結構的碰撞檢測方法，其關(guān)鍵是K_DOPS的計算及BV_ TREE的構造，還有就是對環(huán)境對象包圍盒樹(shù)和活動(dòng)對象包圍盒樹(shù)的遍歷過(guò)程中，對傳統的碰撞檢測算法進(jìn)行了改進(jìn)，使環(huán)境對象樹(shù)和活動(dòng)對象樹(shù)能同時(shí)到達葉結點(diǎn)，降低了縱向搜索的深度，明顯地提高了搜索效率。
參考文獻
[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]王志強，洪嘉振，楊輝.碰撞檢測問(wèn)題研究綜述.軟件學(xué)報，1999，10 (5)： 545-551
[8]魏迎梅，吳泉源，石教英..碰撞檢測中的固定方向凸殼包圍盒的研究.軟件學(xué)報，2001
【碰撞檢測中的KDOPS算法論文】相關(guān)文章：
關(guān)于描述CRP模型中的聚類(lèi)算法的論文06-16
計數查找算法研究精選論文04-05
算法設計與分析課程論文04-22
智能計算的經(jīng)典算法解析論文06-16
作業(yè)成本的計算法論文06-16
近場(chǎng)聲源定位算法研究論文06-18