一種面向3D打印技術(shù)的STL模型快速分層算法

江本赤，王建彬，王　剛

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

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

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

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

1　STL文件信息存儲特點

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

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

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

2　STL模型分層算法

對STL模型進行分層時，其分層方向一般選取與z軸平行的方向。

2.1　STL文件的處理

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

如圖2所示，任意給定一個三角形Tk（k=1，2，…，m）， 該三角形三個頂點坐標分別為 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　交點的計算

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

可得點 pi（xi，yi，zi）坐標

同理可得點 pi+1（xi+1，yi+1，zi+1）坐標

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

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

2.3　拓撲關(guān)系的重建

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

圖3　冗余信息示意圖

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

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

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

拓撲關(guān)系重建算法步驟如下。

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

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

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

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

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

圖4　拓撲關(guān)系

2.4　有序交點的獲取與連接

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

圖5　生成有序交點序列

3　實例驗證

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

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

圖6　某法蘭的STL模型

圖7　模型分層效果

4　結(jié)論

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

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

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

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