Complex models with high depth complexity render many pixels which are ultimately discarded during depth testing. Transforming vertices and rasterizing primitives which are occluded by other polygons reduces the frame rate of the application while adding nothing to the visual quality of the image. Occlusion culling algorithms attempt to identify such non-visible polygons and discard them before they are sent to the rendering pipeline [20,110]. Occlusion culling algorithms are a form of visible surface determination algorithms that attempt to resolve visible (or non-visible surfaces) at larger granularity than pixel-by-pixel testing.
A simple example of an occlusion culling algorithm is backface culling. The surfaces of a closed object which are pointing away from the viewer will be occluded by the surfaces pointing towards the viewer, so there is no need to draw them. Many occlusion culling algorithms operate in object space [20,63] and there is little that can be done with the standard OpenGL pipeline to accelerate such operations. However, Zhang et. al. [109] describe an algorithm which computes a hierarchy of image-space occlusion maps to use in testing whether polygons comprising the scene are visible.
An occlusion map is a 2D array of values, where each value measures the opacity of the image plane at that point. An occlusion map corresponding to a set of geometry is generated by rendering the geometry with the polygon faces colored white. The occlusion map is view dependent. In Zhang's algorithm the occlusion map is generated from a target set of occluders. The occlusion map is accompanied by a depth estimation buffer that provides a conservative estimate of the maximum depth value of a set of occluders at each pixel. Together the occlusion map and depth estimation buffer are used to determine whether a candidate object is occluded. A bounding volume for the candidate object is projected onto the same image plane as the occlusion map and the resulting projection is compared against the occlusion map to determine whether the occluders overlap the portion of the image where the object would be rendered. If the object is determined to be overlapped by the occluders, the depth estimation buffer is tested to determine whether the candidate object is behind the occluder geometry. A pyramidal hierarchy of occlusion maps (similar to a mipmap hierarchy) can be constructed to accelerate the initial overlap tests.