基于臨界傾角約束的樹形支撐結構生成算法

沈振宏　戴　寧　李大偉　吳長友

南京航空航天大學，南京，210016

?

基于臨界傾角約束的樹形支撐結構生成算法

沈振宏戴寧李大偉吳長友

南京航空航天大學，南京，210016

為節省三維打印的材料和時間，針對支撐結構體積優化的問題，提出了一種基于臨界傾角約束的樹形支撐結構生成算法。首先識別待支撐區域，并基于面積自適應采樣獲得待支撐點；再利用臨界傾角約束進行樹形結構節點的計算，并存儲同一棵樹上各節點的連接關系；采用掃掠和泊松曲面重建方法，生成樹形支撐實體，最后通過實例進行了驗證。實驗結果表明，所提出的方法在保證打印穩定性的前提下，有效減少了支撐材料，縮短了打印時間。

三維打印；臨界傾角約束；樹形支撐；泊松曲面重建

0　引言

三維打印工藝過程中普遍存在著零件變形、翹曲、坍塌等問題。例如在SLM(selective laser melting)工藝過程中，熱應力超過材料強度時發生的塑性變形以及逐層鋪粉時的橫向擾動等因素都會導致成形質量下降，因此需要設計支撐結構進行部分熱量傳導和零件固定。FDM(fused deposition modeling)工藝中，每個層面都是在上一層上堆積而成，上一層對當前層起到定位和支撐的作用。當前層的形狀發生較大變化，如出現懸臂結構或較大傾斜面時，上層輪廓就不能給當前層提供充分的定位和支撐，這時就需要設計一些輔助結構用于支撐。因此，支撐結構的生成，是三維打印成形工藝中的一項關鍵技術。

支撐生成算法首先需要尋找模型中的待支撐部位。一類方法是先獲得模型的分層輪廓數據，再利用分層數據進行識別。Chalasani等[1]對各層多邊形進行合并，得到模型截面的最小包絡矩形，進而得到模型的包圍盒，該方法以SLC文件為輸入，可以很快得到截面包絡矩形的信息，但采用包圍盒的方法，需要人工刪除一些不需要添加支撐的區域。Huang等[2]自頂而下地對相鄰兩層實體切片進行求差、并的多邊形布爾運算，算法有效利用了材料的自支撐能力，但是由于涉及到任意多邊形的布爾運算和任意多邊形的雙向偏置，具有一定的復雜度，隨著多邊形和節點的增多，算法的耗時會顯著增加。另一類方法是直接在三維模型上進行識別。Lan等[3]先對模型中待支撐的邊進行處理，然后查找待支撐面片，該方法針對的模型相對簡單，其適用范圍具有一定局限性。Alexander等[4]將模型表面質量、加工時間、支撐體數量作為目標函數，通過求多目標問題的最優解集確定模型的分層方向。該算法采用參數肩高進行表面精度計算，并對肩高求值進行了優化，但是算法的時間復雜度較高。

對于支撐體的結構設計，最簡單的方法是包圍盒法，即求出模型的最小包絡長方體。為了方便加工后支撐體的去除，Strano等[5]采用較稀疏的內部結構進行填充，Kritchman等[6]使用了可溶材料打印支撐體。但包圍盒法沒有考慮零件原型的形態特征，因此它也是一種最耗費支撐材料和成形時間的方法。為了減小包圍盒法中支撐體的體積，陳巖等[7]采用直臂支撐結構，該算法能自動添加支撐點和支撐桿，但算法中的支撐傳遞參數無法自動選取，僅能通過實驗估算。Huang等[8]提出了一種斜壁結構，該支撐結構分為三種類型，通過計算待支撐區域多邊形的穩定系數，進而確定添加的支撐類型，但該算法減小的支撐體積有限，支撐與模型的接觸面積較大。Dumas等[9]采用了一種橋梁支撐結構，該結構由一系列水平橋梁和豎直支柱構成，材料的耗費較少，但是該方法總體路線較為復雜，水平橋梁中錨線段的選取不明確。

本文提出一種基于臨界傾角約束的樹形支撐結構生成算法，該算法對于待支撐的點集，利用下層支撐點的臨界傾角約束獲得下層支撐點位置，構建節點結構體，生成樹形結構，最后通過掃掠和泊松曲面重建生成樹實體。

1　技術流程

基于臨界傾角約束的樹形支撐結構生成算法的技術流程如圖1所示。首先識別模型中的待支撐區域，根據面片方向與加工方向(z軸正方向)的夾角保存模型中的待支撐面片，對待支撐面片集合進行相鄰面片的合并，獲得若干獨立的待支撐區域。然后基于面積自適應采樣獲得待支撐點。之后，進入算法的核心部分，即利用臨界傾角約束條件自上而下逐層生成樹形支撐結構。以待支撐點為輸入，利用下層支撐點的位置約束條件進行樹形結構節點的計算，構建節點結構體，生成若干獨立的樹結構。最后，通過截面單元掃掠和泊松曲面重建生成支撐實體。

圖1　基于臨界傾角約束的樹形支撐結構算法流程圖

2　基于臨界傾角約束的樹形支撐結構生成

2.1待支撐區域識別

零件待支撐區域的自動識別，首先要讀入零件的模型數據。三維打印系統多用STL格式文件表示零件的數據，即用大量的三角面片近似整個零件的表面。根據零件模型中面片方向與加工方向的夾角α與臨界傾角β的大小關系，識別需要添加支撐的面片。α≤β時，由于材料自身的粘力作用，無需添加輔助支撐結構；α>β時，需要對面片添加支撐(圖2粗實線區域)。同時對向下傾斜且不需要支撐區域的局部最低的點和邊進行識別。

圖2　待支撐區域識別

對于識別的待支撐面片集合Tsup，需要將集合中共邊的面片進行合并，得到若干獨立的待支撐區域A0，A1，…，An，面片合并結果為

(1)

Ai∩Aj=?i，j=1，2，…，n且i≠j

算法采用區域增長法進行相鄰面片的合并。首先任取集合中的一個面片作為種子，判斷該種子的共邊三角面片是否在集合Tsup中。若共邊面片在集合中且未存為種子面片，則將其存到種子集中。繼續尋找與其他種子共邊的三角面片，直到種子集中的所有種子都查找過為止。重復上述步驟，完成各個區域的面片合并，流程如圖3所示。

圖3　相鄰面片合并算法流程圖

2.2基于面積自適應采樣的待支撐點選擇

獲得待支撐區域后，需要在區域內采樣一系列的待支撐點。算法首先獲得區域投影的凸包，再對凸包進行柵格劃分，根據柵格中面片的大小選取待支撐的點。

獲得模型投影的凸包有兩種方法。一種方法是先提取區域邊界，再求邊界點的凸包。邊界提取，即先保存面域中的非公用邊，得到組成邊界的各條線段，再利用種子擴散法將相鄰線段連接起來。另一種方法是直接將面域中的各頂點往某一平面投影，得到這些頂點投影的凸包。

得到投影的凸包后，采用一定的柵格間距d對凸包進行網格劃分。柵格間距d的選取與材料的臨界打印長度(材料在沒有支撐的情況下保持不變形的極限打印長度)L有關。為了保證支撐的穩定性，同時避免選擇的支撐點過于密集，選取經驗值d=L/2。然后從柵格的左下頂點開始，逐行往上判斷每個柵格中的頂點個數。當柵格中的點個數為0時，插入相應的點并保存；當柵格中的點個數大于1時，計算這些點的中心點并保存。最后通過射線求交，求得這些點在模型上的交點，得到一系列的待支撐點。

2.3基于臨界傾角約束的支撐結構生成

獲得待支撐點后，算法基于自上而下的生長策略，利用下層支撐點的臨界傾角約束條件，生成樹形支撐結構。對于待支撐點集P中的點p，假設通過下方的點s進行支撐，則向量sp與加工方向的夾角不大于臨界傾角β。因此s可落于以點p為頂點、錐角為2β的圓錐體上或體內的任意位置。圖4中，點p1、p2為零件原型上待支撐的點，c1為點p1對應的圓錐體，c2為點p2對應的圓錐體，則同時支撐p1和p2的下層節點可取圓錐體c1和c2相交區域中的任意點。本文選取該區域的最高點s，因為此時線段p1s、p2s的長度之和是最小的，即打印的支撐材料最少。

圖4　錐約束求下層支撐點示意圖

通過待支撐點的配對求交，并將交點插入到點集P中，直到點集P中所有點都計算過為止。該算法的輸入為待支撐的點集P(按z從大到小存儲)和以點集P中各點為頂點生成的對應的圓錐集C。整體支撐結構的生成通過遍歷點p∈P和其對應的圓錐c∈C執行以下操作：

(1)查找圓錐c和模型m的最近交點sm，圓錐c與其他圓錐{ci|ci∈C且ci≠c}的最近交點；

(2)在圓錐c與其他圓錐{ci|ci∈C且ci≠c}的交點集合中，選擇交點到相應兩圓錐頂點p、pi距離之和L1最小的交點smin。如果線段psmin的長度大于線段psm的長度，刪除點p和相應的圓錐c，保存線段psm，對下個點重復執行步驟1；

(3)將交點smin插入到點集P中，保存線段psmin、pismin；

(4)生成點smin對應的圓錐，刪除點p、圓錐c和ci；

(5)當P非空時，對下一個點重復上述步驟。

通過配對求交獲得樹形結構中上下節點的連接關系，建立node結構體來存儲樹形結構中的各個節點，其定義如下：

Struct node

{intelement；

intlevel；

boolbvisit；

node*parent， lchild， rchild；

}

其中，成員變量element、level、bvisit分別為節點的索引值、節點在樹結構中的層數、節點的訪問標志，同時，每個節點還包含指向父節點和左右子節點的指針。通過node結構體將同一棵樹上的節點關聯起來，同時按照樹結構層數從小到大的順序逐層地把節點存在列表中。

2.4基于泊松曲面重建的支撐實體生成

2.4.1掃掠獲得初始曲面頂點

得到樹形支撐結構后，需要把它轉化為實體，然后將帶有支撐結構的原型零件轉化為STL文件，經后續分層處理得到零件和支撐的截面輪廓，再對其進行路徑規劃，從而得到零件及支撐體的加工路徑[10-11]。

算法通過分層保存的節點信息，使用水平截面單元逐層掃掠各層各節點到其子節點的路徑，獲得初始曲面頂點。然后對這些頂點進行編號和存儲，生成網格曲面。此時生成的曲面在相交的區域沒有進行相應的處理(圖5三角形區域)，如果直接打印的話，將產生振動，影響打印的穩定性。

圖5　掃掠示意圖

2.4.2泊松曲面重建

由于掃掠生成的曲面是相互獨立的，并且存在相交區域，因此需要對掃掠曲面進行曲面重建，使每棵樹成為一個獨立的整體。本文采用的泊松曲面重建方法[12]首先計算三維指標函數χ(點在模型內部時，χ=1；點在模型外部時，χ=0)，然后采用Marching Cubes算法提取一個適當的等值面來獲得重建曲面。

重建算法首先計算模型的指標函數。指標函數的梯度是一個在表面附近非零，在其他任意位置都為零的向量場。因此，帶法矢的表面點樣本可以看作是指標函數梯度的樣本。計算指標函數的問題因此可簡化為梯度算子的反算，即找到標量函數χ，使其梯度最佳逼近由采樣點定義的向量場V，即求minχ‖χ-V‖。如果采用散度算子，該問題就可以轉化為一個標準的泊松問題，即計算拉普拉斯算子等于向量場V的散度的標量函數χ:

Δχ=·χ=·V

(2)

泊松曲面重建的重要步驟如下(重建結果如圖6所示)：

(1)根據采樣點的位置信息定義一個八叉樹?，然后給八叉樹的每一個節點o∈?，定義一個節點函數F0，之后定義函數空間f?,F≡Span{F0}，其結構類似于傳統的小波表示；

(2)選擇基函數F；

(3)定義向量場V；

(4)求解minχ‖χ-V‖的最小值；

(5)抽取等值面。

圖6　泊松曲面重建示意圖

另外，在進行泊松曲面重建之前，算法對樹形支撐結構進行了局部優化：①在支撐結構與模型的接觸區域，采用小圓接觸。小圓的半徑r=0.3 mm，圓平面法矢方向與待支撐點的法向量同向。采用小圓接觸可以減小支撐體與模型表面的接觸面積，方便后處理中支撐結構的剝離。②在支撐結構與底板的接觸處采用較大的底面圓，底面圓半徑為4.0 mm，從而更好地黏住底板，增加支撐結構穩定性。

3　實驗結果與分析

3.1實驗條件

提出的算法在MicrosoftVisualStudio2008軟件開發平臺上實現，并通過OpenGL進行模型顯示。建模后的模型在美國MakerBot公司的MakerBotReplicator2打印機上完成打印，打印材料為ABS塑料絲，打印速度為40mm/s，移動速度為60mm/s，層高為0.2mm。

3.2臨界傾角β標定實驗

由于臨界傾角β并不是一個定值，不同的打印機和打印材料對應的臨界傾斜角可能不同。為此設計了不同傾角的樹枝并進行實驗，如圖7所示。得到結果如表1所示，表1中的編號與圖7的編號相對應。

圖7　臨界傾角標定試驗

編號(1,1)(1,2)1,3)(1,4)(1,5)傾角(°)010203040變形情況無無無無無編號(2,1)(2,2)(2,3)(2,4)(2,5)傾角(°)5060708090變形情況輕微輕微稍重稍重嚴重編號(3,1)(3,2)(3,3)(3,4)(3,5)傾角(°)3031323334變形情況無無無無無編號(4,1)(4,2)(4,3)(4,4)(4,5)傾角(°)3536373839變形情況無無無無無編號(5,1)(5,2)(5,3)(5,4)(5,5)傾角(°)4041424344變形情況無無無無無編號(6,1)(6,2)(6,3)(6,4)(6,5)傾角(°)4546474849變形情況輕微輕微輕微輕微輕微

由表1可以看出，當傾角大于45°的時候，樹枝開始發生變形，為了保證打印過程中的穩定性，保留一定的余量，取臨界傾角β為40°。

3.3支撐建模及實驗

獲得了打印機對應的臨界傾斜角β后，基于臨界傾角約束逐層生成樹形支撐結構的過程如圖8所示，首先識別待支撐區域，然后基于面積自適應采樣獲得待支撐點，再根據下層支撐點的臨界傾角約束計算樹形結構中節點的位置，基于自上而下的生長策略生成樹形支撐結構，最后通過泊松重建獲得樹形結構實體。

(a)識別待支撐區域　　　(b)計算待支撐點

(c)生成支撐結構(狀態1)　(d)生成支撐結構(狀態2)

(e)生成支撐結構(狀態3)　　(f)泊松重建生成實體

由于打印過程中存在擾動，影響樹形結構整體的打印穩定性，因此算法對于圖8e中的支撐結構底層進行了輔助支撐，再進行泊松曲面重建，得到圖8f所示的結果。

為了客觀評價提出的算法，將算法生成的支撐模型與打印機內置軟件MakerWare和Magics RP v16.03(比利時Materialise公司)生成的支撐模型作對比，圖9所示為懸吊球模型在不同方法支撐下的打印結果。圖10所示為添加了樹形支撐結構的牙頜托盤模型和人體骨頭模型。3個模型的打印結果對比如表2所示。

(a)MakerWare　　　　　　　(b)Magics RP

(c)本文算法　　　　　(d)去除支撐后的模型圖9　模型打印結果對比

圖10　添加支撐后的牙頜托盤和骨頭模型

對比參量懸吊球牙頜托盤人體骨頭打印時間(min)MakerWare9493102MagicsRP788085本文算法747468材料消耗(g)MakerWare8.016.714.6MagicsRP2.914.112.4本文算法2.712.310.0

由表2可以得出，相比MakerWare，本文算法降低了20%左右的時間消耗和近40%的材料消耗；相比Magics RP，本文算法在時間和材料耗費上也均占有優勢。在模型表面成形質量方面，由于算法生成的支撐與物體模型的接觸面積很小，所以生成的支撐對模型表面損害較小，同時降低了剝除支撐體的難度。

4　結論

(1)針對包圍盒法和直臂支撐法生成的支撐結構體積大、打印時間較長的問題，提出一種基于臨界傾角約束的樹形支撐結構自動生成算法。算法利用下層支撐點的臨界傾角約束條件，計算樹形支撐結構節點的位置。

(2)針對支撐體生成、去除和支撐體穩定性的問題，本文通過掃掠獲得初始支撐結構曲面，采用泊松曲面重建生成樹形支撐實體。在支撐結構與模型的接觸位置采用小圓接觸的方式進行優化，同時對結構中承載較重的底部樹干進行了輔助支撐。實驗結果表明，該方法在保證模型原型正常打印的前提下，有效地減小了支撐體的體積和數量，同時縮減了打印時間。

(3)本文方法仍有不足之處，對于需要添加支撐的區域仍不能實現最小化，可能生成了一些額外的支撐。因此后續的研究重點是對區域的優化分析。

[1]Chalasani K，Jones L，Roscoe L. Support Generation for Fused Deposition Modeling[C]//Proceedings of Solid Freeform Fabrication Symposium. Austin：Texas，USA， 1995：229-241.

[2]Huang Xiaomao，Ye Chunsheng，Mo Jianhua，et al. Slice Data Based Support Generation Algorithm for Fused Deposition Modeling[J]. Tsinghua Science and Technology，2009，14(S1)：223-228.

[3]Lan Po-Ting，Chou Shuo-Yan，Chen Lin-lin，et al. Determining Fabrication Orientation for Rapid Prototyping with Stereolithography Apparatus[J]. Computer-Aided Design，1997，29(1)：53-62.

[4]Alexander P，Allen S，Dutta D. Part Orientation and Build Cost Determination in Layered Manufacturing[J]. Computer-Aided Design，1998，30(5)：343-356.

[5]Strano G，Hao L，Everson R，et al. A New Approach to the Design and Optimization of Support Structures in Additive Manufacturing[J]. Advanced Manufacturing Technology，2013，66(9/12)：1247-1254.

[6]Kritchman E，Gothait H，Miller G. System and Method for Printing and Supporting Three Dimensional Objects：US，7364686[P]. 2008-04-29.

[7]陳巖，王士瑋，楊周旺，等. FDM三維打印的支撐結構的設計算法[J]. 中國科學，2015，45(2)：259-269.

Chen Yan，Wang Shiwei，Yang Zhouwang，et al. Construction of Support Structure for FDM 3D Printers[J]. Scientia Sinica，2015，45(2)：259-269.

[8]Huang Xiaomao，Ye Chunsheng，Wu Siyu，et al. Sloping Wall Structure Support Generation for Fused Deposition Modeling[J]. Advanced Manufacturing Technology，2009，42(11/12)：1074-1081.

[9]Dumas J，Hergel J，Lefebvre S. Bridging the Gap：Automated Steady Scaffolding for 3d Printing[J]. ACM Transactions on Graphics，2014，33(4)：1-10.

[10]卞宏友，劉偉軍，王天然. 基于STL模型支撐算法的研究[J]. 機械設計與制造，2005(7)：49-52.

Bian Hongyou，Liu Weijun，Wang Tianran. Study on Algorithm for Generate Support Based on STL File[J]. Machinery Design & Manufacture，2005(7):49-52.

[11]洪軍，王崴，張宇紅. 光固化快速成形自動支撐技術研究[J]. 機械工程學報，2004，40(11)：134-138.

Hong Jun，Wang Wei，Zhang Yuhong，et al. Research on Auto-support in Stereolithography[J]. Journal of Mechanical Engineering，2004，40(11):134-138.

[12]Kazhdan M，Bolitho M，Hoppe H. Poisson Surface Reconstruction[C]//Proceedings of the fourth Eurographics Symposium on Geometry Processing. Aire-la-Ville，Switzerland：Eurographics Association，2006：61-70.

(編輯張洋)

Generation of Branching Support Structures Based on Critical Angle Constraint

Shen ZhenhongDai NingLi DaweiWu Changyou

Nanjing University of Aeronautics & Astronautics，Nanjing，210016

In order to optimize support structures’ volume, and save the material and printing time, an automatic generation algorithm was proposed based on critical angle constraint. Firstly, the algorithm detected areas that required support, and the support points were obtained by adaptive sampling based on the area. Secondly, through critical angle constraint, the nodes in branching support structures were calculated, and all nodes information in a tree were saved. Finally, the resulting structure was obtained by the sweep surface after Poisson reconstruction. The algorithm was evaluated by experiments, and the experimental results demonstrate that the algorithm provides a reliable method to ensure the printing stability as well as reducing the printing material and time.

3D printing; critical angle constraint；branching support；Poisson surface reconstruction

沈振宏，男，1990年生。南京航空航天大學機電學院碩士研究生。主要研究方向數字化設計與制造、三維打印技術。戴寧(通信作者)，男，1978年生。南京航空航天大學機電學院副教授。李大偉，男，1989年生。南京航空航天大學機電學院碩士研究生。吳長友 ，男，1989年生。南京航空航天大學機電學院碩士研究生。

2015-06-15

國家高技術研究發展計劃(863計劃)資助項目(SS2013AA040802)；江蘇省科技支撐項目(BE2014009-3)；航空科學基金資助項目(20151652024)；江蘇省三維打印裝備與制造重點實驗室開放課題資助項目(BM2013006)

TH164

10.3969/j.issn.1004-132X.2016.08.020