Loose Octrees for frustum culling (part 1)
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)
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.
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.
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.
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.
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.
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.
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.
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.