HotCSE Seminar
Computational Science & Engineering
Wednesday February 03, 12pm-1pm, 1116-E Klaus

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

Mohammad M Hossain
Advisor: Prof. Richard Vuduc and Prof. Thomas Kurfess (ME)


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.


Mohammad M Hossain is a CS PhD student, advised jointly by Prof. Richard Vuduc and Prof Thomas Kurfess (ME) since Spring 2014. His research work focuses on storage-efficient hybrid data structure design for extreme-resolution volumes processing on GPUs. He is working on a GPU-accelerated CAM (computer-aided manufacturing) development that will enable subtractive (CNC milling) manufacturing with the ease of the programmability of 3D printing.