基于包圍盒的碰撞檢測算法綜述

《基于包圍盒的碰撞檢測算法綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、萬方數(shù)據(jù)第18卷第4期2006年4月系統(tǒng)仿真學(xué)報(bào)@JournalofSystemSimulationVbl．18NO．4Apr．，2006基于包圍盒的碰撞檢測算法綜述馬登武，葉文，李瑛(海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系，煙臺(tái)264001)摘要：對(duì)基于包圍盒的碰撞檢測算法中的軸向包圍盒法、方向包圍盒法、離散方向多面體法、時(shí)空包圍盒法的檢測原理和檢測效率進(jìn)行了詳細(xì)地分析比較。分析結(jié)果表明：包圍盒的簡單性和它包襄對(duì)象的緊密性是一對(duì)矛盾，包圍盒越簡單其包裹緊密性越差，如何更好地兼質(zhì)簡單性和緊密性成為包圍盒法的關(guān)冀；離散方向多面體是介于軸向包圍盒和凸包之同的包圈盒，只

2、要合理地選取平行平面對(duì)的個(gè)數(shù)和方向，就可以在碰撞檢洲的簡單性和包襄物體的緊密性之間靈活取舍。研究結(jié)論對(duì)于虛擬場景的動(dòng)態(tài)建模具有一定的指導(dǎo)意義。。關(guān)鍵詞：虛擬現(xiàn)實(shí)；碰撞檢測；算法；包圍盒中圖分類號(hào)：TP391．9文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1004—731X(2006)04．1058—04SurveyofBox-basedAlgorithmsforCollisionDetectionMADeng·wu，YEWen,LIYing(DepartmentofOrdnanceScienceandTechnology,NAEI，Yantai264001，China)Abst

3、ract：Differentalgorithmsforcollisiondetections(CD)invirtualsceneweresurveyed．Theprincipleandeffectivenessofaxis—alignedboundingboxes(AABB)method，orientedboundingboxmethod(OBB)，discreteorientationpolytopesfk—DOP)methodandSpace．TimeBoundingBoxes(STBB)methodwerediscussedindetail．There

4、sultsofanalysisprovethatthesimp跆nessofboundingboxisincontradictionwiththecompactnessofwrappedobjectandthek—DOPmethodiSbetweenAABBmethodandD口Bmethod伽theeffectivenesso，CD．Themainresultsareusefulfordesigningvirtualscene．Keywords：virtualreality：collisiondetection；algorithm；boundingbox引

5、言在虛擬現(xiàn)實(shí)中，用戶感覺虛擬對(duì)象應(yīng)該是“真實(shí)”存在的，例如飛機(jī)不可能穿過一座山飛過去，用戶用虛擬手敲打石頭時(shí)，虛擬手不應(yīng)穿過石頭等。這要求虛擬現(xiàn)實(shí)系統(tǒng)必須實(shí)時(shí)、準(zhǔn)確判斷虛擬物體之間是否發(fā)生了碰撞【1，2】。碰撞問題涉及碰撞檢測與碰撞響應(yīng)兩個(gè)方面，其中碰撞檢測用來檢測不同對(duì)象之間是否發(fā)生了碰撞。精確的碰撞檢測對(duì)提高仿真的真實(shí)性、可信性，增強(qiáng)虛擬環(huán)境的沉浸感有著至關(guān)重要的作用，而虛擬環(huán)境自身的復(fù)雜性和實(shí)時(shí)性也對(duì)碰撞檢測提出了更高的要求[3]。碰撞檢測算法總體上可分為空間分解法和層次包圍盒方法兩大類，其中層次包圍盒方法應(yīng)用得更為廣泛，十分適用于復(fù)雜環(huán)境中的碰撞檢測

6、。因此本文基于對(duì)國內(nèi)外有關(guān)包圍盒碰撞檢測算法研究論述的深入研究與系統(tǒng)分析，綜述相關(guān)研究成果，以期有助于包圍盒碰撞檢測算法這一研究的繼續(xù)深入與廣泛應(yīng)用。1碰撞檢測的基本原理簡單地講，碰撞檢測就是檢測虛擬場景中不同對(duì)象之間是否發(fā)生了碰撞。從幾何上講，碰撞檢測表現(xiàn)為兩個(gè)多面體收稿日期l2005．01．21修回日期l2005—09—24作者簡介t馬登武(1964．)，男，山東淄博人，副教授，博士，研究方向?yàn)楹娇毡鞴こ?、?jì)算機(jī)仿真、虛擬現(xiàn)實(shí)；葉文(1979一)，男，安徽黃山人，助教，博士，研究方向?yàn)榈涂胀环?、?jì)算機(jī)仿真、虛擬現(xiàn)實(shí)。的求交測試問題；按對(duì)象所處的空間可分

7、為二維平面碰撞檢測和三維空間碰撞檢測。平面碰撞檢測相對(duì)簡單一些，已經(jīng)有較為成熟的檢測算法，而三維空間碰撞檢測則要復(fù)雜得多【4，5】。在VR系統(tǒng)中，主要是如何解決碰撞檢測的實(shí)時(shí)性和精確性的矛盾。不同的應(yīng)用場合，對(duì)實(shí)時(shí)性和精確性的要求不盡相同。由于碰撞檢測問題在虛擬現(xiàn)實(shí)、計(jì)算機(jī)輔助設(shè)計(jì)與制造、機(jī)器人等領(lǐng)域有著廣泛的應(yīng)用，甚至成為關(guān)鍵技術(shù)，人們已經(jīng)從不同的角度對(duì)碰撞檢測問題進(jìn)行了廣泛的研究。按照是否考慮時(shí)間參數(shù)，碰撞檢測又可分為連續(xù)碰撞檢測和離散碰撞檢測。連續(xù)碰撞檢測的定義如下：定義1設(shè)三維空間R用三維幾何坐標(biāo)系統(tǒng)Fw表示，其中有N個(gè)運(yùn)動(dòng)模型，它們的空間位置和姿態(tài)

8、隨著時(shí)間而改變，F(xiàn)i表示第i個(gè)模型所占的空間。F。隨