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:

 

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:

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.  

• Application of vertex-surface form factors
• Probabilistic progressive refinement