Basic Octree

Last modified: 06 Feb 2017

Here’a a basic implementation of Octree using DirectX.

Download demo and source

My demo recursively creates the octree based from 2 critierias - the maximum number of polygons and the bounding box size extent allowed on each node while making sure they are grouped by attributes (materials) when they are rendered.

In a nutshell, the octree creation process goes like this in my code:

  1. Extract and group all the triangle indices and attributes together from a D3DXMESH instance.

  2. For each group, create an index buffer.

  3. Create one large vertex buffer to hold the entire mesh, basically we will stream from here. We will simply use the indices from the group’s index buffer to index the vertices that only needs to be rendered.

  4. We now go ahead and recursively create the octree adding nodes to it when the 2 critierias I mentioned above are satisfied.

The octree truly shines when you start rendering your scene. When a parent node is not visible, then all its child nodes are automatically culled as well - you don’t need to go through them!

Then the rendering process goes like this:

  1. Lock all the index buffers - we will fill it up with the indices of the visible faces.

  2. Recursively find out which nodes are visible using a camera frustum bounding box check. When a node is not visible, we simply leave that out including all its child nodes.

    When a node is visible, we step through until we find a leaf node (bottom most) then we just copy those face indices to our group’s index buffer - counting along the way how many faces we’re copying.

  3. When all our groups index buffers are filled up with all the visible faces, we simply loop through each one of them, unlocking the index buffer (it was locked on step.. 1) and rendering each with a call to DrawIndexedPrimitive(…).