Jump to content
  • Advertisement
Sign in to follow this  
Katachi

Find nearest triangle to a point (not ray)

This topic is 2133 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,

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
Thanks
Sam Edited by Katachi

Share this post


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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!