Geometry Processing for Subtractive Fabrication

Subtractive manufacturing technologies, such as 3-axis CNC milling, add a useful tool to the digital manufacturing arsenal. However, each milling pass using such machines can only carve a single height-field surface, defined with respect to the machine tray, limiting the set of geometries that may be produced with this technique. This thesis presents two methods which enable the fabrication of simplified or decomposed geometries using subtractive techniques. The first method aims to obtain, starting from a given model, a simplified shape that can be easily unfolded. The final objective is to reproduce it by producing the unfolded object using a 3-axis CNC milling machine with special milling tools called V-Routers, to create particular joints which make the assembly process an easy task. The second method enables fabrication of general 3D shapes using 3-axis CNC milling methodology by providing a novel robust algorithm for decomposing general 3D geometries into a small set of overlap-free height-field blocks, volumes enclosed by a flat base and a height-field surface defined concerning this base. Such blocks can be manufactured with a single pass of 3-axis milling and then assembled to form the target geometry. Computing the desired decomposition requires solving a highly constrained discrete optimization problem, variants of which are known to be NP-hard. We effectively compute a high-quality decomposition by using a two-step process that leverages the unique characteristics of our setup. Specifically, we notice that if the height-field block directions are constrained to the major axes we can always produce a valid decomposition starting from a suitable surface segmentation. Our method first produces a compact set of large, possibly overlapping, height field blocks that jointly cover the model surface by recasting this discrete constrained optimization problem as an unconstrained optimization of a continuous function, which allows for an efficient solution. We then cast the computation of an overlap-free, final decomposition as an ordering problem on a graph, and solve it via a combination of cycle elimination and topological sorting. The combined algorithm produces a compact set of height-field blocks that jointly describe the input model within a user given tolerance and satisfy all manufacturing constraints. We demonstrate our method on a range of inputs, and showcase some real-life models manufactured using our technique.