面向虛擬維修的碰撞檢測算法

王 崴 周 誠 楊 云 彭勃宇

面向虛擬維修的碰撞檢測算法

王 崴1,2周 誠2楊 云2彭勃宇2

1(西安交通大學機械制造系統工程國家重點實驗室 陜西 西安 710049)

2(空軍工程大學防空反導學院 陜西 西安 710051)

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

虛擬維修 空間剖分 八叉樹 OBB 動態

0 引 言

隨著現代計算機不斷發展，虛擬現實VR(Virtual Reality)技術已廣泛應用于模擬維修中。碰撞檢測技術是虛擬維修的基柱，對維修任務的逼真程度、操作人員的感官感覺有著重要的支撐作用。隨著維修對象復雜化、維修環境多元化的現實要求，對碰撞檢測的實時性、互動性有了更嚴苛的要求。

碰撞檢測[1]CD(Collision Detection)也稱為干涉檢測或者接觸檢測，是基于現實生活中一個普遍存在的事實：兩個不可穿透的對象不能共享相同的空間區域。

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

為了加快碰撞檢測效率，本文采用了空間剖分算法與層次包圍盒結合的碰撞檢測算法應用于虛擬維修中，并對相應算法進行改進。提出添加鏈表的方式運用于空間剖分算法中，有效地改進了傳統算法計算量復雜，數據龐大等眾多缺點。針對傳統基于二叉樹的層次包圍盒構建過程費時、效率不高等問題提出運用動態分裂平面的方法，提高了包圍盒樹構建效率。在初步檢測階段利用空間剖分快速剔除不相交物體的特征，同時對可能相交的物體特征進行詳細檢測，充分利用兩種算法的優勢，提高碰撞檢測的效率。

1 相關算法介紹

1.1 空間剖分算法

空間剖分類方法是把場景空間劃分成一個個小單元，在每個單元內存儲所有屬于這個單元的對象[7]。由于不相鄰的單元之內的對象相距較遠，不可能發生碰撞，檢測碰撞只需測試同一個單元內的對象相交情況即可。空間進行剖分過程中，常采用二叉樹的方法[8]，但是二叉樹存在效率不高，劃分過慢等缺點。針對以上問題，本文采用改進的八叉樹方法應用于空間剖分。圖1為八叉樹應用于空間剖分。

圖1 利用八叉樹的空間剖分

1.2 層次包圍體樹算法

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

針對虛擬維修中物體的特點，一般多為移動、精巧的物件。如虛擬手、虛擬工具拆裝零件等。為了更好滿足緊密包圍物體的特點，本文采用方向包圍盒。方向包圍盒碰撞測試較為復雜，且包圍盒逼近物體的過程繁瑣。針對這些問題，本文提出了對OBB層次包圍盒的改進，使之在不失緊密逼近物體優點的同時加快層次樹構建進程，從而提高檢測效率。

2 本文提出的算法

2.1 算法簡介

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

圖2 算法流程圖

2.2 初步檢測階段

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

首先對剖分后的空間單元進行編號Ri(R1,R2,…,Rn)。同時對環境中物體添加標記，如有n個物體，則添加標記為Oi(O1,O2,…,On)。此時記錄每個物體所在單元，并設定兩個鏈表。在子空間數據結構中設置鏈表Alist1，記錄同一子空間中物體的個數F。在物體結構數據中添加一個Alist2鏈表，用來記錄單個單元中與該物體相鄰的物體標識，注意只記錄比自生大的標號。對于物體Oi(1

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

對閾值判斷過程中，存在一個缺陷，嚴重時將會導致程序陷入死循環。當環境空間中若存在大量過大物體，空間剖分時將無法滿足閾值判斷的情況，從而程序異常終止。針對以上問題，本文提出了設置偏差從而對比增量Δ。Δ代表兩次記錄鏈表中物體個數F之差。若Δ=0，即兩次剖分時子空間所含物體個數不再減少，則停止空間剖分。

對環境空間剖分遵循以下原則：

(1) 對于空間中數目已經小于閾值的子空間不再進行剖分，否則繼續剖分。

(2) 由于一個物體可能同時包含于多個子空間內，故可能存在大量數據的重復檢測。此時，鏈表中記錄的數據只能是比自身大的標號，避免數據重復計算或漏算。

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

(4) 當增量Δ為零時，即物體個數不發生變化，此時空間劃分停止，避免陷入死循環。

2.3 逐步求精階段

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

2.3.1 方向包圍盒的確定

對Alist2鏈表中數集兩兩進行相交測試。根據各包圍盒特點與虛擬維修環境要求，本文選用OBB方向包圍盒。OBB計算核心問題就是尋找出最優的方向，從而確定該方向上包圍盒最小尺寸。其計算過程為：

由物體頂點坐標向量求得均值向量μ，再由均值向量計算協方差矩陣C。

計算公式為：

(1)

(2)

2.3.2 基于動態分裂平面的包圍樹構建

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

圖3 葉子節點分配代價圖

針對以上問題，本文提出了通過動態分裂平面的方法，即通過對包圍盒各軸長度的判斷，確定包圍盒分離平面的數量，由此確定各個子節點的數量。具體分配過程遵循如下原則：

(1) 如果包圍盒某一軸長遠遠超過另兩軸之長，長軸是短軸5倍以上。此時，分裂軸為最長軸，分裂點選擇此軸的一半，分裂平面為1個，葉子節點的數量為2。

(2) 如果包圍盒內兩條軸的大小都遠遠超過第三條軸，兩軸為第三軸5倍以上。此時，分裂軸為兩條，即為兩條較長軸，分裂點為兩條軸的中心位置，分裂平面為2個，葉子節點的數量為4。

(3) 如果包圍盒內三條軸的長度相差不大，三條軸大小為1倍以內。此時，取三條軸為分裂軸，分裂點為其中心位置，分裂平面為3個，葉子節點數量為8。

(4) 如果包圍盒內兩條軸的大小都超過第三條軸，而這兩條軸大小相差不大。比較這兩軸的大小，若較長軸不超過較短軸2倍。此時，分裂軸為兩條，即為兩條較長軸，分裂點為兩條軸的中心位置，分裂平面為2個，葉子節點的數量為4。

(5) 如果包圍盒內兩條軸的大小都超過第三條軸，而這兩條軸大小相差不大。比較這兩軸的大小，若較長軸超過較短軸2倍，此時，分裂軸為最長軸，分裂點選擇此軸的一半，分裂平面為1個，葉子節點的數量為2。

(6) 其他情況，分裂軸為最長軸，分裂點選擇此軸的一半，分裂平面為1個，葉子節點的數量為2。

3 仿真分析

在CPU i3 3.3 GHz內存4.00 GB的windows 7 PC機上用VisualStudio 2008編程實現了算法。算法首先應用于圖4所示的理想模型環境中。

圖4 理想環境空間

因環境中簡單幾何形體的數量可以不斷增加，從而保證環境中三角形面片數不斷遞增。首先根據圖示環境分析出最理想的閾值Fmax的取值。實驗過程為，在理想環境中不斷改變簡單幾何體數目，使三角形面片數不斷改變。在保證三角形面片數依次相等的特定的不同環境中，比較不同Fmax時，物體平均檢測時間。

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

圖5 Fmax與平均檢測時間關系

仿真二 為忽略初步檢測的快速篩選階段，針對包圍盒樹構建過程將傳統OBB與本文采用動態構建包圍盒樹效率進行對比，對比結果如表1所示。仿真中共取四個模型，對應的包圍盒體積各不相同。由表格數據可知，本文算法與傳統算法對比，包圍盒構樹建時間明顯減少。但是隨著模型包圍盒體積的增加，包圍盒構樹建時間并不是呈線性關系減少。這主要是由于模型自身的性質決定的，與模型正規化程度相關。模型正規化程度越高，即模型越規則，包圍盒樹構建時間相對較少，模型正規化程度越低，即模型越復雜，包圍盒樹構建時間相對較長。

表1 包圍盒樹構建效率對比

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

圖6 不同算法性能比較

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

4 結 語

本文針對空間剖分與包圍盒混合的碰撞檢測算法進行了研究。針對空間剖分碰撞檢測算法存在的問題提出了利用添加鏈表、設置閾值、對比增量等方法，有效地改進了傳統算法計算量復雜，數據龐大等缺點；針對傳統基于二叉樹的層次包圍盒構建過程費時、效率不高等問題提出了運用動態分裂平面的方法，提高了包圍盒樹構建效率。結合實驗仿真，充分驗證本算法的有效性，同時對比數據結果可知，該算法在速度、精度方面較其他算法對比均有明顯改善。

[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] 寧濤,郭晨,張升文.用混合包圍盒優化碰撞檢測方法[J].計算機工程與應用,2011,47(1):1-3.

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

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

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

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

[7] 王祎.虛擬現實中碰撞檢測關鍵技術研究[D].吉林:吉林大學,2009.

[8] 楊巧艷.基于OBB碰撞檢測算法研究[D].天津:河北工業大學,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] 王娟,賴思渝,李明東.依賴表面提取的二次空間分解碰撞檢測方法[J].計算機工程與應用,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。國家高技術研究發展計劃項目(2013AA 040604)。王崴，副教授，主研領域：機器視覺及自動控制。周誠，碩士生。楊云，副教授。彭勃宇，碩士生。

TP391.9

A

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