Browse Theses

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: (1) Generality. It should be applicable to arbitrary models, not limited to architectural models or models with many large, polygonal occluders. (2) Significant Speed-up. It should not only be able to cull away large portions of a model, but do so fast enough to accelerate rendering. (3) Portability and Ease of Implementation. It should contain as few assumptions as possible on special hardware support. It must also be robust (i.e. insensitive to floating-point errors).

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 sub-problems—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.