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

魏瀟然,耿國華,張雨禾

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

?

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

魏瀟然,耿國華,張雨禾

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

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

關鍵詞:3D打印;模型劃分;支撐結構;錐體

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

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

3D打印中支撐結構受模型形狀影響較大.若模型不存在懸空部分,則打印時就不需要為其構造支撐結構.現有算法在模型劃分時大多僅考慮劃分均勻、易于組裝、適應打印空間等問題,較少考慮劃分后模型支撐結構問題,導致劃分后模型打印時需要大量支撐結構.

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

1 去支撐分區算法

1.1 算法概述

若模型S存在一基底平面B,S內任意一點與該點在基底平面的垂直投影連線均在S內,則稱模型S為錐體.打印錐體模型時不需要支撐結構[3].文中算法目標是將模型劃分為一組適應打印空間的錐形模型.

圖1 基底支撐平面

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

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

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

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

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

圖2 模型劃分結果示意圖

1.2 算法實現

1.2.1 模型分區

首先采用區域生長方法對模型進行粗分區.

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

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

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

圖3 區域分割與區域聚類

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

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

1.2.2 候選切面法向量計算

為了快速計算候選切面方向,對區域進行聚類.

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

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

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

若切平面法向量在范圍內,則切平面可以支撐ai區域.各區域對應的基底法向量夾角范圍為R(θ0),…,R(θn).

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

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

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

1.2.3 劃分切面價值計算

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

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

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

圖4 切平面劃分模型

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

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

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

1.2.4 集束搜索最優解

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

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

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

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

(4)當所有劃分終止后,取搜索結果中價值最大一組劃分為最優劃分結果.

2 實驗結果與分析

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

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

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

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

圖5 模型分區打印及組裝

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

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

表1 算法性能統計

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

3 總結與展望

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

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

參考文獻:

[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全國大學生數學建模競賽一等獎4項、二等獎6項(規定每校最多可獲10項),并有3份答卷入選全國優秀論文(全國共10篇).其中一支團隊奪得全國本科組惟一的MATLAB創新獎.這是繼2014年、2015年我校連獲國際數學建模競賽特等獎之后的再次突破.學校同時獲得陜西賽區優秀組織工作獎.

摘自《西電科大報》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-),男,西北大學博士研究生,E-mail:wxran1987@163.com.

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

收稿日期:2015-06-04

doi:10.3969/j.issn.1001-2400.2016.02.031

中圖分類號:TP391

文獻標識碼:A

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