I’ve had an idea floating around in my head for several months now, but evening classes, a hard drive failure, then a GPU failure prevented me from doing much about it until this weekend. First, a couple of screenshots of what I’ll be talking about.

Cornell box, I choose you!

The above screenshots are of real-time single-bounce GI in a static scene with fully dynamic lighting. There are 7182 patches, and the lighting calculations take 36ms per frame on one thread of an Intel Core 2 @2.4 GHz. The code is not optimized.

The basic idea is simple and is split into two phases.

A one-time scene compilation phase:

• Split all surfaces in the scene into roughly equal sized patches.

• For each patch i, build a list of all other patches visible from i along with the form factor between patches i and j:

  \[F_{ij} = \frac{cos \phi_i \, cos \phi_j}{\pi \, |r|^2} \, A_j\]

  where:
  F_ij is the form factor between patches i and j
  A_j is the area of patch j
  r is the vector from i to j
  Φ_i is the angle between r and the normal of patch i
  Φ_j is the angle between r and the normal of patch j
  

And a per-frame lighting phase:

• For each patch i, calculate the direct illumination.

• For each patch i, calculate single-bounce indirect illumination from all visible patches:

  \[I_i = \sum_j D_j \, F_{ij}\]

  where:
  I_j is the single-bounce indirect illumination for patch i
  D_j is the direct illumination for patch j
  

So far, so radiosity. If I understand Michal Iwanicki’s GDC presentation correctly, this is similar to the lighting tech on Milo and Kate, only they additionally project the bounce lighting into SH.

The problem with this approach is that the running time is O(N²) with the number of patches. We could work around this by making the patches quite large, running on the GPU, or both. Alternatively, we can bring the running time down to O(N.log(N)) by borrowing from Michael Bunnell’s work on dynamic AO and cluster patches into a hierarchy. I chose to perform bottom-up patch clustering similarly to the method that Miles Macklin describes in his (Almost) realtime GI blog post.

Scene compilation is now:

• Split all surfaces in the scene into roughly equal sized patches.
• Build a hierarchy of patches using k-means clustering.
• For each patch i, build a list of all other patches visible from i along with the form factor between patches i and j. If a visible patch j is too far from patch i look further up the hierarchy.

And the lighting phase:

• For each leaf patch i in the hierarchy, calculate the direct illumination.
• Propagate the direct lighting up the hierarchy.
• For each patch i, calculate single-bounce indirect illumination from all visible patches clusters.

Although this technique is really simple, it supports a feature set similar to that of Enlighten:

• Global illumination reacts to changes in surface albedo.
• Static area light sources that cast soft shadows.

That’s basically about it. There are a few of other areas I’m tempted to look into once I’ve cleaned the code up a bit:

• Calculate directly and indirect illumination at different frequencies. This would allow scaling to much larger scenes.
• Perform the last two lighting steps multiple times to approximate more light bounces.
• Project the indirect illumination into SH, HL2 or the Half-Life basis.
• Light probes for dynamic objects.

You can grab the source code from here. Expect a mess, since it’s a C++ port of a C# proof of concept with liberal use of vector and hash_map. Scene construction is particularly bad and may take a minute to run. You can fly around using WASD and left-click dragging with the mouse.