Monday, 21 October 2013

Picking code from the Octree

As I begin work on the next game it's nice to revisit some well worn code.  The octree  I wrote for 'Last Chapter of Man' worked well but the implementation meant the tree was kind of top heavy with objects, not ideal but bounding sphere checks are pretty it worked.  Once it was up and running I didn't want to break it mid game unless I had to.  Now though I've gone back and improved it into a loose octree implementation.

Without loose bounds (left) a lot of objects only fit in the root node.
With loose bounds they can filter down (right).

I won't go over the basics of octrees, there's a number of articles available on them. I do want to go over a few parts I personally found confusing though as I found there was a slight gap between the theory and the implementation in a few of areas.  I may well just be stupid, but hopefully others find this a little helpful too.  My confusion stemmed from...

  1. Handling objects that crossed boundaries, i.e. didn't fit within a box.
  2. Pruning of the tree when objects are removed..and related to this
  3. Expanding and collapsing the tree as objects move around.

1) In my implementation, objects are only present in one node of the tree.  If an object wasn't wholly contained within the bounding area it would not filter down.  And I store these objects in a list rather than an array, so octree nodes have an ideal amount of objects they want to hold...but they can happily hold more as needed.

2) When I remove an object, I call that node's parent to try and prune the tree.  And all it does is count how many objects are contained in it's branch, and if it's less than our max we copy all the objects into this parents node clear everything below us.

3) Every time an object moves there are a few checks it makes.  If it no longer fits within it's bounding area we remove it and add it back into the tree from the root.  If it does still fit within the bounding area, we don't just leave it be.  If that node isn't a leaf we also try and filter it further down the tree, so objects are constantly being filtered into the best position for boundary checking.

objects moving and the tree adjusts accordingly.
Only  non-empty nodes are shown.

I'm sure all games require variations on the above, but those where the areas where I was fuzzy on and it took me some head scratching to get working correctly.  With the loose tree version, the boundary checking uses the center point of the sphere against the strict bounding box.  When you do your collision checking you have to check against the loose bounds rather than the strict ones, the loose bounds being twice as large. It means you have to check against more parts of the tree then, but the tree itself is more balanced to compensate.

I've posted the code online and you can download my loose octree implementation and study it for yourself.  I think it's robust and bug free but by all means let me know if you spot an error. I hope it of use to others and I intend to post other small little snippets of code too as this blog continues.