6.4 Discrete Random Walk Methods for Radiosity

In the previous section, a first class of stochastic methods was described for solving the radiosity system of equations (Equation 6.6) or the equivalent power system (Equation 6.8) by means of stochastic variants of well-known iterative solution methods for linear systems, such as the Jacobi iterative method. It was shown that form factor computation and storage is effectively avoided, allowing us to compute radiosity in large models with less computer storage and less computing time than their deterministic counterparts.

This section covers a second class of methods with identical properties. The methods discussed here are based on the concept of a random walk in a so-called discrete state space, explained in Section 6.4.1. Unlike stochastic relaxation methods, random walk methods for linear systems are well covered in Monte Carlo literature [62, 183, 61, 43, 153]. They have been proposed for solving linear systems similar to the radiosity system since the beginning of the 1950s [50, 224]. Their application to radiosity has been proposed in [161, 162].

It turns out that these algorithms are not better than the stochastic Jacobi algorithm of the previous section. We will, however, introduce a number of fundamental concepts that are needed in later sections and chapters, but that are easier to understand first in this context.