Indirect Lighting for Building Interiors

It's time to discuss indirect room lighting. This is turning out to be a long and technical post. I've scattered some screenshots around in there somewhere for those of you who don't want to read the wall of text. I'll also add Wikipedia links for some of the technical terms.

I want to improve the quality of lighting inside my procedural buildings. Most of my previous screenshots have shown the combined contributions of three types of lighting: 

• Direct lighting from room ceiling lights and lamps, pointed downward in the lower hemisphere as a 180 degree spotlight so that I can use a single shadow map
  
• A very weak sky lighting representing light coming in through windows, which at least tints walls different colors in otherwise unlit rooms
  
• A fake constant ambient term that varies by floor/basement/attic

This looks reasonably good in well lit rooms where the lights are on. However, rooms with their lights off have very flat colors and all surfaces tend to look the same. This is both uninteresting and unrealistic. Also, places in shadows and along the upper wall and ceiling of lit rooms have very little indirect light and suffer from the same problems.

I've been trying to add proper indirect lighting support for some time now. Has it been as much as a year? Maybe. The difficulty is getting a good quality of lighting with low noise and low light leakage through walls, and having this lighting update in buildings as the player moves around without causing lag and hurting the framerate.

I consider this a solved problem for fixed size static scenes in 3DWorld. I can precompute lighting offline, save it to disk, and reload it in under a second when the scene is loaded in 3DWorld. This works well on scenes of moderate complexity such as San Miguel. I even had this working for my office building basement using player controlled dynamic lights, and in the static Sponza scene all the way back in 2014. This system worked by sending millions of rays from the sun, sky, and local point lights into the scene, calculating their reflections/refractions, and accumulating their paths into a 3D volume texture.

Why can't I use the same solution here? Well, in theory I can. The only problem is that the player has to wait 20 min. for the lighting to be computed before entering a building. [Technically we can also let the player enter the building and wait 20 min. for lighting to appear.] That doesn't work very well in an open world game with thousands of buildings, does it? Now I can hack things and use a few tens of thousands of rays rather than millions to get the computation down to a few seconds. My first attempt at this gave me the following results:

Failed attempt at indirect lighting on building interiors. Did I show this screenshot in a previous post?

That's actually a really neat effect. It looks like the walls are made of dirty aluminum foil due to the way their normal maps interact with the lighting. That's not the look I was going for here, but I can't pass up the opportunity to show off my accidental artwork. I was able to fix this of course, but the floor didn't get much better than that black and gray pixelated mess you see above. So I could get noisy garbage lighting in a few seconds, or wait tens of minutes to get something that looked nice. Neither case was acceptable, so I lost interest in this last year.

... Wait, that screenshot is from Feb. 2020. So this was over two years ago? Wow, I didn't realize it had been that long. Surely I've gotten a new computer since then, it's super fast, and that solved all of my problems, right? Nope, same computer. It's too much effort to install all of my software and development tools on a new PC.

Optimizations

Anyway, I got back to working on this a few months ago. There are actually quite a few optimizations I can use to speed this up and get more rays (= less noise) in less runtime. I can also reserve one of my CPU cores for drawing the scene rather than using them all for lighting computation, which allows me to get a reasonable framerate for walking around in the building while the lighting is being computed in the background.

I'm storing precomputed lighting values in 3D voxels (volume elements). Each fragment (pixel in non-OpenGL terms) of drawn geometry queries its indirect lighting from the nearest voxel, biased in the direction of the surface normal. One of the reasons why tracing light rays is slow is because I need to accumulate light into all voxels along the entire path of the ray rather than only at the hit points. This nearly doubles runtime, especially for long rays in open space when using a fine voxel grid. I need to store lighting data for the empty space in a room to get proper lighting on dynamic objects such as people, animals, and whatever items the player moves around. These objects aren't present during lighting computation, so there are no ray hit points associated with them.

One of the biggest optimizations I discovered is to only calculate lighting on the floor of the building the player is on. It seems so obvious now that I think about it. This cuts the number of active light sources by a factor of 10x for a 10 story building, which is quite good. But it gets better than that! I can build the 3D acceleration structure I use for ray intersection checks for only objects on the current floor rather than the entire building. I don't get another 10x runtime reduction though, because ray query time scales as the log of the number of objects in the bounding volume hierarchy. The actual speedup is more like 20x for a 10 story building. That's still pretty good though. The cost I pay for this decision is incorrect lighting on floors above and below the player when looking up or down stairs.

Another related optimization is that I only need to store the lighting for a few floors of one building at a time, and I only need to draw it for the floor the player is on. This reduces memory usage on both the CPU and the GPU. I pass the 3D bounding cube of the current floor into the fragment shader and use my original constant ambient term rather than the indirect lighting calculation for anything drawn outside the current floor. This way the slice of valid indirect lighting can follow the player around and everything else looks as it did with indirect lighting disabled. I was even able to go back and further optimize ray intersections to simply clamp rays to the range of z-values (altitudes) spanned by the current floor since any rays extending outside the range are ignored anyway.

I chose a range of 5 floors to store in memory. This allows the player to walk between the floors of houses without invalidating lighting data along the way, since all floors can fit within this range. If I had used only one floor, the lighting would need to be rebuilt every time the player walked up or down the stairs. Note that some houses with both basements and tall attics can exceed this range and require some amount of re-computation. Office buildings can be as high as 20 floors and won't all fit in memory at once. I decided to disable lighting updates while the player is in an elevator so that lighting is not unnecessarily computed for floors the player doesn't even stop on. Lighting updates will begin when the elevator door opens, where the first light to be updated is likely the one on the ceiling in front of the elevator.

The next step was to prioritize lights that have more of an effect on the area visible to the player. This includes weighting based on lights near the player and in the view frustum, and lights inside/affecting the room the player is in. This change allowed me to generate lighting almost immediately for nearby rooms, have the lighting follow the player around as they moved from room to room, and compute lighting for rooms not yet visible in the background when the player stops.

Noise

Those optimizations, plus some smaller ones that I won't list, allowed me to have near realtime indirect lighting. It works well for rooms that are fairly well lit. Unfortunately, it still has a lot of noise in rooms that are less well lit due to the relatively small number of rays reaching these rooms from light sources on the ceilings of other rooms. These rays take several bounces to get there. The fewer ray samples there are, the higher the variance, and this leads to random noise. Here's one example:

Indirect lighting in a room with the light off. All light comes from other rooms, most of it indirect. Lighting is noisy in cases like this.

It's noisy, but it's fast. Getting results of this quality before these optimizations involved suffering through a minute of low, laggy framerate before any indirect lighting appeared. If I increase the number of light rays by 10x I can almost completely remove the noise, but the player must wait for the lighting to appear again. It's a typical runtime vs. quality trade-off. I would call this partial success.

Indirect lighting in a kitchen with the lights off again. The area under the chairs is dark.

It's unclear if this solution is worthwhile in these situations, but it appears to work great in basements, parking garages, and attics. There are fewer objects and no windows, so it tends to be faster. Basement lighting is normally uniformly dark, so having indirect lighting is a huge improvement even if it's noisy. The same is true for attics. I added config options to only enable indirect lighting in basements and/or attics where it's faster and more effective. I may make this the default going forward.

Light Leakage

I ran into another problem: light leakage. Indirect lighting is stored in a 3D grid of equal size voxels. If a voxel is wider than a wall, the floor and ceiling on each side of the wall often query the same voxel. This may result in light areas around the edge of a wall in a dark room where the adjacent room has a bright light. Similarly, there may be dark edges around a wall of a lit room next to a dark room. I can't make walls thicker without breaking other parts of building generation, and I can't make the voxels too small due to computation time and memory constraints. Fortunately, my optimization to limit indirect lighting to the current few floors avoids this same problem in the vertical direction involving the ceilings and floors.

If you look closely at some of the screenshots in this post, you can see bands of bright or dark areas around the edges of walls, ceilings, and floors. There are similar dark edges around the curved sides of ceiling light fixtures that are turned off. It's not too bad after I made a pass at tweaking constants in the code.

Indirect lighting in a basement room. There's less noise when the light is on. You can see a red tint on the ceiling from light that bounces on the red rug on the floor. The man standing in the room has indirect lighting as well.

 

Here's another basement where the noise is almost undetectable. It helps to have lit rooms with dark ceilings. Also, I added a screenshot of a parking garage with cars.

Indirect lighting in the basement makes it easier to see the pipes near the ceiling. Without it they're in shadow and appear very dark. You can also see some darkening above the water heater.

Parking garage with indirect lighting. The indirect component makes the pipes and ceiling easier to see, and softens the shadows under the cars.

Windows

So far I only discussed indirect lighting from room ceiling lights and lamps. There's another source of indirect lighting. Can you think of it? I'll give you a hint: Bedrooms shouldn't be dark like basements when the light is off during the daytime. That's right, I need to include the indirect lighting from the sun (and moon) coming in through the windows. I can treat each window as an area light source and generate rays through it that enter the building. This works well, but sadly now there are more than twice as many light sources to handle in a typical house. On top of that, windows seem to need more rays to reduce their noise, so we're back to having a slow lighting solution. Fortunately, it's still much faster than it was before.

Bedroom with the ceiling light off. All light comes in from the windows. You can see the soft shadows under the bed and dresser.

Bedroom brightly lit from both the ceiling light and the sun outside.

Here's a comparison of the same room with and without indirect lighting. The second image has brighter walls with more color variation and fewer shadows.

Bedroom with direct lighting from the ceiling light (pointed down) and a constant ambient term.

Bedroom with both direct and indirect lighting from the ceiling light, and indirect lighting through the windows.

I'm not quite sure why there's an orange tint around the light on the ceiling. Maybe it's because the color of the light is somewhat orange-ish rather than completely white. It could be that the color is saturated to white in some areas but not around that cylinder. Or maybe there's an orange rug above it in the attic and I'm getting some sort of incorrect light bleeding from that. I have no idea. I should go back and revisit this, if I can manage to find that house again. (It's not one of the houses next to the player's starting position.) 

[Update: I found the house again. It looks like the light itself is yellow. It appears white because the direct + indirect/ambient saturates the colors to white, possibly because the gamma correction is off. The light shines downward with a 180 degree field of view in the bottom hemisphere. Therefore it doesn't shine directly on the ceiling. The lighting near the light in the center of the ceiling is yellow light reflected off a dark brown floor, plus the edges of the light fixture itself, which I guess results in that shade of orange.]

Dynamic Lighting / Player Interaction

So we're done, problem solved, right? Not quite. Up until now I've treated buildings as static. In reality the player can turn lights on and off, open and close doors, and move furniture around. All of these things will obviously affect the indirect lighting. As you might expect, adding support for dynamic indirect lighting introduces a huge amount of complexity. I haven't quite figured everything out yet.

Let me start with turning room lights, closet lights, and lamps on and off. It can either be the action of the player, the building AI people, or one of the new motion detection + timer lights. (I added that last one to automatically turn lights on and off in some office buildings.) This also includes the player opening and closing bedroom window blinds, which I have somewhat working. The full precomputed lighting on a building floor is the sum of the indirect lighting from each light source. This means that turning a light on is as simple as adding a new light to our queue of lights to process that will be accumulated into the total. Turning lights off is more complex. It can be implemented by subtracting light by using a negative intensity ray, but we need to be careful to make the rays deterministic so that the positive and negative rays will exactly cancel each other out. A lack of determinism leads to - you guessed it - more noise. Finding a deterministic solution that worked across multiple threads proved to be difficult.

One possible optimization is to cache the contribution of each light source separately. This avoids re-computation when the player turns lights on and off, and also solves the determinism problem. The downside is that this is both complex and takes significant memory. The light volume itself consists of 128x128x128 = 2M voxels in {X, Y, Z}. Each voxel holds a floating-point number for each of the {red, green, blue, intensity} components of light. 2M * 4 bytes * 4 components = 32MB of data. A single building floor can contain as many as 100 lights, including ceiling lights, closet lights, lamps, and windows. We clearly can't be storing 3.2GB of cached data across all lights. How can this be improved? Most lights will only affect a few rooms on a single floor rather than the entire 5-story horizontal slice of a building. If I was to compute the bounding cube of influence of each light, it would be constrained to a small subset by the walls, the floor below, and the ceiling above. This would reduce memory usage to as low as 1MB per light. That would still be 100MB of data for 100 lights, but this number is reasonable.

I was pretty happy with the system I had in place for recomputing indirect lighting when room lights were toggled by the player. I considered doors next. Opening and closing doors is more complex because they can influence multiple lights that illuminate the room on each side of the door. When a door is closed, light rays that previously reflected off the door back into room will instead exit that room and add light to the adjacent room. This requires the indirect accumulation to shift between the two rooms, and possibly other nearby rooms connected with open doors.

It was easy enough to determine which lights are affected by which doors by using the room connectivity graph. The hard part was figuring out how to correctly rebuild the ray spatial acceleration structure when a door opens or closes. The problem is, indirect lighting ray tracing is running in another thread in the background. I can't simply rebuild the data structure while it's being used. Instead, I have to wait for the current light's computation to finish, or kill it if the current light will be invalidated by the door state change. Then I have to remove the contribution of each light that will be updated, using the door's original state. Next, I can update the door's state and rebuild the acceleration structure. Finally, I have to re-add each light's contribution using the door's new state.

This sort of works, in theory. In practice it's problematic because I need to update the door's open/closed state in the drawing code immediately, otherwise it will look odd if the door doesn't move until the lighting is completed a few seconds later. So I have to use two different door states: first the drawing state changes, then the lighting state changes once old lights have been removed. To make matters worse, what happens if the player toggles the door back to it's original state before the lighting has been updated? Or what if the player opens or closes some other door that affects the same light(s)? I can build a queue of door state changes and light update passes, but the system may not be able to keep up with the player. Even if it can keep up, it's probably going to be wasting a ton of CPU cycles recomputing everything.

I experimented with this for quite some time, but was never able to get it working correctly in all cases. Instead I left it as-is, where it only works correctly when the player opens or closes a door when there's no current lighting calculation and no pending light updates. Otherwise the lighting is wrong in various ways. Then I later disabled door updates entirely because the failure cases where light or darkness appeared from nowhere caused too many issues. Door state changes now only have an effect if they happen when lights are off, because the new door state will be picked up and used when lighting is recomputed as lights are turned on.

Doors are trouble for other reasons. Remember the potential light caching optimization I mentioned a few paragraphs above? Well, any door open or close events will have to invalidate cached lights whose area of influence cubes intersect the door. (In fact, any player movement of furniture should affect lighting as well, but I'm going to ignore that for this discussion.) It's only worthwhile to cache lights if they remain valid for multiple on/off toggles without a door state changing in between. So, which happens more frequently, a light toggle or a door open/close? I'm not sure. Given the fact that door state changes affect multiple lights, my guess is that light invalidations are more frequent than light switch toggles, meaning there's not much benefit in caching per-light data. This is why I haven't yet implemented light caching. The cost of high memory usage, code complexity, and frequent invalidations combined to likely outweigh the benefits.

Indirect lighting is still a work in progress. I have it disabled by default and can toggle it with a key press. I'll probably enable it for basements and attics where it works best, and for screenshots. If I can find more ways to either improve computation time or reduce noise then I may enable it by default later.

The technical reader may wonder why I don't simply use screen space ambient occlusion. I've considered this approach, and done some experiments, but I found that it doesn't work very well in this application. First, I'm using Forward+ (tiled forward) lighting and don't have normals available in the fragment shader. This makes SSAO more difficult to implement. Also, there are lots of partially transparent materials (windows, glass tables, car windshields), alpha masked leaves and grass, ray marched clouds, and various other drawn objects that are unfriendly to SSAO. Besides, it's not a physically correct approach and it doesn't add neat effects such as color transfer between surfaces.

The source code for building lighting can be found here: https://github.com/fegennari/3DWorld/blob/master/src/building_lighting.cpp

To end, here is a video showing me walking through a house while turning lights on and off.