3D打印中一種快速分層處理算法的研究

劉大偉，王蘇洲

(1.南京工程學(xué)院 自動化學(xué)院 ，南京 211167；2.南京工業(yè)大學(xué) 電氣工程與控制科學(xué)學(xué)院 ，南京 211816)

3D打印中一種快速分層處理算法的研究

劉大偉1，王蘇洲2

(1.南京工程學(xué)院 自動化學(xué)院 ，南京 211167；2.南京工業(yè)大學(xué) 電氣工程與控制科學(xué)學(xué)院 ，南京 211816)

通過對3D打印中STL數(shù)據(jù)模型分層規(guī)則的分析建立有向加權(quán)圖數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)在找到鄰接三角形的同時也記錄了其權(quán)值信息，運用圖的深度優(yōu)先遍歷法，建立遞歸搜索函數(shù)，針對遞歸切片中出現(xiàn)的三角形“點切”問題，提出了一種基于STL模型的快速分層算法即分組排序的有向加權(quán)遞歸算法。此算法通過對三角形面片分組排序后，進行有向加權(quán)圖遞歸搜素，獲得三角形面片之間有序排列的交點，在OpenGL環(huán)境中實現(xiàn)了截面輪廓的自動生成，根據(jù)每個輪廓環(huán)切割的第一個三角形面片數(shù)據(jù)，確定截面輪廓的走向。實驗結(jié)果證明該算法可以減少面片之間建立拓撲關(guān)系的時間，實現(xiàn)簡單，穩(wěn)定可靠。

3D打??；分層算法；STL模型

0 引言

3D打印采用分層制造原理，以STL模型作為3D打印的文件格式，但它無法直接作為3D打印的輸入數(shù)據(jù)，必須通過分層軟件對輸入數(shù)據(jù)進行處理?；赟TL分層算法的關(guān)鍵步驟是在獲取輪廓時，先判斷三角面片和切平面的位置關(guān)系，若相交則求交。這種求交過程中，要遍歷所有三角形面片，而大部分三角形面片與切平面不相交，查找過程比較費時。并且每條邊都要求交兩次，交線排序過程也比較費時。為了提高分層效率，研究者對STL模型數(shù)據(jù)先進行預(yù)處理，其中主要分層算法有兩類。

一是基于STL模型幾何特征分類的算法。此算法對STL文件的三角形直接進行分級分類，然后進行求交計算，但必須整理截面輪廓信息形成封閉的有向線段。利用三角面片存在的特點：在Z方向上如果三角面片越長，那么與其相交的切平面將會越多；三角面片在Z方向的最低點越是最低，與切平面相交將越快。但這種方法對三角面片類的劃分指標(biāo)是模糊值，因此難以完全杜絕位置關(guān)系的無效判斷。

二是基于STL模型拓撲結(jié)構(gòu)信息的分層算法。三角形面片在STL模型中毫無順序，這一算法首先建立三角形面片的幾何拓撲數(shù)據(jù)，在拓撲信息的基礎(chǔ)上進行分層處理。如果沒有建立拓撲信息，搜索三角形面片比較費時，但是建立拓撲信息后，能夠搜索到構(gòu)成該三角形面片的三個頂點和三條邊，通過邊的信息還可以搜索到鄰接三角形面片。此方法算法在三角形面片和切平面求交時，每個三角形面片只對一條邊求交，可以直接得到有向封閉輪廓，但是建立拓撲數(shù)據(jù)過程費時，且占用內(nèi)存較大。

本文在充分研究上述分層算法特點的基礎(chǔ)上，吸取各自優(yōu)點，提出了基于分組排序的有向加權(quán)圖遞歸分層算法。首先對所有三角形面片分組排序，把排序之后三角形面片建立分層關(guān)系矩陣，再對活性三角形面片分別進行有向加權(quán)圖遞歸搜素，并求交點，最終生成截面輪廓數(shù)據(jù)。該算法可以減少面片之間建立拓撲關(guān)系的時間，實現(xiàn)簡單，穩(wěn)定可靠。

1 分層算法原理

1.1 分組排序

分組排序可以減少判斷三角形面片與切平面位置關(guān)系的次數(shù)，假設(shè)切平面為n個，那么所有的三角形面片可以被分成n組。根據(jù)分層方向上三角形面片3個頂點中的坐標(biāo)最小值來決定該片初次在分層中出現(xiàn)的層號。依據(jù)矩陣關(guān)系遍歷模型中全部的三角形面片，將與相同切平面相交的三角形面片放在同一組中，每層重新生成以層號為索引的相交面片集合表[4]。

如圖2所示Fi表示一個新的與第i個切平面相交三角形面片的集合，即Fi=(fi1，fi2…fij…fim),與當(dāng)前切平面相交的三角形面片組成的集合稱為活性三角面片表，可以提高分層效率。

圖2 分層關(guān)系矩陣的結(jié)構(gòu)

1.2 有向加權(quán)圖遞歸算法原理

假設(shè)V是非空有限頂點的集合，集合內(nèi)的元素表示頂點。假設(shè)E也是非空有限邊的集合，集合內(nèi)的元素分別于V(V中的元素一一對應(yīng)，則稱G=(V，G)組成一個圖，E內(nèi)的每個元素為圖的一條邊。如果E中一條邊的兩個頂點出現(xiàn)的順序不重要的時候則稱圖G為無向圖；如果E中一條邊的兩個頂點出現(xiàn)的順序不能顛倒時，則稱圖G為有向圖，圖內(nèi)的邊成為有向邊。

2 分層算法的實現(xiàn)

2.1 分組排序的建立

設(shè)STL模型起始的分層高度為H[1],面片在Z軸上的最大值為Hmax，最小值為Hmin，厚度為△H。介于i和j兩者之間的切平面的序號即與這個面片相交，i和j的值為：

(1)

(2)

由公式(1)和公式(2)可以判斷三角面片位于哪個分層，同時形成三角面片與分層面片序列號的對應(yīng)關(guān)系，產(chǎn)生兩者之間的分層關(guān)系矩陣。當(dāng)Hmax=Hmin時，表示三角形面片與分層平面相互平行，這些的面片將不需要加入到分層矩陣關(guān)系矩陣中。

2.2 有向加權(quán)圖的建立

根據(jù)上文所述的算法原理與圖論知識，建立一種能夠詳細對STL模型毗鄰關(guān)系進行描述的有向加權(quán)圖數(shù)據(jù)結(jié)構(gòu)。

定義：設(shè)STL模型的有向加權(quán)圖C=(V,A,W)使一個有序的三元組，Q為邊的權(quán)值，V，A，W，Q代表的含義如下[5]：

(1)V={V0,V1…Vn}，V內(nèi)的元素表示圖D所有頂點的集合。

(2)A={AVj}={Ai,j}，A代表三角形面片之間的鄰接關(guān)系，即圖D邊的信息，是V內(nèi)不同元素的有序?qū)Φ募?。其中i≠j。

(3)W={W}={Wi,j,k}，i，j，k是三個互不相等的值，代表不同鄰接的三角形面片。

(4)Q={QVj}={Qi,j}，代表面片邊的權(quán)值，其中i≠j。

如圖3所示，假設(shè)三角形面片的三條邊的權(quán)值互相等，設(shè)定共享相應(yīng)邊的鄰接面片的權(quán)值大小，設(shè)連接頂點(v0,vt)兩個頂點的權(quán)值Q(v0,vt)=1，則Q(v1,v0)=1；同理Q(v0,v2)=2，則Q(v2,v0)=2；Q(v1,v2)=2，則Q(v2,v1)=2。根據(jù)權(quán)值得大小可以很快查找到切平面的鄰接三角形面片[6]。

如圖4所示，三棱錐有四個三角形面片，分別取序號為0,1,2,3。那么三角形面片鄰接關(guān)系如圖5所示。三棱錐各三角形面片權(quán)值有向加權(quán)圖如圖6所示。

圖3 三角形面片權(quán)值

圖4 三棱錐

圖5 三角形鄰接關(guān)系

圖6 三棱錐的有問加權(quán)圖

可使用一個加權(quán)有向的關(guān)聯(lián)矩陣將三棱錐頂點鄒城的有向加權(quán)圖描述出來，鄰接矩陣表達如下表1所示。

表1 加權(quán)有向鄰接矩陣

鄰接矩陣用來表達由STL模型頂點組成的有向圖，而這個鄰接矩陣是稀疏矩陣，用它來表達鄰接關(guān)系占用的內(nèi)存空間大。本文采用適合存儲這種這種稀疏矩陣的三角形鄰接出邊鏈表，結(jié)構(gòu)如圖7所示。三棱錐有向加權(quán)圖的鄰接表的存儲數(shù)據(jù)結(jié)構(gòu)如圖8所示。

圖7 結(jié)構(gòu)圖

圖8 鄰接表

鄰接表C語言的數(shù)據(jù)結(jié)構(gòu)如下:

Typedef struct triangle

{

float normal [3]; //三角形面片的法向量

float x [3]; //三角形頂點坐標(biāo)

float y [3];

float z [3];

int slice_flag; //三角形面片的訪問標(biāo)志

int vertex; //三角形面片編號

int Q[3]; //三角形面片的權(quán)值

struct triangle next//鏈表指針

}

建立三角形面片鄰接關(guān)系主要根據(jù)一個三角形的任意兩個頂點是否與另一個三角形的兩個坐標(biāo)相同，如果相同則判定這兩個三角形是鄰接三角形。由于CAD或是其他作圖軟件在繪制STL模型文件中經(jīng)常在不同三角形的頂點坐標(biāo)計算時發(fā)生錯誤，出現(xiàn)同一頂點在不同位置的現(xiàn)象。為了正確的建立三角形之間的鄰接關(guān)系，如果比較任意兩個頂點的距離小于設(shè)定值δ，則認為這兩點是一個頂點[7]。

2.3 遞歸搜索過程分析過程

通過建立的三角形面片的有向加權(quán)圖，使用深度優(yōu)先遍歷法搜索圖中所有的三角形找出相交點，即遞歸搜索。首先從圖中V0開始搜索，接著訪問Vi(Vi與V0相鄰且沒有被訪問)連續(xù)重復(fù)上述遍歷方法，訪問全部頂點及其相鄰的頂點，直到訪問截止。被訪問過的頂點用標(biāo)置位slice_flag=1表示。通過遞歸搜索找出與切平面相交但未曾被訪問的三角形。遞歸搜索程序流程如圖9所示。

圖9 遞歸搜索程序流程

如圖10所示，在遞歸搜索過程中，碰到L2切平面搜索工作順利結(jié)束，同時生成封閉的輪廓線。遇到L1情況時，只有部分頂點在L直線上，則無法搜索到鄰接三角形。

對這種情況進行處理，就是判斷三角形面片的頂點與直線是否相交。如果相交，將把這個三角形面片設(shè)置slice_flag=1，不再求交計算。以此三角形面片為基礎(chǔ)，依據(jù)它的權(quán)值，求其鄰接的三角形面片，搜索將繼續(xù)進行。如果三角形面片在搜索過程中處于求交的范圍內(nèi)，但未被求交計算，則表示在這個切平面高度還有封閉的輪廓，將重新開始搜索遞歸算法，生成一條新的封閉輪廓[8]。

圖10 三角形搜索狀況

3 分層算法的實現(xiàn)

3.1 三角面片與切平面交點求取

求取三角形面片與切平面的交點可能會出現(xiàn)下列情況[9]：①相鄰切平面與同一個三角形面片相交的交點求??；②切平面與未相交過的三角形面片的交點求取。

(1) 相鄰切平面與同一個三角形面片相交的交點求取

采用迭代算法中的增量計算法，即每一步的計算結(jié)果上一步的計算結(jié)果和增量組成，這種算法計算量少，效率高。

如圖11所示，ΔABC的頂點坐標(biāo)分表為B(x1，y1，z1)，C(x2，y2，z2)，A(x3，y3，z3),假設(shè)L1的切平面高度為Z=zi，邊BC與L1相交的點設(shè)為Vi，坐標(biāo)設(shè)為(xi，yi，zi)。當(dāng)L1增加ΔZ高度時，則L2切平面的高度zi+1=zi+Δz，那么邊BC與L2的交點為Vi+1，坐標(biāo)則為(xi+1，yi+1，zi+1)。一個三角形面片存在與多個切平面相交，交點之間存在相關(guān)性，利用這種相關(guān)性可求其他的交點。

圖11 Δ ABC與切平面求交情況

邊BC的方程表示為:

(3)

則邊BC與相鄰切平面Z=zi與Z=zi+1的相交對的交點Vi，Vi+1可以用如下公式計算：

(4)

(5)

(6)

(7)

由式(4)和式(5)兩個表達式可得：

(8)

(9)

yi+1=yi+Δy

(10)

使用增量算法進行交點求取，假設(shè)三角形面片一邊與N個切面相交，在求解N個交點的坐標(biāo)時，可以降低計算量，提高效率。

(2)切平面與未相交過的三角形面片的交點求取

利用平行于xoy面的切平面與三角形面片求取交點，設(shè)分層方向為z軸的正方向，將切平面與三角形面片相交的交點連接起來的線段就是截面輪廓。如圖12所示，切平面z=h與ΔABC相交的交點為V1，V2，已知AB兩點的坐標(biāo)設(shè)為(x1，y1，z1)，(x2，y2，z3)，V1與V2交點V1的坐標(biāo)設(shè)為(x，y，z)，那么直線V1V2可以用式(3)表示?？梢郧蟮肰1的坐標(biāo)為：

(11)

圖12 截面輪廓方向的確定

3.2 分層算法描述

本文采用的分層算法根據(jù)三角形面片的Z軸方向建立分層關(guān)系矩陣，根據(jù)確定的分層關(guān)系矩陣可以建立分組三角形面片的有向加權(quán)圖，使用遞歸搜索法對三角形面片進行求交運算，最后獲得每層切片的輪廓數(shù)據(jù)信息，確定截面輪廓走向。算法的實施步驟如下：

(1)導(dǎo)入STL模型文件計算出模型需要的最大空間；

(2)運算出三角面片在Z軸坐標(biāo)的最大值與最小值；

(3)確定分層的厚度Z；

(4)根據(jù)獲取的各面片頂點坐標(biāo)的最大值與最小值確立分層關(guān)系矩陣；

(5)對切平面建立有向加權(quán)圖；

(6)選用遞歸搜索法求有向加權(quán)圖中相交的的三角形，全部清除所有的相交邊，將求到的交點放入輪廓線數(shù)據(jù)中。

(7)根據(jù)獲得的輪廓數(shù)據(jù)，對截面輪廓走向進行直接確定；

(8)將切平面進行上移，如果切平面比模型最大高度還高，則進入(7)，否則進入(2)；

3.3 截面輪廓走向的確定

分層切片獲得得輪廓線走向是不明確的，進行線寬補償需要確定輪廓線的走向及內(nèi)外邊界。假設(shè)實體的外輪廓的逆時針方向為正方向，實體內(nèi)輪廓的順時針方向為正方向。STL文件內(nèi)每個三角形切片數(shù)據(jù)中含其外法向量，所以在對STL文件進行切片的過程中，可以對輪廓環(huán)的走向進行直接確定。

在對分層算法描述中，可知對第一個三角形面片的分層過程中，任意選定三角形的一條邊，接著沿著這個三角形面片的鄰邊三角形的方向搜索下去，一直到返回這個三角形。因此正確選擇第一個三角形的邊對得到截面輪廓方向是十分重要的，如圖12所示，三角形F為第一個被切割的三角形。若得到交點P0，則輪廓的走向?qū)刂鳧0方向，若得到P1點，那么輪廓將沿著D1的方向。本文為此選用如下方法來對截面輪廓走向的確定，判別函數(shù)如下：

F=(N×P0P1)×n

(12)

表達式中N為三角形的單位法向量，n為切片方向(Z軸上的單位向量)，n=[0,0,1]。

若F>0，選取P1為交點，截面輪廓的方向為D0；若F<0，選取P0為交點，截面輪廓的方向為D1。

4 實驗結(jié)果

將本文提出的基于分組排序的有向加權(quán)圖遞歸分層算法與兩種常用的算法進行比對，分別是基于STL模型幾何特征分類的算法和基于STL模型拓撲結(jié)構(gòu)信息的分層算法。在本文實驗中簡稱為算法1和算法2。

實驗從模型分層時間、內(nèi)存空間和體積誤差三個方面對算法進行評估，3種算法應(yīng)用于6個復(fù)雜程度不同的模型，STL模型如圖所示。依次編號為1～6，各個模型包含的三角形面片的個數(shù)如表1所示。實驗環(huán)境為OpenGL，算法語言使用C++[10]。

表2列出了模型分層厚度為0.01mm時3種算法對6個實驗?zāi)Ｐ偷贸龅哪Ｐ头謱訒r間、內(nèi)存空間和體積誤差，因為模型復(fù)雜程度的不同，各角度實驗數(shù)值相差也比較大。

圖13 6個STL模型

表2 6個模型在3種算法下的結(jié)果

圖14為3種算法的分層時間對比曲線，從圖中可以看出本文算法在分層運算效率方面優(yōu)勢明顯，耗時相對算法1與算法2大幅減少，僅僅為算法2的18%左右，對于一些結(jié)構(gòu)簡單的STL模型，本算法只需幾十甚至幾百毫秒，面片數(shù)在2×104的模型只需要十幾秒，適用性比較強。相比較而言，算法1比較適用于結(jié)構(gòu)簡單的模型，但對于三角形面片數(shù)在2×103以上的STL模型，分層需要的時間上升，無法進行應(yīng)用。相對于算法1，算法2雖然在分層時間上有所減少，但是在建立拓撲數(shù)據(jù)過程耗時，且占用內(nèi)存較大。對于面片數(shù)在2×104以下的模型，可以在20s以內(nèi)很快完成分層，但對于復(fù)雜程度較大的模型，則需要很長時間才能完成。

圖14 三種算法分層時間

圖15給出的是本算法與算法1、算法2在減少體積偏差方面的比較。相對于算法1而言，本文算法平均可以使體積偏差減少大約3.6%的體積偏差，對模型2、5甚至達到了7%左右,但是在對模型10處理時出現(xiàn)了稍微的反復(fù)。與算法2相比較，本文算法平均可以使體積偏差減少大約1.16%，除了個別模型(模型6)。下降的幅度都相對較少，大約只有0.69%。該實驗結(jié)果是在預(yù)期范圍內(nèi)的，體積偏差雖然變大，但是分層效率明顯提高。

(a)與 算法1相比較 (b)與算法2相比較圖15 本算法與算法1、算法2的精度性能比較

5 結(jié)論

本文提出的一種基于STL模型的快速分層算法即分組排序的有向加權(quán)遞歸算法。經(jīng)過理論分析與實驗結(jié)果對比，可以得到以下結(jié)論：

(1)通過對3D打印中STL模型文件進行分析，建立有向加權(quán)圖數(shù)據(jù)結(jié)構(gòu)，該拓撲結(jié)構(gòu)找到鄰接三角形記錄其權(quán)值數(shù)據(jù)信息，通過權(quán)值信息直接找到邊，進而求得邊與截面的交點。該數(shù)據(jù)結(jié)構(gòu)建立耗時短，分層效率高。

(2)通過對遞歸切片中出現(xiàn)的三角形“點切”問題的分析，在調(diào)用的遞歸函數(shù)中可以自動進行判斷，完成搜索任務(wù)，進而避免攝動誤差，達到分層的智能化與集成化。

(3)本文所有算法試驗都是以正確STL文件為基礎(chǔ)，對于部分殘缺的STL模型在進行算法試驗之前必須對模型進行修補，才可以生成完好的輪廊。對于如何處理有缺陷的STL模型軟件也在開發(fā)之中。

[1] 朱曉鵬.激光熔覆再制造過程中的分層切片方法[D].上海:上海交通大學(xué)，2013.

[2] 黃建.數(shù)控加工空間運動平滑路徑的規(guī)劃[D].揚州: 揚州大學(xué)，2013.

[3] 劉斌，黃樹槐.快速原型制造技術(shù)中實時切片算法的研究與實現(xiàn)[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，1997,9(6) :488-493.

[4] 王春香 郝志博. 快速成型技術(shù)STL模型等厚分層算法研究[J]. 機械設(shè)計與制造,2014(4):133-136.

[5] 張嘉易，劉偉軍，王天然,等.快速成型數(shù)據(jù)處理系統(tǒng)研究[J].機械設(shè)計與制造，2004(1) :38-40.

[6] Zhang L C,Han M , Huang S H. An effective error-tolerance slicing algorithm for STLfiles[J].The International lounutl of Advanced Manufacturing Technology,2002,20(5)；363-367.

[7] 趙吉賓,劉偉軍.快速成形技術(shù)中基于STL模型的分層算法研究[J].應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報，2008,16(2):224-233.

[8] 朱經(jīng)緯,王乘,蒙培生.基于控制點誤差控制的網(wǎng)格簡化算法[J].計算機應(yīng)用，2007,27(5)：1150-1152.

[9] 王春香,郝志博,陳浩宏.快速成型中基于MATLAB軟件的STL模型的分層優(yōu)化[J]. 機床與液壓，2014,42(21):113-117.

[10] 羅楠,王泉.一種快速3D打印分層方向確定算法[J].西安交通大學(xué)學(xué)報,2015,49(5):140-146.

(編輯李秀敏)

ResearchonaFastHierarchicalAlgorithmfor3DPrinting

LIU Da-wei1，WANG Su-zhou2

(1. College of Automation，Nanjing Institute of Technology，Nanjing 211167,China；2.College of Electrical Engineering and Control Science，Nanjing Tech University,Nanjing 211816,China)

Through the analysis of the hierarchical rule STL data 3D printing model weighted directed graph data structure, the data structure found in the neighboring triangle also records the weight information, using depth first traversal method graph, establish recursive search function, for the triangle "cut" the problem of recursive slices, put forward a fast algorithm based on STL model is a sorting algorithm to weighted recursive. This algorithm based on triangle sorting, directed weighted graph recursive search, obtain the intersection between triangles arranged orderly, in OpenGL environment to achieve the automatic generation of contour, according to the first triangle data of each contour cutting, to determine the profiles. The results show that the algorithm can reduce the time of establishment of the topology relation between patches, simple, stable and reliable.

3D printer；hierarchical algorithm；STL model

TH164;TG506

：A

1001-2265(2017)09-0050-05

10.13462/j.cnki.mmtamt.2017.09.013

2016-11-26；

：2017-01-08

劉大偉(1980—)，男，安徽蕭縣人，南京工程學(xué)院實驗師，碩士，研究方向為3D打印機的研究，(E-mail)zdhxldw@njit.edu.cn。