Cohen M.F., Wallace J.R. - Radiosity and realistic image synthesis (1995)(en)

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

solution in the case of the rendering equation) is given by the Neumann series

Each term of the series corresponds to an additional application of the operator. Kajiya points out the following physical interpretation of this series: each application of the operator, K, corresponds to an additional surface interaction, or bounce, along a path from the light to the eye. Thus, the term K2e accounts for paths in which light reaches the eye via two bounces. This interpretation provides a useful way of comparing illumination algorithms, which Kajiya undertakes for several classic shading techniques.

The usefulness of such a comparison can be increased by formally including the split of the BRDF into components, since algorithms can often be characterized by how they account for these components. Several authors have taken this approach; the following discussion is based on Heckbert [120], who also introduces the use of regular expressions to provide a compact notation for describing paths.

For simplicity, the BRDF will be split into a Lambertian diffuse and a specular component, as in Heckbert’s presentation. The specular component subsumes the glossy and ideal specular parts. The kernel of the rendering equation can then be split into diffuse and specular components. Similarly, the integral operator becomes the sum of diffuse and specular operators K = D + S.

Expanded in terms of these operators, the Neumann series becomes

Each term in this equation represents a subset of the infinitely many paths that start at the light source and enter the eye from a particular direction. The first term, e, is the path leading directly from the light to the eye. The second term, De, consists of paths that start at the source and are diffusely reflected once before entering the eye, while the third term, Se, represents paths that contain one specular reflection, and so on. In all, light reaching the eye from a given direction may have traveled from the source via paths that include any number and combination of diffuse and specular interactions (see Figure 10.3). Since the series is infinite all possible light paths are accounted for. Similarly, an algorithm that accounts (correctly) for all paths provides a solution to the integral.

Heckbert suggests the use of regular expressions5 to simplify the description of paths. With the addition of L to indicate emission from the light and E to

5A regular expression describes a language consisting of words constructed from a

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.3: Some of the paths contributing to the radiance for a particular direction leading to the eye.

Heckbert suggests the use of regular expressions5 to simplify the description of paths. With the addition of L to indicate emission from the light and E to indicate absorption by the eye, any particular type of path can be represented textually by a string of symbols from the alphabet consisting of the letters {L,D,S,E}. As an example, light arriving via one bounce from a diffuse surface follows the path LDE, and that arriving by one bounce from a specular surface follows the path LSE.

The regular expression L(D|S)*E expresses the set of all possible paths for the two-component reflection model. This expression simply states that light leaving the source and reaching the eye may follow a path containing any number (including zero) of diffuse and specular reflections in any order. Algorithms can be characterized compactly by expressions that describe the subset of all possible paths that they attempt to account for.

The most common type of local illumination model, called the Utah approximation by Kajiya and widely available in graphics hardware, is characterized by the expression L(D|S)E. This expression contains the paths LDE (lo-

5A regular expression describes a language consisting of words constructed from a

the superscripted term). The symbol | means OR, and the parentheses have the obvious meaning.

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.4: Paths handled by the Utah approximation.

cal diffuse shading) and LSE (the Phong highlight), as shown in Figure 10.4. In addition to ignoring paths involving multiple reflection, such models often ignore shadowing, and thus include nonphysical paths. Classical ray tracing handles the paths LDS*E | LS*E, but with some restrictions (see Figure 10.3). The sequence LS in any path approximates glossy reflection using the Phong model, but subsequent specular reflections ignore all but ideal specular reflection. Distribution ray tracing extends ray tracing to account for all paths in LDS*E | LS*E. Radiosity is limited to the paths LD*E since in its traditional form it cannot handle specular reflection (see Figure 10.6).

10.2.2 Tracing the Transport Paths

A complete global illumination algorithm must account for all paths that start at the light and end at the eye. However, because of absorption and directional reflection, all paths do not contribute equally to the radiance reaching the eye. An efficient algorithm distributes computational resources among the paths appropriately, expending the greatest effort on paths that contribute most to the image.

Eye-Ray Tracing

For portions of paths consisting of the sequence S*E, the BRDF provides an a priori basis for estimating the importance of various paths. The eye position and

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.5: Representative paths handled by classical ray tracing.

the pixel location determine the outgoing direction for the final S interaction, and the shape of the BRDF provides a guide as to which incoming directions are likely to contribute significantly.6 (In the case of ideal specular reflection, the outgoing direction determines the only contributing incoming direction.) Working backwards from the eye, each subsequent S interaction along the path can be treated similarly. This provides the basic strategy for Whitted-style ray tracing and distribution ray tracing.

The utility of this strategy hinges on the ability to distinguish a limited number of incoming directions as important. As the brdf becomes increasingly diffuse, the relative importance of different incoming directions becomes correspondingly closer to equal and an increasing number of incoming directions must be considered for an accurate estimate (see Figure 10.7). At some point this strategy becomes prohibitively expensive. In such cases, most ray tracing algorithms give up and determine importance based on the location of the luminaires rather than the BRDF.

Light-Ray Tracing

Specular reflection also provides an a priori importance estimate when working forwards from the light source, for portions of paths consisting of the sequence

6A posteriori sampling is also useful, since the actual contribution coming from various incoming directions cannot be estimated until some samples have been taken. The graphics literature contains a great deal of discussion of such strategies [71, 135, 140, 147].

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.6: Paths handled by radiosity.

LS*. In this case, a path starting at the light intersects a surface, which determines an incoming direction, and the BRDF provides a basis for weighting the importance of all possible outgoing directions. This is the motivation for lightray tracing, which is often used to find what are loosely referred to as caustics7. Light-ray tracing for this purpose was first described by Arvo [12], although it was applied to shading by Appel very early in computer graphics [8]. Many subsequent algorithms have also used this approach [120, 214, 272]. As with eye-ray tracing, this strategy loses its utility once a D interaction is encountered (see Figure 10.7).

Bidirectional Ray Tracing

If there is only one D interaction, light-ray tracing and eye-ray tracing can be combined to account for all paths by having them meet in the middle at the diffuse surface (an approach often called bidirectional ray tracing). Light rays that end on the diffuse surface typically have their power deposited in “bins” into which the surface is subdivided. Eye rays ending on the diffuse surface then interpolate the stored power to approximate contributions that would be obtained by tracing the path farther (see Figure 10.8).

7Although the term caustic has a very specific meaning in optics, in image synthesis it has often been used more generally to refer to the illumination of diffuse surfaces by light reflected from a specular surface. Mitchell and Hanrahan discuss caustics in detail in [168].

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.7: Light-ray tracing and eye-ray tracing. Neither provide an advantage for path segments containing a diffuse interaction.

Bidirectional ray tracing handles the paths LS*DS*E. Paths are effectively “broken” at the diffuse surface by averaging together the effect of many paths landing within a certain bin. This takes advantage of the fact that the ideal diffuse component of radiance usually changes fairly slowly, a consequence of the fact that incident illumination is integrated over the entire hemisphere of incoming directions—essentially a filtering operation.

Radiosity and Transport Paths

In one sense, radiosity is simply a generalization of the bidirectional ray tracing strategy to multiple diffuse interactions. Radiosity restricts the number of paths to be considered by agreeing to minimize the error over a region (Galerkin method) or at discrete points distributed over surfaces (point collocation). The interactions between the regions or points are then computed using numerical integration. In effect, the form factor between two elements (or basis functions) averages together the effect of paths that directly join the two elements.

Conventional radiosity handles the paths LD*E. When combined with eye—and light-ray tracing, it can be extended to the paths LS*(D*)S*E (see Figure 10.9). In this case, light rays are traced until their power is deposited on an ideal diffuse surface. A radiosity solution is then performed with initial radiosities determined from the deposited power. Finally, eye-ray tracing is used to render an image, tracing paths from the eye through (potentially) several

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.8: Bidirectional ray tracing with a single diffuse interaction.

specular interactions to reach a Lambertian diffuse surface.

The inner sequence D* in the above expression, which is handled by the radiosity step, is incomplete, since it is only a subset of the correct sequence, (D*S*D*)*.8 This is because radiosity does not account for light that travels from one diffuse surface to another via specular reflection by intermediate surfaces.

The next sections will present methods for accounting for these missing paths in the radiosity solution. Such methods can be classified as either implicit or explicit. In an explicit method, the global illumination problem is formulated in terms of the radiance L(x, φ). An approximation of L(x, φ) is computed and stored for all surfaces, including those with a BRDF containing glossy or ideal specular components.

In an implicit method, the problem formulation remains the same as in the radiosity method, with the effect of reflection from ideal specular or glossy surfaces included only to the extent that they affect Lambertian diffuse surfaces. This is accomplished by modifying coefficients of the operator K. The glossy and ideal specular components are never actually computed or approximated.

8The string LS*(D*S*D*)*S*E is equivalent to the string L(S|D)*E.

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.9: Radiosity with eye-ray tracing and light-ray tracing.

10.2.3 Implicit Methods

Extended Form Factors

The discretized radiosity equation expresses the radiosity for each element as a linear sum of the radiosities of all other elements. Somewhat surprisingly, it is possible to rewrite the equation, leaving out certain elements and still form a correct solution for the remaining elements. The new system will be correct as long as the coefficients of the radiosity equation, the form factors, account for all paths between the elements of interest. This can be used to incorporate the effect of glossy and ideal specular surfaces into the radiosity solution.

As an example, if there are four elements {a, b, c, d} (see Figure 10.10) element b can be eliminated from the computation by computing extended form factors from all other elements to all other elements via element b. In the case of constant basis functions, the extended form factor Fdba represents the fraction of energy leaving element d and arriving at element a after reflecting from element

b. If all surfaces are diffuse, then Fdba = Fdb * ρb * Fba. An equivalent system of form factors can thus be constructed given all extended form factors with b

as the intermediate element, by

1.adding Fibj to the term Fij, for all pairs ij, and

2.eliminating the bth row and column from K.

The resulting system is equivalent to the original system, insofar as the included

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

Figure 10.10: Extended form factors.

elements are concerned. Eliminating element b is much like the elimination involved in linear equation solvers such as Gaussian elimination.

The extended form factor is a natural generalization of the notion of a form factor, which simply expresses the fraction of energy leaving one element that will arrive at another element. Eliminated elements provide additional multibounce paths along which energy can be transported between the remaining elements. The additional paths are accounted for by increasing or extending the form factors between the other elements.

When does it make sense to exclude certain surfaces from the solution? Whenever it is difficult or expensive to store an approximation of the radiance for those surfaces. This is certainly the case for surfaces with a highly directional BRDF, since an adequate approximation requires storing a detailed directional distribution at closely spaced nodes. It may also be useful to exclude procedurally defined objects, like fractal surfaces, for which it may be impractical to generate a mesh. When excluded surfaces are rendered in the final image, their radiance is computed using another algorithm such as eye-ray tracing, with the radiosity solution providing the approximation of the ideal diffuse component where needed.

The basic theory for extended form factors was introduced to image synthesis by Rushmeier [197, 201]. Rushmeier provides an algorithm for computing ex-

CHAPTER 10. EXTENSIONS

10.2 DIRECTIONAL REFLECTION

tended form factors for paths that contain a single ideal specular bounce (DSD) from a planar surface (i.e., a mirror). With these limitations it is possible to compute extended form factors using the hemicube algorithm. Mirrors are simply treated as openings into a virtual mirror world, which consists of the entire scene flipped about the plane of the mirror. The form factor to an element in the mirror world is added to the form factor to the element in the normal world, to obtain the total extended form factor. Rushmeier’s mirror form factor algorithm provides the first pass of the two-pass method described by Wallace et al. [246]. Hall [114] provides pseudocode for the mirror form factor algorithm.

Malley, Sillion, and others [142, 157, 218] compute extended form factors using recursive ray tracing. This allows multi-bounce DS*D paths to be followed and BRDFs with a glossy reflection component to be included. It also extends the method to nonplanar surfaces. In addition, ray tracing can be used to compute extended form factors that account for transparent, refracting surfaces. Shirley [212] has demonstrated the use of extended form factors to eliminate a Lambertian diffuse surface from the solution. In this algorithm, the radiosity of the excluded surface is computed during rendering using Monte Carlo ray tracing.

Color plates 43 and 44 provide a comparison of images computed with and without the use of extended form factors. Note the light missing from the top of the table in front of the mirror in the “before” image.

10.2.4 Explicit Methods

Implicit methods, like extended form factors, do not provide an approximation of the directional component of the radiance, which must be computed by other means during rendering. By contrast, in an explicit method the more general rendering equation is solved to produce an approximation of the radiance, L(x, ω ). The approximation must thus represent the directional as well as spatial variation of the radiance.

The Global Cube

One straightforward approach to approximating both the directional and spatial variations of the radiance is to use two sets of basis functions. The directional radiance distribution at each node can be approximated using one set of basis functions defined over direction, with the spatial variation interpolated across elements using a different set of basis functions.

Immel et al. [132] approximate the directional radiance distribution at each node using a global cube, in which the radiance for discrete directions over finite solid angles is approximated by a constant value. The directional discretization is determined by uniformly subdividing the faces of a cube (see Figure 10.11).