一種平臺化的樹形支撐結構生成算法*

王燕寧，趙祖燁，張軍飛

0 引言

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

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

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

1 樹形支撐結構生成問題簡述

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

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

圖1 樹形支撐結構圖

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

圖2 算法流程圖

2 待支撐區域識別及待支撐點提取

2.1 待支撐區域識別

目前，STL文件為3D打印領域中事實上的工業標準，它存儲的是離散的三角形面片頂點坐標和指向實體外方向的單位法向矢量。支撐區域可以通過三角面片外法矢量與Z軸夾角，與臨界傾角α的大小關系來判斷。臨界傾角α與材料屬性、工藝類型、機器型號等因素相關，表示實體區域可以實現自支撐的最大角度。

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

2.2 待支撐點提取

完成待支撐區域識別后，進行待支撐點的提取。待支撐區域實則是三維坐標點集，即三維凸包[8]。三維凸包的點采樣一般采用柵格法。先完成待支撐區域在XOY平面內的投影，對待支撐區域的XOY平面投影進行網格劃分，以劃分的每個網格中心點為射線的起點沿Z軸正向與待支撐區域三角面片求交，所求交點即待支撐點。

3 樹形支撐結構生成

3.1 樹形支撐節點搜索原理

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

3.2 樹形支撐結構生成流程

樹形支撐生成流程采用貪心算法和迭代的思想，選取支撐節點連接長度最短的連接方式并生成新的支撐節點。對每個當前支撐點求解連接距離之和最短的連接方式，以逼近樹形支撐結構構建最優解。樹形支撐結構生成流程如下所述。

（1）新支撐點生成

獲得原始待支撐點后，自上而下生成新的支撐點，利用臨界傾角約束條件，生成樹形支撐結構。

1）逐步求得與當前點生成新支撐點連接距離最短的點，生成新支撐點與樹形支撐的局部連接枝干；

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

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

圖4為采用本文方法生成的門把模型的樹形支撐結構圖。

圖3 支撐節點搜索原理圖

圖4 門把樹形支撐結構圖

4 樹形支撐結構工藝路徑生成

4.1 SLC文件格式

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

4.2 Clipper庫處理樹形支撐結構

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

圖5 支撐結構工藝路徑規劃流程圖

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

5 結論

圖6 SLC工藝路徑圖

本文提出了一種樹形支撐結構生成算法，相比傳統的支撐結構，樹形支撐結構在節省材料使用量和支撐加工時間上具有優勢。目前，本文關注點主要在樹形支撐結構生成方面，對于具體工藝的支撐優化工作較少。例如，支撐截面形狀、截面大小對于支撐穩定性的影響，如何通過支撐避免制件出現應力變形等。因此，未來的工作將主要對此進行深入研究。

參考文獻：

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

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

［3］劉汝虎.光固化快速原型制造數據預處理關鍵技術研究與實現［D］.南京：南京航空航天大學，2008.

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

［5］錢波，莫健華，張李超.光固化快速成形中網形支撐生成算法的研究［J］.鍛壓裝備與制造技術，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模型的表面區域遞歸拾取算法［J］.華中科技大學學報（自然科學版），2008（09）：90-93.

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

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