The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Efficient Algorithms for Occlusion Culling and Shadows

Timo Aila

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Computer Science and Engineering for public examination and debate in Auditorium AS1 at Helsinki University of Technology (Espoo, Finland) on the 25th of February, 2005, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-7483-3)   [11066 KB]
Dissertation is also available in print (ISBN 951-22-7480-9)

Abstract

The goal of this research is to develop more efficient techniques for computing the visibility and shadows in real-time rendering of three-dimensional scenes. Visibility algorithms determine what is visible from a camera, whereas shadow algorithms solve the same problem from the viewpoint of a light source.

In rendering, a lot of computational resources are often spent on primitives that are not visible in the final image. One visibility algorithm for reducing the overhead is occlusion culling, which quickly discards the objects or primitives that are obstructed from the view by other primitives. A new method is presented for performing occlusion culling using silhouettes of meshes instead of triangles. Additionally, modifications are suggested to occlusion queries in order to reduce their computational overhead.

The performance of currently available graphics hardware depends on the ordering of input primitives. A new technique, called delay streams, is proposed as a generic solution to order-dependent problems. The technique significantly reduces the pixel processing requirements by improving the efficiency of occlusion culling inside graphics hardware. Additionally, the memory requirements of order-independent transparency algorithms are reduced.

A shadow map is a discretized representation of the scene geometry as seen by a light source. Typically the discretization causes difficult aliasing issues, such as jagged shadow boundaries and incorrect self-shadowing. A novel solution is presented for suppressing all types of aliasing artifacts by providing the correct sampling points for shadow maps, thus fully abandoning the previously used regular structures. Also, a simple technique is introduced for limiting the shadow map lookups to the pixels that get projected inside the shadow map.

The fillrate problem of hardware-accelerated shadow volumes is greatly reduced with a new hierarchical rendering technique. The algorithm performs per-pixel shadow computations only at visible shadow boundaries, and uses lower resolution shadows for the parts of the screen that are guaranteed to be either fully lit or fully in shadow.

The proposed techniques are expected to improve the rendering performance in most real-time applications that use 3D graphics, especially in computer games. More efficient algorithms for occlusion culling and shadows are important steps towards larger, more realistic virtual environments.

This thesis consists of an overview and of the following 5 publications:

  1. T. Aila, V. Miettinen, and P. Nordlund. 2003. Delay streams for graphics hardware. ACM Transactions on Graphics 22, number 3, pages 792-800.
  2. T. Aila and T. Akenine-Möller. 2004. A hierarchical shadow volume algorithm. In: Proceedings of the Eurographics Symposium on Graphics Hardware 2004, Eurographics Association, pages 15-23.
  3. T. Aila and V. Miettinen. 2004. dPVS: an occlusion culling system for massive dynamic environments. IEEE Computer Graphics and Applications 24, number 2, pages 86-97.
  4. J. Arvo and T. Aila. 2003. Optimized shadow mapping using the stencil buffer. Journal of Graphics Tools 8, number 3, pages 23-32.
  5. T. Aila and S. Laine. 2004. Alias-free shadow maps. In: Proceedings of the Eurographics Symposium on Rendering 2004, Eurographics Association, pages 161-166.

Errata of publication 1

Keywords: computer graphics, shadow algorithms, occlusion culling, 3D graphics hardware, order-independent transparency

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2005 Helsinki University of Technology

Last update 2011-05-26