search

georust / rstar

R*-tree spatial index for the Rust ecosystem
https://docs.rs/rstar
Apache License 2.0
386 stars 67 forks source link

Question: How to implement intersection on AABB for testing if cluster is in viewport? #90

Open AnachronicNomad opened 2 years ago

AnachronicNomad commented 2 years ago

Hello! I'm using an R*-Tree to hold 3D graphical data, organized as points. I'm trying to figure out how I could determine whether the AABB for a given leaf node in the tree is within view of a camera.

One way I've thought of to define the view would be to approximate the camera view as a Cone, with a central axis along the camera's view direction and sufficient radius to match up with the camera's FOV. However, I can't tell from the documentation how I might implement a Cone geometry as an AABB Envelope in order to perform intersection tests on the R*-Tree data structure.

Another thought that came to mind would be trying ray-based intersections across the tree. However, I don't know how I would approximate the camera's view with so many rays to do intersection tests, using this library.

Does anybody have any thoughts or suggestions?
Thanks so much in advance for any insights!

rmanoka commented 2 years ago

An AABB for a Cone can be constructed if you know the height of the cone; that is a max-distance from the view-port to the points. I'm not sure if it is the most optimal method though.

Another option is to construct a function: Cone::is_intersecting_aabb(aabb: AABB) -> bool that tells if the given cone object is viewing any part of a input aabb. Then, you can implement trait SelectionFunction which will then let you efficiently traverse only the points that are inside the cone.