Jump to content
  • Advertisement
Sign in to follow this  

Find nearest triangle to a point (not ray)

This topic is 2222 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


I am looking for an acceleration structure that allows to efficiently find the nearest triangle to a specific point coordinate. All I can find is dealing with shooting a ray and find an according triangle to that (kdtrees, octrees, bvh...) but I couldn't find anything on finding the nearest triangle to a point coordinate.

So how to find the nearest triangle using a kdtree for example? I am only looking to find the triangle index, so I can do an exact point-triangle distance only on a limited amount of triangles in the vicinity. So it doesn't have to incorporate an exact distance estimate for finding the triangle index (which probably says that I am rather looking for the correct split and search condition in a kd-tree to achieve what I need)

I appreciate your help
Sam Edited by Katachi

Share this post

Link to post
Share on other sites
A KD tree is a good choice. Just recurse down the tree as follows:

  • If the node is a leaf, just scan over the triangles and find the closest one. Return the index of the triangle and the distance to it.
  • If the current node is not a leaf, figure out which side of the split plane that contains the query point, and recurse down that side. You will get the index and distance to the closest triangle in that subtree. Then, check if the distance to the nearest triangle is closer to the query point than the distance between the query point and the split plane. If it is closer, there is no need to recurse down the other side of the KD tree and you can just return. Otherwise, you will need to recurse down the other way too, and return whichever result is closer.

    Hope that was clear enough.

    Keep in mind that the closest point on your mesh could be an edge or a point, and in that case you will have a tie ... this may or may not be a problem depending on what you want to do with the triangle index you get.

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!