~~Title: Voxel-based Offsetting at High Resolution with Tunable Speed and Precision using Hybrid Dynamic Trees.

Mohammad M. Hossain
Computer Science Ph.D. Candidate
School of Computational Science and Engineering
College of Computing
Georgia Institute of Technology

Date: Wednesday, October 5, 2016
Time: 11 AM – 1 PM
Location: Klaus Advanced Computing Building (KACB) 1120E
(please note the change)

Committee:
---------------
Dr. Richard Vuduc (Advisor, School of Computational Science and Engineering, Georgia Tech)
Dr. Thomas Kurfess (Co-Advisor, School of Mechanical Engineering, Georgia Tech)
Dr. Jarek Rossignac (School of Interactive Computing, Georgia Tech)
Dr. Jeffrey Young (School of Computer Science, Georgia Tech)
Dr. Thomas Tucker (Tucker Innovations Inc.)

Abstract:
------------
In the recent years, digital manufacturing has experienced the wave of rapid prototyping through the innovation and ubiquity in 3D printing technology. While such advancement liberates the constraints of shape selection in physical objects, 3D printing is yet to match the precision, robustness and vast applicability offered by the classical subtractive  manufacturing process. To simplify the toolpath planning in conventional multi-axis CNC machining, recent researches have proposed adopting a voxel-based geometric modeling. Inherently, a voxel representation is amenable for parallel acceleration on modern ubiquitous GPU hardware. While there can be many different approaches to represent voxels, this work is based on a novel voxel data structure called hybrid dynamic tree (HDT) that combines dense grid and sparse octree in such a way that makes it both more compact (i.e., storage efficient) and better-suited to GPUs (i.e., computation effective) than state-of-the-art alternatives. This dissertation contributes in the following four aspects:

First, we present a parallel method to construct the HDT representation on GPU for a  CAD input modeled in a triangle mesh. In addition, to optimize the memory footprint in the HDT our research explores the theoretical storage analysis for different active node branchings in the Octree. Thus, we incorporate tunability into the HDT organization to study the complexity of memory footprint. The developed theoretical storage analysis is validated with rigorous experimentation that helps devising optimal parameter selections for storage-compact HDT representation.

Next, the thesis presents a mathematical morphology based offsetting algorithm using the HDT voxel representation.  At our target resolution of 4096 x 4096 x 4096, our goal is to compute large-scale offsets in minutes, match or beat the number of bits of the representation compared to state-of-the-art alternatives, and experimentally characterize any trade-offs among speed, storage, and precision. While using the HDT as the underlying data structure leads naturally to a storage-efficient representation, the challenge in developing a  high-performance implementation of offset algorithm is choosing an optimal configuration of the HDT parameters.These parameters not only govern the memory footprint of the voxelized representation of the solid, but also control the parallel code execution efficiency on parallel computing units on GPU.

Capability of fine-tuning of a data structure is crucial for understanding, and thereby optimizing, the developed  computation-intensive algorithm that uses the HDT as the underlying voxel representation. Towards that end, this thesis explores different practical approaches to achieve high-performance voxel offsetting. First, we study the impact of the different HDT configurations on the voxel offsetting. Next, to devise a fast voxel offsetting we analyze the trade-offs between speed and accuracy through controllable size of the morphological filter. We study the impact of the decomposition of a large offset distance into a series of offsetting with smaller distances. To facilitate this trade-off analysis, we implement a GPU-accelerated error measurement technique.

Finally, to enable even faster voxel offsetting, we present the principles of offloading the offset computation in the HDTs across a cluster of GPUs co-hosted on the same computing node. Our research studies the impact of different approaches for CUDA kernel execution controlled through either single or multiple independent CPU threads. In addition, we examine different load distribution policies that consider the computational disparity in the deployed GPUs. With more and more GPUs  integrated on a single computing node, such exploration of algorithmic speedup through load-balanced implementation of voxel offsetting across multiple GPUs emphasizes the high scalability of the HDT's hybrid voxel representation.