Hi there, I'm searching a fast algorithm for the following problem: I've an arbitrary 3d point P and a triangle mesh (consisting of vertices, edges and triangles). For point P I must find the coordinate of the closest point on the surface of the mesh. This point can therefore lay within a mesh's triangle, onto an edge or can coincide with a vertex. The question is: How? How am I doing this efficiently? My first thought was to try to find a point defined in barycentric coordinates on each triangle for which the distance to the point P is minimal. But I assume this is very time consuming and secondly I've no clue how to do that. Another way of thinking was to find the closest vertex within the mesh. Then, find the closest point on each adjacent edge by projecting the point P on the edge and -- further on -- find the closest point on the adjacent triangles by projecting P onto the plane defined by them and checking if this projection lays within the triangle and taking the closest of all these. But this also sounds too inefficient. Well, if anyone can give me a hint I'd be thankful. Greetings, Data

Your method is asserting that the mesh is defining a convex body. Is that so? If, in general, not, then I don't think that you can get much faster than just check all minimal distances (distance to all vertices, distances to all edges that contain your point's projection on their line, and the same with faces).

Hi, the mesh is definitely NOT convex. So you suggest using my second approach? Finding a closest point (or all closest points in a given radius) and from there, testing all adjacent edges and triangles?

My suggestion: first code up a triangle-point distance function.

Then implement a brute-force solution (just walk through all triangles). Keep this as a reference.

Then I would be inclined to put the mesh triangles in a spatial structure - (loose) octree for example. Then find the closest octree cell to your point. Walk through all the triangles in this cell, and in any other cells that lie inside/intersect the sphere formed from the query point and the furthest corner of the closest octree cell (hope that makes sense!).

If your mesh structure stores faces, edges and vertices seperately - i.e. sharing edges between triangles - you can probably speed up the low-level checks since the distance result for one triangle edge will be the same as for an adjacent triangle edge.

But in any case do a search (e.g. Google distance point mesh) as it's a common thing to want to do.

Ultimately the "efficiency" depends on the algorithm, your implementation, your data and whether you're interested in speed or memory or development time etc - you need to experiment, measure and compromise.