一種平臺化的樹形支撐結(jié)構(gòu)生成算法*

王燕寧，趙祖燁，張軍飛

0 引言

自20世紀(jì)80年代以來，3D打印發(fā)展迅速，出現(xiàn)了如熔融沉積成型（Fused Deposition Model?ing，F(xiàn)DM）、選擇性激光燒結(jié)（Selective Laser Sin?tering，SLS）、選擇性激光熔化（Selective Laser Melting，SLM）、光固化成型（Stereo Lithography Apparatus，SLA）和分層實體制造（Laminated Object Manufacturing，LOM）等眾多3D打印工藝。

其中，F(xiàn)DM、SLM、SLA等工藝在加工過程中需要添加支撐結(jié)構(gòu)。在SLM工藝過程中，熱應(yīng)力超過材料強(qiáng)度時發(fā)生的塑性變形以及逐層鋪粉時的橫向擾動等因素都會導(dǎo)致成形質(zhì)量下降，因此需要設(shè)計支撐結(jié)構(gòu)進(jìn)行部分熱量傳導(dǎo)和零件固定。FDM工藝中，每個層面都是在上一層上堆積而成，上一層對當(dāng)前層起到定位和支撐的作用。當(dāng)前層的形狀發(fā)生較大變化，如出現(xiàn)懸臂結(jié)構(gòu)或較大傾斜面時，上層輪廓就不能給當(dāng)前層提供充分的定位和支撐，這時就需要設(shè)計一些輔助結(jié)構(gòu)用于支撐[1-2]。SLA工藝以光敏樹脂為原料，采用計算機(jī)控制下的激光束以預(yù)定原型各分層截面的輪廓為軌跡點(diǎn)掃描，使被掃描區(qū)的樹脂薄層產(chǎn)生光聚合反應(yīng)后固化形成一個薄層截面[3]，上一層對當(dāng)前層起到定位和支撐的作用，當(dāng)截面形狀變化很大時需要添加支撐結(jié)構(gòu)。可見，支撐結(jié)構(gòu)的生成是3D打印成型工藝中的一項關(guān)鍵技術(shù)。

目前支撐結(jié)構(gòu)的類型主要有：點(diǎn)支撐、線支撐、塊狀支撐、柱狀支撐[4]、網(wǎng)狀支撐[5]、肋狀支撐和錐形支撐等。樹形支撐相比其他類型的支撐，所消耗的支撐材料更少，達(dá)到了節(jié)省材料降低成本的目的；同時，對于支撐體的打印時間減少，達(dá)到節(jié)省時間、降低成型周期的目的。在文獻(xiàn)[6]中通過大量實驗得出當(dāng)樹形支撐的傾斜角小于臨界角度時，可以達(dá)到支撐效果。證明了樹形支撐在支撐耗材比塊狀支撐、網(wǎng)狀支撐、柱狀支撐等其他支撐類型更少、打印時間更少的情況下，實體打印效果不受影響。故本文對樹形支撐結(jié)構(gòu)進(jìn)行深入研究，提出一種自上而下的樹形支撐結(jié)構(gòu)生成算法。

1 樹形支撐結(jié)構(gòu)生成問題簡述

樹形支撐是一種類似樹枝形狀的支撐結(jié)構(gòu)，與支撐面接觸部位采用眾多子枝干提供支撐，子枝干通過連接節(jié)點(diǎn)匯聚，為3D打印過程中的懸空區(qū)域提供支撐的支撐結(jié)構(gòu)。相較于柱狀支撐及網(wǎng)格支撐，樹形支撐由于子枝干的匯聚在節(jié)省材料及打印時間上有一定的優(yōu)勢。

圖1為本文算法生成的樹形支撐結(jié)構(gòu)圖，為了節(jié)省支撐耗材，樹形支撐結(jié)構(gòu)長度應(yīng)盡量小。因此，在某種程度上樹形支撐的構(gòu)建類似于Eu?clidean Steiner最小生成樹（ESMT）問題。ESMT的目標(biāo)是找到輸入點(diǎn)集中各點(diǎn)連接距離之和最短的長度。而樹形支撐結(jié)構(gòu)是在三維空間中構(gòu)建，且需滿足臨界傾角約束條件，因此該問題復(fù)雜程度至少是NP難度[6]。

圖1 樹形支撐結(jié)構(gòu)圖

本文采用的樹形支撐生成算法為一種自上而下的生長方式，在識別的待支撐區(qū)域上拾取支撐點(diǎn)，通過子枝干節(jié)點(diǎn)搜索連接距離最短的連接節(jié)點(diǎn)，連接子枝干與連接節(jié)點(diǎn)，連接節(jié)點(diǎn)成為新的子枝干節(jié)點(diǎn)，依次迭代，直到搜索結(jié)束條件，構(gòu)建整體支撐結(jié)構(gòu)。支撐算法的研究主要分兩部分內(nèi)容：待支撐區(qū)域的識別和支撐體的生成。具體樹形支撐生成流程如圖2。

圖2 算法流程圖

2 待支撐區(qū)域識別及待支撐點(diǎn)提取

2.1 待支撐區(qū)域識別

目前，STL文件為3D打印領(lǐng)域中事實上的工業(yè)標(biāo)準(zhǔn)，它存儲的是離散的三角形面片頂點(diǎn)坐標(biāo)和指向?qū)嶓w外方向的單位法向矢量。支撐區(qū)域可以通過三角面片外法矢量與Z軸夾角，與臨界傾角α的大小關(guān)系來判斷。臨界傾角α與材料屬性、工藝類型、機(jī)器型號等因素相關(guān)，表示實體區(qū)域可以實現(xiàn)自支撐的最大角度。

根據(jù)三角面片外法矢量與Z軸夾角來判斷待支撐區(qū)域，一般需要支撐的部位主要有兩種：一種是被支撐面與Z軸垂直；另一種是被支撐面與Z軸的夾角等于或者小于臨界傾角α。待支撐區(qū)域識別，本文采用基于STL格式的支撐區(qū)域識別算法[7]。

2.2 待支撐點(diǎn)提取

完成待支撐區(qū)域識別后，進(jìn)行待支撐點(diǎn)的提取。待支撐區(qū)域?qū)崉t是三維坐標(biāo)點(diǎn)集，即三維凸包[8]。三維凸包的點(diǎn)采樣一般采用柵格法。先完成待支撐區(qū)域在XOY平面內(nèi)的投影，對待支撐區(qū)域的XOY平面投影進(jìn)行網(wǎng)格劃分，以劃分的每個網(wǎng)格中心點(diǎn)為射線的起點(diǎn)沿Z軸正向與待支撐區(qū)域三角面片求交，所求交點(diǎn)即待支撐點(diǎn)。

3 樹形支撐結(jié)構(gòu)生成

3.1 樹形支撐節(jié)點(diǎn)搜索原理

獲得待支撐點(diǎn)后進(jìn)行樹形支撐節(jié)點(diǎn)搜索和支撐結(jié)構(gòu)生成。樹形支撐節(jié)點(diǎn)需滿足臨界傾角約束條件：（1）樹形支撐連接枝干之間的夾角不大于傾角α；（2）新支撐點(diǎn)的Z坐標(biāo)大于等于基底Z坐標(biāo)。樹形支撐節(jié)點(diǎn)搜索原理如圖3所示，為減少支撐材料，連接相鄰的待支撐點(diǎn)距離和應(yīng)在滿足臨界傾角約束條件下盡量小。區(qū)域c中的點(diǎn)均滿足臨界傾角約束，點(diǎn)q為連接待支撐點(diǎn)p1和p2距離和最短的連接點(diǎn)。樹形支撐節(jié)點(diǎn)q在圓錐體c1和c2的對稱面上，同時也在圓錐體c1和c2的圓錐面上。根據(jù)聯(lián)立方程組，即可求解樹形支撐節(jié)點(diǎn)q。

3.2 樹形支撐結(jié)構(gòu)生成流程

樹形支撐生成流程采用貪心算法和迭代的思想，選取支撐節(jié)點(diǎn)連接長度最短的連接方式并生成新的支撐節(jié)點(diǎn)。對每個當(dāng)前支撐點(diǎn)求解連接距離之和最短的連接方式，以逼近樹形支撐結(jié)構(gòu)構(gòu)建最優(yōu)解。樹形支撐結(jié)構(gòu)生成流程如下所述。

（1）新支撐點(diǎn)生成

獲得原始待支撐點(diǎn)后，自上而下生成新的支撐點(diǎn)，利用臨界傾角約束條件，生成樹形支撐結(jié)構(gòu)。

1）逐步求得與當(dāng)前點(diǎn)生成新支撐點(diǎn)連接距離最短的點(diǎn)，生成新支撐點(diǎn)與樹形支撐的局部連接枝干；

2）對于剩余的獨(dú)點(diǎn)，遍歷所有的下一層新支撐點(diǎn)，找到與獨(dú)點(diǎn)連接距離最短的新支撐點(diǎn)，并判斷是否滿足臨界傾角約束條件，如果滿足則加入到樹形支撐的連接枝干中，若不滿足則將獨(dú)點(diǎn)加入到下一層新支撐點(diǎn)中。

（2）將獲得的下一層新支撐點(diǎn)迭代步驟（1）中的方法，繼續(xù)求解，直到新一層支撐點(diǎn)個數(shù)小于等于1。

圖4為采用本文方法生成的門把模型的樹形支撐結(jié)構(gòu)圖。

圖3 支撐節(jié)點(diǎn)搜索原理圖

圖4 門把樹形支撐結(jié)構(gòu)圖

4 樹形支撐結(jié)構(gòu)工藝路徑生成

4.1 SLC文件格式

SLC文件格式是Materialise公司為獲取快速成型三維模型分層切片后的數(shù)據(jù)而提出的一種數(shù)據(jù)存儲的文件格式。SLC數(shù)據(jù)模型對三維模型的輪廓表達(dá)采用的是2.5D模式，最終形成的三維模型是沿著Z軸方向由一系列內(nèi)外輪廓包圍形成的小實體疊加而成的[9]。SLC格式使用的實體有輪廓邊界、輪廓層、直線段和多義段。其中輪廓邊界是值按逆時針排序的外邊界與按順時針排序的內(nèi)邊界、輪廓層是指由實體材料的內(nèi)外邊界線所組成的部分。直線段指的是位于二維平面上的兩點(diǎn)間的連線。

4.2 Clipper庫處理樹形支撐結(jié)構(gòu)

Clipper是一種開源的二維圖形裁剪庫，可對平面多邊形進(jìn)行布爾運(yùn)算（交、并、差、異或）。由樹形支撐結(jié)構(gòu)的骨干結(jié)構(gòu)轉(zhuǎn)化為工藝路徑，具體流程如圖5。

圖5 支撐結(jié)構(gòu)工藝路徑規(guī)劃流程圖

首先根據(jù)支撐結(jié)構(gòu)骨干線，結(jié)合圓柱方程構(gòu)造樹形支撐結(jié)構(gòu)三維數(shù)據(jù)結(jié)構(gòu)，然后沿著Z軸方向切片，對于給定Z值的切片需要進(jìn)行輪廓的布爾運(yùn)算，采用Clipper庫進(jìn)行布爾運(yùn)算得到最終的切片輪廓。得到切片輪廓后，進(jìn)行路徑填充，即可得到樹形支撐結(jié)構(gòu)的工藝路徑。圖6為圖1的樹形支撐結(jié)構(gòu)SLC工藝路徑。

5 結(jié)論

圖6 SLC工藝路徑圖

本文提出了一種樹形支撐結(jié)構(gòu)生成算法，相比傳統(tǒng)的支撐結(jié)構(gòu)，樹形支撐結(jié)構(gòu)在節(jié)省材料使用量和支撐加工時間上具有優(yōu)勢。目前，本文關(guān)注點(diǎn)主要在樹形支撐結(jié)構(gòu)生成方面，對于具體工藝的支撐優(yōu)化工作較少。例如，支撐截面形狀、截面大小對于支撐穩(wěn)定性的影響，如何通過支撐避免制件出現(xiàn)應(yīng)力變形等。因此，未來的工作將主要對此進(jìn)行深入研究。

參考文獻(xiàn)：

［1］沈振宏，戴寧，李大偉，等.基于臨界傾角約束的樹形支撐結(jié)構(gòu)生成算法［J］.中國機(jī)械工程，2016（8）：1107-1112.

［2］姜耀林，邵中魁.3D打印在快速熔模精密鑄造技術(shù)中的應(yīng)用［J］.機(jī)電工程，2017（1）：48-51.

［3］劉汝虎.光固化快速原型制造數(shù)據(jù)預(yù)處理關(guān)鍵技術(shù)研究與實現(xiàn)［D］.南京：南京航空航天大學(xué)，2008.

［4］董學(xué)珍，莫健華，張李超.光固化快速成形中柱形支撐生成算法的研究［J］.華中科技大學(xué)學(xué)報（自然科學(xué)版），2004（08）：16-18.

［5］錢波，莫健華，張李超.光固化快速成形中網(wǎng)形支撐生成算法的研究［J］.鍛壓裝備與制造技術(shù)，2005（04）：122-124.

［6］ VANEK J，GALICIA J A G，BENES B.Clever Sup?port：Efficient Support Structure Generation for Digital Fabrication ［J］.Computer Graphics Forum， 2014，33（5）： 117-125.

［7］錢波，張李超，史玉升，等.基于STL模型的表面區(qū)域遞歸拾取算法［J］.華中科技大學(xué)學(xué)報（自然科學(xué)版），2008（09）：90-93.

［8］周培德.計算幾何/算法設(shè)計與分析/中國計算機(jī)學(xué)會學(xué)術(shù)著作叢書：算法設(shè)計與分析［M］.北京：清華大學(xué)出版社有限公司，2005.

［9］吳懋亮，華麟鋆.SLC文件的掃描路徑生成方法［J］.機(jī)械與電子，2010（11）：18-20.