Hierarchical Occlusion Maps
and Occlusion Culling

Hansong Zhang

Hansong Zhang, Effective Occlusion Culling for the Interactive Display of Arbitrary Models, Ph.D. dissertation, Department of Computer Science, University of North Carolina at Chapel Hill, July 1998 (PDF).


Abstract. As an advanced form of visibility culling, occlusion culling detects hidden objects and prevents them from being rendered. An occlusion-culling algorithm that can effectively accelerate interactive graphics must simultaneously satisfy the following criteria:

Based on proper problem decomposition and efficient representations of cumulative occlusion, this dissertation presents algorithms that satisfy all three of the criteria listed above. Occlusion culling is decomposed into two subproblems -- in order for an object to be occluded by the occluders, its screen-space projection must be inside the cumulative projection of the occluders, and it must not occlude any visible parts of the occluders. These two necessary conditions are verified by the overlap tests and the depth tests, respectively. The cumulative projection and the depth of the occluders are represented separately to support these tests.

Hierarchical occlusion maps represent the cumulative projection to multiple resolutions. The overlap tests are performed hierarchically through the pyramid. The multi-resolution representation supports such unique features as aggressive approximate culling (i.e. culling away barely-visible objects), and leads to the concept of levels of visibility.

Two depth representations, the depth estimation buffer and the no-background Z-buffer, have been developed to store the depth information for the occluders. The former conservatively estimates the far boundary of the occluders; the latter is derived from a conventional Z-buffer and captures the near boundary.

A framework for a two-pass variation of our algorithms is presented. Based on the framework, a system has been implemented on current graphics workstations. Testing of the system on a variety of models (from 300,000 to 15 million polygons) has demonstrated the effectiveness of our algorithms for the interactive display of arbitrary models.

Hansong Zhang