Voxelization using Quadtree Partitioning

Help and Feedback Scripting Support
#1

Hello, I’ve been making voxel physics for my game. Everything seems well and fine, except for that it lags very hard when trying to voxelize larger walls, as many small parts are being made in order to fill the wall.

As I was looking into ways to try to fix this, I came across Quadtree partitioning. It is exactly what I need in order for this. The game Voxel Destruction Physics uses this to help with optimization, as it is very powerful.

Basically, the whole wall will voxelize, with parts closer to the impact point being more packed together.

Spatial-partitioning-data-structures
Spatial-partitioning-data-structures850×761 47.7 KB

This is the code I have for creating the voxels.

local function Divide(part : BasePart, targetBlockSize, HitPosition : Vector3)
	
	if not part:IsA("BasePart") then return nil, nil end
	if part:IsA("TrussPart") then return nil, nil end
	
	local NewParts = {}
	
	local Blocks = {}

	local function Elw(vec, op)
		return Vector3.new(op(vec.X), op(vec.Y), op(vec.Z))
	end

	local blockCount = Elw(part.Size, function(l) return math.floor(l / targetBlockSize) end)
	local blockSize = part.Size / blockCount
	local Offset = (part.Size + blockSize) / 2.0;
	
	local Health = nil
	
	pcall(function()
		Health = (blockSize.Magnitude / part:GetAttribute("Health")) / 0.01
	end); --smaller part has less health, bigger has more health
	
	local NewCS = ChunkSystem.new(3, blockSize.X)

	
	for x = 1, blockCount.X do 
		Blocks[x] = {}
		for y = 1, blockCount.Y do
			Blocks[x][y] = {}
			for z = 1, blockCount.Z do
				
				--local p = Instance.new("Part")
				--p.Anchored = true
				--p.Size = blockSize
				--p.CFrame =  part.CFrame:ToWorldSpace(CFrame.new(Vector3.new(x,y,z) * blockSize - Offset));
				--p.Parent = workspace
				
				Blocks[x][y][z] = {
					
					Offset = Offset;
					CF = part.CFrame:ToWorldSpace(CFrame.new(Vector3.new(x,y,z) * blockSize - Offset));
					Position = Vector3.new(x, y, z);
					OriginalSize = part.Size;
					BlockSize = blockSize;
					Health = Health;
					
					PropertyInfo = {
						Color = part.Color;
						Material = part.Material;
						Transparency = part.Transparency;
						Reflectance = part.Reflectance;
						CastShadow = part.CastShadow;
						Name = part.Name..":"..x..":"..y..":"..z;
						Parent = part.Parent;
						
						Descendants = part:GetDescendants()
					}
				}
			end
		end
	end

	return Blocks, blockCount
end

If someone can figure out a way to just make it more optimized using Quadtrees, I’d be very very thankful.

4 Likes
Making these Voxel Destruction Physics
How to do optimized Voxel Destruction?
#2

I have an example of a Octree that I started and has a few functions:
octree.rbxl (55.3 KB)

1 Like
#3

it helps me understand it more, but the way i need it is to work to breakdown the chunks to get smaller depending on proximity to the point, and larger the further away it is.

1 Like
#4

I don’t have time to read your code, but here is how I would go about it. (Note a quadtree will be 2 dimensions only, depending on specific needs you might need to extend this to an octree)

Take a block and take the collision point. First split up the block into its 4(8) pieces. Call that the split function. Then take the position and see which cell the point resides in. Take that block and pass it again through the split function (generate 4(8) parts in its place). Do this recursively until you hit minsize.

Some considerations, a point can land directly in between 2 cells, you’ll need to consider that. Also, this makes it so that points in the center of large cells are the most realistic, you’ll need to consider a bit more to allow it to break up perfectly in any position. Consider the collision as a circle for this instead of a point probably. Splitting up cells that collide with the circle or sphere instead of checking a single point. So basically just measure the cell distance from point and split it based on if it hits a specific distance threshold I guess is the simplification here.

1 Like
#5

yeah i have no idea how to implement it onto my script though

1 Like