二維碰撞檢測(cè)算法

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