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:

306 Likes
Voxel Grouping Algorithm
Greedy Mesher Not Working
Practical systems and solutions (scripting)
What are you working on currently? (2020)
Model pixelator plugin
How can I expand this 1D greedy mesher to 2D and 3D?
How to make a Greedy Mesher
Greedy Meshing Voxels
How to insert 204.8k parts at once without roblox crashing
How to do voxel grouping?
Is there any way to make super-efficient parts, similar to how minecraft works?
Is there a way to parent a 5000+ children welded creation without freezing the server?
I made a thing that can draw images
Performance considerations, improvements, and optimizations when making a game
How to greedy mesh?
A* Algorithm design review/help, optimization concerns
How would I reduce lag in random-generated world
Question about an optimization system
Efficient way of rendering pixels to reduce lag
Tips for Optimizing a Block Generation Script
Combining Parts to reduce lag
Gaps Appearing in Randomly Generated Terrain (Visible blocks only)
Remove the overlapping transparency of bricks
What are you working on currently? (2021)
DestructionModule for in-game destruction needs!
How do I expand my greedy meshing algorithm from 1D to 2D? (or even 3D)
How do I index a table in cubes?
How do I optimize this script?
R/place now on Roblox!
CSG: None of these 108 parts will union with any of the others
How would you optimize a voxel building system?
How do I make 3d fractals in Roblox without lag?
How can I get all adjacent floor tiles in a room?
[HELP!] - How do I make this group of parts one single part?
How do I generate parts around the player?
How to create procedural part destruction?
Does having a lot of parts/meshparts affect performance?
What are you working on currently? (2020)
How do I combine 2 parts using code?

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

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

2 Likes

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:

3 Likes

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

4 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.

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.

2 Likes

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!