Closest Point on a Mesh : Background and Approaches

PROBLEM STATEMENT

Given a Mesh, a Query Point and a search radius, retrieve the closest point on the mesh if it exists.

Assumptions for the code

• The mesh will be a triangulated mesh
• Input is from PLY ASCII file format

Background

Let us visualize this problem as follows. We have a Query point and search radius,which is a Sphere with the point at its center. Given a mesh, the candidate point should satisfy these conditions

• Candidate point lies within the sphere
• Candidate point lies on the mesh
• This point should be the closest to Query point in terms of a distance metric(euclidean distance).

We can think of this problem as an intersection of a mesh and a sphere. How quickly can we reduce this search space is the question at hand. Either we have a fast and efficient data structure for the mesh represenation, which helps reduce query time or we try to reduce the "problem space".

The other spectrum is doing minimal/simple calculations of O(n), assuming we have abundant compute resource. Further speedup(if needed) is to think of this as parallel computing problem which can be solved as smaller disjoint problems.

Approaches to solution

1. Brute Force

Loop through all primitives, find a point on mesh which is closest to the query point.

2. Simple Plausible Solution

Another way to look at this problem is, if a point is on the mesh, it should either be a Vertex of a triangle, or lie on the edges or on the interior of a triangle. We compute all these distances and the least distance will be the closest point.

• It is faster to compute distance between 2 points (Vertex, QueryPoint)
• It is also fast enough to compute distance point and a line segment. We don't have to compute the distance if the projection from the query point doesn't lie on the line segment, as it might be a part of another edge or not of interest.
• A similar approach can be used to compute distance to an internal point on the face of a triangle

Optimizations

• When scanning through all vertices and edges to compute distance, maintain a list of vertices(end points of an edge) as a set.
• These vertices are definitely the best candidates, which exist in the bounding sphere with the QueryPoint at its center and search distance being radius
• We can save on looping through all faces, and can pick only those faces which have at least one of the vertices in this set
• Most of this can be parallel, i.e when processing vertices and edges for minimum distance.

3. Volumetric Approach / BVH Tree / Sphere Tree

Most third party softwares, usually store the mesh data as some variant of a tree which partitions data based on proximity, so we have a faster access time. But, this data structure has an overhead of building it once, either top down or bottom up. Lookup is always better than compute.

• Ideally if we got the intersection of the Bounding sphere and mesh as a new mesh, our task would be to simply compute distances in any of the known methods described above.
• The volumetric approach can be discussed in detail based on the data structure in use, but the concepts remain same. For example, in a BVH Tree(Bounding Volume Hierarchy) each bounding volume node comprises of a set of primitives which are grouped based on proximity. If we choose not to traverse a path in the tree, we can effectively neglect any descendants and speeding up the search.
• Shoot a ray from the point towards the mesh, and any volumes greater than the search distance can be dropped. The remaining volume can be used to find distances as mentioned above.
• Dealing with volumes has a small flip side of overestimation - To estimate the smallest bounding volume for a given set of primitives.

4. Numerical Methods

The last approach is to look at it as a pure linear programming problem. Consider a triangle to be defined by a set of points on the edges and interior of itself. The density of points can be varied to have a tighter representation of the triangle. Extending this to a mesh, we have a massive point cloud representation. The resolution of this mesh can be tweaked for higher accuracy.

The problem is to now compute distances between surface points and query point to find the minimum point. Computing squared distance can be used instead of the square root to help optimize speed. The resolution of points on mesh and the minimization step could vary depending on the trade off between computation time and accuracy.