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
Find nearest triangle to a point (not ray)
A KD tree is a good choice. Just recurse down the tree as follows:
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.
- 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
