Mesh rendering using Octree algorithm

Question

Hi Guys, I'm the founder of SceneMax - a 3D scripting language since 2005. I want to add a scene rendering using one mesh object built with 3d package like 3ds max and splited by octree algorithm for optimized performance. Do you know where can i find such algorithm which takes a mesh .X file,split it to nodes (octree) and knows how to render it? I want to add it to my engine. The engine is open source (google for SceneMax if you're interested).

P.s. I'm using C++

Thanks, Adi

Answer 1

There are several variations, but when building an octree, one approach is this:

1. Start with one node (ie. a cube) encompassing your entire scene or object being partitioned.
2. For each element in your scene/object (eg. a mesh, or a poly, or whatever granularity you're working to):
   1. Check if that element fits completely inside the node.
   2. If yes, subdivide the node into eight children, then recursively do Step 2 for each child.
   3. If no, then continue to the next node until there are no nodes left.
   4. Add the element to the smallest node that can contain it.

It's also common to stop recursion based on some heuristic, like if the size of the nodes or the number of elements within the node is smaller than a certain threshold.

See this Flipcode tutorial for some more details about building the octree.

Once you have the octree, there are several approaches you can take to render it. The basic idea is that if you can't "see" a node, then you can't see its children either, so everything inside that node (and its children) don't need to be rendered.

Frustum culling is easy to implement, and does the "can you see it?" test using your view projection's frustum. Gamedev.net has an article discussing frustum culling and some other approaches.

You can also go further and implement occlusion culling after frustum culling, which will let you skip rendering any nodes which are covered up by nodes in front of them, using the z-buffer to determine if a node is hidden. This involves being able to traverse your octree nodes from closest to furthest. This technique is discussed in this Gamasutra article.