Computer Science ›› 2020, Vol. 47 ›› Issue (8): 267-271.doi: 10.11896/jsjkx.190700184

Previous Articles     Next Articles

Intelligent 3D Printing Path Planning Algorithm

YANG De-cheng1, LI Feng-qi1, WANG Yi2, WANG Sheng-fa2, YIN Hui-shu1   

  1. 1 School of Software Technology, Dalian University of Technology, Dalian 116600, China
    2 International School of Information Science &Engineering, Dalian University of Technology, Dalian 116600, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:YANG De-cheng, born in 1995, M.D.His main research interests include virtual simulation manufacturing and so on.
    WANG Yi, born in 1980, Ph.D, associate professor, is a member of China Computer Federation.Her main research interests include machine learning and virtual reality.
  • Supported by:
    This work was supported by the National Key Research and Development Program of China (2017YFB1107704) and Fundamental Research Funds for the Central Universities (DUT19ZD209).

Abstract: The path planning of large industrial parts in additive manufacturing directly affects manufacturing quality and efficiency.At present, the commonly used traditional path planning methods have many problems, such as turning and stacking of print head and the number of rise and fall of print head, so they are not suitable for large industrial parts.Therefore, an intelligent path planning algorithm is proposed.Firstly, the two-dimensional plane obtained after slicing is concavely convexly decomposed into printing sub-areas, and then the internal long-axis scanning along the partition is performed on each sub-area to reduce the number and length of printing paths.Then, the sub-partition connection is treated as a traveling salesman problem (TSP) using gene-tic algorithms to complete the path planning between the sub-areas.Meanwhile, an intelligent 3D printing path planning system is designed and developed with C# language, which has the functions of slice input and display, print width setting, intelligent path planning and G-code code output.By comparing with the two traditional path planning algorithms, the proposed method significantly reduces the number of paths, the idle travel distance, and the number of print head lifts.The sub-partition-based intelligent path planning method provides a new idea for the additive manufacturing process of large industrial parts.

Key words: 3D Printing, Path planning, Genetic algorithm, Concave polygonal convex decomposition, Traveling Salesman Problem

CLC Number: 

  • TP391
[1] WONG K V, HERNANDEZ A.A Review of Additive Manufacturing[J].ISRN Mechanical Engineering, 2012, 2012:1-10.
[2] ASIABANPOUR B, KHOSHNVIS B.Machine path generation for the SIS process [J].Robotics and Computer-Integrated Ma-nufacturing, 2004, 20(3):167-175.
[3] LANARO M, FORRESTAL D P, SCHEURER S, et al.3Dprinting complex chocolate objects:Platform design, optimization and evaluation[J].Journal of Food Engineering, 2017, 215:13-22.
[4] TARABANIS K A.Path planning in the proteus rapid prototyping system[J].Rapid Prototyping Journal, 2001, 7(5):241-252.
[5] YANG Y, LOH H T, FUH J Y H, et al.Equidistant path gene-ration for improving scanning efficiency in layered manufactur-ing[J].Rapid Prototyping Journal, 2002, 8(1):30-37.
[6] ZHAO H S, GU F L, JORGE G, et al.Connected fermat spirals for layered fabrication[J].ACM Transactions on Graphics, 2016, 35(4):1-10.
[7] JIN Y, HE Y, FU G, et al.A non-retraction path planning approach for extrusion-based additive manufacturing[J].Robotics and Computer Integrated Manufacturing, 2017, 48(1):132-144.
[8] HAN G X, SONG X H, YIN M, et al.Path Optimization Algo-rithm of 3D Printing Based on Fused Deposition Modeling[J].Transactions of The Chinese Society of Agricultural Machinery, 2018, 49(3):393-401.
[9] GREGORY G.Traveling Salesman Problem[J].Encyclopedia of Operations Research & Management Science, 2008, 60(4):1-12.
[10] CHEN T.An Improved Algorithm of Cyrus-Beck Segment Clipping to Process Concave Polygon [J].Computer Science, 2006, 33(12):217-220.
[11] XIONG W J.A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree for the Master of Engineering [D].Hangzhou:Huazhong University of Science and Technology, 2007.
[12] ZHANG Y L.Software design and algorithm optimization ofmulti-axis Laser Direct Metal Deposition system [D].Changsha:Hunan University, 2018.
[13] KOK-WHY N, WONG Y P, HO S N.Improvement in Decimation of Triangle Meshes for Level of Detail[C]∥International Conference on Geometric Modeling & Graphics.IEEE, 2003.
[14] BAI R B.Research and Implementation of Critical PolygonMethod in Two-Dimensional Irregular Parts Layout[D].Xi’an:Northwestern Polytechnical University, 2002.
[15] KEIL M, SNOEYINK J.On The Time Bound for Convex Decomposition of Simple Polygons[J].International Journal of Computational Geometry & Applications, 2002, 12(3):181-192.
[16] MARK BAYAZIT.Mark Bayazit's Algorithm [EB/OL].[2019-03-25].
[17] LIN Z, FU J, HE Y, et al.A robust 2D point-sequence curve offset algorithm with multiple islands for contour-parallel tool path[J].Computer-Aided Design, 2013, 45(3):657-670.
[1] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[2] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[3] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[4] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[5] JIANG Chen-kai, LI Zhi, PAN Shu-bao, WANG Yong-jun. Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm [J]. Computer Science, 2020, 47(8): 272-277.
[6] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[7] YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem [J]. Computer Science, 2020, 47(6A): 124-129.
[8] BAO Zhen-shan, GUO Jun-nan, XIE Yuan and ZHANG Wen-bo. Model for Stock Price Trend Prediction Based on LSTM and GA [J]. Computer Science, 2020, 47(6A): 467-473.
[9] MA Chuang, LV Xiao-fei and LIANG yan-ming. Agricultural Product Quality Classification Based on GA-SVM [J]. Computer Science, 2020, 47(6A): 517-520.
[10] ZHOU Jun and WANG Tian-qi. Single Departure and Arrival Procedure Optimization in Airport Terminal Area Based on Branch and Bound Method [J]. Computer Science, 2020, 47(6A): 552-555.
[11] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[12] HU Shi-juan, LU Hai-yan, XIANG Lei, SHEN Wan-qiang. Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP [J]. Computer Science, 2020, 47(6): 219-224.
[13] ZHANG Ju, WANG Hao, LUO Shu-ting, GENG Hai-jun, YIN Xia. Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm [J]. Computer Science, 2020, 47(6): 236-241.
[14] JIN Xiao-min, HUA Wen-qiang. Energy Optimization Oriented Resource Management in Mobile Cloud Computing [J]. Computer Science, 2020, 47(6): 247-251.
[15] ZENG Wei-liang, WU Miao-sen, SUN Wei-jun, XIE Sheng-li. Comprehensive Review of Autonomous Taxi Dispatching Systems [J]. Computer Science, 2020, 47(5): 181-189.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .