So I may be a bit late to this party, but I've decided to build a minecraft-like game. I'm not 100% about the exact format, but my thinking is it'll be an FPS shooting with destructible terrain. I envisage that at the end of a round, you'll just be sitting in a crater on top of a pile of bodies... anyway, I've started off with a much simpler problem: how do you turn a 3D voxel array into an efficient mesh?
To begin with, I've started with a very simple data structure, just a single bit for "solid" vs. "empty". I'm working with a 32x32x32 chunk of voxels. I'll expand on that later to support textures and different materials and so on, but I think the general principle is the same.
The first version of my algorithm was very simple: just render a 6-sided cube for each solid voxel:
This is obviously horribly inefficient (it's actually closer to 300k vertices, despite what the display says there: it's doubled because the wireframe causes the vertices to be counted twice -- still, 300k is insane!)
This algorithm is so dumb, I'm not even going to bother posting it. Now, the second version of my alorithm was actually a very minor modification. For each face of each cube, it would look at the neighboring voxel. If the neighbour had the same value (i.e. if they were both solid), it would simply skip that face. The results look much nicer, even with the noise of the wireframe:
OK, so this ends up being about 17k vertices (without the wireframe) which seems pretty reasonable. But you can see in this view that there's actually quite a lot of redundant quads being drawn.
I found a pretty nice algorithm from a few years ago titled "Meshing in a Minecraft game". It was a little math-y for me, so it took me a little while to figure out exactly how it's supposed to work. I prefer to think in terms of pictures. Anyway, this is the result:
Pretty neat! Down from 300k vertices to 3,000. 100x improvement! It's still not 100% optimal, but it's close enough that I don't really care.
OK, so how does it work? The first step is sweeping through the volume one axis at a time. I actually sweep through each axis twice, once for each direction. Then, for each sweep, you generate a bunch of "slices", and populate the slices with quads for each side of the cube on that slice. Here's an example of what you see after I've sweeped through the Y axis only and just rendered all of the quads:
Now, for each slice we end up with a 2D array of the quads and all we want to do is make as few larger quads as possible. Here's a little animation to show how I'm doing it:
As you can see, we just iterate through the slice, find the first quad and then try to expand it to be as big as possible (going as far to the left as we can, then taking it as far down as we can).
As I said, it's not the most efficient algorithm (as in, it doesn't generate the absolute most optimal mesh), but it's pretty easy to understand and it gets us pretty far along. I'm pretty happy with the result overall!