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.