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