Lee, Andrew Hickinbottom (3D) Tank Girl, Pedro Conti (2D)

View Full Version : kD Tree box (aka. value-range) insertion

07-13-2005, 07:26 PM
I'm currently working on a way to speed up the rebuild of spatial data structures (like kD-Tree or Bounding Volume Hierarchies) for dynamic scenes. So far so good, found nearly no papers on that theme (if anyone knows some ...), and I've already got one very simple question for the static case:

How do you insert a box (3D axis aligned in this case) into an *existing* kD-Tree?

All I found were explanations for points, which is rather simple, as points will never be in two or more halfspaces. The next thing is, that nearly everyone seems to build a kD-Tree out of a set of exisiting points which means, that I would have to "flatten" my existing tree and rebuild the whole thing when inserting a new object - which is exactly what I don't want to do.
The problem of splitting a box will already occur when building a tree from scratch (out of a set of objects) as there are cases where you can never find a non-splitting plane between objects. (think of a square where there is one split at each wall, creating four boxes, meaning you always have a box at the other side of a split).

So, IMHO there have to be papers around explaining ways to do it.
I would just split my bounding volume into two halfes and go down on both sides of the node in case of an overlap but maybe there are better ways of doing this.

Note (added after reading a flipcode article):
You don't really have to split the volume, as you can safely go on with the complete volume (the "other side" will always stay outside the current halfspace).

CGTalk Moderation
07-13-2005, 07:26 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.