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 is:

since .

Looking at the form factor formula, we notice that a weighted area is to be calculated, where the weight function compensates for the unexpected term. Introducing the compensating function 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 , with axes parallel with the sides of the hemicube, we get:

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:

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

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

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

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

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

The only unknown term here is , 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 and the pixel defines a ray which may intersect several other surfaces. If the closest intersection is on the surface j, then is 1, otherwise it is 0.

A faster solution is provided by the z-buffer method. Assume the color of the surface to be j, the center of the camera to be 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 .

The projections on the side faces can be handled in exactly the same way, except that the weight function has to be selected differently ( or 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 form factors using the z-buffer method, is:

 
for  i = 1 to N do  for j = 1 to N do  ;
for  i = 1 to N do 
       camera = center of   ;
       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 
                               +=   ;
              endfor 
       endfor 
endfor 

In the above algorithm the weight function 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 worst case complexity, the computation of the form factors, embedding 5N z-buffer steps, is obviously , where N is the number of surface elements and 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 .

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