基于CuraEngine 的3D 打印模型切片算法研究＊

邵乙迪，張士亨，李博文

（季華實(shí)驗(yàn)室新型增材制造研究院，廣東 佛山 528000）

3D 打印技術(shù)是以三維模型數(shù)據(jù)為基礎(chǔ)，通過層層堆積成型的一種新型制造技術(shù)。3D 打印技術(shù)通過對(duì)CAD 軟件設(shè)計(jì)生產(chǎn)的三維模型進(jìn)行切片處理，將三維模型“降維” 到二維輪廓，再通過相應(yīng)算法對(duì)輪廓進(jìn)行路徑規(guī)劃和填充，形成了打印設(shè)備能夠識(shí)別的加工數(shù)據(jù)文件，接下來設(shè)備只要根據(jù)數(shù)據(jù)文件中的位置和工藝參數(shù)等信息便可以逐層進(jìn)行打印，直到零件加工完成。與傳統(tǒng)減材制造技術(shù)相比，3D 打印能夠通過三維模型數(shù)據(jù)直接進(jìn)行生產(chǎn)制造，無須像傳統(tǒng)加工制造那樣將模型通過人工轉(zhuǎn)化加工圖紙，節(jié)省了零件成型所需的模具加工成本，簡化了零件的加工過程，也突破了傳統(tǒng)加工制造方式對(duì)設(shè)計(jì)的約束，能夠成型拓?fù)浣Y(jié)構(gòu)復(fù)雜的構(gòu)件，是未來智能制造必不可少的技術(shù)之一[1]。3D 打印原理如圖1 所示。

圖1 3D 打印原理

3D 打印技術(shù)的核心之一就是對(duì)三維模型的加工處理技術(shù)，它決定了3D 打印的成型效率和零件的力學(xué)性能。這些技術(shù)一般作為算法的形式集成到設(shè)備或者軟件中，從而實(shí)現(xiàn)完全自動(dòng)化處理。隨著3D 打印技術(shù)的迅速發(fā)展，3D 打印也越來越普及，所需成型的零件也越來越復(fù)雜，對(duì)算法的處理速度和準(zhǔn)確性要求也隨之升高。其中對(duì)三維模型數(shù)據(jù)的切片處理直接關(guān)系到最終產(chǎn)品的成型質(zhì)量和加工效率，因此很多的學(xué)者和企業(yè)對(duì)三維模型數(shù)據(jù)的切片算法有諸多研究[2]。本文以在3D 打印行業(yè)廣泛應(yīng)用的開源軟件CuraEngine 為基礎(chǔ)，通過剖析CuraEngine 中的切片算法實(shí)現(xiàn)，為3D打印切片算法的改進(jìn)和優(yōu)化提供參考和借鑒。

1 基于STL 模型的分層切片算法

STL 文件格式是目前使用最廣泛的三維模型文件格式之一，在3D 打印行業(yè)應(yīng)用廣泛，所以大部分切片算法也都是基于STL 文件開發(fā)。STL 文件主要描述了由三角面片構(gòu)成的三維模型信息，STL 文件中記錄了每個(gè)三角面片的法向量和頂點(diǎn)數(shù)據(jù)，為三維模型的讀取和渲染提供了最基本的信息。STL 文件有2 種格式，一種為ASCⅠⅠ編碼格式，另一種為二進(jìn)制格式。ASCⅠⅠ編碼格式的STL 文件可以直接通過文本進(jìn)行閱讀，但是ASCⅠⅠ編碼格式會(huì)導(dǎo)致文件占用空間較大，所以在處理大型模型時(shí)，最好選擇二進(jìn)制格式的STL 文件進(jìn)行保存，以盡可能節(jié)省儲(chǔ)存空間且便于文件傳輸。

基于STL 模型進(jìn)行分層切片的主要原理是通過選取合適的切片厚度，基于該厚度計(jì)算出各層高度，最后求得模型與各層高度相交的二維輪廓信息。這種分層操作會(huì)帶來“階梯效應(yīng)”，即在一定角度的三維模型表面產(chǎn)生階梯狀的臺(tái)階，隨著層厚減小，“階梯效應(yīng)” 會(huì)隨之減弱。因此，切片時(shí)層厚的選取與打印模型的精度密切相關(guān)，層厚越小，打印成型的零件越精細(xì)，但是打印過程的工作量和打印時(shí)長會(huì)增加。為了減少“階梯效應(yīng)”，目前的切片算法可以分為2 種，一種是自適應(yīng)層厚的切片算法，另一種是等層厚的切片算法。

國外有技術(shù)人員研究了自適應(yīng)層高的切片算法對(duì)模型處理的影響[3]；國內(nèi)部分學(xué)者在等層厚的切片算法基礎(chǔ)之上，提出了基于面片之間拓?fù)湫畔⒌姆謱忧衅惴╗4]、基于不同模型本身幾何特征的切片算法[5]和基于模型集合連續(xù)性的切片算法[6]。

Cura 是最早的3D 打印開源切片軟件之一，經(jīng)過多年的更新與維護(hù)，目前Cura 已經(jīng)成為了3D 打印行業(yè)中應(yīng)用最廣泛的切片軟件之一，而CuraEngine 作為目前Cura 最新的開源切片引擎，也是經(jīng)過了多年的發(fā)展和用戶的驗(yàn)證。CuraEngine 主要采取了等層厚的切片算法，并通過對(duì)STL 模型進(jìn)行優(yōu)化處理，有效提高了切片算法的效率，接下來通過對(duì)CuraEngine 的切片算法進(jìn)行分析，來探究3D 打印對(duì)三維模型的處理和分層方法。

2 STL 模型的讀取和前處理

STL 文件格式簡單，不像其他復(fù)雜的CAD 格式那樣需要多種復(fù)雜的幾何表示方法對(duì)模型進(jìn)行描述，其通過保存三角面片的信息基本可以保證在加工精度范圍內(nèi)準(zhǔn)確地描述任何三維模型，但是STL 文件的缺點(diǎn)也很明顯。由于STL 文件中直接記錄了每個(gè)三角面片的法向量和頂點(diǎn)數(shù)據(jù)信息，因此造成了較多的數(shù)據(jù)冗余，因?yàn)橥粋€(gè)頂點(diǎn)信息會(huì)被共用的三角面片重復(fù)記錄。其次就是STL 文件未保存模型的拓?fù)湫畔ⅲ黾恿饲衅碾y度，也增加了修復(fù)模型拓?fù)溴e(cuò)誤的難度，所以在進(jìn)行切片之前需要對(duì)STL 模型的數(shù)據(jù)進(jìn)行處理，建立模型中各個(gè)點(diǎn)、線、面之間的拓?fù)潢P(guān)系，為切片做好準(zhǔn)備。

如圖2 所示，將CAD 模型保存為STL 格式后，三維模型全都轉(zhuǎn)換成三角面片表示，直接讀取STL 格式文件，可以得到1 個(gè)三角面片的數(shù)據(jù)集合Mesh，每個(gè)三角面片保存了3 個(gè)頂點(diǎn)的坐標(biāo)數(shù)據(jù)（若需要對(duì)模型進(jìn)行渲染，可以同時(shí)保存面片的法向量數(shù)據(jù)，也可以通過頂點(diǎn)數(shù)據(jù)進(jìn)行計(jì)算）。此時(shí)Mesh 集合中未包含面片和頂點(diǎn)的拓?fù)潢P(guān)系，數(shù)據(jù)也有冗余。

首先可以通過哈希表對(duì)所有的頂點(diǎn)數(shù)據(jù)進(jìn)行分組。通過特定的哈希函數(shù)可以將頂點(diǎn)進(jìn)行分類，每一個(gè)哈希值將對(duì)應(yīng)一個(gè)頂點(diǎn)集合。接著遍歷頂點(diǎn)集合中的每個(gè)頂點(diǎn)，將每個(gè)遍歷到的頂點(diǎn)和對(duì)應(yīng)的頂點(diǎn)集合中的所有點(diǎn)進(jìn)行比較，過濾掉重復(fù)的頂點(diǎn)，將剩下的不重復(fù)的頂點(diǎn)數(shù)據(jù)保存在數(shù)組PointList 之中。利用哈希表可以大大加快處理重復(fù)頂點(diǎn)的時(shí)間，有效提高算法效率。同樣對(duì)三角面片進(jìn)行遍歷，將其保存在數(shù)組FaceList 中，期間對(duì)每個(gè)三角面片進(jìn)行處理，添加相連的三角面片在FaceList 中的下標(biāo)，并保存在集合Touching 中；為每個(gè)頂點(diǎn)添加所在面片在FaceList 中的下標(biāo)，并保存在集合FaceⅠndex 中。

這樣就對(duì)原始STL 數(shù)據(jù)進(jìn)行了優(yōu)化，得到了除去冗余數(shù)據(jù)的頂點(diǎn)數(shù)據(jù)列表（PointList）和包含拓?fù)潢P(guān)系的三角面片數(shù)據(jù)列表（FaceList）。其中每個(gè)頂點(diǎn)元素包含了所在三角面片的信息，每個(gè)三角面片元素也包含了相鄰三角面片的信息，這樣就有效減少了接下來切片工作的工作量，有效提高了切片的效率。

3 基于CuraEngine 的切片算法

通過對(duì)STL 模型數(shù)據(jù)的前處理，得到了擁有拓?fù)潢P(guān)系的頂點(diǎn)和三角面片數(shù)據(jù)，在切片過程中就可以利用這些數(shù)據(jù)形成每一層的輪廓多邊形。切片過程主要可以分為2 個(gè)部分，第一個(gè)部分是求取三角面片在切片平面內(nèi)的投影線段（Segment），第二部分是通過拓?fù)潢P(guān)系將這些投影線段進(jìn)行連接，形成每一層的輪廓多邊形。切片流程如圖3 所示。

在第一部分中首先根據(jù)層厚和模型起始位置計(jì)算出各個(gè)層的高度值，再對(duì)FaceList 中的各個(gè)三角面片計(jì)算其在每層高度平面的投影線段，并將投影線段保存在當(dāng)前層的集合中。在對(duì)FaceList 中的三角面片進(jìn)行求交運(yùn)算時(shí)，可以先通過三角面片的高度值范圍對(duì)集合中的數(shù)據(jù)進(jìn)行過濾，忽略不包含所求高度值的三角面片，以提高效率。

在計(jì)算三角面片的投影時(shí)，可以根據(jù)每個(gè)頂點(diǎn)在平面上方或者下方共枚舉出6 種情況，最后通過投影公式計(jì)算出三角面片在高度平面上的投影線段。在計(jì)算投影公式時(shí)，要注意輸入頂點(diǎn)的順序，因?yàn)檩斎腠旤c(diǎn)的順序直接決定了投影線段的起始點(diǎn)和終止點(diǎn)的方向，從而影響到后續(xù)輪廓多邊線的方向，對(duì)于多連通區(qū)域來說，內(nèi)外輪廓的方向至關(guān)重要。

得到投影線段之后，根據(jù)三角面片中保存的拓?fù)潢P(guān)系，找到每條投影線段所在三角面片的相鄰三角面片的投影線段，最后將其首尾相連就得到了該層的輪廓多邊形。對(duì)于復(fù)雜的或者有破損的STL 模型數(shù)據(jù)，有可能會(huì)得到未閉合的輪廓多邊形，這時(shí)就需要對(duì)未閉合的輪廓多邊形進(jìn)行修復(fù)，通過距離檢測和長度過濾能夠修復(fù)大部分未閉合的輪廓多邊形。但是對(duì)于通用層接口文件（Common Layer Ⅰnterface，CLⅠ），可以儲(chǔ)存填充線段（Hatches）數(shù)據(jù)，這些數(shù)據(jù)可以表示支撐結(jié)構(gòu)或者填充線段，對(duì)這些特殊的未閉合輪廓線段需要進(jìn)行特殊處理。

最終將得到的層數(shù)據(jù)集合按照用戶所需的格式進(jìn)行輸出，以供后續(xù)打印流程使用。

4 結(jié)論與展望

本文通過梳理CuraEngine 中的切片算法，對(duì)3D打印中的模型切片技術(shù)做了介紹。該算法的優(yōu)點(diǎn)在于：①采用哈希表快速剔除了STL 文件中的冗余數(shù)據(jù)；②在對(duì)三角面片進(jìn)行求交的過程中，剔除了與高度平面不相交的面片，避免了大量的無效判斷；③可以直接通過三角面片的相鄰關(guān)系快速找到首尾相連的輪廓線段。

但是CuraEngine 的切片算法仍有諸多可以改進(jìn)之處。首先，該算法中間用來存儲(chǔ)數(shù)據(jù)的臨時(shí)變量較多，增加了算法的空間復(fù)雜度；其次，線性的計(jì)算流程對(duì)當(dāng)下追求算法效率的行業(yè)發(fā)展來說略顯吃力，可以引入一定的多線程并行技術(shù)，這樣在處理大型復(fù)雜三維模型時(shí)會(huì)取得更好的效果；最后，在對(duì)輪廓線進(jìn)行連接時(shí)仍較為復(fù)雜，可以通過對(duì)相連的面片進(jìn)行一定排序，直接求出有向的邊界輪廓。