基于冗余信息的STL模型快速切片算法*

錢 乘 李 震 江本赤

(安徽工程大學，安徽 蕪湖 241000)

3D打印技術(3D Printing)理論上可以打印出任何模型，被認為第三次工業(yè)革命的代表性技術，其廣泛運應于機械制造、醫(yī)學領域、房屋建筑、汽車行業(yè)、電子行業(yè)等[1]。對大多數(shù)3D打印系統(tǒng)而言，理論模型首先被構(gòu)建，根據(jù)用戶對精度的需求設定參數(shù)將模型轉(zhuǎn)換為STL文件，然后對STL模型進行切片處理。切片處理是3D打印系統(tǒng)中重要的一步，切片輪廓是生成刀具路徑與逐層沉積的基礎。STL模型將實體模型表面細分三角形來獲得，丟失了其原有模型的拓撲信息。STL模型每個三角形面片的頂點至少被記錄4次，從而帶來額外的計算存儲器占用和時間消耗；當物體表面的所需近似精度增加時，生成的STL文件的大小被大幅度增加，等等。這些造成了對STL模型切片算法效率較低。STL文件雖然存在數(shù)據(jù)冗余且無拓撲關系的缺陷，但是由于具有生成簡單性、輸出的廣泛性、易于切片處理等優(yōu)勢，對STL模型切片算法的研究仍然是研究的主流[2]。

目前，研究人員已提出了多種對STL模型切片算法。定層厚切片是目前普遍使用的切片算法,主要有3種即基于面片拓撲關系的分層切片算法，基于模型幾何特征的分類算法以及基于幾何連續(xù)性的切片算法[3]。Zhang等人[4]利用三角形之間的拓撲關系進行切片的優(yōu)化；王彥云等人[5]通過建立點表與面表快速實現(xiàn)拓撲信息重建。上述方法可以提高切片效率，但是拓撲關系的構(gòu)建需要花費時間較長且占用內(nèi)存大。Chakraborty等人[6]提出了三角形的精簡排序，提高算法效率，王春香等人[7]提出了快速精簡算法，直接提取只與切片面相交的三角形面片，提高分層效率，但是排序界限非常模糊，不能夠避免三角形面片與分層平面位置無關的無效判斷，且需要對雜亂無章的交線段進行排序；王素等人[8]提出了STL模型的分層鄰接排序快速切片算法,朱君等人[9]建立STL模型的分層面新相交三角形面片表文件,提取模型的活性拓撲結(jié)構(gòu)的方式,加快分層速度，但是在動態(tài)面片組合中，增減三角形操作，拓撲關系構(gòu)建仍然耗時。對于自適應算法而言，Hayasi[10]、Sikder[11]等專家學者進行了深入的研究，自適應切片方法切片速度較慢，但是精度比較高。

考慮到對STL模型切片過程中存在的冗余信息，本文提出了一種基于冗余信息的STL模型快速切片算法。在分析STL模型信息的基礎上，對于第i層切線平面，建立只與其相交的三角形集合，減少切平面與三角形相交判斷次數(shù)；分析了STL三角形面片與切平面的位置情況，求出集合中各三角形與切平面的交點信息并記錄交點存儲形式，將坐標值重復的交點視為冗余信息并分析拓撲關系可能存在的兩種情況，根據(jù)交點的冗余信息通過逐點識別與剔除以建立三角形之間的拓撲關系；依據(jù)拓撲關系獲得有序點列依次連接，得到二維封閉輪廓。通過兩個典型模型對該切片算法進行檢驗，表明該算法對STL模型進行切片處理有較好的效果。

1 STL模型的特點

1.1 STL模型的獲取

目前通常利用兩種方法來生成三維模型即正向設計技術與逆向設計技術。前者利用三維CAD工具建立模型，例如:AutoCAD、UG、SolidWorks等等，利用計算機生成、處理、存儲、輸出三維空間模型。CAD物理模型確定了表面的方向性、形體內(nèi)部材料的物理性能等參數(shù)、其幾何和拓撲信息最為完善的模型[12]。后者即三維測量技術建立模型,其大致可以分為4個階段：首先利用三坐標測量機(CMM)或者激光掃描儀來獲取零件原形表面點的三維坐標(點云數(shù)據(jù))；其次對點云數(shù)據(jù)進行預處理，去除不可用的數(shù)據(jù)；然后從測量數(shù)據(jù)中提取零件原型的幾何特征；最后進行零件CAD模型的重建[13]。

一般的CAD系統(tǒng)可直接轉(zhuǎn)換成STL格式；也可以直接對點云模型進行三角網(wǎng)格重構(gòu)，目前比較流行的方法Delaunay三角剖分，其對應關系如圖1所示。

1.2 STL文件信息存儲特點

STL(STereoLithographic)是由3D SYSTEM公司在1988年制定的一個接口協(xié)議[3]。STL文件由多個三角形面片定義組成，每個三角形面片的定義包括三角形3個頂點的坐標以及法向量。由于STL格式生成簡單性、輸出的廣泛性、易于切片處理等優(yōu)勢，已然成為3D打印行業(yè)默認的標準文件格式。STL文件雖然簡單易懂，僅僅記錄了坐標信息和法向量信息，但是幾何體之間的拓撲信息并沒有表達，三角面片記錄雜亂無章。

STL存在兩種格式：文本(ASCII)格式與二進制(BINARY)。ASCII格式記錄了每個字符和數(shù)字，具有可讀性，直觀性，方便進一步對數(shù)據(jù)進行處理。二進制STL格式更緊湊，其大小約為ASCII格式的STL文件大小的1/6，文件尺寸小、易于傳輸、對于數(shù)據(jù)處理更有效。STL文件文本與二進制結(jié)構(gòu)分別如表1所示：

文本格式結(jié)構(gòu)二進制格式結(jié)構(gòu)solid filename //文件名稱 UINT8[80] // 文件頭facet normalnxnynz // 法向量坐標UINT32 // 三角面片數(shù)量outer loopforeachtriangle // 定義一個三角面片vertex x1y1z1 // 第一個頂點坐標REAL32[3] // 法向量矢量vertexx2y2z2 // 第二個頂點坐標REAL32[3] // 第一個頂點坐標vertexx3y3z3 // 第三個頂點坐標REAL32[3] // 第二個頂點坐標endloopREAL32[3] // 第二個頂點坐標endfacet //完成一個三角面片定義UINT16 // 文件屬性… // 循環(huán)定義三角面片… // 循環(huán)定義三角面片endsolid// 文件定義結(jié)束end // 文件定義結(jié)束

2 基于冗余信息的STL模型切片算法

對于第i層切平面，建立只與該層切平面相交的三角形集合；分析了STL三角形面片與當前切平面的位置情況，求出集合中各三角形與切平面的交點信息；分析了拓撲關系一般與特殊的兩種情況；利用冗余信息重建拓撲關系；然后依據(jù)拓撲關系得到有序點列，依次連接；最后得到二維封閉輪廓。

2.1 相交三角形集合的建立

在進行分層處理的過程中(z軸方向為分層方向)，建立只與當前切平面相交的三角形集合，減少切平面與三角形的相交判斷次數(shù)，提高整體切片效率。

2.1.1 預處理

在進行數(shù)據(jù)操作時，為減少數(shù)據(jù)的處理量，忽略法向量信息。法向量可由STL記錄的3個頂點坐標獲得，可以把法向量坐標看作冗余數(shù)據(jù)進行處理。對ASCII文件進行讀入時法向量坐標應進行刪除；并根據(jù)每個三角形三個頂點z坐標值升序排序。預處理操作步驟如下：

Step1：根據(jù)ASCII文件記錄特點，1、5、9、…、4(n-1)+1行記錄法向量坐標，將其對應的行數(shù)刪除(n為三角形面片數(shù))。

Step2：按照每個三角形3個頂點的z坐標進行升序排列。

Step3：將得到的排列后的頂點數(shù)據(jù)排成一行每行代表1個三角形，即：[(x1,y1,zmin)(x2,y2,zmid)(x3,y3,zmax)]。

Step4：將所得到的數(shù)據(jù)依據(jù)zmax以行為單位進行升序排列。

2.1.2 集合的建立

經(jīng)過分析，與切平面zi無關的三角形有圖2所示3種情況，三角形T1、T2、T3分別為每種情況的示例。根據(jù)2.1.1節(jié)中三角形頂點的記錄方式，其刪除條件分別為：zmaxzi。

刪除上述3種無關三角形，建立相交三角形集合步驟如下：

Step1：升序排序后的三角形頂點坐標zmax與切平面高度zi進行比較，判斷zmax

Step2：從三角形頂點數(shù)組中刪除前p行向量與刪除數(shù)組相同坐標的向量。

Step3：將得到的數(shù)組依照zmin以行為單位進行降序排列。

Step4：判斷zmin>zi, 記錄下最終行數(shù)q。

Step5：從排序后的數(shù)組中刪除前q行向量。

經(jīng)上述操作即得到只與當前切平面相交的三角形集合。

2.2 相交三角形交點計算

2.2.1 交點計算公式

分層切片是用一系列與XOY平面相平行的平面去截取STL模型。截面輪廓為分層平面與STL模型相交三角形所得交點依次連接起來的多邊形。如圖3所示，ΔABC為STL模型中任意三角形，分層平面高z=zi。

根據(jù)AC的直線方程可得到：

(1)

可得：

(2)

同理可得：

(3)

2.2.2 三角形與切平面相交的情況分析

為簡化相交判斷條件，對相交三角形的z向坐標與分層高度zi進行差值處理，即：[(x1,y1,zmin-zi)(x2,y2,zmid-zi)(x3,y3,zmax-zi)]，然后運用差值處理后的z向坐標與0進行比較，從而判斷處于那種相交情況,應用2.2.1節(jié)中的交點計算公式計算交點。交點的記錄對zi坐標進行忽略，僅僅記錄交點x,y坐標，即:[(x13,y13)(x23,x23)],在繪制輪廓時對交點坐標進行循環(huán)賦zi值。經(jīng)過分析集合中各三角形與切平面共有7種相交情況如圖4所示。

三角形T1、T2、T3、…、T7分別為每種情況的示例，根據(jù)2.1.1節(jié)中三角形頂點的記錄方式，判斷三角形與切平面的相交處于何種情況的條件以及交點的記錄方式依次為：

(1)zmax-zi=0且zmid-zi<0，交點坐標記錄：[(x3,y3)(x3,y3)]。

(2)zmax-zi=0且zmid-zi=0，交點記錄：[(x2,y2)(x3,y3)]。

(3)(zmax-zi)×(zmid-zi)<0且(zmax-zi)×(zmin-zi)<0，交點記錄：[(x13,y13)(x23,y23)]。

(4)(zmax-zi)×(zmin-zi)<0且zmid-zi=0，交點記錄：[(x13,y13)(x2,y2)]。

(5)(zmax-zi)×(zmin-zi)<0且(zmid-zi)×(zmin-zi)<0。交點記錄：[(x13,y13)(x12,y12)]。

(6)zmin-zi=0 且zmid-zi>0，交點記錄：[(x1,y1)(x1,y1)]。

(7)zmin-zi=0 且zmid-zi=0，交點記錄：[(x1,y1)(x2,y2)]。

對于獲取的交點坐標，(1)與(6)、(2)與(7)、(3)與(5)、(4)分別存入獨立的臨時數(shù)組，以方便對影響拓撲關系的交點的處理。

2.3 拓撲關系分析

根據(jù)STL模型連續(xù)三角形面片與切平面的相交情況，依據(jù)交點數(shù)組冗余信息重建的拓撲關系可以總體分為圖5所示兩種情況。圖5a所示的一般拓撲關系根據(jù)重建之后的拓撲關系，獲得的有序點列不會造成輪廓不封閉的現(xiàn)象。圖5b所示的特殊拓撲關系在進行拓撲重建時將會受到三角形T2、T5、T7、T3或T6的影響，從而造成輪廓不封閉現(xiàn)象。可將影響拓撲關系重建的三角形分為兩種情況即：兩個頂點與切平面相交與三角形一個頂點與切平面相交。前者應對交點坐標進行去重操作，后者根據(jù)與相鄰三角形的交點坐標重復的特征進行刪除操作。兩種情況余留下的交點坐標即為不影響拓撲關系重建的交點坐標。

2.3.1 交點坐標去重

將兩個頂點與切平面相交的情況，視為情況1，進行去重操作。具體步驟如下：

Step1：將此臨時數(shù)組交點坐標以x進行升序排序，若x坐標值相同則以y坐標值進行升序排序，即：[(xmin,y1)(xmax,y2)]。

Step2：將數(shù)組的第一行坐標賦值給一個變量如變量a，并存入另一臨時數(shù)組，并將此行坐標從臨時數(shù)組中刪除。

Step3：以變量a進行搜索該數(shù)組，若在臨時數(shù)組中搜索到與之相同的坐標信息便將此行坐標從臨時數(shù)組中刪除。

Step4：判斷臨時數(shù)組是否為空，若數(shù)組為空搜索結(jié)束，變量a坐標所存入的另一臨時數(shù)組代替原臨時數(shù)據(jù)，變?yōu)榍闆r1的交點數(shù)組，若不為空，重復上述Step2、Step3步驟。

2.3.2 交點坐標刪除

三角形一個頂點與切平面相交的情況，視為情況2，根據(jù)相鄰交點坐標重復進行刪除操作。具體步驟如下：

Step1：將此數(shù)組的具有相同坐標的行進行刪除并保留一個，得到不重復交點數(shù)據(jù)組成的數(shù)組。

Step2：將得到的數(shù)組每一行的第一個交點坐標，與2.2.2節(jié)情況(4)的交點存入的臨時數(shù)組和上述情況1的交點數(shù)組的交點坐標，進行比較。

Step3：若存在相同，記錄下該行在此數(shù)組中的行數(shù)。

Step4：將此數(shù)組中被記錄下的行數(shù)進行對應刪除。

2.4 拓撲關系的重建

由于STL模型丟失了原物理模型之間的拓撲關系，三角形的記錄雜亂無章，需要對其重建三角形之間的拓撲關系。由于STL模型三角形之間存在共邊原則，切片過程中存在的交點冗余信息，基于此信息利用逐點識別與剔除的思想重建拓撲關系。如圖6所示，三角形面片T1、T2根據(jù)STL文件規(guī)則共用一條邊，T1與T2交點記錄形式分別為[ab]、[cd]，其中由于b與c坐標值相等，若以b坐標搜索整個交點數(shù)組進行三角形拓撲關系的構(gòu)建，那么c坐標便為b坐標的重復交點，視為冗余信息。具體步驟如下：

Step1：將交點數(shù)組的第一行賦值給一個變量如d，并存入有序數(shù)組并將此行坐標從整個交點數(shù)組中刪除。

Step2：應用變量d的第二點坐標，進行整個交點數(shù)組的搜索,記錄此時交點數(shù)組行數(shù)k1。

Step3：搜索到與第二點坐標相同的坐標，并將此行坐標以d第二點為第一點進行重新排列，并將排列后的此行坐標賦值給d與有序數(shù)組，并從交點數(shù)組中刪除該行，記錄下刪除后的交點數(shù)組行數(shù)k2，k1=k1-1。

Step4：判斷k1=k2是否成立,若相等則說明有序點列未形成一個封閉的截面輪廓，重復Step2、Step3；不相等說明在交點數(shù)組中己不存在該d的冗余信息，有序點列己形成一個封閉的截面輪廓。

Step5：判斷交點數(shù)組是否為空，若為空，說明當前切片層內(nèi)的其余封閉輪廓完全獲得結(jié)束循環(huán)；不為空，說明該切片層內(nèi)存在其余的封閉輪廓，重復上述Step1、Step2、Step3、Step4，直至為空。

2.5 有序交點的獲取與連接

拓撲關系重建完成后，需要從中獲取有序點列依次進行連接，形成封閉的截面輪廓。對應關系如圖7所示。三角形面片T1、T2、T3、…、Tk根據(jù)上述重建的拓撲關系可得到每個三角形交點有序排列，如：[ab]、[bc]、[cd]、…、[ja]。從中可以看出上述有序點列重復，需要獲取單個有序坐標，即：[a]、[b]、[c]、…、[j]、[a]，依次進行連接，形成封閉多邊形。

具體步驟如下：

Step1：初始坐標點插入有序數(shù)組最后一行，形成新的有序數(shù)組。獲取有序數(shù)組的第一個交點坐標(有序數(shù)組的第一列與第二列元素，獲得依次連接的交點坐標)。

Step2：對獲取后的交點依次賦值zi，成為完整的三維坐標。

Step3：依次進行連接，得到二維截面輪廓。

3 實例驗證

為了檢驗上述算法的可行性與可靠性，給出了圖8所示兩個實例進行驗證。圖9與圖10分別為獎杯與飾品的模型切片效果圖，圖9a與圖10a分別為STL切片模型，圖9b與圖10b分別為其中某層切片輪廓。可見，該算法對STL模型的切片處理有較好的效果。

4 結(jié)語

(1)建立只與當前切平面相交三角形的集合，可減少切平面與三角形相交判斷次數(shù)，從而提高了切片效率。

(2)分析了特殊拓撲關系的存在情況，對于影響拓撲關系的兩種情況的交點，依據(jù)各自特點進行刪除操作，保證有序點列形成封閉截面輪廓，不受無關點列的影響。

(3)基于逐點識別與剔除思想的拓撲關系重建，有效減少了遍歷交點數(shù)組的次數(shù)，提高了切片效率。

[1]李曉麗, 馬健雄,李萍，等.打印技術及應用趨勢[J].自動化儀表, 2014, 35(1):1-5.

[2]韓霞, 楊恩源.快速成型技術與應用[M].北京:機械工業(yè)出版社, 2012.

[3]黃麗.基于STL模型分層算法研究與軟件實現(xiàn)[D].泰安：山東農(nóng)業(yè)大學，2016.

[4] Zhengyan Zhang, Sanjay Joshi. An improved slicing algorithm with efficient contour construction using STL files[J]. Int J Adv Manuf Technol, 2015, 80(5):1347-1362.

[5]王彥云, 陳鴻, 謝明師，等.基于哈希表的STL格式文件拓撲重建的算法[J].現(xiàn)代制造工程, 2015(12):61-64.

[6] Chakraborty D, ChoudhuryAR. A semi-analytic approach for direct slicing of free form surfaces for layered manufacturing[J]. Rapid Prototyping Journal, 2008, 13(4):256-264.

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

[8]王素，劉恒，朱心雄.模型的分層鄰接排序快速切片算法[J].計算機輔助設計與圖形學學報, 2011, 23(4):600-605.

[9]朱君，郭戈，顏永年.快速成形制造中基于模型連續(xù)性的快速分層算法研究[J].中國機械工程, 2000, 11(5):549-554.

[10] Hayasi MT, Asiabanpour B.A new adaptive slicing approach for the fully dense freeform fabrication (FDFF) process[J].J Intell Manuf, 2013, 24(4):683-694.

[11] S Sikder，A Barari, HA Kishawy. Global adaptive slicing of NURBS based sculptured surface for minimum texture error in rapid prototyping[J]. Rapid Prototyping Journal, 2015, 21(6):649-661.

[12]曹麗娜, 田曉霞.三維CAD技術在機械設計中的應用研究[J].裝備制造技術, 2014, (6):97-99.

[13]張倩.逆向工程在產(chǎn)品創(chuàng)新設計中的實踐應用研究[D].太原：太原理工大學，2014.