Preamble

This is the first part in a (probably) 2-part article on loose octrees. The illustrations will be in 2D, the code snippets and text will always refer to octrees (and not their 2D variant, the quadtree). Dynamic subdivision is implied. I will also use Axis Aligned Bounding Boxes (AABB’s) as the bounding volume of inserted object, but most algorithms can easily be adapted to use other bounding volumes.

Values of AABB’s are written as ((min.x,min.y,min.z),(max.x,max.y,max.z)

Introduction

An octree is a 3D spatial partitioning structure where every node is always split into 8 subnodes (“octant”) by three axis-aligned planes, usually in the middle of the original node. Each octant has the volume of an AABB. Objects are typically inserted in the smallest octant that contains the entire object.

Octree subdivision

A loose octree differs from the original in the introduction of a second volume, which I call a loose bound of an octant. This volume is a larger AABB with the same center as the original, “strict” bound. Objects are guaranteed to be bounded only by the loose bound, and potentially straddle the strict bound.

Loose Octree subdivision with loose bounds shown in dashed lines

The relationship between the dimensions of the loose and strict bound is “k”, with 1 < k.

We also need to introduce a constraint. If we only guarantee that an object is full contained by the loose bound, we have the possibility that an object is fully contained by more than one node in the same hierarchy. EG we have a root node and we split it once. If we put a tiny object in it, the object could be validly stored in any of the child octants.

All level 1 octants contain the object fully

 

To remove this ambiguity, we will work under the assumption that the centre of an object’s AABB is always inside the strict bound of a octant.

Consequences

No hot spots

The traditional octree has an inherent difficulty dealing with objects that straddle a splitting plane. For example, an object with the following the following AABB ((0.40,0.0,0.0),(0.60,0.1,0.1)) inserted into an octree with bounds ((0,0,0),(1,1,1). Since it straddles a splitting plane of the root node, and can’t be moved further down the hierarchy.

Problematic cases

When we try to do frustum culling using this hierarchy, we can only cull this object by checking it’s own AABB, without any benefit of our octree. This will happen for all objects that straddle a splitting plane of a node that is high up in the hierarchy. We call the regions close to one of these splitting planes the “hot spots’ of the octree, as an object that straddle these planes will have to be checked often, even if they’re small and nowhere near the frustum.

Visualisation of a octree with 5000 objs, 96% with 0.01 < diag < 0.03 and 4% 0.03 < diag < 0.15. A smaller depth is a bigger node. Red == Bad

With loose bounds, this problems disappear naturally. This is probably the most important advantage “going loose” has. Next post, we’ll have some numbers to see how much of a difference this makes.

A much better balanced octree. This will translate into early culling of large groups of objects with less AABB intersection tests overall.

 

Faster insertion code

In a traditional octree implementation, we use the following pseudo code to find the correct octant for an object.

Octant findOctantForBB(AABB BB, Octant)
    if (o is not split)
        return O
 
    foreach child
    if (child.BB.contains(BB))
        return findOctantForObject(BB,child)
 
    //no valid child
    return O

We call this function with the root node of the hierarchy. Even a well optimized implementation will have to do a couple of floating point comparisons when checking which child octant (if any) can contain the object.
With a loose hierarchy, we can do better. Since we know that only the object’s centre is inside the strict bounds, we can calculate the lowest level it can be safely inserted, as well as it’s desired node. 4 integers are enough to uniquely identify a 3D octant inside a hierarchy : the logical x,y,z index of an octant, as well as it’s depth in the hierarchy.

findIdealInsertion(AABB bb, ret x, ret y, ret z, ret depth)
    octantStrictBounds = sceneBB.strictBounds
    depth = 0
 
    while(true)
        octantStrictBounds /= 2
        //worst case: centre of bb is right on the border of the strict bounds
        if(octantStrictBounds * (1-k)/2 < bb/2)
            break
        depth++
 
    //we're off by one
    depth--
    octantStrictBounds *= 2
    //get the index of the node
    x,y,z = (int) bb.centre / octantStrictBounds

Now, we need to recursively descend the hierarchy again, since we’re not sure the octant we’re looking for is actually allocated. If it’s not, we can take an octant higher up, since it’s loose bounds are guaranteed to fully overlap the desired octant’s loose bounds anyway.

octant findBestFittingOctant(AABB objectBB, x,y,z,depth)
    octant = rootOctant
    for (currentDepth = 0; currentDepth != depth; ++currentDepth)
        if (!octant.split)
            return octant
        else
            /*
                We can find the exact child without any comparisons
                For example, we're looking for an octant at depth 2 with x,y,z = (2,1,3)
                This will be a child of the octant at depth 1 with x,y,z = (1,0,1)
 
                We take the convention that childOctants are layed out as:
 
                local index                1D index
                [(0,1,0) (1,1,0)]        [2 3]
                [(0,0,0) (1,0,0)]        [0 1]
                                    =
                [(0,1,0) (1,1,0)]        [6 7]
                [(0,0,0) (1,0,0)]        [4 5]
 
                To find the local index of an octant in the frame of it's direct parent, we have to divide the index by two.
                To find the local index of an octant in the frame of it's  parent x times up, we have to divide the index by 2^x
 
            */
            //this generates the local index of the child octant at (currentDepth - 1)
            currentDepthX = x >> (depth - (currentDepth+1))
            currentDepthY = y >> (depth - (currentDepth+1))
            currentDepthZ = z >> (depth - (currentDepth+1))
            childIndex = cuurentDepthX + currentDepthY << 1 + currentDepthZ << 2
            octant = octant.child[childindex]
 
    //if we make it here, we're at the minimum depth. and we found our octant
    return octant

Which bring the code down to one comparison per level.

Implementation

Next post!