Hi, it’s me again. I’ve done voxel stuff in the past, but I think this one is big enough to deserve its own topic.
Quick terminologies:
Voxel - A 3-dimensional pixel; usually represented as blocks. Minecraft, for example, is a voxel game.
Multithreading - This project uses Parallel Luau to multithread certain processes to make them faster.
LoD - Level of Detail; a common feature in games that makes faraway objects render at a lower quality to save performance. You may know this in Roblox as RenderFidelity.
LoD system demo video:
Multithreading demo video:
(There are 343 chunks, each 16x16x16 in size, meaning there’s over 1.4 million voxels!)
Basic explanation on how it works
How does it work?
Chunks use several 3-dimensional tables to represent the voxels. For simplicity, I will be calling them tensors, and they are organized in tensor[x][y][z] = value
format. The reason why they have multiple tensors is because each tensor will represent each level of LoD (there are 4 levels).
When a chunk is created, all 4 tensors will be filled with booleans to represent the physical world; true
means the voxel is occupied, and false
means air. A 3D Perlin noise algorithm is used to generate those booleans for each voxel based on the voxel’s position in the world.
--for the voxel located at (1, 2, 3)
tensor[1][2][3] = perlinNoise3D(1, 2, 3) --> true or false
To save performance, instead of loading in every single occupied voxel, we can just only load in the surface voxels. It’s going to be like marching cubes but everything will remain cubical. Surface voxels are just voxels that are next to air, and we will loop through the entire tensor to find them.
Note that marching cubes is not the only optimization method. A better one would be greedymeshing, but for the purpose and use case of this project, I deem it unfeasible. Note that I do have an older voxel project that does use greedymeshing if you’re interested.
Multithreading
The tensor-generating process is all multithreaded. There is an arbitrary number of actors (workers). When you create a chunk, it will first pick the laziest worker (least amount of current tasks) and instruct it to do work via a BindableEvent. It will take time, so the chunk will actually wait until the worker returns back the result.
function newChunk(...)
...
local worker = getLazyActor() --find a lazy worker
local results
worker.ReturnSignal:Once(function(data) --listen for the returned results
results = data
end)
worker.InstructSignal:Fire(chunkData) --give them instructions to do work
while results == nil do task.wait() end --wait until they are done with the homework
local tensors = results.stuff --continue doing stuff
...
end
Data Compression
But, you may ask, isn’t it very expensive to send super-big tables across BindableEvents? You are right, which is why the data is actually being compressed! It uses LZW compression, the same compression system I used in my older voxel project (link already shared above).
Basically, there is a massive lookup table storing every possible voxel position relative to the chunk (A 16x16x16 chunk has exactly 4096 voxels). This allows the voxels to be easily converted between Vector3 and a 3-character string. The tensor is encoded into a string by the worker before returning it, and then on arrival, it gets decoded back into a tensor.
After all the tensors are ready, you can just tell the chunk which one to load in. It will read the entire tensor and create parts based on the coordinates.
for x, y, z, v in tensor:iter() do
newPart(x, y, z)
end
Below are some (and parts) of the code I used. I put them here to hopefully give any aspiring prospector some ideas if they are doing anything similar to what I made.
Code for the "Tensor" class object, used to store voxels
type class = {
new: <T>(tensorValue<T>?) -> tensor<T>,
}
export type array<T> = {[number]: T}
export type matrix<T> = {[number]: array<T>}
export type tensorValue<T> = {[number]: matrix<T>}
export type tensor<T> = { --later aliased in scripts to become Tensor<T> with an uppercase
_ : tensorValue<T>,
set: (self: tensor<T>, x: number, y: number, z: number, value: T) -> (),
get: (self: tensor<T>, x: number, y: number, z: number) -> T?,
iter: (self: tensor<T>) -> () -> (number, number, number, T),
}
local Tensor = {}
Tensor.__index = Tensor
function Tensor.new<T>(tensor: tensorValue<T>?): tensor<T>
return setmetatable({_ = tensor or {}}, Tensor)::any
end
function Tensor.set<T>(self: tensor<T>, x: number, y: number, z: number, value: T): ()
local m: matrix<T>? = self._[x]
if m then
local a: array<T>? = m[y]
if a then
a[z] = value
return
end
m[y] = {[z] = value}
return
end
self._[x] = {[y] = {[z] = value}}
return
end
function Tensor.get<T>(self: tensor<T>, x: number, y: number, z: number): T?
local m: matrix<T>? = self._[x]
if m then
local a: array<T>? = m[y]
if a then
return a[z]
end
end
return nil
end
function Tensor.iter<T>(self: tensor<T>): () -> (number, number, number, T)
return coroutine.wrap(function()
for x, m in self._ do
for y, a in m do
for z, v in a do
coroutine.yield(x, y, z, v)
end
end
end
end)
end
return (Tensor::any)::class
Use example of the Tensor data structure
local Tensor = require(script.Tensor)
type Tensor<T> = Tensor.tensor<T>
local thing: Tensor<Vector3> = Tensor.new() --generic type accepts anything
thing:set(1, 2, 3, Vector3.one) --set a value
print(thing:get(1, 2, 3)) --read a value
thing:set(1, 2, 4, Vector3.zero)
for x, y, z, value in thing:iter() do --iterate through the tensor
print(x, y, z, '|', value)
end
Snippet of the voxel/tensor compression system
...
local encode: {[Vector3]: string} = {}
local decode: {[string]: Vector3} = {}
local timeBegin: number = os.clock()
local counter: number = 0
for x = 1, 32 do
for y = 1, 32 do
for z = 1, 32 do
counter += 1
local vec: Vector3 = Vector3.new(x, y, z)
local hash: string = base93.tobase93(counter)
if #hash == 1 then
hash = [[\\]]..hash
elseif #hash == 2 then
hash = [[\]]..hash
end
encode[vec] = hash
decode[hash] = vec
end
end
if x % 4 == 0 then --so u dont crash lol
task.wait()
end
end
print(`Time taken to init tensor encoder: {os.clock() - timeBegin}`)
local function encodeBinaryTensor(tensor: Tensor<boolean>): string
debug.profilebegin [==[encode binary tensor]==]
local hashes: {string} = {}
for x, y, z, v in tensor:iter() do --this is a coroutine iterator btw
if v == true then
table.insert(hashes, encode[Vector3.new(x, y, z)]) --encode is {[Vector3]: string}
end
end
debug.profileend()
return table.concat(hashes) --table.concat is excluded from profiler
end
local function decodeBinaryTensor(code: string): Tensor<boolean>
debug.profilebegin [==[decode binary tensor]==]
local t: Tensor<boolean> = Tensor.new()
for i = 1, #code, 3 do --split the long string into triplets (each triplet represents one voxel)
local vec: Vector3 = decode[string.sub(code, i, i+2)] --decode is {[string]: Vector3}
t:set(vec.X, vec.Y, vec.Z, true)
end
debug.profileend()
return t
end
...
Snippet of the actor scripts
...
instructEvent.Event:ConnectParallel(function(instruction: taskInstruction)
print(`Processor {id} received a new task`)
local encodeds: {string} = {}
for k, corner: Vector3 in instruction.corners do
local voxelDim: number = wCFG.lodVoxelDims[k]
local chunkDim: number = wCFG.lodChunkDims[k]
local scalarField: Tensor<boolean> = Tensor.new() --these are random names lol
local surfaceMap: Tensor<boolean> = Tensor.new()
local function getVoxel(x: number, y: number, z: number): boolean
local filled: boolean? = scalarField:get(x, y, z)
if filled == nil then --if the voxel doesn't exist, make one and store it
filled = perlin.noiseBinary(corner.X+x*voxelDim, corner.Y+y*voxelDim, corner.Z+z*voxelDim)
scalarField:set(x, y, z, filled::boolean)
end
return filled::boolean
end
local function isSurfaceVoxel(x: number, y: number, z: number): boolean --just check to see if the voxel is next to air (nothing)
if not getVoxel(x+1, y, z) then return true end
if not getVoxel(x-1, y, z) then return true end
if not getVoxel(x, y+1, z) then return true end
if not getVoxel(x, y-1, z) then return true end
if not getVoxel(x, y, z+1) then return true end
if not getVoxel(x, y, z-1) then return true end
return false
end
for x = 1, chunkDim do
for y = 1, chunkDim do
for z = 1, chunkDim do
if getVoxel(x, y, z) and isSurfaceVoxel(x, y, z) then
surfaceMap:set(x, y, z, true)
end
end
end
end
encodeds[k] = tensorEncoder.encodeBinaryTensor(surfaceMap)
end
local _r: taskResult = {
id = instruction.id,
encodedTensors = encodeds
}
returnEvent:Fire(_r)
end)
...
3D Perlin noise implementation
local seed: number = 123456
local genScale: number = 0.01
local noise = math.noise
local function noiseBinary(x: number, y: number, z: number): boolean
local trueY: number = y
y += 28.48675
x *= genScale; y *= genScale; z *= genScale
local _x = noise(y - 3.95382, z + 1.26932, seed)
local _y = noise(x + 7.40134, z - 5.48274, seed)
local _z = noise(x - 2.11045, y + 4.88563, seed)
return _x+_y+_z >= .5 --this number should change to make the world more spacious or full
end
local module = {
noiseBinary = noiseBinary,
}
return module