Jump to content
  • Advertisement
Sign in to follow this  
data2

Finding closest point on mesh

This topic is 4372 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!