Generic voxel generator

Help and Feedback Code Review
1

i made this voxel system and idk if its fast or not but i think it is and would like feedback on the script and how it can be improved

voxelhandler module:

local module = {}

local function GetLongestAxis(Size: Vector3)
	if Size.X > Size.Y and Size.X > Size.Z then
		return Vector3.new(Size.X, 0, 0)
	elseif Size.Y > Size.X and Size.Y > Size.Z then
		return Vector3.new(0, Size.Y, 0)
	else
		return Vector3.new(0, 0, Size.Z)
	end
end

local function DividePart(Part: Part)
	local LongestAxis = GetLongestAxis(Part.Size)

	-- just cut the part in half
	if LongestAxis.X ~= 0 then
		Part.Size = Vector3.new(LongestAxis.X / 2, Part.Size.Y, Part.Size.Z)
	elseif LongestAxis.Y ~= 0 then
		Part.Size = Vector3.new(Part.Size.X, LongestAxis.Y / 2, Part.Size.Z)
	else
		Part.Size = Vector3.new(Part.Size.X, Part.Size.Y, LongestAxis.Z / 2)
	end
	Part.Position -= LongestAxis / 4

	local NewPart = Part:Clone()
	NewPart.Parent = Part.Parent
	NewPart.Position = Part.Position + LongestAxis / 2

	return {Part, NewPart}
end

local function AABBIntersect(a: Part, b: Part)
	local aMin = a.Position - a.Size / 2
	local aMax = a.Position + a.Size / 2
	local bMin = b.Position - b.Size / 2
	local bMax = b.Position + b.Size / 2

	return (aMin.X <= bMax.X and aMax.X >= bMin.X)
		and (aMin.Y <= bMax.Y and aMax.Y >= bMin.Y)
		and (aMin.Z <= bMax.Z and aMax.Z >= bMin.Z)
end

function module.VoxelizeCollidingParts(Shape: Part, AxisMinLength: number)
	local Voxels = {}
	local VoxelQueue = {}
	local SeenSet = {}

	-- check all colliding parts to see if they can be voxelized
	local InitialParts = workspace:GetPartsInPart(Shape)
	for _, Part in pairs(InitialParts) do
		if Part:HasTag("Voxelize") then
			table.insert(VoxelQueue, Part)
			SeenSet[Part] = true
		end
	end

	while #VoxelQueue > 0 do
		local Current = table.remove(VoxelQueue, 1)
		local size = GetLongestAxis(Current.Size).Magnitude

		if size <= AxisMinLength then
			-- goes under limit add voxel NOW!!
			table.insert(Voxels, Current)
		else
			-- cut up the parts and do some math
			local Divided = DividePart(Current)

			for _, SubPart in pairs(Divided) do
				local subSize = GetLongestAxis(SubPart.Size).Magnitude
				if subSize <= AxisMinLength then
					table.insert(Voxels, SubPart)
				elseif AABBIntersect(SubPart, Shape) then
					if not SeenSet[SubPart] then
						SeenSet[SubPart] = true
						table.insert(VoxelQueue, SubPart)
					end
				else
					-- ignore it
				end
			end
		end
	end

	return Voxels
end

return module
1 Like
2

Hello :slight_smile:

I think you would get more feedback on Code Review

2 Likes
3

Hi, this is cool and looks pretty optimised already

Maybe cache the Part.Position or Part.Size? Accessing the property for each part is probably quite expensive to do especially at the speed it runs at, you might get some slight performance gains

2 Likes
4

If you are looking to better the performance of your script, I would recommend looking into Parallel Lua as your script may potentially benefit from this.

1 Like
5

i was looking into adding this and learned that caching these and reconstructing parts made integrating this into parallel possible. very neat. ill make another reply once ive added it fully

(sorry for late reply ive been very very busy last couple weeks)

7

changes
i cached literally everything and added parallel
pulled an allnighter doing this

voxelhandler module

local module = {}

local function GetLongestAxis(Size: Vector3)
	if Size.X > Size.Y and Size.X > Size.Z then
		return Vector3.new(Size.X, 0, 0)
	elseif Size.Y > Size.X and Size.Y > Size.Z then
		return Vector3.new(0, Size.Y, 0)
	else
		return Vector3.new(0, 0, Size.Z)
	end
end

--[[local function DividePart(Part: Part)
	local LongestAxis = GetLongestAxis(Part.Size)

	-- just cut the part in half
	if LongestAxis.X ~= 0 then
		Part.Size = Vector3.new(LongestAxis.X / 2, Part.Size.Y, Part.Size.Z)
	elseif LongestAxis.Y ~= 0 then
		Part.Size = Vector3.new(Part.Size.X, LongestAxis.Y / 2, Part.Size.Z)
	else
		Part.Size = Vector3.new(Part.Size.X, Part.Size.Y, LongestAxis.Z / 2)
	end
	Part.Position -= LongestAxis / 4

	local NewPart = Part:Clone()
	NewPart.Parent = Part.Parent
	NewPart.Position = Part.Position + LongestAxis / 2

	return {Part, NewPart}
end]]

local function DividePart(partData)
	local originalCFrame = partData.CFrame
	local originalSize = partData.Size
	local longestAxis = GetLongestAxis(originalSize)

	local direction = longestAxis.Unit
	local axisLength = longestAxis.Magnitude
	local halfLength = axisLength / 2

	local newSize = Vector3.new(
		(direction.X ~= 0) and halfLength or originalSize.X,
		(direction.Y ~= 0) and halfLength or originalSize.Y,
		(direction.Z ~= 0) and halfLength or originalSize.Z
	)

	local offset = direction * (halfLength / 2)

	local partA = {
		CFrame = originalCFrame * CFrame.new(-offset),
		Size = newSize,
		Tag = true,
	}

	local partB = {
		CFrame = originalCFrame * CFrame.new(offset),
		Size = newSize,
		Tag = true,
	}

	return { partA, partB }
end



--[[local function AABBIntersect(a: Part, b: Part)
	local aMin = a.Position - a.Size / 2
	local aMax = a.Position + a.Size / 2
	local bMin = b.Position - b.Size / 2
	local bMax = b.Position + b.Size / 2

	return (aMin.X <= bMax.X and aMax.X >= bMin.X)
		and (aMin.Y <= bMax.Y and aMax.Y >= bMin.Y)
		and (aMin.Z <= bMax.Z and aMax.Z >= bMin.Z)
end]]

local function OBBvsAABB(obbCFrame, obbHalfSize, aabbCenter, aabbHalfSize)
	--im finally proving to be the child of a savant and an asian
	local u = {
		obbCFrame.RightVector,
		obbCFrame.UpVector,
		obbCFrame.LookVector
	}

	local tWorld = aabbCenter - obbCFrame.Position
	local t = Vector3.new(tWorld:Dot(u[1]), tWorld:Dot(u[2]), tWorld:Dot(u[3]))

	-- Rotation matrix (third time ever ive had to apply matrix math in programming)
	local R = {}
	local AbsR = {}
	for i = 1, 3 do
		R[i] = {}
		AbsR[i] = {}
		for j = 1, 3 do
			local worldAxis = Vector3.new((j == 1) and 1 or 0, (j == 2) and 1 or 0, (j == 3) and 1 or 0)
			R[i][j] = u[i]:Dot(worldAxis)
			AbsR[i][j] = math.abs(R[i][j]) + 1e-6
		end
	end

	-- Test axes (sorry me)
	for i = 1, 3 do
		local ra = obbHalfSize[i]
		local rb = aabbHalfSize.X * AbsR[i][1] + aabbHalfSize.Y * AbsR[i][2] + aabbHalfSize.Z * AbsR[i][3]
		if math.abs(t[i]) > ra + rb then
			return false
		end
	end
	for j = 1, 3 do
		local ra = obbHalfSize[1] * AbsR[1][j] + obbHalfSize[2] * AbsR[2][j] + obbHalfSize[3] * AbsR[3][j]
		local rb = aabbHalfSize[j]
		-- t dot vj is just component j of tWorld since AABB axes are world axes
		local tDotVj = (j == 1 and tWorld.X) or (j == 2 and tWorld.Y) or tWorld.Z
		if math.abs(tDotVj) > ra + rb then
			return false
		end
	end

	local a = obbHalfSize
	local b = aabbHalfSize

	-- ok from now im not explaining any more of my garbage programming
	local function abs(x) return math.abs(x) end

	local ra = a.Y * AbsR[3][1] + a.Z * AbsR[2][1]
	local rb = b.Y * AbsR[1][3] + b.Z * AbsR[1][2]
	local tVal = abs(t[3] * R[2][1] - t[2] * R[3][1])
	if tVal > ra + rb then return false end

	ra = a.Y * AbsR[3][2] + a.Z * AbsR[2][2]
	rb = b.X * AbsR[1][3] + b.Z * AbsR[1][1]
	tVal = abs(t[3] * R[2][2] - t[2] * R[3][2])
	if tVal > ra + rb then return false end

	ra = a.Y * AbsR[3][3] + a.Z * AbsR[2][3]
	rb = b.X * AbsR[1][2] + b.Y * AbsR[1][1]
	tVal = abs(t[3] * R[2][3] - t[2] * R[3][3])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[3][1] + a.Z * AbsR[1][1]
	rb = b.Y * AbsR[2][3] + b.Z * AbsR[2][2]
	tVal = abs(t[1] * R[3][1] - t[3] * R[1][1])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[3][2] + a.Z * AbsR[1][2]
	rb = b.X * AbsR[2][3] + b.Z * AbsR[2][1]
	tVal = abs(t[1] * R[3][2] - t[3] * R[1][2])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[3][3] + a.Z * AbsR[1][3]
	rb = b.X * AbsR[2][2] + b.Y * AbsR[2][1]
	tVal = abs(t[1] * R[3][3] - t[3] * R[1][3])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[2][1] + a.Y * AbsR[1][1]
	rb = b.Y * AbsR[3][3] + b.Z * AbsR[3][2]
	tVal = abs(t[2] * R[1][1] - t[1] * R[2][1])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[2][2] + a.Y * AbsR[1][2]
	rb = b.X * AbsR[3][3] + b.Z * AbsR[3][1]
	tVal = abs(t[2] * R[1][2] - t[1] * R[2][2])
	if tVal > ra + rb then return false end

	ra = a.X * AbsR[2][3] + a.Y * AbsR[1][3]
	rb = b.X * AbsR[3][2] + b.Y * AbsR[3][1]
	tVal = abs(t[2] * R[1][3] - t[1] * R[2][3])
	if tVal > ra + rb then return false end

	-- all this for maybe a 10% performance increase bruh programming is hard
	return true
end

local function SphereVsAABB(sphereCenter, sphereRadius, aabbCenter, aabbHalfSize)
	local closestPoint = Vector3.new(
		math.clamp(sphereCenter.X, aabbCenter.X - aabbHalfSize.X, aabbCenter.X + aabbHalfSize.X),
		math.clamp(sphereCenter.Y, aabbCenter.Y - aabbHalfSize.Y, aabbCenter.Y + aabbHalfSize.Y),
		math.clamp(sphereCenter.Z, aabbCenter.Z - aabbHalfSize.Z, aabbCenter.Z + aabbHalfSize.Z)
	)

	local difference = sphereCenter - closestPoint
	local distanceSquared = difference.Magnitude^2
	--this one was alot easier
	return distanceSquared <= sphereRadius^2
end

local function shouldKeepVoxel(shapeBounds, voxelCFrame, voxelSize)
	local halfSize = voxelSize / 2

	if shapeBounds.PartType == Enum.PartType.Block then
		return not OBBvsAABB(
			shapeBounds.CFrame,
			shapeBounds.Size / 2,
			voxelCFrame,
			halfSize
		)
	elseif shapeBounds.PartType == Enum.PartType.Ball then
		local radius = math.max(shapeBounds.Size.X, shapeBounds.Size.Y, shapeBounds.Size.Z) / 2
		return not SphereVsAABB(
			shapeBounds.CFrame.Position,
			radius,
			voxelCFrame,
			halfSize
		)
	end

	-- Default: keep it
	return true
end

function module.ReconstructParts(voxels)
	if #voxels == 0 then return {} end

	-- might add greedy meshing later??? sounds kinda unoptimized tho
	local parts = {}

	for _, voxel in ipairs(voxels) do
		table.insert(parts, {
			CFrame = voxel.CFrame,
			Size = voxel.Size,
		})
	end

	return parts
end

function module.AcceptCachedData(InitialParts: {Part},shapedescription: {}--[[cframe, size, partType]], AxisMinLength: number) --i pulled an all nighter for this
	local CutVoxels = {}
	local RemainingVoxels = {}
	local VoxelQueue = {}
	local SeenSet = {}

	local shapeBounds = {
		["CFrame"] = shapedescription[1],
		["Size"] = shapedescription[2],
		["PartType"] = shapedescription[3],
	}

	-- check all colliding parts to see if they can be voxelized
	for _, partData in ipairs(InitialParts) do
		if partData.Tag then
			table.insert(VoxelQueue, partData)
			SeenSet[partData] = true
		end
	end


	while #VoxelQueue > 0 do
		local Current = table.remove(VoxelQueue, 1)
		local size = GetLongestAxis(Current.Size).Magnitude

		if size <= AxisMinLength then
			-- goes under limit add voxel NOW!!
			if shouldKeepVoxel(shapeBounds, Current.CFrame, Current.Size) then
				print("remain")
				table.insert(RemainingVoxels,Current)
			else
				table.insert(CutVoxels, Current)
			end
		else
			-- cut up the parts and do some math
			local Divided = DividePart(Current)

			for _, SubPart in pairs(Divided) do
				local subSize = GetLongestAxis(SubPart.Size).Magnitude
				if subSize <= AxisMinLength then
					if shouldKeepVoxel(shapeBounds, SubPart.CFrame, SubPart.Size) then
						print("remain")
						table.insert(RemainingVoxels,SubPart)
					else
						table.insert(CutVoxels, SubPart)
					end
				elseif shapeBounds.PartType == Enum.PartType.Block then
					if OBBvsAABB(shapeBounds.CFrame,shapeBounds.Size/2,SubPart.CFrame,SubPart.Size/2) then
						if not SeenSet[SubPart] then
							SeenSet[SubPart] = true
							table.insert(VoxelQueue, SubPart)
						end
					else
						print("remain")
						table.insert(RemainingVoxels,SubPart)
					end
				elseif shapeBounds.PartType == Enum.PartType.Ball then
					if SphereVsAABB(shapeBounds.CFrame.Position,math.max(shapeBounds.Size.X/2,shapeBounds.Size.Y/2,shapeBounds.Size.Z/2),SubPart.CFrame,SubPart.Size/2) then
						if not SeenSet[SubPart] then
							SeenSet[SubPart] = true
							table.insert(VoxelQueue, SubPart)
						end
					else
						print("remain")
						table.insert(RemainingVoxels,SubPart)
					end
				else
					-- ignore it
					if not SeenSet[SubPart] then
						SeenSet[SubPart] = true
						table.insert(VoxelQueue, SubPart)
					end
				end
			end
		end
	end

	local RemainingParts = module.ReconstructParts(RemainingVoxels)

	print(CutVoxels)
	print(RemainingVoxels)

	return CutVoxels,RemainingVoxels
end

local bindableFunc = game.ServerStorage.Voxelization

function module.RunVoxelization(cachedParts, shapeBounds, axisMinLength)
	-- Send data to Actor script and wait for result
	local voxels,reconstruct = bindableFunc:Invoke({
		parts = cachedParts,
		bounds = shapeBounds,
		minLength = axisMinLength
	})
	return voxels,reconstruct
end

return module

parallel script:


local bindableFunc = game.ServerStorage.Voxelization
local voxelModule = require(game.ServerScriptService.VoxelHandler)

bindableFunc.OnInvoke = function(data)
	-- Run voxelization inside the Actor (parallel safe!)
	local voxels,reconstruct = voxelModule.AcceptCachedData(data.parts, data.bounds, data.minLength)

	print(voxels)
	print(reconstruct)

	return voxels,reconstruct
end

current testing script

local TweenService = game:GetService("TweenService")
local VoxelHandler = require(game.ServerScriptService.VoxelHandler)

script.Parent.Activated:Connect(function()
	local MouseCFrame = script.Parent.GetMouse:InvokeClient(game.Players:GetPlayerFromCharacter(script.Parent.Parent))
	local NewVoxelizer = Instance.new("Part")
	NewVoxelizer.Shape = Enum.PartType.Ball
	NewVoxelizer.Size = Vector3.new(1,1,1)
	NewVoxelizer.Anchored = true
	NewVoxelizer.Color = Color3.new(1,0,0)
	NewVoxelizer.Transparency = 0.8
	NewVoxelizer.CFrame = MouseCFrame
	NewVoxelizer.CanCollide = false
	NewVoxelizer.CanQuery = false
	NewVoxelizer.Parent = game.Workspace
	
	local StartTick = tick()
	local Tween = TweenService:Create(NewVoxelizer,TweenInfo.new(1),{Size = Vector3.new(100,100,100)})
	Tween:Play()
	
	repeat
		task.wait(0.01)
		local cached = {}
		for _, part in pairs(workspace:GetPartsInPart(NewVoxelizer)) do
			if part:IsA("BasePart") and part:HasTag("Voxelize") then
				table.insert(cached, {
					CFrame = part.CFrame,
					Size = part.Size,
					Tag = true -- you could store other info too maybe just be careful
				})
				part:Destroy()
			end
		end

		local voxelMetaData,ReconstructionMetaData = VoxelHandler.RunVoxelization(cached,{NewVoxelizer.CFrame,NewVoxelizer.Size,NewVoxelizer.Shape},3)
		print(voxelMetaData)
		print(ReconstructionMetaData)
		--[[for _, v in ipairs(voxelMetaData) do
		local p = Instance.new("Part")
		p.Anchored = false
		p.Size = v.Size
		p.CFrame = v.CFrame
		p.Parent = workspace
	end]]
		for _, v in ipairs(ReconstructionMetaData) do
			local p = Instance.new("Part")
			p.Anchored = true
			p.Size = v.Size
			p.CFrame = v.CFrame
			p.Parent = workspace
			p:AddTag("Voxelize")
		end
	until
	tick() - StartTick >= 1
	
	NewVoxelizer:Destroy()
end)

edit: video (forgot to add colors oops) and fixed the scripts

if you cant tell the difference between this one and the last one, this one has MUCH more detail while still being pretty performant (although really the minimum size should be around 5-7 for huge things like that)

1 Like