Greedy Meshing Voxels


Greedy meshing is a really cool way to optimize voxel games such as minecraft. Basically you just combine a bunch of voxels together into bigger blocks. Minecraft uses this to reduce the render load. You can then break back down the bigger blocks into their respective voxels quite easily, in situations where you mine a voxel thats apart of a bigger block. Another application is optimizing voxel art. @Elttob wrote an article about greedy meshing (link below in sources) and I decided to write my own implementation of it. This is considered naive greedy meshing, because there are ways to do it where the model will be less parts and therefore more optimized for rendering, but take considerably longer to calculate.

In the pictures above, I took 3864 voxels and condensed them down into 103 blocks. Thats a 97.3% reduction! Of course with more complex shapes you will get worse results, because the shapes I used were really blocky.

Now I did it in the order of X > Z > Y because my application will be mostly voxel objects with width and length larger than their height, but the order is arbitrary and can be anything you want. You will find that a specific order for specific objects will be more optimal than others.

I also used a lazy instantiation method to create the 3d array to keep track of all the voxels, given that 3d voxel space can get very large in memory. However this approach is really only for small objects, and is really slow for large worlds like minecraft, so for that you’d want a different structure like octrees or something.

How it works: given an area of voxels, start from the bottom left back most voxel space and loop through until you find a voxel. This will be your starting voxel. Then, loop down the voxels in the x direction until theres an empty space. The amount of voxels is your x size. Then, loop down the voxels in the z direction from the starting voxel and check x voxels down every z row until either theres an empty space. This is your z size. Then, do the same thing with the y direction, except this time youre checking both the x and z voxels within your x and z size in every y row. Basically, for your x, youre checking in 0 dimensions, your z in 1 dimension, and your y and 2 dimensions. This will give you a block, or a “chunk” as I call it in the program. Repeat these steps until every voxel is checked.

greedyMesh.rbxl (39.8 KB)

sources:

46 Likes