6.3: Stochastic Relaxation Radiosity

6.3 Stochastic Relaxation Radiosity

This section and the next one (Section 6.4) cover radiosity algorithms that solve the radiosity system of equations (Equation 6.6) using form factor sampling as discussed in the previous section. We shall see that by doing so, the form factor will appear in the numerator and denominator of the mathematical expressions to be evaluated, so that their numerical value will never be needed. Because of this, the difficult problems of accurately computing form factors and their storage are simply avoided. These algorithms therefore allow much larger models to be rendered with a fraction of the storage cost of other radiosity algorithms. In addition, Monte Carlo radiosity algorithms have a much better time complexity: roughly log-linear in the number of patches rather than quadratic like their deterministic counterparts. In short, they do not only require less storage, but for all but the simplest models, they also finish in less computation time.

There are basically two approaches to solve the radiosity system of linear equations (Equation 6.6) by means of Monte Carlo methods. This section covers the first approach: stochastic relaxation methods; the next section covers the second approach: discrete random walk methods.

The main idea of stochastic relaxation methods is that the radiosity system is solved using an iterative solution method such as Jacobi, Gauss-Seidel, or Southwell iterations [29, 172]. Each iteration of such a relaxation method consists of sums: dot products of a row of the form factor matrix with the radiosity or power...