an algorithm to encode binary voxels (essentially a 3-dimensional table storing booleans) into a buffer, which can then be further serialized to JSON via base64.
It uses LZW compression to store the coordinates of the voxels. Best case scenario it uses 3 bytes to represent each voxel regardless of location, although it is limited by the 32 bit signed integer limit.
buffer format explanation for nerds
The buffer format is [flag][size][dictionary][data]
-
flag
is a u8 representing the format to use for decoding the data, which is either u8, u16, or u32 (8, 16, or 32 respectively)
-
size
is a u32 representing the length of the LZW dictionary, which is just a stream of numbers where the index is the ID
-
dictionary
is 4*size
bytes long because all elements use i32 (4 byte integer)
-
data
takes up the remaining buffer, and depending on the flag
it uses either u8, u16, or u32 to represent IDs from the dictionary.
- it is read in groups of 3 to represent the coordinates (X, Y, and Z) so the length of
data
is always a multiple of 3.
Code snippets
Encoder:
...
local b: buffer
if i < 2^8 then -- unsigned 8 bit encoding
b = buffer.create(5 + i*4 + #data)
buffer.writeu8(b, 0, 8)
buffer.writeu32(b, 1, i)
for j, v in mapList do
buffer.writei32(b, j*4+1, v)
end
for j, v in data do
buffer.writeu8(b, j+i*4+4, v)
end
elseif i < 2^16 then -- unsigned 16 bit encoding
b = buffer.create(5 + i*4 + #data*2)
buffer.writeu8(b, 0, 16)
buffer.writeu32(b, 1, i)
for j, v in mapList do
buffer.writei32(b, j*4+1, v)
end
for j, v in data do
buffer.writeu16(b, i*4+j*2+3, v)
end
else -- unsigned 32 bit encoding
b = buffer.create(5 + i*4 + #data*4)
buffer.writeu8(b, 0, 32)
buffer.writeu32(b, 1, i)
for j, v in mapList do
buffer.writeu32(b, j*4+1, v)
end
for j, v in data do
buffer.writeu32(b, i*4+j*4+1, v)
end
end
...
Decoder:
...
local t: Tensor.Tensor<boolean> = Tensor.new()
if intLen == 8 then
for i = 1, mapLen do
map[i] = buffer.readi32(b, i*4+1)
end
for i = mapLen*4+5, buffer.len(b)-1, 3 do
local x: number = buffer.readu8(b, i)
local y: number = buffer.readu8(b, i+1)
local z: number = buffer.readu8(b, i+2)
t:Set(map[x], map[y], map[z], true)
end
elseif intLen == 16 then
for i = 1, mapLen do
map[i] = buffer.readi32(b, i*4+1)
end
for i = mapLen*4+5, buffer.len(b)-1, 6 do
local x: number = buffer.readu16(b, i)
local y: number = buffer.readu16(b, i+2)
local z: number = buffer.readu16(b, i+4)
t:Set(map[x], map[y], map[z], true)
end
else
for i = 1, mapLen do
map[i] = buffer.readi32(b, i*4+1)
end
for i = mapLen*4+5, buffer.len(b)-1, 12 do
local x: number = buffer.readu32(b, i)
local y: number = buffer.readu32(b, i+4)
local z: number = buffer.readu32(b, i+8)
t:Set(map[x], map[y], map[z], true)
end
end
...
base64 may unintentionally spell out profanity