Frustum Culling

Rendering sets of several thousand (20,000 +) triangles thirty times a second can slow the rendering process down, so it's important to have a fast and efficient way of culling items that don't need to be drawn.

Trivially, we can ignore anything that is behind the camera. While this helps, there are still items forward of the camera that are not visible, items that are too high above the camera or too far below for instance.

The viewing volume described by a rectangular screen is in the shape of a rectangular based frustum (that is, a pyramid with the top cut off). By drawing only items that appear in this volume, we can render scenes in a fraction of the time. Initially, culling can be constrained to items that do not intersect the viewing volume, although this can be extended to handle individual triangles for elements which do. The diagram below shows the camera and view frustum (intersecting the ground plane) and three objects. The yellow is outside the frustum, and is culled. The blue is entirely within and is drawn in whole. The green is partially within, so further culling is used to draw only the relevant triangles.

The fastest way of culling an object is by using a bounding sphere, which is calculated as a centre and a radius, both of which can be found using the maximum and minimum values for vertex data in each dimension. We need only test the distance of the centre of the element to be drawn from each of the six planes which make up the frustum. If this point is behind any of the planes, and further than the radius, we can cull the object. Using the Hessian normal form of plane notation for the frustum's six planes, we can quickly calculate whether a sphere is behind a plane using the inequality

n.v - p < -r

where n is the plane normal, v the centre of the sphere to be tested, r the radius of the sphere and p the distance of the plane to the origin. If the above inequality is true, the sphere is behind the plane. If the inequality is false for all six planes, the sphere is within the frustum (this includes cases where the sphere intersects the frustum)