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

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

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

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

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

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

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

線纜;剛性體;碰撞檢測(cè);虛擬維修

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

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

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

1 包圍盒間碰撞檢測(cè)

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

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

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

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

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

圖2 包圍盒碰撞檢測(cè)

2 線纜與剛性體包圍盒碰撞檢測(cè)

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

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

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

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

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

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

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

在線纜幾何建模結(jié)束后，每段線纜中心線(即單段3次開(kāi)放均勻B樣條曲線)的4個(gè)控制點(diǎn)已經(jīng)確定，u是曲線方程中包含的唯一變化參數(shù)，而且顯然xp(u)是一個(gè)三次多項(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ù)(即虛部不為零)，則它們必然成對(duì)出現(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)楦?jiǎn)單的二次多項(xiàng)式，這里不再贅述。其他不等式的求解與之類(lèi)似。

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

3 面片層碰撞檢測(cè)

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

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

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

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

圖3 D＆R碰撞檢測(cè)流程

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

［6］潘振寬，崔樹(shù)娟，張繼萍，等.基于層次包圍盒的碰撞檢測(cè)方法［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)武，沈杰，等.基于分層包圍盒的線纜與剛性體碰撞檢測(cè)算法［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.