NEP Lighting Engine Part 2: Diffuse Light
This is the third installment in a four-part series on the lighting engine in my upcoming indie game, Non-Essential Personnel. If you ended up here first, maybe try starting at the beginning instead.
What do I mean by diffuse light?
In the last post, I talked about the "diffuse" component of the Blinn-Phong lighting model, and how we used some hacks to make it look better without modeling complicated atmospheric effects. In this post, I'll use "diffuse light" to mean something similar, but slightly different. This time I'm going to talk about actually diffusing the light through the game world. Meaning, for every position in the world (i.e., a block) we need to know what light is shining there. We figure that out by taking light from each light source and spreading it around (i.e. "diffusing") it to nearby places.
One really easy way to visualize how this works is to look at flowing water in everyone's beloved building game, Minecraft.
Flowing water in
Minecraft. There's one water "source" block at the center which flows (i.e.
diffuses) into neighboring blocks. Each time the water flows to a new block, it loses a
little bit of height. Water stops flowing when there's not enough water height left to
spill over to the next neighbor.
NEP's lighting system works a lot like that, except instead of water height, we're diffusing light intensity. The source block has some initial intensity and neighboring blocks inherit some of that intensity depending on how far away they are.
Diffusing light intensity
The main goal for the diffuse lighting system is to figure out where all our light sources are and how much intensity diffuses to each block. In a voxel engine, every block could potentially be a light source, so we could be dealing with thousands of light sources in a single scene.
In a perfect world, each block would keep track of a list of all the light sources that illuminate it. Then when it's time to render that block, we gather up all the light sources and send them to the shader. The trouble with this simple approach is, depending on how far each light can shine, the list of lights shining on each block could be huge! We can only make the light radius so small without making the game look bad, so storing all the lights in range of each block is a very very bad idea.
Gratuitous
infographic. If our light radius is 1 block, then only 4 lights can shine on each block.
That's not so bad. But if the light radius raises to merely 8 blocks, that number shoots
up to 144. If you want a reasonable radius of 32 blocks, you'd need to store 2112
lights. 32 blocks might seem like a lot, but exponential falloff makes most of that area
very dim. Unless your game is Captain Sunglasses and the Adventures of Not Seeing A Damn
Thing, this approach isn't going to work.
So let's do something crazy and limit ourselves to just one light per block for now and see how far we can get with that. That way we only need to keep track of the closest light source for each block. Turns out, that's exactly what Minecraft does with its water too.
Two water
sources colliding in Minecraft. They don't pass through each other. They just meet in
the middle.
One block, one light source
Now that we've solved the multi-source problem by completely ignoring it, we can figure out how to actually implement diffusion with logic instead of pictures of water. One way to do it uses a real workhorse of computer science literature called Breadth-First Search. Those in the know lovingly refer to it as BFS.
The basic idea of BFS on a grid of blocks is to start at a block (the source), make a list of all that block's neighbors, and then visit those neighbors. Then we visit the neighbors' neighbors, and the neighbors' neighbors' neighbors, and the neighbors' neighbors' neighbors' neighbors, so on until we find a reason to stop.
Sounds perfect for flowing water or light diffusion, right? That's because it is. =)
The's one catch though. If we use the most obvious definition for neghboring blocks (a "neighborhood"), and the simplest reason to stop, our lights look really crappy.
With just four
neighbors, dropping a constant amount of intensity at each stop, and stopping after we
pass a fixed number of neighbors, we get very pointy lights.Simple is great. I love simple. But sometimes it just doesn't look good and we have to try harder. Turns out, to make the light look perfectly radial, we have to give up on our BFS idea. BFS requires that we only compare blocks to their neighbors, but a perfectly radial light would mean that every block compares to the source block. Sooo.... we can't be perfect.
Release the hacks!!
We can make our light more round-er-ish by using this one simple trick. You won't believe what happened next!
By using eight
neighbors instead of four, and switching to a weighted distance, we get rounder lights.
Instead of dropping a constant amount of intensity at each step, we drop intensity in a
5:7 ratio depending on which neighbor we used. This is one ratio that very closely
approximates the real straight-line distances to the source block. We can't match the
ratio perfectly because math (square roots are evil), but we can get pretty close.
What about solid blocks?
Solid blocks are a bit of a stumbling block.
Hah!
I totally intended that pun. Anyway...
We don't want to let light pass through blocks, yet we still want to light up blocks a little bit so we can see them. Seems like an unstoppable force just met an immovable object, so what do we do?
The way NEP deals with this is to give up on the idea of immovable objects. Unstoppable forces FTW!
Meaning, we'll actually let light pass through solid blocks. Again, it's not realistic. It's dirty. It's horrible. It's a total hack. It just happens to look pretty good. We need to be careful though and not let light travel back into empty space again. That would look too weird.
On the left is
the obvious don't-let-light-pass-through-solid-blocks idea. But then we can't see the
solid blocks! If we do let light pass through blocks (middle), then the blocks are too
light-ey. On the right, we make it look better by penalizing light intensity that
travels through blocks. Making light fall off more quickly inside of blocks looks pretty
good.
Wait a minute...
The lights in that last image look really smooth, but the lights in all that madness about who makes the best neighbors look like a blocky mess. Also, I don't see the spikes coming out of the light source anymore.
I know, right? Shaders are AWESOME!!
One trick I did to get rid of the blockiness is to use bilinear interpolation between intensities of neighboring blocks. That's a pretty standard technique, so I won't discuss it here. I wanted to get fancy, so I actually tried bicubic interpolation thinking it would look even better. It actually looks worse than bilinear interpolation in this application because of overshoot. Higher degree polynomials are usually more awesome (unless you have to solve them), but not this time.
The other trick I used will probably take the other half of this blog post to explain.
Which brings me to...
Diffusing light direction
One way to smooth out the lights is to make sure each pixel is lit slightly differently rather than have all pixels in a block look the same.
Fragment Shaders To the Rescue!
We already did this for the light intensity by using bilinear interpolation, but intensity is just one component of the light source. There's also color and direction. Color is pretty self-explanatory, so I won't say much about it here. There's a lot we can do with the light direction though.
If we just think about a light whose source is a point, and we give that point to the fragment shader instead of just sending a per-block intensity, the shader can compute a unique light direction and a unique intensity for each pixel. This makes the light look really smooth and gets rid of those spikes you saw in our blocky light sources above. We're not just going to ignore all that work we did computing block intensities though. We'll use them again later. Hang on.
Once we have a position for the light, we just need to tell all the lit-up blocks where it is. For this to work, we just need a notion of diffusion for light directions that works like diffusion for light intensities.
The simplest way to diffuse directions from source blocks to other blocks is to have each block merely "point" to the source block. Call it a lit-by pointer. That is, when the BFS visits a neighbor block, the neighbor inherits the source of the current block. To make the induction work, we'll just have the source block "point" to itself. That means when we're lighting a block, the shader will get the position of the light at the source block and its source intensity (i.e., how bright the light is independent of distance). Then the shader can do the distance- and orientation-based intensity calculations per-pixel and make some really smooth-looking lights.
On the left is our
old blocky light source. On the right is the new per-pixel shaderific light source.
So what about all the per-block intensities we just ignored?
There's another better use for that information than directly lighting blocks. It's really useful for computing shadows!
What?! Shadows?
Yeah, shadows!
Check this out
Since we designed our light spreading as a diffusive process, that means light intensity gets to "flow" around obstacles like solid blocks.
Well... it doesn't flow like solid blocks. That would be silly. Solid things don't flow. At least, not very fast. The light flows like water, but now I'm just getting distracted...
Or it can "bend" around corners if you like that idea better. With this idea in mind, a shadow is just a spot where the light gets darker because we've turned a corner. If we want to make shadowed areas darker, then we just need to go hunting for corners.
This one's
complicated. I'll talk about it below.
On the left side, we have our scene with some solid blocks shown as red boxes. Without any other changes, we're still sending the light source position to the shader for the empty space "behind" the solid blocks. It doesn't look good. The "behind" space should be darker somehow.
The yellow lines in the center section show the search tree induced by the BFS. In other words, for each block, the tree shows from which neighboring block it inherited its properties. If we want the "behind" blocks to look darker, we need to send them different lighting information somehow. For the blocks that are "behind" something, we need a way to detect the corners of that something.
One way to do that is ray tracing. Specifically, for 2d block worlds, Bresenham's algorithm is a really cheap and easy-to-implement ray tracer. If some block can't "see" the light source, then there's gauranteed to be some block in its tree ancestry that can, since the whole tree is rooted at the light source. That means the first block in the ancestry that can't "see" the light source is the "corner."
What we'd really like is to do is occlude some of the light in the subtree of the corner. i.e., the blocks that are "downstream" from the corner. We don't want to occlude all the light though, because our good friend atmospheric scattering really can send some light around corners. One way to do this is to put another light source right at the corner that's just a bit darker than the original light source should be at that spot. Then we just force the subtree to be lit by that light source instead of the original one. We can just set the lit-by pointer at each block to the corner light instead of the actual light source!
This is the part where we can use our original diffuse intensities that we ignored for a bit. To calibrate the source intensity of our hacky "corner" light source, we use the diffuse intensities, but with a small penalty so it looks a bit darker.
All that's left is to make the whole process of finding corners recursive and then we can get fancy compound shadows. Easy, right?
But the world has more than one color
As long as our world is only lit by one color, we're done! For sky light, that works pretty well actually. If our game world has more than one color though (say colored light fixtures or lamps), our assumption that each block should only care about the nearest light breaks down Really Fast. With multiple colors, we really do have to start blending multiple light sources onto a single block or the game will look really really bad. To learn how to do that, check out the final installment of my lighting blog post!
