吳 建 吳 婷 陳廷豪 潘成鋼

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

隨著計(jì)算機(jī)圖形學(xué)的發(fā)展，用于描述三角網(wǎng)格模型的 STL(stereolithography) 文件己成為 CAD/CAM 系統(tǒng)的一類標(biāo)準(zhǔn)接口文件格式。STL文件不僅占用儲(chǔ)存空間少，而且可以滿足模型信息在不同軟件系統(tǒng)之間高效、及時(shí)傳輸?shù)男枨骩1]。在對(duì)STL文件模型進(jìn)行3D打印或數(shù)控加工時(shí)，分層切片處理是其中較為關(guān)鍵的一步，它是通過層切平面與3D模型相交，得到各層截面輪廓信息，因此切片處理的效率和準(zhǔn)確性直接影響到模型制作的精度和質(zhì)量[2]。

由于STL模型表面分布著大量無(wú)序的三角片，因此進(jìn)行分層切片時(shí)，需要確定三角片之間的鄰接關(guān)系，才能將切平面與三角片的交點(diǎn)連接成有序的封閉輪廓。目前，應(yīng)用較為廣泛的STL模型切片算法大致分為兩大類：(1)基于交點(diǎn)信息的切片方法。這種方法首先計(jì)算切平面與每個(gè)三角片的交點(diǎn)，然后對(duì)這些交點(diǎn)進(jìn)行排序以構(gòu)建成首尾封閉的有序輪廓[3-4]。田仁強(qiáng)等[5]利用二分查找法進(jìn)行三角片的快速分組，然后求出三角片與切平面的相交線段后，根據(jù)各相交線段端點(diǎn)間的冗余信息利用深度優(yōu)先搜索算法對(duì)相交線段優(yōu)化以創(chuàng)建有序封閉輪廓。Minetto R等[6]將三角片與切平面交點(diǎn)之間的鄰接關(guān)系創(chuàng)建成哈希表，根據(jù)哈希表中存貯的鄰接索引依次追蹤交點(diǎn)以構(gòu)建成有序輪廓路徑，該方法能夠避免三角片公共邊交點(diǎn)的重復(fù)計(jì)算，也無(wú)需復(fù)雜的網(wǎng)格拓?fù)潢P(guān)系重建，能夠有效提高分層切片處理效率。(2)基于三角片拓?fù)湫畔⒌那衅椒?。這種方法需要建立相鄰三角片之間的拓?fù)潢P(guān)系，利用拓?fù)湫畔⒄业脚c其相鄰的下一個(gè)三角片，依次遍歷后即可構(gòu)成有序的相交三角片集合。這種方法的優(yōu)點(diǎn)是可直接獲得首尾連接的有向封閉輪廓, 無(wú)需對(duì)交點(diǎn)進(jìn)行重新排序，但缺點(diǎn)在于建立鄰接拓?fù)湫畔⒌臄?shù)據(jù)結(jié)構(gòu)較為費(fèi)時(shí)[7]。王素等[8]將三角片間的鄰接關(guān)系構(gòu)建成鏈表，鏈表的節(jié)點(diǎn)為交點(diǎn)、前驅(qū)指針、后繼指針構(gòu)成的結(jié)構(gòu)體，利用鏈表數(shù)據(jù)結(jié)構(gòu)依次搜索和插入相鄰三角片并求出的交點(diǎn)從而形成首尾封閉的輪廓線。Zhang Z等[9]根據(jù)每個(gè)三角片的法矢方向確定切平面與三角片交線段的走向，從而確定相交三角片公共邊的索引鏈表，然后按照鏈表順序依次進(jìn)行求交得到有序輪廓路徑。徐明月等[10]采用Map容器建立相交邊的唯一索引和鄰接關(guān)系，并按規(guī)定的正方向存儲(chǔ)交點(diǎn)從而形成最終切片輪廓。徐敬華等[11]利用半邊數(shù)據(jù)結(jié)構(gòu)[12]重構(gòu)各層相交面片的鄰接拓?fù)潢P(guān)系，并通過哈希表獲得有序的網(wǎng)格面片環(huán)，最后按順序求出面片環(huán)中各個(gè)三角片與切平面的交點(diǎn)獲得有序輪廓。

上述兩類切片處理方法都是將交點(diǎn)或三角片依次排序成一條有向封閉環(huán)來(lái)獲得最終輪廓的，但是當(dāng)某一層切片存在開環(huán)輪廓或多條輪廓相交等情況時(shí)，算法有可能產(chǎn)生錯(cuò)誤的結(jié)果。對(duì)于流行網(wǎng)格模型來(lái)說，產(chǎn)生這種問題的主要原因是：模型表面的一些點(diǎn)、邊、面與切平面重合，從而導(dǎo)致求交后出現(xiàn)孤立點(diǎn)、懸邊和相交邊等奇異問題。目前，常用的解決方法是采用Kim h J等人[13]的頂點(diǎn)轉(zhuǎn)移法，該方法首先判斷每個(gè)三角片的點(diǎn)、邊、面與切平面是否重合，若重合則進(jìn)一步確定這些點(diǎn)、邊、面是局部最大還是局部最小，然后將它們沿層切方向向上或向下平移微小距離來(lái)解決奇異問題，但是這種改變模型頂點(diǎn)位置的方法有可能因?yàn)橛?jì)算精度誤差產(chǎn)生錯(cuò)誤。因此，改善分層切片算法的有效性和準(zhǔn)確性，對(duì)于提高快速成型系統(tǒng)的可靠性和制作精度具有重要意義。

針對(duì)上述問題，本文提出一種避免輪廓相交的STL模型切片處理方法，該方法將切平面與模型產(chǎn)生的交點(diǎn)映射成圖，利用圖論和Delaunay三角剖分相結(jié)合的方法來(lái)構(gòu)建有序輪廓，以解決切片輪廓相交等問題。

1 本文方法

本文提出的切片處理方法主要包括以下幾個(gè)部分：(1)建立與各層切平面相交的三角片集合。(2)計(jì)算相交三角片集合中每個(gè)三角片與切平面的交點(diǎn)，然后將交點(diǎn)當(dāng)作節(jié)點(diǎn)，交點(diǎn)之間的連接關(guān)系當(dāng)作邊，將它們映射為無(wú)向加權(quán)圖。(3)根據(jù)圖中的節(jié)點(diǎn)連通特性，對(duì)節(jié)點(diǎn)排序以形成有序輪廓，并結(jié)合Delaunay三角剖分方法對(duì)相交輪廓進(jìn)行修復(fù)。

1.1 建立相交三角片集合

STL模型表面上具有大量散亂的三角片，為了快速計(jì)算出各層切平面與模型的交線，避免不必要的計(jì)算，應(yīng)分析出哪些三角片會(huì)與切平面相交，建立與切平面相交的有效三角片集合。

假設(shè)STL模型沿z軸方向進(jìn)行分層制造，共分為n層，各層切平面的高度為hi，i=1, 2, …,n。對(duì)于每一層切平面， 三角片與切平面的相交位置關(guān)系可以分為如圖1所示的6種情況。為避免多個(gè)三角片產(chǎn)生的交點(diǎn)重復(fù)，應(yīng)排除三角片與切平面只有1個(gè)交點(diǎn)(圖1d、1e)以及三角片與切平面重合(圖1f)的情況，即只有在圖1a～1c所示的3種情況下，三角片與切平面有2個(gè)交點(diǎn)，從而形成有效交線段。

根據(jù)上述分析，在讀取模型三角片數(shù)據(jù)后，計(jì)算每個(gè)三角片的3個(gè)頂點(diǎn)z坐標(biāo)的最小值z(mì)min、中間值z(mì)mid和最大值z(mì)max，并將所有三角片按最小值z(mì)min從低到高進(jìn)行排序，以加快搜索速度。然后，從第1層切片開始，逐層按照如下條件提取出與切平面hi(i=1, 2, …,n)相交的三角片集合：

(1)當(dāng)zmin

(2)當(dāng)zmid=zmin=hi，且zmax>hi，該三角片的下面一條邊與切平面hi重合，形成的2個(gè)交點(diǎn)分別為該邊的2個(gè)端點(diǎn)，如圖1b所示。

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

1.2 構(gòu)建無(wú)向圖

在建立的每一層相交三角片集合里，每個(gè)三角片與切平面形成2個(gè)交點(diǎn)，交點(diǎn)之間形成交線段。如圖2所示，切平面與三角片T1形成交線段v1v2，與三角片T2形成v3v4。為將這些線段按照某種順序連接成首尾封閉的有序輪廓，可以利用基于圖論的排序方法。圖論是應(yīng)用數(shù)學(xué)的一個(gè)分支，它是將復(fù)雜網(wǎng)絡(luò)抽象為簡(jiǎn)單幾何圖形的一種通用建模方式[14-15]，在圖像處理、路徑規(guī)劃和工業(yè)生產(chǎn)優(yōu)化等方面有著廣泛的應(yīng)用。其主要思想是將待研究對(duì)象中的每個(gè)元素映射為圖的節(jié)點(diǎn)，元素間的連接關(guān)系映射為圖的邊，邊的權(quán)值代表元素之間的重要性。將研究對(duì)象映射為圖后，就可以利用基于圖論的方法解決節(jié)點(diǎn)之間的拓?fù)渑判騿栴}，具體步驟如下：

(1) 計(jì)算該層相交三角片集合{T1,T2, …,Tm-1,Tm}中每個(gè)三角片與切平面的交點(diǎn)，得到集合：

(2)對(duì)集合V0中的交點(diǎn)進(jìn)行重復(fù)性判斷，建立不含重復(fù)點(diǎn)的節(jié)點(diǎn)集合V={vi|vi≠vj(i≠j)}，并將集合V中每個(gè)點(diǎn)的索引號(hào)映射回集合V0，求得索引向量Id，使V0=V(Id)。

(3)由于V0中每2個(gè)連續(xù)交點(diǎn)形成交線段，因此建立V中節(jié)點(diǎn)之間的邊集E為：

E= {, , …, }，邊的權(quán)值按如下規(guī)則進(jìn)行定義：

其中，wij代表節(jié)點(diǎn)vi,vj連成的邊 的權(quán)值。

(4)利用節(jié)點(diǎn)集合V和邊集E，構(gòu)建圖G= (V,E)。

以圖2所示情況為例，該切平面與模型共有3個(gè)三角片相交，通過求交后可得到交點(diǎn)集合V0= {v1,v2,v3,v4,v5,v6}(圖2a)。經(jīng)過重復(fù)性判斷，可知v2=v3,v4=v6,v5=v1，去除重復(fù)點(diǎn)后得到節(jié)點(diǎn)集合V= {v1,v2,v4}，將集合V中的這3個(gè)節(jié)點(diǎn)映射回集合V0，可得索引向量Id=[1, 2, 2, 3, 1, 3]，使V0=V(Id)；根據(jù)V0中每2個(gè)連續(xù)交點(diǎn)形成交線段的關(guān)系，得到邊集E= {, , }，即E= {, , }。利用V和E構(gòu)建圖G= (V,E)，如圖2b所示。

1.3 排序輪廓線

將三角片與切平面形成的交點(diǎn)映射成圖后，為將這些交點(diǎn)連接成有序的輪廓線，需要對(duì)它們進(jìn)行排序。由于每層切片有時(shí)會(huì)出現(xiàn)多條輪廓，多條輪廓之間又有可能出現(xiàn)輪廓相交等奇異問題。因此，本文首先利用基于圖論的深度優(yōu)先算法對(duì)交點(diǎn)進(jìn)行排序，然后結(jié)合三角剖分方法對(duì)相交輪廓進(jìn)行修復(fù)。

對(duì)于任意一層切片構(gòu)建的交點(diǎn)無(wú)向圖G，建立切片輪廓線的基本過程為：首先將圖G進(jìn)行連通分解，得到圖G的連通分量Gi，i=1, 2, …,n；n為連通分量總數(shù)。對(duì)每個(gè)連通分量中的節(jié)點(diǎn)利用深度優(yōu)先算法進(jìn)行排序，即從圖Gi中的某一節(jié)點(diǎn)v1出發(fā)，搜索與它相鄰且未被遍歷過的節(jié)點(diǎn)v2，然后從節(jié)點(diǎn)v2出發(fā)，搜索與v2相鄰且未被遍歷過的節(jié)點(diǎn)v3，當(dāng)循環(huán)搜索后回到起點(diǎn)v1，即創(chuàng)建一條有序封閉輪廓v1→v2→v3→v4→v5→v1，如圖3所示。

在深度優(yōu)先的排序過程中，每個(gè)節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù)可能分為以下3種情況：

(1)當(dāng)連通子圖內(nèi)每個(gè)節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù)都為2時(shí)，輪廓為簡(jiǎn)單封閉環(huán)，如圖3所示。

(2)當(dāng)連通子圖內(nèi)某個(gè)節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù)為1時(shí)，輪廓為簡(jiǎn)單開環(huán)，此時(shí)需要以該節(jié)點(diǎn)作為起始點(diǎn)重新利用深度優(yōu)先算法排序。

(3)當(dāng)連通子圖內(nèi)某個(gè)節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù)大于2時(shí)，該連通子圖內(nèi)的多條輪廓相交。例如圖4a所示的連通圖中，節(jié)點(diǎn)8和9所鄰接的節(jié)點(diǎn)個(gè)數(shù)大于2，其余節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù)都等于2。由于3D打印只會(huì)在輪廓封閉區(qū)域的內(nèi)部進(jìn)行材料填充，因此，對(duì)于此種類型的節(jié)點(diǎn)拓?fù)渑判?，只需找到該連通圖的外邊界節(jié)點(diǎn)，而對(duì)于內(nèi)部的多余輪廓分支可予以剔除。因此本文結(jié)合三角剖分方法創(chuàng)建有序封閉輪廓，具體步驟為：

Step1，將連通子圖內(nèi)Gi的所有節(jié)點(diǎn)利用基于約束的Delaunay三角剖分方法[16-17]構(gòu)建一個(gè)三角網(wǎng)格DT。

Step2，構(gòu)建三角網(wǎng)格DT的邊界集合Boundary。邊界集合中的邊按照如下規(guī)則定義：Boundary= { |Dep=1}，其中代表三角網(wǎng)格DT中由節(jié)點(diǎn)vi、vj構(gòu)成的邊，Dep為依附于邊的三角形的個(gè)數(shù)，當(dāng)Dep=1時(shí)， 為邊界邊，vi、vj為邊界節(jié)點(diǎn)。

Step3，判斷邊界集合Boundary中的每一條邊界邊是否屬于連通子圖Gi的邊集Ei，①若存在 ?Ei，將與該邊相連的三角形刪除，更新三角網(wǎng)格DT后，轉(zhuǎn)Step2；②若不存在 ?Ei，直接轉(zhuǎn)Step4。

Step4，依次連接三角網(wǎng)格DT的邊界節(jié)點(diǎn)即為連通子圖Gi內(nèi)的有序封閉輪廓。

例如，圖4a所示的連通圖Gi=(Vi,Ei)，其節(jié)點(diǎn)集合Vi={1,2,…,9}, 邊集Ei= {<1, 2>, <2, 3>, <3, 4>, <4, 5>, <5, 9>, <9, 8>, <9, 6>,<6, 8>,<8, 7>,<7, 1>}。首先將節(jié)點(diǎn)集合Vi進(jìn)行三角剖分得到三角網(wǎng)格DT，如圖4b所示，然后構(gòu)建網(wǎng)格DT的邊界集合Boundary= {<1, 2>, <2, 3>, <3, 4>, <4, 5>, <5, 7>, <7, 1>}，由于集合Boundary中的邊界邊<5, 7> ?Ei，因此將與邊<5, 7>相連的三角形△578刪除，得到新的三角網(wǎng)格DT，如圖4c所示，獲取新的邊界集合Boundary后，發(fā)現(xiàn)邊界邊<5, 8>?Ei，因此刪除與<5, 8>相連的△589，此時(shí)新的三角網(wǎng)格DT的邊界集合Boundary完全屬于圖Gi中的邊集Ei，如圖4d所示，依次連接邊界節(jié)點(diǎn)，得到有序封閉輪廓為1→2→3→4→5→9→8→7→1。

2 實(shí)例驗(yàn)證

采用 Matlab 軟件平臺(tái)，在 Windows 10環(huán)境下開發(fā)本文方法的分層切片程序, 并以不同 STL模型為實(shí)例，利用本文方法與傳統(tǒng)方法以及商業(yè)軟件進(jìn)行局部切片測(cè)試對(duì)比, 以充分展示本文方法的有效性。實(shí)驗(yàn)在2.4 GHz的CPU、8 GB內(nèi)存的PC機(jī)上運(yùn)行。

測(cè)試模型選取如圖5所示的曲柄和圖6所示的差速器STL模型，這兩個(gè)實(shí)例模型為流行網(wǎng)格模型，且模型表面都存在和切平面方向平行的三角片，在這些位置進(jìn)行切片，能夠很好地顯示算法是否有處理輪廓相交問題的能力。圖5a所示的曲柄STL模型，三角片總數(shù)為10 758， 模型沿X、Y、Z方向的總長(zhǎng)、總寬和總高分別為 84.64 mm、33 mm、15 mm。在切平面P內(nèi)，產(chǎn)生了如圖5b所示的交點(diǎn)。這些交點(diǎn)若采用傳統(tǒng)方法，如文獻(xiàn)[5]和[8]等，無(wú)論選擇哪個(gè)點(diǎn)作為起始點(diǎn)，都無(wú)法形成一個(gè)完整的封閉輪廓，會(huì)產(chǎn)生如圖5c所示的輪廓路徑錯(cuò)亂。本文方法首先將切片P內(nèi)的交點(diǎn)集合映射為圖，并利用Delaunay三角剖分方法構(gòu)建如圖5d 所示的三角網(wǎng)格。然后利用圖的邊集對(duì)剖分網(wǎng)格進(jìn)行裁剪，得到最終的三角網(wǎng)格如圖5e所示，順序連接網(wǎng)格的邊界點(diǎn)得到正確的有序封閉輪廓，其結(jié)果如圖5f所示。圖6a為某汽車差速器STL模型，該模型三角片總數(shù)為50 530，模型沿X、Y、Z方向的總長(zhǎng)、總寬和總高分別為 200 mm、200 mm、153 mm。在該模型的高度為92 mm(切片1)、24 mm(切片2)、17 mm(切片3)處，產(chǎn)生的交點(diǎn)圖6b所示，采用傳統(tǒng)算法同樣產(chǎn)生如圖6c所示的輪廓路徑混亂，無(wú)法構(gòu)成有效封閉區(qū)域，而利用本文方法能夠去除多去分支，獲得如圖6d所示的封閉輪廓。

從以上兩個(gè)實(shí)例的切片測(cè)試結(jié)果可以發(fā)現(xiàn)，當(dāng)切平面與流行網(wǎng)格模型表面的某些三角片共面時(shí)，容易出現(xiàn)輪廓奇異問題。由于傳統(tǒng)切片算法是將交點(diǎn)/三角片依次排序成一條有向封閉環(huán)來(lái)獲得輪廓，因此當(dāng)多條輪廓相交時(shí)，在共同相交處由于無(wú)法判斷分支走向，會(huì)造成排序輪廓出現(xiàn)繞行。本文結(jié)合連通圖和三角剖分的方法，利用Delaunay三角剖分構(gòu)建封閉區(qū)域，利用無(wú)向圖的邊集對(duì)剖分網(wǎng)格進(jìn)行裁剪，以去除多余輪廓分支，從而避免了排序混亂，也避免了頂點(diǎn)轉(zhuǎn)移法[13]帶來(lái)的精度損失。

為進(jìn)一步顯示本文方法的運(yùn)行效率，利用本文方法和著名開源切片軟件Cura對(duì)上述3種模型進(jìn)行切片耗時(shí)對(duì)比，其結(jié)果如表1所示。可以看出，本文基于圖論的深度優(yōu)先技術(shù)，無(wú)需復(fù)雜耗時(shí)的拓?fù)潢P(guān)系重建，因此算法運(yùn)行效率比Cura軟件提高了接近50%左右，具有顯著的效率優(yōu)勢(shì)。

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

3 結(jié)語(yǔ)

本文針對(duì)STL三角網(wǎng)格模型，提出了一種避免輪廓相交的切片處理方法。該方法通過相交三角片集合提取、交點(diǎn)圖構(gòu)建和輪廓線排序等步驟，有效構(gòu)建出模型的各層切片輪廓。實(shí)例測(cè)試結(jié)果表明，本文方法不僅能夠準(zhǔn)確獲取簡(jiǎn)單封閉切片輪廓，而且能夠處理切片輪廓相交的情況。與現(xiàn)有方法相比，本文方法主要優(yōu)點(diǎn)在于：(1) 將交點(diǎn)映射成圖，利用基于圖論的強(qiáng)大搜索技術(shù)進(jìn)行拓?fù)渑判虻姆椒ū苊饬撕臅r(shí)而復(fù)雜的網(wǎng)格拓?fù)潢P(guān)系重建。(2) 對(duì)于簡(jiǎn)單封閉輪廓，采用基于圖的深度優(yōu)先搜算策略，算法時(shí)間復(fù)雜度僅為O(n),n為節(jié)點(diǎn)數(shù)目，從而極大提高了交點(diǎn)排序效率。(3)對(duì)于復(fù)雜輪廓，采用基于圖和三角剖分相結(jié)合的方法，利用圖的邊集對(duì)剖分網(wǎng)格進(jìn)行裁剪，能夠有效去除多余輪廓分支，從而解決輪廓相交問題。