Geometry Boost List: Re: [geometry] Non-axis aligned bounding box collision in 3D

Subject: Re: [geometry] Non-axis aligned bounding box collision in 3D
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-03-27 18:46:45

Hi David,

David Sauter wrote:
> Greetings,
>
> I've got a current implementation that works using BG and r-tree but 
> it's using an AABB that completely encompass the query area so I've 
> got a lot of false positives to weed through.  I'm looking for a 
> cleaner way to query a large data set.
>
>  The data set consists of X/Y plane squares of various sizes and at 
> various  coordinates within a known range.  The tricky part is that I 
> need to cull all but those that touch a small square area projected 
> along a non-axis aligned vector.
>
> Is there any way to query the r-tree with a non-axis aligned bounding 
> box?  If not is there a known way to do this query that I'm just 
> overlooking?
>

Currently in BG there is no Oriented Bounding Box concept. Which means 
that it's impossible to run algorithms for OBBs, e.g. to check if they 
intersect or to expand them, etc. This also means that the rtree can't 
use them.

I'd like to understand every aspect of your use-case.

AFAIU you're searching for a spatial index which allows to find values 
intersecting some OBB. But should this index be able to store OBBs as 
well or AABBs (like the one we have right now)? Or maybe to also use 
OBBs for tree nodes?

I assume that you tried to index and search using AABBs and those 
queries return many Values which you must then check again using OBBs? 
Or are you then checking for the intersection of some more detailed 
objects or aren't preforming any additional checks?

Is this some bottleneck in your application? And are you sure that 
storing/using OBBs internally in the spatial index would increase the 
performance? Isn't the use of AABBs and then more detiled check using 
OBBs enough?

I'm asking because I'm not sure about the performance increase. All 
calculations done for OBBs WRT AABBs are more complex. It's possible 
that if you performed a query using AABB and then just check the result 
using more detailed method, e.g. OBBs or some other objects it would be 
faster than in the case of performing all operations for OBBs. The 
spatial index must be created, structure balanced on insertion then 
query performed, all using slower OBBs. It probably all depends on the 
data and how many nodes must be traversed in both cases during the 
query. Do you expect that for you data AABBs will overlap each other a 
lot more than OBBs?

AFAIK OBBs are planned, though I don't know when because there are other 
things which we're working on. You could think about contributing your 
implementation of functionalities required by the rtree to work for 
OBBs. Or maybe there is someone already working on OBBs? Bruno?

So depending on what do you need you could think about the following:
1. For performing the query on an existing implementation of the rtree 
using the OBB
a) The definition of concept and access to data stored in the OBB
b) The implementation of the spatial relation function used in the 
query, e.g. bg::intersects(OBB, AABB)
2. For storing the OBBs in the rtree but using AABBs for the rtree nodes
a) bg::expand(AABB, OBB)
b) probably a specialization of some struct to enable OBBs as Indexables
3. For using OBBs as the bounding objects of nodes of the rtree
a) a few functions used internally by the rtree to calculate some 
metrics used by the balancing algorithms (similar to area and volume)
b) figure out how the packing/bulk loading algorithm should look like 
for OBBs (or just adapt the one for AABBs)
c) ... (see below)
4. For the nearest() query
a) e.g. bg::comparable_distance(Point, OBB)

But this is not the whole truth in the case of 3. From the functional 
point of view a) would be enough. But from a library point of view more 
work should be done. Mainly because the structure using OBBs wouldn't be 
an rtree anymore. We should implement another template/interface using a 
different name, let's say bounding_tree<> which in addition to the Value 
type would take the bounding object type as a parameter. This data 
structure should be able to use any bounding object in the internals 
including:
- AABB
- OBB
- NSphere - this would give us a M-tree (probably?)
- Convex Polygons - this would be a lot slower than the above, but why not?
- boost::variant<...> (any combination of the above) - this would give 
us a BVH-tree

And the rtree<> template should be built on top of bounding_tree<> or 
rather just share some functionalities.

Regards,
Adam