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!

Generating Decorative Terrain Features

Rock outcrops in various sizes, shapes, and rock types

I'm working in a little test world -- featureless, nearly-flat terrain -- to add bits of interest to the terrain generators. Not sure what got me on this kick but I started working on it over the weekend and I've added a few so far. The first that I added was rock outcrops, and so that's what I'm calling stuff like this: Outcrops.

I'm currently working on adding a type of rock "outcrop" that's actually very low to the ground, sorta kinda like replacing a small patch of terrain with rock, but also adding a little bit of height to the thing.

I'm thinking of where I go next with the terrain generators, and really the process got me thinking about how I want the world to look. What I want to strive for. For one, I really need to put the mountains and forests back! But after adding a few more outcrops, that's what I'm planning on doing; getting the whole thing going again. Generating screenshots of whole worlds again, rather than this little test area.

It's starting to feel empty without a skybox, actually. That's probably the first thing back.

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.