Hierarchical Frustum Culling
The particular implementation of frustum culling I did was Hierarchical Frustum Culling with plane caching. This technique has become one of my favorites for doing frustum culling with static objects, since it exhibits a really nice performance. The basic idea is to build an AABB tree, where the root is an AABB surrounding the entire scene and the children split up the parent into smaller pieces. The basic algorithm then goes: test if an AABB is all inside, all outside, or intersecting the frustum. If it’s all inside, draw all the children. If it’s all outside, don’t bother traversing it anymore. If it’s intersecting, we have to check to recursively do the same test for all the children AABBs. Where plane caching comes in is absolutely magical. A maximum of 6 plane tests are needed to determine if an AABB is within a frustum. However, when doing a plane test with plane P, if we find an AABB to be all outside then we can cache plane P so that next time we run it we start with P. This caching mechanism works off the basis of temporal coherence, or in other words if something is off to the right, more than likely the next frame it will continue to be off to the right. One interesting result is that if you look away entirely from the scene, it takes only one plane test to throw everything out (of course… how interesting of a game would that be :P).