江本赤，王建彬，王　剛

（安徽工程大學(xué) 機(jī)械與汽車工程學(xué)院，安徽 蕪湖241000）

3D打印是以數(shù)字模型文件為基礎(chǔ)，可將設(shè)計(jì)理念快速、準(zhǔn)確地轉(zhuǎn)換為具有一定功能原型的技術(shù)［1］。大多數(shù)3D打印系統(tǒng)都是先建立CAD模型，再設(shè)定精度將CAD模型轉(zhuǎn)換為STL模型，然后對STL模型進(jìn)行切片處理。切片處理是3D打印中的重要步驟，切片處理后生成的一系列二維封閉多邊形輪廓是3D打印的基礎(chǔ)。STL文件存在多種缺陷，如：在記錄三角形頂點(diǎn)坐標(biāo)信息時(shí)存在冗余；在將CAD模型轉(zhuǎn)換為STL模型時(shí)，存在精度損失，且精度損失越小，STL文件越大；存在信息缺乏、三角形間無任何拓?fù)潢P(guān)系等。這些造成了STL模型切片算法效率較低，但因?yàn)镾TL文件生成簡單、輸出廣泛適用、易于切片處理等優(yōu)點(diǎn)，所以對STL模型切片算法研究仍然是研究的主流［2-4］。

目前，研究人員已提出了多種STL模型切片算法。如：王素等［5］采用鄰接插入法建立三角形間的鄰接關(guān)系，根據(jù)三角形頂點(diǎn)坐標(biāo)反求與該三角形相交的切片平面，利用已經(jīng)建立的三角形間鄰接關(guān)系獲取有序的交點(diǎn)，完成對STL模型的切片；田明海［6］建立層變邊數(shù)組與初始層數(shù)的鄰接邊順序鏈表，利用層變邊數(shù)組與初始層數(shù)的鄰接邊鏈表進(jìn)行斷鏈與合鏈操作，求取下一層的鄰接邊順序鏈表，進(jìn)而建立整體的鄰接邊順序鏈表，完成對STL模型的切片；黃麗［7］首先建立與當(dāng)前切平面相交的三角形集合，然后根據(jù)交點(diǎn)間的冗余特性構(gòu)建三角形間的拓?fù)潢P(guān)系，完成對STL模型的切片；鐘山等［8］首先設(shè)定角度閾值并求取垂直切片輪廓線的點(diǎn)切線與水平分層面的切線角，然后比較角度閾值與切線角的大小決定分層的厚度，最后利用三角形的鄰接關(guān)系完成對STL模型的切片；Zhang等［9］建立與切平面相交的三角形集合，將每個(gè)三角形與切片平面相交的兩條邊設(shè)定為前邊與后邊，利用前邊與后邊的關(guān)系重建拓?fù)潢P(guān)系，獲得鄰接邊順序鏈表，完成對STL模型的切片。

考慮到STL模型存在冗余信息，我們在吸收上述算法優(yōu)點(diǎn)的基礎(chǔ)上，提出了一種STL模型快速切片算法。在讀取STL文件時(shí)，確定STL模型中與每層切片平面相交的三角形，將三角形索引值和三條邊存入切片面結(jié)構(gòu)數(shù)組，將三角形與切片平面相交的兩條邊、與邊所屬的三角形面片的索引值存入每層切片平面的切片邊結(jié)構(gòu)數(shù)組。根據(jù)每層切片邊數(shù)組中的三角形信息，利用逐邊識(shí)別與剔除的思想和相鄰切片層間的三角形拓?fù)潢P(guān)系具有繼承性的特點(diǎn)重建拓?fù)潢P(guān)系，將建立完成的拓?fù)潢P(guān)系和求出的交點(diǎn)坐標(biāo)依次存入有序邊點(diǎn)數(shù)組中。從有序邊點(diǎn)數(shù)組中獲取有序交點(diǎn)并依次連接得到二維封閉輪廓。

1　STL文件信息存儲(chǔ)特點(diǎn)

STL文件格式是由美國3D SYSTEMS公司于1988年制定的［1］。STL模型由CAD模型表面三角化處理生成，但轉(zhuǎn)換成STL模型后其原有的拓?fù)潢P(guān)系會(huì)丟失。STL文件中每個(gè)三角形的定義都包括以逆時(shí)針順序記錄的頂點(diǎn)坐標(biāo)與指向模型外側(cè)的單位法向量。

STL文件有兩種格式：二進(jìn)制格式與ASCII格式。二進(jìn)制采用固定字節(jié)給出三角形面片的幾何信息，ASCII格式以關(guān)鍵字為標(biāo)志逐行給出三角形面片的幾何信息。由于ASCII格式比二進(jìn)制格式更具可讀性和直觀性且方便對數(shù)據(jù)做進(jìn)一步處理，在對STL模型進(jìn)行分層時(shí)，普遍選擇STL文件的ASCII格式，如圖1所示。

圖1　STL文件的ASCII格式結(jié)構(gòu)

2　STL模型分層算法

對STL模型進(jìn)行分層時(shí)，其分層方向一般選取與z軸平行的方向。

2.1　STL文件的處理

在讀取STL文件時(shí)，建立分層面結(jié)構(gòu)數(shù)組存儲(chǔ)STL文件中記錄的三角形數(shù)據(jù)，該數(shù)組包含三角形面片的索引值和三角形的邊，其中每條邊的頂點(diǎn)坐標(biāo)都按照z坐標(biāo)值的升序排列。在建立分層面結(jié)構(gòu)數(shù)組的同時(shí)，也針對每個(gè)分層平面建立分層邊結(jié)構(gòu)數(shù)組，該結(jié)構(gòu)數(shù)組包含三角形與分層平面相交的兩條邊及與邊所屬的三角形面片的索引值。這里，三角形兩條邊中任意一條若是首次與切平面相交則被記錄，不是則不被記錄；若三角形的一條邊在切平面上，則記錄另外兩條首次與分層平面相交的邊，整個(gè)三角形在切平面上不會(huì)被記錄。

如圖2所示，任意給定一個(gè)三角形Tk（k=1，2，…，m）， 該三角形三個(gè)頂點(diǎn)坐標(biāo)分別為 Vkmin（xk1，yk1，zkmin）、Vkmid（xk2，yk2，zkmid）和 Vkmax（xk3，yk3，zkmax），其中 zkmax≥zkmid≥zkmid，在分層面數(shù)組中的記錄形式為［Tk，Sk1（Vkmin，Vkmid），Sk2（Vkmid，Vkmax），Sk3（Vkmin，Vkmax）］。假設(shè)與三角形 Tk相交的分層平面分別為 Layer（i）、Layer（i+1）和 Layer（i+2）（i=1，2，…，n-2）。 在 Layer（i）分層中，三角形的兩條邊 Sk1和 Sk3首次與 Layer（i）分層平面相交，因此它們在 Layer（i）的分層邊數(shù)組中記錄方式為［Tk，Sk1（Vkmin，Vkmid），Sk3（Vkmin，Vkmax）］；在 Layer（i+1）分層中，三角形的兩條邊 Sk1和 Sk3與 Layer（i+1）分層相交，但并不是首次與切平面相交，因此它們在Layer（i+1）的分層邊數(shù)組中不記錄；在 Layer（i+2）分層中，三角形的兩條邊 Sk1、Sk2中 Sk2首次與 Layer（i+2）分層平面相交，因此它們在Layer（i+2）的分層邊數(shù)組中記錄方式為［Tk，Sk2（Vkmid，Vkmax），Sk3（Vkmin，Vkmax）］。

圖2　三角形與分層平面相交示意圖

2.2　交點(diǎn)的計(jì)算

在STL模型的分層算法中，高效獲取各三角形與分層平面的交點(diǎn)數(shù)據(jù)可以提高分層算法的效率。設(shè)圖2 中三角形 Tk的 Sk3邊與 Layer（i）和 Layer（i+1）分層平面的交點(diǎn)分別為點(diǎn) pi（xi，yi，zi）和 pi+1（xi+1，yi+1，zi+1），根據(jù)邊Sk3的直線方程

可得點(diǎn) pi（xi，yi，zi）坐標(biāo)

同理可得點(diǎn) pi+1（xi+1，yi+1，zi+1）坐標(biāo)

其中：zi為 Layer（i）分層平面的高度，zi+1為 Layer（i+1）分層平面的高度。

若三角形的某一條邊首次與切平面相交，則利用式（4）求出交點(diǎn)坐標(biāo)；若該邊再與其他切平面相交，則利用式（5）求出交點(diǎn)坐標(biāo)。該方法簡化了交點(diǎn)的計(jì)算，提高了分層效率。

2.3　拓?fù)潢P(guān)系的重建

因?yàn)樵贑AD模型轉(zhuǎn)換為STL模型時(shí)丟失了原有的拓?fù)潢P(guān)系，所以STL文件中記錄的三角形毫無順序。為了獲取有序的交點(diǎn)，需要重建三角形間的拓?fù)潢P(guān)系。我們根據(jù)STL模型本身的冗余信息，利用逐邊識(shí)別與剔除的思想及相鄰分層間的三角形拓?fù)潢P(guān)系具有繼承性的特點(diǎn)重建拓?fù)潢P(guān)系。如圖3所示，根據(jù)STL文件的冗余信息，三角形T1與三角形T2共用一條邊，可得到S13=S23。因此，利用三角形T1的邊S13可快速查找到三角形T2，重建三角形間的拓?fù)潢P(guān)系。

圖3　冗余信息示意圖

三角形間的拓?fù)潢P(guān)系可以分為簡單拓?fù)潢P(guān)系與特殊拓?fù)潢P(guān)系，如圖 4 所示。 在圖 4（a）中，與 Layer（i）、Layer（i+1）和 Layer（i+2）分層平面相交的三角形沒有改變，因此不需要建立 Layer（i+1）及 Layer（i+2）分層平面相交三角形間的拓?fù)潢P(guān)系，可以繼承已經(jīng)建立的與Layer（i）分層平面相交三角形間的拓?fù)潢P(guān)系。在圖 4（b）中，與 Layer（i）、Layer（i+1）分層平面相交的三角形發(fā)生改變，需要重新建立與Layer（i+1）分層平面相交三角形間的拓?fù)潢P(guān)系。在Layer（i）分層平面中，已經(jīng)建立的三角形間的拓?fù)潢P(guān)系為［T1，T3，T5，T7，T8］，則在建立與 Layer（i+1）分層平面相交的三角形間的拓?fù)潢P(guān)系時(shí)，先在Layer（i）分層的三角

撲關(guān)系中刪除與Layer（i+1）分層平面不相交的

形，標(biāo)記只有一條邊與Layer（i+1）分層相交的三角形，得到［T1，T8］，再獲取 Layer（i+1）分層平面的分層邊數(shù)組信息［T1，T4，T2，T6，T8］，最后根據(jù)該信息重新建立Layer（i+1）分層中三角形間的拓?fù)浣Y(jié)構(gòu)［T1，T4，T2，T6，T8］。STL 模型中與 Layer（i+1）、Layer（i+2）分層平面相交的三角形并沒有改變，因此Layer（i+2）分層三角形拓?fù)潢P(guān)系可繼承Layer（i+1）分層的三角形間拓?fù)潢P(guān)系。

拓?fù)潢P(guān)系重建算法步驟如下。

Step1：讀取Layer（1）分層的分層邊數(shù)組信息。

Step2：任意獲取Layer（1）分層邊數(shù)組中的一個(gè)三角形Tk，以該三角形與切平面相交的一條邊Sk1遍歷整個(gè)Layer（1）分層邊數(shù)組，找到三角形Tk的鄰接三角形然后將有關(guān)三角形Tk與的信息從Layer（1）分層邊數(shù)組中刪除，同時(shí)將相交邊與交點(diǎn)數(shù)據(jù)存入有序邊點(diǎn)數(shù)組，如其中，Ik與為通過式（4）計(jì)算出的邊Sk1、與分層平面的交點(diǎn)。

Step4：讀取 Layer（i）（i=2，3，…，n）的分層邊數(shù)組信息，在Layer（i-1）分層三角形拓?fù)潢P(guān)系中刪除與Layer（i）分層平面不相交的三角形，標(biāo)記只有一條邊與Layer（i）分層平面相交的三角形，交點(diǎn)信息通過式（5）進(jìn)行更新。

Step5：在 Layer（i）的分層邊數(shù)組中找到與標(biāo)記三角形對應(yīng)的三角形索引值，以該三角形為Tk，對于任意第Layer（i）分層，利用上述方法進(jìn)行拓?fù)渲亟?，直至找到另一個(gè)標(biāo)記三角形（即與Layer（i）分層平面相交但尚未記錄在Layer（i）分層邊數(shù)組中的三角形），利用所繼承Layer（i-1）分層內(nèi)的拓?fù)潢P(guān)系，獲取封閉二維輪廓。

Step6：判斷 Layer（i）的分層邊數(shù)組是否為空，若不為空，則說明存在其他封閉輪廓，依次利用上述方法直至Layer（i）的邊數(shù)組為空，獲取該層內(nèi)所有的封閉輪廓。

圖4　拓?fù)潢P(guān)系

2.4　有序交點(diǎn)的獲取與連接

完成拓?fù)潢P(guān)系重建之后，從有序邊點(diǎn)數(shù)組中獲取有序交點(diǎn)并依次連接，即可形成封閉的二維截面輪廓。如圖5所示，對于Layer（t）分層平面，建立的有序點(diǎn)邊數(shù)組為獲取的有序交點(diǎn)數(shù)組其中I1=I3。舍棄重復(fù)的坐標(biāo)值I3，將有序交點(diǎn)坐標(biāo)值依次進(jìn)行連接，形成封閉的二維截面輪廓。

圖5　生成有序交點(diǎn)序列

3　實(shí)例驗(yàn)證

以圖6所示的某法蘭STL模型為例，檢驗(yàn)算法的分層效果。該模型具有較復(fù)雜的幾何結(jié)構(gòu)，有助于評判復(fù)雜二維截面輪廓的正確性。

利用本算法對圖6中的STL模型進(jìn)行分層，獲得了圖7（a）所示的分層效果，圖7（b）為其中一個(gè)層片的二維輪廓情況。由圖7可以看出，分層模型可清晰地包絡(luò)出原始STL模型，其中的一個(gè)層片亦完全符合模型的局部幾何特征，這驗(yàn)證了算法的有效性和可行性。

圖6　某法蘭的STL模型

圖7　模型分層效果

4　結(jié)論

基于STL模型文件信息的冗余特性分析，通過判斷三角形各邊的共用情況，建立了相應(yīng)的拓?fù)潢P(guān)系，并獲取了封閉的二維輪廓，進(jìn)而實(shí)現(xiàn)了對STL模型的分層操作。通過對一個(gè)典型模型的分層實(shí)驗(yàn)證實(shí)了該算法可行性。通過以上研究工作可以得出以下結(jié)論：

（1）在讀取STL文件的同時(shí)，確定STL模型中與各分層平面相交的三角形集合，有利于減少三角形與分層平面間位置關(guān)系的判斷次數(shù)。

（2）在求三角形與分層平面間的交點(diǎn)時(shí)，利用相鄰層片交點(diǎn)間的關(guān)系，可快速獲取交點(diǎn)坐標(biāo)，并可避免分層交點(diǎn)的重復(fù)計(jì)算。

（3）基于逐邊識(shí)別與剔除的思想建立拓?fù)潢P(guān)系，利用拓?fù)潢P(guān)系的繼承性，可減少遍歷次數(shù)，有效提高計(jì)算效率。