An Improved Algorithm for Fast Computing Distance Between Points and Triangle Meshes

To solve the problems of the existing point-to-triangle-mesh distance computation algorithm which runs slow or gets a wrong answer in some cases, an improved algorithm based on voxel structure was proposed.This algorithm first computes the voxelized mesh by sampling all triangles and computing the voxels of sample points of each triangle;Then the algorithm searches all voxels which are away from the given point less than a given value within the bounding box of the mesh by considering the distance variation of adjoin voxels, expands the given value gradually until at least one non-empty voxel is found, gets the original distance by computing the distance between the given point and the nearest triangle within the triangles which are found, and expands the given value to the original distance adding an appropriate small number.The nearest triangle will be found and the accurate distance will be calculated.Experimental results show that this algorithm has a good performance.The time consumption of distance computation between a triangle mesh and a distant point can be reduced compared with the existing algorithm.