一種避免輪廓相交的STL模型快速切片方法*

吳 建 吳 婷 陳廷豪 潘成鋼

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

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

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

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

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

1 本文方法

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

1.1 建立相交三角片集合

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

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

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

(1)當zmin

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

(3)當zmid=zmax=hi，且zmin

1.2 構(gòu)建無向圖

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

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

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

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

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

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

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

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

1.3 排序輪廓線

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

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

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

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

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

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

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

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

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

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

例如，圖4a所示的連通圖Gi=(Vi,Ei)，其節(jié)點集合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é)點集合Vi進行三角剖分得到三角網(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，此時新的三角網(wǎng)格DT的邊界集合Boundary完全屬于圖Gi中的邊集Ei，如圖4d所示，依次連接邊界節(jié)點，得到有序封閉輪廓為1→2→3→4→5→9→8→7→1。

2 實例驗證

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

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

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

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

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

3 結(jié)語

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