基于分層包圍盒的線纜與剛性體碰撞檢測算法

馬龍，任衛武，沈杰，劉侃

(1.武漢軍械士官學校，武漢 430075;2.上海航天局第八〇三研究所，上海 200233)

基于分層包圍盒的線纜與剛性體碰撞檢測算法

馬龍1，任衛武1，沈杰2，劉侃1

(1.武漢軍械士官學校，武漢 430075;2.上海航天局第八〇三研究所，上海 200233)

基于B樣條繪制的線纜模型逼真度高、計算量小，被廣泛應用于虛擬現實環境，但其碰撞檢測算法鮮見研究。提出基于圖像的算法，分3層對待檢測鏈表中的剛性體和線纜進行碰撞檢測。3層碰撞檢測分別是:線纜包圍盒與剛性體包圍盒碰撞檢測;線纜與剛性體包圍盒碰撞檢測;面片層線纜與剛性體碰撞精確檢測。每一層檢測均基于模型在坐標面的投影是否相交來判斷碰撞。應用表明:該算法能滿足虛擬維修真實感的需要。

線纜;剛性體;碰撞檢測;虛擬維修

碰撞檢測也稱為干涉檢測或接觸檢測，它基于現實世界中一個普遍存在的事實:空間上的一個點不可能被兩個不同的物體同時占有。碰撞檢測作為虛擬現實系統中的一個關鍵組成部分，主要任務是判斷物體模型之間、模型與場景之間是否發生了碰撞，并給出碰撞位置、穿刺深度等信息［1］。

近幾年，碰撞檢測技術的研究重點逐漸轉移到柔性體上，如人體的器官軟組織或布料［2-3］，其算法基本通過改進剛性體碰撞檢測算法獲得。目前，關于線纜的碰撞檢測研究較少，對基于B樣條繪制的線纜模型尚未見可直接使用的碰撞檢測算法。隨著裝備虛擬維修技術研究的逐漸深入，線纜碰撞檢測必將成為虛擬現實領域新的研究熱點。

本文采用基于圖像的算法，分3層對待檢測鏈表中的剛性體和線纜進行碰撞檢測。3層碰撞檢測分別是:1)線纜包圍盒與剛性體包圍盒碰撞檢測;2)線纜與剛性體包圍盒碰撞檢測;3)面片層線纜與剛性體碰撞精確檢測。每一層檢測均基于模型在坐標面的投影是否相交來判斷碰撞。

1 包圍盒間碰撞檢測

基于B樣條的線纜幾何建模算法通常將線纜中心線看作是一系列有次序的3次開放B樣條曲線段。根據B樣條的凸包性質［4］，可以通過對每一個曲線段構建包圍盒(或球)，逐段包圍線纜中心線。

系統中剛性體包圍盒采用AABB(axis-aligned bounding box［5-6］)，本文使用類似方法構建線纜的包圍盒。構建基本過程可以描述為:單段3次開放均勻B樣條曲線有4個控制點(V0，V1，V2，V3)，通過控制點分別作與坐標面平行的鉛垂面，然后通過位置最高和最低的控制點作水平面(水平面與XOY面平行，鉛垂面與XOZ面或YOZ面平行)，根據B樣條的凸包性質，線纜中心線必然位于這6個面圍成的包圍盒內(含表面，下同，稱該包圍盒為Original Box，簡稱OB);為了將整個線纜包圍進去，將包圍盒的每個面向外移動線纜的半徑r，這樣線纜必然全部位于擴大后的包圍盒(expanded box，EB)內。該包圍盒在二維平面的投影如圖1所示。

圖1 包圍盒在二維平面投影

線纜包圍盒與剛性體的包圍盒碰撞檢測算法與剛性體包圍盒之間碰撞檢測算法類似，具體如下:

在投影坐標系下，建立待檢測列表中零組件(包括線纜)在XOY面的包圍盒(如圖2所示，圖中每一個長方形由2個點來確定)。設P代表線纜部件的包圍盒，則確定它所對應長方形的2個點分別是右上角頂點P1(Xmax，Ymax)和左下角頂點P0(Xmin，Ymin)，它們分別是零組件(X，Y)值的最大點和最小點。設待檢測物體的任意點坐標為M(X，Y)，將滿足X＜Xmin或X＞Xmax或Y＜Ymin或Y ＞Ymax的零組件排除待檢測列表。如圖2所示，將物體M排除待檢測列表。

圖2 包圍盒碰撞檢測

2 線纜與剛性體包圍盒碰撞檢測

線纜在虛擬環境中的跨度可能會很大，運動中的EB可能會頻繁地碰撞多個AABB。這樣，如果在包圍盒碰撞檢測后直接進行面片檢測，必然導致檢測的計算量很大，因此有必要提出一種算法進一步排除不可能碰撞的物體。

最容易想到的方法是對EB或AABB進行層次劃分，如BSP方法。但是這種方法需要重復檢測子包圍盒的碰撞情況并給出層次劃分的終止條件。當虛擬環境下線纜碰撞多個剛性體時，這種方法很難實現實時性。

本文根據線纜的幾何特征及B樣條的性質，提出了一種基于圖像的進一步碰撞檢測算法。算法的基本思想如下:1)將虛擬環境下剛性體包圍盒AABB的每個面向外移動線纜的半徑r，構成EAABB(expand axis-aligned bounding box);2)構建OB，并與EAABB進行碰撞檢測，如果OB與EAABB沒有交集，則線纜與剛性體不會發生碰撞;3)如果二者有交集，則線纜與剛性體可能發生碰撞。此時，進一步判斷線纜中心線上是否存在一點在EAABB內。如果不存在，則線纜不可能與剛性體發生碰撞，如果存在則需要進行下一步更為精確的碰撞檢測。因此，目前的核心問題是判斷線纜中心線上是否存在一點位于EAABB內。

假設通過碰撞檢測，某段線纜的OB與某剛性體的EAABB發生碰撞。設P是該段線纜中心線上的任一點，(xp(u)，yp(u)，zp(u))是其空間坐標。EAABB占據的空間為

那么，只有存在u滿足下列條件時線纜才有可能與剛性體發生碰撞:

換言之，如果不等式組(1)的實數解集不為空，則線纜有可能與剛性體發生碰撞;如果實數解集為空，則不會發生碰撞。

不等式組(1)由8個不等式組成，下面以xp(u)≥ax為例說明求解方法。

在線纜幾何建模結束后，每段線纜中心線(即單段3次開放均勻B樣條曲線)的4個控制點已經確定，u是曲線方程中包含的唯一變化參數，而且顯然xp(u)是一個三次多項式，因此可以假設

在復數范圍內，等式右端多項式必然可以分解為c3(u-d1)(u-d2)(u-d3)。于是，xp(u)≥ax即為

假設di(i=1，2，3)均為實數，且d1≤d2≤d3。如果c3＞0，則其解集為

如果c3＜0，則其解集為

如果di中存在非實數(即虛部不為零)，則它們必然成對出現(共軛復數)。不妨假設d2和d3是非實數，則必然有(u-d2)(u-d3)＞0，原不等式等效為

如果c3＞0，其解集為u≥d1;如果c3＜0，其解集為u≤d1。

如果c3=0，則c0+c1u+c2u2+c3u3變為更簡單的二次多項式，這里不再贅述。其他不等式的求解與之類似。

如果式(1)的8個不等式解集的交集不為空，則說明線纜中心線必然有一段(或一點)在EAABB內部。否則，線纜與剛性體不會發生碰撞。

3 面片層碰撞檢測

面片層碰撞檢測的研究對象是組成物體的最基本單元，在輕量化模型中這些基本單元是各種形狀的三角面片。三維空間中的面片層無疑是最耗費資源的運算，平面內三角面相交測試的計算復雜度遠小于三維空間三角面的相交測試。通過降低維度將三維空間里的對象相交問題轉化到二維空間處理可有效提高相交測試效率。因此，有必要采用投影法降低維度來簡化運算。

二維三角面相交測試方法:設2個三角形T1 與T2，測試T1的3條邊與T2的3條邊是否相交。如果有一對邊相交，則2個三角形相交;如果每對邊都不相交，則進一步進行頂點與三角形的測試，以此來判斷T1是否在T2內部或者T2是否在T1內部;如果T1和T2互不包含，則T1和T2不相交。

經過面片層碰撞檢測可以確定2物體是否確實發生了碰撞。循環精確碰撞檢測過程以確定所有可能發生碰撞物體之間的碰撞情況。

綜合上述，碰撞檢測流程如圖3所示。

圖3 D＆R碰撞檢測流程

將上述算法應用于某虛擬現實系統能夠準確檢測線纜與剛性體之間的碰撞。碰撞結果將作為線纜重繪的約束條件，從而建立正確的線纜幾何模型(如圖4所示)，驗證了算法的正確性。

圖4 某虛擬現實系統中的線纜幾何模型

4 結束語

目前，剛性體碰撞檢測算法已經較為成熟，但對于柔性體參與的碰撞，檢測算法還有待進一步研究。隨著線纜幾何建模技術的日益完善，其碰撞檢測算法逐漸成為構建多體虛擬現實系統的關鍵環節之一。本文針對線纜與剛性體的碰撞檢測展開研究，主要完成以下工作:1)利用B樣條的凸包性質成功構建了線纜包圍盒;2)基于二維投影相交測試成功實現了線纜包圍盒與剛性體包圍盒的碰撞檢測;3)通過化簡求解三次不等式組成功實現了線纜與剛性體包圍盒的碰撞檢測;4)通過二維三角形面相交測試成功實現了線纜與剛性體面片層的碰撞檢測。下一步研究的重點是線纜與線纜之間的碰撞檢測。

［1］ERICSON CHRISTER.Real-timecollisiondetection ［M］.Morgan Kaufmann Publishers Inc，2005.

［2］吳崢，謝叻，馬浩博.虛擬手術實時物體碰撞檢測和軟組織變形研究［J］.計算機仿真，2010，27(2):255 -259.

［3］劉智斌，李占利，曹寶香.虛擬環境中織物的碰撞檢測及響應［J］.系統仿真學報，2007，19(7):1497-1500，1578.

［4］莫蓉，吳英，常智勇.計算機輔助幾何造型枝術［M］.北京:科學出版社，2004:58-62.

［5］鄒益勝，丁國富，許明恒，等.實時碰撞檢測算法綜述［J］.計算機應用研究，2008，25(1):8-11.

［6］潘振寬，崔樹娟，張繼萍，等.基于層次包圍盒的碰撞檢測方法［J］.青島大學學報:自然科學版，2005，18: 71-76.

(責任編輯 楊黎麗)

Collision Detection Algorithm of Cable and Rigid Body by Hierarchical Bounding Box

MA Long1，REN Wei-wu1，SHEN Jie2，LIU Kan1
(1 Wuhan Mechanical College，Wuhan 430075，China; 2.No.803 Institute of Shanghai Aerospace Bureau，Shanghai 200233，China)

The model of cable based on B-spline consists of high fidelity and small amount of calculation.It has been used in VR early.However，the collision detection is rarely researched.An algorithm based on projection is proposed.It detects the collisions of cable and rigid bodies within detection list by three steps.First is the collision detection of the bounding boxes of cable and rigid bodies; Second is cable and rigid bodies’box;Third is cable and rigid bodies by triangle facets intersection test.The application shows that the algorithm consists high fidelity and small amount of calculation in virtual maintenance.

cable;rigid body;collision detection;virtual maintenance

TP391.9

A

1674-8425(2014)08-0098-04

10.3969/j.issn.1674-8425(z).2014.08.020

2014-01-09

馬龍(1988—)，男，河南新蔡人，碩士研究生，主要從事武器系統仿真研究。

馬龍，任衛武，沈杰，等.基于分層包圍盒的線纜與剛性體碰撞檢測算法［J］.重慶理工大學學報:自然科學版，2014(8):98-101.

format:MA Long，REN Wei-wu，SHEN Jie，et al.Collision Detection Algorithm of Cable and Rigid Body by Hierarchical Bounding Box［J］.Journal of Chongqing University of Technology:Natural Science，2014(8):98-101.