Radiosity Homework
John McCorquodale

Notes on Terminology

Path vs. Link: It's one of those old, happy principles of good software engineering to name things with abstraction-domain terms, rather than implementation-domain terms. A name should express what something is or does, rather than how you implemented the something. With this sensible idea in mind, I will consitently use the term energy transport path, or path for short, to refer to what the radiosity literature often calls a link.

Project: Refractive Solids

(we'll see if it's done by tonight)

Programming Assignment 6: Progressive Hierarchical-Adaptive Solution

Make your system progressive. Start with a large error tolerance and decrease epsilon over several to many iterations. Use an error metric that includes the radiance of the source patch. Describe the error metric, tell how you decrease epsilon, show an image for each of the iterations (refinement iterations, not gather iterations), and give the CPU time for each iteration.

Here are some images from a progressive radiosity solution. The idea of progressive radiosity is that instead of trying to fully refine a "dark" scene, then propagate all the energy around, you refine the scene a little, propagate the energy, refine it some more, propagate some more and so on.

Progressive radiosity is a Good Deal for several reasons. Numerically, energy propagation tends to converge to a correct solution faster because gross energy transport is carried out on a small matrix, and detailed matrices need only be iterated to perturb an already mostly-correct solution to completion.

More importantly, progressive radiosity lets us involve energy in our error terms. Whereas in assignment 5 we needed to specify separate target error values for form-factor error, visibility error and so forth, with knowledge of energy we can unify all these error metrics into a single currency, energy error. For a given target energy error value, we refine by considering sources of error on each path as follows:

• The L-infinity norm of the source's energy times the path's form factor and visibility represents the amount of energy error the receiver will see as a result of source cell aggregation. If this error exceeds threshold, the source is subdivided.

• The L-infinity norm of the form-factor times the path's visibility times the source's energy represents the amount of energy error the receiver will see as a result of form-factor error. If this error exceeds threshold, the receiver is subdivided.

• The L-infinity norm of the visibility times the path's form factor times the source's energy represents the amount of energy error some point on the receiver may see due to a shadow cast by an intervening object. If this error exceeds threshold, the receiver is subdivided.

Following are images of a five-stage progressive solution to the Cornell Box. Note that wholistically, energy error reflects the amount of confidence you can have in a cell's value at an arbitrary point within the cell. As you wish to become more certain of your continuously-varying solution, it is only natural that the cells become smaller.

		We start out by computing the maximum error in the scene and quartering it. This produces some refinement for form-factor error. Energy Error: 0.000592 Path count: 381 Path generation/refinement: 3s Energy Propagation: 0.246s

		On the next refinement, further form factor refinement occurrs for the hotspots on the walls, but more importantly, refinement to capture shadow detail from the room light occurs on the floor. Energy Error: 0.000148 Path count: 1,440 Path generation/refinement: 20s Energy Propagation: 2s

		The shadow refinement has reached the minimum cell size in some locations. Form-factor refinement continues on the walls in the hot spots. Energy Error: 0.000037 Path count: 7,155 Path generation/refinement: 1m 42s Energy Propagation: 13s

		Now we're getting a nice image. Most regions of fast perceptual change are reasonably well-refined, including shadow penumbrae. The wall/ceiling corners are beginning to refine to capture the dark areas there, but not excessively. Energy Error: 0.000009 Path count: 24,501 Path generation/refinement: 4m 50s Energy Propagation: 33s

(click for big images)		And just because I can, one more refinement brings the hotspots to the minimum feature size. At this point, the border between any two adjacent cells is almost imperceptable, even without a higher-order display mesh. Energy Error: 0.000002 Path count: 169,500 Path generation/refinement: 33m 50s Energy Propagation: 2m 8s

A Note on Performance

No real effort has been made to achieve efficient code or reuse values that are expensive to compute. Visibility terms are computed by drawing 100 samples from the source, and visibility errors are computed by computing 100 visibilities. Clearly this may be unnecessary computation. I estimate a factor of five speedup to be achievable with a solid day's effort.

For example, all form factors, visibilities and errors are recomputed on each refinement iteration. This is tremendously wasteful, because the amount of work done each time is a function of the total number of paths rather than the number of paths newly introduced. A few hours of reorganization will yield a factor of two speedup from this problem alone.

Programming Assignment 5: Hierarchical-Adaptive Solution

Compute a hierarchical radiosity solution with some initial tolerance on the error in the links using something like CreateLinks. Your error term should probably ignore energy. Solve the system using something like the GatherSweep routine.

Here are some images generated with a hierarchical matrix solver. Errors are static (energy-ignoring), which leads to excessive visibility-error-driven refinement in the Cornell Box image.

(click for big image)		Visibility Error (refinement for shadows) For each receiver cell / source pair, a visibility error term is estimated. This term represents the maximum possible difference between two visibility computations on the receiver. If a receiver has a great deal of visibility error, this can be interpreted to mean that the image of the source will be discontinuous as seen over the surface of the receiver due to shadowing by other objects in the scene. Here you can see receiver mesh refinement to capture the soft shadow cast by the green square. Different values for maximum tolerable visibility error result in different finenesses of refinement for shadows.

(click for big image)		Form Factor Error (refinement for hot spots) A form factor error term is also computed for each receier cell / source pair. This error term represents the maximum possible difference of two form factors from the source to arbitrary points on the receiver. Different values for maximum tolerable form factor error result in different levels of refinement to capture inverse-square dropoff and projected-area effects.

(click for big images)		Hierarchical Radiosity (distant source cell aggregation) If an source is far away, it appears small to the receiver and fine detail is not visible. We can aggregate a source's cells together into a larger conglomerate cell from the receiver's point of view. By setting a target source form factor, the receiver can aggregate the source's cells as appropriate to capture detail appropriate for its distance. These images are of a thin, left-facing light source illuminating the back wall (which is white). The right wall (which is green) receives only indirect light from the back wall. In the image on the top, the right wall sees the back as a single cell, whose average radiance is small. In the image on the bottom, parts of the right wall see the bright parts of the back wall and receive their light. A careful choice of target form factor balances realism with a potentially large number of cell-cell interactions. The thing to notice is that the green is brighter close to the back wall in the second image. The first image is less correct due to aggregation error.

(click for big image)		Cornell Box All of these techniques together produce a fun and exciting Cornell Box image. Note that this image has significantly more detail than the naive image below, yet took considerably less time to generate due to the hierarchical cell interaction. As noted, energy-ignoring visibility error drives excessive refinement throughout the scene. Paths generated: 210,018 Path generation/refinement: 29m 21s Energy propagation: 3m 7s Ray tracing: 6m 21s

Programming Assignment 4: Naive Matrix Solution

Create a matrix represented as links for the Cornell box. Solve the system of equations using either Gauss-Seidel or Jacobi. What was your termination criterion? Roughly how much faster was this than PA 1 (running time, not coding time)?

Here are two radiosity solutions to the Cornell Box. Energy propagation was terminated when no basis coefficient changed by more than 1/1000th of the light source intensity. Tracing was performed with a pinhole lens model and 16 regularly distributed samples per image pixel.

Basis:

Rectangular, constant

Iteration:

Gauss-seidel

Form Factors:

Exact node-to-polygon by Stokes' Theorem

Visibility:

4x4 regular grid of visibility rays from node to energy source

Paths:

1,807,680 energy transport paths were constructed, forming a non-hierarchical complete O(N^2) connection of 1,345 elements.

Runtime:

2h 30m (path construction), 18m (energy propagation), 2h (ray tracing) on surreal

(click for big image)		RGB Color Model Colors: Light: <1,1,1>, White: <0.8,0.8,0.8>, Red: <0.8,0,0>, Green: <0,0,0.8> Mesh: 16x16 (walls), 4x4 (boxes) Notes: The ceiling is a single mesh; the mesh elements partially eclipsed by the light source receive no radiation, hence the black border around the light.
(click for big image)		Spectral Color Model Colors: Physical Cornell Box spectra (gamma 2.5 for display) Mesh: 16x16 (walls), 4x4 (boxes), 9x9/4x4 (ceiling fragments) Notes: The ceiling has been (manually) split into four fragments which exactly border the light source in order to eliminate the icky light-source border.

Programming Assignment 3: Monte Carlo Form Factors

You can see the pictures.

Written Assignment 5: Talk About Progressive Solution Methods

Here's a no-frills writeup as a GIF or as PostScript.

Written Assignment 4: Compute some Form Factors

Here's a no-frills writeup as a GIF or as PostScript.

Written Assignment 3: Read a Paper

For this homework, I read a little paper on radiosity with higher-order bases. Here's a little informal review as GIF or as PostScript.

Written Assignment 2: Norms

This is a little homework about the definitions of p-norms and the local and global energy transport operators. The solution is avaialable as a GIF or as PostScript.

Written Assignment 1: Basis Functions

This is the homework on the basis functions. You can get problem 1 and problem 2 in PostScript for your printing enjoyment.

Alternatively, the individual problems are available here in GIF format (anti-aliased even!) so you can look at 'em in your little web browser: 1-p1, 1-p2, 1-p3, 1-p4, 2

Class Notes

1998 March 30: Basis Functions and Duals
1998 April 1: Implementation: Meshing
1998 April 6: Operators and Norms
1998 April 8: Meshing and Basis Implementation Complexities