Hey! I initially made this as a response to a DM I got asking how my greedy mesher algorithm for Blox works.
Greedy meshing is a really useful concept when working with voxels, especially in Roblox where large numbers of parts can cause a lot of lag. The idea is to combine adjacent blocks with each other, to reduce the part count while visually keeping everything the same.
In the above picture, the red scene has 15931 instances. The blue scene only has 508.
Anyways, the following is my response to that DM:
Before I get into how the greedy meshing works in higher dimensions, I think it’d be reasonable to talk about how it works in 1D in more detail.
Suppose we have a few blocks like this:
Starting with the first block, we record our ‘starting position’.
Then move along one block at a time until we can’t include the next block, at which point we will have reached our ‘ending position’. A block can be included if it meets these two criteria:
- The block is not empty
- We haven’t visited that block before
(note I’m using blue to indicate blocks I’ve already visited)
Those starting and ending positions can then be interpreted as the two opposite corners of a cuboid:
And that’s how the 1D algorithm works! Just repeat that for every single block (except for ones you’ve already visited, of course!).
Here’s how each stage looks on a more complex 1D scene:
(notice on the far side, the starting and ending positions can be in the same place!)
So now that we have the 1D algorithm, how can we expand it to 2D?
It’s actually simpler than you think. Let’s start with a 2D plane of blocks:
Starting with the first block again, we find the starting and ending positions like we did before;
Now, to cover the blocks in the other direction, we simply try to expand in that direction. As long as all the blocks in that direction can be included, we can safely expand across:
Just like with the 1D case, we keep on expanding until we run into a block we can’t include:
Finally, just like before, we can use those starting and ending positions to define a cuboid:
And that’s all there is to it! Again, do that for every block like you did before, and you’re good to go.
Here’s a more complex 2D scene done step by step:
Expanding the algorithm into 3D utilises the same expanding concept, so it should be easy to take it from here yourself.
Hopefully this helps you out a bit if you needed it! Resources are pretty scarce so I figured I may as well share it with you guys