葉麗娜

摘要：本文首先介紹了碰撞檢測的基本原理及常用的幾種碰撞檢測方法，并對它們做出比較，指出其優(yōu)缺點(diǎn)，最后提出基于包圍球的快速碰撞檢測優(yōu)化算法，并在此基礎(chǔ)上實(shí)現(xiàn)了一個(gè)簡單的應(yīng)用碰撞檢測技術(shù)的實(shí)例Demo。

關(guān)鍵詞：碰撞檢測；軸向包圍盒；方向包圍盒；離散方向多面體

中圖分類號：TP37 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）07-0220-02

Abstract： This paper first introduces the basic principle of collision detection and collision of several commonly used detection method， and make comparison of them， and point out the advantages and disadvantages， finally put forward a fast collision detection algorithm based on optimal bounding sphere， and on this basis， the realization of a simple application of collision detection technology is an instance of Demo.

Key words：Collision detection；AABB；OBB；K-DOP

技術(shù)的進(jìn)步以及人們對游戲體驗(yàn)的不斷苛求和升級，對游戲環(huán)境尤其是三維場景的構(gòu)建提出了更大的挑戰(zhàn)。在現(xiàn)實(shí)生活中，碰撞總是自然而然的發(fā)生著，比如踢足球、打籃球的時(shí)候，我們總是需要控制球的方向和力度等。自從3D游戲出現(xiàn)以來，程序員就不斷為模擬更精確的現(xiàn)實(shí)世界而努力。為了更加逼真地模擬真實(shí)環(huán)境，開發(fā)出現(xiàn)場感體驗(yàn)感更強(qiáng)的優(yōu)質(zhì)游戲，就必須要將客觀實(shí)際中存在的各種物理規(guī)律現(xiàn)象融入到整個(gè)游戲開發(fā)過程中，在這其中大部分的游戲離不開碰撞檢測，這其中不管是物體與場景之間的碰撞檢測，還是物體與物體之間的碰撞檢測，碰撞檢測技術(shù)便是諸多最為關(guān)鍵的問題之一。當(dāng)我們在游戲進(jìn)行中出現(xiàn)飛向墻壁的小球穿墻而過，或是是駕駛的汽車與障礙物出現(xiàn)干涉時(shí)，就會大大降低游戲體驗(yàn)的真實(shí)感，由此可見，碰撞檢測技術(shù)確實(shí)成為游戲場景開發(fā)中的一項(xiàng)重要課題，而針對該項(xiàng)技術(shù)國外多家知名游戲開發(fā)商早已著手開展了相關(guān)技術(shù)的探索工作。

1 碰撞檢測的基本原理

碰撞檢測是檢測虛擬物體之間是否發(fā)生干涉，是虛擬現(xiàn)實(shí)技術(shù)中的關(guān)鍵問題之一，它是判斷圖形連同虛擬場景滿足時(shí)空的一致性定律的條件，即對游戲場景中的出現(xiàn)對象間的相對關(guān)系進(jìn)行判定以決定是否觸發(fā)新的相應(yīng)游戲事件，簡單來講，就是多面體間的相交測試問題。而3D游戲中的碰撞檢測比2D游戲中的碰撞檢測要復(fù)雜得多。

在3D游戲開發(fā)過程中最常見的情況是一個(gè)或一些在靜態(tài)環(huán)境中運(yùn)動(dòng)的物體。以下三種情況一般由碰撞檢測所描述：檢測碰撞連接點(diǎn)和對碰撞響應(yīng)建模；檢測兩個(gè)物體之間的碰撞；檢測碰撞發(fā)生和連接點(diǎn)的精確度。

從渲染角度來說，第一種描述需要一個(gè)動(dòng)態(tài)模型，若兩個(gè)物體渲染的位置重疊，即發(fā)生了碰撞；而后面兩種情況則屬于幾何操作。

2 基于層次包圍盒的碰撞檢測法

2.2.1軸向包圍盒（AABB）檢測法的基本原理

一個(gè)3D的AABB就是簡單的六面體，每一邊都平行于一個(gè)坐標(biāo)平面，而矩形邊界框不一定都是立方體，它的長、寬、高可以彼此不同。這種方法相對簡單，從二維的碰撞檢測降到一維空間操作，當(dāng)兩個(gè)AABB包圍盒相交時(shí)，當(dāng)且僅當(dāng)它們在X軸、Y軸和Z軸上的投影均重疊，只要存在一個(gè)方向上的投影不重疊，那么它們就不相交。AABB間的相交測試和包圍體的更新速度是最快的，因此使用最廣泛，尤其適用于多物體運(yùn)動(dòng)的大規(guī)模環(huán)境和變形體碰撞檢測。

2.2.2方向包圍盒（OBB）檢測法的基本原理

OBB的相交測試是基于分離軸的理論的，它被定義為包含該對象且相對于坐標(biāo)軸方向任意的正六面體。它的最佳方向必須保證在該方向上包圍盒的尺寸最小，這樣就形成了一個(gè)物內(nèi)劃分。由于其方向的任意性，較好的緊密性，在執(zhí)行碰撞查詢時(shí)，可能只需要遍歷更少的樹層次，其重疊檢測速度更快，大大提高了算法的效率。

2.2.3 離散方向多面體（k-DOP）檢測法的基本原理

k-DOP的概念最早由Kajiya和Kay二人提出，使用k/2對的平行平面來包圍物體，它是AABB的推廣。這種方法的優(yōu)勢在于增加AABB的包圍效率，與此同時(shí)保留它相對于OBB的優(yōu)勢。通過調(diào)整k的取值，可以在簡單性、緊密性中達(dá)到一定的折衷，從而提高碰撞檢測的效率，這樣就能滿足一個(gè)高效的場景層次結(jié)構(gòu)應(yīng)具有的條件。

2.2.4 AABB、OBB、K-DOP檢測方法比較

AABB法被用作模型的包圍盒時(shí)，雖然相交測試較簡單但緊密性差，且跟隨性差，運(yùn)算量大，這將極大的減慢應(yīng)用的速度，此外該方法仍面臨著精度的問題。OBB法同樣需要進(jìn)行大量的計(jì)算，且速度慢，不適用于動(dòng)態(tài)對象的檢測。采用OBB方法的另一個(gè)缺點(diǎn)是需要進(jìn)行大量的矩陣運(yùn)算。K-DOP方法則介于前述兩種方法之間的一種方法，其特點(diǎn)是只要合理地選取平行平面對的個(gè)數(shù)和方向，就可以在檢測的簡單性和包裹物體的緊密性之間靈活取舍，但計(jì)算量仍然很大，且對于平行平面對的選取更是一個(gè)難點(diǎn)問題，在使用該方法對于動(dòng)態(tài)環(huán)境下復(fù)雜虛擬場景中多虛擬對象之間的碰撞檢測問題還是顯得效率低下。

3 算法優(yōu)化及其運(yùn)行結(jié)果

鑒于對以上各種包圍盒體測試方法的比較，本文的做法是在對多面體進(jìn)行碰撞檢測時(shí)采用一個(gè)球體包裹每一對象或?qū)ο蟮囊徊糠郑缓髾z測這些球體是否相交。此方法計(jì)算的代價(jià)較低。包圍球法雖然算法簡單，但是在遇到動(dòng)態(tài)環(huán)境下復(fù)雜虛擬游戲場景中多虛擬對象之間的碰撞檢測問題時(shí)同樣給該處理器帶來了不小的計(jì)算負(fù)荷?；诖吮疚膶υ摲椒ㄟM(jìn)行了如下優(yōu)化：

1）過濾法：

此種優(yōu)化是邏輯上的，即使用檢測范圍的概念。本文在開發(fā)引擎代碼時(shí)在為不同多面體包圍球設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)在其中加入了一個(gè)布爾型標(biāo)志位，首先在幀與幀之間檢測該包圍球體的空間位置是否發(fā)生了變化，這種檢測只需通過計(jì)算包圍球體的三維坐標(biāo)是否發(fā)生了變化，僅涉及到加法、減法的計(jì)算并不會給處理器帶來較大的額外負(fù)擔(dān)，但卻十分有效。

2）公式優(yōu)化法：

以二維圖形為例，如圖1所示在A物體的外圍畫一個(gè)圓，作為檢測碰撞的邊線，任何物體是否與其發(fā)生了碰撞，都用圓心與圓心的距離來判斷，當(dāng)兩個(gè)圓心的距離等于或者小于2個(gè)物體碰撞圓周的半徑之和時(shí)，就說明這兩個(gè)物體發(fā)生了碰撞。如B和C兩個(gè)物體，當(dāng)它們圓心的距離等于兩個(gè)半徑的和的時(shí)候，也就是兩個(gè)碰撞檢測的圓相切的時(shí)候，這時(shí)我們判斷這兩個(gè)物體碰撞了。

參考文獻(xiàn)：

[1] Earnshaw R A， Gigante M A， Jones H. Virtual Reality Systems [M].Academic Press Limited 24/28，Oval Road London NW1 7DX，1993，135-237.

[2] 王志強(qiáng)等. 碰撞檢測問題研究綜述[J]. 軟件學(xué)報(bào)，1999，10（5）：545-551.

[3] ChristerEricson實(shí)時(shí)碰撞檢測算法技術(shù)[M].劉天慧譯.北京：清華大學(xué)出版社，2010

[4] 趙偉，譚睿璞，李勇.復(fù)雜虛擬環(huán)境下的實(shí)時(shí)碰撞檢測算法[J].系統(tǒng)仿真學(xué)報(bào)，2010