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

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

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

1 包圍盒的建立

1.1 幾何建模過程

本文的碰撞檢測是建立在早期的幾何建模的基礎之上的，因此有必要簡要介紹一下幾何建模過程。

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

圖1 三角形面片頂點索引Fig.1 Vertex index for triangular facets

圖2 幾何建模過程Fig.2 The process of geometric modeling

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

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

1.2 建立上層及底層包圍盒

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

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

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

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

1.3 包圍盒的更新

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

2 碰撞檢測算法的實現(xiàn)

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

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

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

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

2.1 上層包圍盒的相交測試

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

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

2.2 底層包圍盒的相交測試

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

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

2.3 三角形面片的幾何相交測試

該部分實際上可以看作是檢測三維空間上的2個三角形是否相交的問題，采用穿越算法［12］來完成該部分檢測。該算法步驟分為3步:

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

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

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

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

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

其中，

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

同理，可以得到Gm點的坐標和線段

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

若式(7)中的am1、am2、am3同時大于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同時成立的話，則可以推斷出與三角形△A［3m］A［3m+1］A［3m+2］的一條邊相交。同理，也可以通過該方法檢測是否與該三角形的其他兩條邊相交。若檢測出位于三角形△A［3m］A［3m+1］A［3m+2］的內(nèi)部或者與其任意一條邊相交的話，則可以斷定手術器械與手術之間的碰撞發(fā)生。

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

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

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

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

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

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

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

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

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

Switch(num_section)

{

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

…

…

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

}

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

if(碰撞檢測開始)

{

t1=timeGetTime();

do

{碰撞檢測}

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

t2=timeGetTime();

collision_time=t2－t1;

}

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

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

3.2 預測碰撞檢測法

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

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

在表1的基礎上加上預測碰撞檢測法，記錄之前5組值，如表2。

圖12 手術器械運動軌跡Fig.12 The trajectory of surgical instrument

表2 預測碰撞檢測算法效率Table 2 The efficiency of predicted collision detection

3 結(jié)束語

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

［1］呂婷，劉桂鈴，杜海洲，等.虛擬現(xiàn)實技術在生物醫(yī)學領域中的應用［J］.中國組織工程研究與臨床康復，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］馬登武，葉文，李瑛.基于包圍盒的碰撞檢測算法綜述［J］.系統(tǒng)仿真學報，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］鄒益勝，丁國富，許明恒，等.實時碰撞檢測算法綜述［J］.計算機應用研究，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］史紅兵，張毅彬，童若鋒，等.虛擬場景自動漫游的路徑規(guī)劃算法［J］.計算機輔助設計與圖形學學報，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］謝倩茹，耿國華.虛擬手術中的快速碰撞檢測算法［J］.計算機應用，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.