Bounding boxes in octrees

Question

I've seen that octrees are often used for things like frustum culling and collision detection in 3D. But I'm just not sure how the algorithm works at all. Surely the whole principle of the octree breaks when you try to use bounding boxes, because any given box could be stored in one node but actually overlap the space represented by another node. In addition, I'm not sure how this can possibly work for looking up bounding boxes rather than points, because again, you could be stuck looking up into virtually all the nodes, defeating the purpose.

So how on earth do octrees cope with bounding boxes?

Answer 1

An Octree (3D) uses the same concepts as a Quadtree (2D). If you read and understand the wikipedia article on Quadtrees, you should be able to apply the same concepts into 3D.

Both of these trees allow you to use area-based lookups that can greatly reduce the number of comparisons required to figure out what objects are in a certain area. This can be useful for vis-culling, or even for collisions, depending on your game.

The basic concept is that the world-space is divided up into "buckets": squares for 2D or cubes for 3D. With an empty world, you start with a single square or cube bucket that covers the entire world. As you add objects to the world, you start at the root node and work your way into the tree based on the location and size of the object. If the destination bucket reaches capacity, you subdivide it by splitting squares into 4 smaller squares (Quadtree), or splitting cubes into 8 smaller cubes (Octree). Each object you add to world is only inserted as deep in the tree as it can physically fit completely inside the bucket's bounds. If an object does not fit inside the bounds of the current bucket, you must move the object to the smallest parent bucket that it does completely fit inside. Using trees like this allows you quickly disregard massive chunks of your world with only a few bound checks, instead of comparing against each object in your world.

Note that using either a Quadtree or Octree is overkill if you do not have a lot of objects in your world. There are also open-source solutions to both.

Answer 2

n-trees are the most famous but not the only spatial partitioning system available. There are many, many others. A bit more information about the data you have would go a long way toward finding the best choice. Do your boxes change size, or move around? How big are they? How many are there? Do you have a lot of insertions / removals?