CODEWITHSUNDEEP
c++searchkdtree
Tyson
Tyson

Reputation: 1238

Data structure for finding nearest triangle in 3D

I have a set of triangles, and I want to find the closest triangle to an arbitrary point in space.

A brute force approach is too slow for my liking, so I'm looking into various data structures which could help accelerate the search.

My problem is that the structures I've looked into (rtree, kdtree) use bounding boxes to narrow the search, but there are many cases where nearest bounding boxes do not necessarily correspond to nearest triangles.

Here is one such case:

bbox example

Notice how the blue point is closest to the large bounding box, but closer to the small green triangle. This makes me feel that data structures relying on bounding boxes would result in incorrect search results...unless I'm missing something obvious?

Overall, I'm looking for a lightweight-ish c++ solution (so no CGAL or other beastly packages), or just a point towards the right kind of algorithm I should be looking into.

Thanks!

Upvotes: 1

Views: 1460

Answers (2)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122457

You can use the bounding boxes approach to narrow down the search. All you have to do extra is the following:

  • Find the closest bounding box (lets say it is the big one in your example)
  • Let r be the distance between the point and the closest bounding box and b the size of the bounding box. Find all bounding boxes that are closer than (r+b) from the point.
  • Use brute force to find the closest triangle among the remaining bounding boxes.

Upvotes: 2

Adam
Adam

Reputation: 952

I think you could use Binary Space Partitioning to handle the awkward cases like the one you described more effectively.

Essentially you'd have something similar to a k-d tree, where instead of having axis aligned splits, you could split along an arbitrary plane (commonly based on one of the existing edges in the scene).

The downside is that it will probably be slower to build the tree.

Upvotes: 0

Related Questions