How to "flatten" or "index" 3D-array in 1D array?

Question

I am trying to flatten 3D array into 1D array for "chunk" system in my game. It's a 3D-block game and basically I want the chunk system to be almost identical to Minecraft's system (however, this isn't Minecraft clone by any measure). In my previous 2D-games I have accessed the flattened array with following algorithm:

Tiles[x + y * WIDTH]

However, this obviously doesn't work with 3D since it's missing the Z-axis. I have no idea how to implement this sort of algorithm in 3D-space. Width, height and depth are all constants (and width is just as large as height).

Is it just x + y*WIDTH + Z*DEPTH ? I am pretty bad with math and I am just beginning 3D-programming so I am pretty lost :|

PS. The reason for this is that I am looping and getting stuff by index from it quite a lot. I know that 1D arrays are faster than multi-dimensional arrays (for reasons I cant remember :P ). Even though this may not be necessary, I want as good performance as possible :)

Answer 1

Here is a solution in Java that gives you both:

• from 3D to 1D
• from 1D to 3D

Below is a graphical illustration of the path I chose to traverse the 3D matrix, the cells are numbered in their traversal order:

Conversion functions:

public int to1D( int x, int y, int z ) {
    return (z * xMax * yMax) + (y * xMax) + x;
}

public int[] to3D( int idx ) {
    final int z = idx / (xMax * yMax);
    idx -= (z * xMax * yMax);
    final int y = idx / xMax;
    final int x = idx % xMax;
    return new int[]{ x, y, z };
}

Answer 2

The algorithm is mostly the same. If you have a 3D array Original[HEIGHT, WIDTH, DEPTH] then you could turn it into Flat[HEIGHT * WIDTH * DEPTH] by

Flat[x + WIDTH * (y + DEPTH * z)] = Original[x, y, z]

As an aside, you should prefer arrays of arrays over multi-dimensional arrays in .NET. The performance differences are significant

Answer 3

I think the above needs a little correction. Lets say you have a HEIGHT of 10, and a WIDTH of 90, single dimensional array will be 900. By the above logic, if you are at the last element on the array 9 + 89*89, obviously this is greater than 900. The correct algorithm is:

Flat[x + HEIGHT* (y + WIDTH* z)] = Original[x, y, z], assuming Original[HEIGHT,WIDTH,DEPTH] 

Ironically if you the HEIGHT>WIDTH you will not experience an overflow, just complete bonkers results ;)

Answer 4

x + y*WIDTH + Z*WIDTH*DEPTH. Visualize it as a rectangular solid: first you traverse along x, then each y is a "line" width steps long, and each z is a "plane" WIDTH*DEPTH steps in area.

Answer 5

You're almost there. You need to multiply Z by WIDTH and DEPTH:

Tiles[x + y*WIDTH + Z*WIDTH*DEPTH] = elements[x][y][z]; // or elements[x,y,z]

Answer 6

TL;DR

The correct answer can be written various ways, but I like it best when it can be written in a way that is very easy to understand and visualize. Here is the exact answer:

(width * height * z) + (width * y) + x

TS;DR

Visualize it:

someNumberToRepresentZ + someNumberToRepresentY + someNumberToRepresentX

someNumberToRepresentZ indicates which matrix we are on (depth). To know which matrix we are on, we have to know how big each matrix is. A matrix is 2d sized as width * height, simple. The question to ask is "how many matrices are before the matrix I'm on?" The answer is z:

someNumberToRepresentZ = width * height * z

someNumberToRepresentY indicates which row we are on (height). To know which row we are on, we have to know how big each row is: Each row is 1d, sized as width. The question to ask is "how many rows are before the row I'm on?". The answer is y:

someNumberToRepresentY = width * y

someNumberToRepresentX indicates which column we are on (width). To know which column we are on we simply use x:

someNumberToRepresentX = x

Our visualization then of

someNumberToRepresentZ + someNumberToRepresentY + someNumberToRepresentX

Becomes

(width * height * z) + (width * y) + x

Answer 7

The forward and reverse transforms of Samuel Kerrien above are almost correct. A more concise (R-based) transformation maps are included below with an example (the "a %% b" is the modulo operator representing the remainder of the division of a by b):

dx=5; dy=6; dz=7  # dimensions
x1=1; y1=2; z1=3  # 3D point example
I = dx*dy*z1+dx*y1+x1; I  # corresponding 2D index
# [1] 101
x= I %% dx; x  # inverse transform recovering the x index
# [1] 1
y = ((I - x)/dx) %% dy; y  # inverse transform recovering the y index
# [1] 2
z= (I-x -dx*y)/(dx*dy); z  # inverse transform recovering the z index
# [1] 3

Mind the division (/) and module (%%) operators.

Answer 8

The correct Algorithm is:

Flat[ x * height * depth + y * depth + z ] = elements[x][y][z] 
where [WIDTH][HEIGHT][DEPTH]

Answer 9

To better understand description of 3D array in 1D array would be ( I guess Depth in best answer is meant Y size)

IndexArray = x + y * InSizeX + z * InSizeX * InSizeY;

IndexArray = x + InSizeX * (y + z * InSizeY);

Answer 10

m[x][y][z] = data[xYZ + yZ + z]

x-picture:
0-YZ
.
.
x-YZ

y-picture 

0-Z
.
.
.
y-Z


summing up, it should be : targetX*YZ + targetY*Z + targetZ  

Answer 11

In case, somebody is interested to flatten an nD (2D, 3D, 4D, ...) array to 1D, I wrote the below code. For example, if the size of the array in different dimensions is stored in the sizes array:

#  pseudo code
sizes = {size_x, size_y, size_z,...};

This recursive function gives you the series of {1, size_x, size_x*size_y, size_x*size_y*size_z, ...}

// i: number of the term
public int GetCoeff(int i){
        if (i==0)
            return 1;
        return sizes[i-1]*GetCoeff(i-1);
}

So, we have to multiply nD indexes by their corresponding series term and sum them to get {ix + iy*size_x + iz*size_x*size_y, ...}:

// indexNd: {ix, iy, iz, ...}
public int GetIndex1d(int[] indexNd){
    int sum =0;
    for (var i=0; i<indexNd.Length;i++)
        sum += indexNd[i]*GetCoeff(i);
    return sum;
    
}

In this code I assumed, the nD array is contiguous in memory along firstly x, then y, z, ... . So probably you call your array-like arr[z,y,x]. But, if you call them the other way, arr[x,y,z] then z is the fastest index and we like to calculate iz + iy*size_z + ix* size_z*size_y. In this case, the below function gives us the series {1, size_z, size_z*size_y, ...}:

// Dims is dimension of array, like 3 for 3D
public int GetReverseCoeff(int i){
       if (i==0)
            return 1;
        return sizes[Dims-i]*GetReverseCoeff(i-1);
}

The coefficients are stored in the right order:

public void SetCoeffs(){
    for (int i=0;i<Dims;i++)
            coeffs[Dims-i-1] = GetReverseCoeff(i);
}

The 1D index is calculated the same as before except coeffs array is used:

// indexNd: {ix, iy, iz, ...}
public int GetIndex1d(int[] indexNd){
    int sum =0;
    for (var i=0; i<indexNd.Length;i++)
        sum += indexNd[i]*coeffs[i];
    return sum;
    
}

Answer 12

Samuel Kerrien's answer to python :

def to1D(crds,dims):
  x,y,z=crds
  xMax,yMax,zMax=dims
  return (z * xMax * yMax) + (y * xMax) + x

def to3D(idx,dims):
    xMax,yMax,zMax=dims
    z = idx // (xMax * yMax)
    idx -= (z * xMax * yMax)
    y = idx // xMax
    x = idx % xMax
    return x, y, z