Consume everything - how greedy meshing works

[Elttob (dphfox)]

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

[grilme99 (brooke)]

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?

[Elttob (dphfox)]

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!

[grilme99 (brooke)]

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.

[adama88766 (mysticmst)]

Please dm me on how you do those screenshots

[ThatTimothy]

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?

[Elttob (dphfox)]

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

[Quoteory]

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

Procedural Terrain Generation (Parts)

This reminds me of trying to combine voxelized terrain into convex surfaces to be made into a navigation mesh, but in 3D. To summarize it, finding the optimal way to combine parts to minimize the number of parts used could be reduced to a NP-hard optimization problem. The best method is probably to use an approximate solution in linear time, like mentioned above. I’ll start by assuming that the map generated is a height map with special labels for the type of cell. For every cell at random, per…

[Unknownstaffmembe (Unknown)]

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?

[Elttob (dphfox)]

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

[Rootie_DaHoodie (StickBug)]

I actually needed this to improve my voxel importer.

[sevenpolygons]

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.

[anon66957764]

@sevenpolygons

how do you handle the cases in which the player clicks on a block to start digging when it has been combined with others?

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…

[Dev_HDWC (HDWC)]

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

[Brickman808 (NonFunctionalProgram)]

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.

[Ethanthegrand14 (Ethanthegrand)]

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

[Varonex_0 (Varonex)]

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

[Ylsid]

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.

[7z99 (cody)]

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!