Find closest point from an origin, in a mesh

Question

I want to do something similar to a raycast. With a raycast, you can set an origin and a destiny, and check where the ray collides with something but only with a line. What I want to do, is given an origin with x, y and z coordinates, check which is the closest point it collides in a mesh. so if I have a box in 0, 0, 0 with width 2, and my origin is on 0, 0.5, 0, the algorithm/function should return that the closest point it collides is 0, 1, 0. I hope I am clear enough.

I am using Ogre3D, and bullet physics. I can also use OpenGL.

Thanks.

Answer 1

You want to use GJK. The general algorithm finds the closest point between two (convex) meshes, but of course one of your "meshes" can just be a single point in space.

Note that since it only works with convex shapes, you need to break your mesh down into convex pieces (if it's not already convex) in order to apply the algorithm. Find the closest point to each chunk and then keep the closest result.

The algorithm operates by evaluating geometric primitives and refining the primitive under consideration by finding the "next closest" adjoining primitive. You start on each mesh with a point, expand that to a line, then to a triangle, then a tetrahedron, "walking" the adjoning tetrahedrons (or simpler shapes) until you arrive at the point/line/triangle closest to the other shape.

It's easier to visualize than it is for a paragraph or two of prose to explain. Check out Allen Chou's overview or this Molly Rocket video tutorial. The technique extends fairly easily from 2D to 3D.

Answer 2

Finding the closest point on a mesh to a point P can be done by iterating on all primitives of the mesh’s surface (triangles, quads, etc.) and finding the primitive that is closest to P. If your mesh is made of triangles, this question has pointers to several methods for distance calculation, especially “Distance from a point to a triangle (3D)” which comes with full source code. Otherwise, you may look at e.g. box-point distance.

Once you know which is the closest primitive, you can find the closest point. It’s possible that the distance calculation already provides the information (if you used the source code from geometrictools.com). Sometimes the closest point is a vertex of the mesh, sometimes it’s on an edge, and some other times it lies in the middle of a triangle.

This would be the algorithm:

best_primitive = null
best_dist = infinity
for each primitive in mesh:
    new_dist = distance(P, primitive)
    if new_dist < best_dist:
        best_dist = new_dist
        best_primitive = primitive
best_point = closest_point(P, best_primitive)

This method is O(n).