基于傘形搜索的樹形支撐結構生成算法

王燕寧，張李超+，陳森昌，胡漢偉，史玉升

(1.華中科技大學 材料科學與工程學院 材料成形與模具技術國家重點實驗室，湖北 武漢 430074； 2.廣東技術師范學院 汽車與交通工程學院，廣東 廣州 510635)

0 引言

由于3D打印采用截面逐層堆疊方式構建物體，對于一些3D打印工藝，如熔融沉積型(Fused Deposition Modeling，F(xiàn)DM)、光固化成型(Stereo Lithography Appearance，SLA)、數(shù)字光處理型(Digital Light Processing，DLP)和激光選區(qū)熔化(Selective Laser Melting，SLM)等，需要在打印模型的懸空部位下方添加支撐結構才能保證正常打印。陳巖等[1]指出支撐結構設計主要針對兩方面內容研究：①如何尋找添加支撐結構的部位；②如何生成支撐結構。對于內容①，已經(jīng)有很多成熟的方法，主要有兩種：一是Meshmixer和Magics等軟件采用的基于三角面片外法矢量與水平面夾角來尋找添加支撐部位的方法[2-3];二是根據(jù)對相鄰切片的布爾運算結果進行分析[4]。本文重點研究內容②，3D打印的支撐類型主要有直壁支撐、斜壁支撐[5]、網(wǎng)形支撐[6]、塊狀支撐、柱形支撐[7]等。樹形支撐較上述結構支撐在節(jié)省支撐耗材方面更具優(yōu)勢，本文對樹形支撐結構生成進行深入研究，提出一種基于傘形搜索的樹形支撐結構生成算法。

目前，樹形支撐結構已有部分研究成果。商用軟件MeshMixer采用樹形支撐生成算法生成的支撐結構不對稱且不穩(wěn)定，有時甚至會失敗。Vanek等[8]所提樹形支撐生成方法，支撐結構對稱性較差且不穩(wěn)定，支撐與制件實體表面接觸較多；宋國華等[9]提出的樹形支撐算法采用改進的L-系統(tǒng)算法自下而上生成樹狀結構，這種生成方法對于帶凸臺結構的模型會出現(xiàn)支撐不全的問題；魏瀟然等[10]針對熔融沉積過程中結構不穩(wěn)定的問題，提出一種以熔絲為支撐單位的樹形稀疏支撐結構，該方法雖然在減少耗材和打印時間上進行了優(yōu)化，但是在算法計算時間上不具有優(yōu)勢。

針對上述問題，本文提出一種樹形支撐生成算法，通過傘形搜索算法求解樹形支撐節(jié)點，同時用體素法判斷支撐結構與模型的位置關系，保證了復雜模型的支撐結構穩(wěn)定合理，降低了算法的時間復雜度。

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

圖1所示為本文算法生成的樹形支撐結構圖，為了節(jié)省支撐耗材，樹形支撐結構長度應盡量小。在某種程度上樹形支撐的構建類似于歐式最小生成樹(Euclidean Steiner Minimal Tree，ESMT)問題。ESMT的目標是找到輸入點集中各點連接距離之和最短的連接方式和連接總長度，而樹形支撐結構在三維空間中構建，且需滿足臨界傾角約束條件，因此該問題的復雜程度至少是NP難度[8]。針對該問題，本文提出基于傘形搜索的樹形支撐結構生成算法。

圖2所示為帶凸臺結構的模型圖，對于這種模型或者類似模型，需對支撐與制件實體進行干涉判斷，合理處理支撐落腳點。本文采用體素法對樹形支撐枝干與制件實體進行干涉判斷與處理。

本文樹形支撐結構生成流程如下：以三維模型文件作為輸入，識別待支撐區(qū)域并提取待支撐點，通過傘形搜索算法搜索支撐節(jié)點，生成樹形支撐結構;針對圖2中出現(xiàn)的凸臺結構，在生成樹形支撐結構過程中，對樹形支撐枝干與制件實體進行干涉判斷處理。

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

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

目前，STL文件為3D打印領域中事實上(de facto)的工業(yè)標準，其存儲的是離散的三角形面片頂點坐標和指向實體外方向的單位法向矢量。支撐區(qū)域的判斷方法是比較臨界傾角α與三角面片外法矢量和Z軸所形成夾角的大小。臨界傾角α表示制件實體可以實現(xiàn)自支撐的最大角度，與材料屬性、工藝類型、機器型號等因素相關。

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

2.2 待支撐點提取

完成待支撐區(qū)域識別后提取待支撐點。待支撐區(qū)域為三維坐標點集，即三維凸包，三維凸包的點采樣一般采用柵格法。如圖3所示，先完成待支撐區(qū)域在XOY平面內的投影，再對其進行網(wǎng)格劃分，以劃分的每個網(wǎng)格中心點為射線起點沿Z軸正向與待支撐區(qū)域三角面片求交，所求交點即為待支撐點。

3 樹形支撐結構的生成

獲得待支撐點后，對樹形支撐節(jié)點進行搜索，具體原理如圖4所示。樹形支撐節(jié)點需滿足臨界傾角約束，即樹形支撐各連接枝干與Z軸的夾角不大于臨界傾角α。Vanek等[8]對臨界傾角約束條件進行了實驗證明。圖4中，p1，p2為待支撐區(qū)域中的兩個待支撐點，c1，c2分別為以p1，p2為頂點的圓錐體，α為臨界傾角，q點為c1與c2相交區(qū)域中連接p1p2距離最短的交點。易知兩圓錐體c1與c2相交區(qū)域c內的點都滿足臨界傾角約束條件。為了節(jié)省支撐耗材及支撐打印時間，所構建的樹形支撐結構長度越短越好，因此求解滿足臨界傾角約束條件且連接點p1和p2距離之和最短的點q是樹形支撐結構生成算法的關鍵,本文采用傘形搜索算法進行求解。

3.1 傘形搜索算法

圖4中，區(qū)域c中的點均滿足臨界傾角約束條件，下面證明樹形支撐節(jié)點q在圓錐體c1和c2的對稱面上，同時也在圓錐體c1和c2的圓錐面上。

證明1如圖5a所示，空間內任意一點P2都可以在平面M1N1M2N2上找到其投影點P1，連接P1M1，P1M2，P2M1，P2M2。因P1P2垂直于平面M1N1M2N2，故P1P2垂直于P1M1和P1M2。因斜邊長度大于直角邊，故P2M1>P1M1，P2M2>P1M2。因此，P2M1+P2M2>P1M1+P1M2，連接點M1和點M2距離最短的點必在平面M1N1M2N2上。如圖5b所示，連接兩圓錐面頂點距離之和最短的點必在兩圓錐的對稱面上。

因此，圖4中樹形支撐節(jié)點q的求解問題可以抽象為圖7所示的數(shù)學模型。圖7中，求解以點M1和M2為頂點的兩圓錐面相交曲線與其對稱面M1N1M2N2的交點。其中，點M1和M2的坐標分別為M1(x1,y1,z1)，M2(x2,y2,z2)，圓錐體的半頂角為α，M1N1M2N2為兩圓錐體的對稱面，假設點P(x,y,z)為所求交點。

根據(jù)圖7的數(shù)學模型求解樹形支撐節(jié)點，可通過聯(lián)立兩圓錐面方程和圓錐體對稱面方程求得。以點M1和M2為頂點的圓錐面方程為：

(1)

(y2-y1)x+(x1-x2)y+x2y1-x1y2=0。

(2)

易知，所求交點必在兩圓錐頂點的下方，得不等式

z

(3)

聯(lián)立式(1)～式(3)得

(4)

(5)

(6)

將式(6)代入方程(5)求解，得到點P′(x′,y′,z′)坐標如下：

(7)

反向坐標轉換后，求得點P(x,y,z)的坐標如下：

(8)

3.2 樹形支撐結構生成流程

文中每層支撐點兩兩配對，通過傘形搜索算法求得下一層支撐點，若當前層支撐點為奇數(shù)，則最后一點在下一層的所有支撐點中尋找與其距離最短的點連接。因此，樹形支撐枝干結構類型有兩叉枝干和三叉枝干兩種，如圖8所示。兩種枝干結構中，各枝干與Z軸方向的夾角均不大于臨界傾角α。

樹形支撐生成流程采用貪心算法和迭代的思想，對每個當前支撐點求解連接距離之和最短的連接方式，以逼近樹形支撐結構構建的最優(yōu)解。待支撐點構成支撐點集U，點集V表示新支撐點集，集合E以線段的形式存儲各層支撐點之間的連接關系。通過點集U的不斷迭代，求解完整的樹形支撐結構，具體流程如下：

(1)對當前支撐點Pi∈U，遍歷點集U中所有未搜索點Pj(i≠j)，利用傘形搜索算法求解點Pi與點Pj的新支撐點Qij，選取PiQij+PjQij最小的點Pj作為點Pi的組合點，點Qij為點Pi和點Pj的新支撐點。

(2)點Pi，Pj，Qij構建兩叉枝干，對該枝干與制件實體進行位置判斷。若枝干與制件實體不干涉，則將點Pi和點Pj標記為已搜索點，點Qij為新增支撐點，PiQij和PjQij為新增枝干線段;若枝干與制件實體干涉，則處理方式見4.3節(jié)。

(3)將新增支撐點存入點集V中，新增枝干線段存入集合E中。

(4)遍歷點集U中的未搜索點作為當前支撐點，重復(1)～(3)，直到點集U中無未搜索點，或者只剩下一個未搜索點。對于該獨點P，在點集V中搜索與其距離最短的點Q，判斷PQ是否滿足臨界傾角約束條件，然后進行枝干與制件實體干涉判斷。

(5)點集V迭代點集U，重復(1)～(4)，搜索下一層支撐點。

(6)重復(1)～(5)，直到最終點集U中點個數(shù)不大于1。若最后支撐點P的Z值大于基底的Z坐標，則求點P在基底平面上的投影點Q，將線段PQ存入集合E中。

4 基于體素法的樹形支撐結構干涉處理

圖2中出現(xiàn)的凸臺結構直接生成樹形支撐會出現(xiàn)支撐與實體相交的現(xiàn)象。為解決此問題，本文采用體素法對枝干與制件實體進行干涉判斷，具體流程如圖9所示。圖中對枝干與制件實體的干涉判斷分為3步，制件實體的體素化只在導入三維模型時進行一次，枝干體素化和干涉判斷則在每次生成新枝干時進行。

4.1 STL實體體素化

STL實體體素化采用緊密排列的正六面體(體素)描述STL模型，建立模型體素表，具體算法參考文獻[12]。

4.2 枝干體素化

新生成的連接枝干僅為連接支撐點的線段，判斷連接枝干與STL實體之間的空間位置關系，需要先將連接線段實體化，然后再體素化，圖10所示為流程圖。步驟b～步驟c，將連接枝干骨架線實體化為圓柱體，空間圓柱體參數(shù)方程見文獻[13]；步驟c～步驟d，以圓柱體旋轉軸為局部坐標系的Z軸，沿Z軸方向進行體素化。

4.3 枝干與制件實體干涉判斷與處理

在全局坐標系中，通過制件實體體素表判斷枝干的每一個體素點是否位于制件實體中。枝干結構與制件實體干涉判斷主要有兩種類型：①兩叉枝干與制件實體干涉判斷;②三叉枝干與制件實體干涉判斷。以圖8為例，分別介紹兩種干涉判斷的處理方式。

兩叉枝干與制件實體的位置關系類型有4種：①枝干PiQij,PjQij與制件實體均不相交；②枝干PiQij與制件實體相交，枝干PjQij與制件實體不相交；③枝干PiQij與制件實體不相交，枝干PjQij與制件實體相交；④枝干PiQij,PjQij與制件實體均相交。

類型①，枝干與制件實體不相交，樹形支撐生成流程中已介紹處理方式。類型②～④，枝干與制件實體相交。對于當前點Pi，類型②～④中點Qij均失效。其中，類型②，④可通過三角面片求交得到點Pi新的支撐點，類型③則無法求得，因此放棄類型③中Pi與Pj組合，將點Pi存入點集V中。對于類型②，通過射線PiQij與三角面片求交，求得點Qi，將線段PiQi存入集合E，將點Pi標記為已搜索；對于類型④，通過射線PiQij、射線PjQij與三角面片求交，分別求得交點Qi和Qj，將線段PiQi和線段PjQj存入集合E，將點Pi和點Pj標記為已搜索。

三叉枝干與制件實體的干涉判斷分為兩步：①兩叉枝干與制件實體干涉判斷；②新增枝干與制件實體干涉判斷。第②步有新增枝干與制件實體相交、新增枝干與制件實體不相交兩種情況。若新增枝干與制件實體相交，則通過射線PkQij與三角面片求交求得交點Qk，將線段PkQk存入集合E；若新增枝干與制件實體不相交，則將線段PkQij存入集合E。

以上為體素法判斷樹形枝干與制件實體的方法，對圖2中的凸臺結構采用該方法，所生成的樹形支撐結構圖11所示。

5 算法驗證

本文算法在樹形支撐節(jié)點搜索和支撐與制件實體干涉這兩方面進行了改進優(yōu)化：①提出傘形搜索算法，在滿足臨界傾斜角約束條件下快速求得任意兩支撐點的最短距離連接點，從而高效生成完整的樹形支撐結構；②將制件實體和樹形支撐各枝干分別體素化，判斷兩者是否干涉并進行干涉處理，解決了圖2所示帶凸臺結構等復雜模型的支撐問題，且該算法避免了對大量三角面片進行求交，降低了算法的時間復雜度。

傳統(tǒng)干涉判斷采用三角面片求交算法，設制件實體三角面片數(shù)為n，樹形支撐枝干數(shù)為m，則三角面片求交算法的時間復雜度為o(mn)，由于m遠小于n，其漸進時間復雜度為O(n)。假設枝干平均體素數(shù)為k，則體素法干涉判斷的時間復雜度為o(mk)，因為m,k遠小于n，所以其漸進時間復雜度為O(1)。

將本文算法與商用軟件Meshmixer算法進行比較，兩種算法采用相同的支撐生成密度，對比支撐生成結構的穩(wěn)定性和算法所需的時間。圖12所示為本文算法與Meshmixer軟件生成的樹形支撐結構圖，其中圖12a、圖12c、圖12e為本文算法生成的支撐結構圖，圖12b、圖12d、圖12f為Meshmixer軟件生成的支撐結構圖。對比可以看出，本文算法生成的支撐結構對稱性更好，穩(wěn)定性更優(yōu)。而且Meshmixer軟件生成的支撐對于某些情況不合適，需要人工干預[14]，例如圖12b中支撐與平臺的連接不符合力學要求。

表1所示為圖12中臺燈、扁嘴鳥、Bunny模型，用Meshmixer軟件和本文算法生成樹形支撐結構所用的時間。測試平臺參數(shù)為Intel?CoreTMi3-4150 CPU @ 3.50 GH 處理器、8 G內存、64位操作系統(tǒng)。由表1可看出，本文算法所用時間均比Meshmixer軟件短，雖然Bunny模型的三角面片數(shù)量眾多，但是待支撐區(qū)域少，且模型較小，因此兩種算法所用的時間相差不大。對比扁嘴鴨和臺燈，當三角面片數(shù)量或者模型包圍盒大小增大時，Meshmixer軟件所用時間的增長速度明顯大于本文算法。綜上所述，相比于Meshmixer，在支撐生成密度相同的情況下，本文算法生成的支撐結構更優(yōu)，且算法所用時間更短。

表1 本文算法與Meshmixer算法時間對比表

圖13所示為本文算法對帶凸臺結構及類似模型的處理結果。圖13a的上方圖片為本文算法處理Bunny模型中耳朵的細節(jié)，下方圖片為本文算法處理雪人模型鼻子的細節(jié)。由圖13可見，帶凸臺或類似結構的模型的支撐落腳在凸臺或實體上，不會出現(xiàn)支撐貫穿實體的情況，因此本文算法能合理處理支撐與實體的干涉問題。

6 結束語

本文提出傘形搜索的樹形支撐生成算法。算法以待支撐點為輸入求解新支撐點，逐層獲取樹形支撐枝干關系，采用體素法對枝干和制件實體進行干涉判斷。樹形支撐生成流程采用貪心算法和迭代的思路逼近最優(yōu)解，并通過體素法判斷枝干與制件實體的干涉，避免了大量三角面片求交，降低了算法的時間復雜度。從算法驗證可以看出，本文算法在生成樹形支撐結構和提高支撐生成效率上具有較好水平。

目前，本文主要關注樹形支撐結構生成，對具體工藝的支撐優(yōu)化研究較少。例如，支撐截面形狀、截面大小對支撐穩(wěn)定性的影響，如何通過支撐避免制件出現(xiàn)應力變形等，這將是未來的研究方向。