Beerman's adventures in voxel-land, part 7 : Need for speed

Previous Entries : Intro Part 1 Part 2 Part 3 Part 4 Part 5 Part 6

With the basics of the trench runner working, I wanted to take a look at a performance issue that’d been giving me trouble - the initial version of the engine was pretty much limited to only seeing about 10 chunks ahead if I wanted to keep it at 60fps, which was giving me some pretty visible popup on the far end of the trench.

The problem was in the mesh generation for my chunks. I had the basic optimisation in place of not adding faces to the mesh that were in between adjacent filled blocks, but that meant that for a completely solid chunk I was still rendering hundreds of little cubes where one would be enough.

A spot of googling helped me find something called a greedy meshing algorithm. Basically, you take 2d slices across each chunk in every direction, then for each slice, the greedy algorithm starts in the top left corner and identifies the largest rectangle it can make consisting only of filled squares. Once that’s done, it adds the rectangle to the mesh and continues from the next unprocessed square until all squares in the slice have been processed

Start with top left filled square. Expand right and down until we can't make a bigger rectangle. Add rectangle to mesh and remove squares from slice. Continue with next filled square.

After a lot of swearing, I got a successful implementation up and running, which cut my rendering action from upwards of 10 million triangles a frame to somewhere closer to 300,000, and let me push the render distance out past 100 chunks without affecting the framerate.

before meshing after meshing

And here it is in action