Three dimensional table in Lua

Question

I need the best way to store a three dimensional table for pixels. What I need to do is have multiple x,y tables (basically three dimensional) it is to raster multiple two dimensional pixel maps with transparency. You see I can create two dimensions easily like so:

pixels = {{},{}}
pixels[1][5] = "green" --just an example
print(pixels[1][5])

However, I cannot do this like I can in Java...

pixels = {{}, {}, {}}
pixels[1][4][3] = "red" -- [x][y][z]
print(pixels[1][4][3])

This is the functionality I want, but I have disgustingly got around this by doing this...

pixels = {}
pixels["x23,y02,z05"] = "green"
print(pixels["x23,y02,z05"]")

I just use string.sub, and string.concat to read and set the tables... I really would like the functionality of example 2 to work, however I know it might need to be implemented differently.

Answer 1

There are basically two ways to go about this

Auto-tables

Auto-tables generate sub-tables transparently using metatables and essentially after creating it you should be able to forget about them.

function newAutotable(dim)
    local MT = {};
    for i=1, dim do
        MT[i] = {__index = function(t, k)
            if i < dim then
                t[k] = setmetatable({}, MT[i+1])
                return t[k];
            end
        end}
    end

    return setmetatable({}, MT[1]);
end

-- Usage
local at = newAutotable(3);
print(at[0]) -- returns table
print(at[0][1]) -- returns table
print(at[0][1][2]) -- returns nil
at[0][1][2] = 2;
print(at[0][1][2]) -- returns value
print(at[0][1][3][3]) -- error, because only 3 dimensions set

What is not so nice about them is that they generate lots of tables -- obviously. That's some memory overhead and each level of depth increases the execution time.

What's nice about them is that they can be completely dynamic in size. You could even make them infinitely deep. Though in your use-case this is very likely not necessary and probably even a bad idea.

This structure is very suitable for non-integer indexes though, you could for example make the depth even depend on a "template structure" and so implement a transparent dynamic configuration table, but I'm getting side-tracked...

Flattened arrays

The other variant are flattened arrays. user3125367 already wrote about them, but I want to expand on this as this can be done a lot more convenient and explain a few things.

Often flattening your multi-dimensional arrays is a good idea in CG anyway, since then you can do many matrix operations very easily. Calculating a modified index is also relatively cheap in terms of processing time required. But it should be noted, although kind of obvious, that this approach only works with numeric keys and a predefined size of your matrix.

function newMdArray(X, Y, Z)
    local MT = { __call = function(t, x, y, z, v)
        if x>X or y>Y or z>Z or x<1 or y<1 or z<1 then return; end
        local k = x + X*(y-1) + X*Y*(z-1);
        if v ~= nil then t[k] = v; end
        return t[k];
    end };
    return setmetatable({}, MT);
end

-- Usage
local mdt = newMdArray(100, 100, 100);
local v = mdt(1, 2, 3);
mdt(1, 2, 3, v*.1);

This code is taken from another answer from me: dynamic tables or arrays

It can probably be optimised a little (for example calculate X*Y in the closure) but I wanted to paste the original code here. Anyway, with this you can both easily work on the flattened structure by just using normal array indexing:

for i=1, #mdt
    mdt[i] = (mdt[i] or 0)*.5
end

As well as access 3d indexes directly:

mdt(12, 13, 14, 0)

You can also easily modify the function to return a default value for missing keys by adding an __index field to the metatable or so that the table saves the matrix dimensions etc.

Answer 2

In addition to classic 'array in array in array' scheme, you can use benefits of Lua table internals. How? Lua table is just a mapping from key to value, and when you use it as an array, you may skip some keys and this will cost virtually nothing.

t = { }
t[1] = "Hello"
t[500000] = "World" -- does NOT allocate additional 499999 elements

So, if your data is sparse (over 50% of your 3d-points having no value), you may benefit from this:

local n_x, n_y, n_z = 1920, 1080, 1000
local n_xy = n_x * n_y

function setValue(t, x, y, z, value)
    assert(x > 0 and x < n_x)
    assert(y > 0 and y < n_y)
    assert(z > 0 and z < n_z)

    t[((z-1) * n_xy) + ((y-1) * n_z) + x] = value
end

function getValue(t, x, y, z)
    assert(x > 0 and x < n_x)
    assert(y > 0 and y < n_y)
    assert(z > 0 and z < n_z)

    return t[((z-1) * n_xy) + ((y-1) * n_z) + x]
end

t = { }
setValue(t, 1, 1, 1, "red")
setValue(t, 1, 1, 2, "green")