# Find nearest triangle to a point (not ray)

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

## 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)

Thanks
Sam Edited by Katachi

##### 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633663
• Total Posts
3013232
×