吳 婷，張禮兵

(嘉興學(xué)院 信息科學(xué)與工程學(xué)院，浙江 嘉興 314001)

0 引言

三角網(wǎng)格模型是一種采用大量三角片模擬復(fù)雜物體表面的三維幾何模型。描述三角網(wǎng)格模型的STL(standard template library)文件因其數(shù)據(jù)格式簡單、占用儲存空間少，已成為3D打印系統(tǒng)的一類標準接口文件格式，它能夠滿足模型信息在不同軟件系統(tǒng)之間高效、及時傳輸?shù)男枨骩1]。在對STL模型進行3D打印時，分層切片處理是首要且最為關(guān)鍵的一步，它通過層切平面與三維模型相交，得到各層切片輪廓信息[2]。由于切片處理需要計算每層切平面與三角片的交線，大量三角片會影響創(chuàng)建切片輪廓的時間，切片算法的有效性直接影響了最終模型制作的效率和質(zhì)量。

目前，現(xiàn)有切片算法和商業(yè)軟件都主要針對流形網(wǎng)格模型，即模型封閉且無自交，不存在法向量錯誤、相鄰面片不共頂點、頂點分離、重疊面片和孤立面片等網(wǎng)格模型常見錯誤[3]。然而，在實際應(yīng)用中，從三維掃描儀、CT和MRI等設(shè)備構(gòu)建出來的STL模型，通常含有孔洞、懸邊、懸面、自交等情況。將CAD軟件繪制的3D模型轉(zhuǎn)換為STL模型時，也容易出現(xiàn)三角片重疊、拓撲連接信息重復(fù)或相鄰面片法向不相容等情況[4]。雖然一些逆向工程軟件能夠自動修復(fù)不正確法矢、重疊三角片、孔洞裂縫等簡單錯誤，但對于一些復(fù)雜的非流形三角片則無法進行修復(fù)。如果直接用傳統(tǒng)流形網(wǎng)格的切片算法處理非流形網(wǎng)格，會導(dǎo)致難以修復(fù)的錯誤結(jié)果。因此，研究適用于流形網(wǎng)格和非流形網(wǎng)格模型的切片處理算法，對于提高分層切片處理的有效性和魯棒性具有重要意義。

1 相關(guān)工作

STL模型文件記錄了每個三角片的頂點和法矢信息，因此對STL模型進行切片，需首先根據(jù)頂點坐標判斷三角片與各層切平面的相交關(guān)系，然后計算出切平面與三角片的交線段，并將這些交線段連接成有序輪廓，如圖1所示。根據(jù)STL模型的復(fù)雜性，切片算法具體可分為基于流形網(wǎng)格的算法和基于非流形網(wǎng)格的算法兩種情況。

1.1 流形網(wǎng)格模型切片算法

流形網(wǎng)格模型一般需滿足兩個條件：①每一條網(wǎng)格邊只被兩個三角面片所共享；②與每一個頂點相鄰接的邊和面構(gòu)成一個且只能構(gòu)成一個圍繞該頂點的“環(huán)”。一個網(wǎng)格表面是流形(manifold)的，當且僅當它所有的邊和頂點都是流形的，否則為非流形(non-manifold)的[5]，如圖2所示。

盡管流形網(wǎng)格模型中三角片之間拓撲連接緊密，但在STL文件中三角片的存儲順序卻是雜亂無章的，因此要想獲得有序的切片輪廓，關(guān)鍵在于如何將切平面與這些散亂的三角片形成的交線段有序地組織起來。目前已有的基于流形網(wǎng)格的切片算法中，應(yīng)用最廣泛的有以下兩種類型：

(1)基于冗余交點信息的切片算法 該類算法首先計算出切平面與所有三角片的交線段，由于相鄰三角片之間存在公共邊，因此這些交線段的端點存在重復(fù)，利用這些重復(fù)冗余的交點信息即可確定三角片之間的鄰接關(guān)系，將交點依次首尾連接即可得到有序封閉輪廓[6-8]，如圖3所示。田仁強等[9]首先采用二分查找法進行切平面與相交三角片的快速分組，然后在計算出交線段后，利用深度優(yōu)先搜索算法將這些散亂交線段連成有序封閉輪廓。MINETTO等[10]將相交線段端點間的鄰接關(guān)系建立成哈希表，利用哈希表的快速查詢功能將這些交線段構(gòu)成有序輪廓，從而極大提高了切片算法的執(zhí)行時間。這種類型的算法無需構(gòu)建復(fù)雜的網(wǎng)格拓撲關(guān)系，但在計算切平面和三角片公共邊的交點時會重復(fù)計算兩次。

(2)基于網(wǎng)格拓撲信息的切片算法 該類算法需要首先建立STL模型三角片之間的鄰接拓撲關(guān)系，然后在求得切平面與第一個相交三角片后，根據(jù)拓撲關(guān)系找到與之相鄰的下一個三角片，依次求交后即可得到首尾相連的有向封閉輪廓[11-12]。這種算法能夠避免重復(fù)計算冗余交點，而且無需對交點進行重新排序。但如果建立整個網(wǎng)格的拓撲關(guān)系，分層算法處理拓撲信息耗時較長、內(nèi)存占用量較大，尤其是在處理數(shù)據(jù)量較大的STL文件時，將十分費時且對計算機的計算能力要求更高[13]。王素等[14]根據(jù)三角片各點坐標在切平面方向上投影的最大值和最小值反求與此三角片相交的切平面，并通過分析相鄰兩個三角片公共邊與切平面的位置關(guān)系, 按鄰接順序建立交點鏈表，該算法不進行整體拓撲信息的提取和三角片的分組排序，只需讀取一次信息即可建立有序的交點鏈表。徐敬華等[3,15]利用半邊數(shù)據(jù)結(jié)構(gòu)[16]建立每層相交三角面片集合的局部鄰接拓撲關(guān)系，通過哈希鏈表遞歸遍歷求解每一個三角面片的鄰接面片，最后依次求解這些面片間的公共邊與切平面的交點以獲得有序輪廓交點集，如圖4所示。ZHANG等[17]根據(jù)STL文件中三角片頂點的存儲順序和坐標值確定出每個三角片與切平面相交的“前驅(qū)邊”和“后繼邊”，并由此建立了三角片之間的鄰接關(guān)系鏈表，依次計算鏈表中每個三角片的前驅(qū)邊和切平面的交點即可得到有序的封閉輪廓，該算法不僅可以避免冗余交點的重復(fù)計算和交點排序，還能夠自動識別內(nèi)外輪廓。

1.2 非流形網(wǎng)格模型切片算法

與流形網(wǎng)格相比，非流形網(wǎng)格模型中三角片的拓撲關(guān)系更為復(fù)雜，通常表現(xiàn)為一個網(wǎng)格邊被兩個以上的三角片共享。因此，若用傳統(tǒng)方法對非流形網(wǎng)格進行切片，由于在公共邊處無法分辨分支走向，會造成輪廓排序混亂。針對這一問題，MCMAINS等[18]將非流形三角片的法矢投影到與非流形邊垂直的平面上，根據(jù)法矢投影的指向來構(gòu)建相鄰三角片的鄰接關(guān)系，以此構(gòu)建正確的封閉輪廓，但該方法無法處理大量非流形邊匯聚相交的問題。HUANG等[19]通過分析模型上的每個公共邊所共享三角片的數(shù)量，將每條邊的屬性進行標記，然后在計算切平面與邊的交點時，若遇到非流形邊，找到與該邊相鄰的下一個非流形邊進行求交，直到計算完成所有邊與切平面的交點。該方法對于模型上的裂縫能夠產(chǎn)生較好的效果，但當多個三角形共享一條邊時，求得的交線容易出現(xiàn)繞行，從而無法產(chǎn)生正確的封閉區(qū)域。巢海遠等[20]針對非封閉網(wǎng)格，首先建立點邊面的拓撲連接關(guān)系，并利用邊界判斷規(guī)則提取所有邊界邊，然后在計算切平面與所有三角片的交點后，從含有邊界邊的三角片開始，按照鄰接關(guān)系依次連接交點以獲得非封閉的切片輪廓，由于這種方法需要建立整個網(wǎng)格的拓撲關(guān)系和邊界邊索引，因此切片效率較低。

可以看出，現(xiàn)階段關(guān)于流形網(wǎng)格模型切片算法的研究較多，而對非流形網(wǎng)格模型的切片算法還沒有形成一套完善的體系。目前切片算法主要存在兩個需要解決的問題：①如何避免耗時耗空間的鄰接拓撲關(guān)系的建立，并將散亂的交線段排列成有序輪廓，關(guān)系到整個算法的效率;②無論是流形網(wǎng)格還是非流形網(wǎng)格，都有可能產(chǎn)生切片輪廓的奇異問題，傳統(tǒng)單一的輪廓跟蹤或攝動法[21]無法解決多個輪廓的自交，也不能去除多余輪廓分支，因此建立有效的奇異問題解決方法尤為重要。

針對上述挑戰(zhàn)和問題，本文提出一種面向流形和非流形網(wǎng)格模型的高效切片算法，該方法將三角片和切平面的相交關(guān)系映射成無向圖，利用圖的節(jié)點度特性判斷切片輪廓的封閉性和復(fù)雜性，并基于圖論的路徑規(guī)劃技術(shù)進行輪廓構(gòu)建，以解決切片輪廓的排序和自交問題。

2 本文方法

本文提出的面向流形和非流形網(wǎng)格模型的高效切片算法主要包括數(shù)據(jù)預(yù)處理、相交邊提取、無向圖構(gòu)建、輪廓路徑規(guī)劃4個部分，算法整體框架如圖5所示。首先對輸入的模型進行預(yù)處理，使模型數(shù)據(jù)滿足正則性和有序性要求；其次，根據(jù)三角片與切平面的關(guān)系提取每層的相交邊集合，并將相交邊關(guān)系映射為無向圖；最后利用圖的節(jié)點度特性判斷切片輪廓的封閉性和自交性，并基于路徑規(guī)劃技術(shù)對不同類型輪廓進行拓撲排序。

2.1 數(shù)據(jù)預(yù)處理

為保證切片算法的有效性和準確性，首先應(yīng)對輸入的STL模型進行合法性檢查，修復(fù)模型的拓撲錯誤，使模型為正則三角網(wǎng)格模型[4]，即模型無懸面、無重疊等錯誤。

修復(fù)STL模型后，由于模型三角片的存儲順序是散亂的，為提高分層切片處理速度，需根據(jù)三角片的頂點坐標對三角片數(shù)據(jù)進行排序優(yōu)化，以加快篩選出與各層切平面相交的三角片集合。

不失一般性，設(shè)層切平面垂直于z軸。根據(jù)成型精度和模型表面形態(tài)特征，首先確定各層切平面的位置hi,i=1, 2, …,n，n為切片總數(shù)；然后獲取模型上每個三角片的3個頂點坐標vmin(x1,y1,zmin)，vmed(x2,y2,zmed)，vmax(x3,y3,zmax)，其中，zmin、zmed、zmax分別為3個頂點z軸坐標的最小值、中間值和最大值。由圖6可知，對于第i層切平面hi，當zmin≤hi≤zmax時，該三角片與當前層切平面hi相交。因此，將模型三角片序列中每個三角片的3個頂點按z軸坐標最小值zmin、中間值zmed和最大值zmax的順序進行排序；然后對所有的三角片按z軸坐標最小值進行升序排序，即z軸坐標最小值zmin更小的三角片排在前面。

2.2 相交邊提取

當模型的三角片序列按照從低到高排序后，對于高度為hi的切平面，若某個三角片的zmin>hi, 則排在其后的三角片都不會與該切平面相交, 無需再進行相交計算。因此，查找三角片序列中最后一個滿足zmin≤hi的三角片索引號j，提取出前j個三角片，然后在前j個三角片中比較每個三角片的zmax和hi大小，若有zmax

對于任意一層切平面篩選出的相交三角片集合，切平面均與集合中每個三角片的兩條邊相交。為了快速計算出交點坐標，將三角片的每條邊用該邊的兩個頂點vi、vj表示為，當某個頂點vi與切平面在z軸方向的距離小于容差ε(例如，ε=10-5)時，則認為該頂點vi在切平面上，將其相交邊修改為。

提取出每個三角片與切平面相交的兩條邊e1、e2后，將其構(gòu)建成一個相交邊對：[e1,e2]。根據(jù)當前切片面hi與三角片3個頂點z軸坐標zmin、zmed、zmax的關(guān)系，相交邊對分為如下幾種情況：

(1)當zmin

當hi

相交邊對：[，]；

當hi=zmed，

相交邊對：[，]；

當hi>zmed，

相交邊對：[，]。

(2)當zmed=zmin=hi且zmax>hi, 如圖7b所示:

相交邊對：[，]。

(3)當zmed=zmax=hi且zmin

相交邊對：[，]。

(4)其他。

無相交邊。

以如圖8所示情況為例，切平面hi與各三角面片F(xiàn)j(j=1,2,…,7)產(chǎn)生的相交邊如表1所示，其中三角片F(xiàn)6與切平面只有一個交點，故無相交邊對。因此，最終得到的有效相交邊集合為： {[e1,e2],[e3,e4],…,[e11,e12]}。

表1 圖8所對應(yīng)的相交邊信息

2.3 構(gòu)建相交邊無向圖

由于每個三角片的兩條邊與切平面產(chǎn)生交點，交點連線構(gòu)成交線段，可以將這兩條邊映射為節(jié)點，交線段映射為節(jié)點間的邊，將所有三角片與切平面形成的交線段都這樣映射后，就可以得到一個無向圖。具體步驟為：

步驟1將所有三角片的相交邊對組成集合：

V0={[e1,e2],[e3,e4],…,[e2s-1,e2s]}，

式中s為相交三角片總數(shù)。

步驟2將集合V0中的每條邊當做節(jié)點，對節(jié)點進行冗余過濾，建立不含冗余節(jié)點的集合：

V={ei|ei≠ej(i≠j)}。

將集合V中的節(jié)點對應(yīng)回原集合V0，求得索引向量id，使V0=V(id)。

步驟3根據(jù)集合V0中每兩條邊構(gòu)成邊對的關(guān)系，建立邊集：

步驟4利用集合V和邊集E，構(gòu)建無向圖G= (V,E)。

步驟5對圖G中的邊進行精簡，刪除重復(fù)的邊。

以如圖9a所示的切平面與三角片相交情況為例，按照所述方法，提取的相交邊對集合V0={[e1,e2],[e3,e4],…,[e11,e12]}，由于e2=e9,e3=e10,e4=e5,e6=e7=e11,e8=e12，對V0進行冗余過濾后得到集合V= {e1,e2,e3,e4,e6,e8}，然后根據(jù)V0中每兩個節(jié)點構(gòu)成邊對的關(guān)系，得到邊集E={[e1,e2], [e2,e3], [e3,e4], [e4,e6], [e6,e8], [e6,e8]}，利用V和E構(gòu)建的無向圖G如圖9b所示，因為圖9a中有兩個三角片與切平面產(chǎn)生的交線段重合，導(dǎo)致邊集E中的邊對[e6,e8]重復(fù)記錄了兩次，所以需對圖G中的邊集E進行精簡，刪除重復(fù)的邊，最終結(jié)果如圖9c所示。

2.4 輪廓路徑規(guī)劃

通過建立相交邊無向圖的數(shù)據(jù)結(jié)構(gòu), 可將相交邊的拓撲排序問題轉(zhuǎn)化為基于圖論的路徑規(guī)劃問題。根據(jù)模型的復(fù)雜性，每層切片有可能產(chǎn)生多條輪廓，每條輪廓還可能出現(xiàn)封閉、不封閉、自交等問題。為使算法具有較高的魯棒性，本文首先計算無向圖G的極大連通子圖Gg，g=1, 2, …,k，k為連通分量總數(shù)，根據(jù)每個連通子圖Gg中節(jié)點度的分布特性，對不同類型圖采用不同方法進行拓撲排序，以得到正確有序切片輪廓，整個技術(shù)路線如圖10所示。

節(jié)點度是指在一個圖中與該節(jié)點關(guān)聯(lián)的節(jié)點個數(shù)總和[22]。設(shè)D(Gg)為連通子圖Gg中所有節(jié)點的節(jié)點度集合，根據(jù)D(Gg)的分布特性，可將連通子圖Gg分為如圖11所示的3種類型。

如圖11a所示，這種類型的連通圖中所有節(jié)點度均為2，其所對應(yīng)的切片輪廓為簡單封閉環(huán)。對于這種輪廓的拓撲排序，可以將任意一個節(jié)點作為起點e1，然后從起點e1出發(fā)，按照深度優(yōu)先遍歷[23]搜索與它關(guān)聯(lián)的鄰接節(jié)點e2，再從節(jié)點e2出發(fā)，搜索與e2鄰接且未被訪問過的節(jié)點e3，依次進行搜索，直到回到起點e1。例如圖11a所示的連通圖，以節(jié)點1開始，按照深度優(yōu)先遍歷得到的有序封閉輪廓路徑為：1→2→3→4→5→1。節(jié)點排列順序確定后，依次計算節(jié)點對應(yīng)的相交邊和切平面的交點坐標即可得到有序輪廓交點集。

如圖11b所示，這種類型的連通圖，除首末節(jié)點的度等于1外，其余節(jié)點的度均為2，其所對應(yīng)的切片形狀為非封閉的開輪廓。對于這種輪廓的拓撲排序，首先找到圖中節(jié)點度為1的節(jié)點，將其作為首節(jié)點e1，然后按照深度優(yōu)先遍歷搜索與它關(guān)聯(lián)的鄰接節(jié)點，直到遍歷完全部的節(jié)點，即創(chuàng)建一條有序開輪廓。圖11b所示的開輪廓中，只有節(jié)點2和節(jié)點3的度數(shù)為1，按照存儲順序，節(jié)點2在節(jié)點3之前，因此以節(jié)點2為起點進行深度優(yōu)先排序，結(jié)果為2→1→5→4→3。

如圖11c所示，這種類型的連通圖存在度大于2的節(jié)點，如節(jié)點1、節(jié)點3和節(jié)點5，說明在該層切片位置，模型可能具有非流形邊，從而導(dǎo)致輪廓存在自交問題。對于該類型的節(jié)點拓撲排序，需找到圖中的割點，將圖分解為簡單連通圖。所謂割點，是指在一個圖中去掉一個節(jié)點，同時去掉與該點相關(guān)聯(lián)的所有邊后，該圖的連通分量數(shù)增加，則稱該節(jié)點為割點[24]。割點的節(jié)點度通常大于2，因為它是多個輪廓匯聚的關(guān)節(jié)點，利用Tarjan算法[25]可以找到圖的割點，并將圖分解為多個雙聯(lián)通子圖，每個雙聯(lián)通子圖不存在割點，從而有利于后續(xù)的節(jié)點排序，避免輪廓繞行。

根據(jù)上述分析，本文提出遞歸雙連通分解法來解決復(fù)雜自交輪廓的排序問題，整個流程如圖12所示。其基本思想為：首先計算連通圖Gg的雙連通子圖，若雙連通子圖的個數(shù)為1，即不存在割點，則直接利用雙連通子圖的節(jié)點建立凸包，根據(jù)凸包確定輪廓路徑的起始邊，然后進行路徑跟蹤，當構(gòu)成一條有序封閉輪廓路徑后，再將剩余節(jié)點集組成新圖后繼續(xù)進行分解；若雙連通子圖的個數(shù)不為1，則計算每個雙連通子圖節(jié)點度：若節(jié)點度都為2，則利用深度優(yōu)先遍歷構(gòu)建輪廓路徑，若某個雙連通子圖存在度大于2的節(jié)點，則利用上述基于凸包的方法進行輪廓跟蹤。

具體步驟如下：

步驟1計算連通圖Gg中每個節(jié)點對應(yīng)的相交邊與切平面的交點，將交點坐標作為圖中的節(jié)點坐標。

步驟2計算連通圖Gg的極大雙連通子圖，若雙連通子圖的個數(shù)大于1，則對每個雙連通子圖Ggg循環(huán)執(zhí)行步驟3；若雙連通子圖的個數(shù)等于1，則轉(zhuǎn)步驟4。

步驟3判斷雙連通子圖Ggg中節(jié)點度的分布：①當所有節(jié)點的度都等于2時，即D(Ggg)=2，利用深度優(yōu)先遍歷獲得該連通域內(nèi)的有序切片輪廓；②當節(jié)點度范圍D(Ggg)≤2時，則為多余輪廓分支，不進行該連通域內(nèi)輪廓路徑的創(chuàng)建；③當存在度大于2的節(jié)點時，即D(Ggg) ≥2，則轉(zhuǎn)步驟4。

步驟4利用雙連通子圖Ggg= (Vgg，Egg)的節(jié)點集Vgg的節(jié)點坐標計算凸包，凸包按逆時針方向排序，然后在凸包邊界邊上找到屬于雙連通子圖Ggg邊集Egg的一條邊，并將其作為切片輪廓路徑的起始邊s1s2(起始邊的第1個節(jié)點為s1，第2個節(jié)點為s2)，在子圖Ggg中搜索與s2關(guān)聯(lián)且未被使用的鄰接點作為下一個路徑點s3，若當前節(jié)點有多個鄰接點，為使沿逆時針路徑方向物體內(nèi)部區(qū)域始終在路徑的左邊，應(yīng)選擇最右拐的節(jié)點作為下一個路徑點，依次遍歷求出路徑點，直到回到起點s1，則完成一條有序切片輪廓路徑P的創(chuàng)建，同時記錄路徑P中的割點SP。

步驟5提取剩余節(jié)點Vgg-P+SP，組成新圖Ggg后，轉(zhuǎn)步驟3，以完成剩余輪廓路徑的創(chuàng)建。

以圖13所示為例，說明本文方法對自交切片輪廓進行路徑規(guī)劃的過程。由于該連通圖中存在節(jié)點度大于2的節(jié)點，首先對該連通圖進行雙連通分解，得到5個雙連通子圖。其中，前4個雙連通子圖中節(jié)點度都為2，利用深度優(yōu)先遍歷即可構(gòu)建有序封閉輪廓路徑；第5個雙連通子圖中存在節(jié)點度大于2的點，因此首先計算凸包，然后從凸包上找到屬于該雙連通子圖邊集上的一條邊作為起始邊s，從起始邊s開始逆時針跟蹤最右拐的點，構(gòu)建一條封閉輪廓路徑后，再對剩余節(jié)點進行路徑搜索，從而得到所有的有序輪廓。

3 實驗

為驗證本文算法的有效性，以不同類型的STL模型為例, 進行分層切片測試。在Windows 10環(huán)境下利用MATLAB開發(fā)基于本文算法的分層切片程序，實驗在2.4 GHz的CPU、8 GB內(nèi)存的PC機上運行。

實驗1如圖14和圖15所示為帶有復(fù)雜孔洞結(jié)構(gòu)的流形網(wǎng)格模型進行分層切片的效果圖。利用這些模型進行實驗?zāi)軌虮憩F(xiàn)算法處理復(fù)雜嵌套輪廓的能力。如圖14a所示為一個具有1 194 952個三角片的鏤空燈罩模型，為顯示清晰，圖14b所示為層厚2 mm的切片效果，該模型在頂層具有28個輪廓環(huán)，其所構(gòu)成的連通域如圖14c所示。圖15a所示為一個具有96 364個三角片的扇子模型，圖15b所示為層厚1 mm的切片效果，該模型的每一層切片上具有474個輪廓環(huán)，其所構(gòu)成的連通域如圖15c所示?？梢钥闯觯疚姆椒▽哂袕?fù)雜孔洞結(jié)構(gòu)的模型均能夠產(chǎn)生正確的切片結(jié)果。

利用本文方法和著名的Cura切片軟件對這兩種模型在不同切片厚度下的切片效率進行對比，結(jié)果如表2所示。對于第1個燈罩模型，在同樣的切片厚度參數(shù)下，本文方法比Cura軟件在耗時方面節(jié)省了近6%。對于第2個扇子模型，本文方法比Cura軟件在耗時方面節(jié)省了近80%，這主要是因為燈罩模型中每層切片最多的只有28個輪廓環(huán)，而扇子模型的每層切片包含474個輪廓環(huán)，所以當處理大型嵌套輪廓時，本文方法比Cura軟件更高效。

本文方法對于這兩種模型在不同層厚下，各層切片從相交邊提取到輪廓路徑規(guī)劃的執(zhí)行時間如圖16和圖17所示?？梢钥闯觯瑢τ跓粽帜Ｐ?圖16)，各層切片耗時大部分集中在0.02 s～0.03 s內(nèi)，靠近頂層的三角片較多，但耗時也都在0.05 s以內(nèi)。

表2 本文方法與Cura軟件切片耗時對比

對于扇子模型(圖17)，由于該模型各層切片的輪廓個數(shù)一樣，即使具有474個輪廓環(huán)，各層切片耗時也都只有0.17 s左右。各層耗時加起來遠遠低于Cura軟件的處理時間，可以看出，本文基于圖論的路徑規(guī)劃技術(shù)，無需復(fù)雜耗時的拓撲關(guān)系重建，因此對于處理大量嵌套輪廓的拓撲排序具有顯著的效率優(yōu)勢。

實驗2利用本文方法和著名切片軟件Cura軟件、Simplify3D軟件對非封閉模型進行切片測試。如圖18a所示為米老鼠頭的STL模型，該模型為帶有邊界的非封閉網(wǎng)格模型，三角片總數(shù)為65 019，X、Y、Z方向總體尺寸分別為77 mm、24 mm、69 mm。由圖18b可以看出，Cura軟件無法處理非封閉模型，因此不能產(chǎn)生非封閉的切片輪廓線。而Simplify3D軟件將模型強行封閉后再進行切片計算，因此每層切片輪廓都是封閉的，如圖18c所示，顯然，這種方法將會導(dǎo)致錯誤的打印結(jié)果，同時也會浪費較多的打印材料和時間。如圖18d所示為本文方法在切片測試精度為1 mm下生成的切片效果圖，可以看出，無論是在米老鼠臉部的單連通區(qū)域還是兩個耳朵處的多連通區(qū)域，均能產(chǎn)生正確的非封閉輪廓線。這是由于本文方法將相交邊當做節(jié)點，將三角片與切平面的相交關(guān)系映射為圖，利用圖的節(jié)點度特性找到了非封閉模型輪廓的邊界起點位置，從而有效解決了開環(huán)輪廓的排序錯亂問題，將這些開環(huán)切片輪廓線偏置一定的厚度，即可得到正確的打印填充區(qū)域。

實驗3利用本文方法與Simplify3D軟件、Cura軟件對非流形網(wǎng)格模型(如圖19a)進行切片測試。測試的3種模型在不同程度上都具有一些非流形三角片，由圖19b和圖19c所示的切片結(jié)果可以看出，Simplify3D軟件和Cura軟件會在非流形邊附近產(chǎn)生輪廓斷裂現(xiàn)象，而本文方法能夠產(chǎn)生如圖19d所示的正確的切片連通域。這是由于這些非流形網(wǎng)格的非流形邊被兩個以上的三角片所共享，因此若用傳統(tǒng)方法進行輪廓排序，在非流形邊處由于無法分辨正確的鄰接三角片，從而造成輪廓排序錯誤。本文方法將三角片與切平面的相交關(guān)系映射為圖后，利用圖的節(jié)點度特性分析出非流形邊(即圖的割點)的位置所在，并利用雙聯(lián)通分解法將這種復(fù)雜自交圖轉(zhuǎn)化為簡單連通圖，有效解決了自交輪廓排序混亂問題，獲得了正確的有序切片輪廓。

4 結(jié)束語

本文針對流形和非流形網(wǎng)格模型，提出了一種基于節(jié)點度的高效切片方法。該方法通過數(shù)據(jù)預(yù)處理、相交邊提取、無向圖構(gòu)建、輪廓路徑規(guī)劃等步驟，快速而準確地構(gòu)建出模型的各層有序切片輪廓。實驗分析結(jié)果表明，本文方法在處理大型嵌套的切片輪廓具有較高的效率，而且能夠解決非流形模型切片輪廓存在的非封閉和自交問題。

與現(xiàn)有方法相比，本文方法主要優(yōu)點在于：① 通過判斷三角片頂點與切平面的相對位置，將相交邊映射為無向圖，利用基于圖論的強大路徑規(guī)劃技術(shù)進行拓撲排序，不僅避免公共邊交點的重復(fù)計算，還無需耗時而復(fù)雜的網(wǎng)格拓撲關(guān)系重建，從而提高分層處理效率；② 利用圖的節(jié)點度特性智能判斷輪廓的封閉性和自交性，無需進行額外的網(wǎng)格非流形邊的判斷；③針對切片輪廓產(chǎn)生的自交問題，提出雙連通分解法，將復(fù)雜自交圖轉(zhuǎn)化為簡單連通圖，從而能夠有效去除多余輪廓分支，解決輪廓排序混亂問題。本文方法目前只針對正則的流形和非流形網(wǎng)格模型，對于非正則網(wǎng)格模型的切片方法將是未來研究的重點。