Conservative Visibility Preprocessing
using Extended Projections

Visualisation of very complex environments can be significantly accelerated using occlusion culling. In this paper we present a visibility preprocessing method which efficiently computes potentially visible geometry for volumetric viewing cells. We introduce novel extended projection operators, which permits efficient occlusion culling with respect to all viewpoints within a cell, and takes into account the combined occlusion effect of multiple occluders. We use extended projection of occluders onto a set of projection planes to create extended occlusion maps; we show how to efficiently test occludees against these occlusion maps to determine occlusion with respect to the entire cell. We also present an improved projection operator for certain specific but important configurations. An important advantage of our approach is that we can re-project extended projections onto a series of projection planes (via an occlusion sweep), and thus accumulate occlusion information from multiple blockers. This new approach allows the creation of effective occlusion maps for previously hard-to-treat scenes such as leaves of trees in a forest. Graphics hardware is used to accelerate both the extended projection and reprojection operations. We present a complete implementation of our preprocessing algorithm demonstrating significant speedup with respect to view-frustum culling only, without the computational overhead of on-line occlusion culling.

IMPORTANT UPDATE (07/13/2000)

Well after the completion of the camera-ready version of our paper, the following closely related paper by H. L. Lim:
Toward a Fuzzy Hidden Surface Algorithm, Hong Lip Lim Computer Graphics International, Tokyo, 1992
was brought to our attention. In this paper, H. L. Lim uses concepts from AI and names the technique fuzzy projections because extended projections can be seen as the 1-cut of a fuzzy set. Make sure you check it out, since it also contains alternative techniques for the computation of extended projections.

Additionally, note that H. L. Lim has a patent on his fuzzy projection technique (USA patent 5914721, Japanese, European and Canadian patent pending). Third parties willing to use our extended projection technique should check for possible patent infringement.

The main differences to our paper are as follows:

• We use projection planes at a finite distance from the volumetric cell instead of a projection plane at infinity (direction space) which allows us to treat umbras of finite extent.
• We define the improved extended projection which improves the technique for convex and planar blockers.
• The computation of the extended projections is different
• We use conservative rasterization
• We define the reprojection operator
• We define the occlusion sweep
• We present a complete occlusion culling system with adaptive hierarchical computation.

• A discussion of the connection with fuzzy logic and AI
• An efficient technique for the projection of concave meshes

City, Forest

updated version of this page

@article{Durand:2000:CVP,
        author = {Fr\'edo Durand and George Drettakis and Jo\"elle Thollot and Claude Puech},
        title = {Conservative Visibility Preprocessing using Extended Projections},
        journal = {Proceedings of SIGGRAPH 2000},
        series = {Computer Graphics Proceedings, Annual Conference Series},
        year = {July 2000},
        editor = {Kurt Akeley},
        publisher = {Addison Wesley},
        pages = {},
        note = {Held in New Orleans, Louisiana.},
        keywords = {Occlusion culling, visibility determination, PVS},
     }

See also the recent papers on the subject

Conservative Volumetric Visibility with Occluder Fusion G. Schaufler, J. Dorsey, X. Decoret, and F. X. Sillion, SIGGRAPH 2000.

Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs Peter Wonka, Michael Wimmer, Dieter Schmalstieg, EGRW 2000

Virtual Occluders: An Efficient Intermediate PVS representation Vladlen Koltun, Yiorgos Chrysanthou and Daniel Cohen-Or, EGRW'2000

iMAGIS is a joint research project of CNRS/INRIA/UJF/INPG.
iMAGIS/GRAVIR, BP 53, F-38041 Grenoble cedex 9 France.
http://www-imagis.imag.fr
http://graphics.lcs.mit.edu/~fredo/sig2000