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

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

259 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?

5 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

Also, all those images are from Studio directly!

4 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

1 Like

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

3 Likes

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

4 Likes

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.

2 Likes

I actually needed this to improve my voxel importer.

2 Likes

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ā¦

3 Likes

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

Is there a script for this? I waisted a ton of time to get this to work in 3D. 1D and 2D do not interest me.

1 Like

No matter what I do, i canāt seem to be able to expand this to 2D or 3D. I got 1D working fine, but no matter what I do, I cant seem to be able to make use of loops and the other axis to make this work according to the tutorial.

``````local function FindVoxel(X, Y, Z)  -- Get voxel based on position
for i, Voxel in pairs(Voxels) do
-- Im using Voxel.Position to identify if the voxel is empty or not (nil or Vector3)
if Voxel.Position and Voxel.Position.X == X and Voxel.Position.Y == Y and Voxel.Position.Z == Z then
return Voxel
end
end
end

local StartPos = nil
local EndPos = nil

local IsInEmptyRegion = false  -- Make sure we aren't creating voxels in empty regions

for X = VoxelSize, PartToDestroy.Size.X, VoxelSize do
X = X - (PartToDestroy.Size.X / 2) - (VoxelSize/2) -- Origin

local Voxel = FindVoxel(X, 0, 0)

if Voxel then
if not StartPos then
StartPos = Vector3.new(X, 0, 0)
end
EndPos = Vector3.new(X, 0, 0)
end

if (not Voxel or Voxel.Visited) and not IsInEmptyRegion and StartPos and EndPos then
IsInEmptyRegion = true
CreateMeshedVoxelData(StartPos, EndPos)  -- Create the new voxel according to the starting and ending positions
end

if Voxel and not Voxel.Visited then -- Check if the voxel is not empty and it hasn't been visited before
if IsInEmptyRegion then -- We are no longer in an empty region. Reset the starting position to the current position
IsInEmptyRegion = false
StartPos = Vector3.new(X, 0, 0)
end
Voxel.Visited = true
end

end

if StartPos and EndPos then
CreateMeshedVoxelData(StartPos, EndPos) -- Create the new voxel according to the starting and ending positions
end
``````

Iām trying to script a 2D one (X, Z) for custom terrain generation, and Iām using `Region3` with `workspace:FindPartsInRegion3()` method

Weird question, but how about achieving the opposite? I.e. breaking down a simple model into lots of parts dynamically. Useful for high performance destruction without using unions, etc.

Thank you for this tutorial! I just implemented greedy meshing to optimize my wall cutter and plan on using it to patch up walls when walls are removed. This āalgorithmā (not sure if itās considered an algorithm) actually is more versatile than I thought. Props to you!