TY - JOUR
T1 - Axis-aligned height-field block decomposition of 3D shapes
AU - Muntoni, Alessandro
AU - Livesu, Marco
AU - Scateni, Riccardo
AU - Sheffer, Alla
AU - Panozzo, Daniele
N1 - Funding Information:
This work was supported in part by the NSF CAREER award IIS-1652515, the Italian DSURF PRIN 2015 (2015B8TRFM) project, the European Union's Horizon 2020 research and innovation programme under grant agreement No 680448 (CAxMan), a gift from Adobe, and a gift from NTopology.
Funding Information:
This work was supported in part by the NSF CAREER award IIS-1652515, the Italian DSURF PRIN 2015 (2015B8TRFM) project, the European Union’s Horizon 2020 research and innovation programme under grant agreement No 680448 (CAxMan), a gift from Adobe, and a gift from NTopology. Authors’ addresses: A. Muntoni, M. Livesu, R. Scateni, A. Sheffer, and D. Panozzo; emails: {muntoni.alessandro, marco.livesu}@gmail.com, [email protected], sheffa@ cs.ubc.ca, [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2018 Association for Computing Machinery. 0730-0301/2018/10-ART169 $15.00 https://doi.org/10.1145/3204458
Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/11
Y1 - 2018/11
N2 - We propose a novel algorithm for decomposing general three-dimensional 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 fabrication settings. Computing our 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 directions are constrained to the major axes, then 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.
AB - We propose a novel algorithm for decomposing general three-dimensional 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 fabrication settings. Computing our 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 directions are constrained to the major axes, then 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.
KW - Fabrication
KW - Shape decomposition
UR - http://www.scopus.com/inward/record.url?scp=85055756106&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85055756106&partnerID=8YFLogxK
U2 - 10.1145/3204458
DO - 10.1145/3204458
M3 - Article
AN - SCOPUS:85055756106
SN - 0730-0301
VL - 37
JO - ACM Transactions on Graphics
JF - ACM Transactions on Graphics
IS - 5
M1 - 169
ER -