Ph.D Thesis, Department of Computer Science, KU Leuven, Celestijnenlaan 200A, 3001 Heverlee, December 1999.
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 al- gorithms 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.
