The computing time of the program.
Commercial 3D printers have been increasingly implemented in a variety of fields due to their quick production, simplicity of use, and cheap manufacturing. Software installed in these machines allows automatic production of components from computer-aided design (CAD) models with minimal human intervention. However, there are fewer options provided, with a limited range of materials, limited path patterns, and layer thicknesses. For fabricating metal functional parts, such as laser-based, electron beam-based, and arc-welding-based additive manufacturing (AM) machines, usually more careful process design requires in order to obtain components with the desired mechanical and material properties. Therefore, advanced design for additive manufacturing, particularly slicing and path planning, is necessary for AM experts. This chapter introduces recent achievements in slicing and path planning for AM process.
- Additive Manufacturing
- Path Planning
- 3D Slicing
- Medial Axis Transform
1. 3D CAD slicing
AM requires an input computer-aided design (CAD) model of the part which may be designed in a CAD system, or obtained from reverse engineering such as 3D scanners. Once the CAD model is completed, it is converted to the standard STL format, which is most commonly used to represent 3D CAD models in additive manufacturing. A section of an STL file and its 3D model are shown in Figure 1. In an ASCII STL file, the CAD model is represented using triangular facets, which is described by the x-, y-, and z-coordinates of the three vertices and a unit vector to indicate the normal direction that point outside of the facet . Redundant information for indicating model name, facet normal, and vertex is also included. In the following sections, unidirection slicing and multidirection slicing of STL models are described.
2. Unidirection slicing
Unidirection slicing algorithm slices the STL model into a variety of 2.5D layers parallel to the build direction. Figure 2a shows an STL model and various cutting planes for unidirection slicing; and Figure 2b shows the resulting slicing layers which are polygons.
Uniform slicing method slices CAD model with a constant thickness. The accuracy of the additively manufactured parts could be controlled by altering the layer thickness. The smaller the layer thickness, the higher the accuracy will be obtained. Also, the deposition rate or productivity is highly relevant to the sliced layer thickness. Adaptive slicing approach slices a model with a variable thickness. Based on the surface geometry of the model, this approach adjusts automatically the layer thickness to improve the accuracy or to improve the build time.
With the increasing size of the STL file, a major challenge of slicing algorithms is the computing efficiency. An efficient and fault-tolerant slicing algorithm was proposed by Choi et al. . The detailed slicing algorithm is presented as follows.
Figure 3 shows the flowchart of the tolerant slicing algorithm . Two stages are included, namely, preprocessing stage regarding the optimum orientation of the part, and slicing stage generating slices from STL model. The orientation of the STL model is usually user defined or obtained with respect to the optimal build time, the surface quality, support structures required, or other criteria. Algorithms regarding the orientation of CAD models are beyond the scope of this chapter.
For each layer construction in slicing, the method scans the STL file to extract one facet at a time sequentially and compares the z-coordinates of its three vertices to the z-height of the slicing (cutting) plane. Through setting a small value bound tolerance, the possibilities of intersection of a facet with a cutting plane can be divided into the following four classes, as shown in Figure 4 . Four classes could be found as following.
Class 1 is shown in case 1 in Figure 4, where a facet intersects with the cutting plane without one vertex lies on the plane. Two intersecting points are calculated by the intersection of the plane and the triangular facet in this case. A line segment is generated by connecting the intersection points and stored for constructing the slice layer contour .
Class 2 is shown in case 2 in Figure 4, where one vertex lies in the cutting plane while the two remaining vertices lie in different sides of the cutting plane. Case 3 and case 4 also show that one vertex lies in the cutting plane while other vertices lie in the same side of the cutting plane. In this case, there will be no intersection line segments calculated .
Class 3 is shown in case 5 and case 6 in Figure 4, where two vertices of the facet lie in the cutting plane. The remaining vertex can be either above or below the cutting plane. This is a concurrent case in a valid STL model that results in one duplicated line segment and either one should be ignored .
Class 4 is shown in case 7 in Figure 4, where all three vertices lie in the cutting plane. In this case, the whole triangular facet lies in the cutting plane and will not contribute any line segments to the contour of the slice layer. Therefore, this case can be directly ignored without any ambiguity .
After all the possible intersection line segments have been calculated and stored, the contour of the slice layer is constructed through head-to-tail connecting of the line segments.
The algorithm has been implemented in MATLAB program. The slicing algorithm was able to slice complex STL models with good performance. Three case studies are provided as shown in Figure 5–7. The number of facets of three models is provided in Table 1. The algorithm is verified to be efficient with the computing time less than half second for all cases.
|Case I||1076||12 ms|
|Case II||1584||34 ms|
|Case III||172,122||352 ms|
3. Multidirection slicing
Most of the current AM processes involve slicing a 3D CAD model into a set of 2.5D layers with a constant or adaptive thickness along the build-up direction as mentioned in unidirection slicing. However, to fabricate parts with complex shapes the unidirectional slicing strategies are generally limited by the need for support structures to deposit overhangs. Figure 8a shows a component and its usual build direction
Some of the additive manufacturing techniques are able to deposit materials along multiple directions. The application of multidirection deposition could eliminate or significantly decrease the usage of supports for complex components. As shown in Figure 8c, the component can be fabricated in multiple directions, for example,
A key challenge in multidirection AM is to develop robust algorithms capable of automatically slicing any 3D model into a set of layers which satisfy support-less and collision-free layered deposition. The following sections review some existing multidirection slicing strategies.
Silhouette edges projection : This strategy firstly identifies the unbuildable surface features of a model by projecting silhouette edges along the user defined original build direction. Then the part is decomposed into buildable and unbuildable sub-volumes using the silhouette-edge-based method. For the unbuildable sub-volume, a new suitable build direction is determined using the Gauss and Visibility maps. With the new build direction, the unbuildable sub-volume is further decomposed through repeating the same projection procedures. This projection method is recursively used to decompose the sub-volume as shown in Figure 9. The framework for the multidirection slicing and some essential problems have been addressed and discussed by the authors. However, the implementation of the strategy could be complicated and computationally expensive for complex components with inner cavities.
Transition wall : The key idea of this strategy is to identify the overhang layers by computing the difference between the current layer and the previous layer. Then, as shown in Figure 10, to build an overhang structure, the machine is turned 90° to start depositing a transition, namely thin wall. After the deposition of the first few layers, the wall is finished and the subsequent overhang structures can be deposited in the vertical direction again. Although this strategy is simple, it is only suitable for a subset of part geometries. In some cases, the deposition of the transition wall is difficult or impossible to implement due to deposition nozzle collision, such as the part shown in Figure 8a.
Centroid axis extraction : The first step in this strategy is to extract the centroid axis of the model as shown in Figure 11, which provides a global perspective on the geometry, allowing the slicing procedure to be conducted on an optimal sequence. Through analyzing the topological information from the centroid axis, the splitting surface is identified and the subsequent decomposition operation is conducted. For each subcomponent obtained from decomposition, multiaxis slicing is performed and the collision-free slicing sequence is finally generated. The centroid axis extraction method decomposes the component by detecting the change of centroid of presliced layers, making the geometry analysis process easier. However, in some cases it will be difficult to decompose components efficiently as required since the centroid axis does not always indicate the change of the geometry.
Other multidirection slicing methods have been proposed that are either adaptations or combinations of a few techniques from the above strategies, such as adaptive slicing algorithm , offset slicing , skeleton method , and modular boundary decomposition . However, each method is only suitable for a subset of part geometries. In addition, these methods are not efficient for processing parts with holes and depression features. As shown in Figure 12, the part is decomposed into buildable volume and unbuildable volume due to the direction of hole, H, is vertical to the build direction, B, of its associated volume. The part is firstly decomposed into buildable and unbuildable sub-volume . The unbuildable sub-volume could be further built by offset slicing strategy  with the direction as shown in Figure 12b. However, unbuildable volume also exists due to the holes. It is clear that holes would hamper implementing multidirection slicing algorithm.
Decomposition–regrouping method : Differing from these existing slicing approaches, which are mainly focused on finding an optimal volume decomposition strategy, a recent study proposed simplification of holes and a decomposition–regrouping method. A model simplification step is introduced before CAD decomposition to significantly enhance the capability of the proposed multidirection strategy. The CAD model is then decomposed into sub-volumes using a simple curvature-based volume decomposition method and consequently a depth tree structure based on topology information is introduced to merge them into ordered groups for slicing. The proposed strategy is proven to be simple and efficient on various tests parts. As an example shown in Figure 13, the part is decomposed and regrouped, then sliced in multiple directions with holes been filled. Since there is no robust multidirection slicing algorithm validated for any complex geometry, the proposed multidirection slicing algorithm is not versatile also, while it is particularly useful for components with large number of holes.
4. 2D path planning
Another important step in AM is the development of an elaborate path planning strategy. Path planning for powder-based AM processes that have fine, statistically distributed particles is somewhat independent of geometric complexity. However, path planning for AM processes that have coarse and large-sized deposits is influenced by geometric complexity. Also, the property of the deposited shape will be influenced by the deposition path trajectory. In the following sections, methods are described to generate different types of deposition paths.
5. Raster path
The raster scanning path technique, as shown in Figure 14a, is based on planar ray casting along one direction. In this strategy, 2D regions are filled by a set of scan lines with finite width . It is commonly employed in commercial AM systems due to its simple implementation and suitability for almost any arbitrary boundary.
6. Zigzag path
Derived from the raster strategy, zigzag tool-path generation is the most popular method used in commercial AM systems. While it fills geometries line by line along one direction like the raster approach, the zigzag approach combines the separate parallel lines into a single continuous pass (see Figure 14b) which significantly reduces the number of tool-path passes [12, 13]. This method significantly improves the productivity of the AM process by reducing the required transition motions of the machine. However, the outline accuracy of the part for both raster and zigzag approaches is poor due to the discretization errors on any edge that is not parallel to the tool motion direction.
7. Contour path
Contour path generation as shown in Figure 14c, which is another typical method, can address the above geometrical quality issue effectively by following the geometrical trend of the boundary contours [14, 15]. Various contour map patterns were investigated by Li et al.  to develop optimal tool-path patterns for sculptured parts with a single island and no seriously non-convex shape.
8. Spiral path
The spiral tool-path generation, as shown in Figure 14d, has been widely applied in numerically controlled (NC) machining, especially for 2D pocket milling and uniform pocket cutting [17, 19]. This method can also be used to solve the problems of zigzag tool paths in AM process, but is only suitable for certain special geometrical models.
9. Hybrid path
The hybrid path planning strategy is promising as it shares some merits of various approaches. A combination of contour and zigzag pattern is commonly developed to meet both the geometrical accuracy and build efficiency requirements. Zhang et al.  applied a new image algorithm for welding-based AM. The planned approach includes one inner zigzag path which is faster and more universal, and one outline vector path which is very helpful for maintaining the surface accuracy and quality. Jin et al.  proposed a mixed tool-path algorithm to generate contour and zigzag tool path for AM of biomedical models, as shown in Figure 14e. The zigzag tool path is employed to fill the interior area of the part to improve the efficiency, while the contour tool path is used to fabricate the area along the boundary of the contours to improve the geometrical quality of the model.
10. Continuous path
Continuous path planning can be considered as another tool-path generation method. Hilbert filling curve applied by Bertoldi et al.  is a continuous path, which can cover a region of space without intersecting itself as shown in Figure 15a. It has been found to be particularly useful in reducing shrinkage during AM fabrication processes. However, the large number of path direction turning motions that are produced by using this strategy are not suitable for AM. Wasser et al.  introduced a fractal-like build style using a simulated annealing algorithm. This method is able to generate filling patterns that allow the continuous deposition of a single path to fill arbitrarily shaped areas, as shown in Figure 15b. In this method, the area to be deposited is firstly decomposed into nodes, with the number of the nodes determined by the accuracy requirement of the AM process. However, when the area to be filled is large and the accuracy requirement is high, the processing time required would be unacceptably long. Moreover, highly convoluted paths may result in accumulation of heat in certain regions, therefore inducing excessive distortion of the part. Frequent alternations of tool-path travel directions are also not preferred in AM.
11. Hybrid and continuous path
Dwivedi et al.  developed a continuous path planning approach which combines the merits of zigzag and continuous path patterns, as shown in Figure 15c. In this method, the 2D geometry is firstly decomposed into a set of monotone polygons. For each monotone polygon, a closed zigzag curve is then generated. Finally, a set of closed zigzag curves are combined together into an integrated continuous torch path.
The continuous path planning approach significantly reduces the number of welding passes. However, purely employing zigzag-based curves would have a surface accuracy issue, as Zhang et al.  point out the importance of filling the outline of the image with vector motions in wire and arc additive manufacturing (WAAM). Recently, we proposed another continuous path pattern which leverages the advantages of zigzag, contour, and continuous path patterns, as shown in Figure 15d . It is indicated that this continuous path pattern is suitable for WAAM of solid structures.
12. Medial axis transformation (MAT) path
Kao  has proposed an alternative methodology of using the medial axis transformation (MAT) of the geometry to generate the offset curves by starting at the inside and working toward the outside, instead of starting from the boundary and filling toward the inside. This approach is able to compute paths which can entirely fill the interior region of geometry as the paths are generated from interior to the boundary. This strategy avoids producing gaps by depositing excess material outside the boundary, as illustrated in Figure 16. The extra material can subsequently be removed by post-processing. Therefore, the traditional contour path patterns from outside to inside is natural for machining whereas MAT path starting from inside and working toward the outside is suitable for AM of void-free components.
However, the previous authors limit their discussion to geometries with simple MAT paths. Recently, Ding et al. [26, 27] developed a methodology of generating MAT-based paths for an arbitrary geometry, either thin-walled or solid structures.
The following are the main steps for generating MAT-based paths:
Compute the medial axis: The cross section of a sliced layer with a thin-walled structure is shown in Figure 17a. The medial axis or skeleton of the geometry is computed and represented using red lines. The computed skeleton is the crucial information, which describes the shape of the geometry.
Decompose the geometry: Using the computed medial axis, the geometry is decomposed into several domains. As the geometry with N holes will be decomposed into N+1 domains, this geometry is decomposed into 10 domains as shown in Figure 17b. As displayed in different colors, each domain is bounded by a portion of medial axis (red lines in Figure 17a) and a boundary loop (black line loop in Figure 17a).
Generate path for the domain: Deposition paths for each domain are generated by offsetting the medial axis loop (red line loop in Figure 17c for domain 3) toward the corresponding boundary loop (black line loop in Figure 17c) with an appropriate step-over distance. The offsetting is repeated and terminates when the domain is fully covered. Green line loops in Figure 17c, represent the generated deposition paths.
Complete the deposition paths: A complete set of MAT-based deposition paths is obtained by repeating step 3) for all the decomposed domains. The generated paths are a set of closed-loop lines without start/stop sequences, which is preferred for the arc welding system.
From the above description, the MAT path planning algorithm for an arc welding process is able to be automated for any complex geometry; just as the existing commercially available raster and contour path planning strategies have been automatically applied to powder-based AM. MAT path is particularly preferred for void-free AM. Example of MAT path generation for a solid structure with holes is shown in Figure 18.
13. Adaptive MAT path
Traditional contour path always generates gaps or voids as shown in Figure 19a and b. To avoid internal voids, the MAT path was introduced and its extension for complex geometries was developed. MAT paths are generated by offsetting the medial axis of the geometry from the center toward the boundary. Figure 19c shows an example of MAT path with the deposition sequence indicated by numbers. Although void-free deposition is obtained using MAT paths, this is achieved at the cost of creating discontinuity of the path (such as path 3, 4, and 5 in Figure 19c) and extra deposition at the boundary as described in Figure 19d. Post-process machining must be used to remove the extra materials and improve the accuracy at the cost of material and energy wastage.
Step-over distance, which is defined as the distance between the next deposition path and the previous one, is always constant for both contour path patterns (refer to Figure 19a) and MAT path patterns (refer to Figure 19c). For certain geometries, it is not possible to achieve both high accuracy (refer to Figure 19b) and void-free (refer to Figure 19d) components using paths with constant step-over distance. However, some AM processes, such as wire feed AM process, are capable of producing different widths of deposits within a layer through varying travel speed and wire feed rate, while maintaining a constant deposit height. Therefore, we propose an adaptive path planning strategy that uses continuously varying step-over distances by adjusting the process parameters to deposit beads with variable width within any given path . The developed adaptive MAT path planning algorithm is able to automatically generate path patterns with varying step-over distances (refer to Figure 19e) by analyzing geometry information to achieve better part quality (void-free deposition), accuracy at the boundary, and material efficiency, as shown in Figure 19f. Example of adaptive MAT path generation for a geometry with multiple holes is shown in Figure 20. Examples of void-free additive manufacturing using adaptive MAT paths could be found in .
This chapter presented slicing strategy for AM, namely unidirection slicing and multidirection slicing. Apart from the slicing, methods of existing path planning, including the newly published MAT-based non-adaptive and adaptive paths, were reviewed for advanced design in AM.
The main conclusions are listed as following:
Unidirection slicing method is normally used for current commercial AM machines due to its robustness and simplicity. However, supports are required for some complex geometries with overhangs which reduce the accuracy and the building speed of products.
Multidirection slicing strategy enhances the ability of AM and reduces the usage of supports. Nevertheless, its application is still limited since it requires the AM machine to be able to deposit along multiple directions, and more importantly, algorithms for multidirection slicing are complex and not versatile.
Ample software are available to generate zigzag, or contour paths for AM process, but the geometries are usually not fully covered by these paths, therefore left the built geometry with voids or gaps. For fabricating the functional products, gap-free paths are beneficial. Therefore, advanced design on path planning is essential as the example of MAT path generation introduced in this chapter.
D.-H. Ding, Z.-X. Pan, C. Dominic, and H.-J. Li, "Process planning strategy for wire and arc additive manufacturing," in Robotic Welding, Intelligence and Automation: RWIA’2014, T.-J. Tarn, S.-B. Chen, and X.-Q. Chen, Eds., Cham: Springer International Publishing, 2015, pp. 437–450.
S. Choi and K. Kwok, "A tolerant slicing algorithm for layered manufacturing," Rapid Prototyping Journal, vol. 8, pp. 161–179, 2002.
D. Ding, Z. Pan, D. Cuiuri, H. Li, N. Larkin, and S. van Duin, "Automatic multi-direction slicing algorithms for wire based additive manufacturing," Robotics and Computer-Integrated Manufacturing, vol. 37, pp. 139–150, 2016.
P. Singh and D. Dutta, "Multi-direction slicing for layered manufacturing," Journal of Computing and Information Science in Engineering, vol. 1, pp. 129–142, 2001.
Y. Yang, J. Fuh, H. Loh, and Y. Wong, "Multi-orientational deposition to minimize support in the layered manufacturing process," Journal of Manufacturing Systems, vol. 22, pp. 116–129, 2003.
J. Ruan, T. E. Sparks, A. Panackal, F. W. Liou, K. Eiamsa-ard, K. Slattery, et al., "Automated slicing for a multiaxis metal deposition system," Journal of Manufacturing Science and Engineering, vol. 129, pp. 303–310, 2007.
J. Zhang and F. Liou, "Adaptive slicing for a multi-axis laser aided manufacturing process," Journal of Mechanical Design, vol. 126, pp. 254–261, 2004.
P. Singh and D. Dutta, "Offset slices for multidirection layered deposition," Journal of Manufacturing Science and Engineering, vol. 130, p. 011011, 2008.
R. Dwivedi and R. Kovacevic, "Process planning for multi-directional laser-based direct metal deposition," Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, vol. 219, pp. 695–707, 2005.
L. Ren, T. Sparks, J. Ruan, and F. Liou, "Process planning strategies for solid freeform fabrication of metal parts," Journal of Manufacturing Systems, vol. 27, pp. 158–165, 2008.
M. R. Dunlavey, "Efficient polygon-filling algorithms for raster displays," ACM Transactions on Graphics (TOG), vol. 2, pp. 264–273, 1983.
S. C. Park and B. K. Choi, "Tool-path planning for direction-parallel area milling," Computer-Aided Design, vol. 32, pp. 17–25, 2000.
V. Rajan, V. Srinivasan, and K. A. Tarabanis, "The optimal zigzag direction for filling a two-dimensional region," Rapid Prototyping Journal, vol. 7, pp. 231–241, 2001.
R. Farouki, T. Koenig, K. Tarabanis, J. Korein, and J. Batchelder, "Path planning with offset curves for layered fabrication processes," Journal of Manufacturing Systems, vol. 14, pp. 355–368, 1995.
Y. Yang, H. Loh, J. Fuh, and Y. Wang, "Equidistant path generation for improving scanning efficiency in layered manufacturing," Rapid Prototyping Journal, vol. 8, pp. 30–37, 2002.
H. Li, Z. Dong, and G. W. Vickers, "Optimal toolpath pattern identification for single island, sculptured part rough machining using fuzzy pattern analysis," Computer-Aided Design, vol. 26, pp. 787–795, 1994.
F. Ren, Y. Sun, and D. Guo, "Combined reparameterization-based spiral toolpath generation for five-axis sculptured surface machining," The International Journal of Advanced Manufacturing Technology, vol. 40, pp. 760–768, 2009.
G. Jin, W. Li, and L. Gao, "An adaptive process planning approach of rapid prototyping and manufacturing," Robotics and Computer-Integrated Manufacturing, vol. 29, pp. 23–38, 2013.
H. Wang, P. Jang, and J. A. Stori, "A metric-based approach to two-dimensional (2D) tool-path optimization for high-speed machining," Transactions-American Society of Mechanical Engineers Journal of Manufacturing Science and Engineering, vol. 127, p. 33, 2005.
Y. Zhang, Y. Chen, P. Li, and A. T. Male, "Weld deposition-based rapid prototyping: a preliminary study," Journal of Materials Processing Technology, vol. 135, pp. 347–357, 2003.
M. Bertoldi, M. Yardimci, C. Pistor, and S. Guceri, "Domain decomposition and space filling curves in toolpath planning and generation," Proceedings of the 1998 Solid Freeform Fabrication Symposium, The University of Texas at Austin, Austin, Texas, 1998, pp. 267–74.
T. Wasser, A. D. Jayal, and C. Pistor, "Implementation and evaluation of novel buildstyles in fused deposition modeling (FDM)," Strain, vol. 5, p. 6, 1999.
R. Dwivedi and R. Kovacevic, "Automated torch path planning using polygon subdivision for solid freeform fabrication based on welding," Journal of Manufacturing Systems, vol. 23, pp. 278–291, 2004.
D. Ding, Z. S. Pan, D. Cuiuri, and H. Li, "A tool-path generation strategy for wire and arc additive manufacturing," The International Journal of Advanced Manufacturing Technology, vol. 73, pp. 173–183, 2014.
J.-H. Kao and F. B. Prinz, "Optimal motion planning for deposition in layered manufacturing," Proceedings of DETC, 1998, pp. 13–16.
D. Ding, Z. Pan, D. Cuiuri, and H. Li, "A practical path planning methodology for wire and arc additive manufacturing of thin-walled structures," Robotics and Computer-Integrated Manufacturing, vol. 34, pp. 8–19, 2015.
D. Ding, C. Shen, Z. Pan, D. Cuiuri, H. Li, N. Larkin, et al., "Towards an automated robotic arc-welding-based additive manufacturing system from CAD to finished part," Computer-Aided Design, 2016 vol. 73, pp. 66–75.
D. Ding, Z. Pan, D. Cuiuri, H. Li, S. van Duin, and N. Larkin, "Bead modelling and implementation of adaptive MAT path in wire and arc additive manufacturing," Robotics and Computer-Integrated Manufacturing, vol. 39, pp. 32–42, 2016.