Tree of 3d bounding boxes

[Sylvain Bougerel]

On Tue, Sep 30, 2008 at 5:12 PM, Moritz Moeller
<libkdtree at virtualritz.com> wrote:
> Dear kd-tree huggers. :)
>
> I used KD trees often in recent years but always with 3d points.
> Now I need to work with 3d bounding boxes for the 1st time.
>
> I'm a little bit lost on how to do that myself with something like
> libkdtree++.
> Does anyone have any pointers or a simple example to share?
> Could I e.g. just treat 3d bounding boxes as 6-dimensional points?

Yes! You can!

However range searches have to be treated very carefully. You need to
swap the ranges coordinates to perform a search of bounding box.
However you will not be able to find intersecting bounding boxes
without modifying a bit the algorithm of range search. So you have to
tell me what kind of operation you wanna do with the KD-tree.

You can also find cool thing like: which the box who is the closest to
a given box in terms of shape and position.

There is a hint on how to do this on wikipedia itself:
http://en.wikipedia.org/wiki/Kd-tree#Variations


>
> Basically, what I'm after is a tree of 3d bounding boxes, not points.
>
> The tree should also be balanced so that splitting planes intersect as
> few such boxes as possible, i.e. a box should ideally always be enclosed
> by a single cell, not intersect multiple cells.
>

The tree is rebalanced when running the `optimize()' method. You will
ALWAYS get a box ideally enclosed, because the boxes are forming the
cells. The reason for this is: the kd-tree algorithm we are using is
not an indexing tree: i.e. it stores the values at every node in the
tree, not just the leaves.

> Is libkdtree++ even the right lib for this sort of problem?

Well, I heard that n-dimensional interval trees are better if you look
for replying the kind of questions: I want all the boxes that
intersect this box. It's very useful if you try to do scene clipping,
or collision detection. They can be build from kd-trees or
range-trees.

Ideally your Kd-tree will answer quickly the 2 following question: Who
is fully included in the range [a, b], who is closest to a.

Once again, you have to tell us what kind of operation you wanna do
with the tree.

>
> Heaps sorry about asking such n00b questions. :|
>

No prob, I'm a n00b too in plenty of domains... Sometime I wonder if I
even know anything at all.