付文宇,喬愛科,付鵬斌

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

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

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

要對 STL文件進(jìn)行拓?fù)渲亟?需知道 STL文件數(shù)據(jù)結(jié)構(gòu),其詳細(xì)信息參見文獻(xiàn)[5-7].由于 STL文件只給出實體表面三角面片的點坐標(biāo)及其法線向量,因此任何一個可以完整表示多面體的數(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)用一個只有半邊沒有伙伴半邊的邊查找過程,就能將STL模型開口邊界識別出來,因此,本文選擇半邊結(jié)構(gòu)作為拓?fù)渲亟ǖ臄?shù)據(jù)結(jié)構(gòu).

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

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

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

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

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

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

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

2 實體邊界識別

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

邊界識別過程分為 2個步驟:

1)將 STL文件表示實體的所有邊界點全部提取出來;

2)在步驟 1)的基礎(chǔ)上,將各個單獨的封閉邊界點集從全部邊界點集中提取出來.

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

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

步驟 2)是通過 5個子過程實現(xiàn)的:

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 動脈血管模型Fig.5 Model of artery blood

圖 6 封閉的動脈血管模型Fig.6 Closedmodelof arteries

4 結(jié)束語

本文以動脈血管 STL模型為例,探討了 STL模型的拓?fù)渲亟?、開口邊界識別及其三角剖分的方法.在此基礎(chǔ)上,開發(fā)了相應(yīng)的自動處理軟件.文中所述方法和所開發(fā)軟件不僅適用于動脈血管 STL模型,而且對其他領(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實體模型的拓?fù)渲亟捌淙毕菪迯?fù)[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文件格式的實體分割及缺陷修復(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]王成,曾曉雁.激光三維雕刻中實時切片算法研究[J].工程圖學(xué)學(xué)報,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格式實體的快速拓?fù)渲亟╗J].工程圖學(xué)學(xué)報,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.