An octree is a way of subdividing 3D space, otherwise known as space partitioning.  It allows you to only draw the part of your world/level/scene that is in your frustum (camera's view).  It can also be used for collision detection.  Let me give you an example of why space partition is necessary.  Assume you created a world for your game and it has over 100, 000 polygons to draw.  If you did a loop and passed in every one of those polygons, on top of your characters polygons per frame your frame rate would come to a crawl.  If you have a nice Geforce card it might not be as horrible, but you just restricted anyone from viewing your game that doesn't have a $300+ graphics card.  Sometimes, even though you have a really nice graphics card, the part that slows it down a considerable amount is the loop that you use to pass in that data.  Wouldn't it be great if there was a way to only render the polygons that the camera was looking at?  This is the beauty of an octree.  It allows you to quickly find the polygons that you are in your view and only draw them.

An octree works in cubes.  Initially, the octree starts with a root node that has an axis aligned cube surrounding the entire world, level or scene.  So, imagine an invisible cube around your whole world (Figure 1.1). 

Figure 1.1

So this root node now stores all the vertices in the world.  Currently, this wouldn't do us much good because it will draw the whole thing.  We want to subdivide this node into 8 parts (hence the word octree).    Once we subdivide there should be 8 cubes inside of the original root node's cube.  That means 4 cubes on top and 4 on the bottom.  Take a look at Figure 1.2.  Keep in mind the yellow lines outlining each node would not be there.  The lines were added in to get a visual idea of what is going on.

Figure 1.2

We have just divided the world into 8 parts with just 1 subdivision.  Can you imagine how effective this would be if we had 2, 3 or 4 subdivisions?  Well, now what?  We subdivided the world, but what do we do with this?  Where does the speed come from that I mentioned?  Let's say that the camera is in the middle of the world looking towards the back right corner (Figure 1.3).  If you look at the lines you will notice that we are only looking at 4 of the 8 nodes in the octree.  These nodes include the 2 back top and bottom nodes.  This means we would only need to draw the vertices stored in those nodes. 
 

Figure 1.3

How do we do check which nodes are in our view?  This is pretty easy if you have frustum culling.  You can get the dimensions of your frustum and then check each cube if it intersects or is inside of your viewing frustum.  There is a frustum culling tutorial at www.GameTutorials.com for more reference.  If a cube intersects the frustum, we then draw the vertices that are assigned to that node.  Basically, in the example above we just cut the amount we need to draw down by 50 %.  Remember, this was just 1 subdivision of our world.  The more subdivisions the more accuracy we will achieve (to a point).  Of course we don't want too many nodes because it could slow us down a bit with all that recursion.  Is this starting to make sense?  Let's subdivide yet another level.  Take a look at Figure 1.4.

Figure 1.4

You'll notice something different about Figure 1.4 from the last subdivision.  This level of subdivision didn't create 8 cubes inside of each of the original 8 cubes.  The top and bottom parts of the original 8 nodes aren't subdivided.  This is where we get into the nitty gritties of the octree creation process.  You always try to subdivide a node into 8 more nodes, but if there are no triangles stored in that area, we disregard that node and don't allocate any memory for it.  The further we subdivide, the more the nodes shape the original world.  If we went down another level of subdivision the cubes would form a closer resemblance to the scene.  To further demonstrate this, let's take a look at Figure 1.5.  There are 2 spheres in the scene, but on completely opposite sides.  Notice that in the first subdivision (Left) it splits the world into only 2 nodes, not 8.  This is because the spheres only reside in 2 of the nodes.  If we subdivide 2 more times (Right) it more closely forms over the spheres.  This shows that nodes are only created where they need to be.  A node will not be created if there is no triangles occupying it's space.
 

                        Figure 1.5

Now that we understand how the subdivision works, we need to know how to stop it so it doesn't recurse forever.  There are a few ways which we can do this.  1) We could stop subdividing the current node if it has a triangle count that is less than a max triangle count that we define.  Say for instance, we chose 100 for the max.  That means that before we subdivide the node, it will check to see if the total amount of triangles it has contained in it's area is less than or equal to the max triangle count that we decided.  If it is less than or equal to the max, then we stop subdividing and assign all those triangles to that node.  Note that we never assign any triangles to a node unless it's the end node.  If we subdivide a node we do not store the triangles in that node, but in it's children node, or their children's nodes, or even their children, etc...  This will make more sense when we go over how we draw the octree.  2) Another way to check if we want to stop subdividing is if we subdivide past a certain level of subdivision.  We could create a max subdivision level like 10, and if we recurse above that number then we stop and assign the vertices in the cube's area to that node.  When I saw "above that number" I mean 11 levels of subdivision.  3) The last check we can perform is if the nodes exceed a max node variable.  Let's say we set this constant variable to 500.  Every time we create a node we increment the current nodes created variable, then before we create another node we check if our current node count is less than or equal to the max node count.  If we get to 501 nodes in our octree then we should not subdivide that node, but assign it's current vertices to it.  I personally use the 1st and 3rd method, but it's a good idea to start with the 1st and 2cnd method so you can test the different levels of subdivision visually and manually.

Once the octree is created we can then draw the nodes which are in our view.  The cubes don't have to be all the way inside our view, just a little bit.  That is why we want to make our triangle count in each node somewhat small so if we have a little corner of a node in our frustum it won't draw thousands of triangles.  To draw the octree we start at the root node.  We have a center point stored for each node and a width.  This is perfect to pass into a function like so:

// This function takes the center point of the cube (x, y, z) and it's size (width / 2)
bool CubeInFrustum( float x, float y, float z, float size );

This will return a true or false, depending on if the cube is in the frustum (Once again refer to the frustum tutorial at www.GameTutorials.com for frustum source code).  If the cube is in the frustum them we check all of it's nodes to see if they are in the frustum, otherwise we ignore that whole branch in the tree.  Once we get to a node that is in the frustum but does not have any nodes under it, we want to draw the vertices stored in that end node.  Remember, only the end nodes have vertices stored in them.  Take a look at Figure 1.6 to see an example run through of the octree.  The nodes that are shaded are the ones that were in the frustum.  The white cubes are the ones that are not in the frustum.  This just shows the hierarchy of 2 levels of subdivision.

Figure 1.6

An octree isn't just for rendering, but can be used for collision detection as well.  Since collision detection varies from game to game, you will want to pick your own algorithm for checking if your character or object collided with the world.  Here are a few examples on how you could check for this:  1) You will want to create a function that allows you to pass in a point in 3D space to your octree and return the vertices that are found around that point.  The point that you would pass in could be the center point of your character or object.  This alone might work some times, but what if the point is right near the edge of one of the nodes?  Your character or object could be colliding with vertices that are in another node.  To solve this problem you could do a couple things.  You could pass in either a radius or bounding box of the character/object and then check if that radius or bounding box (easier with a cube) collides with another of the surrounding nodes.  This would all depend on the shape of your character/object that you are testing.  The following are some function prototypes for these ideas:

// This function takes the center point of the character/object (x, y, z) and returns the vertices near it
CVector3 *GetVerticesFromPoint( float x, float y, float z );

// This function takes the center point of the character/object (x, y, z) and radius, then returns the vertices in the nodes that collide with it
CVector3 *GetVerticesFromPointAndRadius( float x, float y, float z, float radius );

// This function takes the center point of the character/object (x, y, z) and cube size, then returns the vertices in the nodes that collide with it
CVector3 *GetVerticesFromPointAndCube( float x, float y, float z,  float size );

I am sure you can think of more optimal ways to speed these checks up, but this should get you started on the basics.  Once you get the vertices that are in that area of your character/object you can do your more intense calculations.  Once again, when it comes to collision it's totally how your game works.

This tutorial should give you enough information to get started creating your own octree.  There is also a code tutorial that is associated with this document.  If it is not you can find it at www.GameTutorials.com.  I hope this helps someone struggling with these advanced concepts.  Good luck!

Ben Humphrey (DigiBen)
Game Programmer
DigiBen@GameTutorials.com
Co-Web Host of www.GameTutorials.com