基于改進(jìn)軸向包圍盒算法的軟組織形變仿真

陳冬英

（福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108）

在醫(yī)學(xué)領(lǐng)域，手術(shù)作為一種醫(yī)療手段，常用來(lái)維持患者的健康。軟組織模型的三維重建是模擬軟組織形變的基礎(chǔ)，形變仿真效果的真實(shí)性與其模型的質(zhì)量密不可分[1]。

在虛擬手術(shù)中，為了模擬組織形變過(guò)程，應(yīng)當(dāng)實(shí)時(shí)檢測(cè)軟組織與其他手術(shù)器械的接觸情況，實(shí)時(shí)檢測(cè)碰撞包圍盒檢測(cè)算法是碰撞檢測(cè)中常用的方法，主要思路是用一個(gè)形狀規(guī)則的包圍盒近似地代替不規(guī)則的研究對(duì)象[2]。根據(jù)形狀的不同，包圍盒又可具體的分為：球形包圍盒 （sphere）[3]、方向包圍盒（oriented bounding box，OBB）[4]、軸向包圍盒（axis-aligned bounding box，AABB）[5]和離散有向多面體（k-DOP）[6]等。AABB與Sphere相對(duì)其他包圍盒具有結(jié)構(gòu)簡(jiǎn)單，緊密性好的特點(diǎn)，為確保模型的實(shí)時(shí)性并減小檢測(cè)誤差，較多采用AABB的碰撞檢測(cè)法對(duì)模型進(jìn)行處理。

AABB包圍盒檢測(cè)法雖然過(guò)程簡(jiǎn)單、計(jì)算量小，能夠保證虛擬手術(shù)中碰撞檢測(cè)的實(shí)時(shí)性，但該方法使用規(guī)則的長(zhǎng)方體來(lái)代替無(wú)規(guī)則的軟組織模型接受碰撞，不能精確檢測(cè)手術(shù)器械與軟組織中細(xì)節(jié)部位發(fā)生碰撞[7]。因此，檢測(cè)出來(lái)的結(jié)果存在明顯的誤差，導(dǎo)致了碰撞檢測(cè)的漏報(bào)和誤報(bào)。而三角面片相交的檢測(cè)方法雖然需要較大的計(jì)算量，但其對(duì)細(xì)節(jié)部分的處理相比AABB包圍盒碰撞檢測(cè)方法而言具有明顯的優(yōu)勢(shì)。將這種方法用在軟組織模型和手術(shù)器械相貼近的位置，就能夠?qū)χ付ㄐ巫儏^(qū)域的所有網(wǎng)格進(jìn)行劃分，并分別進(jìn)行檢測(cè)，從而使精確度大大提高。

為了提高軟組織受到碰撞時(shí)反饋的精確性，利用三角形面片相交的檢測(cè)方法能夠提高結(jié)果的精確度，AABB包圍盒碰撞檢測(cè)方法又能保證檢測(cè)的實(shí)時(shí)性，本節(jié)提出三角形面片相交與AABB相結(jié)合的碰撞檢測(cè)方法對(duì)其進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，在保證實(shí)時(shí)性與真實(shí)性均衡的情況下，提出的兩者結(jié)合的碰撞檢測(cè)法的實(shí)現(xiàn)效果較AABB包圍盒碰撞檢測(cè)法更為精確。

1 軟組織形變的AABB碰撞檢測(cè)法

軟組織在形變仿真過(guò)程中，AABB的碰撞檢測(cè)可分為三個(gè)步驟：AABB的建立、構(gòu)建以及樹的遍歷。

1.1 AABB的建立

首先，選擇一個(gè)合適的包圍盒樹度數(shù)，包圍盒樹度數(shù)和樹的深度成反比。度數(shù)越大，深度就會(huì)越小，則樹的遍歷時(shí)間就會(huì)越少，但每個(gè)節(jié)點(diǎn)在訪問(wèn)時(shí)需要進(jìn)行的計(jì)算就會(huì)增多。一般情況下，包圍盒樹度數(shù)并沒(méi)有明確規(guī)定，一般可以根據(jù)需要來(lái)選擇。

選擇完樹的度數(shù)、深度后，進(jìn)行包圍樹的方法構(gòu)建。包圍樹的構(gòu)建方法一般有三種：自底向上、自頂向下及漸進(jìn)插入法，其構(gòu)建過(guò)程如圖1所示。

圖1 包圍盒樹的構(gòu)建方法Figure 1 Bounding box tree construction method

1.2 構(gòu)建包圍盒

該過(guò)程可分為三步：

第一步，求出包圍盒映射在各個(gè)坐標(biāo)軸上的最大與最小值，據(jù)此求出軟組織模型外部的最大包圍盒，顯示構(gòu)建軟組織模型外部最大的包圍盒的情況；

第二步，根據(jù)均值法，將模型外部的最大包圍盒一分為二，在分割面處選擇兩個(gè)子節(jié)點(diǎn)，并根據(jù)新的子節(jié)點(diǎn)重建新的包圍盒；

第三步，重復(fù)第一和第二的步驟，直到包圍盒內(nèi)元素的大小在誤差范圍內(nèi)。

1.3 包圍盒樹的遍歷

經(jīng)典包圍盒樹的遍歷法一般包含兩種，分別為：廣度優(yōu)先搜索（BFS）與深度優(yōu)先搜索（DFS），它們的實(shí)現(xiàn)過(guò)程如圖2所示。BFS搜索的順序是按：根節(jié)點(diǎn)-所有子節(jié)點(diǎn)-所有葉節(jié)點(diǎn)來(lái)進(jìn)行的，而DFS的搜索是按：根節(jié)點(diǎn)-子節(jié)點(diǎn)-葉節(jié)點(diǎn)-子節(jié)點(diǎn)-葉節(jié)點(diǎn)-……。

圖2 包圍盒樹的搜索方式Figure 2 Bounding box tree search

利用上述三個(gè)步驟對(duì)A，B兩個(gè)碰撞模型可構(gòu)建出TreeA及TreeB兩個(gè)包圍盒樹，它們間的檢測(cè)過(guò)程又為如下二步，其具體流程如圖3：

第一，檢測(cè)兩個(gè)模型的根節(jié)點(diǎn)有無(wú)發(fā)生碰撞，只有根節(jié)點(diǎn)發(fā)生碰撞后才能再執(zhí)行下一步。

第二，執(zhí)行包圍盒樹的遍歷，這個(gè)遍歷過(guò)程從根節(jié)點(diǎn)到葉節(jié)點(diǎn)。直到全部葉節(jié)點(diǎn)均無(wú)檢測(cè)到碰撞，完成本次的碰撞檢測(cè)，得出兩模型沒(méi)有發(fā)生碰撞的結(jié)論。

由流程圖3可知，AABB包圍盒的碰撞檢測(cè)法采用多次檢測(cè)的方法，能夠較好地實(shí)時(shí)檢測(cè)軟組織模型與手術(shù)器械的碰撞。

圖3 包圍盒樹碰撞檢測(cè)的流程圖Figure 3 Bounding box tree collision detection flow chart

2 AABB碰撞檢測(cè)的改進(jìn)

上述AABB包圍盒的檢測(cè)法雖然過(guò)程簡(jiǎn)單、計(jì)算量小，能夠保證虛擬手術(shù)中碰撞檢測(cè)的實(shí)時(shí)性，但該方法使用規(guī)則的長(zhǎng)方體來(lái)代替無(wú)規(guī)則的軟組織模型接受碰撞，不能精確檢測(cè)手術(shù)器械與軟組織中細(xì)節(jié)部位發(fā)生碰撞。因此，檢測(cè)出來(lái)的結(jié)果存在明顯的誤差，導(dǎo)致了碰撞檢測(cè)的漏報(bào)和誤報(bào)。為了提高軟組織受到碰撞時(shí)反饋的精確性，本節(jié)提出三角形面片相交與AABB相結(jié)合的碰撞檢測(cè)方法對(duì)其進(jìn)行改進(jìn)。

三角網(wǎng)格面片間的檢測(cè)原理具體如下所述：

兩個(gè)模型中，兩個(gè)三角形網(wǎng)格面片具有的關(guān)系只有兩種可能：一種是相離，即這兩個(gè)三角形間沒(méi)有產(chǎn)生碰撞，如圖4（a）所示；一種是相交，即這兩個(gè)三角形面片間發(fā)生了碰撞，如圖4（b）。

圖4 兩個(gè)三角形面片之間的相互關(guān)系Figure 4 The relationship between two triangular patches

當(dāng)三角形面片發(fā)生相交時(shí)，相交線段可由L來(lái)表示[8]，即

其中

設(shè) I（x，y）是三角形 N1N2N3 里面的任何一點(diǎn)，它的表達(dá)式為：

公式中的 x≥0，y≤0，且 x+y≤ 1。求兩個(gè)三角形的相交處時(shí)，即可聯(lián)立公式（1）和公式（3）可得出如下公式：

即

上式中的t表示點(diǎn)N1到平面三角形的距離。將公式（5）的兩邊分別表示為矩陣的形式：

令 d0=M1-N1d1=N2-N1d2=N3-N1，則公式（6）可轉(zhuǎn)變?yōu)槿缦拢?/p>

且，由公式（8）所示：

可將公式（7）轉(zhuǎn)化為：

由公式（9）中的關(guān)系式可知：

（a）若求出的且，則兩個(gè)三角形相離且距離t相對(duì)于向量來(lái)說(shuō)是正方向。

（b）若求出的且，則兩個(gè)三角形相離且距離t相對(duì)于向量來(lái)說(shuō)是負(fù)方向。

（c）若求出的且或者且，則兩個(gè)三角形相交，這種情況下的t的正負(fù)方向與，的絕對(duì)值的大小密切相關(guān)。

由以上分析可以得出，三角面片相交的檢測(cè)方法雖然需要較大的計(jì)算量，但其對(duì)細(xì)節(jié)部分的處理相比AABB包圍盒碰撞檢測(cè)方法而言具有明顯的優(yōu)勢(shì)。將這種方法用在軟組織模型和手術(shù)器械相貼近的位置，就能夠?qū)χ付ㄐ巫儏^(qū)域的所有網(wǎng)格進(jìn)行劃分，并分別進(jìn)行檢測(cè)，從而使精確度大大提高。

三角形面片相交的檢測(cè)方法能夠提高結(jié)果的精確度，AABB包圍盒碰撞檢測(cè)方法又能保證檢測(cè)的實(shí)時(shí)性，因此，本設(shè)計(jì)中將這兩種方法相結(jié)合，由AABB包圍盒碰撞檢測(cè)方法進(jìn)行內(nèi)部區(qū)域處理，再用三角形面片相交的檢測(cè)方法處理邊緣部分，從而使得檢測(cè)過(guò)程中保證實(shí)時(shí)性的同時(shí)有效提高了碰撞檢測(cè)的精確度。

3 實(shí)驗(yàn)結(jié)果及分析

為了更好的進(jìn)行實(shí)驗(yàn)結(jié)果的比較和性能的分析，在本設(shè)計(jì)的實(shí)驗(yàn)中，假設(shè)兩種碰撞檢測(cè)方法運(yùn)用在同一個(gè)軟組織模型的相同位置且它們?cè)谌我鈺r(shí)刻的受力情況都相同。在這種前提下，比較AABB碰撞檢測(cè)改進(jìn)前后兩種方法所檢測(cè)到的形變網(wǎng)格的個(gè)數(shù)。實(shí)驗(yàn)結(jié)果如圖5所示。

實(shí)驗(yàn)結(jié)果表明，由前分析提出的混合方法的碰撞檢測(cè)方法的檢測(cè)效果較AABB包圍盒碰撞檢測(cè)方法更精確。由折線圖可得出，在力為0.1N的情況下，兩種檢測(cè)方法的檢測(cè)效果并沒(méi)有很大的差別，但隨著外力的不斷增大，改進(jìn)后的方法檢測(cè)到軟組織的形變網(wǎng)格數(shù)較原方法檢測(cè)到的形變網(wǎng)格面片數(shù)不斷的遞增，這與受碰撞區(qū)域的外圍輪廓線長(zhǎng)度有一定的關(guān)系。此后，由于構(gòu)成子空間和全空間邊界的網(wǎng)格數(shù)在增加，所以改進(jìn)后的碰撞檢測(cè)方法的優(yōu)勢(shì)在不斷的加強(qiáng)，使檢測(cè)效果更加準(zhǔn)確、更為合理。

圖5 AABB碰撞檢測(cè)和混合的碰撞檢測(cè)方法檢測(cè)效果比較Figure 5 Comparison of AABB collision detection and mixed collision detection methods

4 結(jié)論

為了降低漏報(bào)和誤報(bào)發(fā)生的概率，以減小碰撞檢測(cè)的誤差，在不引入過(guò)大計(jì)算量的前提下，本設(shè)計(jì)提出了三角面片相交的碰撞檢測(cè)方法，并與AABB包圍盒相結(jié)合實(shí)現(xiàn)了碰撞檢測(cè)方法的改進(jìn)。根據(jù)三角形面片相交的檢測(cè)方法能夠提高結(jié)果的精確度，AABB包圍盒碰撞檢測(cè)方法又能保證檢測(cè)的實(shí)時(shí)性，因此設(shè)計(jì)由AABB包圍盒碰撞檢測(cè)方法進(jìn)行內(nèi)部區(qū)域處理，再用三角形面片相交的檢測(cè)方法處理邊緣部分。實(shí)驗(yàn)結(jié)果表明，AABB包圍盒碰撞檢測(cè)方法改進(jìn)后較改進(jìn)前更精確。又因構(gòu)成子空間和全空間邊界的網(wǎng)格數(shù)在增加，所以改進(jìn)后的碰撞檢測(cè)法的檢測(cè)效果更加準(zhǔn)確、更為合理，為虛擬手術(shù)的應(yīng)用提供廣闊的前景。