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