魏瀟然,耿國華,張雨禾

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院,陜西西安 710069)

?

3D打印中的模型去支撐劃分方法

魏瀟然,耿國華,張雨禾

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院,陜西西安 710069)

摘要:打印模型適應(yīng)打印空間,模型懸空部分添加支撐,這是3D打印過程中需要解決的兩類重要問題,現(xiàn)有算法無法同時解決這兩類問題.針對這兩類問題,提出一種模型劃分算法,將模型劃分為適應(yīng)打印空間的錐體:錐體是一種打印時不需要支撐結(jié)構(gòu)的圖形.該算法首先采用區(qū)域生長方法對模型表面進(jìn)行分區(qū),分析各區(qū)域法向獲取多個候選劃分方向;用候選劃分方向生成候選切面劃分模型,若劃分后的子模型為非錐體,則用相同的方法繼續(xù)對子模型進(jìn)行劃分,直到所有子模型均為錐體.多個候選劃分切面會生成多組劃分方式,一組劃分方式可以表示為一棵樹,利用評價函數(shù)計算劃分價值,并采用集束搜索對解空間搜索獲得價值最大的樹,即為最優(yōu)劃分.實驗結(jié)果表明,該算法能將模型劃分為不需要支撐結(jié)構(gòu)同時適應(yīng)打印空間的子模型.

關(guān)鍵詞:3D打印;模型劃分;支撐結(jié)構(gòu);錐體

三維(3-Dimensional,3D)打印是快速成型領(lǐng)域中的革命性技術(shù),隨著3D打印技術(shù)的成熟,其在工業(yè)設(shè)計、制造業(yè)、醫(yī)學(xué)、建筑等領(lǐng)域已有廣泛的應(yīng)用.

3D打印通常在一個固定的打印空間中進(jìn)行,若打印模型超出該空間,必須將模型劃分成零件打印后再裝配.關(guān)于3D打印中的模型劃分已有大量研究.文獻(xiàn)[1]提出一種基于曲率的模型劃分方式,該算法范用性較差.文獻(xiàn)[2]用平面切分模型進(jìn)行劃分,對影響劃分后模型形狀的因素進(jìn)行分析,并用集束搜索方法選擇較優(yōu)劃分方式.文獻(xiàn)[3]將模型體元化并對體元進(jìn)行聚類分析,將模型劃分為易打印結(jié)構(gòu).文獻(xiàn)[4]分析魯班鎖原理將模型拼合部分構(gòu)造成魯班鎖樣式,模型裝配穩(wěn)固性很高并且不需要粘合劑.支撐結(jié)構(gòu)同樣是3D打印研究中的熱點問題,3D打印必須在支撐面上打印,而大多3D模型中存在懸空區(qū)域,故必須為其構(gòu)造支撐結(jié)構(gòu),支撐結(jié)構(gòu)不僅需要人工輔助構(gòu)造,浪費打印材料,而且在拆除支撐結(jié)構(gòu)時容易對模型造成破壞.關(guān)于支撐結(jié)構(gòu)的研究,主要包括提升支撐穩(wěn)定度和減少支撐材料兩方面.文獻(xiàn)[5]將原本柱體支撐結(jié)構(gòu)設(shè)計為錐體,減小了支撐結(jié)構(gòu)的體積.文獻(xiàn)[6]通過減少支撐結(jié)構(gòu)下層的體積和復(fù)雜性進(jìn)一步減少了支撐結(jié)構(gòu)體積.文獻(xiàn)[7]將建筑學(xué)中的絞架結(jié)構(gòu)引入3D打印支撐結(jié)構(gòu)設(shè)計中,從力學(xué)角度考慮設(shè)計了一種抗壓的穩(wěn)固支撐結(jié)構(gòu).文獻(xiàn)[8]在計算稀疏支撐點的基礎(chǔ)上,利用垂直支柱并在其間橋接設(shè)計支撐結(jié)構(gòu).許多公司也開發(fā)了生成支撐結(jié)構(gòu)的軟件,Autodesk公司的meshmixer軟件選取若干離散支撐點來設(shè)計支撐結(jié)構(gòu),并利用樹形結(jié)構(gòu)將這些支撐點連接起來,但該軟件生成的支撐結(jié)構(gòu)可靠性方面仍有待提高.Makerbot公司的makerware軟件利用大量交錯支架生成支撐結(jié)構(gòu).也有研究者從支撐材料考慮,用可溶解材料打印支撐結(jié)構(gòu),使支撐結(jié)構(gòu)更易分離[9].也有學(xué)者對模型內(nèi)部支撐結(jié)構(gòu)進(jìn)行研究,以提高模型的穩(wěn)固性和抗壓能力[10-12].

3D打印中支撐結(jié)構(gòu)受模型形狀影響較大.若模型不存在懸空部分,則打印時就不需要為其構(gòu)造支撐結(jié)構(gòu).現(xiàn)有算法在模型劃分時大多僅考慮劃分均勻、易于組裝、適應(yīng)打印空間等問題,較少考慮劃分后模型支撐結(jié)構(gòu)問題,導(dǎo)致劃分后模型打印時需要大量支撐結(jié)構(gòu).

針對以上問題,筆者提出一種自動模型分區(qū)算法.通過對模型表面分區(qū)并對各區(qū)域法向分析,尋找候選劃分方向,根據(jù)這些候選劃分方向構(gòu)造切平面劃分模型,將這些劃分構(gòu)造成樹形式,通過集束搜索方法搜索最優(yōu)劃分,將模型劃分為不需要支撐結(jié)構(gòu)的錐體.該算法同時解決模型的打印空間適應(yīng)問題和支撐結(jié)構(gòu)耗材問題.實驗表明,該方法能有效將模型劃分為符合打印空間要求的、尺寸均勻且不需要支撐結(jié)構(gòu)的子模型.

1 去支撐分區(qū)算法

1.1 算法概述

若模型S存在一基底平面B,S內(nèi)任意一點與該點在基底平面的垂直投影連線均在S內(nèi),則稱模型S為錐體.打印錐體模型時不需要支撐結(jié)構(gòu)[3].文中算法目標(biāo)是將模型劃分為一組適應(yīng)打印空間的錐形模型.

圖1 基底支撐平面

定義模型曲面上所有頂點法向量方向指向模型內(nèi)部,如圖1所示,基底平面B與平面P1的夾角在π/2到π區(qū)間,以B作為基底,以B法向量方向打印,平面P1不需要支撐結(jié)構(gòu),文中后續(xù)簡稱基底B1能支撐平面P1;平面P2與B的夾角在0到π/2區(qū)間,以B作為基底,以B法向量方向打印,平面P2需要支撐結(jié)構(gòu),文中后續(xù)簡稱基底B不能支撐平面P2.將基底法向量的方向稱為基底方向.模型為錐體的充分必要條件為,模型存在一個基底平面B,使得模型上所有頂點的法向量與B法向量的夾角在[π/2,π]區(qū)間.

定理1 若一封閉模型存在基底B,能支撐模型其他所有表面區(qū)域,則該模型為錐體.該錐體可以以B為底面,無支撐打印.

若模型表面存在一組連續(xù)曲面,則可以根據(jù)定理1求得這些連續(xù)曲面的共同基底的基底方向N;若存在以N為法向量的平面B,則該平面能與這些連續(xù)曲面組成一個封閉三維模型S,可以平面B切分模型,得到子模型S,以B為底部可無支撐打印S.

劃分除需滿足錐體條件外,還需要滿足打印空間條件.設(shè)打印空間為R(x,y,z),則最終劃分后的所有子模型的最小有向包圍盒(OBB包圍盒)必須能包含在R內(nèi).

該算法首先用區(qū)域生長方法將模型表面分區(qū),獲取能支撐各區(qū)域的基底方向;將各區(qū)域根據(jù)支撐基底方向進(jìn)行聚類,分析聚類后各類間相交基底方向區(qū)域,獲取數(shù)個候選基底方向.以候選基底方向間隔一定距離生成切平面劃分模型,計算每次劃分的價值.將所有劃分建立成一顆劃分樹,每次劃分為一個樹節(jié)點,采用集束搜索方式搜索,每層僅選取較優(yōu)的數(shù)個節(jié)點.若劃分后模型不全為錐體,對不為錐體的模型繼續(xù)劃分,直到所有劃分均為錐體.最終從符合條件的錐體劃分方案中選取最優(yōu)劃分.圖2(a)為模型劃分結(jié)果,圖2(b)為該劃分的樹表示.

圖2 模型劃分結(jié)果示意圖

1.2 算法實現(xiàn)

1.2.1 模型分區(qū)

首先采用區(qū)域生長方法對模型進(jìn)行粗分區(qū).

(1)對模型上所有頂點進(jìn)行掃描,若存在沒有歸屬的頂點,則以該頂點為種子點進(jìn)行區(qū)域生長.

(2)一頂點為種子點,遍歷該頂點的鄰域點.如果鄰域點與種子點滿足法向夾角小于α,則將鄰域頂點加入種子點鄰域,之后以這些鄰域點為種子點繼續(xù)區(qū)域生長.

(3)直到模型上所有頂點都有歸屬區(qū)域,區(qū)域生長完成,如圖3(a)、3(d)所示.

圖3 區(qū)域分割與區(qū)域聚類

若區(qū)域中法向變化較平滑,則會劃分出過大區(qū)域,如圖3(a)中燈底部淺灰色區(qū)域;若使用該分區(qū)進(jìn)行后續(xù)計算,則會導(dǎo)致最優(yōu)基底方向計算不準(zhǔn)確.故若區(qū)域a中存在兩頂點法向夾角大于n,則需將區(qū)域細(xì)分:利用主成分分析法獲取該區(qū)域中法向變化最大的方向N,以區(qū)域中心點Vave為平面一點,N為法向量做平面將區(qū)域分成兩部分.圖3(a)、圖3(d)中模型細(xì)分獲得分區(qū)如圖3(b)、圖3(e)所示.

模型最終分區(qū)為A(a0,a1…an),分區(qū)的法向量Ni為區(qū)域中所有頂點法向量平均值.若區(qū)域中法向量方向一致,則將該區(qū)域加入基底候選區(qū)域集Φ.人造模型中一般大多在其表面存在一個或多個基底候選區(qū)域,如圖3臺燈的底座就為基底候選區(qū)域.

1.2.2 候選切面法向量計算

為了快速計算候選切面方向,對區(qū)域進(jìn)行聚類.

根據(jù)每個區(qū)域法向量夾角θi(θx,θy,θz)計算區(qū)域間距離,兩區(qū)域間距離定義為

采用均值距離層次聚類方法,對區(qū)域進(jìn)行聚類,聚類的終止條件為,若新加入?yún)^(qū)域與簇中任一區(qū)域夾角距離大于λ.聚類完成后模型如圖3(c)、3(f)所示.

在笛卡爾坐標(biāo)系下,ai區(qū)域的法向量Ni與x,y,z這3個軸的夾角為θi(θix,θiy,θiz),文中后續(xù)通稱法向量夾角,根據(jù)1.1節(jié)中描述,能支撐ai區(qū)域的基底B的法向量夾角范圍為

若切平面法向量在范圍內(nèi),則切平面可以支撐ai區(qū)域.各區(qū)域?qū)?yīng)的基底法向量夾角范圍為R(θ0),…,R(θn).

根據(jù)定理1,期望每次切分后子模型一基底區(qū)域能支撐更多的其他區(qū)域.為滿足這一期望,要求切面方向能支撐盡可能多的區(qū)域,同時保證切面能較多地被其他基底候選區(qū)域支撐.

首先確定能支撐盡可能多區(qū)域的切面法向量.通過求各簇之間支撐范圍交集獲得,若區(qū)域間存在非空交集,該交集內(nèi)法向量對應(yīng)的可支撐區(qū)域為交集包含的區(qū)域數(shù),獲取數(shù)個包含最多簇的交集區(qū)域.在每個交集區(qū)域中均勻采樣數(shù)個方向,獲取候選方向集合.

對每個候選方向求基底候選區(qū)域集Φ中能支撐這些方向的區(qū)域數(shù)量,每個候選方向的價值為其能支撐的簇和可以支撐該方向的基底數(shù)量和,取價值最高的n個方向作為最終的候選切面方向.

1.2.3 劃分切面價值計算

確定候選切面法向量后,沿法向量每隔距離η生成一個切平面將模型切分,計算每次切分后模型的切分價值.

評價切分優(yōu)劣主要有兩方面考慮,即空間期望和錐體期望.空間期望希望切分后模型均勻且各部分盡可能大,錐體期望希望切分后模型各部分更趨近錐體.

計算空間期望:設(shè)模型為M,n次切分后劃分模型為M0,…,Mn-1,模型包圍盒體積為O(M),劃分后模型包圍盒體積為O(Mi),劃分的空間期望如式(3)所示,Ev為劃分價值,Ev越大,劃分空間價值越高.

圖4 切平面劃分模型

f(Pi,Pj)函數(shù)判斷切分平面Pj是否能支撐區(qū)域Pi.若f(Pi,Pj)=1,則Pj可支撐Pi;若f(Pi,Pj)= 0,則Pj不能支撐Pi.nA為模型區(qū)域數(shù)量,nΦ為候選基底區(qū)域數(shù)量.錐體期望計算公式為

式(5)將切面可支撐的區(qū)域占總區(qū)域的比例和可支撐切面的基底占所有基底的比例相加,Ep越大,劃分的錐體價值越高.

將空間價值與錐體價值相乘,可獲得切面劃分的價值,即

1.2.4 集束搜索最優(yōu)解

模型上的一組劃分可構(gòu)造為一棵二叉樹,如圖2(b)所示.樹中每個節(jié)點代表一次劃分.利用集束搜索方法獲取一棵二叉樹,要求總體劃分價值最高且子模型均為椎體,設(shè)搜索束寬為n,搜索方法如下:

(1)選取原始模型的n個較優(yōu)劃分作為n棵樹的根節(jié)點.

(2)將n棵樹向下層劃分,對一棵樹中所有未達(dá)到終止條件的節(jié)點向下劃分,每個節(jié)點劃分時均取n個較優(yōu)劃分作為候選,在每棵樹中選取累加價值最大的n組劃分作為該層劃分結(jié)果.計算所有樹的下層劃分后,獲取nn棵新樹,在這些樹中取總體價值最大的n組劃分作為該層劃分結(jié)果.

(3)將樹繼續(xù)按照步驟(2)向下劃分,直到所有節(jié)點到達(dá)終止條件.節(jié)點終止條件為按該節(jié)點劃分后的兩個子模型體積適應(yīng)打印空間且不為錐體或按該節(jié)點劃分后該樹價值大于任一已獲得搜索結(jié)果.由于每次劃分都會使得可能滿足錐體的區(qū)域增加,最終所有區(qū)域都會滿足錐體條件,最差情況為所有子模型均為四棱錐.若模型表面較復(fù)雜,則模型可能劃分過小,打印效果會受到影響,故也可設(shè)置強(qiáng)制終止條件.強(qiáng)制終止條件為模型體積小于v,強(qiáng)制終止的打印模型仍然能夠打印,但需要為其構(gòu)造支撐結(jié)構(gòu).

(4)當(dāng)所有劃分終止后,取搜索結(jié)果中價值最大一組劃分為最優(yōu)劃分結(jié)果.

2 實驗結(jié)果與分析

實驗測試集選用40個3D模型數(shù)據(jù),模型主要來源于COSEG數(shù)據(jù)集.

文中算法主要包含4個參數(shù),區(qū)域生長中相鄰頂點生長法向夾角α設(shè)為π/36,細(xì)分區(qū)域夾角閾值n設(shè)為π/2,聚類中類間最大距離λ設(shè)為31/2π/2,掃描分區(qū)間隔η取值為模型包圍盒最小軸長的1/20.集束搜索的束寬取10.

實驗采用Makerbot Replicator2X打印機(jī),打印參數(shù)設(shè)置為層厚0.3 mm,噴頭掃描速度120 mm/s,噴頭空駛速度150 mm/s,打印材料為ABS樹脂.

圖5為模型打印后的零配件及裝配后結(jié)果,裝配時采用粘合劑粘合.由圖5可見,每一個子模塊都為錐體,打印時均不需要為其添加支撐結(jié)構(gòu).打印時指定打印空間為5 cm×5 cm×5 cm,可見各圖中模型大小分布均勻.圖5(c)模型由中間對稱軸剖成兩部分可分成兩錐體,但由于剖分后模型超出打印空間,故最終被分為4部分.

圖5 模型分區(qū)打印及組裝

實驗結(jié)果顯示各零配件在無支撐情況下成型效果良好,裝配后與原模型無明顯差異,粘合處可以精確吻合.

表1為原模型與拆分后模型打印時間、打印耗材對比,可見拆分后打印模型由于不需要支撐結(jié)構(gòu),其耗材明顯較少,并且打印時間隨之減少.

表1 算法性能統(tǒng)計

實驗結(jié)果表明,文中算法能有效劃分超出打印空間的模型使其符合打印空間要求,并且能有效減少打印耗材.

3 總結(jié)與展望

針對3D打印中打印物體超出打印空間、打印物體需要過多支撐材料兩問題,提出了一種模型劃分方法,將模型分為若干可包含在打印空間內(nèi)的子模型,并且每個子模型均為錐體,不需要支撐即可打印.實驗結(jié)果表明,針對多組模型,該算法均能有效將其分為大小均勻的子模型,并且可以不需要支撐結(jié)構(gòu)打印.對超出打印空間的模型分區(qū)打印的同時節(jié)約了打印支撐材料.

文中算法主要針對人造模型,該類模型表面通常都較規(guī)律.若模型表面過于特殊,則模型并不能均勻劃分錐體.針對這類模型,需要設(shè)計能劃分均勻并且附帶較少支撐結(jié)構(gòu)的分區(qū)算法,這也是后續(xù)的研究方向.

參考文獻(xiàn):

[1]HAO J,FANG L,WILLIAMS R.An Efficient Curvature-based Partitioning of Large-scale Stl Models[J].Rapid Prototyping Journal,2011,17(2):116-127.

[2]LUO L,BARAN I,RUSINKIEWICZ S,et al.Chopper:Partitioning Models into 3D-printable Parts[J].ACM Transactions on Graphics,2012,31(6):129.

[3]HU R,LI H,ZHANG H,et al.Approximate Pyramidal Shape Decomposition[J].ACM Transactions on Graphics,2014,33(6):213.

[4]XIN S,LAI C F,FU C W,et al.Making Burr Puzzles from 3D Models[J].ACM Transactions on Graphics,2011,30(4):97.

[5]HUANG X,YE C,WU S,et al.Sloping Wall Structure Support Generation for Fused Deposition Modeling[J].The International Journal of Advanced Manufacturing Technology,2009,42(11/12):1074-1081.

[6]HEIDE E K.Method for Generating and Building Support Structures with Deposition-based Digital Manufacturing Systems:US Patent Application 12/687996[P].2010-01.

[7]WANG W,WANG T,YANG Z,et al.Cost-effective Printing of 3D Objects with Skin-frame Structures[J].ACM Transactions on Graphics,2013,32(6):177.

[8]DUMAS J,HERGEL J,LEFEBVRE S.Bridging the Gap:Automated Steady Scaffoldings for 3D Printing[J].ACM Transactions on Graphics,2014,33(4):98.

[9]KRITCHMAN E,GOTHAIT H,MILLER G.System and Method for Printing and Supporting Three Dimensional Objects:US Patent 7364686[P].2008-04.

[10]LU L,SHARF A,ZHAO H,et al.Build-to-last:Strength to Weight 3D Printed Objects[J].ACM Transactions on Graphics,2014,33(4):97.

[11]B?CHER M,WHITING E,BICKEL B,et al.Spin-it:Optimizing Moment of Inertia for Spinnable Objects[J].ACM Transactions on Graphics,2014,33(4):96.

[12]ZHANG X,XIA Y,WANG J,et al.Medial Axis Tree-an Internal Supporting Structure for 3D Printing[J].Computer Aided Geometric Design,2015,35(5):149-162.

(編輯:李恩科)

簡 訊

日前,我校榮獲2015全國大學(xué)生數(shù)學(xué)建模競賽一等獎4項、二等獎6項(規(guī)定每校最多可獲10項),并有3份答卷入選全國優(yōu)秀論文(全國共10篇).其中一支團(tuán)隊奪得全國本科組惟一的MATLAB創(chuàng)新獎.這是繼2014年、2015年我校連獲國際數(shù)學(xué)建模競賽特等獎之后的再次突破.學(xué)校同時獲得陜西賽區(qū)優(yōu)秀組織工作獎.

摘自《西電科大報》2015.11.28

Partition model into 3D-printable and no supporting parts

WEI Xiaoran,GENG Guohua,ZHANG Yuhe
(School of Information Science and Technology,Northwestern Univ.,Xi’an 710069,China)

Abstract:The printing object must fit into the printing working volume and overhangs require a disposable support structure to be added,which are two main problems in the 3D printing process.Existing algorithms cannot solve these two problems at the same time.To solve these problems,we present a model partition algorithm,dividing the model into the pyramidal fitting printing working volume,with the pyramidal having the shape which can be printed without a supporting structure.Firstly,we partition the model surface using the region growing method and analyze the region’s normal vector to determine the candidate dividing directions.Secondly,we use the candidate dividing directions to generate candidate dividing planes in order to segment the model.If the divided sub-model is not a pyramidal,continue segmenting the sub-model by using the same method until all of the sub-models are pyramidal.The candidate dividing planes may generate multi-group division modes.Each division mode constructs a tree,the evaluation function is employed to appraise the dividing values and the beam search method is utilized to search the largest value tree in the solution space which is the optimal partition.Experimental results show that the proposed algorithm can divide the model into sub-models which needn’t support structures and fit into the printing working volume.

Key Words:3D printing;model partition;support structure;pyramidal

作者簡介:魏瀟然(1987-),男,西北大學(xué)博士研究生,E-mail:wxran1987@163.com.

基金項目:國家自然科學(xué)基金資助項目(61373117)

收稿日期:2015-06-04

doi:10.3969/j.issn.1001-2400.2016.02.031

中圖分類號:TP391

文獻(xiàn)標(biāo)識碼:A

文章編號:1001-2400(2016)02-0180-06