Next: Application of vertex-surface form Up: RADIOSITY METHOD Previous: Gauss-Seidel iteration

# Progressive refinement

The previously discussed radiosity method determined the form factor matrix first, then solved the linear equation by iteration. Both steps require time and space, restricting the use of this algorithm in commercial applications. Most of the form factors, however, have very little effect on the final image, thus, if they were taken to be 0, a great amount of time and space could be gained for the price of a negligible deterioration of the image quality. A criterion for selecting unimportant form factors can be established by the careful analysis of the iteration solution of the radiosity equation:

If is small, then the whole column i of will not make too much difference, thus it is not worth computing and storing its elements. This seems acceptable, but how can we decide which radiosities will be small, or which part of matrix should be calculated, before starting the iteration? We certainly cannot make the decision before knowing something about the radiosities, but we can definitely do it during the iteration by calculating a column of the form factor matrix only when it turns out that it is needed, since the corresponding surface has significant radiosity.

Suppose we have an estimate allowing for the calculation of the contribution of this surface to all the others, and for determining a better estimate for other surfaces by adding this new contribution to their estimated value. If an estimate increases by , due to the contribution of other surfaces to this radiosity, other surface radiosities should also be corrected according to the new contribution of , resulting in an iterative and progressive refinement of surface radiosities:

These considerations have formulated an iterative algorithm, called progressive refinement. The algorithm starts by initializing the total ( ) and unshot ( ) radiosities of the surfaces to their emission, and stops if the unshot radiosity is less than an acceptable threshold for all the surfaces:

```for  j=1 to N do  ;
do
j = Index of the surface of maximum
Calculate   ,    ,...,    by a single hemicube;
for  i = 1 to    N do
;
+=   ;
+=   ;
endfor
;
;
while  error > threshold;
```

This algorithm is always convergent, since the total amount of unshot energy decreases in each step by an attenuation factor of less than 1. This statement can be proven by examining the total unshot radiosities during the iteration, supposing that was maximal in step m, and using the notation again:

since and , because it is the maximal value among -s.

Note that, in contrast to the normal iteration, the attenuation factor defining the speed of convergence now does depend on N, slowing down the convergence by approximately N times, and making the number of necessary iterations proportional to N. A single iteration contains a single loop of length N in progressive refinement, resulting in overall complexity, taking into account the expected number of iterations as well. Interestingly, progressive refinement does not decrease the time complexity, but in its simpler form when the form factor matrix is not stored, it can achieve O(N) space complexity instead of the behavior obtained by the original method.

Next: Application of vertex-surface form Up: RADIOSITY METHOD Previous: Gauss-Seidel iteration

Szirmay-Kalos Laszlo
Mon Oct 21 14:07:41 METDST 1996