Fast and Efficient 3D Chamfer Distance Transform for Polygonal Meshes

Abstract

We present an efficient GPU-based method to perform 3D chamfer distance transform (CDT) in a wavefront scheme. In this context, we also introduce a binary voxelization algorithm which provides the initial boundary condition for the CDT. The voxelization method is capable of both, surface and solid voxelization, allowing for the computation of unsigned distance fields for arbitrary polygonal meshes and signed distances for models with orientable surfaces. Our method is trimmed on speed rather than accuracy. It works with simple chamfer metrics such as the Manhattan and chessboard distance and requires only a single rendering pass per distance layer. Due to the wavefront scheme, a propagation can be stopped if a required number of distance layers is reached. However, even a complete distance field can be computed in the magnitude of 10?3 seconds including the preprocessing voxelization step. This allows for a use in real-time applications such as path planning or proximity computations. We demonstrate the application of our method for the latter.