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

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

10 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!

1 Like

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.