Optimizing Voxels - Greedy Meshing pt. 1

Intro

A while ago I ended up diving moderately deep into creating a fast and efficient voxel engine, and there are some pieces I've implemented along the way that I thought might be worth sharing and explaining in detail. My hope is that this might help people who are learning these details, or in some cases could be novel ideas that could be further expanded on. Some of the ideas I've put into this project were using little to no guidance and could be something nobody else has considered.

For anyone completely new to voxel engines, I will not be going over voxel basics in this series, such as octrees or voxels themselves. This series is going to focus on optimizing and hitting good performance on top of an already bare bones voxel engine. So it's going to be expected that you know at least the surface level details, as well as some basic rendering details such as what a mesh is and how it's made.

Greedy Meshing - What is it?

Greedy Meshing is an algorithm that takes an octree full of voxels and tries to render it out into a mesh of as few triangles as it can. I couldn't tell you that it's the most efficient possible mesh you could generate, but it's very good, somewhat simple and, if done right, very fast to generate. This makes it a very good and very popular technique in the space.

So how is it done? Let's start simple. Let's say you have an octree where each voxel holds some integer ID that defines its type. Let's also say that you have only a single layer of voxels, and that we only care about the top faces of this layer. This makes our problem 2 dimensional for now to understand the basic approach. To start, you need to find a voxel to start with. That would be one that hasn't been touched by the greedy mesher yet. Our voxels would have some flag that gets marked when they've been part of a greedy meshing already. Then it's as simple as looping through and finding the first voxel that needs to be meshed and hasn't been yet.

let start = null;
for y in layer {
	for x in layer[y] {
		let voxel = layer[y][x];
		if voxel.id != AIR && !voxel.meshed {
			start = (x, y);
			voxel.meshed = true;
			break;
		}
	}
}
if start == null {
	return null;
}

The way this algorithm works at its core is to expand in one dimension, let's say the X axis, until it reaches some boundary. This "boundary" can be defined as a voxel that does not match some requirements. In this case, our requirement is that the IDs of the voxels match, so only voxels with the same ID will be meshed together. Then it expands along the other axis, let's say the Y axis, comparing every voxel we accrued along the X axis until it reaches some boundary that way. This way, we always result in a rectangle of some dimensions. Here's some pseudo code and a gif to help in understanding.

let length = 1;
let width = 1;
let id = layer[start.y][start.x].id

fn voxel_matches(voxel) -> bool {
	return voxel.id == id && !voxel.meshed;
}

// Figure out how long our rectangle is on the X axis.
// Since we know from our start search that our first position is good,
// we can skip it (start.x+1)
for x in start.x+1..len(layer[start.y]) {
	let voxel = layer[y][x];
	if voxel_matches(voxel) {
		length += 1;
		voxel.meshed = true
	} else {
		break;
	}
}
// Each row, make sure we can expand to it given our length.
// Since we already checked start.y in the length loop, we can skip it here
for y in start.y+1..len(layer) {
	for x in start.x..start.x+length {
		let voxel = layer[y][x];
		if !voxel_matches(voxel) {
			return (start, length, width);
		}
	}
	// We've confirmed the row is being added, so we can mark them
	for x in start.x..start.x+length {
		let voxel = layer[y][x];
		voxel.meshed = true;
	}
	width += 1;
}

Greedy Meshing in 2D
Greedy Meshing in 2D

The result of this algorithm is a length and width and starting position. That's everything needed to define a rectangle, which is also enough to define a face for our mesh. We can then run this again and again, until our function returns null indicating that no unmeshed voxels remain for this layer.

I think it's worth clarifying here that my pseudo code simplified the data down to a 2D array, because it's easier to understand. If you're working with an octree, which you probably are, you would probably have a function to get the voxel ID at a certain position. Some of it may require a bit of reworking to fit your scenario. You will also probably have to store your "meshed" flags separately anyway, since this data probably won't fit well into a sparse octree.

So now, with this logic under our belt, we can expand it to 3 dimensions. The good news is that our logic is nearly there already. One big issue that's been left out until now is that a voxel doesn't need a face if it's blocked on that side by another voxel. For this, the nicest way I've found to do it is to generate bitflags for each voxel whether it's exposed on any given side and will be meshed. We can then add this information into our function to check if a voxel matches up with the ones beside it and pass in which side we're worried about.

fn voxel_matches(voxel, side_mask) -> bool {
	return voxel.id == id && voxel.exposed_sides & side_mask != 0 && !voxel.meshed;
}

We now need to go through each layer of our octree and run our logic on it. The main thing we need to do to expand this to 3 dimensions is have it support multiple axes. A square might have 1 side, but a cube has 6. Unfortunately, since some sides can be obscured but others won't, that means we have to run against all 6 sides.

There are probably a few ways to handle this depending on the language to reduce code reuse. One way is to just feed our code a slice of the octree in such a way where the 3rd axis is ambiguous. Since it will run through any 2D slice perfectly fine, we can know and work with the results externally for each unique pair of axes and side that we're worried about. Our pairs of axes being XY, XZ, YZ. Then it's as simple as iterating through each slice for each pair of axes and side, and then meshing the faces accordingly. We're done! But can we take it further?...

The next level: Binary

There exists a superior version of our previous greedy mesher, one that vastly surpasses it in performance. The Binary Greedy Mesher. This version is much more efficient because it works with things computers know best, binary data. It's a bit of a long topic, so I've split it into Optimizing Voxels - Greedy Meshing pt. 2. Go read it there if you're ready for an upgrade.