# A G-Code Generator for Volumetric Models
## 3 Materials and Methods
### Support Structure Generation  
In some LM processes, for example fused deposition modelling (FDM), support structures are needed to prevent the printed objects from collapsing during the printing stage. Many support structure generation techniques have been proposed for polygonal models [23; 24]. Most of these methods explore the angles between the \(z\) axis and surface normal of the input model to detect supporting points and generate support structures. Since our input models are voxel-based, their support structures cannot be built by using these conventional methods. In this research, we developed a pattern-based method to produce support structures for volumetric models. At first, we found all the voxels in the input model that had no neighboring voxel immediately beneath them. We called these voxels the overhangs in this article. Secondly, we classified all overhangs into different types. Then, based on their types, necessary support structures were produced below the overhangs.  
Our overhang classification method works as follows: Assume that the target overhang is at position (\(i\), \(j\), \(k\)). At first, we examined the 8 voxels residing at layer \(k-1\) and were adjacent to the overhang by sharing an edge or a vertex. If two or more of these neighbors are model voxels, this overhang would get enough support from them and this overhang is classified as supported. No support structure will be grown below it at the following stage. Otherwise, we check the 8 neighboring voxels residing at layer \(k\) and classify the overhang as an end, corner, edge, or bottom overhang according to predefined patterns. Some of these classification patterns are depicted in Figure 3. If this overhang has no more than 1 neighboring model voxel at layer \(k\), as shown in part (a), it is classified as an end overhang. If it is on the boundary of the model and the acute angle around it is less than or equal to 90 degrees, this overhang is classified as a corner overhang as shown in part (b). If it is on the boundary and the acute angle is greater than 90 degrees, as depicted in part (c), this overhang is an edge overhang. If this overhang does not meet any of the above conditions, it is regarded as a bottom overhang as shown in part (d).  
If the overhang is an end or a corner overhang, the cohesion between it and the neighboring vertex may not be strong enough to support it, and a vertical bar is placed under it. The top end of the bar reaches the overhang, and the other end of this pillar extends to the floor or the model's surface. If the overhang is an edge or a bottom overhang, it has some support from its neighbors (because of cohesion). We do not have to create support structures for all of them. Instead, we select some of them as supporting points and build support bars beneath them. The selected overhangs should be  
Figure 3: Classification patterns of overhangs: (**a**) end, (**b**) edge, (**c**) corner, and (**d**) bottom overhangs. The star represents the overhang to be classified, and the squares are its neighboring model voxels at the same layer. This figure shows only some representative patterns. Other patterns can be obtained by rotations or by analogy.  
away from other model voxels at the same layer by at least \(d\) voxels, where \(d\) is a constant decided by the users.  
An example of support structure generation is shown in Figure 2. The support structures of the input model and the oriented model are shown in parts (c) and (d). The model voxels are rendered in red, while the support structures are shaded in dark green. The value of \(d\) is 4 voxels in this case. The support structures of the original model contain 67,388 voxels, while the support structures of the oriented model include only 50,390 voxels. In this case, our orientation program reduces the volume of the support structures by more than 25%.