next up previous index
Next: Cubic tetrahedral algorithm Up: Form factor calculation Previous: Hemisphere algorithm

Hemicube algorithm

   

The hemicube algorithm is based on the fact that it is easier to project onto a planar rectangle than onto a spherical surface. Due to the change of the underlying geometry, the double projection cannot be expected to provide the same results as for a hemisphere, so in order to evaluate the inner form factor integral some corrections must be made during the calculation. These correction parameters are generated by comparing the needed terms and the terms resulting from the hemicube projections.

  
Figure: Form factor calculation by hemicube algorithm

Let us examine the projection onto the top of the hemicube. Using geometric arguments and the notations of figure 1.5, the projected area of a differential patch tex2html_wrap_inline1814 is:

equation401

since tex2html_wrap_inline2095 .

Looking at the form factor formula, we notice that a weighted area is to be calculated, where the weight function compensates for the unexpected tex2html_wrap_inline2097 term. Introducing the compensating function tex2html_wrap_inline2099 valid on the top of the hemicube, and expressing it by geometric considerations of figure 1.5 which supposes an (x,y,z) coordinate system attached to the tex2html_wrap_inline1812 , with axes parallel with the sides of the hemicube, we get:

equation412

Similar considerations can lead to the calculation of the correction terms of the projection on the side faces of the hemicube:

If the side face is perpendicular to the y axis, then:

equation416

or if the side face is perpendicular to the x axis:

equation419

The weighted area defining the inner form factor is an area integral of a weight function. If tex2html_wrap_inline1824 has a projection onto the top of the hemicube only, then:

equation422

Instead of integrating over tex2html_wrap_inline1824 , the same integral can also be calculated on the top of the hemicube in an x,y,z coordinate system:

equation427

since tex2html_wrap_inline2115 . Indicator tex2html_wrap_inline2117 shows whether tex2html_wrap_inline1824 is really visible through hemicube point (x,y,1) from tex2html_wrap_inline1826 or if it is obscured.

This integral is approximated by a finite sum having generated a tex2html_wrap_inline2125 raster mesh on the top of the hemicube.

displaymath2127

equation440

The only unknown term here is tex2html_wrap_inline1818 , which tells us whether or not surface j is visible through the raster cell called ``pixel'' (X,Y). Thanks to the research that has been carried out into hidden surface problems there are many effective algorithms available which can also be used here. An obvious solution is the application of simple ray tracing. The center of tex2html_wrap_inline1812 and the pixel defines a ray which may intersect several other surfaces. If the closest intersection is on the surface j, then tex2html_wrap_inline2139 is 1, otherwise it is 0.

A faster solution is provided by the z-buffer method. Assume the color of the surface tex2html_wrap_inline1824 to be j, the center of the camera to be tex2html_wrap_inline1812 and the 3D window to be a given face of the hemicube. Having run the z-buffer algorithm, the pixels are set to the ``color'' of the surfaces visible in them. Taking advantage of the above definition of color (color is the index of the surface), each pixel will provide information as to which surface is visible in it. We just have to add up the weights of those pixels which contain ``color'' j in order to calculate the differential form factor tex2html_wrap_inline2149 .

The projections on the side faces can be handled in exactly the same way, except that the weight function has to be selected differently ( tex2html_wrap_inline2151 or tex2html_wrap_inline2153 depending on the actual side face). The form factors are calculated as a sum of contributions of the top and side faces.

  The complete algorithm, to calculate the tex2html_wrap_inline1862 form factors using the z-buffer method, is:

 
for  i = 1 to N do  for j = 1 to N do tex2html_wrap_inline2165 ;
for  i = 1 to N do 
       camera = center of  tex2html_wrap_inline1826 ;
       for  k = 1 to 5 do  // consider each face of the hemicube
              window = kth face of the hemicube;
              for  x = 0 to    P-1 do 
                     for y = 0 to P-1 do pixel[x,y] = 0;
              Z-BUFFER ALGORITHM (color of surface j is j)
              for  x = 0 to P-1 do  for y = 0 to P-1 do 
                     if  (pixel[x,y] > 0) then 
                             tex2html_wrap_inline2203  +=  tex2html_wrap_inline2205 ;
              endfor 
       endfor 
endfor 

In the above algorithm the weight function tex2html_wrap_inline2205 must be evaluated for those pixels through which other surfaces are visible and must be added to that form factor which corresponds to the visible surface. This is why values of weight functions at pixel centers are called delta form factors.   Since the formula for weight functions contains many multiplications and a division, its calculation in the inner loop of the algorithm can slow down the form factor computation. However, these weight functions are common to all hemicubes, thus they must be calculated only once and then stored in a table which can be re-used whenever a value of the weight function is needed.

  Since the z-buffer algorithm has tex2html_wrap_inline2209 worst case complexity, the computation of the form factors, embedding 5N z-buffer steps, is obviously tex2html_wrap_inline2213 , where N is the number of surface elements and tex2html_wrap_inline2217 is the number of pixels in the z-buffer. It is important to note that P can be much less than the resolution of the screen, since now the ``pixels'' are used only to approximate an integral finitely. Typical values of P are tex2html_wrap_inline2223 .

Since the z-buffer step can be supported by a hardware algorithm this approach is quite effective on workstations supported by graphics accelerators.


next up previous index
Next: Cubic tetrahedral algorithm Up: Form factor calculation Previous: Hemisphere algorithm

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