基于分組的STL模型快速切片算法

侯聰聰，南 琳，張 磊

(1.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，沈陽(yáng) 110016；2.中國(guó)科學(xué)院大學(xué)，北京 100049)

0 引言

快速成型技術(shù)RP( Rapid Prototyping ) 是集機(jī)械、計(jì)算機(jī)、光學(xué)、電子及新材料為一體的新型先進(jìn)制造技術(shù)，通過(guò)逐層增加材料制造零件[1,2]。在所有的RP工藝中，無(wú)論是由CAD造型軟件還是由逆向工程生成的零件CAD模型，都必須經(jīng)過(guò)分層處理才能將數(shù)據(jù)輸入到RP設(shè)備中，因此分層算法是RP制造中的一個(gè)關(guān)鍵環(huán)節(jié)。

STL文件是RP系統(tǒng)中數(shù)據(jù)交換的標(biāo)準(zhǔn)文件類型[3]，用三角網(wǎng)格面近似地表現(xiàn)三維CAD模型，并記錄模型中每個(gè)三角面片的幾何信息，包括三角面片所在平面的法矢和它所包含的三個(gè)頂點(diǎn)的坐標(biāo)。由于STL模型數(shù)據(jù)格式簡(jiǎn)單、易于交換處理，基于STL模型的切片處理已被大多數(shù)RP系統(tǒng)采用。

目前，STL模型的切片算法主要分為以下兩類：

1）基于幾何拓?fù)湫畔⒌腟TL模型切片算法[4～8]。該類算法根據(jù)三角面片的點(diǎn)、邊和面數(shù)建立STL模型的整體拓?fù)湫畔ⅲ猛負(fù)湫畔⒖梢匝杆俨檎业较噜徣敲嫫?，并通過(guò)對(duì)相鄰三角面片的追蹤得到有向輪廓線。其優(yōu)點(diǎn)是利用拓?fù)潢P(guān)系，無(wú)需排序，可直接獲得首尾相連的封閉輪廓線。但該算法也存在一定局限性：獲取STL模型整體拓?fù)湫畔⒌倪^(guò)程相當(dāng)費(fèi)時(shí)，尤其對(duì)于復(fù)雜的STL模型占用系統(tǒng)資源較多；當(dāng)STL文件有錯(cuò)誤時(shí)，可能無(wú)法得到正確的截面輪廓線。

2）基于三角面片幾何特征的STL模型切片算法[9～12]。該類算法根據(jù)三角面片頂點(diǎn)坐標(biāo)沿切片方向投影值的大小進(jìn)行分組排序，減少三角面片與切片平面位置關(guān)系的判斷次數(shù)，加快分層處理速度。但是該算法的局限性在于：對(duì)大量三角面片的排序是一個(gè)耗時(shí)的過(guò)程；在后續(xù)輪廓線的生成過(guò)程中，還要進(jìn)行交線連接關(guān)系的搜索判斷；三角面片分組界限比較模糊，經(jīng)常無(wú)法判斷三角面片與分層平面的位置關(guān)系。

針對(duì)以上兩種分層算法的優(yōu)缺點(diǎn)，本文提出整體分組排序，局部建立基于鏈表的拓?fù)潢P(guān)系的思路以進(jìn)一步的降低分層算法的復(fù)雜度。針對(duì)具體的零件模型，通過(guò)仿真對(duì)比分析，得到合適的分組組數(shù)。同時(shí)本文提出了基于鏈表的STL文件拓?fù)渲亟ㄋ惴?，在建立拓?fù)潢P(guān)系的同時(shí)去除了冗余數(shù)據(jù)，節(jié)省了存儲(chǔ)空間，提高了存儲(chǔ)效率。

1 基于鏈表的拓?fù)渲亟ㄋ惴?/h2>

STL文件的數(shù)據(jù)量很大，一個(gè)表面復(fù)雜的實(shí)體模型由幾萬(wàn)甚至幾十萬(wàn)個(gè)三角形面片構(gòu)成，由于對(duì)任意多面體，均存在歐拉公式F-E +V=2，其中F表示面的數(shù)目，E表示邊的數(shù)目，V表示點(diǎn)的數(shù)目。對(duì)于一個(gè)由三角面片構(gòu)成的多面體，每個(gè)三角面片具有3條邊，每條邊被2個(gè)三角面片共享，因此可得出E=3F/2。將其帶入歐拉公式得V=F/2+2，而STL文件中所存頂點(diǎn)數(shù)是三角面片數(shù)的3倍，所以平均分裂后的點(diǎn)數(shù)為原拓?fù)潼c(diǎn)數(shù)的6倍。因此數(shù)據(jù)的冗余現(xiàn)象比較嚴(yán)重。如果簡(jiǎn)單地照原樣提取數(shù)據(jù)，會(huì)占用大量的計(jì)算機(jī)資源，降低計(jì)算速度，而且使得后續(xù)的處理計(jì)算量增大。因此從文件中提取數(shù)據(jù)時(shí)必須進(jìn)行數(shù)據(jù)篩選，去除冗余信息。因而，STL文件拓?fù)渲亟ㄟ^(guò)程通常由兩部分組成：冗余數(shù)據(jù)的去除和拓?fù)浣Y(jié)構(gòu)的建立。

本文提出了基于鏈表的STL文件重建算法。該算法采用鏈表[13]作為數(shù)據(jù)結(jié)構(gòu)，將兩部分融合為一個(gè)整體，對(duì)冗余點(diǎn)和冗余邊進(jìn)行了處理，實(shí)現(xiàn)了數(shù)據(jù)的無(wú)重復(fù)存儲(chǔ)。節(jié)省了存儲(chǔ)空間，提高了存儲(chǔ)效率，同時(shí)建立了拓?fù)浣Y(jié)構(gòu)，提高了數(shù)據(jù)的可操作性，為后續(xù)分層奠定了基礎(chǔ)。

1.1 拓?fù)渲亟ǖ臄?shù)據(jù)結(jié)構(gòu)

拓?fù)渲亟ㄟ^(guò)程數(shù)據(jù)結(jié)構(gòu)分為三類，面（ Facet）、邊（Edge）和頂點(diǎn)（Vertex），由三個(gè)類產(chǎn)生三個(gè)對(duì)象，并建立相應(yīng)的對(duì)象鏈表。為了節(jié)省拓?fù)潢P(guān)系存儲(chǔ)的時(shí)間和空間，頂點(diǎn)鏈表只記錄該點(diǎn)的坐標(biāo)，邊鏈表只記錄所包含的頂點(diǎn)在頂點(diǎn)鏈表中的編號(hào)和所屬面片在面鏈表中的編號(hào)，面鏈表只記錄所包含的邊在邊鏈表中的編號(hào)。具體的數(shù)據(jù)結(jié)構(gòu)如圖1～圖3所示。

1.2 拓?fù)浣Y(jié)構(gòu)重建

本算法以三角面片為基本單位，依次讀取每個(gè)三角面片的頂點(diǎn)數(shù)據(jù)，對(duì)頂點(diǎn)鏈表中的頂點(diǎn)進(jìn)行查詢，在判斷一個(gè)頂點(diǎn)為非冗余點(diǎn)后，將其插入頂點(diǎn)鏈表并為其建立鄰域信息，并在插入了其他點(diǎn)后對(duì)其進(jìn)行實(shí)時(shí)更新；以同樣方法進(jìn)行邊的去冗余及建立鄰域信息，最終建立一個(gè)完整的拓?fù)浣Y(jié)構(gòu)。

算法具體步驟如下：FaceCount為STL文件中的三角面片個(gè)數(shù)總和。

Step1：分別創(chuàng)建點(diǎn)對(duì)象鏈表vlist、邊對(duì)象鏈表elist及面對(duì)象鏈表f l ist。

Step2：創(chuàng)建三個(gè)點(diǎn)對(duì)象v1、v2、v3，三條邊對(duì)象e1、e2、e3和面對(duì)象f，并將f添加到flist，取三角面片三個(gè)頂點(diǎn)數(shù)據(jù)，分別賦給v1、v2、v3。

Step3：取v1，查找vlist中是否有相同的點(diǎn)。如果有，則將該點(diǎn)在vlist中對(duì)應(yīng)的索引號(hào)賦給e1的EVertexIndex1、e3的EVertexIndex2；如果沒(méi)有，則將v1添加到vlist，并將v1在vertexlist中對(duì)應(yīng)的索引號(hào)賦給e1的EVertexIndex1、e3的EVertexIndex2。v2和v3同v1。

Step4：取e1，查找elist中是否有相同的邊，如果有，則將該邊在elist中對(duì)應(yīng)的索引號(hào)賦給f的FEdgeIndex1，同時(shí)將f在flist中的索引號(hào)賦給該邊的EFacetIndex2；如果沒(méi)有，則將e1添加到elist，并將e1在elist中對(duì)應(yīng)的索引號(hào)賦給f的FEdgeIndex1，同時(shí)將f在flist中的索引號(hào)賦給e1的EFacetIndex1。e2和e3同e1。

Step5：讀第n個(gè)三角面片，如果n≤ FaceCount，則返回step2；否則退出程序，拓?fù)浣Y(jié)構(gòu)創(chuàng)建完成。

1.3 算法復(fù)雜度分析

圖1 頂點(diǎn)鏈表

圖2 邊鏈表

圖3 面鏈表

該算法的時(shí)間復(fù)雜度主要是冗余點(diǎn)和冗余邊的濾除時(shí)間。對(duì)于上述算法，設(shè)STL文件中三角面片個(gè)數(shù)為n，則頂點(diǎn)數(shù)和邊數(shù)均為3n。依據(jù)上述STL文件中三角面片的公式E=3F/2，V=F/2+2，得到最終存儲(chǔ)的頂點(diǎn)數(shù)為n/2，邊數(shù)為3n/2。對(duì)于一個(gè)頂點(diǎn)i（i=1,2,…,3n），在鏈表中查找的平均時(shí)間復(fù)雜度為o(l)（l為鏈表長(zhǎng)度，l=1,2,…,n/2），則去除冗余頂點(diǎn)的時(shí)間復(fù)雜度為o(n2)。同理，去除冗余邊的時(shí)間復(fù)雜度為o(n2)。因此，該算法的總的時(shí)間復(fù)雜度為o(n2)。與其他算法相比，該算法在相同的時(shí)間復(fù)雜度的情況下，既去除了冗余頂點(diǎn)和邊，又建立了拓?fù)潢P(guān)系，提高了算法的效率，節(jié)省了存儲(chǔ)空間。

2 基于分組思想的分層算法

該算法的基本思想是“整體分組排序，借助分組結(jié)果，局部建立基于鏈表的拓?fù)潢P(guān)系”，即先對(duì)所有的三角面片依據(jù)其在分層方向的投影值的大小將其分為幾個(gè)大組，在此基礎(chǔ)上建立局部拓?fù)潢P(guān)系，進(jìn)行分層處理。

2.1 整體分組

假設(shè)Z軸為分層切片方向，STL模型在Z軸上的最大值為Zmax，最小值為Zmin。假設(shè)將整個(gè)模型分為k組，各組的范圍分別為：[Z0,Z1]，[Z1,Z2]…[Zi-1,Zi]…[Zk-1,Zk]，Z0=Zmin，Zk=Zmax。三角面片F(xiàn)在Z軸投影范圍[Fzmin,Fzmax]，F(xiàn)zmin，F(xiàn)zmax分別為三角面片在Z軸投影的最小和最大值。如果[Zi-1,Zi]（i=1,2…k）與[Fzmin,Fzmax]有交集，則F屬于第i組。在進(jìn)行分層時(shí)通過(guò)分層平面的高度可以直接在對(duì)應(yīng)的組中查找與切平面相交的首個(gè)三角面片，減少了三角面片與平面位置關(guān)系判斷的次數(shù)。

圖4 分組實(shí)例

以圖4所示的局部STL模型為例，運(yùn)用上述分組思想，分組結(jié)果如表1所示。

表1 分組結(jié)果

2.2 分層切片求取輪廓線

分組之后，采用小節(jié)1中拓?fù)渲亟ㄋ惴ń⒕植客負(fù)浣Y(jié)構(gòu)，分層求交，獲取輪廓線。先找到一條與當(dāng)前切平面有交點(diǎn)且未被切過(guò)的邊，求出此邊與切平面的交點(diǎn)，保存，并將此邊的位置標(biāo)志為已切。根據(jù)上述拓?fù)潢P(guān)系找到此邊所屬的三角面片，在三角面片中查找與切平面有交點(diǎn)且未被切過(guò)的邊，求其交點(diǎn)，保存。以此類推，則可得到與當(dāng)前切平面相交的一組首尾相連、封閉的多邊形輪廓線。設(shè)Z軸為分層方向，具體分層求交算法如下：

Step1：確定第一個(gè)切平面高度h=Zmin（模型在分層方向上的最小值）。

Step2：將elist中所有邊對(duì)象的mark置為false，f l ist中所有面對(duì)象的mark置為false。

Step3：找到一個(gè)與當(dāng)前切平面相交且未被切過(guò)的邊edge0，如果存在則執(zhí)行下一步，否則跳到step8。

Step4：求邊edge0與切平面的交點(diǎn)，保存，并將該邊的mark置為true。

Step5：根據(jù)拓?fù)潢P(guān)系找到包含該邊的且未被切過(guò)的三角面片，將該三角面片的mark置為true，求三角面片另外兩條邊中與當(dāng)前切平面相交且未被切過(guò)的邊，求交點(diǎn)保存，并將該邊的mark置為true。

Step6：重復(fù)step5直到回到初始邊edge0，得到與當(dāng)前切平面相交的一個(gè)多邊形輪廓線。

Step7：返回step3，直至求出所有與當(dāng)前切平面相交的多邊形輪廓線。

Step8：令 h= h+thick (切片厚度)，如果h≤Zmax（模型在分層方向上的最大值），返回step2，否則，退出程序，切片完成。

整體分組、局部建立拓?fù)潢P(guān)系可以有效的降低STL建立拓?fù)潢P(guān)系的算法復(fù)雜度。由于建立拓?fù)潢P(guān)系時(shí)的算法復(fù)雜度與面片個(gè)數(shù)的平方成正比，假設(shè)一個(gè)STL文件中包含n個(gè)三角面片，如果對(duì)整個(gè)模型建立拓?fù)潢P(guān)系算法復(fù)雜度為o（n2）；如果將整個(gè)STL文件按分層方向分為k（k

理論上，k越大，即組數(shù)越多，算法復(fù)雜度越小，但是k過(guò)大，組之間重疊的三角面片數(shù)量過(guò)多，重疊的面片在不同的組之間重復(fù)建立拓?fù)潢P(guān)系增加了算法的復(fù)雜度。以圖5所示軸套為例，三角面片的數(shù)目為8537個(gè)，分組數(shù)分別取1、10、20、30、40、50，分層厚度為2mm，分組切片時(shí)間開(kāi)銷（每個(gè)分層組數(shù)重復(fù)仿真20次，求取時(shí)間的平均值）如表2所示。

通過(guò)對(duì)表2進(jìn)行分析，可以發(fā)現(xiàn)當(dāng)分組數(shù)目逐漸增大時(shí)，分層算法的時(shí)間開(kāi)銷逐漸減少；但是當(dāng)分組數(shù)目大于20時(shí)，時(shí)間開(kāi)銷開(kāi)始增加。由此可見(jiàn)，分組組數(shù)并不是越大越好。因此，對(duì)于不同的零件和三角面片數(shù)量要選擇合適的分組組數(shù)。

3 模型仿真與對(duì)比

在軟硬件環(huán)境相同的情況下，三種不同切片算法的對(duì)比如表3所示，其中m為三角面片的個(gè)數(shù)，h為分層厚度，T1為基于拓?fù)湫畔⒌那衅惴ㄋ脮r(shí)間，T2為基于三角形幾何特征的切片算法所用時(shí)間，T3為本文算法所用時(shí)間（每種算法重復(fù)仿真20次，求取時(shí)間的平均值），g為本文算法對(duì)三角面片進(jìn)行分組所得的組數(shù)。由表1可以看出，與其他2種算法相比，隨著模型三角形面片個(gè)數(shù)的增加，本文算法的效率逐漸提高。

4 結(jié)論

該算法綜合考慮了現(xiàn)有切片算法的特點(diǎn)，提出了分組的思想降低了建立拓?fù)潢P(guān)系的算法復(fù)雜度，并同時(shí)提出了基于鏈表的拓?fù)渲亟ㄋ惴ǎ诮⑼負(fù)潢P(guān)系的同時(shí)去除了冗余數(shù)據(jù)，降低了算法空間開(kāi)銷。最后通過(guò)實(shí)例仿真，證明了算法的可行性和高效性。根據(jù)三角面片數(shù)量以及零件形狀精確的確定最優(yōu)的分組數(shù)量以使算法復(fù)雜度得到進(jìn)一步的降低是未來(lái)研究的重點(diǎn)。

表3 不同切片算法對(duì)比

[1]顏永年,張偉,盧清萍,王剛,刁慶軍,時(shí)曉明.基于離散/堆積成型概念的RPM原理和發(fā)展[J].中國(guó)機(jī)械工程,1994,5(4):64-66.

[2]韓光超,張海鷗,王桂蘭.面向金屬模具快速制造的機(jī)器人成型加工系統(tǒng)[J].機(jī)器人,2006,28(5):515-518.

[3]劉光富,李愛(ài)平,王東立.三維實(shí)體零件分層處理軟件的研究與開(kāi)發(fā) [J].制造業(yè)自動(dòng)化,2004,26(11): 21-24.

[4]王素,劉恒,朱心雄.STL模型的分層鄰接排序快速切片算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,26(4):4-6.

[5]謝存禧,李仲陽(yáng),成曉陽(yáng).STL文件毗鄰關(guān)系的建立與切片算法研究[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2000,28(3):33-38.

[6]李仲陽(yáng),謝存禧,楊家紅.基于STL文件的快速成型分層算法與毗鄰?fù)負(fù)湫畔⒌目焖偬崛J].計(jì)算機(jī)工程與應(yīng)用,2002,38(7):32-35,79.

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

[8]CHOI S H,KWOK K T.A tolerant slicing algorithm for layered manufacturing[J].Rapid Prototyping Journal,2002,8(3):161-79.

[9]趙保軍,汪蘇,陳五一.STL數(shù)據(jù)模型的快速切片算法 [J].北京航空航天大學(xué)學(xué)報(bào),2004,30(4):329-333.

[10]胡德洲,李占利,李滌塵,et al.基于STL模型幾何特征分類的快速分層處理算法研究[J].西安交通大學(xué)學(xué)報(bào),2000,34(1):37-40,45.

[11]李占利,梁棟,李滌塵,et al.基于信息繼承的快速分層處理算法研究[J].西安交通大學(xué)學(xué)報(bào),2002,36(1):43-46.

[12]趙吉賓,劉偉軍.快速成型技術(shù)中分層算法的研究與進(jìn)展[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(2): 2-21.

[13]SAHNI S.數(shù)據(jù)結(jié)構(gòu),算法與應(yīng)用 [M].北京:機(jī)械工業(yè)出版社.2000.