Fast Point to Mesh Distance by Domain Voxelization

Abstract

Computing the distance from a point to a triangle mesh is a key computational step in robotics pipelines such as registration and collision detection, with applications to path planning, SLAM, and RGB-D vision. Numerous techniques to accelerate this computation have been developed, many of which use a cheap pre-processing step to construct a hierarchical decomposition of the mesh. If the mesh is fixed and known ahead of time, there is an opportunity to conduct more expensive pre-computations to accelerate the subsequent distance queries. This work presents a voxelization approach, implemented on both CPU and GPU, to compute point to mesh distance that constructs for each voxel a near-minimal set of triangles that is guaranteed to include every triangle that is closest to at least one point in the voxel. Theoretical and numerical comparisons with six alternative distance algorithms demonstrate the speed advantages of the proposed method.