Philippe Bekaert Katholieke Universiteit Leuven

Contact: Philippe Bekaert

Ph.D. Thesis, Katholieke Universiteit Leuven, 260 + xii p

Abstract

The radiosity method is a physically based method to compute the illumination in a virtual environment with diffuse (matte) surfaces. It allows to generate very realistic images of such environments by computer, and it is suitable for quantitative predictions of the illumination.

In the radiosity method, a number of simplifying assumptions are made that can however lead to certain image artifacts. In this dissertation, the numerical error introduced by these assumptions is analysed. The analysis allows to propose new algorithms in which this error, the discretisation error, is efficiently controlled during the computations by means of hierarchical refinement.

The radiosity method also requires the solution of very large non-sparse systems of linear equations (about 100,000 equations is common). Moreover, the coefficients of these systems are non-trivial four-dimensional integrals. The main part of this dissertation is devoted to an in-depth study of how the Monte Carlo method can be applied in this context.

The Monte Carlo method is suitable for reliable computation of the coefficients of the systems of equations. It also leads to algorithms that do not require explicit computation and storage of these coefficients. A systematic overview of such algorithms is presented. Previously proposed algorithms of this type are compared and some new algorithms are developed. Next, the application of several variance-reduction techniques is described, and the use of low-discrepancy sampling in this context is discussed. Finally, new ways to incorporate higher-order radiosity approximations and hierarchical refinement are proposed.

The resulting Monte Carlo radiosity algorithms do not only appear to be more reliable, but also often lead more rapidly to usable images than their deterministic counterparts. They require significantly less computer storage, and they are more user friendly. It is expected that these algorithms will stimulate the use of the radiosity method in a wide spectrum of applications.

---

Keywords: computer graphics, physically based image synthesis, illumination simulations, radiosity method, Galerkin method, hierarchical refinement, Monte Carlo method, quasi-Monte Carlo, form factor computation, systems of linear algebraic equations.

---

Overview

This dissertation is organised as follows:

• Chapter 1 introduces physically based global illumination and the radiosity method. The problems of the radiosity method and previous work are shortly described. The objectives of this dissertation are formulated;
• Chapter 2 presents a short review of the radiosity method with higher order approximations and hierarchical refinement;
• In chapter 3, the discretisation error in higher-order Galerkin radiosity computations is analysed and some algorithms proposed in order to deal with it;
• Chapter 4 briefly reviews the basic principles and techniques of the Monte Carlo method. The Monte Carlo method will be used for more reliable form factor computation as well as for solving the radiosity system of equations. An overview is given at the end of this chapter;
• The chapters 5 to 8 present a systematic overview of basic Monte Carlo estimators that can be used in the context of radiosity with constant approximations:
• Chapter 5 deals with Monte Carlo form factor computation. It also introduces basic sampling techniques that will be used in subsequent chapters;
• Chapter 6 presents stochastic relaxation methods for the solution of the radiosity system of equations;
• Chapter 7 presents the solution of the radiosity system of equations by random walk methods;
• In chapter 8, some other Monte Carlo methods for linear systems, found in general literature on this subject, are briefly mentioned.
Special attention is paid to analysing the computational error of the algorithms and ways of controlling it;
• The chapters 9 to 11 deal with variance reduction techniques that can be applied in order to increase the efficiency of stochastic relaxation and random walk methods:
• Chapter 9 presents applications of importance sampling. In particular, view-importance driven Monte Carlo radiosity algorithms are proposed;
• Chapter 10 discusses the control variates variance reduction technique;
• In chapter 11, various strategies for combining gathering and shooting radiosity estimates are proposed.
• Chapter 12 deals with the issue of low-discrepancy sampling in Monte Carlo radiosity. Various experiments are presented that also confirm theoretical results derived in previous chapters;
• In chapter 13, presents the extension of the Monte Carlo radiosity algorithms for constant radiosity approximations to higher-order approximations;
• Chapter 14 proposes per-ray refinement as a strategy to incorporate hierarchical refinement in Monte Carlo radiosity, paving the way for the development of radiosity algorithms in which both the discretisation and computational error is efficiently controlled;
• Chapter 15 concludes with a summary, a list of original contributions, and some directions for future research;
• The appendices contain additional information about our implementation of the algorithms described in this thesis.

---

Reproduction:

• Print two-sided: each chapter starts on an odd page, odd pages are printed "recto", even pages appear "verso": on the back of odd pages)
• Cut as indicated below:

Downloads

• Text (TAR,10.6 MB)
• Text (zipped PDF,9.0 MB)
• Titlepage and Abstract (PS.GZ)
• Table of Contents (PS.GZ)
• Chapter 1: Introduction (PS.GZ)
• Chapter 2: The Radiosity Method (PS.GZ)
• Chapter 3: Discretisation Error Control (PS.GZ)
• Chapter 4: The Monte Carlo Method (PS.GZ)
• Chapter 5: Monte Carlo Form Factor Computation (PS.GZ)
• Chapter 6: Stochastic Relaxation Radiosity (PS.GZ)
• Chapter 7: Random Walk Radiosity (PS.GZ)
• Chapter 8: Other Monte Carlo Methods for Linear Systems (PS.GZ)
• Chapter 9: Importance Sampling in Monte Carlo Radiosity (PS.GZ)
• Chapter 10: Control Variates In Monte Carlo Radiosity (PS.GZ)
• Chapter 11: Combining Estimators in Monte Carlo Radiosity (PS.GZ)
• Chapter 12: Low-discrepancy Sampling in Monte Carlo Radiosity (PS.GZ)
• Chapter 13: Monte Carlo Radiosity with Higher Order Approximations (PS.GZ)
• Chapter 14: Hierarchical Monte Carlo Radiosity (PS.GZ)
• Chapter 15: Conclusion (PS.GZ)
• Bibliography (PS.GZ)
• Appendices and List of Notations (PS.GZ)
• Dutch Summary (PS.GZ)

Links

• Lirias