Voxel Engines, Lighting, Shadows, and Occlusion

SteamShards early alpha: Directional light, no shadows

Game-engine lighting is a complex subject. If you're a graphics programmer, though, it's ... standard fare. It's what you do. Lighting, shadows, occlusion, and effects dominate the job.

But voxel worlds -- especially sandbox voxel worlds, where any block anywhere can be added or removed at nearly any time by any player -- are entirely different than normal graphics programming. That's a lot of any. The rub is that the precalculated lighting techniques common for fixed level designs don't work too well when you've got tens of thousands of voxels on the screen. How much can you reliably recalculate whenever something changes? It's worse in a multiplayer world, too, where it's not just the player but any player out there changing stuff. And procedural terrain generation means you can't have an artist go in and place lights and sampling probes by hand.

This is the problem. How can you do effective lighting under such conditions? All geometry is effectively dynamic, and there's tons of it. All lights are effectively dynamic, and if you've seen Minecraft castles lit for night, you know there's tons of torches everywhere. Now you need code to handle what's normally beautified by an experienced, talented artist.

With and without directional lighting

So let's start with technique #1: directional lighting. This adds a huge amount of reality to a voxel world. The first screenshot has only directional lighting; the second screenshot (here on the left) compares a scene with it and without it. The effect is even more useful when you're playing the game, as you quickly get used to where the light is and what different shades mean in terms of how the world is shaped. Directional lighting is so profoundly helpful that it's difficult to find screenshots that don't have it, or a more complex variant.

Technique #2 is shadows. There's many different shadow techniques, and most of them are great when you have a few lights in the scene, or a few major lights. In outdoor worlds, sunlight is one of those. It's very common to see shadow maps used even in games where a lot of the geometry doesn't even cast shadows. You know World of Warcraft? Big game, right? Tons of great art and some fancy lighting effects -- but things like tables and chairs cast no shadows. Yet the players do, and obviously that's enough for them.

Early Minecraft Lighting: Directional light + shadows

The third screenshot (here on the right) is a very early build of Minecraft, which uses a simple lighting model that just has a directional light (the sun) plus voxel-based shadows. Those shadows give a lot more life to the game, compared to the first image at the top of the page.

There are some other texture tricks that one can add: bump maps, specularity maps, emissive textures, or extreme tricky stuff like ambient occlusion, depth-of-field, "god rays," bloom, and so on. I'm gonna skip most of these and stick to one, because of its relevance to voxel worlds: occlusion.

Voxel Occlusion in SteamShards

Advanced lighting models try to model "radiance." In effect, what it models is the fact that real light bounces off of surfaces and lights everything else. Surfaces aren't lit just by direct light, but also by all of that indirect light.

On a bright day here in real life, interior rooms still appear well-lit not because of direct sunlight but because what incoming sunlight there is (even none!) bounces around everywhere. Just having a window open to the sky can provide enough indirect light to effectively illuminate an entire room -- and even the next room over.

Occlusion is somewhat the reverse of radiance: it models where light isn't bouncing from. Corners are darker than the middle of walls because the adjacent walls (and floor or ceiling) block light that might otherwise come in. This final screenshot is another old screenshot from SteamShards, one with an early implementation of a shadowing algorithm. There's no directional lighting here -- everything is just shadows and occlusion. Each vertex looks at the four voxels in front of it. The more of them that are filled, the darker the vertex.

There's troubles once one adds in subvoxel shapes, however, and that's one of the issues that I'm currently addressing. The technique I'm using is Pretty Dang Messy™, but I'll write it up here when I'm happy with it!

Obi-Wan Errors and the Subvoxel Blues

I just discovered another glitch in my voxelizing algorithm. In some cases, I was seeing holes in geometry, like specific bits of a voxel weren't being rendered.

This is ultimately because I very aggressively strip out voxel sides that can't be seen. If a voxel is blocked on one side by another voxel, then there's no reason to render that face.

First note that I cut the world up into 16x16x16 chunks in order to submit reasonable amounts of geometry to the rendering engine; allowing me to clip what's not in front of the camera, and meaning that I don't have to do too much work whenever the user edits terrain -- by mining into the ground, placing fortifications, or just using the tools to do some terraforming.

OK. Now. Take the naïve case: in a 16x16x16 chunk, and assuming it's solid, that's 4096 different little cubes. Each one has six faces, and each face (quad) is actually rendered using two triangles. That's just under 50,000 triangles in one chunk. Hmm, ok, not a big deal yet. Next, remember the view distance is 8 or 10 or 12 or 16 or 20 chunks' distance. In all directions. If you're staring at the ground, this means 512 to 8000 chunks. It's easy to say "I want to see further" but that means an exponential increase in the number of chunks that get drawn. So 50k tris times 8000 chunks is 400 million triangles. Per frame. That's a lot.

Now compare that to a flat surface, where everything hidden is not drawn. Then you only see the surface chunk -- if your view distance is 20 chunks, that means 400 chunks, not 8000. And there's only one side of each visible voxel drawn, so two tris per voxel. And in each chunk you're only seeing one layer of voxels, not 16 layers. So that's 256 voxels per chunk. 256 voxels x 2 tris x 400 chunks = 200,000 tris. That's a thousand-fold reduction in the amount of work to do. When you're working with voxels, it pays to save as much work as possible.

Back to the problem: I noticed this problem while working on a new terrain gen feature. In some cases (but not all), what should have been visible wasn't being rendered. I played around with reproducing the problem and I got the image above. I realized that the problem is yet-another "16 problem," of which I've had a few. Lots of special case stuff goes on at the borders between chunks, because I'm dealing with multiple chunks instead of just one.

The problem is dealing with the end of the fence differently than the middle of the fence. Normally fencepost errors are typing while (x<16) instead of while (x<=16), stuff like that. "Fencepost" gives the problem a natural analogy. They're sometimes called an off-by-one error, by which we get the name "Obi-Wan Error."

The second image demonstrates the fix. The sand marks the corner where four chunks come together, and you can see the brown clay material is now behaving properly.

I've got a bunch of bits that say "if the camera is inside THIS type of voxel, can you see THAT face?", plus routines to handle what happens when the voxel in question is rotated and if it's one of the 39 different non-cube voxel shapes that I support. In this case, I'm working with seven voxels. As I decide which face of a voxel to add to the geometry call, I consider its six neighbors. Originally, I forgot to swizzle the bits correctly; I previously fixed it for the "interior" of the fence, but not the borders. Now, with today's fix, I've got the end of the fence (the borders between chunks) working correctly.

Plus now I see that there's another lighting issue. Chunks appear to be importing incorrect lighting information at their corners -- but only one of the corners. The sides are fine, three of four corners are fine, but somehow this one is different. Hence: subvoxel blues. I've got more debugging on my plate tomorrow.

Subvoxel Terrain

Range of subvoxels I currently have implemented

In my first pass at subvoxel terrain, I'm trying to shoehorn a random Perlin Noise field into a bunch of subvoxels. Instead of a single integer height value, I could use of the subvoxels pictured at right.

For now I'm sticking to just eleven possibilities: the solid voxel (duh), the half-slab, and the nine sloped options at the bottom-left of the picture. In other words, I can now support elevations at the corners -- that is, four elevation values go into deciding what to draw at each voxel.

There's some tricks here. What if the highest elevation is in a different voxel? Before I get into that, let me describe how I'm thinking about the problem.

First I pick a lowest integer voxel value; one that's at or below the lowest corner. This value I call "0", duh. Then the corners are numbered according to how many half-voxels they are above that voxel. The lowest corner could actually be a 1, or even a 2 -- the latter case if the lowest corner is 0.75 units above the floor.

The set of options I have to work with are things like 0011 or 0222 or 2202, etc. There's three ways to consider the numbers: as they are, with the northwest corner first; rotated, such that the lowest corner is first; or as a generic set of corner values. There's 15 possibilities in that set, btw, which I'll leave as an exercise for the reader.

15 possibilities -- if each corner is 0, 1, or 2. But what if I have a voxel where my corner values want to be 0, 1, 2, and 3? Or 1, 3, 5, and 9? That I'm just punting for now, actually. I've got some shapes that I could rotate such that I could handle a combination (clockwise) like 0044, and I'm planning on adding a couple shapes that would handle 0033 or 1144 or 1133. Maybe I need to add something for 1333? And I could do a two-voxel stack that would handle 0242.

I think options like 0244 is just right out; that would require a radically different way of handling voxels. Converting corner elevations to subvoxels is a bit of a "hack" -- taking what I have in the engine, and trying to find a simple way to generate undulating terrain with something other than plain stairsteps.

OK, so what DO we have? Let's take 0000, 1111, and 2222 first. In this cases, I have no voxel, a half-slab, and a solid voxel. Simple enough.

Next comes combinations of two height-values. The nine angled shapes in the front-left of the image represent the (clockwise) combinations 2211, 1211, 2221; 1100, 0100, 1110; and 2220, 0200, plus 2200. Note that I haven't implemented 2121, 1010, or 2020. With rotation, these shapes can handle all of the possibilities of two numbers (again, minus the 2121 1010 and 2020 cases).

There's also the problem of voxels like 1133. What do I do with that? If I'm not going to do two voxels (and I don't have the shapes for that yet), do I force that to 1122, or 2233 (and raise the surface voxel up one unit)? For now, I've got some simple logic that decides; I don't know that there's a one-size solution, so I went with "close enough" and we'll see where that gets me.

subvoxel terrain test world

So that's what I do. Simple pattern-matching. Here's what it looks like now, and it makes plain -- I need to fix subvoxel lighting! Guess what I work on next? :)

Voxel-Based Lighting

Smooth voxel-based lighting

So, like, how do you light a voxel world, anyway?

I'm using Unity. However, my terrain is procedurally generated at run time. The data can be saved and loaded, but it's not like I'm building a Quake level here. My Unity scene is empty. Stark. Bare. I can't use all those fancy Unity tools for lighting. No lightmaps, no light samples, no baked radiosity, nothing.

And it's a sandbox voxel world. Voxels come and go, so I can't do anything fancy that requires precomputation. Whenever some user walks up and deletes a voxel, I've got to redo lighting. And if you've played Minecraft much, you know that you've got to kinda dump torches every 10 meters. All over the place. A distant view of your castle will have hundreds of light sources.

From playing the game, one can guess what Minecraft does. You might be wrong. At some point, lighting for a voxel was calculated by shooting out rays from each voxel into the sky, and the number of those rays that made it determined the light value for that voxel. This only works outdoors, though; what happens when the sun sets? What do torches do?

So the next guess has two parts: (1) Anything directly exposed to sunlight gets lit at full brightness (during the day). (2) Everything else seems to be lit by light values in a voxel slowly dropping from voxel to voxel. A voxel "in the shade" (ie not directly exposed to sunlight) but that is next to such a voxel will be lit just one tick darker. And so that's what I did.

The next trick is to figure out how to light each quad in the world. (With all my subvoxels, I've actually got to worry about WAY more planes, but that's a different story. Let's pretend we're doing strict cube-only worlds for now.) Lighting is there to see stuff, obviously, but we've got two main goals with the light algorithm: to model light occlusion, and to model light radiance.

The first means that something not facing a light source should be darker than something facing it. Further, if a quad faces a light source but is occluded by an intervening object, then it should be darker. In a simple game engine, we could model the sun using a shadow map, perhaps rendered in screenspace, to indicate which parts of the world are exposed to a light. But, again: 100+ lights! This is madness. We need a solution.

The second term -- radiance -- means that, even if a quad isn't exposed to the sun, it will pick up light bounced off of other surfaces. Ideally, the surface should colorize the reflected light. This gets tricky with sunlight, however, since the sun itself isn't in the direction of sunlight. Sunlight comes from the whole sky, bouncing through the atmosphere, although most brightly in a straight line. That bounced light is what makes outdoor shadows soft-edged and light. We kinda want an HDR solution here; a way of providing tons of resolution to the "how much light is here?" equation, as well as handling the fact that the human eye will adapt to the total amount of light in the environment.

But I get ahead of myself here.

So let's go back to the "simple" MineCraft-style solution. Any voxel directly exposed to sunlight gets the maximum light value. Any voxel with a torch in it gets the maximum light value. Other light-generating objects (jack'o'lanterns, ovens, glowstone) get the same treatment, although their light values are lower. Next, every other voxel gets assigned a light value that is one less than the most brightly-lit neighbor.

I'd love to colorize this light value. I'd love to directionalize it, so that we're actually modelling radiance; that would mean assigning 6 light values to a given voxel, with each value being not just a 4-bit value but an actual color. Maybe a full 32 bits. And maybe rather than the 6 cardinal directions, we could model 18 directions (the 6 + the 12 diagonal directions along plane lines) or 26 directions (ie to all neighboring 26 voxels in a 3x3x3 cube around our source). Do we have processor power for that? Hurm. Dunno. There are real-time lighting solutions for complex-geometry games that compute light in six directions, eg using a clipmap, that can model complex interactions.

But... well do we really need that much detail?

Ok, so let's go back. Let's just get something working. We got a light value at a voxel. How do we light quads?

The goal here, really, is to provide consistency. Take a 2x2 chunk of grass voxels, sitting in a plane under the sun. The intersection at the middle of the four top quads of these voxels should be seamless. Or not; that's a choice here. Minecraft Classic only lit quads by whether they were facing the sun or not. It was a simple directional one-light system with an ambient factor. You could tell which way a poly was facing by the lighting on its quads. At some point, MC introduced smooth lighting, and that's what I'm talking about here. Smooth lighting looks sooo much better. So that's our goal. (When did MC add good support for both sunlight and moonlight, and torches, and the rest? I don't know. I'm not too interested in the history here.)

So the solution I've used is to come up with a clear definition for the lighting at any given vertex based upon neighboring voxel light values and the facing of the tri. (Remember, I'm dealing with subvoxels that have many faces not in any of the 3 axis planes.) In the simple case, at a corner such as our 2x2 chunk of grass voxels, lighting at the corner is the average of the light value of the four voxels directly above the grass. No matter which voxel you look at, that voxel's quad will have the same light value at each corner.

This gives us partial occlusion for free. If one of the four voxels above a vertex is solid, then that vertex will only be 75% lit. Two voxels, 50% lit. Three voxels, 75% lit. And we let the graphics card smoothly interpolate lighting across the quad.

Take a look at the image. The red area seems odd; why the bright contrast? Well that's cuz the bright bit faces out into the sunlight, while the dark bits are directly under the tree. (Sidewise light propagation is turned off in this image.) Inside the blue circle, you can see that corners get progressively darker.

There's algorithmic hoops to jump through to get this working fast, but do you really want to know about hashsets? I'll skip those details for now.