How to make a Greedy Mesher

If you are wondering what a greedy mesher is visit this post by @Elttob for what it is

This post will show you how to make a 2D(easily extendable to 3D) greedy mesher for all your voxel optimization needs(i would not recommend visible faces only for this as it runs slower than all in my testing). So let’s start by making a heightmap. But inside of that we will also make a table of whether or not it has been visited before(you’ll see why later).

Make the map

Okay so let’s start by defining the tables. For your height map, you can use any function you want, if its math.noise or just if the y < 20, it won’t make a difference. For now though, we will just use math.sin

local isVisited = {}
local map = {}

We’ll have them named like that. So lets loop through every x and y.

for x = 0,50,1 do
    for y = 0,50,1 do
		
    end
end

Now let’s make map[x][y] = 0 or 1 (block or air), and we will have isVisited[x][y] be false, since we haven’t visited it yet.

for x = 0,50,1 do
    map[x] = {}
    isVisited[x] = {}
    for y = 0,50,1 do
        map[x][y] = y > math.sin(x) * 25 and 0 or 1
        isVisited[x][y] = false
    end
end

Ok, now we can move on to the actual mesher!

The Greedy Mesher

Okay, so for the greedy mesher we’ll need these variables, and a utility function. isEmpty checks if block ~= 0, cause we remember that 0 is a block, and 1 is air.

local cuboids = {}
local size = 50
 
local function isEmpty(block)
    return block ~= "0"
end

Okay, now let’s get into the mesh loop.

for x = 1, size do
    for y = 1,size do
        local startX = x
        local startY = y
        local endX = x
        local endY = y
 
		 isVisited[x][y] = true
 
	end
end

That should be fine. Now the actual greedy mesher!
Repeat checking if the block isVisited or the block is empty, and if both are false, then we can move the endX on by 1! This should be nested inside of the for loop.

while endX < size do
            local newEndX = endX + 1
            
            local isUseable = not isVisited[newEndX][y] and not isEmpty(map[newEndX][y])
            
            if not isUseable then
                break
            end
            
            isVisited[newEndX][y] = true
            endX = newEndX
        end

Okay, now we can do the same for the Y except when we push up the Y, we have to go through all the blocks on the line to make sure they work. This should be right after the X loop

while endY < size do
            local newEndY = endY + 1
            
            local isRowUseable = true
            
            for dx=startX, endX do
                local isUseable = not isVisited[dx][newEndY] and not isEmpty(map[dx][newEndY])
                if not isUseable then
                    isRowUseable = false
                    break
                end
            end
            
            if not isRowUseable then
                break
            end
            
            for dx=startX, endX do
                isVisited[dx][newEndY] = true
            end 
            endY = newEndY
        end        
			-- this inserts it
table.insert(cuboids, {
            startX = startX,
            startY = startY,
            endX = endX,
            endY = endY
        })

Now all we have to do is generate it. But I’ll leave that to you.

Pictures

Here is an example of a 3D one:

52 Likes

This was a really good tutorial, thanks. But I’ve found a way to lower the part count even more. If we allow parts to go through parts that have a greater height in order to reach other parts of the same height on the other side, we can lower the part count even more. The first example shows the greedy mesher being used with no changes. The second example uses the second method. The part count went from 3687 to 2345, a 36% decrease. The terrain is identical, and the only problem introduced from this method is Z-fighting, which could also be solved.



The best part about this is how easy this change is to implement.

while endX < grid do
	if not isVisited[endX+1][startY] and map[startX][startY] <= map[endX+1][startY] then
		if map[startX][startY] == map[endX+1][startY] then
			isVisited[endX+1][startY] = true
		end
		endX = endX+1
	else
		break
	end
end

When scanning the first column, change the condition to check if the height of the starting coordinate is less than or equal to the height of the coordinate. If it is, then proceed, and only mark the coordinate as visited if the height is equal to the starting coordinate. This is because if the height is more, then the actual height is not being achieved. So that coordinate is not finished. The row will just keep scanning through that coordinate, and potentially get any other coordinates that have the same height.

if not isVisited[dx][endY+1] and map[startX][startY] <= map[dx][endY+1] then		
	if dx == endX then
		for i = startX,endX do
			if map[startX][startY] == map[i][endY+1] then
				isVisited[i][endY+1] = true
			end
		end
		isRowUseable = true
	end
else
	break
end				

Here, we’re basically doing the same thing. Check if the starting coordinate is less than or equal to instead of just equal to, and when you’re marking them as visited, only mark the ones that have equal height as visited. That’s all. Those two small changes can lower your part count by around a third.

14 Likes

Hello! Sorry for reviving this post but I’ve been trying to get this algorithm to work on the X and Z axis for a few days now and I have yet to be able to wrap my head around it. Ive been able to make it work on 1 axis as you can see here:


But when I try to add some difference on the same axis I get this result: (the one on the left is the expected result and the one on the right is the generated result). For my implementation of this algorithm I swapped the isEmpty function for instead just checking if the parts are on the same Y. It seems I’ve been able to calculate the size of the parts correctly (as I just set it to the End value(s) subtracting the Start value(s) and adding 1), but not their position (what I do is just set the part’s CFrame to the StartX and StartZ values the algorithm generates and I swapped out the StartY for StartZ). If my own code is needed for further help ill be glad to post it! Thank you for your time.

1 Like

UPDATE: I have solved my problem. turns out the problem was that when I was scaling my parts their position would get all screwed up, so what I did was use the part’s Resize function to scale them correctly while maintaining their position!

2 Likes

This doesn’t appear to work for me. All my blocks are overlapping each other. And I don’t seem to be getting any errors too. Am I doing anything wrong?

-- Greedy meshing
local VoxelSize = 1

local Cuboids = {}

local function IsEmpty(block)
	return block ~= 0
end

for X = VoxelSize, PartToDestroy.Size.X, VoxelSize do
	for Y = VoxelSize, PartToDestroy.Size.Y, VoxelSize do
		
		local StartX = X
		local StartY = Y
		local EndX = X
		local EndY = Y
		
		IsVisited[X][Y] = true
		
		while EndX < PartToDestroy.Size.X do
			local NewEndX = EndX + 1
			local IsUsable = not IsVisited[NewEndX][Y] and not IsEmpty(Map[NewEndX][Y])
			
			if not IsUsable then
				break
			end
			
			IsVisited[NewEndX][Y] = true
			EndX = NewEndX
			
		end
		
		while EndY < PartToDestroy.Size.Y do
			local NewEndY = EndY + 1

			local IsRowUsable = true

			for dx = StartX, EndX do
				local IsUsable = not IsVisited[dx][NewEndY] and not IsEmpty(Map[dx][NewEndY])

				if not IsUsable then
					IsRowUsable = false
					break
				end
			end

			if not IsRowUsable then
				break
			end

			for dx = StartX, EndX do
				IsVisited[dx][NewEndY] = true
			end

			EndY = NewEndY
		end
		table.insert(Cuboids, {StartX = StartX, StartY = StartY, EndX = EndX, EndY = EndY})
	end
end

Also which for loop? Theres two. The X and the Y

Could you explain how you use endX, endY, startX and startY? I cant seem to understand and get it working.