A part complexity measurement method supporting 3 D Printing
The use of packing algorithms to fill build volumes in 3D printing promotes both more efficient processes and better utilisation of the available build space. There are various packing techniques, and the choice of an appropriate one is often highly dependent on the characteristics of the parts to be printed, among other factors. Part complexity, and particularly convexity, is an important factor. This paper presents metrics for quantitatively evaluating part complexity, extending a 2D metric to a 3D situation. These metrics are then available for classifying problems and identifying appropriate packing algorithms. Introduction Cutting and packing (C&P) is an important research area within Operations Research. It aims to develop solutions for problems of maximising the utilisation of available manufacturing capacity or material. It has been demonstrated that there is a relationship between the usage of the available build space and the efficiency of some 3D Printing processes in terms of resource consumption, including financial cost [1] and energy consumption [2] Therefore, improving and applying automated packing methodologies to 3D Printing is likely to result in more sustainable and profitable production. A large variety of C&P techniques have been developed in the last few decades. One particular approach that has shown promising results is the utilisation of basic information about the parts to be packed to evolve the method itself rather than to solve an individual case [3, 4] The majority of papers that use this approach address regular packing problems by orthogonally placing cuboid elements of geometry within a large bin or container. To address more realistic cases, this research investigates whether additional characteristics, or features, present in irregular parts can be used to improve the performance of C&P methodologies. Previous research on the evaluation of part complexity, sometimes referred to as shape complexity, has been applied to areas other than 3D Printing, e.g. architecture [5] and design [6] This paper introduces a new part complexity measure for packing approaches supporting 3D Printing processes. By discussing the proposed complexity measure in the context of the existing measures which have already been identified in the literature, the authors expect to lay the groundwork for future research into irregular packing. This paper is structured as follows: A brief presentation of packing methodologies applied to 3D Printing and an overview of existing shape complexity measures are presented in the next two sections. The next section introduces the new proposed metrics, along with a practical method for calculating the Spies Ratio. The experimental results are then presented and discussed, before the final section concludes the paper, summarising the work and discussing future work. Background A variety of packing methodologies has been applied to 3D Printing [7, 8, 9, 10] and they differ mainly in the way that they search for promising sequences of parts, i.e. in the order in which the items are positioned within the build volume. For example, Canellidis et al. [11] use a Genetic Algorithm (GA) to determine a good ordering of the parts. A GA is a metaheuristic, which is a high level algorithm that mimics the process of natural selection and reproduction of the fittest individuals [12] An interesting aspect in [11] is that each part has its orientation previously optimised according to one of three criteria: height, volume of supporting structures and surface roughness. This method, therefore, uses basic information about the geometry of parts to improve the overall results of the algorithm. There are metaheuristic optimization methods which make use of problem features for choosing and applying the best approach before or during the search process to solve a given problem instance [13, 4] This line of studies on the application of data science techniques to exploit richer information (e.g. problem instance/solution features) improving the learning process leading to more effective solution methods in combinatorial optimization has been growing [14, 15] For example, hyperheuristics utilizing part characteristics have been successfully applied to regular packing [16, 17] Existing Metrics This section presents existing methodologies for evaluating part complexity. The first is the Spies Ratio (SR) [18] which is calculated by the dividing the volume of the geometry part by the volume of the primitive that contains it. An interesting aspect of the SR is the need to find the correct alignment of the part which will minimise the primitive volume. The second part complexity that we consider was presented by Valentan et al. [19] and is a straightforward assessment of part complexity which depends entirely on the number of facets (f) the surface area (a) and the volume (v) of the used polygonal model of part geometry. Its method of calculation is presented in Table 1. Finally, the mean connectivity value (MCV) proposed by Psarra and Grajewski [5] assesses the complexity of twodimensional polygons (rather than three dimensional parts) by considering the 'connectivity' between areas on the perimeter. Additional supporting measures were introduced to evaluate the variation of connectivity amongst the perimeter locations and the fluctuation rate of connectivity values, which are the v value and h value respectively. 6 This measure is the basis for the proposed part complexity method in this paper, which extends the MCV and the v value to the three dimensional context leaving the hvalue measure for future work. The MCV and the two part complexity methods previously mentioned are summarised in Table 1. Measure Formulation Range Interpretation Spies Ratio[18] vpart vprimitive (0,1] Volume of the part divided by the volume of the primitive Valentan et al.[19] f *a v (0, Number of facets times the surface area divided by the volume Psarra and Grajewski [5] n i=1 VCi n (0,1] Mean of connectivity values of the n voxels on the surface Table 1: Summary of the three part complexity in literature. Proposed Metrics This section proposes new metrics for measuring the characteristics of given 3D parts: a 3D version of MCV and vvalue as well as a practical approach to calculating SR. The MCV measure, mentioned in the previous section, assesses twodimensional geometries by evaluating the connectivity between areas on their perimeters [5] This research extends [5] to a 3D situation, considers the way in which the voxelisation can affect the areas which are connected by the algorithm and the effects of the granularity of the voxelisation upon the value of the metric. Although not the main focus of this paper, an optimization method for calculating the minimum bounding box of a part is also proposed, to support the calculation of the Spies Ratio [18] Calculation of MCV and v value The first step of the MCV calculation consists of the rasterization of the geometric model of the part into a 3D voxel grid with an appropriate resolution from the viewpoint of performance and execution time, a process called voxelization [20] In contrast to the original approach [5] which calculates the connectivity between areas on the perimeter, this technique calculates the connectivity between voxels on the surface. Figure 1. An example from the Baumers et al. [9] rasterized in resolutions of 20, 100 and 200 voxels. Following the discretization process, the connectivity value (CV) of each voxel belonging to the surface of the part is calculated which is the percentage of other surface voxels that can be connected to the former one through a Bresenham's line [21] such that all voxels on that line belong to the interior of the shape. The interpretation is that voxels with low CV have poor interconnectivity to other portions of the part. The MCV of a part is then formed by calculating the mean of the CV values of all the surface voxels. For fully convex parts, the MCV is equal to 1. Entrant features will reduce the MCV value, so the more concave the shape, the closer MCV will be to 0. The resolution of the voxelisation has a large effect upon performance, in terms of both runtime and accuracy. To visualise the differences, Figure 1 illustrates an example of part used by Baumers et al. [9] voxelized using a grid of 20, 100 and 200 parts, respectively. It was found that low resolutions lead to fast but imprecise MCV calculations, as perhaps expected from the visualisation, however high resolutions result in computationally expensive processing. For example, tests conducted on a 3.40GHz Intel PC with 8.00 GB RAM showed that resolutions above 100 voxels result in MCV calculations which take over five minutes per part. The calculations of the CV and MCV metrics for voxel pairs and parts, respectively, allow the extension of the auxiliary metric v value, which describes the variation of connectivity through the surface of the part. It is obtained by taking the standard deviation of the CV values of all of the voxels on the surface of the part. Calculation of Spies Ratio Algorithm 1: Pseudo code of the Steepest Ascent Hill Climbing with Random Restart. 1 currentSolution randomSolution( 2 bestSolution currentSolution; 3 while not termination criterion do 4 currentValue evaluate(currentSolution) 5 bestNeighbour NULL; 6 for each solution s in the neighbourhood of (currentSolution) do 7 if evaluate(s) evaluate(bestNeighbour) then 8 bestNeighbour s; 9 end 10 end 11 if evaluate(bestNeighbour) evaluate(currentSolution) then 12 if evaluate(currentSolution) evaluate(bestSolution) then 13 bestSolution currentSolution;