About Octrees Usage

Question

I'm studying about Octrees since I've read they're used to organize my elements in space, but I couldn't find any practical example so I'm kinda lost as to their use.

From what I could understand, I'll divide my "space" in 8 cubes, and each cube will divide it's own space in another 8 cubes and so on until my defined "depth" is reached. This is what I could understand from octrees, so now about their uses:

1. Are they done so the check of each cube's with the camera frustum is easier to compute?
2. If I have a open world scenario, do I put all the vertexes in it? And related:
3. How often do they get updated? Everytime I insert a new game element, don't I have to re-do all the calculations for the current node and it's subnodes?

If you can share any resource on BSPs/Octrees and their practical usages (not just the concept, which I've been reading a lot), please share!

Answer 1

1. The point is that once you cull one octree node, you can stop culling and discard all of its children therein. Consider a binary search for example. Once you know that your key isn't in one part of the array, you can stop searching that part completely. The check itself isn't easier to compute, it just decreases the number of calls you may have to make (as long as you don't use silly depths or in other words use too many nodes for too few objects)

2. I'm not sure what you mean by vertexes. I'm assuming you mean models/entities, in which case, the answer is maybe. In the end you might have multiple systems of subdividing space and multiple culling systems in order to maximise performance. Generally though, if we're talking about say plain scene objects (e.g renderable vehicle, player characters), the answer is yes. It must be stressed though, you won't be adding individual vertexes, you'll be adding the bounding box belonging to the entity that contains the vertexes. You will still end up ultimately culling the specific entity you add to the tree if it ends up in the visible candidate list, it just allows you to say, if you are at one end of the map, eliminate dozens or even hundreds of entities with a single cull check.

3. It depends on what you mean by 'update'. If you mean 'cull', thereby updating the list of visible candidates (objects that may be visible) then yes, otherwise you might run into a situation where an object that should be on the screen isn't rendered.

   When you refer to calculations, what are you referring to? The insertion of a new element will generally involve recursion, beginning with your root node, adding it to nodes that contain it. (strictly speaking this can be a bit more complex depending on how you produce your visible list - you don't want duplicates) The only calculations you will have to perform (not may) will be the bounding box intersection test with each node you recurse for.

Here is some basic pseudo-code (just to give you an idea, not necessarily accurate)

void RecurseAddBoundsToOctree(TBoundingBox boundsToAdd, TOctreeNode node)
{
    if node == NULL
        return

    for each child
        RecurseOctree(currentChild); 

    //Note: Above we may want to prevent multiple children from containing the
    //same bounding box (you could return a boolean to indicate whether it was added)

    if BoundingBoxIntersect(boundsToAdd, node.BoundingBox)
        node.AddBoundingBox(boundsToAdd)
}