二維碰撞檢測算法

二維碰撞檢測算法碰撞檢測(CollisionDetection,CD)也稱為干涉檢測或者接觸檢測，用來檢測不同對象之間是否發(fā)生了碰撞，它是計(jì)算機(jī)動(dòng)畫、系統(tǒng)仿真、計(jì)算機(jī)圖形學(xué)、計(jì)算幾何、機(jī)器人學(xué)、CAD\CA嘛研究領(lǐng)域的經(jīng)典問題。碰撞物體可以分為兩類：面模型和體模型。面模型是采用邊界來表示物體，而體模型則是使用體元表示物體。面模型又可根據(jù)碰撞后物體是否發(fā)生形變分為剛體和軟體，剛體本身又可根據(jù)生成方式的不同分為曲面模型和非曲面模型。目前對于碰撞的研究多集中于面模型的研究，因?yàn)轶w模型是一種三維描述方式，對它進(jìn)行碰撞檢測代價(jià)較高。而在面模型的研究中，對剛體的研究技術(shù)更為成熟。下面列舉幾種常用的碰撞檢測技術(shù)：1:包圍盒(boundingbox)是由Clark提出的，基本思想是使用簡單的幾何形體包圍虛擬場景中復(fù)雜的幾何物體，當(dāng)對兩個(gè)物體進(jìn)行碰撞檢測時(shí)，首先檢查兩個(gè)物體最外層的包圍盒是否相交，若不相交，則說明兩個(gè)物體沒有發(fā)生碰撞，否則再對兩個(gè)物體進(jìn)行檢測?；谶@個(gè)原理，包圍盒適合對遠(yuǎn)距離物體的碰撞檢測，若距離很近，其物體之間的包圍盒很容易相交，會(huì)產(chǎn)生大量的二次檢測，這樣就增大了計(jì)算量。包圍盒的類型主要有AABB(AlignedAxisBoundingBoX)坐標(biāo)軸的包圍盒、包圍球、OBB(OrientedBoundingBox)方向包圍盒和k-DOP(kDiscreteOrientationPolytopes)離散方向多面體等。AABB是包含幾何對象且各邊平行于坐標(biāo)軸的最小六面體,兩個(gè)AABB包圍盒相交當(dāng)且僅當(dāng)它們?nèi)齻€(gè)坐標(biāo)軸上的投影均重疊，只要存在一個(gè)方向上的投影不重疊，那么它們就不相交。AABB間的相交測試和包圍體的更新速度比其他算法效率高，因此使用最廣泛，尤其適用于多物體運(yùn)動(dòng)的大規(guī)模環(huán)境和變形體碰撞檢測。OBB包圍盒的相交測試基于分離軸的理論的，它的構(gòu)造關(guān)鍵在于包圍盒最佳方向的確定，最佳方向必須保證在該方向上包圍盒的尺寸最小。由于其較好的緊密性，大大提高了算法的效率，但需要較多的存儲(chǔ)空間，構(gòu)造和更新包圍體的速度都比較慢，不能有效地處理變形體等情況。k-DOP使用k/2對的平行平面來包圍物體，如果在由k-DOP的邊構(gòu)成的固定方向集合種的某個(gè)方向上的投影不重疊，則包圍盒必不相交；如果在所有方向上的投影都重疊，則包圍盒必相交。通過調(diào)整k的取值，k-DOP可以在簡單性、緊密性中達(dá)到一定的折衷，從而提高碰撞檢測的效率。包圍盒是目前應(yīng)用最為廣泛的碰撞檢測方法，包圍盒本身的簡單性和所包圍物體的緊密性是相互矛盾的，簡單性越高其緊密性差，反之如此，所以如何解決這個(gè)矛盾是包圍盒技術(shù)的關(guān)鍵。.空間剖分法空間剖分法是依據(jù)某種規(guī)則將場景空間劃分成若干小單元，并記錄所有單元內(nèi)的特征，通過查詢同一個(gè)單元或相鄰單元內(nèi)的特征間的相交情況來判斷是否發(fā)生碰撞檢測。按照剖分空間的方法可分為均勻剖分和非均勻剖分。均勻剖分是將場景中的空間均勻的劃分為大小一致的單元格，非均勻剖分的方法很多，如BSP樹和Kd樹等?？臻g剖分法使用于物體之間距離較遠(yuǎn)的場景，因?yàn)槿绻矬w之間的距離很近，需要對單元格進(jìn)行更深的遞歸分割，這樣需要更多的空間存儲(chǔ)單元格，并需要進(jìn)行更多的單元格相交測試，從而降低了效率。.距離場距離場是一種基本的圖形表示模型，表示距離物體表面的最小距離。距離場是矢量場，距離的正負(fù)可表示物體在外部或內(nèi)部，用距離場表示表面封閉的物體不需要物體的拓?fù)湫畔⒑图s束信息，能快速計(jì)算碰撞后的穿刺距離和法向量。距離場的空間劃分方法有很多種，標(biāo)準(zhǔn)柵格法、八叉樹和BSP樹等，［1］中提出了自適應(yīng)的采樣距離場（ADFs）它在距離場含有細(xì)節(jié)的時(shí)候采用較高的采樣率，在場變化小的時(shí)候，采用較低的采樣率，從而避免在細(xì)節(jié)部分采樣數(shù)量不夠多，導(dǎo)致整體碰撞檢測精度下降。采樣策略在建立距離場之前確定，從而控制了精確度，能最有效地利用內(nèi)存。距離場進(jìn)行碰撞檢測是逐點(diǎn)進(jìn)行的，通過把一個(gè)物體的頂點(diǎn)逐個(gè)與另一個(gè)物體的距離場進(jìn)行檢測，確定是否發(fā)生碰撞。當(dāng)然碰撞還存在邊與邊之間的相交，在［2］中提出了一種類似劃分的方法，他們通過增加測試變形特征的每條邊的中心來增加碰撞檢測的精確度。.圖像空間方法圖像空間的碰撞檢測方法不需要為物體建立層次包圍體樹模型，它利用圖形硬件將三維物體降為二維圖像，對二維圖像進(jìn)行采樣并建立相應(yīng)的深度信息，通過對信息的分析判斷是否發(fā)生碰撞。圖像空間法不需要預(yù)處理，適合動(dòng)態(tài)的變形體，但是它需要降物體光柵化，其精度取決于對物體的離散化程度，不能提供準(zhǔn)確的碰撞信息，是用效率換取精度。但是，圖像空間法是一類較新的碰撞檢測方法，［3］和［4］提出過利用兩個(gè)深度緩存分別保存物體的最小和最大深度（M應(yīng)于物體的最前層和最后層），通過判斷第二個(gè)物體象素的最大深度值是否介于第一個(gè)物體象素的最大最小深度值之問來確定是否碰撞，但只能判斷凸體。［5］提出了利用模板緩存來保存窗口中每個(gè)象素上所代表的射線進(jìn)入物體和離開其他物體的次數(shù)，之后讀取模板緩存中的值來判斷兩物體是否相交，進(jìn)一步改善了圖像空間碰撞檢測算法的局限性。［6］將圖象空間碰撞檢測算法率先用到動(dòng)態(tài)布料仿真中，利用圖形硬件的深度緩存和顏色緩存來判別衣服和虛擬人體模型是否發(fā)生碰撞，該算法也是只能用于凸體。［7］提出了能檢測任意物體碰撞的方法，為物體計(jì)算層次深度圖LDI(LayeredDepthImage)來標(biāo)識(shí)物體的體積，先用AABB包圍盒進(jìn)行相交測試，對相交的包圍盒中的物體構(gòu)建LDI,再進(jìn)行相交測試，計(jì)算相交體積，這就要求物體必須是封閉的。LDI是圖像空間方法的基本結(jié)構(gòu)，所以對LDI的改進(jìn)是提高圖像空間方法的關(guān)鍵。［8］中用三中方法改進(jìn)了LDI,兩種是通過圖形硬件加速，另一種是通過改進(jìn)程序，結(jié)果顯示圖形硬件適合幾何形態(tài)復(fù)雜的場景，而以使用程序加速的方法比較靈活，更適合場景較小的情況。.隨機(jī)碰撞檢測方法隨機(jī)碰撞檢測是用效率換取精度的一類碰撞檢測方法，注重碰撞后的實(shí)時(shí)模擬，是碰撞領(lǐng)域的一個(gè)熱點(diǎn)。隨機(jī)碰撞檢測可分為Average-case方法和基于隨機(jī)選擇幾何元的碰撞檢測方法。Average-case^法是以包圍盒相交區(qū)內(nèi)兩個(gè)物體的特征個(gè)數(shù)的比作為是否發(fā)生碰撞的標(biāo)準(zhǔn)，算法靈活，能控制碰撞檢測的精確度。隨機(jī)選擇幾何元的碰撞檢測方法是通過在碰撞對象內(nèi)部隨機(jī)取樣作為初始的潛在的碰撞區(qū)域，然后跟蹤采樣對。［9］中提出采用k-dop來限制采樣點(diǎn)在兩物體之間較接近的部分，采用爬山法來逐步逼近局部最小并保留一個(gè)哈希表紀(jì)錄訪問過的特征對。［10］和［11］分別提出利用時(shí)空一致性和時(shí)間一致性，對隨機(jī)選擇幾何元的碰撞檢測方法進(jìn)行改進(jìn)。.智能算法智能算法是目前一個(gè)比較新的領(lǐng)域，是受自然規(guī)律的啟迪，根據(jù)仿生原理，模仿求解問題的算法，這方面的內(nèi)容很多，如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和群集智能技術(shù)等。[12]從求解物體的最短距離的角度判斷物體碰撞的可能性，將對最短距離的計(jì)算問題變成對約束條件的非線性規(guī)劃問題，利用遺傳算法對其求解，實(shí)驗(yàn)證明，該算法計(jì)算速度快、計(jì)算精度高。[13]提出利用粒子群算法和隨機(jī)碰撞檢測方法相結(jié)合，通過在物體特征域內(nèi)采樣把三維物體空間內(nèi)碰撞檢測問題轉(zhuǎn)換到二維空間解決，增加了算法的適應(yīng)性，實(shí)驗(yàn)證明該算法能有效的處理變形體的碰撞檢測問題。[14]提出用頂點(diǎn)的凸包來表示凸多面體，將物體間距離的問題歸結(jié)為約束條件的非線性規(guī)劃問題，利用模擬退火遺傳算法對該問題進(jìn)行求解，結(jié)果表明，該算法有較高的計(jì)算效率和計(jì)算速度。智能算法在碰撞檢測領(lǐng)域的應(yīng)用目前還不廣泛，但它本身在解決優(yōu)化等問題上的優(yōu)勢，對今后碰撞檢測技術(shù)的提高具有一定的意義。由于對于不同的物體，比如剛體和軟體，所采用的方法不同，并且對于不同的使用領(lǐng)域?qū)ε鲎矙z測要求的方面不同，比如速度和精確度更側(cè)重哪一方面，等等這些要求，就決定了對碰撞檢測算法的篩選和優(yōu)化。碰撞檢測技術(shù)在虛擬現(xiàn)實(shí)領(lǐng)域的重要性，決定了對它的研究將是一個(gè)漫長的過程，而且將會(huì)有更多新的算法融入其中。參考文獻(xiàn):[1]FriskenS.F.,PerryR.N.,Rockwood,PonesT.R.,Adaptivelysampleddistancefields:Ageneralrepresentationofshapeforcomputergraphics.SIGGRAP區(qū)000,ComputerGraphicsProceedings(2000),249-254.[2]A.Fuhrmann,G.Sobotka,andfieldsforrapidcollisiondetectioninphysicallybasedmodeling.InProceedingsofGraphiCon,2003,5865.[3]Shinyaanddetectionthroughrasterization.TheJournalofVisualizationandComputerAnimation,1991,132-134.[4]G.Baciu,W.S.-K.Wong,andimage-basedcollisiondetectionalgorithm.TheJournalofVisualizationandComputerAnimation,1999,181-192.[5]K.Myszkowski,O.Okunev,andcollisiondetectionbetweencomplexsolidsusingrasterizinggraphicshardware.TheVisualComputer,11(9),1995,497-12.[6]T.Vassilev,B.Spanlang,andclothanimationonwalkingavatars.InProceedingsofEurographics,2001,137-150.[7]B.Heidelberger,M.Teschner,andvolumetricintersectionsofdeformingobjects.InProceedingsofVision,Modeling,Visualization,2003461汨68.[8]StefanKimmerle,collisiondetectionandpost-processingforphysicalclothsimulation,Dissertation,Tubingen,2005,28-31.[9]S.Kimmerle,M.Nesme,andF.Faure.,Hierarchyacceleratedstochasticcollisiondetection.InProceedingsofVision,Modeling,Visualization,2004,307314.[10]LIN.M.C,CANNYJF.EfficientCollisionDetectionforAnimation[C],Proc.3rdEurographicsWorkshoponAnimationandSimulation,Cambridge,1992[11]LaksRaghupathi,LaurentGrisoni,FrancoisFaure,eta1.Anintestinesurgerysimulator：Real-timecollisionprocessingandvisualization[J],IEEETransactionon