Axis-Aligned Height-Field Block Decomposition of 3D Shapes
Alessandro Muntoni, Marco Livesu, Riccardo Scateni, Alla Sheffer, Daniele Panozzo
ACM Transaction on Graphics (2018)
Abstract
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 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 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.
Source Code
Source code is hosted on this GitHub repository. The program is built and tested on Ubuntu 18.04 system with GCC 7.3.
Downloading
git clone --recursive https://github.com/muntonialessandro/HeightFieldDecomposition.gitBuild and Run (Ubuntu 18.04)
sudo apt-get install qt5-default
sudo apt-get install libboost-all-dev libcgal-dev libgmp-dev libqglviewer-dev-qt5 libeigen3-devclone libigl and create an environment variable named LIBIGL_HOME containing its directory (https://github.com/libigl/libigl/) install gurobi and create an environment variable named GUROBI_HOME containing its directory (https://www.gurobi.com/) clone cinolib and create an environment variable named CINOLIB_HOME containing its directory (https://github.com/maxicino/cinolib)
qmake HeightFieldDecomposition.pro
make