馬龍，任衛(wèi)武，沈杰，劉侃

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

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

馬龍1，任衛(wèi)武1，沈杰2，劉侃1

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

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

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

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

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

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

1 包圍盒間碰撞檢測

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

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

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

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

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

圖2 包圍盒碰撞檢測

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

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

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

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

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

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

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

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

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

在復(fù)數(shù)范圍內(nèi)，等式右端多項(xiàng)式必然可以分解為c3(u-d1)(u-d2)(u-d3)。于是，xp(u)≥ax即為

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

如果c3＜0，則其解集為

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

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

如果c3=0，則c0+c1u+c2u2+c3u3變?yōu)楦唵蔚亩味囗?xiàng)式，這里不再贅述。其他不等式的求解與之類似。

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

3 面片層碰撞檢測

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

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

經(jīng)過面片層碰撞檢測可以確定2物體是否確實(shí)發(fā)生了碰撞。循環(huán)精確碰撞檢測過程以確定所有可能發(fā)生碰撞物體之間的碰撞情況。

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

圖3 D＆R碰撞檢測流程

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

圖4 某虛擬現(xiàn)實(shí)系統(tǒng)中的線纜幾何模型

4 結(jié)束語

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

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

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

［3］劉智斌，李占利，曹寶香.虛擬環(huán)境中織物的碰撞檢測及響應(yīng)［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19(7):1497-1500，1578.

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

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

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

(責(zé)任編輯 楊黎麗)

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—)，男，河南新蔡人，碩士研究生，主要從事武器系統(tǒng)仿真研究。

馬龍，任衛(wèi)武，沈杰，等.基于分層包圍盒的線纜與剛性體碰撞檢測算法［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，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.