吳德道，劉小平

(1. 南昌大學(xué)信息工程學(xué)院，江西 南昌 330031；2. 景德鎮(zhèn)陶瓷大學(xué)，江西 景德鎮(zhèn) 333000；3. 卡爾頓大學(xué)系統(tǒng)與計(jì)算機(jī)工程系，渥太華 加拿大 K1S 5B6)

1 引言

在虛擬手術(shù)仿真系統(tǒng)中建立自然、準(zhǔn)確的軟組織切口模型是該領(lǐng)域研究的重點(diǎn)之一[1]。主要體現(xiàn)在虛擬手術(shù)切口生成后切口面幾何和拓?fù)浣Y(jié)構(gòu)發(fā)生了明顯的變化，特別是網(wǎng)格化方法中需要重網(wǎng)格化，這將給模型的仿真帶來很大的問題[2]，[3]。而經(jīng)過一段時(shí)間的發(fā)展，研究者們提出許多模擬軟組織切口模型[4]。根據(jù)建模過程中是否需要對虛擬器官和組織對象進(jìn)行細(xì)分和預(yù)處理，可以將軟組織切口模型分為基于網(wǎng)格和無網(wǎng)格的兩種建模架構(gòu)[5]。虛擬手術(shù)切口模型的仿真涉及到使用網(wǎng)格切割技術(shù)修改多邊形或三維網(wǎng)格。網(wǎng)格切割是網(wǎng)格編輯研究的一個(gè)重要組成部分，包括重映射、變形、合并、簡化和平滑操作。目前，關(guān)于網(wǎng)格切割的研究大多集中在虛擬手術(shù)和醫(yī)學(xué)仿真領(lǐng)域，其中較為常見的是三維掃描和三維網(wǎng)格表示。而大多數(shù)醫(yī)學(xué)領(lǐng)域以外的軟件只處理多邊形網(wǎng)格的應(yīng)用，使得該技術(shù)在網(wǎng)格表面操作上更加成熟。曲面網(wǎng)格的使用不僅提高了基于多邊形的渲染引擎的可用性和性能，而且還是實(shí)時(shí)應(yīng)用的關(guān)鍵因素。

早在1997年，Nielsen等首次提出基于網(wǎng)格的單元去除法[6]。為提高切口的仿真效果，Nielsen等提出改進(jìn)模型，如邊緣折疊法、頂點(diǎn)復(fù)制分裂法、曲面約束法等。這種切口模型只處理虛擬物體的表面網(wǎng)格，使用較少的點(diǎn)和面來表示物體的表面形狀，但不能表達(dá)物體內(nèi)部的信息。為更好地模擬和顯示物體被切割后的各種內(nèi)部變化，Bielser等人提出一種基于體積模型[7]的體積元細(xì)分法。之后，相繼出現(xiàn)虛擬節(jié)點(diǎn)法、部分剖分法和立方體單元?jiǎng)澐址ǖ雀倪M(jìn)模型。所有上述模型需要將預(yù)處理網(wǎng)格細(xì)分[8，9]，在切割過程中進(jìn)行網(wǎng)格更新和重組，成本很多。2009年，丹尼斯等人結(jié)合對象空間色散的無網(wǎng)格方法和基于網(wǎng)格表面重建技術(shù)，并成功地應(yīng)用在子宮鏡檢查和切削仿真。但該方法數(shù)據(jù)結(jié)構(gòu)復(fù)雜，算法復(fù)雜度高，計(jì)算效率低。而目前混合模型最大的困難是如何管理好兩個(gè)不同的建模系統(tǒng)[10]。

根據(jù)Bruyns等人[11]的研究，他們把網(wǎng)格切割技術(shù)分為重網(wǎng)格化、切割路徑的定義和新原語的創(chuàng)建。前兩種方法是在間隔點(diǎn)之間或在選定點(diǎn)之間構(gòu)造一個(gè)連續(xù)平面，而它們的區(qū)別是如何設(shè)置切割路徑。模板與網(wǎng)格基元的碰撞檢測是第三種方法的要求。此外，Bruyns等還描述了漸進(jìn)切割方案。為實(shí)現(xiàn)刀具的原始碰撞，在刀具連續(xù)移動位置之間構(gòu)造一個(gè)掃描面。對原語測試曲面的掃描生成邊和面的交點(diǎn)，其中新節(jié)點(diǎn)連接到新創(chuàng)建的邊和面，然后替換原語，該方案適合多層目標(biāo)的碰撞檢測。而對于非漸進(jìn)式切割方法，存儲的信息大多是冗余的，而重網(wǎng)格化方案只處理邊-邊和邊-面相交的情況。此外，切割暴露了表面網(wǎng)格的內(nèi)部，因此該方法只適用于多層網(wǎng)格。

Zhang等人[12]提出一種表面網(wǎng)格模型的漸進(jìn)式切割技術(shù)，該技術(shù)將網(wǎng)格元素細(xì)分，并沿選擇的切割路徑構(gòu)造內(nèi)部結(jié)構(gòu)。在切割線與三角面邊緣相交的地方創(chuàng)建兩個(gè)新節(jié)點(diǎn)。這兩個(gè)節(jié)點(diǎn)初始是一樣的，但隨著切割完成而分離。這種分離留下一個(gè)切口槽，其深度由刀具尖端的切割深度來定義。在此基礎(chǔ)上，他們還提出一種漸進(jìn)式切割算法，通過執(zhí)行臨時(shí)細(xì)分和動態(tài)構(gòu)造切口槽來跟蹤刀具在三角形中的運(yùn)動。與前一種方案一樣，該方法沒有一個(gè)完整的網(wǎng)格重映射方案，并且沒有網(wǎng)格表示的定義，這使得該方法難以重現(xiàn)。

Van der Stappen和Nienhuys[13]定義一種切割技術(shù)，通過限制原始元素不具有短邊或大角度使得生成的新元素較少，從而產(chǎn)生形狀良好的網(wǎng)格結(jié)構(gòu)。切割工具的任意一次移動都會移動一個(gè)額外的活動節(jié)點(diǎn)。在每次移動之后，對應(yīng)三角形將被重新映射到本地。通過這種方式，刪除切割工具前面的節(jié)點(diǎn)，然后將其插入到工具之后。該方法的特點(diǎn)是切割前后目標(biāo)網(wǎng)格的分辨率保持不變，但切割路徑的精度不能得到提高，而這是由初始網(wǎng)格的分辨率決定的[14]。

Lim等人[15]提出一種基于節(jié)點(diǎn)捕獲的漸進(jìn)式切割算法。第一次碰撞接觸時(shí)，最近的節(jié)點(diǎn)被拉到目標(biāo)網(wǎng)格和工具之間的初始接觸位置。在切割過程中，切割路徑上的每個(gè)節(jié)點(diǎn)被分成兩個(gè)方向相反、垂直于切割線的節(jié)點(diǎn)。最后，設(shè)置一個(gè)切割槽來創(chuàng)建體積切割的錯(cuò)覺。為解決切割路徑的切割分辨率依賴于周圍網(wǎng)格的細(xì)分問題，他們還提出一種局部細(xì)分算法[16]。這種方法允許更準(zhǔn)確地表示切割路徑，但內(nèi)存成本高且性能降低。

針對上述建立切口模型方法的優(yōu)缺點(diǎn)，提出一種實(shí)時(shí)模擬切口模型的方法。該方法直接與表面網(wǎng)格交互，并在程序運(yùn)行時(shí)生成新的幾何拓?fù)?，為后續(xù)切口模型的高真實(shí)感渲染提供一個(gè)切口內(nèi)腔結(jié)構(gòu)。本文其余部分組織如下：第2節(jié)中給出建模方案中使用的模擬方法和相應(yīng)算法。第3節(jié)通過實(shí)驗(yàn)進(jìn)一步證實(shí)仿真方法的有效性。最后，在第4節(jié)對本文的研究成果進(jìn)行總結(jié)，并對未來的研究提出建議。

2 建模方法

通常當(dāng)一個(gè)鋒利物體穿過真實(shí)軟組織表面撕裂表皮使皮下組織可見時(shí)，就在軟組織表面留下一個(gè)切口。利用網(wǎng)格編輯技術(shù)對切割影響的網(wǎng)格區(qū)域進(jìn)行局部修改，從而可在虛擬環(huán)境中重現(xiàn)這一現(xiàn)象。本節(jié)中，將研究與切口模擬相關(guān)的算法和技術(shù)，包括將切割線與目標(biāo)網(wǎng)格融合并將切割線擴(kuò)展成切口以及生成切割槽。

2.1 融合切割線

在目標(biāo)網(wǎng)格中插入一條切割線段作為模擬切割邊界，會改變原始網(wǎng)格的許多屬性并破壞原始網(wǎng)格的完整性。因此，為避免這一問題，在插入新的切割線之前，需要對切割線周圍的局部幾何拓?fù)溥M(jìn)行細(xì)分。圖1描繪出切割線與目標(biāo)網(wǎng)格的融合。對于每段切割線段，端點(diǎn)可以與三角形網(wǎng)格的節(jié)點(diǎn)重合，也可以是它的一條邊，或者兩者都在三角形網(wǎng)格內(nèi)等。

圖1 插入的切割線融合到目標(biāo)網(wǎng)格中

按照切割線與目標(biāo)網(wǎng)格共點(diǎn)情況劃分為三類：第一類是不共點(diǎn)情況，切割線端點(diǎn)與網(wǎng)格頂點(diǎn)沒有重合也是最常出現(xiàn)的情況如圖2上所示。第二類是共點(diǎn)情況，切割線端點(diǎn)與網(wǎng)格面頂點(diǎn)重合，如圖2下所示。第三類是比較特殊的情況，整個(gè)切割線包含在一個(gè)三角網(wǎng)格內(nèi)，由于切割線太短，這種情況的切割沒有任何實(shí)際意義，因此在程序中忽略處理。切割線段p0p1與三角網(wǎng)格f之間的每種位置關(guān)系需要不同的方式將其融合到f中。根據(jù)剖分線的定義和網(wǎng)格的屬性對網(wǎng)格表面進(jìn)行細(xì)分。新插入的端點(diǎn)為p0和p1的邊ec被添加到邊ECs的有序集中。圖2給出各位置關(guān)系，其中切割線段用虛線表示，網(wǎng)格細(xì)分用點(diǎn)劃線表示。具體操作是：

圖2 切割線與三角網(wǎng)格的位置關(guān)系

第一類，如圖2上，從左至右分別對應(yīng)以下3種：

1)p0在網(wǎng)格內(nèi)p1在邊上，這種位置關(guān)系常發(fā)生在切割線的初始位置。三角網(wǎng)格f在p0處用3-split算法細(xì)分，在p1處執(zhí)行2-split操作。

2)p0和p1均在邊上，這種位置關(guān)系最常見。切割線段p0p1將網(wǎng)格f分成一個(gè)三角形和一個(gè)四邊形，而為保持三角網(wǎng)格關(guān)系，首先在p1處分出兩個(gè)三角網(wǎng)格(點(diǎn)劃線)，然后在p0處分割一個(gè)新的三角子網(wǎng)格。通過比較p0所在的邊及其邊引用，可以確定p0與兩個(gè)三角子網(wǎng)格中的哪一個(gè)相關(guān)聯(lián)，均采用2-split操作。

3)p0在邊上p1在網(wǎng)格內(nèi)，這種位置關(guān)系常發(fā)生在切割線的末端。將f在p1處按3-split操作進(jìn)行細(xì)分，然后確定p0在哪個(gè)子網(wǎng)格上，在p0處繼續(xù)進(jìn)行2-split操作。

第二類，如圖2下，從左至右分別對應(yīng)以下3種：

1)p0(p1)和網(wǎng)格共點(diǎn)p1(p0)在網(wǎng)格內(nèi)，p1(p0)處將f細(xì)分為三個(gè)子網(wǎng)格并被共享。3-split操作在f內(nèi)部創(chuàng)建三個(gè)新的面和邊，它們都與p1(p0)有關(guān)。其中一條新邊與ec重合，并被添加到ECs上。

2)p0(p1)和網(wǎng)格共點(diǎn)p1(p0)在邊上，切割線段將f細(xì)分為兩個(gè)新的三角網(wǎng)格。使用2-split算法將f在p1(p0)處分割成兩個(gè)子網(wǎng)格，并更新f的直接鄰域。

3)p0和p1均與網(wǎng)格共點(diǎn)，即切割線段p0p1與網(wǎng)格共邊，直接添加到ECs中。

算法1結(jié)合圖3左側(cè)詳細(xì)描述了2-split操作。與圖3右側(cè)相似的組合可以推導(dǎo)出3-split操作。

圖3 面f分別在2-split (左)和3-split操作(右)時(shí)的拓?fù)?/p>

算法1 2-split

輸入： 面f，點(diǎn)p和點(diǎn)p所在的邊es

輸出：分割邊ec，將f從p細(xì)分到它的對面節(jié)點(diǎn)n1

1)獲取節(jié)點(diǎn){n0，n1，n2}，頂點(diǎn){v1，v2，v3}，面f上的邊{e0，e1，e2}

2)在p點(diǎn)處創(chuàng)建節(jié)點(diǎn)nm，頂點(diǎn)vm

3)在nm和n1之間生成切割邊ec

4)分別在n0和nm，nm和n2之間生成邊ex0，ex1

5)分別在nm、n0和n1，nm、n1和n2之間生成面fc0，fc1

6)設(shè)置邊ec的鄰接面fc0，fc1

7)分別設(shè)置邊ex0，ex1的鄰接面fc0，fc1

8)設(shè)置面fc0的鄰接邊ex0，e0，ec

9)設(shè)置面fc1的鄰接邊ec，e1，ex1

10)分別用fc0，fc1取代邊e0的鄰接面f和邊e1的鄰接面f

11)從網(wǎng)格中刪除面f，邊es

12)返回分裂邊ec

2.2 仿真參數(shù)可調(diào)的切口邊界和切割槽

該階段由兩部分組成：切割線擴(kuò)展和切割槽生成。輸入為前一階段創(chuàng)建的一組有序切割線線段集合，分離切割邊的局部幾何形狀，模擬切口。此操作在目標(biāo)網(wǎng)格中留下一個(gè)凹槽，然后融合這個(gè)位于當(dāng)前網(wǎng)格面以下某個(gè)深度的新拓?fù)洹D4描繪出切割線的分離幾何形狀及其內(nèi)部結(jié)構(gòu)。

圖4 復(fù)制相應(yīng)的頂點(diǎn)并生成切口邊界與其內(nèi)腔結(jié)構(gòu)

根據(jù)產(chǎn)生切口的要求，切割線上的節(jié)點(diǎn)和頂點(diǎn)要相互復(fù)制，分別移動。將這些元素與邊緣連接在切口周圍形成一個(gè)邊界(圖4中的粗實(shí)線)，該邊界應(yīng)與切割線兩側(cè)的拓?fù)浣Y(jié)構(gòu)融合。初始切割線上的節(jié)點(diǎn)、頂點(diǎn)和邊不再引用，它們在之后被刪除。根據(jù)Lim等人[16]測量的切口張開距離(IOD)與切口長度L、深度d的關(guān)系，可以得到一般公式

IOD(L，d)=(0.0111+0.0002(d-0.1/0.02))ln(L)

+0.0415+0.0015(d-0.1/0.02)

(1)

通過可調(diào)參數(shù)拋物線來調(diào)節(jié)切割線上任意點(diǎn)的切割位移計(jì)算IOD。這條拋物線確保IOD在中心近似為最大值，在開始和結(jié)束為零，在中間光滑。由此得到計(jì)算方程

IODpi=mIOD(L，d)

(2)

式2中，m可由拋物線方程m=ax2+bx+c確定，其中，a、b、c為可調(diào)系數(shù)，x=i/|Ec|，i=0，…，|Ec|，|Ec|為切割線邊集合Ec的基數(shù)。

定義切割線邊界的新幾何點(diǎn)用于創(chuàng)建網(wǎng)格拓?fù)?，并將切割線劃分為兩個(gè)相似的部分。算法2詳細(xì)描述了這一過程。第一條邊和最后一條邊的處理方式類似，分別對位于p0和p1中的節(jié)點(diǎn)和頂點(diǎn)進(jìn)行重用。切割深度d的計(jì)算公式為

d=max(0.1，min(1.0，l/5))

(3)

算法2 構(gòu)建切割邊界的幾何拓?fù)?/p>

輸入： 有序的切割邊集Ec

While(對每一條邊ec∈Ec)do

1)獲取與邊ec對應(yīng)的端點(diǎn)

2)在垂直切割線方向上計(jì)算vi ± IODpi/2，得到兩條邊界線的新端點(diǎn)

3)將這4個(gè)端點(diǎn)賦值給拓?fù)浣Y(jié)構(gòu)中的節(jié)點(diǎn)

4)生成對應(yīng)4個(gè)頂點(diǎn)

5)由生成邊e+

6)由生成邊e-

7)分別將添加到集合N+，添加到集合N-

8)分別將添加到集合V+，添加到集合V-

9)分別將e+和e-添加到集合E+和E-

10)分別將邊ec的面f0和f1添加到集合F+和F-

對于給定的切割邊ec，計(jì)算p0i和p1i在切割槽中的位置如下

(4)

(5)

通過算法3，創(chuàng)建切割槽結(jié)構(gòu)并與模型表面網(wǎng)格融合。

算法3 模擬切口內(nèi)腔的幾何拓?fù)?/p>

輸入： 切割邊集Ec、E+、E-；節(jié)點(diǎn)集N+，NI，N-，內(nèi)腔頂點(diǎn)集W+、WI、 W-

While(對每一條邊ec ∈Ec)do

1)獲取圖5中所示節(jié)點(diǎn)和頂點(diǎn)

2)兩點(diǎn)生成邊：-->ei+；-->eii；-->ei-；-->e0+； -->e0-； -->e1+； -->e1-

3)3個(gè)節(jié)點(diǎn)和對應(yīng)3個(gè)頂點(diǎn)生成面：-->fi+0；-->fi+1； n0i，n1i，n0-，w0i，w1i，w0->-->fi-0；-->fi-1；

4)設(shè)置邊面關(guān)聯(lián)：-->fi+0； -->fi-1

5)注冊邊面關(guān)聯(lián)：； ； ；

6)注冊相交邊面關(guān)聯(lián)：； ； ；

7)注冊內(nèi)腔面中邊面關(guān)聯(lián)：； ； ；

圖5 切口內(nèi)腔的網(wǎng)格元素

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)環(huán)境配置為便攜式計(jì)算機(jī)，CPU為Intel Core I5 5200，內(nèi)存為4GB，顯卡為AMD Radeon R5 M320。仿真軟件采用VC++的開發(fā)，圖形渲染方面使用OpenGL 圖形庫，材質(zhì)語言為CG。實(shí)驗(yàn)案例是通過三維掃描重建真實(shí)肝臟的數(shù)字模型。

3.1 實(shí)驗(yàn)仿真結(jié)果分析

在肝臟三維數(shù)字模型中，整個(gè)肝臟表面由3968個(gè)三角網(wǎng)格面包裹。圖6為三角形網(wǎng)格面相互銜接形成的三維網(wǎng)格模型，以及切口生成后目標(biāo)網(wǎng)格上形成的拓?fù)浣Y(jié)構(gòu)，著色模型以及切口部分放大后內(nèi)腔拓?fù)浣Y(jié)構(gòu)。在圖6中，切割切口完全融入到目標(biāo)網(wǎng)格中并生成具有一定深度的內(nèi)腔拓?fù)?。切口平滑自然，沒有破壞目標(biāo)網(wǎng)格的完整性。

圖6 數(shù)字肝臟原始網(wǎng)格模型以及生成切口后的網(wǎng)格拓?fù)渥ⅲ喊醋陨隙?，從左到右順序，分別是原始網(wǎng)格模型、切口模型、著色后切口模型以及局部放大切口模型。

圖7中可從多個(gè)角度觀察切口的視覺層次和切口的真實(shí)深度拓?fù)?。最終模擬的切口結(jié)構(gòu)過渡自然，并可以根據(jù)目標(biāo)場景修改切口和腔體實(shí)際對應(yīng)紋理，易于實(shí)現(xiàn)。

圖7 著色渲染后仿真肝臟模型和生成切口后多角度演示的模型

3.2 對比分析

與真實(shí)肝臟軟組織的切口對比如圖8所示，其中左圖是固定切割裝置旁邊是切割產(chǎn)生切口的肝臟軟組織[17]，右圖是采用本文方法對虛擬肝臟切口的渲染。通過對比，可以注意到切口幾何外形基本相似，所不同的是切口周圍血液顏色的渲染，左圖偏向切口外形實(shí)驗(yàn)，右圖兼顧切口外形和周圍表皮顏色的渲染。

圖8 與真實(shí)肝臟切口的對比注：左圖為真實(shí)肝臟切口，右圖為仿真切口。

圖9中，左上是DFFD方法[18]模擬的手術(shù)切口，右上采用的是基于FEM的DFFD方法[19]，中間是本文方法，下圖是本文方法切口局部放大。前兩種方法沒有構(gòu)造切口內(nèi)腔結(jié)構(gòu)缺乏立體逼真感，手術(shù)切口與表皮之間缺乏過渡元素，不利于后期切口的進(jìn)一步渲染。

圖9 不同仿真方法在相同部位生成的切口

3.3 效率分析

通常12幀/秒的幀速率是人眼實(shí)時(shí)交互所能達(dá)到的最低幀速率。在數(shù)字模擬虛擬肝臟模型的三角網(wǎng)格數(shù)為3968的情況下，本文模擬手術(shù)切口(600PP)的方法獲得的幀速率約為230幀/秒，其它渲染過程所對應(yīng)幀速率如表1所示。模擬切口在世界坐標(biāo)(0.02～0.15)下的總時(shí)間為6～10ms，保證了后繼操作的實(shí)時(shí)性。

表1 虛擬肝臟模型渲染過程及手術(shù)切口所對應(yīng)的幀速率

4 結(jié)束語

本文提出一種虛擬手術(shù)切口模型的仿真方法，簡化了切割線與目標(biāo)網(wǎng)格面的對應(yīng)關(guān)系，利用可調(diào)參數(shù)曲線模擬切口邊界。通過減少對切割線周圍網(wǎng)格面的修改來保證網(wǎng)格結(jié)構(gòu)的完整性和穩(wěn)定性并以虛擬肝臟為實(shí)驗(yàn)對象，實(shí)現(xiàn)了對肝臟切口的仿真。該方法不僅適合虛擬手術(shù)切口仿真，而且創(chuàng)建了具有立體感的內(nèi)腔結(jié)構(gòu)，可實(shí)現(xiàn)高真實(shí)感虛擬手術(shù)切口的實(shí)時(shí)渲染。本文主要貢獻(xiàn)是詳細(xì)描述了模擬網(wǎng)格切口所需的技術(shù)，并保持原始網(wǎng)格拓?fù)浣Y(jié)構(gòu)和參數(shù)的完整性。仿真程序能夠通過基本的重網(wǎng)格化操作處理所有的切割線與三角形網(wǎng)格之間的關(guān)系，并為模擬目標(biāo)網(wǎng)格上的切割模型提供完整的數(shù)據(jù)結(jié)構(gòu)和算法。優(yōu)點(diǎn)是對網(wǎng)格拓?fù)涞母蓴_最小，因?yàn)橹恍薷呐c切口邊界有關(guān)的網(wǎng)格面。本文采用的是基本操作和數(shù)據(jù)，能夠支持不同類型的虛擬手術(shù)切口。在判斷兩個(gè)空間點(diǎn)是否重疊時(shí)，網(wǎng)格精細(xì)度問題會導(dǎo)致拓?fù)渚W(wǎng)格失效。在確定網(wǎng)格節(jié)點(diǎn)和頂點(diǎn)時(shí)，通過使用閾值來衡量兩點(diǎn)之間的距離是否小到可視為重疊的程度。因此，閾值需根據(jù)網(wǎng)格表面節(jié)點(diǎn)密度等因素進(jìn)行調(diào)整。最后，無需執(zhí)行額外的網(wǎng)格細(xì)化，只對與切割線相關(guān)的面進(jìn)行重映射。在未來，解決方案可以聚焦在新創(chuàng)建切口周圍的網(wǎng)格變形上。