Would someone please explain Octree Collisions to me?

I've been reading everything I can find on the subject and I feel like the pieces are just about to fall into place, but I just can't quite get it.

I'm making a space game, where collisions will occur between planets, ships, asteroids, and the sun. Each of these objects can be subdivided into 'chunks', which I have implemented to speed up rendering (the vertices can and will change often at runtime, so I've separated the buffers). These subdivisions also have bounding primitives to test for collision. All of these objects are made of blocks (yeah, it's that kind of game). Blocks can also be tested for rough collisions, though they do not have individual bounding primitives for memory reasons. I think the rough testing seems to be sufficient, though.

So, collision needs to be fairly precise; at block resolution. Some functions rely on two blocks colliding. And, of course, attacking specific blocks is important.

Now what I am struggling with is filtering my collision pairs. As I said, I've read a lot about Octrees, but I'm having trouble applying it to my situation as many tutorials are vague with very little code.

My main issues are:

1. 
   

   Are Octrees recalculated each frame, or are they stored in memory and objects are shuffled into different divisions as they move? Despite all my reading I still am not clear on this... the vagueness of it all has been frustrating.

   
   



2. 
   

   How far do Octrees subdivide? Planets in my game are quite large, while asteroids are smaller. Do I subdivide to the size of the planet, or asteroid (where planet is in multiple divisions)? Or is the limit something else entirely, like number of elements in the division?

   
   


3. 
   

   Should I load objects into the octrees as 'chunks' or in the whole, then break into chunks later? This could be specific to my implementation, I suppose.

   
   

I was going to ask about how big my root needed to be, but I did manage to find this question, and the second answer seems sufficient for me. I'm afraid I don't really get what he means by adding new nodes and doing subdivisions upon adding new objects, probably because I'm confused about whether the tree is maintained in memory or recalculated per-frame.

Answer

If you know the maximum size of your world, I would make your root node that size. It keeps things simple with no resizing.

Recalculating the tree each frame is much simpler than moving things around, but it also would be much more expensive. I suspect prohibitively so. Moving objects within the tree may be more performant, but it still may be very expensive depending on how often your objects move across subdivision boundaries. You may have to completely rebuild subtrees in the worst case if too many objects move into the same subdivision. Personally, I would not use an octree for collision detection between moving objects. Perhaps a simpler space partitioning scheme, or an alternative algorithm would be better, but you should benchmark it as you may not have any performance problems.

For the octrees I have seen, there are two parameters: maxDepth and maxElements. If your current depth is equal to maxDepth or the number of elements left to be inserted is less than or equal to maxElements then you do not subdivide any farther. For an example of octree building code look here. You would have to modify it to use bounding boxes instead of points, which can cause some complications like an object which straddles two (or more) subdivisions.

There is a trade off with maxDepth allowing you to control how much time is spent traversing the tree, and maxElements allowing you to control how many objects you will be processing once you find the appropriate leaf in the tree. If processing an element is cheap you may have a large maxElements and low maxDepth because traversing the tree is more expensive than just processing some extra elements and saves you memory. Conversely, if processing an element is expensive, a high maxDepth and a low maxElements will mean you spend more time traversing the tree and take up more memory but it is worth it because it cuts down on the expensive element processing.

However, with massive differences in size between objects, you may find that having a small maxElements will cause problems in that you may have a very large object beside many small ones. Unless you can split the large object into smaller pieces and insert them separately, you won't be able to split the node into 8 pieces and still have the large object fit into one of the subdivisions.

As to what you should insert into the octree, you need to think about what you will be doing once you get to the leaf in the octree. You will have a list of these things, and you will have to do something to find if/where a collision happens. The octree will help make this list shorter, but you will need to do the actual collision detection with these objects.