We propose a novel 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 with respect to this base. This decomposition is useful for fabrication
methodologies such as 3-axis CNC milling, where a single milling pass can only carve a
single height-field surface defined with respect to the machine tray, but can also benefit
other fabricationsettings. Computingourdesireddecompositionrequiressolving 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 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.
We demonstrate our method on a range of inputs, and showcase a number of real life models
manufactured using our technique.
DOWNLOADS
(paper)
(code)
(data)
ADDITIONAL VIDEOS
Milling Max Planck (wood, 3-axis milled)
Assemblage of Max Planck (wood, 3-axis milled)
Assemblage of Lion (plastic, 3d printed without supports)
Assemblage of Moai statue (wood, 3-axis milled)
BibTex
@article{MLSSP18,
author = {Muntoni, Alessandro and Livesu, Marco and Scateni, Riccardo and Sheffer, Alla and Panozzo, Daniele},
title = {Axis-Aligned Height-Field Block Decomposition of 3D Shapes},
journal = {ACM Transactions on Graphics},
year = {2018},
volume = {37},
number = {5},
doi = {10.1145/3204458}}