Title: Hybrid Dynamic Trees: Applications to High-Performance Discrete Volume Offsetting

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:

---------

While the recent development in 3D printing has liberated digital manufacturing, and thus the fabrication of free-form shapes is no longer constrained by the manufacturing process; such technology is limited in terms of the materials that can be used and relatively slow printing speeds.  By contrast, subtractive manufacturing techniques, such as, CNC (computer-numerical control) milling and turning are complementary in many aspects. Nonetheless, these classical manufacturing processes are severely limited in terms of the shapes that can be produced due to the complexity of generating collision-free tool paths with multi-axis CNC setups. A key reason behind the lack of automation in the CNC path-planning process is attributable to the underlying solid geometry representations used in the existing CAD/CAM software. Typically, CAD interfaces are represented in explicit or parametric form that generally yields high quality in geometric modeling, but challenges the core computations of tool trajectories generation process, such as, surface offsetting, set union or intersection etc. to be completely automated.

To address the fundamental limitation of sculptured part fabrication in CNC based subtractive manufacturing, this thesis proposes adopting a discretized three-dimensional geometric modeling. By the nature of the discrete volume (voxel) representation, algorithms operating on such geometric primitive are robust, easy to comprehend, and amenable to accelerated processing on parallel computing units. However, to adopt a voxel based representation there are two major challenges: (1) how to compactly store volume at extreme resolution, and (2) how to efficiently construct and edit volume interactively. These two objectives are contrasting by nature — storage effective representations are computationally inefficient, and vice versa. This dissertation research presents such a hybrid approach of voxel representation that blends a computation-efficient representation with a storage-compact data organization such that both of the objectives are mutually balanced. As the convergence of massively parallel many-core GPUs with conventional multicore CPUs is becoming a reality, we adopt a GPU centric approach to implement the proposed data structure.

Further, in order to design a CNC toolpath planning system with a significantly improved level of automation, this thesis proposes an efficient implementation of discrete volume offsetting algorithm that uses the presented hybrid data structure as the underlying geometric representation. A 3D convolution based offsetting methodology is explored that aims at much higher resolution than the current state-of-the-arts, and targets leveraging the massively parallel computing fabric on modern GPUs to match with the computational demand.