面向復雜網(wǎng)格模型的快速分層算法研究

（中科院廣州電子技術有限公司，廣州 510070）

0 引言

熔融沉積制造（Fused Deposition Modeling，F(xiàn)DM）技術是目前應用最為廣泛的三維打印技術之一，在注塑模具、醫(yī)療、玩具、汽車、電子以及個人定制等領域得到大量應用[1,2]。FDM的制造原理是分層累積成形，其制造過程中每一層都是通過數(shù)據(jù)處理軟件將數(shù)字化三維模型切片后得到截面輪廓，然后規(guī)劃生成打印設備噴頭的運動軌跡并輸出到打印設備進行成形制造。分層切片算法是3D打印軟件的關鍵內(nèi)容之一，不僅是實現(xiàn)離散堆積成形的重要環(huán)節(jié)，而且對成形速度、成形精度、零件表面質(zhì)量等方面都有很大影響。

針對三維打印模型的分層切片算法研究包括兩個主要方面，其一是基于CAD（Computer Aided Design）幾何模型的直接分層切片[3,4]，其二是針對離散化網(wǎng)格模型的分層切片方法。CAD模型具有完整的曲面數(shù)學表示，可以通過求解數(shù)學方程獲得分層輪廓的數(shù)學表達式，因而其截面輪廓更精確，數(shù)據(jù)量也更小，但這種方法的不足之處是數(shù)據(jù)交換導致應用的困難，這是因為CAD模型的邊界表示模型不同廠商之間具有相對差異性，難以在三維打印軟件中統(tǒng)一處理，制約了基于CAD模型分層處理軟件的實際應用。解決這一缺點的一個主要方法將各種CAD數(shù)據(jù)格式轉(zhuǎn)化為標準化的數(shù)據(jù)格式，其中最為典型的是針對STEP（STandard for the Exchange of Product Model Data）標準幾何模型的分層切片算法[5,6]，但仍存在轉(zhuǎn)換過程中的容差差異等系列問題。目前3D打印軟件系統(tǒng)大都采用離散化面片模型作為其數(shù)據(jù)輸入格式[7]，這類模型數(shù)據(jù)格式公開而簡潔，是事實上的三維打印軟件數(shù)據(jù)輸入格式標準，被主流商業(yè)軟件系統(tǒng)所采用，如美國3D Systems公司的Dimension，比利時Materilise公司的MagicRP等。由于網(wǎng)格模型的離散化表示，需要大量求交運算以得到分層切片，因此提高其計算效率對于算法非常重要[8]，這方面的一個重要思路是建立三角網(wǎng)格之間拓撲關系以降低計算量，如基于信息繼承對三角網(wǎng)格進行分類和排序等方法[9,10]，這類方法需要對數(shù)據(jù)結(jié)構(gòu)進行良好的優(yōu)化以降低內(nèi)存消耗。網(wǎng)格模型分層的一個不足之處是層級臺階現(xiàn)象導致加工表面的粗糙，解決這一問題的一個有效方法是進行適應性的分層[11,12]，即基于模型表面的粗糙程度或者精度要求，適應性的變化分層厚度，而不是用單一的厚度來進行分層切片。

3D打印技術是制造史上的巨大突破，其市場前景遠大，但競爭也日趨激烈，要在激烈的市場競爭中占有一席之地，三維打印設備必須從各方面提高其性能。面向三維打印的數(shù)據(jù)預處理技術對于提高三維打印質(zhì)量非常關鍵，在性能近似的硬件設備中，更好的數(shù)據(jù)預處理能夠使類似的硬件設備產(chǎn)生更好的打印效果，從而提高打印設備的市場競爭力。高端的商業(yè)三維打印數(shù)據(jù)處理系統(tǒng)價格昂貴，而開源系統(tǒng)在商業(yè)應用上的許可制度等因素，大大影響了我國三維打印行業(yè)的進一步發(fā)展，開發(fā)具有自主產(chǎn)權(quán)的三維打印軟件系統(tǒng)，對于縮小我國三維打印與先進國家的差距具有重要意義。

針對目前三維打印設備數(shù)據(jù)處理軟件現(xiàn)狀，我們研發(fā)了具有自主知識產(chǎn)權(quán)的數(shù)據(jù)預處理軟件系統(tǒng)，提出了網(wǎng)格模型分層切片技術，針對面片數(shù)較多并且形狀復雜的大模型進行了效率性能方面的改進優(yōu)化。接下來對該方法進行闡述，其中第一部分為算法總體框架，第二部分為算法的具體實現(xiàn)細節(jié)以及關鍵點介紹，第三部分介紹了輪廓區(qū)域界定方法，第四部分給出了系統(tǒng)實現(xiàn)和實例討論，最后給出論文總結(jié)。

1 基于拓撲跟蹤的網(wǎng)格分層切片算法概述

網(wǎng)格分層切片算法是按照三維打印設備的層高要求，從最低端到最高端依次獲取模型的截面輪廓，為后續(xù)驅(qū)動FDM設備噴頭的運動路徑規(guī)劃做準備。當模型變得復雜并且網(wǎng)格數(shù)目較多時，分層效率和穩(wěn)定性尤為關鍵。為此，我們提出基于網(wǎng)格模型拓撲關系的快速分層算法，該算法建立了面向分層切片的網(wǎng)格模型半邊結(jié)構(gòu)，基于該結(jié)構(gòu)依次求取相鄰面片的交線，并自動形成首尾閉合的輪廓線，然后基于輪廓層次結(jié)構(gòu)樹生成輪廓加工區(qū)域，總體框架如圖1所示。該算法以三角網(wǎng)格模型為輸入，以分層切片區(qū)域為輸出，其關鍵在于如何高效的建立模型的拓撲關系，并盡量降低內(nèi)存耗費，其次是如何快速跟蹤求交，得到輪廓的各個線段，最后是如何判斷輪廓的包含關系，得到模型的輪廓截面區(qū)域。

圖1 分層切片算法框架

2 基于拓撲跟蹤的輪廓快速獲取

2.1 網(wǎng)格模型半邊數(shù)據(jù)結(jié)構(gòu)建立

基于半邊結(jié)構(gòu)建立網(wǎng)格模型的拓撲結(jié)構(gòu)，并面向三維打印快速分層需求，在該結(jié)構(gòu)中加入相應的數(shù)據(jù)結(jié)構(gòu)以提高求解效率，如圖2所示。其特點是每條邊分裂為兩條半邊，其表示極為簡潔，并可以非常容易地實現(xiàn)鄰邊查找、邊遍歷、點所關聯(lián)邊查找等關鍵操作。為實現(xiàn)輪廓線快速求取，我們將該半邊結(jié)構(gòu)進行擴充，增加了每條邊的斜率以及當前的截面法向及是否為水平方向等信息。由于三角網(wǎng)格模型只是記錄了三角形的頂點信息，因此需要在建立該結(jié)構(gòu)時，判斷三角形的公共邊，這可以基于頂點建立紅黑樹排序來降低頂點比較次數(shù)，提高計算效率。

圖2 面向分層切片的三角網(wǎng)格半邊結(jié)構(gòu)表示

2.2 輪廓線追蹤求交算法流程

基于建立的網(wǎng)格模型拓撲結(jié)構(gòu)，我們給出了圖3所示的分層輪廓線求解算法。該算法的核心是基于一個初始相交三角網(wǎng)格，通過拓撲關系依次追蹤求解至終止邊界。

圖3 基于拓撲追蹤的分層切片算法

該算法可以實施的一個前提是網(wǎng)格模型的每個面片具有特定的法向，如圖4所示，即每個三角形的邊走向是一定的，其法向指向模型物體的外部。圖4中，B所表示的Z平面中，假設初次獲得的相交三角形是F1，則容易求得交點P1、P2，則線段方向為P1P2。基于P2所對應的半邊，容易得到下一個三角網(wǎng)格為F2，順次求解，可以得到一個完整的輪廓線。圖4中給出了存在的奇異情況A，即交點為三角形頂點，這種情況下，只需要遍歷圍繞該頂點所有三角網(wǎng)格，直至遇到具有兩個不同交點的面片即可，如圖中的F3。

圖4 追蹤求解圖示

三角網(wǎng)格與切面的交點求解只需要求解與每條邊的交點。圖5為分層平面與三角網(wǎng)格的交點情況，分別具有1、2、3個交點，即分別與1、2、3條邊相交，在算法中只需記錄兩個交點以及每個交點對應的半邊。

圖5 平面與三角網(wǎng)格交點情況

不同的交點情況影響到求解輪廓線的過程。如圖6所示，其初始三角形為F1。對于情況B，其求解交點過程是按照F1的走向依次對邊進行求解，顯然輪廓追蹤終止邊界為F2，即依次追蹤求解到F2即可得到當前的完整輪廓線。但對于A情況，由于其交點為錐形端點，因此追蹤邊界為F4，為實現(xiàn)上的方便，我們?nèi)2、F3、F4的集合作為追蹤終止邊界。

圖6 追蹤終止邊界情況

3 分層切面區(qū)域定義

已經(jīng)求得的邊界輪廓線需要定義其走向以確定分層切面的內(nèi)部區(qū)域，以進一步確定打印噴頭所需要填充的區(qū)域。如圖7所示，其中藍色區(qū)域為模型的內(nèi)部區(qū)域，而數(shù)字1到8所標識的輪廓線即為前述算法所確定的輪廓邊界線。

圖7 分層輪廓區(qū)域定義示意圖

確定有效加工區(qū)域算法基本思路是：將所有的輪廓線兩兩判斷相互包含關系，將被包含的輪廓線定義為包含輪廓線的子輪廓，同時將其層級加一，若相互無包含關系，則勿需操作。上述計算結(jié)果是定義了每個輪廓線的所有子輪廓線，同時計算了子輪廓線與其先輩輪廓線的層級距離，最終結(jié)果實際形成了輪廓線之間的父子關系樹，顯然，層級差為1的輪廓線之間組成了一個片連續(xù)加工區(qū)域，從而確定了分層切片的內(nèi)外輪廓。基于上述算法，圖7中的輪廓線層級關系樹如圖8所示。

圖8 輪廓線層級關系樹（針對圖7）

4 系統(tǒng)實現(xiàn)與實例分析

在Windows平臺下，采用C++在Visual Studio 2013開發(fā)環(huán)境下實現(xiàn)了三維打印數(shù)據(jù)處理軟件系統(tǒng)，該系統(tǒng)采用本文所介紹算法對STL模型進行分層切片。以下基于模型實例驗證分析本文算法的有效性。

圖9為采用該算法處理的一個復雜框架模型，該模型頂點數(shù)為40482，三角網(wǎng)格面片數(shù)為81752，物體長、寬、高分別為55、55、55。圖10為高度為1.375時，分層截面的形狀，圖11為高度為23.375時的分層切片。圖12為對模型逐層切片后的結(jié)果，生成該切片數(shù)據(jù)大約需要3秒時間，其中的層高為0.25。

圖13為需要打印的一個工藝品模型，該模型頂點數(shù)為59818，三角網(wǎng)格數(shù)為：124316，物體長、寬、高分別為90、95、43。圖14為高度為4.125時分層截面的形狀，圖15、16分別為高度為10.375、24.625時的分層截面形狀。圖17為對模型逐層切片后的結(jié)果，生成該切片數(shù)據(jù)大約需要4秒時間，其中的層高為0.25。

圖9 框架網(wǎng)格模型

圖10 高度1.375截面輪廓

圖11 高度23.375截面輪廓

圖12 模型總體分層輪廓（模型圖9）

圖13 工藝品網(wǎng)格模型圖

圖14 高度4.125截面輪廓

圖15 高度10.375截面輪廓

圖16 高度24.625截面輪廓

圖17 模型總體分層輪廓（模型圖13）

5 結(jié)論

給出了一種基于網(wǎng)格模型拓撲關系追蹤求交的三維打印分層切片算法，通過對網(wǎng)格模型基于半邊結(jié)構(gòu)建立面向分層切片的內(nèi)在拓撲關系，在求解時可以基于半邊關系追蹤求交并得到輪廓線，勿需基于交點重新組合輪廓線，不僅降低了運行時間，而且可以降低由于容差帶來可能的輪廓錯誤，并基于輪廓層級關系樹確定有效加工區(qū)域。該算法數(shù)據(jù)結(jié)構(gòu)簡潔，計算效率高，內(nèi)存耗費低。實例表明該算法穩(wěn)定可靠，特別是針對復雜網(wǎng)格模型具有良好的效率和魯棒性。