面向虛擬手術(shù)的碰撞檢測(cè)優(yōu)化算法

于凌濤，王濤，宋華建，王正雨，張寶玉

(哈爾濱工程大學(xué)機(jī)電工程學(xué)院，黑龍江哈爾濱150001)

對(duì)于實(shí)習(xí)醫(yī)生來(lái)說(shuō)，傳統(tǒng)手術(shù)訓(xùn)練方法存在很多問(wèn)題，包括使用費(fèi)用、倫理道德、動(dòng)物與人體組織的區(qū)別以及使用人體尸源匱乏等，給手術(shù)培訓(xùn)帶來(lái)了極大的不便。本文建立一個(gè)的虛擬手術(shù)模擬系統(tǒng)可以有效解決這一矛盾。虛擬手術(shù)模擬系統(tǒng)，即通過(guò)精確的人體組織器官造型，來(lái)逼真的模擬組織器官在手術(shù)器械的外力交互作用下產(chǎn)生變形乃至被切割的過(guò)程，并通過(guò)視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)以及其他通道的感官反饋來(lái)提供逼真的手術(shù)感覺(jué)［1］。虛擬手術(shù)中碰撞檢測(cè)用來(lái)解決虛擬環(huán)境中對(duì)象之間是否碰撞，何時(shí)碰撞，何處碰撞3個(gè)問(wèn)題［2］。由于虛擬手術(shù)中，人體的信息數(shù)據(jù)非常大，快速而精確的進(jìn)行三維空間物體的碰撞檢測(cè)是目前虛擬手術(shù)中實(shí)現(xiàn)實(shí)時(shí)操作的重要課題之一［3－4］。常用的碰撞檢測(cè)算法主要有包圍盒的檢測(cè)方法以及空間分割的檢測(cè)方法［5］。目前國(guó)內(nèi)外對(duì)于包圍盒算法的研究主要集中于提高碰撞檢測(cè)算法的效率上以及相交測(cè)試的精確度上。Maciel等［6-7］在包圍盒方面做出了一些研究，但是由于包圍盒自身的原因，往往碰撞檢測(cè)效率不能達(dá)到要求，特別是當(dāng)虛擬對(duì)象有上萬(wàn)個(gè)單元體時(shí)，碰撞檢測(cè)不能很好的滿足虛擬手術(shù)實(shí)時(shí)性。近年來(lái)，隨著計(jì)算機(jī)性能的提高也有很多使用硬件加速等方法來(lái)加快碰撞檢測(cè)的方法，Kim［8］等通過(guò)負(fù)載平衡策略在CPU與GPU之間進(jìn)行合理調(diào)配來(lái)提高算法的整體效率。本文基于混合包圍盒碰撞檢測(cè)法，對(duì)包圍盒中的單元體進(jìn)行分區(qū)域檢測(cè)以及通過(guò)相鄰三角形來(lái)預(yù)測(cè)下一周期的可能發(fā)生碰撞的單元體等算法優(yōu)化，以提高碰撞檢測(cè)算法快速性與精確性。

1 包圍盒的建立

1.1 幾何建模過(guò)程

本文的碰撞檢測(cè)是建立在早期的幾何建模的基礎(chǔ)之上的，因此有必要簡(jiǎn)要介紹一下幾何建模過(guò)程。

首先利用3ds Max軟件建造一個(gè)膽囊模型，在VC++環(huán)境下編寫(xiě)導(dǎo)入程序讀取并存儲(chǔ)僅僅與膽囊模型后期重建有關(guān)的輪廓頂點(diǎn)及面片信息，同時(shí)丟棄與重建無(wú)關(guān)的材質(zhì)，光照、紋理、貼圖等信息，在重建過(guò)程中只需讀取膽囊輪廓頂點(diǎn)及面片數(shù)據(jù)，不再需要讀入整個(gè)3DS文件。然后對(duì)三角形面片頂點(diǎn)信息在頂點(diǎn)序列中進(jìn)行索引，如圖1所示，三角形面片的3個(gè)端點(diǎn)坐標(biāo)可以通過(guò)從頂點(diǎn)坐標(biāo)數(shù)組中索引得到，如第32個(gè)三角形的3個(gè)端點(diǎn)分別對(duì)應(yīng)頂點(diǎn)序列中的第35、48、156個(gè)頂點(diǎn)。同時(shí)，將這些三角形面片相互關(guān)聯(lián)起來(lái)，當(dāng)改變某一個(gè)三角形的形狀，其他的的三角形都會(huì)發(fā)生改變，在后續(xù)工作中只需改變頂點(diǎn)的坐標(biāo)值，就可改變膽囊的位置以及形狀的變化。整個(gè)幾何建模的具體過(guò)程如圖2所示。

圖1 三角形面片頂點(diǎn)索引Fig.1 Vertex index for triangular facets

圖2 幾何建模過(guò)程Fig.2 The process of geometric modeling

將膽囊模型的頂點(diǎn)及面片信息在VC++環(huán)境中利用OpenGL重繪之后，再經(jīng)過(guò)計(jì)算頂點(diǎn)法向量、添加鏡面反射和抗鋸齒功能后的膽囊及手術(shù)器械模型如圖3所示。

圖3 手術(shù)膽囊及手術(shù)器械Fig.3 The gallbladder and surgical instrument

1.2 建立上層及底層包圍盒

一般的包圍體有球包圍盒(Sphere)，軸對(duì)稱(chēng)包圍盒(AABB)，方向包圍盒(OBB)和離散方向多面體包圍盒(K-DOPs)等［9］。一般而言，都是采用構(gòu)建層次二叉樹(shù)的方式自頂向下或者自底向上地建立層次包圍盒樹(shù)［10］.本文摒棄這種思想，建立一個(gè)上層包圍盒以及底層包圍盒，以便后文碰撞檢測(cè)算法的優(yōu)化。所謂的上層包圍盒是一個(gè)剛好能夠緊密包圍住手術(shù)對(duì)象或者手術(shù)器械的包圍盒，主要是應(yīng)用于粗略碰撞階段。底層包圍盒就是一個(gè)針對(duì)于手術(shù)對(duì)象或者器械幾何單元體的包圍盒，主要是應(yīng)用于精確碰撞階段。只有上層包圍盒相交后，才有必要去檢測(cè)底層包圍盒是否相交。

本文所討論的虛擬膽囊由2部分組成:膽囊體及膽囊管。膽囊管只是為了使整個(gè)虛擬手術(shù)在視覺(jué)上更加逼真，使醫(yī)生具有身臨其境的感覺(jué)，而實(shí)際上它是不參與整個(gè)手術(shù)過(guò)程的，可以將其與整個(gè)膽囊手術(shù)分離開(kāi)來(lái)。膽囊體部分為近似橢圓形結(jié)構(gòu)，因此采用軸對(duì)稱(chēng)包圍盒(AABB)。同樣手術(shù)器械實(shí)際上參與到虛擬手術(shù)中的只有末端部分，因此手術(shù)器械部分采用球包圍盒。綜上所述，本文的上層包圍盒采用S-AABB混合包圍盒進(jìn)行粗略的相交測(cè)試。構(gòu)成一個(gè)AABB包圍盒只要6個(gè)參數(shù)，即被包圍對(duì)象中所有頂點(diǎn)在X軸、Y軸、Z軸的最大值以及最小值 (xmax，xmin，ymax，ymin，zmax，zmin)。只要遍歷膽囊體的所有頂點(diǎn)坐標(biāo)就可以得到這6個(gè)參數(shù)，從而獲得AABB包圍盒。構(gòu)成一個(gè)球包圍盒只需要4個(gè)參數(shù)，即器械末端包圍球的中心以及半徑:(x0，y0，z0，r)，便可得到上層包圍盒，如圖4(a)所示。

底層包圍盒主要是針對(duì)構(gòu)成手術(shù)器械與手術(shù)對(duì)象的幾何單元體的包圍盒。幾何建模中的對(duì)象是由三角形面片構(gòu)成的，故底層包圍盒均采用球包圍盒。為每一個(gè)三角形面片構(gòu)建求球包圍盒的方法是:找出每一個(gè)三角形面片的外接圓，圓心為Ow，半徑為rw，再以O(shè)w為球心，以rw為半徑，得到的球即為每一個(gè)三角形面片的球包圍盒。得到的底層包圍盒如圖4(b)所示。

圖4 上層及底層包圍盒Fig.4 The upper and bottom bounding box

1.3 包圍盒的更新

上述建立的包圍盒過(guò)程是在離線狀態(tài)下完成的，即在虛擬手術(shù)開(kāi)始之前，已經(jīng)建立好幾何模型以及包圍盒。而實(shí)際上在手術(shù)過(guò)程中，醫(yī)生會(huì)隨時(shí)通過(guò)旋轉(zhuǎn)膽囊的角度以及移動(dòng)膽囊的位置來(lái)確定自己的視野，甚至?xí)鼓懩耶a(chǎn)生形變。由幾何建模部分已知虛擬對(duì)象是由三角形面片構(gòu)成的，而每一個(gè)三角形面片是由頂點(diǎn)序列中某3個(gè)頂點(diǎn)構(gòu)成的，所以在醫(yī)生移動(dòng)或旋轉(zhuǎn)虛擬對(duì)象時(shí)只需要將頂點(diǎn)序列乘以相應(yīng)的移動(dòng)或旋轉(zhuǎn)矩陣即可［11-12］。同時(shí)也將底層球包圍盒的相關(guān)信息(球心坐標(biāo)及半徑)保存在相關(guān)的數(shù)組中，在手術(shù)過(guò)程中只需要將其乘以相關(guān)的移動(dòng)或者旋轉(zhuǎn)矩陣就可達(dá)到更新的目的，而不是重新計(jì)算所有的包圍盒。

2 碰撞檢測(cè)算法的實(shí)現(xiàn)

為了提高碰撞檢測(cè)的效率，減少該部分所消耗的時(shí)間，將碰撞檢測(cè)的內(nèi)容分為3步:

1)上層包圍盒的相交測(cè)試;

2)底層包圍盒的相交測(cè)試;

3)基本幾何圖元的相交測(cè)試。

2.1 上層包圍盒的相交測(cè)試

球包圍盒與AABB包圍盒相交檢測(cè)問(wèn)題可以轉(zhuǎn)化到二維平面上來(lái)解決。若2個(gè)包圍盒在XOY、YOZ、XOZ這3個(gè)平面的投影都相交的話，那么這2個(gè)包圍盒必定相交，因此可以在3個(gè)二維平面上判定2個(gè)包圍盒是否相交。如圖5所示，將2個(gè)包圍盒投影至XOY平面上，x0－r，x0+r，y0－r，y0+r可以表示球包圍盒在XOY投影面上的極值。若4個(gè)不等式(x0－r＜xmax、x0+r＞xmin、y0－r＜ymax和y0+r＞ymin)同時(shí)都成立的話，2個(gè)包圍盒在XOY面上的投影必定相交。根據(jù)該判別方法也可以得出包圍盒在XOZ以及YOZ2個(gè)投影面上是否相交。實(shí)際上，若6個(gè)不等式x0－r＜xmax、x0+r＞xmin、y0－r＜ymax、y0+r＞ymin、z0－r＜zmax和z0+r＞zmin同時(shí)成立的話，2個(gè)包圍盒必定相交。

圖5 上層包圍盒相交測(cè)試Fig.5 Intersection test of upper bounding box

2.2 底層包圍盒的相交測(cè)試

該部分是手術(shù)對(duì)象與手術(shù)器械之間的底層包圍盒的測(cè)試，一般使手術(shù)器械的所有球包圍盒逐個(gè)的遍歷手術(shù)對(duì)象的所有球包圍盒。如圖5所示，當(dāng)手術(shù)器械包圍球的半徑與手術(shù)對(duì)象包圍球的半徑之和大于兩球心Om與On之間的距離，即rn+rm＜dmn時(shí)2個(gè)底層包圍盒相交，接下來(lái)進(jìn)行被包圍的三角形面片的幾何相交測(cè)試。

圖6 底層包圍盒相交測(cè)試Fig.6 Intersection test of bottom bounding box

2.3 三角形面片的幾何相交測(cè)試

該部分實(shí)際上可以看作是檢測(cè)三維空間上的2個(gè)三角形是否相交的問(wèn)題，采用穿越算法［12］來(lái)完成該部分檢測(cè)。該算法步驟分為3步:

1)確定手術(shù)三角形A所在的平面。若三角形B的所有頂點(diǎn)位于該平面的一側(cè)，則測(cè)試退出并返回不相交信息;

2)計(jì)算三角形A與三角形B的相交線段，且該線段位于三角形A所在的平面內(nèi);

3)測(cè)試第二部中的相交線段是否相交于或者包含于三角形A。若是，則兩三角形相交。

如圖 7 所示，A［3m］A［3m+1］A［3m+2］為手術(shù)對(duì)象的第m個(gè)三角形面片，B［3n］B［3n+1］B［3n+2］為手術(shù)器械的第n個(gè)三角形面片。首先計(jì)算出A［3m］A［3m+1］A［3m+2］所在平面 Фm的法向量nm，通過(guò)判斷l(xiāng)1的正負(fù)號(hào)來(lái)判定三角形B［3n］B［3n+1］B［3n+2］的3 個(gè)點(diǎn)是否位于 Фm的同一側(cè)，假定l1≤ 0，同時(shí)l2≥ 0，l3≥ 0，則表示B［3n］位于一側(cè)，B［3n+1］和B［3n+2］位于另外一側(cè)。

接下來(lái)要找出三角形B［3n］B［3n+1］B［3n+2］與平面Фm的相交線段由圖已知:

其中，

根據(jù)式(1)和(2)可以得出:

同理，可以得到Gm點(diǎn)的坐標(biāo)和線段

式中:向 量nm1、nm2、nm3均 為 三 角 形A［3m］A［3m+1］A［3m+2］所在平面的法向量，將其兩兩相乘，即:

若式(7)中的am1、am2、am3同時(shí)大于0的話，表示nm1、nm2、nm3同向，由此可以推出Fm包含于三角形A［3m］A［3m+1］A［3m+2］。下面討論相交的情況:

將式(8)～ (11)中的nm1'叉乘nm2'，nm3'叉乘nm4'，即:

若a12＜0成立，則表示Fm'與Gm'位于線段A［3m］A［3m+1］的兩側(cè);若a34＜ 0，則表示A［3m］與A［3m+1］位于的兩側(cè);若a12＜0與a34＜0同時(shí)成立的話，則可以推斷出與三角形△A［3m］A［3m+1］A［3m+2］的一條邊相交。同理，也可以通過(guò)該方法檢測(cè)是否與該三角形的其他兩條邊相交。若檢測(cè)出位于三角形△A［3m］A［3m+1］A［3m+2］的內(nèi)部或者與其任意一條邊相交的話，則可以斷定手術(shù)器械與手術(shù)之間的碰撞發(fā)生。

圖7 三角形相交測(cè)試Fig.7 Intersection test of triangular facets

3 碰撞檢測(cè)算法的優(yōu)化

由于在本文算法中沒(méi)有建立層次包圍盒樹(shù)，每一個(gè)周期內(nèi)，手術(shù)器械的每一個(gè)三角形面片都要逐個(gè)的去遍歷手術(shù)對(duì)象的所有三角形，必定會(huì)消耗過(guò)多的時(shí)間，因此對(duì)碰撞算法進(jìn)行優(yōu)化是非常有必要的。本文主要是在兩方面進(jìn)行優(yōu)化:一方面是通過(guò)分區(qū)域檢測(cè)法來(lái)快速的定位發(fā)生碰撞的三角形面片;另外一方面是當(dāng)碰撞發(fā)生后，通過(guò)相鄰三角形面片來(lái)預(yù)測(cè)碰撞的發(fā)生。

3.1 分區(qū)碰撞檢測(cè)法

在離線狀態(tài)(手術(shù)未開(kāi)始之前)下，將初始AABB包圍盒平分為20個(gè)對(duì)稱(chēng)的長(zhǎng)方體碰撞區(qū)域，共5層，每層4個(gè)，如圖8所示。在每一層的4個(gè)長(zhǎng)方體都是對(duì)稱(chēng)劃分，每一層的高度相等，在z軸上平均劃分，每一個(gè)長(zhǎng)方體的邊界坐標(biāo)及中心坐標(biāo)點(diǎn)坐標(biāo)可以通過(guò)搜索包圍盒的各極值點(diǎn)獲得。

圖8 碰撞區(qū)域的劃分Fig.8 The division for collision regions

碰撞區(qū)域劃分完成之后，需要將手術(shù)對(duì)象的三角形面片歸類(lèi)，找出其所屬區(qū)域?？梢酝ㄟ^(guò)判斷三角形面片與長(zhǎng)方體區(qū)域的幾何關(guān)系(包含、相交與相離)找出其所屬區(qū)域。上述工作都是在離線狀態(tài)下完成的，當(dāng)三角形面片找到其所屬區(qū)域后便被歸類(lèi)到該區(qū)域的面片數(shù)組中，永久與其綁定。通過(guò)該方法就可以找出膽囊每一個(gè)三角形面片所屬的碰撞區(qū)域。劃分區(qū)域后的手術(shù)膽囊如圖9所示。

圖9 手術(shù)膽囊分區(qū)圖Fig.9 The region division of surgical gallbladder

碰撞檢測(cè)開(kāi)始后，首先檢測(cè)上層包圍盒是否相交，若相交，進(jìn)行底層包圍盒相交測(cè)試。實(shí)際上手術(shù)膽囊的面片是遠(yuǎn)遠(yuǎn)大于手術(shù)器械的三角形面片的，因此可以將手術(shù)器械的底層包圍球近似的看成被球心所代替的質(zhì)點(diǎn)。相交測(cè)試之前手術(shù)器械的底層包圍盒需要通過(guò)比較其球心與20個(gè)對(duì)稱(chēng)碰撞區(qū)域中心點(diǎn)的距離找出與其相距最近的碰撞區(qū)域，該包圍盒只能與此區(qū)域中的某一個(gè)底層包圍盒相交，找到距離最近的碰撞區(qū)域后利用switch語(yǔ)句來(lái)進(jìn)行后續(xù)的碰撞檢測(cè)，如下:

Switch(num_section)

{

Case 0:執(zhí)行器械面片與區(qū)域0的碰撞檢測(cè);break;

…

…

Case 19:執(zhí)行器械面片與區(qū)域19的碰撞檢測(cè);break;

}

在VC++環(huán)境下，用timeGetTime()函數(shù)來(lái)記錄碰撞檢測(cè)，為了提高檢測(cè)精度，將算法循環(huán)5遍。當(dāng)上層包圍盒相交后開(kāi)始計(jì)時(shí)，直至碰撞檢測(cè)結(jié)束:

if(碰撞檢測(cè)開(kāi)始)

{

t1=timeGetTime();

do

{碰撞檢測(cè)}

while(碰撞檢測(cè)結(jié)束);

t2=timeGetTime();

collision_time=t2－t1;

}

手術(shù)器械面片數(shù)為1 008，手術(shù)膽囊面片數(shù)為228。采集幾組數(shù)據(jù)，對(duì)比出分區(qū)算法的優(yōu)越性，如表1所示。

表1 2種算法的效率對(duì)比Table 1 Comparison of the two algorithms

3.2 預(yù)測(cè)碰撞檢測(cè)法

碰撞發(fā)生后，表示虛擬器械與虛擬膽囊相接觸，接觸之后虛擬器械的位置是隨著醫(yī)生手的移動(dòng)而不斷變化的，在下一個(gè)周期內(nèi)器械的位置有3種情況:1)器械遠(yuǎn)離膽囊，不再產(chǎn)生碰撞;2)器械依然與該三角形面片發(fā)生碰撞;3)器械與其他三角形碰撞.在下一個(gè)周期內(nèi)上述情況都有可能發(fā)生，所以虛擬器械中所有三角形面片需要重新遍歷膽囊上的所有三角形面片，檢測(cè)是否發(fā)生碰撞，然而這個(gè)計(jì)算過(guò)程是非常昂貴的，當(dāng)三角形面片足夠多的時(shí)候必定會(huì)嚴(yán)重影響整個(gè)虛擬手術(shù)的實(shí)時(shí)性。醫(yī)生在手術(shù)過(guò)程中移動(dòng)器械的過(guò)程是連續(xù)的，并且為了獲得有效的視覺(jué)效應(yīng)，整個(gè)虛擬手術(shù)算法每一次循環(huán)計(jì)算的周期是十分短的，也可以被看作是連續(xù)的。因此可以預(yù)測(cè)出下一周期可能發(fā)生碰撞的三角形面片。如圖10所示，假設(shè)虛擬器械與第0個(gè)三角形面片發(fā)生碰撞，第1～14個(gè)三角形與第0個(gè)三角形相鄰.在下一個(gè)周期內(nèi)，虛擬器械最有可能與這15個(gè)三角形中的某一個(gè)三角形發(fā)生碰撞，因此應(yīng)該優(yōu)先檢測(cè)虛擬器械中的三角形面片是否與這15個(gè)三角形面片發(fā)生碰撞，而不是遍歷膽囊上原有三角形，這必將大大減少整個(gè)碰撞檢測(cè)過(guò)程所需要的時(shí)間。利用三角形的3個(gè)頂點(diǎn)找出每一個(gè)三角形面片的所有相鄰三角形面片，將它們分別存放在單獨(dú)的列表中，在手術(shù)過(guò)程中若檢測(cè)到虛擬器械與某一個(gè)三角形面片發(fā)生碰撞，至少需要調(diào)用出與之相鄰的三角形面片來(lái)進(jìn)行下一步的碰撞檢測(cè)即可，其檢測(cè)過(guò)程如圖11所示。

如圖12所示，手術(shù)器械的運(yùn)動(dòng)軌跡為A→B→C。A到B的是碰撞未發(fā)生到碰撞發(fā)生的過(guò)程，因此可以假如分區(qū)碰撞檢測(cè)算法進(jìn)行優(yōu)化。B到C的過(guò)程手術(shù)器械與手術(shù)膽囊一直處于碰撞狀態(tài)，因此沒(méi)有必要重新遍歷所有三角形面片，可以采用相鄰三角形預(yù)測(cè)碰撞檢測(cè)法來(lái)進(jìn)行優(yōu)化。

在表1的基礎(chǔ)上加上預(yù)測(cè)碰撞檢測(cè)法，記錄之前5組值，如表2。

圖12 手術(shù)器械運(yùn)動(dòng)軌跡Fig.12 The trajectory of surgical instrument

表2 預(yù)測(cè)碰撞檢測(cè)算法效率Table 2 The efficiency of predicted collision detection

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

綜上，利用分區(qū)碰撞檢測(cè)，在指定區(qū)域的三角形面片進(jìn)行碰撞檢測(cè)，而不再遍歷虛擬膽囊所有的三角形面片，大大提高了碰撞檢測(cè)的效率;同時(shí)在連續(xù)碰撞時(shí)刻，利用相鄰搜索三角形面片來(lái)預(yù)測(cè)出可能發(fā)生碰撞的面片來(lái)進(jìn)行碰撞檢測(cè)，這也提高了檢測(cè)的效率。該碰撞檢測(cè)算法還可以用在以其他器官組織為對(duì)象的虛擬手術(shù)系統(tǒng)中。

［1］呂婷，劉桂鈴，杜海洲，等.虛擬現(xiàn)實(shí)技術(shù)在生物醫(yī)學(xué)領(lǐng)域中的應(yīng)用［J］.中國(guó)組織工程研究與臨床康復(fù)，2010，14(43):8099-8103.LV Ting，LIU Guiling，DU Haizhou，et al.Application of Virtual reality technique in biomedical field［J］.Journal of Clinical Rehabilitative Tissue Engineering Research，2010，14(43):8099-8103.

［2］馬登武，葉文，李瑛.基于包圍盒的碰撞檢測(cè)算法綜述［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18(4):1058-1064.MA Dengwu，YE Wen，LI Ying.Survey of box-based algorithms for collision detection［J］.Journal of System Simulation，2006，18(4):1058-1064.

［3］TAMURA Y，MIZUGUCHl N，MATSUMOT0 S，et al.Construction of virtual assembly system with real-time collision detection［C］//Proceedings of 17th International Conference on Artificial Reality and Telexistence(ICAT2007).Jylland，Denmark，2007:284-285.

［4］BRADY J L，Virtual surgery enhances surgeon training［J］.Biomedical Instrumentation and Technology，2008，42(1):13-14.

［5］鄒益勝，丁國(guó)富，許明恒，等.實(shí)時(shí)碰撞檢測(cè)算法綜述［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(1):8-12.ZOU Yisheng，DING Guofu，XU Mingheng，et al.Survey on real-time collision detection algorithms［J］.Application Research of Computers，2008，25(1):8-12.

［6］MACIEL A，BOULIE R，THALMANN D.Efficient collision detection within deforming spherical sliding contact［J］.IEEE Transactions on Visualization and Computer Graphics，2007，13(3):518-529.

［7］CHANG J W，WANG W P，KIM M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy［J］.Computer Aided Design，2008，42(1):50-57.

［8］KIM Y J，LIN M，MANOEHA D.Fast penetration depth estimation using rasterization hardware and hierarchical refinement［C］//Symposium on Computational Geometry.San Diego，USA，2003:386-387.

［9］LOM B，JEAN C，CANI M P，et al.Real-time collision detection for virtual surgery［C］//Proceedings of the 1999 Computer Animation.Geneva，Switz，1999:82-90.

［10］HU Songhua，YU Lizhen.Optimization of collision detection algorithm based on OBB［C］//International Conference on Measuring Technology and Mechatronics Automation.Changsha，China，2010:853-855.

［11］史紅兵，張毅彬，童若鋒，等.虛擬場(chǎng)景自動(dòng)漫游的路徑規(guī)劃算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18(4):592-597.SHI Hongbing，ZHANG Yibin，TONG Ruofeng，et al.Path planning for automated navigation in virtual environment［J］.Journal of Computer Aided Design ＆ Computer Graphics，2006，18(4):592-597.

［12］謝倩茹，耿國(guó)華.虛擬手術(shù)中的快速碰撞檢測(cè)算法［J］.計(jì)算機(jī)應(yīng)用，2012，32(3):719-721.XIE Qianru，GENG Guohua.Fast collision detection method in virtual surgery［J］.Journal of Computer Applications，2012，32(3):719-721.

［13］ANKUR B，SRIDHAR S，ARRISH K，et al.RoSS:Virtual reality robotic surgical simulator for the Da Vinci surgical system［C］//Symposium on Haptics Interfaces for Virtual Environment and Teleoperator Systems. Reno，USA，2008:479-480.