面向喷头空行程长度最小化的多零件优化布局方法

doi:10.11996/JG.j.2095-302X.2023061239

图学学报 ›› 2023, Vol. 44 ›› Issue (6): 1239-1250.DOI: 10.11996/JG.j.2095-302X.2023061239

• 计算机图形学与虚拟现实 • 上一篇下一篇

面向喷头空行程长度最小化的多零件优化布局方法

邢晓月(), 陶秀挺, 王姝钫, 潘万彬()

杭州电子科技大学人文艺术与数字媒体学院，浙江杭州 310018

收稿日期:2023-07-21 接受日期:2023-09-20 出版日期:2023-12-31 发布日期:2023-12-17
通讯作者: 潘万彬(1983-)，男，副教授，博士。主要研究方向为CAD、3D打印等。E-mail：panwanbin@hdu.edu.cn
作者简介:
邢晓月(1998-)，女，硕士研究生。主要研究方向为3D打印。E-mail：xiaoyuexing@hdu.edu.cn
基金资助:
工业和信息化部项目(TC2008033);浙江省科技计划项目(2018C01030);浙江大学计算机辅助设计与图形系统全国重点实验室开放课题(A2328)

Optimizing the multi-part layout to minimize the empty travel distance of nozzle

XING Xiao-yue(), TAO Xiu-ting, WANG Shu-fang, PAN Wan-bin()

School of Media and Design, Hangzhou Dianzi University, Hangzhou Zhejing 310018, China

Received:2023-07-21 Accepted:2023-09-20 Online:2023-12-31 Published:2023-12-17
Contact: PAN Wan-bin (1983-), associate professor, Ph.D. His main research interests cover CAD, 3D printing, etc. E-mail：panwanbin@hdu.edu.cn
About author:
XING Xiao-yue (1998-), master student. Her main research interest covers 3D printing. E-mail：xiaoyuexing@hdu.edu.cn
Supported by:
Project of Ministry of Industry and Information Technology(TC2008033);Science and Technology Project of Zhejiang Province(2018C01030);Open Project Program of the State Key Laboratory of CAD&CG,Zhejiang University(A2328)

摘要/Abstract

摘要：

多零件在打印腔室中的布局往往直接影响熔融沉积批量制造的效率和能力。同时，喷头空行程长度对上述效率和能力具有显著的影响。为此，提出了一种面向空行程最小化的多零件优化布局方法，通过优化地减少零件之间喷头的空行程长度来提升熔融沉积批量制造的效率以及打印腔室可容空间。首先，为兼顾空行程长度计算的效率(如加速几何干涉检测)和计算的准确度，以层厚为基准，构建每个零件相应的、逐层堆叠的体素代理模型。然后，基于贪心策略和粒子群优化算法，以逐对累积的方式确定每个体素代理模型的放置顺序和放置位置。最后，将体素代理模型置换为对应的零件，获得输入零件集紧凑的布局。在一组形状复杂的零件集上开展实验。结果表明：在相同的衡量标准下，该方法相比于Magics空行程总量约减少了31.17%。与现有的商业化软件中的布局功能相比，该方法在实施批量制造形状复杂零件集时具有可显著减少喷头空行程长度总量的巨大潜力。

关键词: 批量制造, 体素代理模型, 零件布局优化, 熔融沉积, 3D打印

Abstract:

The layout of multi-part in the printing chamber often directly impacts the efficiency and capability of batch manufacturing for fused filament fabrication (FFF). Meanwhile, the total empty travel distance of the printing nozzle exerts a significant impact on the efficiency and capability mentioned above. Therefore, an optimized layout method for multi-part was proposed, taking into account the empty travel distance. The method improved the efficiency of FFF's batch manufacturing and the printing chamber's available space by reducing the empty travel distance of the printing nozzle between each part. Firstly, to balance the efficiency (such as the acceleration of geometric interference detection) and the accuracy of empty travel distance calculation, the proposed approach constructed the corresponding voxel-based surrogate model layer by layer for each part. Then, based on a greedy strategy and PSO, this paper proposed a method for determining the order and position of each voxel-based surrogate model's placement pair by pair. Finally, the voxel-based surrogate models were replaced with their corresponding parts, and the input part set was compactly arranged. Experiments were conducted on a set of complex-shaped parts. The results showed that the proposed method could reduce the total empty distance of the printing nozzle by 31.17% compared to Magics under the same measuring standard. Furthermore, compared with the layout function in existing commercial software, this method exhibited enormous potential for significantly reducing the total empty distance of the printing nozzle for batch manufacturing with FFF, especially for the set of complex-shaped parts.

Key words: batch manufacturing, voxel-based surrogate model, part layout optimization, fused filament fabrication, 3D printing

中图分类号:

TB23

邢晓月, 陶秀挺, 王姝钫, 潘万彬. 面向喷头空行程长度最小化的多零件优化布局方法[J]. 图学学报, 2023, 44(6): 1239-1250.

XING Xiao-yue, TAO Xiu-ting, WANG Shu-fang, PAN Wan-bin. Optimizing the multi-part layout to minimize the empty travel distance of nozzle[J]. Journal of Graphics, 2023, 44(6): 1239-1250.

图/表 22

图1 打印喷头在2零件间移动的空行程图示((a)切片好的2个零件；(b)切片层1喷头移动的空行程长度；(c)喷头移动的总空行程长度)

Fig. 1 The empty travel distance of the nozzle between two parts ((a) Sliced two parts; (b) The empty travel distance of the nozzle moving in layer one; (c) The total empty travel distance)

图2 布局工作中对零件的不同表示方式

Fig. 2 Different ways of representing parts in layout work

图3 本文方法流程图

Fig. 3 The flow chart of the method in this paper

图4 快速逐层构建输入零件的体素代理模型((a)读取信息；(b)标记悬空区域；(c)轴向包围盒；(d)逐层体素化；(e)得到表面体素；(f)代理模型；(g)代理模型(可实现自支撑)；(h)体素的属性表示)

Fig. 4 Quickly construct the voxel-based surrogate model of input parts layer by layer ((a) Reading information; (b) Marking of overhanging areas; (c) Axial containment box; (d) Layer by layer voxelization; (e) Obtaining surface voxels; (f) Surrogate model; (g) Surrogate model (self-supporting); (h) Attribute representation of voxels)

图5 体素代理模型空行程图示((a)模型间总空行程；(b)单层空行程)

Fig. 5 Empty travel distance of voxel-based surrogate models ((a) Total empty travel distance between models; (b) Single empty travel distance)

图6 基于贪心策略确定代理模型布局序列及空间位置

Fig. 6 The layout sequence and spatial position of the voxel-based surrogate model are determined based on greedy strategy

图7 基于改进的粒子群优化算法

Fig. 7 Improved Particle Swarm Optimization algorithm

图8 代理模型自由度

Fig. 8 The freedom of surrogate model

图9 全局最优值更新的约束条件

Fig. 9 Global optimal update constraints

图10 优化粒子查找方向

Fig. 10 Optimize the finding direction of particle

图11 优化α粒子速度方向

Fig. 11 Optimize the velocity direction of α

图12 代理模型空间位置优化过程示例((a) 20个粒子；(b)优化示例)

Fig. 12 Example of surrogate model spatial position optimization procedure ((a) 20 particles; (b) Optimization example)

图13 实验Ⅰ输入零件

Fig. 13 The input parts of Experiment Ⅰ

图14 实验Ⅰ布局效果

Fig. 14 Layout effect of experiment Ⅰ

图15 实验Ⅱ输入零件

Fig. 15 The input parts of experiment Ⅱ

图16 实验Ⅱ部分代理模型

Fig. 16 Some surrogate models of experiment Ⅱ

图17 实验Ⅱ布局效果

Fig. 17 Layout effect of experiment Ⅱ

表1 方法对比

Table 1 Method comparison with several research work

方法	布局优化过程中零件表示方法	优化过程中考虑打印方向	逐层分析布局时零件间空行程	自支撑区域下方空间利用	零件堆叠放置
文献[4]	零件本身	否	是	否	否
文献[12]	投影多边形	是	否	否	否
文献[15]	零件包围盒	是	DLP打印，不适用	否	是
本文	每层外轮廓体素	否	是	是	否

表2 不同布局序列下的空行程

Table 2 Empty travel distance under different layout sequences

实验模型	批量制造模型数量	平均零件空行程	布局序列	总空行程 (mm)
实验Ⅱ	15	111.5	体积	1 672
	15	104.2	高度	1 563
	15	113.7	随机	1 706
	15	103.4	投影面积	1 551
	15	73.1	贪心(本文)	1 096

图18 实验Ⅰ布局效果比较((a)本文；(b) Magics)

Fig. 18 Experiment Ⅰ layout effect comparison ((a) This paper; (b) Magics)

图19 实验Ⅱ布局效果比较((a)本文；(b) Magics)

Fig. 19 Experiment Ⅱ layout effect comparison ((a) This paper; (b) Magics)

表3 Magics布局对比实验

Table 3 Layout comparison experiments with Magics

实验模型	总空行程长度(mm)			预计批量制造时长(min)
实验模型	本文	Magics	减少比例(%)	本文	Magics	优化时长
实验Ⅰ	583	847	31.17	103	123	20
实验Ⅱ	1027	1483	30.75	263	286	23

参考文献 21

[1]	KARNAN B, BABU K, SHANMUGAM V, et al. Fused deposition modeling based polymeric materials and their performance: a review[J]. Polymer Composites, 2021, 42(11): 5656-5677. DOI URL
[2]	ARAÚJO L J, ÖZCAN E, ATKIN J A, et al. Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset[J]. International Journal of Production Research, 2019, 57(18): 5920-5934. DOI URL
[3]	OH Y, WITHERELL P, LU Y, et al. Nesting and scheduling problems for additive manufacturing: a taxonomy and review[J]. Additive Manufacturing, 2020, 36: 101492. DOI URL
[4]	JIANG J C, XU X, XIONG Y, et al. A novel strategy for multi-part production in additive manufacturing[J]. The International Journal of Advanced Manufacturing Technology, 2020, 109(5-6): 1237-1248. DOI
[5]	CALABRESE M, PRIMO T, PRETE A, et al. Nesting algorithm for optimization part placement in additive manufacturing[J]. The International Journal of Advanced Manufacturing Technology, 2022, 119(7-8): 4613-4634. DOI
[6]	CHE Y X, HU K X, ZHANG Z Z, et al. Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing[J]. Computers & Operations Research, 2021, 130: 105245. DOI URL
[7]	VOLPATO N, GALVAO L C, NUNES L, et al. Combining heuristics for tool-path optimisation in material extrusion additive manufacturing[J]. Journal of the Operational Research Society, 2020, 71: 867-877. DOI URL
[8]	ABILGAZIYEV A, KULZHAN T, RAISSOV N, et al. Design and development of multi-nozzle extrusion system for 3D printer[C]// 2015 International Conference on Informatics, Electronics & Vision. New York: IEEE Press, 2015: 1-5.
[9]	YOSEP O, CHI Z, SARA B. The impact of build orientation policies on the completion time in two-dimensional irregular packing for additive manufacturing[J]. International Journal of Production Research, 2020, 58(21): 6601-6615. DOI URL
[10]	ZHANG Y C, BERNARD A, HARIK R, et al. Build orientation optimization for multi-part production in additive manufacturing[J]. Journal of Intelligent Manufacturing, 2017, 28(6): 1393-1407. DOI URL
[11]	GRIFFITHS V, SCANLAN J P, ERES M H, et al. Cost-driven build orientation and Bin packing of parts in selective laser melting (SLM)[J]. European Journal of Operational Research, 2019, 273(1): 334-352. DOI URL
[12]	ZHANG Y C, BERNARD A, HARIK R, et al. A new method for single-layer-part nesting in additive manufacturing[J]. Rapid Prototyping Journal, 2018, 24(5): 840-854. DOI URL
[13]	BALDACCI R, BOSCHETTI M A, GANOVELLI M, et al. Algorithms for nesting with defects[J]. Discrete Applied Mathematics, 2014, 163: 17-33. DOI URL
[14]	YANG Y Z, LI H C, ZHANG K X, et al. A 3D nesting method based on the convex-concave coding similarity of the voxelized model for additive manufacturing[J]. Additive Manufacturing, 2023, 64: 103429. DOI URL
[15]	CAO L X, TIAN L H, PENG H, et al. Constrained stacking in DLP 3D printing[J]. Computers & Graphics, 2021, 95: 60-68. DOI URL
[16]	JIANG J C, XU X, STRINGER J. Optimisation of multi-part production in additive manufacturing for reducing support waste[J]. Virtual and Physical Prototyping, 2019, 14(3): 219-228. DOI URL
[17]	ROMANOVA T, BENNELL J, STOYAN Y, et al. Packing of concave polyhedra with continuous rotations using nonlinear optimisation[J]. European Journal of Operational Research, 2018, 268(1): 37-53. DOI URL
[18]	ZHANG H, LIU Q, WEI L J, et al. An iteratively doubling local search for the two-dimensional irregular Bin packing problem with limited rotations[J]. Computers & Operations Research, 2022, 137: 105550. DOI URL
[19]	PIOTROWSKI A P, NAPIORKOWSKI J J, PIOTROWSKA A E. Population size in particle swarm optimization[J]. Swarm and Evolutionary Computation, 2020, 58: 100718. DOI URL
[20]	SPACECLAIM. SpaceClaim web help[EB/OL]. [2023-03-25]. https://www.ansys.com/products/3d-design/ansys-spaceclaim?spaceclaimredirect.
[21]	CORPORATION M N. Materialise magics[EB/OL]. [2023-03-20]. https://www.materialise.com/en/software/magics.

面向喷头空行程长度最小化的多零件优化布局方法

Optimizing the multi-part layout to minimize the empty travel distance of nozzle

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 22

参考文献 21

相关文章 2

编辑推荐

Metrics

本文评价

[1]	白宇, 王坤. 基于参数化的3D打印个性化外固定支具设计研究[J]. 图学学报, 2023, 44(5): 1050-1056.
[2]	潘丽娟，商正，贾桂红，储开宇，王进峰. 熔融沉积制造表面粗糙度参数显著性及预测模型研究[J]. 图学学报, 2020, 41(4): 593-598.