Contents  View frustum  culling  Cell-based  occlusion culling  PVS-based  occlusion culling  Other forms of  occlusion culling  Contribution culling  Printable version

Efficient algorithms for determining the visible parts of 3D environments are a key to visualizing complex scenes at interactive rates. Visibility culling algorithms reduce the number of polygons sent down the rendering pipeline based on the simple principle that if something is not seen, it does not have to be drawn. In the following I detail the underlying concepts of the major visibility culling algorithms in use today. We will cover view frustum culling, occlusion culling and contribution culling and finally discuss what else can be used in environments in which this alone is not enough.

View frustum culling

Perhaps the most obvious form of culling is view frustum culling, which is based on the fact that only the objects in the current view volume must be drawn. View volume is usually defined by six planes, namely the front, back, left, right, top, and bottom clipping planes, which together form a cut pyramid. Front and back clipping planes may be defined to lie at the viewer point and infinity, respectively. If a polygon is entirely outside the pyramid, it cannot be visible and can be discarded. If it is partially inside, it is clipped to the planes so that its outside parts are removed.

In the naive version of this algorithm, every object in the world is tested against the six planes. This leads to an asymptotic complexity of O(n) (for an introduction to asymptotic notation, see [CLR90]) if reasonable assumptions hold, meaning that the running speed of the algorithm scales linearly with scene object count. Fortunately, we can do much better than this by hierarchically subdividing space into smaller chunks, and tagging which objects belong to which chunks. A popular way to do this is called the octree. Octree is a hierarchy of axially aligned boxes in which every box is always subdivided to 8 smaller subboxes (i.e. the box is split along every axis) until some criterion to terminate the subdivision process is met. A good choice for the criterion is to stop subdivision when an octree node contains less than a predefined amount of objects. Densely occupied areas can thus have small nodes, whereas predominantly empty areas can be covered with just one big box.

This kind of regular space subdivision leads to hierarchical view frustum culling and logarithmic asymptotic time complexity. The octree is traversed top-down; immediately when a box is totally outside the view pyramid, we can discard all of its children, as they are contained within the parent. Otherwise the recursion continues to the children. Further, as can be immediately seen, octrees can be used for other things, such as speeding up collision queries.

Back-face culling

This primitive form of culling is based on the observation that if all objects in the world are closed, then the polygons which don't face the viewer cannot be seen. This directly translates to the vector angle between the direction where the viewer is facing and the normal of the polygon: if the angle is more than 90 degrees, the polygon can be discarded. Back-face culling is usually automatically performed by the rendering API (Direct3D, OpenGL) and it can be expected to cull roughly half of the polygons inside the viewing frustum.

Next : Cell-based occlusion culling