How do I expand my greedy meshing algorithm from 1D to 2D? (or even 3D)

Help and Feedback Scripting Support
#1

I have been trying to do this for a few solid months now and I still can’t get my head around expanding my 1D greedy mesher into a 2D or 3D one.

I have read several posts on greedy meshing and yet I can’t seem to get my head around it as I cannot find any good code samples or tutorials for lua or roblox greedy meshers. I fully understand the concept and how it works, I have even read a simple tutorial from @Elttob but I just simply have no idea how to do it in code.

Here’s my current poor 1D implementation:

local Module = {}

-- 'Voxels' are an array of voxel data which is structed like this:
-- Voxel = {Position = Vector3, Visited = boolean}
function Module.GreedyMeshVoxels(Voxels, VoxelGroupSize, VoxelSize)
	local MeshedVoxels = {}

	local function CreateMeshedVoxelData(StartPos, EndPos)
		local NewPos = (StartPos + EndPos)/2

		local NewSize = (EndPos - StartPos) + (Vector3.new(1, 1, 1) * VoxelSize)

		local Voxel = {Position = NewPos, Size = NewSize} -- CFrame, Size
		table.insert(MeshedVoxels, Voxel)
	end

	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 IsInEmptyRegion = false  -- Make sure we aren't creating voxels in empty regions

	for Z = VoxelSize, VoxelGroupSize.Z, VoxelSize do
		local PosZ = Z - (VoxelGroupSize.Z / 2) - (VoxelSize/2) -- Origin

		for Y = VoxelSize, VoxelGroupSize.Y, VoxelSize do
			local PosY = Y - (VoxelGroupSize.Y / 2) - (VoxelSize/2) -- Origin

			local StartPos = nil
			local EndPos = nil

			for X = VoxelSize, VoxelGroupSize.X, VoxelSize do
				local PosX = X - (VoxelGroupSize.X / 2) - (VoxelSize/2) -- Origin

				local Voxel = FindVoxel(PosX, PosY, PosZ)

				if Voxel then
					if not StartPos then
						StartPos = Vector3.new(PosX, PosY, PosZ)
					end
					EndPos = Vector3.new(PosX, PosY, PosZ)
				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(PosX, PosY, PosZ)
					end
					Voxel.Visited = true
				end
			end

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

return Module
2 Likes