基于STL文件的3D打印分層算法

作者/強(qiáng)邵雯，西安市第八十三中學(xué)

基于STL文件的3D打印分層算法

作者/強(qiáng)邵雯，西安市第八十三中學(xué)

目前，3D打印技術(shù)逐漸成熟，在日常用品、工業(yè)設(shè)計(jì)、建筑、醫(yī)療和教育等方面都有所應(yīng)用。本文首先介紹了3D打印的基本原理及工作流程，分析了其誤差來(lái)源并把重點(diǎn)放在對(duì)分層算法的研究上。本文選定基于STL文件的分層算法進(jìn)行了更深入的研究。最后，對(duì)目前主流的分層算法進(jìn)行了分析，介紹了一種基于分組排序的加權(quán)有向圖遞歸分層算法。

3D打印；STL文件；分層算法

引言

當(dāng)今世界，3D打印技術(shù)的出現(xiàn)和發(fā)展，有效地提高了產(chǎn)品開(kāi)發(fā)和研究的效率，縮短了產(chǎn)品的開(kāi)發(fā)時(shí)間，成為了企業(yè)間競(jìng)爭(zhēng)成敗的關(guān)鍵。因此這項(xiàng)技術(shù)的研發(fā)與優(yōu)化受到了世界各地不同國(guó)家的廣泛關(guān)注。3D打印具有成型快，產(chǎn)品精度高，生產(chǎn)過(guò)程無(wú)污染等優(yōu)點(diǎn)，這也使得這項(xiàng)技術(shù)有著巨大的潛力和廣闊的發(fā)展前景。所以對(duì)這項(xiàng)技術(shù)的研究及優(yōu)化有著重大的意義[1]。

在進(jìn)行3D打印時(shí)，我們最關(guān)心的性能指標(biāo)主要是打印的精度，即實(shí)際打印出來(lái)的實(shí)物與模型的相似性。一般可以用體積誤差來(lái)衡量3D打印產(chǎn)生的誤差，即3D打印得到的實(shí)體所耗費(fèi)的材料量與理論模型需要的材料量之間的差值。在進(jìn)行3D打印時(shí)，主要會(huì)存在兩種情況的誤差。第一種可能存在的誤差是在格式轉(zhuǎn)換中產(chǎn)生的，即將CAD模型轉(zhuǎn)化為STL標(biāo)準(zhǔn)格式文件過(guò)程中產(chǎn)生的誤差；而第二種誤差是階梯效應(yīng)，即在進(jìn)行分層切片時(shí)，由于打印機(jī)能實(shí)現(xiàn)的最小打印厚度有限，造成的層與層之間所產(chǎn)生的誤差[2]。

1. 3D打印分層算法

■1.1 分層算法簡(jiǎn)介

3D打印分層技術(shù)一般包括兩個(gè)階段，首先是獲取模型與各層切平面交線段的集合，然后是將交線段進(jìn)行首尾相連以獲得封閉的輪廓環(huán)。一個(gè)模型文件中可能包括非常多的三角形面片，而且這些三角形面片的排列是無(wú)序、隨機(jī)的，因此無(wú)論是計(jì)算交線段還是對(duì)交線段進(jìn)行整理排序的效率都可能很低。由此可知主要有以下三點(diǎn)影響分層算法的速度：一是判斷三角形面片與切平面的位置關(guān)系；二是求解面片與切平面的交線段；三是生成切平面的輪廓線。如何提高分層切片的效率是3D打印技術(shù)優(yōu)化的重要問(wèn)題，所以本文主要基于分層算法對(duì)如何提高打印時(shí)的效率進(jìn)行研究。

■1.2 主流的3D打印分層算法

目前主流的分層算法主要包括以下幾個(gè)類(lèi)別：

(1)基于STL文件的分層算法：該方法首先將CAD模型轉(zhuǎn)化為通用的STL格式，再對(duì)其進(jìn)行分層處理，得到分層數(shù)據(jù)。這種方法的優(yōu)點(diǎn)是格式簡(jiǎn)單，有統(tǒng)一標(biāo)準(zhǔn)，且實(shí)現(xiàn)的方式相對(duì)簡(jiǎn)單，成熟度較高等。但存在的主要缺點(diǎn)是對(duì)復(fù)雜模型，分層精度較低且耗時(shí)較長(zhǎng)。

(2)基于CAD模型的分層算法：該方法跳過(guò)了轉(zhuǎn)換為STL格式文件的步驟，直接對(duì)CAD模型進(jìn)行分層處理，因此提高了效率。這種方法的一大優(yōu)點(diǎn)是避免了在標(biāo)準(zhǔn)格式轉(zhuǎn)換過(guò)程中引入的誤差，因而提高了產(chǎn)品的精度。但缺點(diǎn)是缺乏統(tǒng)一標(biāo)準(zhǔn)，很難得到廣泛的應(yīng)用。

(3)基于點(diǎn)云數(shù)據(jù)的分層算法:該方法是通過(guò)現(xiàn)有的掃描技術(shù)先獲取實(shí)體模型的點(diǎn)云數(shù)據(jù)，再根據(jù)該數(shù)據(jù)建立STL模型文件，在此基礎(chǔ)上進(jìn)行分層處理。通過(guò)這種算法所獲得的模型精度較高，但其主要問(wèn)題是實(shí)現(xiàn)難度很高且很難保證點(diǎn)云數(shù)據(jù)的正確性。

綜上，本文選擇基于STL文件的算法進(jìn)行研究，主要因?yàn)樗且粋€(gè)主流的數(shù)據(jù)標(biāo)準(zhǔn)，具有較好的通用性，研究的算法可以很好地應(yīng)用到大部分3D打印機(jī)上。另外該類(lèi)算法的研究比較成熟，具有很好的研究基礎(chǔ)，所以選擇該類(lèi)算法進(jìn)行深入的研究[3]。

■1.3 幾種基于STL文件的分層算法

STL文件是一種用若干個(gè)空間三角形面片來(lái)近似表示實(shí)體表面的數(shù)字格式文件。通過(guò)文件記錄的各個(gè)三角形面片的頂點(diǎn)位置和法向量信息，即可恢復(fù)出與原實(shí)體高度相近的三維模型。一般而言，STL文件只保留實(shí)體名稱、三角形面片的個(gè)數(shù)、各面片的頂點(diǎn)信息及法向量，所含的信息量雖少但足以滿足實(shí)際的應(yīng)用，其好處在于占用的內(nèi)存小且可以保證應(yīng)用的通用性。

STL模型需要遵循四大法則：一是右手法則，即每個(gè)三角形面片的法向量與其三個(gè)頂點(diǎn)的次序滿足右手法則。二是定點(diǎn)法則，即模型中每?jī)蓚€(gè)三角形面片有且僅有兩個(gè)頂點(diǎn)被共享。三是邊法則，即模型中每一條邊最多只能被兩個(gè)三角形面片共享。四是面法則，即每個(gè)三角形面片有且僅有三個(gè)相鄰的三角形面片。這四大法則很好地避免了分層算法在對(duì)面片進(jìn)行交線段求解時(shí)重復(fù)性地對(duì)同一個(gè)對(duì)象進(jìn)行運(yùn)算。

以下介紹主流的基于STL文件的分層算法[4]。

1.3.1 直接求交線的分層算法

該算法分層時(shí)首先通過(guò)預(yù)先的計(jì)算，確定一個(gè)最優(yōu)分層方向，目的是盡量減少分層后所產(chǎn)生的體積誤差。然后確定分層高度的最小值及最大值并確定分層厚度。在設(shè)定當(dāng)前分層高度為最小值后，遍歷所有三角形面片，判斷各面片頂點(diǎn)與當(dāng)前平面的位置關(guān)系。根據(jù)位置關(guān)系，對(duì)與當(dāng)前分層切面有交線的面片進(jìn)行交線段求解運(yùn)算，得到三角形面片與切平面的兩個(gè)交點(diǎn)。再根據(jù)三角形之間的位置關(guān)系判斷交線的順序，連接各個(gè)交線，形成閉合的輪廓環(huán)，得到該模型在當(dāng)前高度的截面輪廓。接著逐層提高分層切面的高度，重復(fù)以上步驟，直至超過(guò)該模型的最大高度，即完成了該模型的分層過(guò)程。

1.3.2 基于模型毗鄰?fù)負(fù)湫畔⒌姆謱铀惴?/p>

該算法首先讀取STL模型信息，并對(duì)所有三角形面片進(jìn)行預(yù)處理，得到模型的毗鄰?fù)匮a(bǔ)信息。然后開(kāi)始分層，先尋找首個(gè)與當(dāng)前切平面相交的面片，進(jìn)行求交點(diǎn)的運(yùn)算，得到交線段。再根據(jù)之前建立的拓?fù)湫畔ⅲ玫脚c其相鄰的面片地址,再選擇該臨近面片進(jìn)行求交點(diǎn)的運(yùn)算，并不斷往下追蹤，最終得到與該切平面相交的所有交線段，然后根據(jù)它們的順序連接成輪廓環(huán)。這種方法的優(yōu)點(diǎn)是每個(gè)交點(diǎn)的計(jì)算只有一次，且提前獲取了毗鄰?fù)負(fù)湫畔?在生成輪廓線時(shí)則無(wú)需再判斷各個(gè)交線段的位置關(guān)系,效率可大大提高。但需提前建立整個(gè)模型的拓?fù)湫畔ⅲ撨^(guò)程較為復(fù)雜且難度高，對(duì)內(nèi)存的消耗大，且十分耗時(shí)。

■1.4 基于分組排序的加權(quán)有向圖遞歸分層算法

基于分組排序的算法的實(shí)現(xiàn)難度、效率及復(fù)雜度相對(duì)于其他算法具有很大的優(yōu)勢(shì)。本文在分組排序的基礎(chǔ)上，利用加權(quán)有向圖的概念，結(jié)合遞歸搜索的算法思想，實(shí)現(xiàn)了一種快速高效的分層切片算法。以下針對(duì)算法實(shí)現(xiàn)過(guò)程進(jìn)行具體的介紹。

1.4.1 分層矩陣的建立

假設(shè)當(dāng)前切平面i高度為Z[i]，當(dāng)前訪問(wèn)的面片j在分層方向的最大值為Zmax[j]最小值為Zmin[j]；設(shè)分層厚度為為ZΔ，最小值為Zmin[j]，則與該切平面相交的最低切平面m和最高切平面 n分別為：

由上式則確定了與面片j相交的所有分層切面的序號(hào)，并可根據(jù)m值的大小將面片放入對(duì)應(yīng)的分層矩陣中。注意到如果滿足ZmaxminZ= ，則表明該三角形面片與切片方向垂直，與切平面不會(huì)有交點(diǎn)，可以把它刪除，不放進(jìn)分層矩陣中。

1.4.2 基于STL的加權(quán)有向圖數(shù)據(jù)結(jié)構(gòu)建立

由于加權(quán)有向圖能很好的表示點(diǎn)與邊的位置關(guān)系，因此本文將其應(yīng)用到分組排序的分層算法中，以表示活性面片表中所有面片的局部拓?fù)湫畔ⅰＦ渲饕^(guò)程為：首先為活性面片表的每個(gè)三角形面片賦予唯一的編號(hào)ID（0,1,2,3,…,N）,并把它們近似為圖上的一個(gè)點(diǎn)。然后根據(jù)面片的相鄰關(guān)系，在相鄰的兩個(gè)面片近似成的頂點(diǎn)間連接一條有向邊，從而建立一個(gè)有向圖。為每條有向邊賦予不同的權(quán)值，形成加權(quán)有向圖，因此得以反映模型的局部拓?fù)湫畔ⅰ⒓訖?quán)有向圖用“鄰接表”的數(shù)據(jù)格式進(jìn)行表示，并將其添加到原STL格式的每個(gè)三角形面片的數(shù)據(jù)結(jié)構(gòu)中，形成具有拓?fù)湫畔⒌臄?shù)據(jù)，便可儲(chǔ)存于計(jì)算機(jī)上[5]。

2.結(jié)論

當(dāng)今時(shí)代3D打印正在飛速發(fā)展，對(duì)該技術(shù)的不斷優(yōu)化與創(chuàng)新也成為了在市場(chǎng)競(jìng)爭(zhēng)中的重要因素之一。本文通過(guò)對(duì)幾種傳統(tǒng)方法的學(xué)習(xí)，在此基礎(chǔ)上利用加權(quán)有向圖和遞歸搜索的思想，提出了一種新的優(yōu)化的算法方案，提高了分層的效率。3D打印是目前乃至將來(lái)都很有發(fā)展前景的一項(xiàng)工程，在今后的研究中，優(yōu)化、創(chuàng)新出新的算法方法對(duì)于人類(lèi)科學(xué)的進(jìn)步、世界的進(jìn)步都有著毋庸置疑的重要作用。

＊ [1]劉紅霞,3D打印分層方向優(yōu)化與分層算法研究[M], 西安電子科技大學(xué), 2014

＊ [2]楊猛，3D打印驅(qū)動(dòng)電路設(shè)計(jì)及文件切片算法研究[M]，北京印刷學(xué)院，2015

＊ [3]趙方，3D打印中基于STL文件的分層算法比較[M]，大連理工大學(xué)，2016

＊ [4]羅中明，3D打印算法研究及應(yīng)用[M]，北京印刷學(xué)院，2014

＊ [5]盧凱，基于FSM的3D打印分層處理技術(shù)研究[M]，長(zhǎng)春工業(yè)大學(xué)，2015