劉大偉，王蘇洲

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

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

劉大偉1，王蘇洲2

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

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

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

0 引言

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

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

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

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

1 分層算法原理

1.1 分組排序

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

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

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

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

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

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

2.1 分組排序的建立

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

(1)

(2)

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

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

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

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

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

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

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

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

如圖3所示，假設(shè)三角形面片的三條邊的權(quán)值互相等，設(shè)定共享相應(yīng)邊的鄰接面片的權(quán)值大小，設(shè)連接頂點(diǎn)(v0,vt)兩個(gè)頂點(diǎn)的權(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所示，三棱錐有四個(gè)三角形面片，分別取序號(hào)為0,1,2,3。那么三角形面片鄰接關(guān)系如圖5所示。三棱錐各三角形面片權(quán)值有向加權(quán)圖如圖6所示。

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

圖4 三棱錐

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

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

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

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

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

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

圖8 鄰接表

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

Typedef struct triangle

{

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

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

float y [3];

float z [3];

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

int vertex; //三角形面片編號(hào)

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

struct triangle next//鏈表指針

}

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

2.3 遞歸搜索過(guò)程分析過(guò)程

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

圖9 遞歸搜索程序流程

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

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

圖10 三角形搜索狀況

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

3.1 三角面片與切平面交點(diǎn)求取

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

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

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

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

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

邊BC的方程表示為:

(3)

則邊BC與相鄰切平面Z=zi與Z=zi+1的相交對(duì)的交點(diǎn)Vi，Vi+1可以用如下公式計(jì)算：

(4)

(5)

(6)

(7)

由式(4)和式(5)兩個(gè)表達(dá)式可得：

(8)

(9)

yi+1=yi+Δy

(10)

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

(2)切平面與未相交過(guò)的三角形面片的交點(diǎn)求取

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

(11)

圖12 截面輪廓方向的確定

3.2 分層算法描述

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

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

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

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

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

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

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

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

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

3.3 截面輪廓走向的確定

分層切片獲得得輪廓線走向是不明確的，進(jìn)行線寬補(bǔ)償需要確定輪廓線的走向及內(nèi)外邊界。假設(shè)實(shí)體的外輪廓的逆時(shí)針?lè)较驗(yàn)檎较颍瑢?shí)體內(nèi)輪廓的順時(shí)針?lè)较驗(yàn)檎较?。STL文件內(nèi)每個(gè)三角形切片數(shù)據(jù)中含其外法向量，所以在對(duì)STL文件進(jìn)行切片的過(guò)程中，可以對(duì)輪廓環(huán)的走向進(jìn)行直接確定。

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

F=(N×P0P1)×n

(12)

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

若F>0，選取P1為交點(diǎn)，截面輪廓的方向?yàn)镈0；若F<0，選取P0為交點(diǎn)，截面輪廓的方向?yàn)镈1。

4 實(shí)驗(yàn)結(jié)果

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

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

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

圖13 6個(gè)STL模型

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

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

圖14 三種算法分層時(shí)間

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

[5] 張嘉易，劉偉軍，王天然,等.快速成型數(shù)據(jù)處理系統(tǒng)研究[J].機(jī)械設(shè)計(jì)與制造，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é)報(bào)，2008,16(2):224-233.

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

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

[10] 羅楠,王泉.一種快速3D打印分層方向確定算法[J].西安交通大學(xué)學(xué)報(bào),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é)院實(shí)驗(yàn)師，碩士，研究方向?yàn)?D打印機(jī)的研究，(E-mail)zdhxldw@njit.edu.cn。