Radiosity lighting is one of those things that makes everybody sit up and say "oh, my." With a good level designer and a good texture artist radiosity can really look cool. Even if you're doing it all by yourself and you have no artistic talent at all, radiosity can still make any level look better. Radiosity is to 3D what mayonnaise is to a smoked turkey and roast beef sandwich with lettuce...and tomato...excuse me, I'll be right back.

Moo can cobe a fimple *gulp* You can code a simple radiosity calculator in a very short period of time. The only drawback is that the complexity of your calculator is inversely proportional to the speed at which it runs. I think that's one of Murphy's laws. The first step to setting up a radiosity calculator is to have an engine that can render light maps. "Ah, but if you don't have light maps, how can you tell if it's rendering them?" Use a hex editor and make some really simple grey scale light maps by hand to test. There is one major decision to make at this point and it is: how detailed will your light maps be? Quake had a maximum resolution of (I think) 32x32 which worked great until you had sharp contrasts on a big wall, it looked like a set of 'z's running down the wall. You can opt for larger light maps or (if you're feeling up to it) you can make different sized light maps for different polygons. Who knows, two or three different sizes might actually save you some memory.


Once you've got light maps working you've got a foundation to test on, so you can start writing the calculator. I'm going to break each of the major concepts into separate groups, take your time to eat a sandwich or something between them 'cause it's heavy stuff.

---

  The Radiosity Equation

The concept of radiosity is pretty easy. The reason more people haven't implemented it is because almost know one who understands it wants to talk about it, probably because they've all got high pay, high stress jobs that keep them far too busy. Sounds to me like someone's bought their silence, probably some of those same guys who claim the whole Roswell thing was to keep Stalin scared the US had UFOs technology. Oh yeah, it's all so clear to me now...

...My point being that once you get past all the integrals and the differential areas and a whole bunch of other fancy lingo it breaks down to this: For every point on every surface everywhere in the world find the total amount of light incident at that point. By incident I mean find all the light that is absorbed, reflected or emitted at that point.

Think about that for a minute: if you're going to find every point on every surface blah blah blah, how big are your points? I mean if they're infinitely small points then it would take forever to solve the equation. Uh oh. The solution is to break each surface into finite, bite size pieces called patches and average the light incident in each patch. Once all the calculations are done the the patches can be converted back to light maps and voila!

Before I show you how to figure out how much light travels from patch i to patch j there's one more very important point to touch on. As I said, radiosity works by finding the amount of light incident at every point everywhere in the world BUT it is supposed to find these values simultaneously. Stay calm, it's not as bad as you might think. When radiosity calculations were first invented there was a brute force solution - given that you had n patches you could build an n² matrix and (slowly) solve it until your first row or column had the light values at every point. In today's world of highly complex geometries and the ever greater push to wow people with high polygon counts, a matrix just isn't a practical solution.

Thus Progressive Refinement came to be. The idea works like this: Find the patch giving off the most light and send it's light to all the other patches. Repeat until the brightest patch is giving off less than some really small value. This means we have to keep track of both the radiosity (light incident) and the delta radiosity (amount of light being reflected) of each patch.

But is there anything else we need to keep track of? Take a look at the wall for a second. What is it you're seeing? The light hitting the wall or the light being reflected? If you said reflected, give yourself a back on the back. Careful, you don't break the arm! If we denote a patch n's radiosity as B_n then our equation so far is


Where Pj is the amount of reflected light, some value in the range (0...1). No sweat, right? Well, this equation would only work if every patch was exactly the same size, shape and distance apart. First of all, we can (for the most part) ignore a difference in shape but size is crucial. If you shine a light the size of a pin near a wall you'd see almost no change on the wall. However the opposite is also true, if you held a pin sized dot near a well lit wall, you'd see the dot very clearly. If we denote the area of a patch n as A_n then we've now got


Much better, but it still needs work. What we're missing is the Form Factor, the most powerful part of the process. If we weren't using patches, the form factor equation would look like this:


Yikes! Thankfully we're using patches so we can take out all the integrals and simplify to


Where

• cos( theta i ) * cos( theta j ) is the angle between the normals of the planes of each patch. This will make sure that a patch in front of a light source gets more light than one that's way off to a side. It will also make sure that a patch that faces directly into the light will get more light than a patch that's turned away.
• pi * r² accounts for the distance between the two patches. The further away, the dimmer the light.
• H( i, j ) is the visibility between patches i and j. If there is no line of sight between i and j then H( i, j ) would be 0. If there was full visibility between the two then H( i, j ) would be 1. Naturally, H( i, j ) can be some fraction in the range [0...1] if the line of sight is partially occluded (blocked)
• dAj is the area of patch j.

So our final patch to patch radiosity equation is


I know that seems weird multiply by dAj in the form factor and then dividing by dAj back in the main part of the radiosity equation but that's the way it goes. Personally, I'd just simplify and remove both references. Note that no one I spoke to would give me a straight, concise answer on what dAj was supposed to be in the form factor so it could be that I've totally screwed this up but if that were true my code wouldn't be working, would it? (:

/* Pseudocode for a simple radiosity calculator loop.
 * I highly reccomend using doubles everywhere, you
 * will need the extra precision.
 */
.
.
.
cPatch *pSrc, *pDest, *pNext;
double FF, deltaRad;

while( ( pSrc = FindBrightestPatch() ) != NULL ) {
  for( pDest = pPatchList; pDest; pDest = pNext ) {
    pNext = pDest->d_pNext;

    FF = FormFactor( pSrc, pDest );
    if( !FF ) continue;

    deltaRad = pSrc->d_deltaRad * pDest->d_reflect
             * FF * H * pSrc->d_area / pDest->d_area;
    pDest->d_deltaRad += deltaRad;
    pDest->d_rad += deltaRad;
  }
}
.
.
.

/* There's an extra multiply and divide that could
 * also be removed but I left it in because
 * src.area/dest.area is a ratio, it's easier to
 * understand what's going on.
 */
double FormFactor( cPatch *pSrc, cPatch *pDest ) {
  double   H, angle1, angle2, dist, factor;
  cVector3 vec;

  H = LineOfSight( pSrc, pDest );
  if( !H ) return 0.0;

  vec = pDest->d_center - pSrc->d_center;
  dist = vec.Length();
  vec /= dist;

  angle1 = vec | pSrc->d_pPoly->GetNormal();
  angle2 = -( vec | pDest->d_pPoly->GetNormal() );

  factor = angle1 * angle2 * pDest->d_area * H;
  factor /= PI * dist * dist;

  return factor;
}

/* Ambient term calculation.  Reflective term can be
 * used later to speed up ambient term updates
 * and prevent infinite looping.
 */
cPatch *pPatch, *pNext;
double ambient, reflect, area;

ambient = 0.0;
reflect = 0.0;
area = 0.0;
for( pPatch = pPatchList; pPatch; pPatch = pPatch ) {
  pNext = pPatch->d_pNext;
  ambient += pPatch->d_deltaRad * pPatch->d_area;
  reflect += pPatch->d_reflect * pPatch->d_area;
  area += pPatch->d_area;
}

reflect /= area;
// <= 0 - almost all walls black
// >= 1 - all walls white, infinite loop.
if( reflect <= 0.0 || reflect >= 1.0 ) return;

reflect = 1.0 / ( 1.0 - reflect );

ambient *= reflect / area;

Now that you know everything you need for your first radiosity processor, let's take a look at some ways to speed things up and avoid pitfalls.

---

  Patches: Triangles or Rectangles?

There are two basic options for splitting polygons into patches: triangles and rectangles. I tried triangles first because

• Their area is easy to calculate.
• Their corners are (relatively) easy to calculate.
• The triangle patches stay exactly within the boundaries of the region of the light map of the polygon they're associated to. Go ahead, say it six times fast, I dare you. P:
• When subdividing a patch into smaller pieces I could use the middle of each edge as the points for the new vertexes, giving me four new patches exactly 1/4 the size. The added advantage here was that if the original patch was very tall and very narrow (not good) then each of the sub patches would be 1/2 the size and 1/2 the width, bringing them gradually closer to right angled (better).

They were great for a brief time but I quickly realized why they weren't used in games like quake and half-life: They look like crap. So I switched to square patches and discovered many advantages.

• Square patches are even easier to subdivide.
• They don't require information on where the corners are, just the width and height so they save time and ram. Schwinnng! Party on Wayne. Party on Garth.
• Converting square patches back into light maps is a lot simpler - you don't have to rasterize triangles or worry about floating point imprecision.
• Squares are much better area to approximate over than irregular triangles, so results would be more accurate.
• They don't look like crap.

---

  Pitfalls

Radiosity really had me stumped at first and I kept screwing with just about every piece of code I could until I stumbled upon the solution and, of course, it wasn't where I expected at all. So here are a few of the setbacks I encountered and what to do about them:

• I have no idea what the hell is going on... Try starting with a simpler model. The first radiosity images were of a cube with a lit ceiling (think of the cheap halogen light panels at school). Always remember to start simple. After all, you did and look! You're almost nearly perfect! (:
• Everything is way too dark, except the light source! This could be one of two problems:
  1. Your patch reflect value is way too low. I find a value of around 0.55 to 0.75 in the models I've tested so far.
  2. Your patches are too big. The smaller the patches, the more accurate the image. A good way to gauge the amount of inaccuracy is to sum the total light that actually reaches the destination patches and compare that to the amount of light that left the source patch. You'll see that the number starts frighteningly large and drops in a k/n² fashion if your patches are too big.
• Things are so SLOOOW! The greater the detail, the slower the calculation. Et la vie, elle pu de temps en temps. Squeeze every possible ounce out of your optimizations as you possibly can.
• There's a tiny patch in front of a big patch and the big patch is completely black! (or)
• There's a tiny patch in front of a big patch, why doesn't the tiny patch cast a shadow? Your line of sight test isn't catching this situation correctly. Or perhaps it is, but not returning the correct fraction. It's this visibility problem that keeps scientists employed.

---

  Faster, faster! OH, YES! YES! *ahem*

How to go faster can be summed into three categories.

Adaptive Subdivision is a really neat trick. Instead of cutting your initial polygons into teeny tiny itsy bitsy eeny weeny (yellow polka dot bikini...) patches try starting with somewhat larger patches. When you're sending light to the patch, check to see if the radiosity gradient is too high across the surface (if the change in light is too high). If it is, split the patch into smaller pieces.


Elements are another good idea for your calculator. Each element contains a certain number of adjacent patches. Only send from the elements but catch the light with the patches, which then report the change in delta radiosity to their element. I made one element for every four patches, thus saving myself 1/4 the work. Granted, it will widen the margin of error but by so little that it shouldn't matter. Also be careful that when you design your elements that they won't cause problems with adaptive subdivision, I had trouble getting them to play nice together.

Hemicubes offer a distinct speed improvement and are by far the most touted, though why this is I don't really know, they seem way too prone to error for my taste. I'll write more about them after I get a chance to try them.

---

Wasn't that fun? I didn't think so either. I finished my first radiosity calculator in nine days without eating, sleeping or taking care of personal hygiene 'cause I had a deadline to meet. Can you tell it's 0400 where I live?

...Since we've been talking about reflective surfaces, it seems only appropriate that we delve into mirrors next!

Back to the top

---

PREV: Possible Visible Set
NEXT: Mirrors