Monte Carlo Techniques for Radiosity
Philippe Bekaert |
Contact: Computer Graphics Research Group
Dagstuhl Seminar No. 00251, Report No. 278
Wadern, Germany, 18-23 June
Abstract
The radiosity method is a physically based method to compute the illumination in a virtual environment with diffuse (matte) surfaces. It leads to very large systems of linear equations (100,000 equations is common). Moreover, the coefficients of these systems are given by non-trivial four-dimensional integrals (form factors). The Monte Carlo method is a method of last resort to solve such difficult mathematical problems. In this talk, an overview is presented of how the Monte Carlo method can be applied in the context of the radiosity problem.
The Monte Carlo method can be used for reliable form factor integration. It turns out to be difficult to determine how many samples are required for computing each form factor in such a strategy however.
The emphasis of the talk is therefore on Monte Carlo techniques for solving the radiosity system of linear equations directly, bypassing the need for explicit form factor computation by interpreting the form factors as probabilities that can be sampled efficiently by tracing rays. Such techniques include stochastic relaxation methods and random walk methods. Stochastic relaxation methods are stochastic adaptations of well known deterministic relaxation methods for linear systems: relaxation methods contain matrix-vector products, which can be estimated by Monte Carlo. Random walk methods for linear systems are very similar to random walk methods for integral equations, used in e.g. path tracing. They have been studied intensively since the second world war.
In order to overcome the slow convergence rate of Monte Carlo, various variance reduction techniques can be used. Variance reduction techniques for Monte Carlo radiosity include view-importance sampling, the use of a constant control variate, combinations of gathering and shooting and weighted importance sampling. Low-discrepancy sampling is another way to speed up Monte Carlo radiosity.
In order to reduce discretisation artifacts, various ways to incorporate hierarchical refinement and to compute higher order radiosity approximations have been proposed in the context of Monte Carlo radiosity.
In my experience, the resulting Monte Carlo radiosity algorithms are an alternative of great value for deterministic radiosity algorithms: they often yield useful images more rapidly, they require less storage and they are more reliable and easier to implement correctly and to use.
Among all discussed algorithms, in particular the simple stochastic Jacobi iterative method proposed by Neumann et al is a good candidate to use in practice. The basic algorithm is as good as other algorithms, but variance reduction techniques appear to be more efficient and easier to implement.
The talk is concluded with some directions for further improvement of Monte Carlo radiosity algorithms.