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