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:

Note that, in contrast to the previous radiosity method when we were
interested in how a surface gathers energy from other surfaces, now the
direction of the light is followed focusing on how surfaces shoot light to
other surfaces. A radiosity increment of a surface, which has not yet been
used to update other surface radiosities, is called **unshot radiosity**.
In fact, in equation 1.52, the
radiosity of other surfaces should be corrected according to the unshot
radiosity of surface *j*. It seems reasonable to select for shooting
that surface which has the highest unshot radiosity. Having selected a
surface, the corresponding column of the form factor matrix should be
calculated. We can do that on every occasion when a surface is selected to
shoot its radiosity. This reduces the burden of the storage of the matrix elements to only a single column containing
*N* elements, but necessitates the recalculation of the form factors.
Another alternative is to store the already generated columns, allowing for
reduction of the storage requirements by omitting those columns whose
surfaces are never selected, due to their low radiosity. Let us realize that
equation 1.52 requires , that is a single column of the form factor matrix, to
calculate the radiosity updates due to . The hemicube method,
however, supports ``parallel'' generation of the rows of the form factor
matrix, not of the columns. For different rows, different hemicubes have to
be built around the surfaces. Fortunately, the reciprocity relationship can
be applied to evaluate a single column of the matrix based on a single
hemicube:

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:

forj=1toNdo;doj= Index of the surface of maximum Calculate , ,..., by a single hemicube;fori= 1toNdo; += ; += ;endfor; ;whileerror>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.

Mon Oct 21 14:07:41 METDST 1996