Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
I think he knows that. I believe the confusion is about how to handle a volume that doesn't fit nicely into a subdivision. –  ClassicThunder Mar 15 '12 at 18:15
2  
I mention that "If an object does not fit inside the bounds, it must be stored one layer up". And it also sounded like the OP was a little confused as to how Octrees worked in general, based on his second sentence. –  John McDonald Mar 15 '12 at 18:17
    
Doesn't that violate the fundamental constraint of octrees, that there are only seven or less in each node? –  DeadMG Mar 15 '12 at 23:50
    
I mean, if I had N objects which lay along the boundary, then I'd be looking at O(N) checks to check against each of them. –  DeadMG Mar 15 '12 at 23:56
    
@DeadMG, "Oct" as in Eight (Octagon, Octane, etc). When the root node splits, it will have 8 children: North East Up, North East Down, NWU, NWD, SEU, SED, SWU & SWD for a total of 9 nodes incl. the root. If one of these child nodes splits, that node will also have 8 sub-nodes, one for each quadrant like before, making a total of 8+8+1 = 17 nodes. If all of your objects fit right on the root node's boundary and do not fit inside any of the 8 quadrants, yes, it will be O(N) and you will have to check against every object and you will not be able to save any compares, in fact it will prob cost. –  John McDonald Mar 16 '12 at 2:40
show 2 more comments

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.