Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

Question

I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only interested in the design, no coding. I believe I can use the approach of kd-trees assuming that the query line is also axis aligned, say x-axis. Any help will be pretty much appreciated. Thanks in advance

Answer 1

If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $(y,z)$-plane and answer the following question: Given $n$ axis aligned rectangles and a query point $p$, report the rectangles containing $p$.

To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that you start building your segment tree according to the projections of your rectangles on one dimension (say $y$) and instead of having some interval $I$ as a leaf, you replace it with a segment tree storing all projections on the $z$-axis of rectangles whose projection on the $y$-axis contain $I$.

You can then query a point by going down the tree and looking for all rectangles which are potential candidates according to their $y$-coordinates and then check among those which "fit" according to their $z$-coordinates.

This leads to $O(n\log^2(n))$ space used, $O(\log^2(n))$ time per query and $O(n\log^2(n))$ construction time.

Answer 2

Assuming that the query line is long, you could split it into small pieces (let's talk about 'long' and 'small' later). For each segment you calculate the bounding box and then you can query with that bounding box any tree that stores AABBs (R-Trees/BVH, Quadtrees, ....). For each result you will have to check manually whether it really intersects with your query line, but this approach should greatly reduce the number of AABBs you have to check.

So, should you split your line into chunks? If it is axis aligned, then no, because the AABB of the line will be exactly the line itself. If the line is not axis aligned, then it depends on how long it is and how far away it is from being axis aligned. The best way is to try out different segmentation strategies, but a good start may be to mage segment at most 5 times as long as your average AABB. This should give a reasonable balance between having to execute many queries (one for each segment) and the number of false positives returned by each query.