1
$\begingroup$

I'm searching for an efficient data structure and algorithm to compute the minimum distance between a ray and a set of meshes in 3D.

What I expect as a result are the coordinates of the nearest point on the nearest mesh.

I'm interested in the general case where the (infinite) ray is not intersecting with any mesh, but I'd expect if it's actually intersecting to get as a result the nearest intersecting point.

For efficiency purpose, I'm willing to set up some accelerating data structure with the list of meshes (and to simplify / decompose those as convex hulls if this is an algorithm expectation), instead of iterating on meshes and their components.

Improve this question
$\endgroup$
4
  • $\begingroup$ Hint: you might want to consider bounding spheres around every edge of every mesh and build a hierarchy of bounding spheres. Then during a search in this hierarchy, when you have found a sphere at a certain maximum distance from the ray, you can ignore any sphere in the hierarchy with a minimum distance larger than that. $\endgroup$
    – user1703
    Sep 3 at 15:16
  • $\begingroup$ @YvesDaoust have in mind, that finding the closest bounding sphere does not meaning finding the closest object... A ray can hit the bounding sphere of object1 and miss the bounding sphere of object2 while a face of object2 is closer to the ray than all faces of object1... $\endgroup$
    – Thomas
    Sep 4 at 12:17
  • $\begingroup$ @Thomas: what do you call closer ? $\endgroup$
    – user1703
    Sep 4 at 12:36
  • $\begingroup$ with closer I mean the minimum distance of a face (triangle) and the line (ray) $\endgroup$
    – Thomas
    Sep 4 at 13:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.