Dynamic Scene Occlusion Culling using Regular Grids

The problem of using visibility culling techniques to accelerate the visualization of large and complex 3D scenes has gained considerable attention of the CG community in the last few years. The relevance of this subject has been mostly attributed to the tremendous growth of processing power the CG community have witnessed in the latest generations of graphics hardware, as well as the advent of cutting-edge technologies such as hardware shader programming. Now we have the power to visualize large scenes composed by several millions of polygons with interactive rates in ordinary applications such as computer games. In addition, CG users and developers have virtually the chance to display such scenes in real-time with complex shaders, thus improving rendering quality. Visibility culling algorithms play a key role to turn this latent chance into reality, as these techniques may discard the processing of significant portions of typical scenes as trivially hidden, thus decreasing performance penalties.

We have concentrated this work on using visibility culling to accelerate the visualization of dynamic scenes, which are scenes composed by objects of arbitrary motion and considered as potential occluders. Our method operates on a regular grid that represents a volumetric discretization of the space and uses the opaque and hidden regions of the scene as occluders in object-space. The choice for regular grids in dynamic scenes was based on the flexibility of these data structures in quickly updating dynamic objects in comparison with hierarchical data structures, such as octrees and kD-trees usually exploited in static environments. Unfortunately, by using a regular grid we lose some benefits of hierarchical approaches, such as the ability to cull-out large portions of the scene in high levels of the hierarchy and the adaptive subdivision of the scene. To overcome these drawbacks we introduce several optimizations in the stages of scene discretization, view-frustum traversal and occlusion computation that strengthen the benefits of using regular grids in dynamic scene occlusion culling algorithms. So far, we have successfully implemented an output-sensitive algorithm for 2D and 3D scenes of arbitrary motion. The test results showed that the regular grid is very efficient in maintaining hidden dynamic objects, but the tightness of approximation of the PVS to the exact set is still unsatisfactory. While better results can be obtained by increasing grid resolution, the efficiency decreases due to the high number of additional voxels that need to be traversed. We believe that this weakness is due to our choice of using occlusion fusion in object-space only. We are currently working to exploit image-space occlusion fusion and to develop a scheme of recursive regular grids in order to discard large portions of the scene without traversing a great number of voxels.

Papers, demonstrations and source code of the current implementation are given below:

Dynamic Scene Visibility Culling using a Regular Grid (PDF) - Submitted to Computer Graphics Forum (Nov/2002)
Dynamic Scene Occlusion Culling using a Regular Grid (PDF) - Published in SIBGRAPI 2002 (Oct/2002)
Visibilidade em Cenas Dinâmicas com base numa Grade Regular (PDF - portuguese only) - Master thesis (Sep/2002)
2D Dynamic Scene Occlusion Culling using a Regular Grid (PDF) - Technical report (Dec/2001):


2D grid 300 dynamic objects (32 potentially visible) Resolution: 256x256x256 cells	2D grid 600 dynamic objects (9 potentially visible) Resolution: 256x256x256 cells


3D grid 4800 static objects + 200 dynamic objects 70x70x70 cells	Rendered scene from the viewpoint 220 potentially visible objects 50 actually rendered

This work was partially supported by Council for Improvement of Higher Education Personnel (CAPES), Brazil.