Computer Graphics & Geometry

A BSP-Based Algorithm for Analytical Form-Factor Calculation

P. Jacob, H. Hagen
University of Kaiserslautern, AG Computer Graphics

Postfach 3049, D-67653 Kaiserslautern, Germany

FAX: +49 (631) 205-3270


Contents

Abstracts:

Radiosity-techniques are global illumination models, which are based on the physics of radiometry. All these techniques have in common the need to calculate form-factors (geometry-factors), which determine the energy exchange between patches of finite or infinite size. Form-factors between a differential area and a patch, so-called differential form-factors, may be used for intensity calculus on surfaces which are illuminated by area light sources.

Hemicube, singleplane and ray tracing approaches are numerical approximations to calculate these form-factors. This paper presents an analytical method for calculating form-factors between a patch and a differential area using BSP-trees. An application of this algorithm called BSP-shading is described, which may be used for rendering scenes with area light sources or scenes on which the progressive refinement [1] method has been applied.

Key words: computer graphics; form-factor; BSP-shading.

1. Form-Factors

1.1. Definitions

The form-factor Fij equals the amount of energy reaching patch i, emitted by parch j. The form-factor between a finite area Aj and a differential area dAi [2,3] is called differential form-factor. Form-factors are defined by the following double integral and are only dependent on the geometry of the objects

Fig. 1. Nusselt analogon

The integral from Equation 1 has to be solved for all radiosity methods like for example the full-matrix-method or the progressive refinement [1,4]. In the year 1928 Nusselt [5] presented a geometric interpretation of Equation 1, where an hemisphere is built on the differential area dAi , having the same direction as the surface normal of patch i. The differential form-factor is equivalent to the ratio of the projected sphere segment Ap and the area of the unit circle (Fig. 1)

A number of analytic expressions for generic patch configurations can be derived, using

the definition of the form-factor between two differential areas (Fig. 2)

Fig. 2. Form-factor between two differential areas

Fig. 3. Delta-form-factor for the hemicube

Example: The following formula is used to calculate the delta-form-factors for an hemicube or a singleplane (Fig. 3)

1.2. Algorithms for the Calculation of Form-Factors

1.2.1. Basics

To evaluate the area integral from the definition of a differential form-factor, Stoke's theorem can be applied to rewrite (1) as a contour integral. In case of polygons this contour integral may be expressed as a sum over the edges of a polygon (Fig. 4)

(2)

Gk is the cross-product of Rk and Rk+1 having the magnitude of the angle gk+1 ; Ni is the surface normal of patch i .

Equation (2) can be used to calculate the exact form-factors, if there are no objects between patch j and the differential area dAi which may cast shadows. Because of that reason the polygons of the scene have to be split and hidden polygon-fragments have to be removed.

1.2.2 The Rendering-Equation

Kajiya [6] derived an integral equation from radiation heat transfer [2], known as the Rendering Equation, which is suitable for computer graphics (Fig. 5)

All rendering algorithms can be seen as an approximation to the solution of the Rendering Equation. The term I(x,x' ), the intensity leaving point x' arriving at point x', consists of two components:

Fig. 4. Differencial form-factor of a polygon

i) e(x,x' ) is the amount of energy which is emitted from point x' to point x;

ii)

is the amount of energy emitted from any point x" from the surface of an object to point x'. From x' the energy is reflected in the direction of point x, weighted with the bidirectional reflectivity of the material.

To solve the second part of equation (3), an integration over S, the union of all surface points of all objects of the scene has to be performed. For all these points the geometry term g(x,x') has to be calculated during the evaluation of I(x',x"). The set S can be reduced to the union of all points Vx' �S which are visible from x', because the contribution of all other points is zero due to the geometry term.

At this point the equivalence of the calculation of a differential form-factor for a 3D-point and the solution of the hidden-surface-problem can be seen. Different rendering algorithms can be used for the calculation of form-factors. Scan conversion and depth buffer are the basic principles of the hemicube and singleplane method. Wallace [7] used ray tracing and sampling techniques to solve the integral from (1).

Fig. 5. Rendering-Equation

1.2.3. The Hemicube

The hemicube [12] is a numerical approximation for the calculation of differential form-factors, which is very efficient, especially if graphics hardware (z-buffer) is available. An hemicube is built with it's center located on the differential area, similar to an hemisphere. Delta-form-factors can be precalculated for each pixel of the hemicube (Fig. 6). The scene is projected on every side of the hemicube, with the center of projection lying on the differential area dAi. The delta-form-factors of all pixels through which the patch j is visible are added.

Fig. 6. Hemicube & Singleplane

The singleplane works in an analog way except that only one projection is needed. The advantage of the singleplane is that it is five times faster than the hemicube, but usually form-factors calculated with this method are underrated because the viewing angle is too small. Increasing this angle to 2p, almost every object is projected in the middle of the singleplane, which causes aliasing problems.

To guarantee that the form-factor to a pixel is a good approximation to the form-factor for that part of the object which is visible through that pixel, several assumptions have to be made.

1.3. The errors in the Calculation of Form-Factors

The errors in the calculation of form-factors, between two surface elements of finite size, fall into two categories.

1.3.1. Proximity and Visibility Assumption

When Fij, is calculated, the inner integral of (1) is assumed to be constant and Fdij is evaluated in several points lying on the object (for example the center of gravity or the corners).

The form-factor Fij, is the average of Fdij samples. If patch i is partially hidden in the view from patch j (visibility assumption), errors may occur. Errors which result from building the average of the samples are a violation to the proximity assumption (for further discussion see [1]).

1.3.2. Errors due to the Aliasing Assumption

If the resolution is too small, an error may occur, when a differential form-factor is calculated using the hemicube (or other numerical methods). In some cases these aliasing effects can be reduced if the sampling rate is increased, but generally this decreases the efficiency of these algorithms.

Aliasing errors occur if the differential form-factor of an object differs from the sum of delta-form-factors of the pixels on which the object has been projected.

1.4. Hybrid Methods

Baum [9] developed a hybrid algorithm, based on the hemicube, which reduces errors in the calculation of form-factors using a small amount of additional computation time. Analog to Cohen & Greenberg [8] first all objects are projected on an hemicube. If the assumptions 1.3.1 and 1.3.2 are satisfied for a single pixel, the delta-form-factors are added to Fij . If one of these assumptions is violated, the pixel is projected on the polygon and the size of the projected area is used as weight of the associated delta-form-factors. Because this algorithm is based on a projection of polygons on discrete pixels, errors may occur if the size of a projected polygon is small compared to the size of a pixel. This is for example the case if an object is lit by several light sources, which are small or located at a large distance.

Example: If a diffuse surface is illuminated by two area light sources i and j (Fig. 7), two differential form-factors have to be calculated for each pixel on the surface. If the intensities of two adjacent points P1 and P2 are compared, it depends on random which of the light sources is visible. If, in addition, the radiosities of the two light sources are different, a noise (aliasing) will appear on the surface.

1.5. BSP-Trees

BSP-trees (binary space partitioning) are binary trees which are used to divide n dimensional spaces in subspaces. This space division has been used very early in computer graphics to solve the hidden surface problem [11]. A BSP-tree is view independent and is built during the preprocessing of a scene. The traversal is a modified binary tree traversal, with respect to a specific viewpoint, which can be used to solve the visibility problem. In the three dimensional case a BSP-node is a plane which divides space in two subspaces. Fig. 8 shows a BSP-tree of a scene composed of five polygons. In this example the BSP-nodes are the planes defined by the polygons.

Fig. 8. A BSP-tree

BSP-Generation

When a BSP-tree is built, first a plane is chosen and all objects are classified against that plane as lying in front or back. Each (internal) BSP-node has a reference to its front and back child which are built recursively (Fig. 10).

void front_to_back(const BSP_tree *bsp_node, const Vector &p)

{

if(bsp_node==NULL) return;

if(p*bsp_node->plane_ptr->n>bsp_node->plane_ptr->d)

{

// 3D-point p is classified as front

front_to_back(bsp_node->front_ptr,p);

// proceding a BSP-node

front_to_back(bsp_node->back_ptr,p);

}

else

{

// 3D-point p is classified as back

front_to_back(bsp_node->back_ptr,p);

// proceding a BSP-node

front_to_back(bsp_node->front_ptr,p);

}

Fig. 9. Front-to-back-Traversal in C++

Recursion stops if no objects have been classified for a node. The depth of the tree depends on the choice of the clipping plane. An increased depth also increases the number of viewpoint classifications needed during the traversal, which decreases the efficiency of the algorithm. class BSP_tree

{

Plane *plane_ptr;

BSP_tree *front_ptr,*back_ptr;

};

Fig. 10. Definition of BSP-node in C++

1.5.2. BSP-Traversal

The traversal for a specific viewpoint B starts with the root of the BSP-tree. In each node B is classified as lying in front or back of the corresponding partitioning plane. For the algorithm described in 1.6 a front-to-back traversal is needed where among polygons, which may hide each

other those are traversed first which have the smallest distance to the viewer. If the point B is classified as front, first the front and then the back BSP-tree are recursively traversed. If the point B is classified as back, the back and then the front BSP-tree are traversed. For the BSP-tree from Fig. 8 the front-to-back traversal for point B would be:

5 1 3 2 4

In Fig. 9 the operator (*) denotes the scalar product between two vectors and the partitioning planes are defined by a normal and a distance to the origin of the coordinate system.

1.6. Analytic SVBSP-Method

1.6.1. Shadow Volumes

Crow [12] used shadow volumes to calculate shadows from point light sources in polyhedral scenes. Chin & Feiner [13] developed an algorithm which uses shadow volumes to split a scene into 'shadow' and 'lit' polygon fragments. A shadow volume is defined by a number of planes and a point (the location of the point light source) which lies on all planes [14].

1.6.2. SVBSP-Trees

SVBSP-trees are BSP-trees where the planes, associated with each node, are the side planes of a shadow volume. The 'in'-leaves are shadow areas of the associated light source, the 'out'-leaves are lit. Fig. 11 shows a SVBSP-tree of the scene from Fig. 8.

1.6.3. SVBSP-Generation and Form-factor Calculation

As polygons, which are close to the viewer may hide other parts of the scene, polygons have to be processed in a front-to-back order. This is achieved by traversing the BSP-tree, that has been built for the scene as described in 1.5.1, front-to-back. First the shadow volume is initialized by an empty tree. The first front-to-back traversed polygon is clipped against the shadow volume and the differential form-factor Fdij of the fragment lying outside of the volume is calculated using the sum formula from 1.2.1. The form-factor is added to the polygon it corresponds, which may have been split during the BSP-generation. Then the shadow volume is extended by that polygon [15]. These steps are repeated until all polygons have been traversed or one of the criteria from 1.6.4 are fulfilled.

Fig. 11. Shadow Volumes

Fig. 12 shows the generation of a SVBSP-tree and form-factor calculation with the example from Fig. 8. The letters a and b represent the corners of a polygon respectively the side-planes of a shadow volume. For simplicity the leaves of the SVBSP-tree have been removed after node 1 has been inserted.

Fig. 12. SVBSP-Generation

1.7. Early termination of the SVBSP-Generation

Usually form-factors are used to calculate intensities or radiosities, which implies that in most cases form-factors to patches which have radiosities equal to zero are not needed. A weight, proportional to the radiosity of each patch, can be used to place patches with non zero radiosities at the top of the BSP-tree. If the number of patches with non zero radiosities is counted during the traversal, one can stop after the last patch which has a radiosity is encountered and terminate the SVBSP-generation before all patches have been processed. In the following example (Fig. 13) 14 polygon fragments have to be processed for a complete BSP- traversal. Patch e and f are the only patches which have non zero radiosities. By using weighs, these patches are on depth 0 and 1 of the BSP-tree. Using the strategy described above to build the BSP-tree, only 4 respectively 12 fragments need to be considered.

If the sum of all form-factors for a single point is equal to one, the entire hemisphere is occupied with projections of objects from the scene. In this situation traversal can be stopped because no objects visible from that viewpoint exist. The form-factor contribution from all the rest- fragments is thus zero.


Fig. 13. Terminator of the BSP-Traversal

Fig. 14. Soft-Shadows

On the right half there are two zoomed images of the marked region. The one generated by hemicube ray tracing [10] shows aliasing effects caused by errors in the form-factors. The hemicube ray tracing needed 1h 45 min to calculate the 135.628 form-factors whereas the SVBSP-method needed only 2 min of CPU-time.

The shading algorithm described in 1.6 has the advantage that it works without hardware accelerator. To speed up shading the algorithm has been distributed on several machines to work parallel on a single image. The time needed to sum up delta-form-factors with the hemicube method is the main reason why this algorithm is relatively slow for small scenes. It gains more efficiency if the number of polygons is increased, because more time is spent in z-buffering and scan conversion. As the form-factors generated by the SVBSP-method are analytic exact, aliasing does not occur in these images. Another advantage of this algorithm is that it is easy to implement and does not cause numerical problems.

References

[1] M.F.Cohen, S.Chen, J.Wallace and D.Greenberg, 'A Progressive Refinement Approach To Fast Radiosity Image Generation', ACM Computer Graphics, 33, (3), 75-84.

[2] R.Siegel and J.Howell, 'Thermal Radiation Heat Transfer', Hemisphere Publishing Corp. Washington DC 1981.

[3] S.Hott, 'Radiative Transfer', McGraw-Hill, New York, 1982.

[4] C.Goral, K.Torrance, D.Greenberg and B.Battaile, 'Modeling The Interaction of Light Between Diffuse Surfaces', ACM Computer Graphics (SIGGRAPH'84), 213-222.

[5] W.Nusselt, 'Graphische Bestimmung des Winkelverhaltnisses bei der Warmestrahlung', VDIZ, 72, 673, (1928).

[6] J.T.Kajiya, 'The Rendering Equation', ACM Computer Graphics, 20, (4), 143-150.

[7] J.Wallace, K.Elmquist and E.Haines 'A Raytracing Algorithm for Progressive Radiosity', ACM Computer Graphics, 23, (3), 315-324.

[8] M.Cohen and D.Greenberg, 'The Hemi-Cube, A Radiosity Solution For Complex Environments', ACM Computer Graphics, 19, (3), 31-40.

[9] R.Baum, H.Rushmeier and J.Wingert, 'Improving Radiosity Solutions Through the Use of Analytically Determined Form-Factors', ACM Computer Graphics, 23, (3), 325-334.

[10] U.Urs Meyer, 'Hemi-Cube Ray Tracing: A Method for Generating Soft Shadows', Proc. Of Eurographics, 365-376, (1990).

[11] H.Fuchs, Kendem, B.Naylor, 'On Visible Surface Generation by A Priori Tree Structures', ACM Computer Graphics, 14, (3), 124-133.

[12] F.Crow 'Shadow Algorithms for Computer Graphics', ACM Computer Graphics, 11, (3), 242-248.

[13] N.Chin and S.Feiner, 'Near Real-Time Shadow Generation Using BSP-Trees', ACM Computer Graphics, 23, (3), 99-106.

[14] A.Woo, P.Poulin and A.Fournier 'Survey of Shadow Algorithms', IEEE Computer Graphics and Applications, (6), (1990).

[15] N.Thibault, 'Operations on Polyherda Using Binary Space Partitioning Trees', ACM Computer Graphics, 21, (4), 153-162.

[16] S.Westin., J.Arvo and K.Torrance, 'Predicting Reflectance Functions from Complex Surfaces', ACM Computer Graphics (SIGGRAPH'92), 26, 255-264.

Computer Graphics & Geometry