三維場景漫游中碰撞檢測的研究與應(yīng)用

摘要:在虛擬現(xiàn)實(shí)環(huán)境下，基于包圍盒算法是一類重要碰撞檢測算法，該文在比較了層次包圍盒下的幾種常用的包圍盒技術(shù)，具體闡述了實(shí)時性好且較容易程序?qū)崿F(xiàn)的軸一致包圍盒(AABB)的定義、重疊測試和碰撞檢測算法，并把該包圍盒技術(shù)應(yīng)用到虛擬現(xiàn)實(shí)系統(tǒng)的碰撞檢測過程中，最終在VC++和OpenGL平臺上實(shí)現(xiàn)了三維場景漫游過程中物體之間的精確碰撞檢測。

關(guān)鍵詞:包圍盒;碰撞檢測;AABB

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2010)11-2706-02

The Research and Application of the Collision Detection Walkthrough in 3D Scene

YIN Xiao-chun， NIE Ming

(Nanjing College of Information Technology， Nanjing 210046， China)

Abstract:The collision detection algorithm based on Bounding Box is an important algorithm for virtual environment. The paper compares several common Bounding Box technologies under Hierarchical Bounding Volumes， illustrates the definition and the overlap test and the collision detection algorithm of AABB， which has well real-time and could be achieved easily， applies the AABB in the collision detection process of virtual reality system， and finally implements the accurate collision detection between objects of virtual scene in VC++ and OpenGL platform.

Key words: bounding Box; collision detection; AABB

碰撞檢測間題在虛擬現(xiàn)實(shí)、計(jì)算機(jī)輔助設(shè)計(jì)與制造(CAD/CAM)、機(jī)器人和自動化、計(jì)算機(jī)圖形學(xué)等領(lǐng)域中經(jīng)常遇到的間題。精確的碰撞檢測對于提高虛擬仿真系統(tǒng)的擬真度、增強(qiáng)虛擬環(huán)境的沉浸感有著至關(guān)重要的作用，而虛擬環(huán)境自身的復(fù)雜性和實(shí)時性也對碰撞檢測提出了更高的要求[1]。

1 碰撞檢測

在現(xiàn)實(shí)生活中，兩個不可穿透的物體不能擁有一個相同的空間區(qū)域，而碰撞檢測的任務(wù)就是判斷在某時刻兩個物體是否發(fā)生碰撞。通常碰撞檢測系統(tǒng)的輸入模型是構(gòu)成幾何對象的基本幾何元素的集合，碰撞檢測就是判斷它們的交集是否為空，如不為空，即發(fā)生碰撞，還需計(jì)算碰撞點(diǎn)(碰撞發(fā)生的位置)。碰撞檢測涉及到3D空間，幾何模型表示、分層數(shù)據(jù)結(jié)構(gòu)、測試方法等[2]，它實(shí)質(zhì)上是通過判斷兩個物體之間的距離(即距離檢測)或重疊與相交(即碰撞檢測)情況來實(shí)現(xiàn)的。

國內(nèi)外學(xué)者在碰撞檢測領(lǐng)域中做了很多有意義的工作，并提出了一些高效的碰撞檢測算法，主要可以分為兩類，空間分解法(Space Decomposition)和層次包圍盒法(Hierarchical Bounding Volumes)。層次包圍盒法是利用體積略大而形狀簡單的包圍盒把復(fù)雜的幾何對象包裹起來，在進(jìn)行碰撞檢測時首先進(jìn)行包圍盒之間的相交測試，計(jì)算兩個待測對象中心點(diǎn)的距離與它們半徑之和的關(guān)系，以此來判定兩物體是否可能碰撞。如果包圍盒相交，再進(jìn)行幾何對象之間精確的碰撞檢測。它是一種最簡單和最常用的分層數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)表示易于構(gòu)造和移植，同時它不取決于任何模型的拓?fù)涮匦訹3-4]。因此，根據(jù)實(shí)際需要，本文針對層次包圍盒方法進(jìn)行研究，并在全景虛擬校園中應(yīng)用。

2 層次包圍盒分析與比較

包圍盒法的基本思想是使用簡單的幾何體來代替復(fù)雜的千奇百怪的幾何體，在虛擬場景中對物體的碰撞檢測可看作對包圍盒進(jìn)行檢測，當(dāng)包圍盒相交時其包圍的物體才有可能碰撞;當(dāng)包圍盒不相交時其包圍的物體一定不碰撞;這樣可以排除大量不可能碰撞的物體，并能夠快速地得到碰撞的物體部位，具體層次包圍盒類型有包圍球、軸一致包圍盒、有向包圍盒、固定方向凸包包圍盒、離散多面體包圍盒等[5]。

2.1 包圍球

包圍球(sphere)是用球形來近似地表示物體或物體的一部分，再判斷這些包圍球是否相交，它是一種最簡單的碰撞檢測方法，這樣僅需要測試兩個球體中心的距離是否小于它們的半徑和(表示發(fā)生了碰撞)。有時人們?yōu)榱诉M(jìn)一步提高碰撞精度，把將包圍球分割成一系列小的球體，檢查與各小球體是否發(fā)生碰撞。通過不斷地分割檢查，最終得到滿意的近似值。包圍球相交測試很簡單，但是它的緊密性太差，因此較少使用。

2.2 有向包圍盒

有向包圍盒(Oriented Bounding Box:簡稱OBB)是任意方向的多面體，它不僅對位置和大小進(jìn)行編碼，而且對方向進(jìn)行編碼，因此，它具有很高的緊密性，可以根據(jù)被包圍的物體的形狀特點(diǎn)盡可能的緊密的包圍物體。并成倍地減少相交測試包圍盒的數(shù)目和基本幾何元素的數(shù)目。在碰撞檢測過程中，尋找包圍盒的方向并確定包圍盒的大小是定義和計(jì)算OBB的關(guān)鍵問題。

2.3 固定方向凸包包圍盒

固定方向凸包包圍盒(Fixed Direction Hull:簡稱FDH)是一種特殊的凸包，是由Kay和Kajiya于1986年在他們的光線跟蹤算法中提出來的。FDH是用超過三對的平行平面對來逼近物體，所有物體的包圍盒的面的法向量來自固定方向向量集合。FDH繼承了凸包緊密性好的優(yōu)點(diǎn)，具有AABB簡單性的特點(diǎn)，但檢測的速度相對比較慢。

2.4 離散多面體包圍盒

離散多面體包圍盒(Discrete Orientation Polytopes:簡稱K-DOPs)用由k/2對平行平面包圍而成的凸多面體來包圍對象物體。k為法向量的個數(shù)。通過判斷k/2個法向量方向上是否有重疊的情況來判定兩個包圍體是否相交。法向量的個數(shù)越多，包圍盒包圍的物體就越緊密，求交集計(jì)算相對就越復(fù)雜，需合理地選取k的大小和平行平面對的方向，來保證碰撞檢測的簡單性和包裹物體的緊密性之間取得較好的折中，保證比較好的碰撞檢測速度。

2.5 軸一致包圍盒

軸一致包圍盒(Axis-Aligned Bounding Boxes:簡稱AABB)是指包含物體且平行于坐標(biāo)軸的最小六面體，該六面體沿著碰撞體局部坐標(biāo)系統(tǒng)的軸向(x， y ， z)構(gòu)造，所有的包圍盒具有方向一致性、易于確定包圍盒相交狀況和構(gòu)建相關(guān)層次結(jié)構(gòu)樹。在碰撞檢測初期，為快速的排除相距較遠(yuǎn)的物體時，AABB檢測效率比較高，它適用于碰撞的物體個數(shù)和即將發(fā)生碰撞的物體個數(shù)遠(yuǎn)小于存在的物體個數(shù)的情況。由于AABB構(gòu)建簡單快速、相交測試的簡單性和較好的緊密性，因此得到了廣泛的應(yīng)用。

3 基于AABB的碰撞檢測

3.1 模型定義

AABB模型可以采用沿空間坐標(biāo)軸上的最大最小值、角點(diǎn)或重心點(diǎn)來定義，其每種定義方式如下:

定義1:設(shè)沿軸線方向包圍盒大小為:xmin，xmax，ymin，ymax，zmin，zmax，則對包圍盒內(nèi)任一點(diǎn)具有:

R={( x， y ， z) | xmin≤x< xmax， ymin≤y < ymax， zmin≤z< zmax }

定義2:如果定義O ( x0 ， y0 ， z0)為包圍盒的一個角點(diǎn)坐標(biāo)，包圍盒長度分別為Dx，Dy，Dz，則有:

R={( x， y ， z) | x0 ≤x< x0+Dx ， y0≤y < y0 + Dy， z0≤z < z0+ Dz， }

定義3:如果定義C ( xc ， yc ， zc)為包圍盒的重心點(diǎn)坐標(biāo)，包圍盒長度分別為Rx ， Ry，Rz，則有:

R={( x， y ， z) || xc -x |≤Rx， | yc -y |≤Ry， | zc -z |≤Rz }

3.2 AABB間的相交測試

在空間中，AABB檢測主要是判斷檢測物體的位置狀態(tài)(分離或重疊)，即判斷物體是否發(fā)生重疊。要判斷物體是否重疊，只需判斷在空間坐標(biāo)軸上的投影是否重疊。因此可得到以下推論:

推論1:三維場景中兩個軸一致包圍盒發(fā)生碰撞(重疊)的充要條件是他們在空間坐標(biāo)軸上的投影都重疊。

在三維場景中，大多數(shù)情況下物體并沒有發(fā)生碰撞(重疊)。因此，不需要花太多時間建立層次結(jié)構(gòu)，更不需要檢查所有包圍盒在空間坐標(biāo)軸上的投影。在實(shí)際應(yīng)用中通常采用降維的方法來提高檢測的效率，滿足實(shí)時快速檢測和動態(tài)檢測的需要。所謂降維法是指首先將所有包圍盒向空間某一坐標(biāo)軸進(jìn)行投影;其次，將投影線段進(jìn)行排序，挑選出發(fā)生重疊的包圍盒對;再次，進(jìn)一步檢查這些包圍盒對在另外兩個軸上的投影是否仍然重疊。如果沒有重疊，則說明兩個物體沒發(fā)生碰撞，無須進(jìn)一步檢測;如果重疊，包圍盒中的物體發(fā)生碰撞的可能性較大，則進(jìn)行下一層的碰撞檢測(如圖1所示)。這樣可以省去在空間其它兩個坐標(biāo)軸上投影線段排序的時間，同時省去了在空間坐標(biāo)軸的投影線段的比較、查找的時間。

3.3 基于AABB碰撞檢測算法

基于AABB樹碰撞檢測算法思想是是通過建立基于AABB樹，并遍歷這兩棵樹，以確定在當(dāng)前位置下兩個碰撞體是否發(fā)生碰撞，這是一個雙重遞歸遍歷的過程。具體描述如下:

步驟1:構(gòu)造三維場景中人(或動態(tài)對象)和碰撞體的AABB樹。

步驟2:在某一時刻，使用人的AABB樹的根結(jié)點(diǎn)遍歷碰撞體的AABB樹。如果發(fā)現(xiàn)人的AABB樹的根結(jié)點(diǎn)的包圍盒與碰撞體AABB樹內(nèi)部結(jié)點(diǎn)的包圍盒不相交，則中止遍歷;如果能夠遍歷到碰撞體AABB樹的葉節(jié)點(diǎn)，再用該碰撞體AABB樹的葉節(jié)點(diǎn)遍歷人的AABB樹。如果能到達(dá)人的AABB樹的葉節(jié)點(diǎn)，執(zhí)行步驟3。

步驟3:檢測基本幾何元素間是否相交測試。

3.4 算法應(yīng)用

在算法實(shí)現(xiàn)過程中，首先建立AABB樹來包圍碰撞體，該樹是按照由上至下的遞歸細(xì)分方式構(gòu)建的二叉樹。在每一次遞歸過程中取最小的AABB，沿所選擇的剖分面將碰撞體分為正負(fù)兩半，并將所對應(yīng)的原始幾何元素(如三角面)分別歸屬正、負(fù)兩邊，遞歸進(jìn)行到每一個葉子節(jié)點(diǎn)只包容一個原始幾何元素為止，其中對于剖分面的選擇，可選擇垂直AABB的最長軸，且平分該軸的平面。

在南京信息職業(yè)技術(shù)學(xué)院三維場景模擬顯示系統(tǒng)的開發(fā)過程中，選用3DMAX制作學(xué)院所有建筑的3D模型、OpenGL實(shí)現(xiàn)一些紋理貼圖、Visual C++6.0作為開發(fā)工具。在系統(tǒng)實(shí)現(xiàn)三維場景漫游過程中，利用上文算法實(shí)現(xiàn)碰撞檢測，取得良好的效果，整體效果如圖2、圖3所示。

4 結(jié)束語

由于碰撞檢測問題由來已久，在不同領(lǐng)域涌現(xiàn)出許多碰撞檢測算法，但在實(shí)際應(yīng)用過程中，可以根據(jù)實(shí)際檢測的精確度和系統(tǒng)的實(shí)時性等需求進(jìn)行選擇哪種算法進(jìn)行碰撞檢測，也可以選擇多種算法綜合應(yīng)用來滿足虛擬現(xiàn)實(shí)系統(tǒng)的需要，進(jìn)而實(shí)現(xiàn)完整的、實(shí)時、更具沉浸感強(qiáng)的虛擬世界。

參考文獻(xiàn):

[1] 彭群生，鮑虎軍.計(jì)算機(jī)真實(shí)感圖形的算法基礎(chǔ)[M].北京:科學(xué)出版社，1999.

[2] 高春曉，劉玉樹.碰撞檢測技術(shù)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2002，38(5):9-11.

[3] 馬登武，葉文.基于包圍盒的碰撞檢測算法綜述[J].系統(tǒng)仿真學(xué)報，2006，18(4):1058-1061.

[4] 高玉琴，何云峰等.改進(jìn)的基于AABB包圍盒的碰撞檢測算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，16(28):3815-3817.

[5] 魏迎梅，王勇.碰撞檢測中的層次包圍盒方法[J]，計(jì)算機(jī)應(yīng)用，2000，20(8):241-244.