面向虛擬維修的碰撞檢測(cè)算法

王 崴 周 誠(chéng) 楊 云 彭勃宇

面向虛擬維修的碰撞檢測(cè)算法

王 崴1,2周 誠(chéng)2楊 云2彭勃宇2

1(西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 陜西 西安 710049)

2(空軍工程大學(xué)防空反導(dǎo)學(xué)院 陜西 西安 710051)

為提高虛擬維修中碰撞檢測(cè)效率，提出一種改進(jìn)的空間剖分與包圍盒混合的碰撞檢測(cè)算法。針對(duì)空間剖分算法存在的響應(yīng)慢、精度低等問(wèn)題，使用添加鏈表、設(shè)置閾值、對(duì)比增量等方法進(jìn)行優(yōu)化，同時(shí)針對(duì)構(gòu)建OBB(Oriented Bounding Box)包圍樹(shù)復(fù)雜費(fèi)時(shí)的問(wèn)題通過(guò)使用動(dòng)態(tài)分裂平面法加速層次包圍盒構(gòu)建進(jìn)程。通過(guò)仿真，結(jié)果表明該算法在復(fù)雜環(huán)境下檢測(cè)效率較高，與傳統(tǒng)算法Rapid與RECODE相比平均檢測(cè)時(shí)間減少71.2%與68.2%，與混合算法CCD與FSABCD相比減少41.4%與27.4%。

虛擬維修 空間剖分 八叉樹(shù) OBB 動(dòng)態(tài)

0 引 言

隨著現(xiàn)代計(jì)算機(jī)不斷發(fā)展，虛擬現(xiàn)實(shí)VR(Virtual Reality)技術(shù)已廣泛應(yīng)用于模擬維修中。碰撞檢測(cè)技術(shù)是虛擬維修的基柱，對(duì)維修任務(wù)的逼真程度、操作人員的感官感覺(jué)有著重要的支撐作用。隨著維修對(duì)象復(fù)雜化、維修環(huán)境多元化的現(xiàn)實(shí)要求，對(duì)碰撞檢測(cè)的實(shí)時(shí)性、互動(dòng)性有了更嚴(yán)苛的要求。

碰撞檢測(cè)[1]CD(Collision Detection)也稱(chēng)為干涉檢測(cè)或者接觸檢測(cè)，是基于現(xiàn)實(shí)生活中一個(gè)普遍存在的事實(shí)：兩個(gè)不可穿透的對(duì)象不能共享相同的空間區(qū)域。

為了提高碰撞檢測(cè)的效率，國(guó)內(nèi)外學(xué)者對(duì)碰撞檢測(cè)技術(shù)進(jìn)行了深入探究，提出了許多獨(dú)特的見(jiàn)解與理論， Coming等人于2005年提出的動(dòng)態(tài)掠掃和裁剪算法KSP(Kinetic Sweep and Prune)[1]、Frisken等人提出的自適應(yīng)采樣距離場(chǎng)算法等等。國(guó)內(nèi)目前比較主流的研究方向是混合層次包圍盒碰撞檢測(cè)算法[2-5]。文獻(xiàn)[3]提出了一種混合層次包圍盒的碰撞檢測(cè)算法，利用包圍球和K-DOPS來(lái)構(gòu)建物體包圍盒，這種混合包圍盒使得包圍的緊密性得到了有效改善，但面對(duì)多物體復(fù)雜環(huán)境能力有限，同時(shí)，算法效率還有很大提升空間。文獻(xiàn)[4]中方向包圍樹(shù)構(gòu)建過(guò)程使用了固定的劃分層次，構(gòu)建速率偏低。文獻(xiàn)[6]提出了利用二叉樹(shù)對(duì)空間進(jìn)行劃分，但二叉樹(shù)存在劃分時(shí)間較長(zhǎng)、效率較慢等缺點(diǎn)。

為了加快碰撞檢測(cè)效率，本文采用了空間剖分算法與層次包圍盒結(jié)合的碰撞檢測(cè)算法應(yīng)用于虛擬維修中，并對(duì)相應(yīng)算法進(jìn)行改進(jìn)。提出添加鏈表的方式運(yùn)用于空間剖分算法中，有效地改進(jìn)了傳統(tǒng)算法計(jì)算量復(fù)雜，數(shù)據(jù)龐大等眾多缺點(diǎn)。針對(duì)傳統(tǒng)基于二叉樹(shù)的層次包圍盒構(gòu)建過(guò)程費(fèi)時(shí)、效率不高等問(wèn)題提出運(yùn)用動(dòng)態(tài)分裂平面的方法，提高了包圍盒樹(shù)構(gòu)建效率。在初步檢測(cè)階段利用空間剖分快速剔除不相交物體的特征，同時(shí)對(duì)可能相交的物體特征進(jìn)行詳細(xì)檢測(cè)，充分利用兩種算法的優(yōu)勢(shì)，提高碰撞檢測(cè)的效率。

1 相關(guān)算法介紹

1.1 空間剖分算法

空間剖分類(lèi)方法是把場(chǎng)景空間劃分成一個(gè)個(gè)小單元，在每個(gè)單元內(nèi)存儲(chǔ)所有屬于這個(gè)單元的對(duì)象[7]。由于不相鄰的單元之內(nèi)的對(duì)象相距較遠(yuǎn)，不可能發(fā)生碰撞，檢測(cè)碰撞只需測(cè)試同一個(gè)單元內(nèi)的對(duì)象相交情況即可?？臻g進(jìn)行剖分過(guò)程中，常采用二叉樹(shù)的方法[8]，但是二叉樹(shù)存在效率不高，劃分過(guò)慢等缺點(diǎn)。針對(duì)以上問(wèn)題，本文采用改進(jìn)的八叉樹(shù)方法應(yīng)用于空間剖分。圖1為八叉樹(shù)應(yīng)用于空間剖分。

圖1 利用八叉樹(shù)的空間剖分

1.2 層次包圍體樹(shù)算法

包圍盒技術(shù)最早是由Clark[7]提出的，近年來(lái)已發(fā)展成熟。其基本思想是用一個(gè)簡(jiǎn)單的幾何形體包圍虛擬場(chǎng)景中復(fù)雜的幾何物體，當(dāng)對(duì)兩個(gè)物體進(jìn)行碰撞測(cè)試時(shí)，首先判斷兩個(gè)物體的包圍盒是否相交，若不相交，則說(shuō)明兩個(gè)物體未發(fā)生碰撞，否則進(jìn)一步對(duì)兩個(gè)物體作詳細(xì)判斷。使用包圍盒只能粗略檢測(cè)到物體是否碰撞，而不能給出物體碰撞的詳細(xì)信息。對(duì)于復(fù)雜物體模型包圍盒比較粗糙，判斷相交情況略顯單薄。由于包圍盒的不同，層次包圍體樹(shù)可以劃分為：層次包圍球樹(shù)[9]、AABB(Aligned Axis Bounding Box)層次樹(shù)、OBB層次樹(shù)[10]、k-dop(Discrete Orientation Polytope)層次樹(shù)[11]等。

針對(duì)虛擬維修中物體的特點(diǎn)，一般多為移動(dòng)、精巧的物件。如虛擬手、虛擬工具拆裝零件等。為了更好滿(mǎn)足緊密包圍物體的特點(diǎn)，本文采用方向包圍盒。方向包圍盒碰撞測(cè)試較為復(fù)雜，且包圍盒逼近物體的過(guò)程繁瑣。針對(duì)這些問(wèn)題，本文提出了對(duì)OBB層次包圍盒的改進(jìn)，使之在不失緊密逼近物體優(yōu)點(diǎn)的同時(shí)加快層次樹(shù)構(gòu)建進(jìn)程，從而提高檢測(cè)效率。

2 本文提出的算法

2.1 算法簡(jiǎn)介

該算法主要包含兩個(gè)階段：初步檢測(cè)階段；逐步求精階段。初步檢測(cè)階段主要是指利用八叉樹(shù)的空間剖分算法將環(huán)境空間進(jìn)行快速分割，從而剔除不在同一空間中的物體，同時(shí)將處于同一空間中的物體進(jìn)行編號(hào)，完成初步檢測(cè)；逐步求精階段是指采用層次包圍盒樹(shù)對(duì)物體進(jìn)行精確的相交測(cè)試。本文的特色在于將添加鏈表的方式運(yùn)用在空間剖分中，有效地改進(jìn)了傳統(tǒng)算法數(shù)據(jù)量龐大、計(jì)算量大、計(jì)算過(guò)程復(fù)雜等眾多缺點(diǎn)。針對(duì)傳統(tǒng)基于二叉樹(shù)的層次包圍盒構(gòu)建過(guò)程費(fèi)時(shí)進(jìn)行改進(jìn)，將動(dòng)態(tài)分裂平面應(yīng)用其中，從而節(jié)省了層次包圍盒樹(shù)構(gòu)建時(shí)間，減少了檢測(cè)時(shí)間，提高算法效率。算法流程圖如圖2所示。

圖2 算法流程圖

2.2 初步檢測(cè)階段

采用八叉樹(shù)對(duì)物體所處環(huán)境空間進(jìn)行剖分，形成八個(gè)立方塊小空間。由于單個(gè)節(jié)點(diǎn)子空間中可能存在多個(gè)物體，比如在空間1中包含物體A、B、C，空間2中包含物體B、C、D，此時(shí)若對(duì)物體進(jìn)行碰撞檢測(cè)，那么空間1中B、C與空間2中B、C將造成重復(fù)檢測(cè)。如果物體個(gè)數(shù)增加，復(fù)雜程度加強(qiáng)，那么將會(huì)存在大量的數(shù)據(jù)重復(fù)計(jì)算，影響計(jì)算效果。除此之外，空間劃分深度也是一個(gè)關(guān)鍵性問(wèn)題。如果空間劃分深度過(guò)低，將會(huì)存在單個(gè)子空間中物體個(gè)數(shù)過(guò)多，不利于初步檢測(cè)階段快速剔除不相交物體；如果空間劃分深度過(guò)高，則遍歷空間剖分過(guò)程成本過(guò)大，嚴(yán)重影響碰撞檢測(cè)的速度和效率。針對(duì)這些問(wèn)題，參考文獻(xiàn)[12]本文提出了如下改進(jìn)方法。

首先對(duì)剖分后的空間單元進(jìn)行編號(hào)Ri(R1,R2,…,Rn)。同時(shí)對(duì)環(huán)境中物體添加標(biāo)記，如有n個(gè)物體，則添加標(biāo)記為Oi(O1,O2,…,On)。此時(shí)記錄每個(gè)物體所在單元，并設(shè)定兩個(gè)鏈表。在子空間數(shù)據(jù)結(jié)構(gòu)中設(shè)置鏈表Alist1，記錄同一子空間中物體的個(gè)數(shù)F。在物體結(jié)構(gòu)數(shù)據(jù)中添加一個(gè)Alist2鏈表，用來(lái)記錄單個(gè)單元中與該物體相鄰的物體標(biāo)識(shí)，注意只記錄比自生大的標(biāo)號(hào)。對(duì)于物體Oi(1

設(shè)置閾值Fmax，其代表單個(gè)空間記錄物體的最大數(shù)目。如果某一個(gè)剖分空間中屬于同一空間或相鄰物體的數(shù)目F超過(guò)閾值Fmax，則對(duì)此空間繼續(xù)剖分。同時(shí)更新子空間標(biāo)記，如Rij(Ri1,Ri2,…,Rin)，再對(duì)Alist1表進(jìn)行實(shí)時(shí)更新，記錄此時(shí)空間中物體所含個(gè)數(shù)F。通過(guò)判斷F與閾值關(guān)系，直至此空間中紀(jì)錄物體數(shù)小于或等于閾值Fmax為止，否則遞歸此程序。當(dāng)遍歷各個(gè)葉節(jié)點(diǎn)后，設(shè)置Alist2鏈表，記錄下與該物體同屬一空間的物體數(shù)集合。

對(duì)閾值判斷過(guò)程中，存在一個(gè)缺陷，嚴(yán)重時(shí)將會(huì)導(dǎo)致程序陷入死循環(huán)。當(dāng)環(huán)境空間中若存在大量過(guò)大物體，空間剖分時(shí)將無(wú)法滿(mǎn)足閾值判斷的情況，從而程序異常終止。針對(duì)以上問(wèn)題，本文提出了設(shè)置偏差從而對(duì)比增量Δ。Δ代表兩次記錄鏈表中物體個(gè)數(shù)F之差。若Δ=0，即兩次剖分時(shí)子空間所含物體個(gè)數(shù)不再減少，則停止空間剖分。

對(duì)環(huán)境空間剖分遵循以下原則：

(1) 對(duì)于空間中數(shù)目已經(jīng)小于閾值的子空間不再進(jìn)行剖分，否則繼續(xù)剖分。

(2) 由于一個(gè)物體可能同時(shí)包含于多個(gè)子空間內(nèi)，故可能存在大量數(shù)據(jù)的重復(fù)檢測(cè)。此時(shí)，鏈表中記錄的數(shù)據(jù)只能是比自身大的標(biāo)號(hào)，避免數(shù)據(jù)重復(fù)計(jì)算或漏算。

(3) 由于物體可能存在于邊界空間相交的情況，當(dāng)記錄鏈表時(shí)會(huì)存在各個(gè)子空間都包含該物體的信息，故記錄時(shí)不能遺漏。

(4) 當(dāng)增量Δ為零時(shí)，即物體個(gè)數(shù)不發(fā)生變化，此時(shí)空間劃分停止，避免陷入死循環(huán)。

2.3 逐步求精階段

逐步求精階段為精確判斷物體相交情況。具體過(guò)程描述如下。

2.3.1 方向包圍盒的確定

對(duì)Alist2鏈表中數(shù)集兩兩進(jìn)行相交測(cè)試。根據(jù)各包圍盒特點(diǎn)與虛擬維修環(huán)境要求，本文選用OBB方向包圍盒。OBB計(jì)算核心問(wèn)題就是尋找出最優(yōu)的方向，從而確定該方向上包圍盒最小尺寸。其計(jì)算過(guò)程為：

由物體頂點(diǎn)坐標(biāo)向量求得均值向量μ，再由均值向量計(jì)算協(xié)方差矩陣C。

計(jì)算公式為：

(1)

(2)

2.3.2 基于動(dòng)態(tài)分裂平面的包圍樹(shù)構(gòu)建

本文運(yùn)用了自頂而下的方法構(gòu)建層次包圍體樹(shù)的過(guò)程。構(gòu)建層次包圍體樹(shù)的過(guò)程包含三個(gè)方面：確定分離軸、確定分裂點(diǎn)、定位分裂平面。傳統(tǒng)的構(gòu)建過(guò)程[4]一般采用二叉樹(shù)的方法，運(yùn)用二叉樹(shù)將層次包圍樹(shù)的父節(jié)點(diǎn)劃分成為兩個(gè)子節(jié)點(diǎn)。其分裂過(guò)程為：首先比較各包圍盒軸大小，選取包圍盒最長(zhǎng)軸為分裂軸；其次，選取包圍盒幾何中心為分裂點(diǎn)，將父節(jié)點(diǎn)劃分為二，形成兩個(gè)子節(jié)點(diǎn)；最后以此遞歸，將子節(jié)點(diǎn)再劃分，直至子節(jié)點(diǎn)不可劃分，形成葉子節(jié)點(diǎn)，此時(shí)完成包圍樹(shù)的構(gòu)建。此構(gòu)建包圍樹(shù)的方法中存在眾多問(wèn)題，當(dāng)包圍盒某邊遠(yuǎn)比其他邊長(zhǎng)，即物體呈柱狀時(shí)，再由二叉樹(shù)分割可能會(huì)造成提前不可分割的情況發(fā)生。當(dāng)物體包圍盒為比較規(guī)則，邊長(zhǎng)大小差距不大，此時(shí)若用二叉樹(shù)將包圍盒分割成為兩個(gè)葉子節(jié)點(diǎn)將會(huì)造成分割時(shí)間嚴(yán)重浪費(fèi)。例如對(duì)于8個(gè)葉子節(jié)點(diǎn)的分配，其分配代價(jià)如圖3所示。圖示可知二叉樹(shù)構(gòu)建(a)需要三步完成，四叉樹(shù)(b)需要兩步，而八叉樹(shù)(c)只需要一步即可。因此，對(duì)于規(guī)則物體構(gòu)建包圍盒樹(shù)時(shí)，可以通過(guò)多層次劃分產(chǎn)生多個(gè)分裂平面，提升劃分效率，減少因劃分而產(chǎn)生的時(shí)間浪費(fèi)，節(jié)省構(gòu)建時(shí)間。

圖3 葉子節(jié)點(diǎn)分配代價(jià)圖

針對(duì)以上問(wèn)題，本文提出了通過(guò)動(dòng)態(tài)分裂平面的方法，即通過(guò)對(duì)包圍盒各軸長(zhǎng)度的判斷，確定包圍盒分離平面的數(shù)量，由此確定各個(gè)子節(jié)點(diǎn)的數(shù)量。具體分配過(guò)程遵循如下原則：

(1) 如果包圍盒某一軸長(zhǎng)遠(yuǎn)遠(yuǎn)超過(guò)另兩軸之長(zhǎng)，長(zhǎng)軸是短軸5倍以上。此時(shí)，分裂軸為最長(zhǎng)軸，分裂點(diǎn)選擇此軸的一半，分裂平面為1個(gè)，葉子節(jié)點(diǎn)的數(shù)量為2。

(2) 如果包圍盒內(nèi)兩條軸的大小都遠(yuǎn)遠(yuǎn)超過(guò)第三條軸，兩軸為第三軸5倍以上。此時(shí)，分裂軸為兩條，即為兩條較長(zhǎng)軸，分裂點(diǎn)為兩條軸的中心位置，分裂平面為2個(gè)，葉子節(jié)點(diǎn)的數(shù)量為4。

(3) 如果包圍盒內(nèi)三條軸的長(zhǎng)度相差不大，三條軸大小為1倍以?xún)?nèi)。此時(shí)，取三條軸為分裂軸，分裂點(diǎn)為其中心位置，分裂平面為3個(gè)，葉子節(jié)點(diǎn)數(shù)量為8。

(4) 如果包圍盒內(nèi)兩條軸的大小都超過(guò)第三條軸，而這兩條軸大小相差不大。比較這兩軸的大小，若較長(zhǎng)軸不超過(guò)較短軸2倍。此時(shí)，分裂軸為兩條，即為兩條較長(zhǎng)軸，分裂點(diǎn)為兩條軸的中心位置，分裂平面為2個(gè)，葉子節(jié)點(diǎn)的數(shù)量為4。

(5) 如果包圍盒內(nèi)兩條軸的大小都超過(guò)第三條軸，而這兩條軸大小相差不大。比較這兩軸的大小，若較長(zhǎng)軸超過(guò)較短軸2倍，此時(shí)，分裂軸為最長(zhǎng)軸，分裂點(diǎn)選擇此軸的一半，分裂平面為1個(gè)，葉子節(jié)點(diǎn)的數(shù)量為2。

(6) 其他情況，分裂軸為最長(zhǎng)軸，分裂點(diǎn)選擇此軸的一半，分裂平面為1個(gè)，葉子節(jié)點(diǎn)的數(shù)量為2。

3 仿真分析

在CPU i3 3.3 GHz內(nèi)存4.00 GB的windows 7 PC機(jī)上用VisualStudio 2008編程實(shí)現(xiàn)了算法。算法首先應(yīng)用于圖4所示的理想模型環(huán)境中。

圖4 理想環(huán)境空間

因環(huán)境中簡(jiǎn)單幾何形體的數(shù)量可以不斷增加，從而保證環(huán)境中三角形面片數(shù)不斷遞增。首先根據(jù)圖示環(huán)境分析出最理想的閾值Fmax的取值。實(shí)驗(yàn)過(guò)程為，在理想環(huán)境中不斷改變簡(jiǎn)單幾何體數(shù)目，使三角形面片數(shù)不斷改變。在保證三角形面片數(shù)依次相等的特定的不同環(huán)境中，比較不同F(xiàn)max時(shí)，物體平均檢測(cè)時(shí)間。

仿真一 采用三角形面片數(shù)分別為4、6、8 KB時(shí)，F(xiàn)max與平均檢測(cè)時(shí)間關(guān)系如圖5所示。其中橫坐標(biāo)表示Fmax數(shù)目，即同一空間中所包含幾何體最大個(gè)數(shù)。縱軸代表平均碰撞檢測(cè)時(shí)間，圖示為三角形面片數(shù)為4、6、8 KB時(shí)，F(xiàn)max與檢測(cè)時(shí)間關(guān)系折線(xiàn)。當(dāng)Fmax為0時(shí)，此時(shí)不含初步檢測(cè)階段，僅包括逐步求精過(guò)程，因此在0時(shí)，折線(xiàn)變化較大，取2時(shí)折線(xiàn)最低，但是剖分過(guò)程最為復(fù)雜，不易計(jì)算。當(dāng)Fmax依次增加，折線(xiàn)緩慢上升，但剖分過(guò)程復(fù)雜度逐漸降低。結(jié)合實(shí)際情況同時(shí)分析實(shí)驗(yàn)數(shù)據(jù)可知，F(xiàn)max取值為2至8之間最為合適。

圖5 Fmax與平均檢測(cè)時(shí)間關(guān)系

仿真二 為忽略初步檢測(cè)的快速篩選階段，針對(duì)包圍盒樹(shù)構(gòu)建過(guò)程將傳統(tǒng)OBB與本文采用動(dòng)態(tài)構(gòu)建包圍盒樹(shù)效率進(jìn)行對(duì)比，對(duì)比結(jié)果如表1所示。仿真中共取四個(gè)模型，對(duì)應(yīng)的包圍盒體積各不相同。由表格數(shù)據(jù)可知，本文算法與傳統(tǒng)算法對(duì)比，包圍盒構(gòu)樹(shù)建時(shí)間明顯減少。但是隨著模型包圍盒體積的增加，包圍盒構(gòu)樹(shù)建時(shí)間并不是呈線(xiàn)性關(guān)系減少。這主要是由于模型自身的性質(zhì)決定的，與模型正規(guī)化程度相關(guān)。模型正規(guī)化程度越高，即模型越規(guī)則，包圍盒樹(shù)構(gòu)建時(shí)間相對(duì)較少，模型正規(guī)化程度越低，即模型越復(fù)雜，包圍盒樹(shù)構(gòu)建時(shí)間相對(duì)較長(zhǎng)。

表1 包圍盒樹(shù)構(gòu)建效率對(duì)比

仿真三 應(yīng)用于虛擬維修系統(tǒng)中。虛擬系統(tǒng)中三角形面片數(shù)為128 056，工作環(huán)境為虛擬扳手拆卸輪胎螺母。由仿真一可知，取Fmax為3。不同算法下的平均碰撞檢測(cè)時(shí)間(ms)如圖6所示。該算法與基于圖像空間的碰撞檢測(cè)算法(RECODE)、基于OBB方向包圍盒的碰撞檢測(cè)算法(Rapid)、基于Sphere與AABB混合包圍盒的算法(CCD)、基于上下分層的混合包圍盒的算法(FSABCD)進(jìn)行對(duì)比。

圖6 不同算法性能比較

圖6中，本文采用算法與傳統(tǒng)算法Rapid算法與RECODE算法對(duì)比，平均檢測(cè)時(shí)間分別減少71.2%與68.2%，與混合算法CCD與FSABCD相比也有明顯改善，分別減少41.4%與27.4%。由此可知在虛擬維修中確實(shí)能起到改善平均檢測(cè)時(shí)間，提高系統(tǒng)效率的作用。

4 結(jié) 語(yǔ)

本文針對(duì)空間剖分與包圍盒混合的碰撞檢測(cè)算法進(jìn)行了研究。針對(duì)空間剖分碰撞檢測(cè)算法存在的問(wèn)題提出了利用添加鏈表、設(shè)置閾值、對(duì)比增量等方法，有效地改進(jìn)了傳統(tǒng)算法計(jì)算量復(fù)雜，數(shù)據(jù)龐大等缺點(diǎn)；針對(duì)傳統(tǒng)基于二叉樹(shù)的層次包圍盒構(gòu)建過(guò)程費(fèi)時(shí)、效率不高等問(wèn)題提出了運(yùn)用動(dòng)態(tài)分裂平面的方法，提高了包圍盒樹(shù)構(gòu)建效率。結(jié)合實(shí)驗(yàn)仿真，充分驗(yàn)證本算法的有效性，同時(shí)對(duì)比數(shù)據(jù)結(jié)果可知，該算法在速度、精度方面較其他算法對(duì)比均有明顯改善。

[1] Coming D S,Staadt O G.Kintic Sweep and Prune for Collision Detection[C].Workshop on Virtual Reality Interaction and Physical Simulation,2005.

[2] 寧濤,郭晨,張升文.用混合包圍盒優(yōu)化碰撞檢測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(1):1-3.

[3] 姜曉路,劉淵.一種新的基于混合層次包圍盒的碰撞檢測(cè)算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(6):143-145.

[4] 胡詠梅.基于層次包圍盒的混合碰撞檢測(cè)[J].計(jì)算機(jī)工程與科學(xué),2012,34(6):127-130.

[5] 鄭延斌,郭凌云,劉晶晶.基于混合包圍盒的碰撞檢測(cè)優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué),2013,35(4):87-92.

[6] 康勇,熊岳山,費(fèi)先宏,等.基于空間分解和包圍盒層次的混合碰撞檢測(cè)算法[J].計(jì)算機(jī)仿真,2010,27(6):191-194.

[7] 王祎.虛擬現(xiàn)實(shí)中碰撞檢測(cè)關(guān)鍵技術(shù)研究[D].吉林:吉林大學(xué),2009.

[8] 楊巧艷.基于OBB碰撞檢測(cè)算法研究[D].天津:河北工業(yè)大學(xué),2007.

[9] O’Sullivan C,Dingliana J.Real-time collision detection and response using sphere-trees[C]//Proceedings of the Spring Conference on Computer Graphics,Bratislava,1999:83-92.

[10] Gottachalk S,Lin M C,Manocha D.A Hierarchical Structure for Rapid Interference Detection[C]//the Proceedings of ACM SIGGRAPH’96,1996:171-180.

[11] Zachmann G.Rapid collision detection by dynamically aligned DOP-Trees[C]//Proceedings of IEEE,VRAIS’98,Atlanta,Georgia,March,1998:90-97.

[12] 王娟,賴(lài)思渝,李明東.依賴(lài)表面提取的二次空間分解碰撞檢測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):156-159.

VIRTUAL MAINTENANCE-ORIENTED COLLISION DETECTION ALGORITHM

Wang Wei1,2Zhou Cheng2Yang Yun2Peng Boyu2

1(StateKeyLaboratoryforManufacturingSystemEngineering,Xi’anJiaotongUniversity,Xi’an710049,Shaanxi,China)2(SchoolofAirandMissileDefense,AirForceEngineeringUniversity,Xi’an710051,Shaanxi,China)

This paper presents an improved collision detection algorithm which mixes space subdivision and bounding box to raise the efficiency of collision detection in virtual maintenance. Aiming at long reaction time, low accuracy and other issues in space subdivision algorithm, we employ the methods of list adding, threshold setting, and increment contrasting to optimise it. In view of the problems of complexity and time consuming in OBB tree construction, we speed up the construction process of hierarchical bounding box through dynamic-build-division-plane method. It is demonstrated by simulation results that this algorithm is more efficient in complex environments. Compared with tradition algorithms Rapid and RECODE, and with mixture algorithms CCD and FSABCD, the average detection time is reduced by 71.2%, 68.2%, 41.4% and 27.4% respectively.

Virtual maintenance Space subdivision Octree Oriented bounding box (OBB) Dynamic

2014-06-30。國(guó)家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2013AA 040604)。王崴，副教授，主研領(lǐng)域：機(jī)器視覺(jué)及自動(dòng)控制。周誠(chéng)，碩士生。楊云，副教授。彭勃宇，碩士生。

TP391.9

A

10.3969/j.issn.1000-386x.2016.04.055