Greedy Voxel Meshing

I've been busy working on improving the performance in my voxel engine over the past week. The biggest improvement came from implementing greedy voxel meshing, which is what this entry is all about. I'm going to put a little more effort into creating higher quality blog posts from now on, with a focus on explaining a concept or algorithm through visualization. If you have any suggestions for improvements or blog posts to write, leave me a comment.

Mikola Lysenko goes into great detail describing various methods of meshing in his blog post . I highly recommend reading his post to get a better understanding of why greedy meshing works and how bad it can get. My goal is to give a more intuitive explanation of Mikola's post. I'll emphasize the most important part of the algorithm to understand: the ordering of quads. Mikola gives this ordering:

bool compareQuads(const Quad &q1, const Quad &q2) {
  if(q1.y != q2.y) return q1.y < q2.y;
  if(q1.x != q2.x) return q1.x < q2.x;
  if(q1.w != q2.w) return q1.w > q2.w;
  return q1.h >= q2.h;
}

What this means is that we form our quads from top to bottom, left to right. Whenever we reach a face that has yet to be covered with a quad, we take the widest possible quad at that point. If we can extend that quad in height, we do so as much as possible.

That's all fairly hand-wavy, so here's an animation to help explain:

Here's a result from my own engine: