Geometric Simplification for Indirect Illumination Calculations

You can obtain a PostScript version of this paper without some of the figures . You can also obtain a PostScript file containing these figures .

Digested Version

Abstract

We present a new method for accelerating global illumination calculations in the generation of physically accurate images of geometrically complex environments. In the new method, the environment geometry is simplified by eliminating small isolated surfaces, and replacing clusters of small surfaces with simple, optically equivalent, boxes. A radiosity solution is performed on the simplified geometry. The radiosity solution is then used in a multi-pass method to estimate the radiances responsible for indirect illumination. We present a preliminary implementation of the new method, and some initial images and timing results. The initial results indicate that using simplified geometries for indirect illumination calculations produces images in times significantly less than previous multi-pass methods without a reduction in image quality.

Introduction

The concept behind a ray tracing/radiosity hybrid is to take advantage of what each does best. Namely, a ray tracing solution is excellent for handling near specular surfaces, but is too expensive for diffuse ones; while a radiosity solution is best for diffuse surfaces, but becomes too expensive for specular ones. A classic hybrid approach is to first run a radiosity solution on the environment with the specular reflections ignored. Then an image is created with ray tracing. When rays bounce from a surface with the intent of gathering specular reflections, processing continues as usual. Suppose though, that a ray is sent to gather for a diffuse reflection. When the surface intersected is found, the radiosity value stored during the radiosity pass is returned and no further processing is necessary since this value is the result of all diffuse reflections. This definition is somewhat simplified but should suffice here. Unfortunately, although a complete radiosity solution for the diffuse energy transfer is less expensive than a ray tracing solution, it is still quite expensive.

Extended Hybrid Algorithm

The extended hybrid method will simplify the environment used by the radiosity pre-pass since the information is only used for diffuse reflections. Surfaces of a small enough size are eliminated and groups of large numbers of small surfaces forming objects are replaced by clumps as shown in Figure 1. Even diffuse surfaces have detailed reflections at close range, so the radiosity values will only be used at a distance of atleast r_thresh.

Figure 1: (Left) Rays from the eye and rays to the light source intersect the detailed environment. (Right) Rays for calculating indirect illumination intersect the simplified environment.

Remember that the radiosity pre-pass solution is not meant to be viewed as an accurate final image itself. It is part of the solution which relies on the Monte Carlo path tracing pass to complete the solution.

The solution method then, has three types of surfaces: normal, complex and simple.

Normal surfaces are large enough to be used both in the radiosity solution and in the final rendering.
Complex surfaces are small and are not used in the radiosity solution, but are used in the high resolution pass of the final rendering.
Simple surfaces are used in place of clusters of complex surfaces in the radiosity solution and during the low resolution requirements of the final rendering.

Small Isolated Surfaces (Complex Surfaces)

The first issue is how small must an isolated surface be to be ignored in the simplified solution? If we assume that the diffuse non-light source surfaces have radiances of approximately the same order of magnitude relative to the radiance of the light sources, the importance of a surface can be estimated by the solid angle it subtends.

A conservative estimate w_max of the solid angle subtended on i by another surface j is

w_max = A / r²

where r is the minimum distance from i to j, and A is the area of j. The actual solid angle subtended will be less than w_max since r is the minimum distance, and because of the omission of a cosine term. Now specify a w_thresh so that any surface with a w_max less than w_thresh with respect to every other surface can be discarded because it will have relatively little effect on the weakly directional component of light for any other surface.

We can now throw out any surface which is small enough with respect to all other surfaces, but calculating w_max for each surface from every other surface is an O(N²) problem. To avoid this cost, remember that we will only use the radiosity results when a ray has traveled a distance of atleast r_thresh. When this is the case, we can then calculate an area A_thresh where any surface smaller can be removed:

A_thresh = w_thresh * r_thesh²

Clusters of Small Surfaces (Simple Surfaces)

While small isolated surfaces will have little effect in a lower detail version of the environment, a cluster of small surfaces will. A simple way to account for the effect of clusters of surfaces is to replace them with a box that is in some sense energy equivalent. The box should provide an energy reflection distribution that is reasonably equivalent to the original surface cluster.

Defining a Cluster

The method for creating simplified equivalent clusters is shown in Figure 2. First, a cluster of small surfaces which could be clumped is manually chosen. A minimum bounding box is fit around the cluster. Each face of the box is discretized into patches, and then the algorithm cast a series of randomly selected rays perpendicularly through each face of this bounding box. The transmittance of the box is represented by shrinking the box according to the percentage of rays that pass through. The reflectance of each patch is set the average reflectance of the surfaces hit while firing rays through that patch.

Figure 2: Patches on the bounding box have reflectance equal to the average reflectance "seen" through the patch. The box is then shrunk to the volume of the enclosed objects. Note that a patch is the average color of the surfaces with no regard for "white space." Also note that a patch with no objects becomes "black" (has a reflectivity of 0). The fact that rays make it through is accounted for by the shrinking of the box.

Results

Notice that this algorithm requires that a user specify the clumps manually. Also, the hierarchy is only one level deep. These simple choices were made in part as a result of not understanding the options available at the time the research was began. It turns out that the results were quite favorable despite these limitations.

To evaluate the effectiveness of GSII, we built a test environment composed of 10,948 surfaces. These surfaces made up the objects in an office including thumb tacks, pens, a computer keyboard and a plant. The detail in the environment, as rendered by GSII, is shown in the three figures below. (Note: Click a figure to get a more detailed [larger] image.)

The radiosity pass of GSII always used the clumps in place of its represented primitives. This solution is at a loss of resolution but a gain in speed. The simplified environment solution was found in less than 1 hour whereas the original environment was halted after running over 142 hours.

During the ray tracing pass, values from the radiosity solution of the simplified environment were returned. However, if a ray leaves a surface with the intent of collecting diffusely reflected light and the surface intersected is too close, the ray assumes that the lower resolution of the simplified environment will produce an unacceptably coarse approximation and continues normally without returning the radiosity value. As a result, the ray tracing pass took longer than a standard hybrid solution but produced images with less artifacts. A classic hybrid solution took 219 minutes and GSII took 254 minutes or 16% longer. Considering both passes, the hierarchical environment saved time and produced a picture as good as or better than the classic solution.

The following figure show the output of the radiosity pre-pass which isn't meant for viewing; but only a low resolution first pass. (Note: Click the figure to get a more detailed [larger] image.)

Finally, the following figures compare a monte carlo path tracing solution (top left). to a full environment radiosity solution (top right), a classic hybrid solution (bottom left), and a GSII hierarchical solution (bottom right) . (Note: Click a figure to get a more detailed [larger] image.)

The monte carlo path tracing solution would take too long to complete and produces much more noise error for a given number of rays. The full environment radiosity solution would likewise take too long and produces too many artifacts for a given number of iterations. The hybrid solution is good, but its radiosity pre-pass was slow and it produces some annoying artifacts (such as the confusing reflections on the Georgia Tech wall plaque.) The GSII hierarchical solution saves much time in the radiosity pre-pass, and produce images with a total noise similar to the hybrid solution, but with less annoying local artifacts.

Acknowledgements

This work was supported by grants from the National Science Foundation and the Apple Computer Company.

For more information, please contact Holly Rushmeier, Charles Patterson, or Aravindan Veerasamy.