A GPU-parallel construction of volumetric tree

Volume data has extensive uses in medical imaging, like, MRI (magnetic resonance imaging) scan, visual effects production, including volume rendering and fluid simulation, computer-aided design and manufacturing (CAD/CAM) in advanced prototyping, such as, 3D Printing, among others. This work presents a compact hierarchical data structure, dubbed HDT, for extreme-scale volume modeling. The name is shorthand for hybrid dynamic tree. HDT is hybrid in that it fuses two contrasting structures, namely, octree and tiled grid. Such fusion of two opposing data layouts alleviate the limitations inherent to the respective structures. We describe the HDT construction algorithm to generate volumetric representation of triangle mesh on GPUs. While HDT mirrors much of the existing works on sparse 3D data modeling, our evaluation and comparative studies with prior researches demonstrate that HDT is arguably the most storage-effective representation. The geometric topology in HDT consumes just short of two bits per voxel --- five times compact relative to the current state-of-the-art volumetric structure.