HyBoDT: Hybrid Bounded Distance Transforms of Trimmed NURBS Models

Abstract

Distance field representation of objects in 3D space has several applications such as shape manipulation, graphics rendering, path planning, etc. Distance transforms (DTs) are discrete representations of distance fields in a regular voxel grid. The two main limitations of using distance transforms are that they are compute-intensive, and there are errors introduced while representing the object using DTs. In this work, we develop a hybrid graphics processing unit (GPU)-accelerated marching wavefront method for computing DTs of models composed of trimmed non-uniform rational B-splines (NURBS) surfaces with theoretical bounds. Our hybrid marching approach eliminates the error due to calculating approximate distances by marching. We also calculate the bounds on the error introduced due to the tessellation of the trimmed NURBS surfaces and calculate the propagation of these bounds in computing the DT. Finally, we present computation times for both 2D and 3D GPU DTs of test objects. We show that our GPU-accelerated approach is significantly faster than existing CPU-based methods.