{'fraction_non_alphanumeric': 0.0348144973091394, 'fraction_numerical': 0.01190646282802305, 'mean_word_length': 4.541831617841119, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Toolpath Planning for Voxel-Based CNC Rough Machining

Multi-axis CNC machines are widely used to manufacture complex industrial parts such as dies and molds. The current CNC toolpath planning strategies are complex and often lead to inefficient part programs. This paper presents an approach to use voxel-based CAD models for efficient zig-zag toolpath planning. The developed system focusses on the rough milling of complex parts having multiple machining features. The system takes the CAD (STL) part model and identifies the machinable and non-machinable areas by analyzing the voxelized part model. This follows the segmentation of machinable area into smaller machining regions. Genetic Algorithm is then used to generate an optimum sequence of machining these regions to reduce air cutting path. The developed system was extensively tested using parts with varying machining feature complexities. The system was found to be better than the traditional zigzag roughing toolpath generation methods in terms of the reduction of the number of tool liftoffs and air cutting path length.


INTRODUCTION
Today, multi-axis Computer Numerical Control (CNC) machines are widely used to manufacture complex industrial products in automobile, aerospace, and die molds industries. The availability of efficient part programs directly governs the productivity and part quality during CNC machining. The process planners use the Computer-Aided Manufacturing (CAM) systems, which often provide inefficient toolpath. In addition, they need several user inputs and iterations, which are cumbersome and time-consuming. A need thus exists to develop toolpath planning algorithms to generate efficient CNC part programs.
The roughing stage of CNC machining takes a significant portion of the total machining cycle time during the manufacture of a part. Roughing strategy aims to achieve near net shape and minimize the total cycle time. Literature documents the development of several toolpath planning strategies for multi-axis (3-5 axis) CNC machining. Various studies on 2.5 D rough milling using toolpath patterns such as zig-zag, spiral, and contour-based have been reported [29]. Kim and Choi [13] observed that smooth zig-zag toolpath gives less machining time than the contour parallel. Generally, in practice, the zig-zag toolpath pattern is most widely used for die and mold machining because of the enhanced constant cutting loads [17].
To improve productivity (minimize cycle time) for large parts with several machining features, there are two main requirements viz. a smaller number of tool lift offs and the optimized sequence of operations. Several studies report work in this direction for applications such as drilling [1] [26], laser cutting [10], yarn cutting [16], and milling segment [12]. Evolutionary optimization techniques have been reported to reduce air cutting time by considering path planning as a traveling salesman problem (TSP). Castelino et al. [6] used the LK heuristic method while Oysu and Bingul [23] used Simulated Annealing (SA) and Genetic Algorithm (GA) methods to find an optimal way of connecting (stitching) milling sub-regions. They fixed the start and end of the subregions apriori, which made the solution sub-optimal. Pavanaskar et al. [24] used a greedy approach for joining geometry streamlines to generate an energy-efficient toolpath for pocket milling. Barclay et al. [5] used a grid-based strategy for simple prismatic parts to find an optimal toolpath using genetic programming. Nassehi et al. [21] reported the use of the STEP-NC model with GA to generate an optimized toolpath. The approach was, however, unable to give better performance than the commercially available software.
All the above strategies work on CAD models in the B-Rep, STL, or parametric equation form to generate toolpath and often need feature recognition which require complex geometric computations. Researchers are thus, exploring the use of voxel-based CAD models for toolpath planning. The voxel representation shifts the computation from real variables to the integer and Boolean space. It specifies the cutter locations by integer indexes that are generated by checking whether the traversing voxel is filled or empty.
Literature reports scant research work on the use of voxel-based CAD models for CNC rough toolpath planning. Jang et al. [11] used the voxel-based model to simplify the computation of regularized Boolean set operations for showing the in-process state of the workpiece. Tarbutton et al. [27] used a ray casting approach to calculate cutter contact (CC) points through GPU (Graphics processing unit) based parallel processing for the generation of roughing toolpath. Tarbutton et al. [28] further extended their work to generate a gouge free roughing and finishing toolpath. Konobrytskyi et al. [15] described a way to determine the cutter contact point for 5-axis machining using GPGPU. However, their algorithm required complex computational tasks such as offset surface calculations. The Iso-scallop toolpath generation using voxel model was reported by Balabokhin and Tarbutton [3] [4]. A voxel-based surface offsetting method was proposed by Lynn et al. [19] for a virtualized voxel-based CAM package. Lynn et al. [20] proposed an alternative to additive manufacturing using voxel-based CNC machining for non-assembly mechanisms. The work was, however, part specific. Shen and Tarbutton [25] introduced a voxel-based toolpath planning approach for welded and cast near net shape parts using the scanned data as the stock material.
Literature shows that there is a need for the development of a comprehensive methodology using the voxel-based CAD models for efficient CNC roughing toolpath planning. The present work is an attempt in this direction. Figure 1 shows the functional modules of the developed system for the rough machining operation on 3-axis CNC milling machine. The system takes the STL CAD part model as input and converts it into the voxel part model. The voxel data, thus generated, is preprocessed to provide stock allowance (for finishing) and fill in the inaccessible (blind) feature for 3-axis CNC machining. The modified voxel model data is then parsed to generate toolpath. Post-processing of the tool path data is carried out to add the controller-specific instruction to carry out real machining. Various functional modules of the developed system are explained one by one. Figure 1: Modular diagram.

Voxelization
Voxelization is a method to convert an object model into a stack of cuboidal blocks (voxels) that best approximate the shape. The process of voxelization takes the STL CAD part model as an input and compute the extents of the cuboidal raw stock. The part model is then voxelized to form machinable ('0'), and non-machinable voxels ('1') using the ray-tracing algorithm [13]. The voxel size is limited by the tool diameter to prevent undercuts. The size of the voxel (∆x, ∆y, ∆z) is taken equal to the user-defined values of the step over (∆x, ∆y) and the depth of cut (∆z), respectively.
In the present work, the voxel-based part model is represented as a 3D array. The index (i, j, k) of each element in the array corresponds to the position of the voxel. When multiplied by the size of the voxel ( =i×∆ ; y=j×∆y; z=k×∆z), it gives the position of the voxel in the Cartesian space. The value stored in the data structure array is in the binary form, i.e., either '1' (material is present) or '0' (material is absent) ( Figure 2).

Pre-Processing
Pre-processing of the voxel part model is done to preclude the generation of fallacious toolpath. The process is explained below.

Generation of offset region
The offset region is generated on the voxel part model to append the finishing stock allowance and the tool radius compensation. The proposed system does this task by expanding the nonmachinable region (X+/-, Y+/-) in each layer. For instance, Figure 3 (a) shows the initial voxels in the cross-section layer X-Y, every voxel is surrounded by eight neighboring voxels in each layer. To perform the offset by one voxel, all the neighboring machinable voxels '0' of non-machinable voxel '1' are converted to '1' (Figure 3   Geometric construction was used to derive the number of voxels to offset, as shown in Figure 4. The cutting tool is placed at the center of the machinable voxel that overcuts the nearby voxels. The amount of material left after the overcutting caused by the cutting tool is the stock allowance. The number of voxels to offset is given by Equation (3.1).
Where no represents the number of offset voxels, st is the stock allowance, and w is the width of a voxel in the direction of tool movement (here, ∆x), and D is the diameter of the cutting tool. For the present work, the voxel size is taken to be equal in both X and Y directions.

Voxel projection
The inner (Blind) features on the part are inaccessible for the vertical (Z) tool in the 3 axis CNC machines ( Figure 5 (a)). These inner features are represented by machinable voxels '0' in the present notation. To forbid cutting tool to move over such voxels (prevent overcutting), voxel projection is performed by the union of upper voxel layer to the consecutive lower layer ( Figure 5 (b)).

Tool Path Generation
The pre-processed voxel data is used to generate toolpath in three steps, viz. Machining area segmentation, Clustering of CL (Cutter Location) points, and Tool path stitching. These are explained as follows.

Machining area segmentation
The cutting tool gets lifted numerous times to machine a part having several machining features. A new way of machining area segmentation is proposed here to reduce the number of tool lifts. For illustration, a closed volume STL part model (500×500×100 mm) with four protruding features is taken as shown in Figure 6(a). The algorithm is as follows.
1. Start moving in the positive X-direction from an initial voxel (part zero for the first region shown by the blue color in Figure 6 (b)) while checking subsequent voxels. If vx'1' (nonmachinable voxels) is encountered, find nearest vx'0' (machinable voxels) in the vicinity of the current voxel in the next Y layer and move to that voxel.
2. Keep following the zig-zag path until the traversed voxel is the Y-extremity or a dead-end (i.e., the current voxel is surrounded by vx'1' only). The current position marks the end of the region. Store all the traversed points as the CL points for this region.
3. Find the remaining machining area (Trapped area) and mark the lowermost extremity of the Trapped area as the starting (initial) point of the next region.
4. Repeat steps 1 to 3 until the whole machinable area is covered.
To quantify the decrease in the number of segments, our result ( Figure 6 (b)) was compared with the one generated by the area decomposition method reported by Li et al. [18] (Figure 6 (c)). It was seen that for the present case, our approach significantly reduced the number of segments from 13 to 5. The subscripts a and b in Figure 6 (b) specify the start and end of the region number (n) where n ∈ [1,5]. The tracing starts at part zero (1a), and it continues in a zig-zag manner until the Y-extremity (1b) to mark the first machining region. The tracing again starts at the lowermost point (2a) of the remaining Trapped area, which stops when at the dead-end 2b. The process is repeated to form regions 3, 4, and 5. The voxel positions saved during the tracing form a toolpath. This approach of toolpath generation is termed as Trapped Area (TA) method in this paper. The TA method, however, is seen to induce unnecessary air cutting during machining. As a result, a sequencing strategy is used to visit these regions in an optimized manner to reduce air cutting.

Clustering of CL points
The generated CL data is approximately equal to the total number of machinable voxels. This data will create a very verbose CNC program having a large number of program blocks. The clustering of CL points is done to join small voxel-length segments into longer ones and generate a compact part program (Figure 7). The steps of clustering are as follows: 1. Identify the CL points that lie on the same line along the tool feed direction (say X).
2. Select the endpoints of the feed line to eliminate the intermediate points.

Tool path stitching
After clustering the CL points, the next task is to join the segmented regions in a proper sequence to minimize the air cutting time. The task of finding out the optimum toolpath can be considered as a modified Travelling salesman problem (TSP). In the present case, each region has two points (start and end), and so the total number of routes becomes n!*2n [8], which makes it harder to solve. Therefore, a modified Heuristic-Genetic Algorithm is used to solve this problem.
The problem can be defined as follows. The region numbers are defined from 1 to n, and with each region, there is an associated binary variable, which is defined as (Equation Where cij is the minimum Euclidian distance between regions i and j. The constraints which make sure that a region is traveled only once are given as (Equation (3.4)): The genetic algorithm (GA) is used to solve the sequencing problem with two ends per region.

Implementation of GA
The primary objective of the GA is to provide a solution to the optimization problems with a large solution space in the polynomial time. It works on the probabilistic transition rules rather than deterministic rules. Therefore, it is better suited to the TSP problem [8]. The steps to solve the tool pat optimization problem in the current work are as follows: 1. Create the initial population of the chromosomes. The elements of the chromosome signify the region numbers, and the order of their placement in the chromosome specifies the sequence of visiting the region. In the present work, the population size is chosen to be between 20 to 100 depending upon the number of regions to be visited. 2. Find the fitness of each chromosome of the population. In this work, a new way of calculating the fitness function to solve the TSP for a "two ends per city" problem is devised. The route indicators 'a' and 'b' for start and end points of a region respectively are added for every chromosome. After the optimization, the route indicator for each region is also received along with the best route as an output. The fitness fR of the route (chromosome) R is given by 1/CR. Where the CR is the minimum distance (Airpath length) required to traverse a route R as shown in Figure 8. Equation (3.5) mathematically represents the minimum distance function (CR).   (3.5) Where m is the length of the chromosome, i is the index for region number in a route, and k specifies the traversing direction of the path for region number i+1 (i.e., 0 for start to end and 1 for end to start).
3. Select the chromosomes with higher fitness as parents to reproduce. The rank selection method was used to select parents for crossover [9].
4. Application of crossover: The developed approach uses a partially matched crossover method [2] to preclude revisiting of the same region by preventing duplication of the genes in a chromosome.
The GA was implemented with the maximum number of iterations of 1000, which gives a nearoptimal solution for up to 50 region problem. The solution, however, converged rapidly (within 200 iterations) for the problems having less than ten regions.

Post-Processing
The toolpath generation module generates CL-data, which is processed to generate the final CNC part program in ISO neutral as well as in FANUC (G/M) format.

RESULTS AND DISCUSSIONS
The toolpath planning algorithm discussed earlier was implemented in Matlab2015b on a windows 10 platform and run on Intel i5 CPU with 8GB RAM. The performance of the developed system (TA and GA based approach) was evaluated for several case studies with varying part complexities. The results obtained from the GA approach were compared with the toolpath generated using our Trapped Area (TA) method and the parallel zig-zag roughing strategy of the commercial software (NX CAM 12.0.2).

Case Study 1
The part shown in Figure 6 (a) is taken as a basic test case for the proposed system. The toolpath parameters were chosen to be 10 mm flat end mill, with the sidestep of 6.6 mm, 2 mm depth of cut, and 3 mm stock allowance. The toolpath was generated using both our approaches (TA and GA). The segmented regions (Figure 6 (b)) were joined using GA and the optimum route was found to be 1a-1b-2b-2a-3a-3b-5a-5b-4b-4a. Figure 9 (a), (b), and (c) shows the roughing toolpath for a typical layer generated using NX CAM 12.0.2, TA, and GA respectively. Both TA and GA approaches are seen to give a smaller number of lift offs (four) compared to NX (five). The GA approach is better than TA and NX as it optimizes the sequence of visiting the segmented regions to reduce air cutting. This is indicated by the small air path segments in Figure 9 (c).  Both TA and GA algorithms give better results than the NX CAM in terms of the performance parameters like the number of tool lifts, and air cutting path length. Using the GA approach, the air cutting path length is reduced by about 54% than the Trapped area (TA) method and 65% less than the NX CAM.

Effect of part orientation
The size and number of the trapped area changes with the part orientation and so the optimum toolpath would change accordingly. It was decided to study the effect of part orientation on the total cycle time. Figure 10 (a-f) shows the variation in the region segmentation for different orientations of the workpiece for various rotation angles (λ = 20-90 degrees with the X-axis). It was seen that the path length changes because the total number of the zig-zag paths get reduced. The maximum reduction in total path length was observed to be 20% at 45 degrees. However, it is difficult to generalize this result because it depends on various factors, such as part geometry and complexity, part size, number and orientation of the features, etc. The proposed approach, however, suggests that the direction of toolpath is a critical factor in finding out the optimum path.

Case Study 2
To test the robustness and efficacy of the developed system, two more complex CAD part models were chosen -Part 1 from the NIST repository [22] (Figure 11 (a)), and Part 2, a complex free form surface model (Figure 11 (b)) having several peaks and valleys. The overall size of Part1 is 780×500×200 mm and that of Part 2 is 100x100x100 mm. The toolpath parameters were kept the same for Part 1 as in the previous case study except the depth of cut, which was taken to be 3.96 mm. For Part 2, the sidestep was chosen as 2 mm and depth of cut of 1 mm. Figure 11 (b) and (d) shows the simulated machined component in Vericut using the toolpath generated by our GA based approach. Table 2 presents the comparison of the performance of our algorithms (TA and GA) with the commercial CAM software (NX CAM). The results show that the GA based approach gives better results in terms of the performance parameters. In particular, the GA based approach has about 37% less air cutting path length than the TA approach, and 47% less than the NX CAM. The reduction in the total tool path length for the GA based approach was observed to be about 9% less than TA and 15% less than NX CAM, respectively.   The performance of our algorithm was tested by running the code on Intel i5 CPU with 8GB RAM. It was observed that for the freeform surface part model by decreasing the voxel size from 5mm to 1 mm, the run time increases from 0.40 sec to 15 secs to generate the CNC part program from voxel CAD model. This is thought to be fairly fast and accurate.
The result of the case studies shows that the developed system (GA based) provides better toolpath in terms of the number of tool lifts, air cutting path length, and the total path length. The actual variation in the performance parameters depends upon the part complexity and the number of features.

CONCLUSIONS
The current approaches for toolpath generation are often sub-optimal and time-consuming. This paper presents a novel approach to generate a zig-zag toolpath for rough machining operations on a 3 axis CNC milling machine. The proposed methodology is efficient, robust, and computationally inexpensive. The algorithm uses the voxelized part model and segregates the machinable and nonmachinable areas. GA based strategy was used to sequence the segmented regions and generate the optimum toolpath with minimal tool lifts. Case studies with various machining features were carried out to compare the performance of toolpath generated by our system with the commercial CAM software. Our system was found to provide more efficient and robust toolpath in terms of a reduced number of tool lifts, air cutting path length, and total path length. The approach can be extended further to other path planning strategies for multi-axis CNC machining.