1
$\begingroup$

I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest neighbor problems for points and triangles, but never meshes as a whole collective.

So, in essence given a point P find the nearest mesh M to the given point P from a collection of meshes (some sort of query structure so this can be done over and over again), where the nearest neighbor mesh M is defined as the shortest Euclidean distance in R3 between the point P and the nearest point on a triangle in the mesh M. I was thinking maybe some sort of generalized voronoi diagram where each cell is associated to a list of meshes, but I start thinking about concavity of meshes and intersecting meshes and the point P inside of closed meshes and the point P inside of intersecting closed meshes and even the all the previous cases with open meshes then I am lost. Is there any such known structure for this? Any help would be appreciated! Thanks

$\endgroup$
1
  • $\begingroup$ Is decomposing the mesh into convex subsets an option? I believe that's a common approach. $\endgroup$
    – Pseudonym
    Jun 22, 2022 at 6:41

1 Answer 1

2
$\begingroup$

It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle is a part of, and that will be the nearest mesh.

$\endgroup$
1
  • $\begingroup$ This is probably an optimal approach. I don't see how knowing that the triangles are organized in meshes could be exploited to speed up the search. $\endgroup$ Jun 22, 2022 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.