基于改進軸向包圍盒算法的軟組織形變仿真

陳冬英

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

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

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

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

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

1 軟組織形變的AABB碰撞檢測法

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

1.1 AABB的建立

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

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

圖1 包圍盒樹的構建方法Figure 1 Bounding box tree construction method

1.2 構建包圍盒

該過程可分為三步：

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

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

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

1.3 包圍盒樹的遍歷

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

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

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

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

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

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

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

2 AABB碰撞檢測的改進

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

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

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

圖4 兩個三角形面片之間的相互關系Figure 4 The relationship between two triangular patches

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

其中

設 I（x，y）是三角形 N1N2N3 里面的任何一點，它的表達式為：

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

即

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

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

且，由公式（8）所示：

可將公式（7）轉化為：

由公式（9）中的關系式可知：

（a）若求出的且，則兩個三角形相離且距離t相對于向量來說是正方向。

（b）若求出的且，則兩個三角形相離且距離t相對于向量來說是負方向。

（c）若求出的且或者且，則兩個三角形相交，這種情況下的t的正負方向與，的絕對值的大小密切相關。

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

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

3 實驗結果及分析

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

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

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

4 結論

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