基于Ｓｎａｋｅ模型的碰撞檢測算法研究
2009-01-01 00:00:00李艷波印桂生張菁
計算機應用研究 2009年3期
（哈爾濱工程大學 計算機科學與技術學院， 哈爾濱 150001）
摘 要：針對現有的碰撞檢測算法難以解決物體形變的問題，提出了一種面向可變形物體的碰撞檢測方法。該算法在AABB碰撞檢測方法的基礎上將Snake模型的能量函數引入到包圍盒的更新過程中。實驗證明該算法不僅適用于剛體間的碰撞檢測，還適用于非剛體對象，計算簡單、速度快且精確度高。
關鍵詞：虛擬現實； 碰撞檢測； 包圍盒； Snake模型
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)03085503
Research on collision detection methods based on Snake
LI Yanbo， YIN Guisheng， ZHANG Jing
(College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China)
Abstract:This paper proposed a new method according to many methods were difficult to solve the problems of deformable models. The energy function of Snake applied to update the bounding volume based on AABB in this method. The experimental results show that it apply to both rigid and nonrigid models， computation simplicity， speed and accuracy.
Key words：virtual reality; collision detection; bounding volume; Snake
0 引言
碰撞檢測在計算機圖形學、仿真、動畫及虛擬現實等應用領域中都是亟待解決的問題之一。目前，虛擬環(huán)境中的三維物體模型越來越復雜，場景越來越大，而實時性的要求越來越高，這使得碰撞檢測過程必須盡可能地快速完成。
通常，碰撞檢測方法通過事先計算出的每個物體的幾何信息來進行實時的碰撞檢測。碰撞檢測算法主要可以分為三大類，即包圍盒層次法[1]、距離跟蹤法和空間剖分法[2]。其中，包圍盒層次法是用體積大而幾何特性簡單的包圍盒來近似地描述復雜的幾何對象，在進行碰撞檢測時首先進行包圍盒之間的相交測試，如果包圍盒相交，再進行幾何對象之間精確的碰撞檢測。目前比較常見的包圍盒有沿坐標軸的包圍盒[3](axis_ aligned bounding boxes，AABB)、包圍球[4]、方向包圍盒[5](oriented bounding boxes，OBB)、固定方向凸包的包圍盒[6](fixed direction convex hull，FDH)、離散方向多面體KDOP[7]等。距離跟蹤方法的實質就是判斷兩個模型中距離最近的兩點，然后計算它們之間的距離。常用的跟蹤算法有LinCanny算法和基于層次數據結構的層次算法。空間分解法是將整個虛擬空間劃分成相等體積的小單元格，只對占據了同一單元格或相鄰單元格的幾何對象進行相交測試，如octrees、kd trees、BSPtrees等。
但這些方法大多適用于剛體，對變形物體的碰撞檢測研究還尚未成熟。目前變形物體的碰撞檢測主要是將剛性物體的碰撞檢測方法加以改進，以適應變形物體形狀的變化。例如Smith等人[8]提出了一種基于AABB包圍盒的解決變形體對象的方法。該方法在每一步都重新計算對象的包圍盒；其缺點是當模型復雜時不能得到時實計算。V.Bergen[3]提出了一種基于SOLID庫的方法，并在每個時候由葉子節(jié)點開始完成自底向上的更新；缺點是發(fā)生大尺度變形時，AABB包圍盒的緊密性就較差且包圍盒與包圍盒之間有非常大的重疊區(qū)域。Sean Curtis等人[9]通過減少三角形模型的點、線和面的檢測次數來提高變形物體的碰撞檢測，缺點是當模型很大時，該方法訪問內存的次數也相對增加。Baraff[10]和Bridson等人[11]均提出了一種基于AABB的變形模型的碰撞檢測方法，但是當模型發(fā)生大范圍變形時，對模型層次更新非常耗時。
針對以上問題，本文提出了一種基于Snake模型的碰撞檢測方法，該方法在AABB方法的基礎上加入Snake模型的能量函數來實現對物體幾何信息的更新，以減少計算量和計算時間。
1 軸向包圍盒(AABB)碰撞檢測算法
一個物體的AABB被定義為包含該碰撞體，且邊平行于坐標軸的最小六面體。因此描述一個AABB，僅需六個標量。在構造AABB時，需沿著物體局部坐標系的軸向(X，Y，Z)來構造，所以所有的AABB具有一致的方向。
AABB樹是基于AABB的二叉樹，按照從上到下的遞歸細分方式構造生成。AABB樹之間的碰撞檢測是一個雙重遞歸遍歷的過程。對AABB樹A和B，若發(fā)現樹A的根節(jié)點的AABB與樹B內部節(jié)點的AABB不相交，則停止向下遍歷。如果遍歷能達到樹B的葉節(jié)點，再用該葉節(jié)點遍歷樹A；如果能到達樹A的葉節(jié)點，則進一步進行基本節(jié)點元素之間的相交測試。
兩個AABB間的相交測試，可以根據兩個AABB相交當且僅當它們在三個坐標軸上的投影區(qū)間均相交。通過投影，可以將三維求交問題轉換為一維求交問題。檢查兩個包圍盒分別向三個坐標軸的重疊情況，即可得出相交測試結果。當物體旋轉需要對AABB進行同樣的旋轉并更新；當物體變形之后只需對變形的基本幾何元素對的包圍盒重新計算，然后可以自底向上由子節(jié)點的AABB合成父節(jié)點的AABB，最后進行包圍盒樹的更新。
這種包圍盒具有構造快速、相交測試簡單、內存開銷少的特點，能較好地適應變形物體實時更新層次樹的需要；缺點是包圍物體不夠緊密，在一些情況下將出現較大的空隙，因此會增加許多不必要的檢測。
2 改進的碰撞檢測方法
在軟體對象環(huán)境中，剛體對象與軟體對象間的碰撞會導致軟體對象的變形，而基本幾何元素形狀的改變導致原來的包圍盒不再適用于當前的對象，數量的增減導致原先的包圍盒樹中某些節(jié)點無效。為了得到正確的碰撞檢測結果，需及時對包圍盒更新以適應環(huán)境的變化。
本文提出一種新的碰撞檢測算法。該算法以AABB方法為基礎，在碰撞物發(fā)生形變時引入Snake模型中的能量函數來決定原有包圍盒的大小、包圍盒邊的移動方向和移動距離，實現對包圍盒的更新。包圍盒樹的更新則采用自底向上的更新方法。
2.1 Snake模型原理
Snake模型[12，13]又稱為主動輪廓模型(active contour model)，其基本思想是首先在圖像中目標的周圍設置一條封閉曲線，然后在內部能量和外部能量的共同作用下使曲線向合適的位置移動并且不斷更新曲線能量，曲線最后到達目標的輪廓，此時曲線能量最小。Snake模型是在內部約束力和外部約束力作用下移動的變形輪廓線。Snake模型的形變過程就是能量函數的最小化過程。主動輪廓模型給出了主動輪廓v(s)=(x(s)，y(s))的參數表示。其中x(s)和y(s)分別表示每個控制點在圖像中的坐標位置，s∈[0，1]。能量函數E*snake定義如下：
E*snake=∫10 Esnake(v(s))ds=∫10Eint(v(s))+Eext(v(s))ds(1)
Eint為Snake模型的內部能量函數，體現了對Snake輪廓曲線連續(xù)性和平滑性的約束。Eint定義如式(2)。其中α和β是加權系數，決定了輪廓線在該點的延伸和彎曲程度。
Eint(v(s))=1/2(α｜v′(s)｜2+β｜v″(s)｜2)(2)
Eext為Snake模型的外部能量函數，它決定著Snake輪廓曲線的移動方向。不同的外部能量函數引導Snake輪廓曲線收斂到圖像不同的特征區(qū)域，定義為
Eext(v(s))=Eimage(v(s))+Econsta int(v(s))(3)
其中：Eimage表示由圖像力產生的圖像能，它與圖像特征有關；Econsta int表示外部約束力能。Eimage是初始化曲線收斂到真實邊界的最重要的判斷條件。在邊界處曲線的圖像能量很大，非邊緣處圖像能量較小。為了使曲線收斂到目標的邊緣時能量最小，Eimage常取負值。圖像能量Eimage可描述為
Eimage=-｜I(x，y)｜2(4)
其中：為梯度算子；I(x，y)是原始灰度圖像。圖像I(x，y)在位置(x，y)的梯度定義為I=[Gx，Gy]T=[I/x，I/y]T。梯度向量指向在坐標(x，y)的I的最大變化率方向，即在物體邊緣處變化率最大，所以梯度向量指向物體邊緣方向。
2.2 算法的基本思想
該碰撞檢測方法的思想是首先構造AABB包圍盒和包圍盒樹，用AABB方法來檢測物體之間是否發(fā)生碰撞。當發(fā)生碰撞時，物體的形狀會發(fā)生變形，更新該子節(jié)點的包圍盒。該更新過程顛覆了傳統(tǒng)的更新整個包圍盒的方法，而采用更新原有包圍盒的一個或多個面，用更新的面和原有的面構成新的包圍盒。更新過程是在確定碰撞部位或發(fā)生形變部位后，在與發(fā)生變形面相垂直的平面上作正交投影，同時將包圍盒在該平面上的投影設定為Snake模型的初始輪廓線，通過Snake模型的能量函數對其各邊施加一個力，讓各邊移動到物體邊緣附近，使包圍盒能緊密地包圍物體。最后可以自底向上由子節(jié)點的AABB合成父節(jié)點的AABB，進行包圍盒樹的更新。算法實現過程描述如下：
a）初始化。構造AABB包圍盒及其包圍盒樹（二叉樹）。
b)AABB碰撞檢測方法檢測物體之間是否發(fā)生碰撞。
c)若發(fā)生碰撞，將包圍盒和變形物體在一平面上作正交投影，并將包圍盒投影后的矩形設置為初始輪廓線。若未發(fā)生碰撞轉至g）。
d）檢測投影后的物體與包圍盒邊之間的交點。
e）若不存在或存在多個交點，將包圍盒的投影設定為Snake模型的初始輪廓線，用Snake模型的能量函數對包圍盒進行更新，重復操作d）；否則轉至f）。
f）自底向上更新包圍盒樹。
g）準備作下一次碰撞檢測。
2.3 包圍盒的更新
碰撞物體發(fā)生形變后，該算法采用Snake模型的能量函數來更新包圍盒邊的大小和位置。Snake模型是在內部約束力和外部約束力作用下移動的變形輪廓線。Snake模型的內部能量函數體現了對Snake輪廓曲線連續(xù)性和平滑性的約束。Snake模型的外部能量函數決定著Snake輪廓曲線的移動方向。根據該碰撞檢測方法的需要，令α=1，使輪廓線在各點均連續(xù)。設矩形輪廓曲線四個頂點為角點，即角點處的β=0，其余點處β=1。通常情況下Snake模型的外部能量函數中的外部約束力能不予以考慮，則能量函數E*snake根據式(1)~(4)可以定義為
E*snake=∫10 1/2(｜v′(s)｜2+β｜v″(s)｜2)-｜I(x，y)｜2 ds
在Snake模型的實現中，需進行離散化，對Snake曲線v(s)沿著弧長s抽樣成N個點，每個點稱為蛇點，用v(i)=(x(i)，y(i))，i=1，…，N表示。初始輪廓線中的控制點(xi，yi)的選取采用相隔若干像素取一點的方法，間隔越小包圍盒邊的定位越準確，但同時提高了計算復雜度。AABB包圍盒更新過程描述如下：
a)計算當前點控制點(xi，yi)鄰近區(qū)域內各像素點的梯度值及其圖像能。點(xi，yi)梯度值的計算如式（5）所示。其中Gx和Gy分別表示I（x，y）沿x和y方向的梯度。
Gx(xi，yi)=0×I(xi，yi)+1×I(xi+1，yi)+(-1)×I(xi，yi+1)+0×I(xi+1，yi+1)
Gy(xi，yi)=1×I(xi，yi)+0×I(xi+1，yi)+0×I(xi，yi+1)+(-1)×I(xi+1，yi+1)
Eimage=-｜I(xi，yi)｜2=-(Gx(xi，yi)2+Gy(xi，yi)2)1/2(5)
b)計算當前控制點(xi，yi)鄰近區(qū)域內各像素點的能量值。
｜v′(i)｜2=｜vi-vi-1｜2=(xi-xi-1)2+(yi-yi-1)2(6)
｜v″(i)｜2=｜vi-1-2×vi+vi+1｜2=(xi-1-2×xi+xi+1)2+(yi-1-2×yi+yi+1)2(7)
結合式(5)~(7)可得控制點(xi，yi)處的能量值，定義為
E*snake=∑Ni=1[1/2(｜vi-vi-1｜2+β｜vi-1-2×vi+vi+1｜2)-
｜I(xi，yi)｜2]
同理可求得(xi，yi)鄰近區(qū)域內各像素點的能量值，并獲得能量值最小的點(xε，yε)。
c)將控制點更新為能量最小點的位置，即(xε，yε)→(xi，yi)，作為下一次迭代的輪廓點的新位置。
d)重復以上步驟處理下一個控制點，直至完成一次迭代為止。
e)若目標的邊界與包圍盒邊相交，交點處位置即為包圍盒邊的位置；否則進行下一次迭代，直到相交為止。
包圍盒的一條邊位置確定后，可結合投影平面上的其他邊更新包圍盒的一個面。同理結合原有包圍盒面可確定更新后的包圍盒的大小及其位置。圖1為物體發(fā)生碰撞前后的對比圖。其中圖1(a)為初始化時物體的包圍盒；(b)為由于碰撞發(fā)生形變用Snake模型能量函數更新后的包圍盒，虛線表示的是邊更新后的位置。
3 實驗結果分析
實驗的軟/硬件平臺為P4 2.0 GHz CPU、512 MB內存、GeForce 4200顯卡、VC++和OpenGL圖形接口等。Roberts梯度算子邊緣定位比較準確，所以該實驗中采用Roberts算子對邊緣進行定位。
實驗以魚的模型為例，如圖2所示。其中（a）為原始網格模型和模型的包圍盒；（b）為變形后的網格模型和更新后的包圍盒。當魚因碰撞或游動發(fā)生形變時采用改進的包圍盒更新算法對物體的包圍盒進行更新，取初始輪廓線上的24個控制點進行多次迭代。
圖3為一次迭代后各控制點的內部能量、圖像能量及其總能量值。原始的AABB碰撞檢測方法與改進的方法的消耗時間對比如圖4所示。當物體形變的區(qū)域大時，更新過程的計算量和消耗的時間很大（如圖中本文算法1曲線）；但當物體變形區(qū)域小時，則計算量和計算時間要相對減少了很多（如圖中本文算法2曲線）。盡管該改進方法包圍盒的更新過程依賴于物體碰撞后變形區(qū)域的大小，但在圖3中可以明顯地看出要比AABB碰撞檢測方法快很多。
通過實驗表明，改進的碰撞檢測算法具有以下優(yōu)點：a)實時性。在對AABB包圍盒更新時，采用Snake能量函數只對變形部位的包圍盒進行計算處理。b)通用性。Snake模型的能量函數可應用的其他包圍盒碰撞檢測方法中，如OBB、KDOP等，同樣能取得好的碰撞檢測效果。c)高效性。將包圍盒的邊設定為Snake模型的初始輪廓線，使輪廓線緊密的包圍物體，物體發(fā)生形變后盡可能地減少Snake模型能量函數的計算量，并提高了計算速度。d)兼容性。該方法適合剛體與非剛體之間的碰撞檢測。
4 結束語
本文在一些傳統(tǒng)的碰撞檢測方法的研究基礎上，提出了一種基于Snake模型的碰撞檢測方法。該方法將Snake模型能量函數引入到碰撞檢測方法中，用其來完成物體幾何信息的更新，它不僅大大減少了碰撞檢測的計算量和計算時間，而且還減少了計算過程中所耗的內存。該方法在算法的簡單性和實時性上均有所提高，但是還沒有解決包圍盒的緊密性問題，所以還需進一步的深入研究。
參考文獻：
［1］CLARK J H. Hierarchical geometric models for visible surface algorithms[J]. Comm ACM， 1976，19(10):547554.
[2]TETSUYA U， TOSHIAKI O， MARIO T. Collision detection in motion simulation[J]. Computer Graphics， 1983，7(2):285293.
[3]BERGEN G van. Efficient collision detection of collision deformable models using AABB trees[J]. Journal of Graphics Tool， 1997，2(4):114.
[4]HUBBARD. Approximating polyhedra with spheres for time critical collision detection[J]. ACM Trans on Graphics， 1996，15(3):179210.
[5]BALLARD D H. Strip trees:a hierarchical representation for curves[J]. ACM Communication， 1981，24(5):310321.
[6]BRUDEA G C， COIFFET P. 虛擬現實技術[M]. 北京：電子工業(yè)出版社， 2005.
[7]KLOSOWSKI J T. Efficient collision detection using bounding volume hierarchies of KDOP[J]. IEEE Trans on Visualization and Computer Graphics， 1998，4(1):2627.
[8]SMITH A， KITAMURA Y， TAKEMURA H， et al. A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion[C]//Proc ofIEEE Virtual Reality Annual International Symposium. 1995:136145.
[9]CURTIS S， TAMSTORF R， MANOCHA D. Fast collision detection for deformable models using representativetriangles[C]//Proc of Association for Computing Machinery. New York: ACM Press， 2008:3961.
[10]BARAFF D，WITKIN A，KASS M. Untangling cloth[C]//Proc of ACM SIGGRAPH. 2003:862870.
[11]BRIDSON R， FEDKIW R， ANDERSON J. Robust treatment for collisions， contact and friction for cloth animation[C]//Proc of ACM SIGGRAPH. 2002:594603.
[12]KASS M， WITKIN A， TERZOPOULOS D. Snakes: active contour models[C]//Proc of the 1st International Conference on Computer Vision. Netherlands:Springer， 1987:259268.
[13]李培華，張?zhí)镂?主動輪廓線模型(蛇模型)綜述[J]. 軟件學報， 2000，11(6):751757.
