動(dòng)脈血管 STL模型邊界識(shí)別及其三角剖分

付文宇,喬愛(ài)科,付鵬斌

(1.北京工業(yè)大學(xué)機(jī)械工程與應(yīng)用電子技術(shù)學(xué)院,北京 100124;2.北京工業(yè)大學(xué)生命科學(xué)與生物工程學(xué)院,北京 100124;3.北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,北京 100124)

在對(duì)人體動(dòng)脈血管進(jìn)行流體力學(xué)分析時(shí),為了得到準(zhǔn)確的結(jié)果,一般需要進(jìn)行計(jì)算流體動(dòng)力學(xué)分析(computational fluid dynamics,CFD).血液流動(dòng)仿真可以給醫(yī)生提供許多人體數(shù)據(jù)信息,幫助他們進(jìn)行手術(shù)規(guī)劃[1].要進(jìn)行計(jì)算流體動(dòng)力學(xué)分析,需對(duì)模型進(jìn)行網(wǎng)格劃分.和真實(shí)血管幾何形狀較為接近的動(dòng)脈血管模型的構(gòu)建方法為:根據(jù)計(jì)算機(jī)斷層掃描技術(shù)(CT)或核磁共振成像(MRI)等技術(shù)獲得血管二維斷層圖像,然后采用表面繪制(surface rendering)或者體繪制(volume rendering)技術(shù)獲得相應(yīng)模型.通過(guò)表面繪制方法,可以獲得以 STL文件表示的動(dòng)脈血管表面模型.有時(shí) STL文件表示的表面模型并不是封閉的,而進(jìn)行體網(wǎng)格劃分的前提是其表面模型必須封閉.因此,必須找到合適的方法將開(kāi)口邊界區(qū)域封閉起來(lái).一些網(wǎng)格劃分軟件有一定的 STL文件編輯功能.比如 NETGEN[2]具有一個(gè) STLDoctor工具,利用它可以對(duì) STL文件表示的模型進(jìn)行一定的編輯操作,如通過(guò)鼠標(biāo)雙擊模型上某一個(gè)三角面片,就可以獲得三角面片頂點(diǎn)坐標(biāo),這樣通過(guò)逐個(gè)選擇處于邊界的三角面片就可以獲得相應(yīng)邊界點(diǎn)坐標(biāo),但這種方法復(fù)雜且易出錯(cuò).若能將 STL文件表示的表面模型的點(diǎn)、線、三角面片之間的關(guān)系表示出來(lái)并利用處于開(kāi)口邊界的邊只屬于一個(gè)三角面片這一特性,就可以將開(kāi)口邊界識(shí)別出來(lái).張翔等[3]對(duì) STL文件的拓?fù)渲亟ǚ椒ㄟM(jìn)行了研究;候?qū)毭鞯萚4]對(duì) STL文件拓?fù)渲亟捌淙毕菪迯?fù)進(jìn)行了研究.但他們的研究是從逆向工程的角度出發(fā),面向快速成型制造,并不關(guān)心開(kāi)口邊界識(shí)別及其三角剖分問(wèn)題.本文對(duì)具有開(kāi)口邊界的 STL文件的拓?fù)渲亟ā⑦吔缱R(shí)別以及使用 Delaunay三角剖分封閉識(shí)別的邊界問(wèn)題進(jìn)行研究,并編程實(shí)現(xiàn)此功能.

1 拓?fù)浣Y(jié)構(gòu)重建

要對(duì) STL文件進(jìn)行拓?fù)渲亟?需知道 STL文件數(shù)據(jù)結(jié)構(gòu),其詳細(xì)信息參見(jiàn)文獻(xiàn)[5-7].由于 STL文件只給出實(shí)體表面三角面片的點(diǎn)坐標(biāo)及其法線向量,因此任何一個(gè)可以完整表示多面體的數(shù)據(jù)結(jié)構(gòu)均可以表示 STL文件的拓?fù)潢P(guān)系.例如,半邊結(jié)構(gòu)(half-edge structure)[8]、翼邊結(jié)構(gòu)(wing-edge structure)[9]等.如果使用半邊結(jié)構(gòu)重建 STL模型的拓?fù)浣Y(jié)構(gòu)并應(yīng)用一個(gè)只有半邊沒(méi)有伙伴半邊的邊查找過(guò)程,就能將STL模型開(kāi)口邊界識(shí)別出來(lái),因此,本文選擇半邊結(jié)構(gòu)作為拓?fù)渲亟ǖ臄?shù)據(jù)結(jié)構(gòu).

本文中使用的半邊結(jié)構(gòu)同文獻(xiàn)[8]中的略有不同,由于在每個(gè) STL文件表示的三角面片中均沒(méi)有內(nèi)部孔,為了使數(shù)據(jù)結(jié)構(gòu)更為緊湊,不用圈(loop)節(jié)點(diǎn),而只使用以下 5個(gè)節(jié)點(diǎn):體(solid)、面(face)、邊(edge)、半邊(half-edge)、頂點(diǎn)(vertex).體節(jié)點(diǎn)形成了 1個(gè)半邊結(jié)構(gòu)實(shí)例的根節(jié)點(diǎn).體節(jié)點(diǎn)中包含指向面、邊、頂點(diǎn)的雙向鏈表的指針,通過(guò)它可以訪問(wèn)相應(yīng)的面、邊、頂點(diǎn).面節(jié)點(diǎn)表示多面體中的 1個(gè)平面,其中包含指向面所屬體的指針以及面鏈表中前、后面的指針.半邊表示 1條有向線段,3條首尾相接的半邊構(gòu)成 1個(gè)三角面片,2個(gè)相鄰的三角面片一定存在 1對(duì)重合的、方向相反的半邊,稱為伙伴半邊.2個(gè)伙伴半邊一起構(gòu)成 1條整邊(父邊),如圖 1所示.每個(gè)半邊結(jié)構(gòu)中都包括 1個(gè)指向它所屬父邊的指針、1個(gè)指向半邊開(kāi)始頂點(diǎn)的指針以及指向相連接的前、后半邊的指針.邊節(jié)點(diǎn)包含屬于它的左右 2個(gè)半邊的指針以及邊鏈表中前、后邊的指針.頂點(diǎn)節(jié)點(diǎn)包含 1個(gè)指向它所屬半邊的指針、頂點(diǎn)的坐標(biāo)值以及頂點(diǎn)鏈表中前、后頂點(diǎn)的指針.

拓?fù)浣Y(jié)構(gòu)重建過(guò)程是在一個(gè) while(C++)循環(huán)過(guò)程中完成的,在 while的一次循環(huán)過(guò)程中,讀入 STL文件的 1個(gè)三角面片數(shù)據(jù),即三角面片 3個(gè)頂點(diǎn)坐標(biāo).先檢查三角面片的 3個(gè)頂點(diǎn)在已建立的模型中是否存在,如果存在,就不建立新的頂點(diǎn)節(jié)點(diǎn);否則,建立新的頂點(diǎn)節(jié)點(diǎn).頂點(diǎn)的查找過(guò)程借助一個(gè)動(dòng)態(tài)平衡二叉樹(shù)(AVL TREE)來(lái)實(shí)現(xiàn),這樣做的原因是表征血管的 STL文件包含的數(shù)據(jù)量非常大,一個(gè)較小文件也會(huì)包含幾萬(wàn)個(gè)頂點(diǎn),具體實(shí)現(xiàn)方法見(jiàn)文獻(xiàn)[10].頂點(diǎn)節(jié)點(diǎn)處理完后,建立該三角面片的 1個(gè)新的面節(jié)點(diǎn)和3個(gè)新的半邊節(jié)點(diǎn),并且建立這 3個(gè)半邊和頂點(diǎn)、三角面片的對(duì)應(yīng)關(guān)系.由于 STL文件中每個(gè)三角面片都會(huì)對(duì)應(yīng) 1個(gè)且是唯一 1個(gè)面節(jié)點(diǎn)及 3個(gè)半邊節(jié)點(diǎn),因此在已建立的模型中肯定不會(huì)出現(xiàn)表示現(xiàn)在這個(gè)三角面片及其 3個(gè)半邊的節(jié)點(diǎn),只需生成新的節(jié)點(diǎn)即可.然后建立新生成的 3個(gè)半邊和父邊的關(guān)系,這里要分 3種情況分別進(jìn)行處理:

1)如果某半邊的起點(diǎn)或終點(diǎn)是新建頂點(diǎn),則該半邊所屬的邊是不存在的,這時(shí)直接在已建立的模型中建立 1個(gè)新的邊節(jié)點(diǎn),同時(shí)將該半邊設(shè)置為新邊的 1個(gè)半邊;

2)通過(guò)對(duì)動(dòng)態(tài) AVL樹(shù)進(jìn)行查找,某半邊的起點(diǎn)和終點(diǎn)在已建立模型中都存在,則進(jìn)一步查找這 2個(gè)點(diǎn)是否曾組成 1個(gè)半邊,如果有,則說(shuō)明這個(gè)半邊的伙伴半邊一定存在,此半邊的父邊節(jié)點(diǎn)在模型中已經(jīng)存在.這時(shí)將查找到的半邊設(shè)置為伙伴半邊,同時(shí)設(shè)置此半邊(新生成的半邊)與父邊的關(guān)系;

3)通過(guò)對(duì)動(dòng)態(tài) AVL樹(shù)進(jìn)行查找,某半邊的起點(diǎn)和終點(diǎn)在已建立模型中都存在,則進(jìn)一步查找這 2個(gè)點(diǎn)是否曾組成 1個(gè)半邊,如果沒(méi)有,則說(shuō)明這 2個(gè)點(diǎn)分屬于不同的 2個(gè)三角面片,需新生成 1個(gè)邊節(jié)點(diǎn),同時(shí)將該半邊設(shè)置為新邊的 1個(gè)半邊.

通過(guò)以上過(guò)程,將生成 4個(gè)雙向鏈表,即體鏈表、面鏈表、邊鏈表、頂點(diǎn)鏈表,還有表示三角面片 3個(gè)互相連接半邊的半邊鏈表(雙向循環(huán)鏈表).需要指出的是拓?fù)渲亟ㄍ瓿珊?體鏈表、面鏈表、邊鏈表、頂點(diǎn)鏈表各只有 1個(gè).而 1個(gè)三角面片就對(duì)應(yīng) 1個(gè)半邊鏈表,有多少三角面片就生成多少半邊鏈表.

圖 1 半邊與邊關(guān)系Fig.1 Relation between halfedge and edge

2 實(shí)體邊界識(shí)別

能將實(shí)體邊界識(shí)別出來(lái)是基于這樣一個(gè)簡(jiǎn)單的事實(shí):處于邊界上的三角面片邊,在拓?fù)渲亟ㄍ瓿珊?在拓?fù)浣Y(jié)構(gòu)中將只有 1個(gè)半邊以及邊,而沒(méi)有伙伴半邊,如圖 2所示;而不處于邊界上的三角面片邊,在拓?fù)渲亟ㄍ瓿珊?將有 1個(gè)半邊及其對(duì)應(yīng)的伙伴半邊和邊,如圖 1所示.

邊界識(shí)別過(guò)程分為 2個(gè)步驟:

1)將 STL文件表示實(shí)體的所有邊界點(diǎn)全部提取出來(lái);

2)在步驟 1)的基礎(chǔ)上,將各個(gè)單獨(dú)的封閉邊界點(diǎn)集從全部邊界點(diǎn)集中提取出來(lái).

步驟 1)是通過(guò)一個(gè)邊查找函數(shù)實(shí)現(xiàn)的,其核心代碼如下(用 C++實(shí)現(xiàn)):

其中,ptEdge是此邊查找函數(shù)的傳入變量,表示拓?fù)渲亟ê笮纬傻倪呮湵淼氖椎刂?he1和 he2是邊節(jié)點(diǎn)中的 2個(gè)成員變量,分別表示 1個(gè)邊的左、右半邊節(jié)點(diǎn)地址.如果 1個(gè)邊節(jié)點(diǎn)只有 1個(gè)半邊而沒(méi)有其伙伴半邊,則說(shuō)明它是 1個(gè)邊界邊,將此邊的 2個(gè)端點(diǎn)坐標(biāo)保存到 outputFile文件流對(duì)象中,然后通過(guò)此文件流對(duì)象將數(shù)據(jù)寫(xiě)入到數(shù)據(jù)文件中.雖然保存的是點(diǎn)坐標(biāo),但實(shí)質(zhì)保存的是各個(gè)邊界線段.也就是說(shuō),第 1、2點(diǎn)組成一個(gè)邊界邊,第 3、4點(diǎn)組成另一個(gè)邊界邊,其余類推.此外,模型中互相相連的邊界邊在實(shí)際查找過(guò)程中不一定以連續(xù)的順序存入數(shù)據(jù)文件,這也是為什么還要執(zhí)行步驟 2)的原因.

步驟 2)是通過(guò) 5個(gè)子過(guò)程實(shí)現(xiàn)的:

①將步驟 1)中提取出來(lái)的全部邊界點(diǎn)集保存起來(lái).因?yàn)辄c(diǎn)集數(shù)目是未知的,所以使用動(dòng)態(tài)數(shù)組能將數(shù)據(jù)保存起來(lái),但是 C++中并沒(méi)有動(dòng)態(tài)數(shù)組這種數(shù)據(jù)類型.標(biāo)準(zhǔn)C++庫(kù)提供了一個(gè)標(biāo)準(zhǔn)容器“vector”,可以使用vector實(shí)例化一個(gè)基本數(shù)據(jù)類型的容器對(duì)象,然后將點(diǎn)集元素存入 vector對(duì)象.同時(shí),vector還提供了追加、查找、刪除等方法,方便了對(duì)數(shù)據(jù)的操作,在后面的幾個(gè)步驟中均用到了這些方法.

②從步驟 1)形成的 vector對(duì)象(下面簡(jiǎn)稱為 v)中提取出第 1個(gè)封閉邊界.將 v中的第 1個(gè)元素(點(diǎn)坐標(biāo))存入另一個(gè) vector對(duì)象 v1,然后在 v中查找同 v的第 2個(gè)元素值相同的另一個(gè)元素(記為第 j個(gè)元素),找到后存入 v1.這樣就將此封閉邊界的第 1個(gè)邊找到,同時(shí)也找到了和第 1個(gè)邊相連的下一個(gè)邊的開(kāi)始點(diǎn)(第 j個(gè)元素).隨后循環(huán)進(jìn)行此過(guò)程,直到找到的元素值和 v中的第 1個(gè)元素值相同,循環(huán)結(jié)束.

③將 v中和 v1元素值相同的元素刪除.

④重復(fù)進(jìn)行②和③,將余下的各個(gè)封閉邊界找出,直到 v中不再有任何元素.

⑤將獲得的各個(gè)封閉邊界點(diǎn)坐標(biāo)輸出到相應(yīng)的數(shù)據(jù)文件.

圖 2 邊界邊示意圖Fig.2 Graph of boundary edge

3 封閉邊界區(qū)域 Delaunay三角剖分

由于 STL文件是由三角面片組成的表面模型,所以必須將獲得的各個(gè)封閉邊界圍成的區(qū)域進(jìn)行三角剖分,才能使 STL文件表示的模型成為一個(gè)封閉的表面模型.一種比較簡(jiǎn)單和自然的三角剖分的方式如圖 3所示(實(shí)線代表原始的封閉邊界),從圖 3中可以發(fā)現(xiàn),該方法產(chǎn)生的三角形大部分是狹長(zhǎng)的,從進(jìn)行有限元分析的角度出發(fā),這種三角形的質(zhì)量不好,不適合進(jìn)行有限元分析.通過(guò)分析,發(fā)現(xiàn)產(chǎn)生狹長(zhǎng)的三角形是因?yàn)槿切蔚淖钚〗禽^小,要是能使剖分后生成的三角形的最小角角度較大,將是一種較好的三角剖分方式(理想的形狀是等邊三角形).

事實(shí)上,這是計(jì)算幾何上的一個(gè)經(jīng)典問(wèn)題,即 Delaunay三角剖分.設(shè) P為任一平面點(diǎn)集.P的任一角度最優(yōu)的三角剖分,必是 P的一個(gè) Delaunay三角剖分.此外,在 P的所有三角剖分中,Delaunay三角剖分使最小角達(dá)到最大[11].美國(guó)的 Jonathan Richard Shewchuk在互聯(lián)網(wǎng)上公布了專門解決 2D點(diǎn)集 Delaunay三角剖分的程序 Triangle[12],利用這個(gè)程序可以非常方便地對(duì) 2D點(diǎn)集進(jìn)行 Delaunay三角剖分.值得注意的是,根據(jù)不同的輸入,Triangle會(huì)對(duì) 2D點(diǎn)集進(jìn)行不同的 Delaunay三角剖分.對(duì)于本文的問(wèn)題,是一個(gè)帶有約束條件的二維 Delaunay三角剖分,同時(shí)應(yīng)允許在封閉邊界內(nèi)部插入一些點(diǎn)(Steiner點(diǎn)),以便進(jìn)行較高質(zhì)量的 Delaunay三角剖分.這里所說(shuō)的約束條件是指,只允許在邊界內(nèi)部插入點(diǎn)而不允許在邊界線段上插入點(diǎn),否則會(huì)產(chǎn)生如圖 4所示的不符合 STL文件格式的三角剖分(一個(gè)三角面片中的頂點(diǎn)不能落在另一個(gè)三角面片的邊上).

圖 3 三角剖分的一種方式Fig.3 One way of triangulation

圖 4 不合適的三角剖分方式Fig.4 An unfitway of triangulation

通過(guò)使用 Triangle程序,可以很容易地對(duì)各個(gè)封閉邊界進(jìn)行 Delaunay三角剖分,同時(shí)獲得剖分后的各個(gè)三角形頂點(diǎn)坐標(biāo).

通過(guò)使用 C++中文件追加數(shù)據(jù)的方法,按照 STL文件的格式要求,可將獲得的三角面片數(shù)據(jù)寫(xiě)回STL文件中.圖 5是沒(méi)有經(jīng)過(guò)上述處理而具有開(kāi)口的 1個(gè) STL文件模型,圖 6是經(jīng)過(guò)上述封閉處理后的 1個(gè) STL文件模型.開(kāi)口表面模型封閉化是進(jìn)一步有限元體網(wǎng)格劃分的關(guān)鍵.

圖5 動(dòng)脈血管模型Fig.5 Model of artery blood

圖 6 封閉的動(dòng)脈血管模型Fig.6 Closedmodelof arteries

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

本文以動(dòng)脈血管 STL模型為例,探討了 STL模型的拓?fù)渲亟?、開(kāi)口邊界識(shí)別及其三角剖分的方法.在此基礎(chǔ)上,開(kāi)發(fā)了相應(yīng)的自動(dòng)處理軟件.文中所述方法和所開(kāi)發(fā)軟件不僅適用于動(dòng)脈血管 STL模型,而且對(duì)其他領(lǐng)域的 STL模型同樣適用.

[1]ZHANG Y,BAZILEVS Y,GOSWAMI S,etal.Patient-specific vascular NURBSmodeling for isogeometric analysis of blood flow[J].Computer Methods in Applied Mechanics and Engineering,2007,196(29-30):2943-2959.

[2]SCHOBERL J.NETGEN-An advancing front 2D/3D-meshgenerator based on abstract ru les[J].Computing and Visualization in Science,1997,1(1):41-52.

[3]張翔,廖文和,程筱勝,等.STL格式文件的拓?fù)渲亟ǚ椒ㄑ芯縖J].機(jī)械科學(xué)與技術(shù),2005,24(9):1093-1096.ZHANG Xiang,LIAO Wen-he,CHENG Xiao-sheng,et al.Study on topology reconstruction of STL file[J].Mechanical Science and Technology,2005,24(9):1093-1096.(in Chinese)

[4]候?qū)毭?劉雪娜.STL實(shí)體模型的拓?fù)渲亟捌淙毕菪迯?fù)[J].計(jì)算機(jī)工程,2005,31(3):213-217.HOU Bao-m ing,LIU Xue-na.Topological reconstruction of STL solidsmodel and its errors repair[J].Computer Engineering,2005,31(3):213-217.(in Chinese)

[5]RYPL D,BITTNAR Z.Generation of computational surface meshes of STL models[J].Journal of Computational and App lied Mathematics,2006,192(1):148-151.

[6]趙美利,楊晶,毛紅奎,等.基于STL文件格式的實(shí)體分割及缺陷修復(fù)方法研究[J].系統(tǒng)仿真技術(shù),2008,4(1):35-39.ZHAO Mei-li,YANG Jing,MAO Hong-kui,et al.Research on themethod for dividing a entity and defects repair based on STL file format[J].System Simulation Technology,2008,4(1):35-39.(in Chinese)

[7]王成,曾曉雁.激光三維雕刻中實(shí)時(shí)切片算法研究[J].工程圖學(xué)學(xué)報(bào),2008,29(1):13-18.WANG Cheng,ZENG Xiao-yan.Real-time slicing algorithm for 3D laser carving system[J].Journal of Engineering Graphics,2008,29(1):13-18.(in Chinese)

[8]MANTYLA M.An introduction to solid modeling[M].Rockville,Maryland:Computer Science Press,1988:168-170.

[9]WEILER K.Edge-based data structures for solid modeling in curved-surface environments[J].IEEEComputer Graphics and Applications,1985,5(1):21-40.

[10]劉金義,侯保明.STL格式實(shí)體的快速拓?fù)渲亟╗J].工程圖學(xué)學(xué)報(bào),2003,24(4):34-39.LIU Jin-yi,HOU Bao-ming.Efficient topological reconstruction of solids in STL format[J].Journal of Engineering Graphics,2003,24(4):34-39.(in Chinese)

[11]BERG M D,KREVELD M V,OVERMARSM,et al.Computational geometry algorithms and applications[M].New York:Springer-Verlag Berlin Heidelberg,1997:191.

[12]SHEWCHUK JR.Delaunay refine mentalgorithms for triangularmesh generation[J].Computational Geometry,2002,22(1-3):21-74.