Hybrid Dynamic Trees for Extreme-Resolution 3D Sparse Data Modeling

We present the hybrid dynamic tree (HDT), a novel adaptive tree-based data structure for representing high-resolution sparse volumes. Roughly speaking, HDTs combine dense volumetric grids with sparse octrees in a way that makes them both more compact and better-suited to GPUs than state-of-the-art alternatives. For our motivating applications in computer-aided design and manufacturing (CAD/CAM), we show 2x reductions in storage on realistic inputs compared to these alternatives; additionally, we show up to 16x speedups over multicore CPU implementations on a specific computational bottleneck known as an offset surface computation. Indeed, these combined improvements allow us to perform offsetting on a single node at resolutions well beyond that of the prior work and the capabilities of current commercial packages. And beyond CAD/CAM, HDTs may find applications in 3D geometric modeling problems for a variety of domains, including medical imaging and graphics.