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

(1.華中科技大學(xué) 材料科學(xué)與工程學(xué)院 材料成形與模具技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074； 2.廣東技術(shù)師范學(xué)院 汽車與交通工程學(xué)院，廣東 廣州 510635)

0 引言

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

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

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

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

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

圖2所示為帶凸臺(tái)結(jié)構(gòu)的模型圖，對(duì)于這種模型或者類似模型，需對(duì)支撐與制件實(shí)體進(jìn)行干涉判斷，合理處理支撐落腳點(diǎn)。本文采用體素法對(duì)樹形支撐枝干與制件實(shí)體進(jìn)行干涉判斷與處理。

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

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

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

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

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

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

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

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

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

3.1 傘形搜索算法

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

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

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

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

(1)

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

(2)

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

z

(3)

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

(4)

(5)

(6)

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

(7)

反向坐標(biāo)轉(zhuǎn)換后，求得點(diǎn)P(x,y,z)的坐標(biāo)如下：

(8)

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

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

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

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

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

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

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

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

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

4 基于體素法的樹形支撐結(jié)構(gòu)干涉處理

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

4.1 STL實(shí)體體素化

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

4.2 枝干體素化

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

4.3 枝干與制件實(shí)體干涉判斷與處理

在全局坐標(biāo)系中，通過制件實(shí)體體素表判斷枝干的每一個(gè)體素點(diǎn)是否位于制件實(shí)體中。枝干結(jié)構(gòu)與制件實(shí)體干涉判斷主要有兩種類型：①兩叉枝干與制件實(shí)體干涉判斷;②三叉枝干與制件實(shí)體干涉判斷。以圖8為例，分別介紹兩種干涉判斷的處理方式。

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

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

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

以上為體素法判斷樹形枝干與制件實(shí)體的方法，對(duì)圖2中的凸臺(tái)結(jié)構(gòu)采用該方法，所生成的樹形支撐結(jié)構(gòu)圖11所示。

5 算法驗(yàn)證

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

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

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

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

表1 本文算法與Meshmixer算法時(shí)間對(duì)比表

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

6 結(jié)束語

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

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