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

This paper presents the hybrid dynamic tree (HDT), a novel adaptive tree-based data structure for representinghigh-resolution sparse volumes. Roughly speaking, HDTs combine dense volumetric grids with sparse octrees ina way that makes them both more compact and better-suitedto GPUs than state-of-the-art alternatives. For our motivatingapplications in computer-aided design and manufacturing(CAD/CAM), we show 2× reductions in storage on realisticinputs compared to these alternatives, additionally, we showup to 16fix speedups over multicore CPU implementations ona specific computational bottleneck known as an offset surfacecomputation. Indeed, these combined improvements allow usto perform offsetting on a single node at resolutions wellbeyondthat of the prior work and the capabilities of currentcommercial packages. And beyond CAD/CAM, HDTs may findapplications in 3D geometric modeling problems for a varietyof domains, including medical imaging and graphics.