Consume everything - how greedy meshing works

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:

image

Starting with the first block, we record our ‘starting position’.

image

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

image

(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:

image

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;

image

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 :slightly_smiling_face:

81 Likes

Awesome tutorial, thanks!

I actually remember back when I suggested you use a similar algorithm in Blox ages ago. Now that it’s implemented, what sort of frame difference do you get?

Also, what did you use to create the images in this tutorial?

2 Likes

I’ve yet to do any profiling or framerate testing for it since the current implementation is too unstable at the moment, but I’ll let you know once it’s more stable :slightly_smiling_face:

Also, all those images are from Studio directly!

2 Likes

I’d also be interested in how long it actually takes to run the algorithm on a chunk, this is really interesting.

Would you make it run across multiple chunks? For example if you could combine a line of blocks that span across two chunks.

Please dm me on how you do those screenshots

Those visuals are great!

However, I have a curious question:

What’s the methodology for choosing the starting block? Loop through everything until you find the first valid block?

1 Like

Good question! To find a starting block, iterate over every block until you find one that isn’t empty and which hasn’t already been visited :slightly_smiling_face:

1 Like

Thanks for the post, I found myself needing something like this for my terrain system a while back

I received a really good solution on my support post about this

3 Likes

I never knew about this until now, thanks!

I’m assuming we’re meant to make our own scripts which utilise this algorithm in modelling software such as blender to achieve this, or could it also be done in Roblox?

1 Like

It’s definitely possible to do with Roblox! The example at the top of this post was made completely using regular scripts.

1 Like

I actually needed this to improve my voxel importer.

1 Like

This is a really helpful post, appreciate it. Question: Which blocks do you apply this to? Is it every block in sight, including those that are within reach of the player? If so, how do you handle the cases in which the player clicks on a block to start digging when it has been combined with others? Thanks.

separate the block back into individual voxels, do the dig, then re-greedy-mesh that one portion of voxels. You don’t have to do this physically, I would personally implement some sort of data structure that allows you to do this easily in memory. I think that back in the day (years ago), there was this shovel Tool floating around that would actually carve holes in any Roblox part, using some sort of greedy-meshing-ish system. Wish I could find it now…

1 Like

same idea as a cutting a window into a wall, split it up and just remove said area