Global Illumination

The term global illumination refers to a family of techniques for computing realistic lighting in computer graphics.

I spent some time experimenting with an approach to global illumination called discontinuity meshing, many years after it had gone out of style and had been replaced by other superior techniques.

A discontinuity mesh encodes the sharp discontinuities in lighting that occur at shadow edges by inserting new vertices into a polygonal model.

I wrote a program that, given a mesh of triangles and a polygonal light source, calculated the new vertices for the shadow edges and added them to the mesh. The program then calculated the indirect lighting for the scene using an algorithm called photon mapping. The indirect lighting values are also assigned to the vertices, just like the direct lighting and the shadows.

Photon mapping provided the secondary illumination caused by light bouncing from one surface to another.

There are many other approaches for dealing with shadows and global illumination. For example, several modern global illumination techniques encode the shadows and global illumination in texture maps, rather than in the mesh vertices. The illumination can also be computed on a per-pixel basis.

The lighting in the discontinuity mesh approach is camera-independent, and no texture maps are required.

I was attracted to the idea of solving the 3D geometric problems involved in computing the vertices for the shadows. I’m not sure why this was. It just seemed like a neat problem, and something I wanted to learn about.

While implementing the project, however, I discovered that computing a discontinuity mesh reliably for an arbitrary input mesh is an extremely hard problem. I spent months debugging errors in the output mesh that would turn out to be caused by subtle floating point roundoff issues. Infinitesimally small geometric errors could easily lead to huge display artifacts, and they were very hard to debug.

I wrote about 70,000 lines of code for the project, 25% of which were unit tests.

The project was a great learning experience, but I realize now why research in this area was abandoned. Discontinuity meshing suffers from many of the same problems as CSG operations on polygonal models, like ambiguous geometric edge cases and unresolvable floating point issues.

I did create a few interesting pictures as test cases, however.

Return to Drew’s Home Page