next up previous index
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 tex2html_wrap_inline2286 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:

displaymath2326

equation590

If tex2html_wrap_inline2258 is small, then the whole column i of tex2html_wrap_inline2290 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 tex2html_wrap_inline2290 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 tex2html_wrap_inline2258 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 tex2html_wrap_inline2258 increases by tex2html_wrap_inline2344 , due to the contribution of other surfaces to this radiosity, other surface radiosities should also be corrected according to the new contribution of tex2html_wrap_inline2258 , resulting in an iterative and progressive refinement of surface radiosities:

  equation595

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 tex2html_wrap_inline2284 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 tex2html_wrap_inline2354 , that is a single column of the form factor matrix, to calculate the radiosity updates due to tex2html_wrap_inline2344 . 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:

equation607

These considerations have formulated an iterative algorithm, called progressive refinement. The algorithm starts by initializing the total ( tex2html_wrap_inline1772 ) and unshot ( tex2html_wrap_inline2360 ) 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  tex2html_wrap_inline2366; tex2html_wrap_inline2368
do  
      j = Index of the surface of maximum  tex2html_wrap_inline2372
      Calculate  tex2html_wrap_inline2374 ,  tex2html_wrap_inline2376  ,...,    by a single hemicube;
      for  i = 1 to    N do 
             tex2html_wrap_inline2384 ;
             tex2html_wrap_inline2360  +=  tex2html_wrap_inline2388 ;
             tex2html_wrap_inline1772  +=  tex2html_wrap_inline2388 ;
      endfor 
      tex2html_wrap_inline2394 ;
      tex2html_wrap_inline2396 ;
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 tex2html_wrap_inline2400 was maximal in step m, and using the notation tex2html_wrap_inline2288 again:

displaymath2406

equation627

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

Note that, in contrast to the normal iteration, the attenuation factor tex2html_wrap_inline2414 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 tex2html_wrap_inline2286 overall complexity, taking into account the expected number of iterations as well. Interestingly, progressive refinement does not decrease the tex2html_wrap_inline2286 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 tex2html_wrap_inline2286 behavior obtained by the original method.  




next up previous index
Next: Application of vertex-surface form Up: RADIOSITY METHOD Previous: Gauss-Seidel iteration

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