binary greedy mesher in luau

Chunk.luau

--!strict
--!native

-- Chunk.luau
-- Uses a binary greedy mesher to chunk
-- everything together.
-- poopbarrel/magicoal_nerb

local CHUNK_FACES: { Vector3 } = {
	Vector3.xAxis,
	Vector3.zero,
	Vector3.zAxis,
	Vector3.zero,
	Vector3.yAxis,
	Vector3.zero,
}

local forward: { number } = table.create(16 * 16, 0)
local masks: { number } = table.create(6 * 16 * 16, 0)
local right: { number } = table.create(16, 0)

local CHUNK_OFFSET = {
	16,
	16,
	1,
	1,
}

local CHUNK_VECS = {
	Vector3.zAxis,
	Vector3.zAxis,
	Vector3.xAxis,
	Vector3.xAxis,
}

local Chunk = {}
Chunk.__index = Chunk

export type Chunk = typeof(setmetatable({} :: {
	opaque: { number },
	data: { number },
}, Chunk))

export type Pair = {
	cframe: CFrame,
	size: Vector3,
}

function Chunk.new(): Chunk
	return setmetatable({
		opaque = {},
		data = {},
	}, Chunk)
end

function Chunk.set(self: Chunk, data: { number })
	-- YXZ
	local opaque = table.create(16*16, 0)
	for i = 0, 16^3-1 do
		local x = bit32.band(bit32.rshift(i, 4), 0xF)
		local z = bit32.band(bit32.rshift(i, 8), 0xF)
		local y = bit32.band(i, 0xF)
		
		local id = x + z*16 + 1
		if data[i+1] ~= 0 then
			opaque[id] = bit32.bor(opaque[id], bit32.lshift(1, y))
		end
	end
	
	self.opaque = opaque
	self.data = data
end

function Chunk.draw(self: Chunk, output: { Pair })
	-- draw code :D
	for i, pair in output do
		local p = Instance.new("Part")
		p.CFrame = pair.cframe + pair.size*0.5
		p.Size = pair.size
		p.Parent = workspace
		p.Anchored = true
	end
end

function Chunk.render(self: Chunk): { Pair }	
	local opaque = self.opaque
	for x = 0, 15 do
		for z = 0, 15 do
			local id = x + z*16 + 1
			local column = opaque[id]
			
			-- +X/-X
			masks[id + 0*16*16] = bit32.band(column, bit32.bnot(opaque[id + 1] or 0))
			masks[id + 1*16*16] = bit32.band(column, bit32.bnot(opaque[id - 1] or 0))
			
			-- +Z/-Z
			masks[id + 2*16*16] = bit32.band(column, bit32.bnot(opaque[id + 16] or 0))
			masks[id + 3*16*16] = bit32.band(column, bit32.bnot(opaque[id - 16] or 0))
			
			-- +Y/-Y
			masks[id + 4*16*16] = bit32.band(column, bit32.bnot(bit32.rshift(column, 1)))
			masks[id + 5*16*16] = bit32.band(column, bit32.bnot(bit32.lshift(column, 1)))
		end
	end
	
	local data = self.data
	local output = {} :: { Pair }
	
	for f = 0, 3 do
		local offset = f*16*16 + 1
		local face = CHUNK_FACES[f+1]
		for id = 0, 16*16 - 1 do
			local z = bit32.band(bit32.rshift(id, 4), 0xF)
			local x = bit32.band(id, 0xF)
			
			local startPos = f < 3 and z or x
			local chk = CHUNK_OFFSET[f + 1]
			
			-- Main greedy mesh step
			local position = offset+id
			local strip = masks[position]
			
			while strip ~= 0 do
				local bitPos = bit32.countrz(strip)
				local length = bit32.countrz(bit32.bnot(bit32.rshift(strip, bitPos)))
				local mask = bit32.lshift(bit32.lshift(1, length)-1, bitPos)
				
				-- Do main scan along the vertical as that's
				-- faster than a memoize table.
				local right = 1
				for k = 1, 16 - startPos do
					local target = position + chk*k
					local label = masks[target]
					if bit32.band(label, mask) == mask then
						masks[target] = bit32.bxor(label, mask)
						right += 1
					else
						break
					end
				end
				
				-- Output
				strip = bit32.bxor(strip, mask)
				table.insert(output, {
					cframe = CFrame.new(x, bitPos, z) + face,
					size = Vector3.yAxis*length + CHUNK_VECS[f+1] * right,
				})
			end
			
			masks[position] = 0
		end
	end
	
	for f = 4, 5 do
		-- Greedy mesh top parts
		local offset = f*16*16+1
		local face = CHUNK_FACES[f+1]
		for id = 0, 16 * 16 - 1 do
			-- Happy face :D
			local z = bit32.band(bit32.rshift(id, 4), 0xF)
			local x = bit32.band(id, 0xF)
			
			local maskId = z*16
			local position = offset+id
			local strip = masks[position]
			
			while strip ~= 0 do
				local bitPos = bit32.countrz(strip)
				local mask = bit32.lshift(1, bitPos)
				strip = bit32.band(strip, bit32.bnot(mask))
				
				local fwd = forward[x*16 + bitPos]
				local rgt = right[bitPos]
				if rgt == 0 and bit32.band(masks[position + 16] or 0, mask) == mask then
					-- Z+ forward
					forward[x*16 + bitPos] += 1
					continue
				end
				
				if forward[x*16 + 16 + bitPos] == fwd
					and bit32.band(masks[position + 1] or 0, mask) == mask then
					-- X+ forward
					forward[x*16 + bitPos] = 0
					right[bitPos] += 1
					continue
				end
				
				forward[x*16 + bitPos] = 0
				right[bitPos] = 0
				
				table.insert(output, {
					cframe = CFrame.new(x-rgt, bitPos, z-fwd) + face,
					size = Vector3.new(rgt+1, 0, fwd+1),
				})
			end
		end
	end

	return output
end

return Chunk