面向流形和非流形網(wǎng)格模型的高效切片方法

吳 婷，張禮兵

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

2 本文方法

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

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

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

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

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

2.2 相交邊提取

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

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

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

(1)當(dāng)zmin

當(dāng)hi

相交邊對：[，]；

當(dāng)hi=zmed，

相交邊對：[，]；

當(dāng)hi>zmed，

相交邊對：[，]。

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

相交邊對：[，]。

(3)當(dāng)zmed=zmax=hi且zmin

相交邊對：[，]。

(4)其他。

無相交邊。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 輪廓路徑規(guī)劃

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

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

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

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

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

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

具體步驟如下：

步驟1計(jì)算連通圖Gg中每個(gè)節(jié)點(diǎn)對應(yīng)的相交邊與切平面的交點(diǎn)，將交點(diǎn)坐標(biāo)作為圖中的節(jié)點(diǎn)坐標(biāo)。

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

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

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

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

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

3 實(shí)驗(yàn)

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

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

利用本文方法和著名的Cura切片軟件對這兩種模型在不同切片厚度下的切片效率進(jìn)行對比，結(jié)果如表2所示。對于第1個(gè)燈罩模型，在同樣的切片厚度參數(shù)下，本文方法比Cura軟件在耗時(shí)方面節(jié)省了近6%。對于第2個(gè)扇子模型，本文方法比Cura軟件在耗時(shí)方面節(jié)省了近80%，這主要是因?yàn)闊粽帜Ｐ椭忻繉忧衅疃嗟闹挥?8個(gè)輪廓環(huán)，而扇子模型的每層切片包含474個(gè)輪廓環(huán)，所以當(dāng)處理大型嵌套輪廓時(shí)，本文方法比Cura軟件更高效。

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

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

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

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

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

4 結(jié)束語

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

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