3D array (1D flat) indexing

Question

I am using a coordinate system x (width), y (height), z (Depth)

Just to clear confusion if there is any x & y are a flat plane and I am using Z as elevation.

I am going to be accessing the array millions of times per second and benchmarking shows that a 1D array using index is faster and I would like to squeeze as much efficiency as possible so that other things can use that time

For example a 2D array --> 1D array creation is just

Object[] oneDArray = new Object[width * height]

and to index the array I can just use the following.

Object obj = oneDArray[x + y * width]

I did find the following on stackoverflow but I am not entirely sure which one is correct How to "flatten" or "index" 3D-array in 1D array?

The "Correct" answer says to index the array do the following

Object[] oneDArray = new Object[width * height * depth]
Object obj = oneDArray[x + WIDTH * (y + DEPTH * z)]

But then another answer says that the "Correct" answer is wrong and uses the following

Object[] oneDArray = new Object[width * height * depth]
Object obj = oneDArray[x + HEIGHT* (y + WIDTH* z)]

What is the correct way to read a flattened 3D array?

Answer 1

This depends on that how you want to order your 3D data in 1D array, if you wanted to have indexes in order: Z, Y, X then your 2x2x2 dimensioned 3D data will be stored like this:

index 0: [z=0,y=0,x=0]
index 1: [z=0,y=0,x=1]
index 2: [z=0,y=1,x=0]
index 3: [z=0,y=1,x=1]
index 4: [z=1,y=0,x=0]
index 5: [z=1,y=0,x=1]
index 6: [z=1,y=1,x=0]
index 7: [z=1,y=1,x=1]

DEPTH dimension corresponds to z, HEIGHT to y and WIDTH to x

The index calculation will be: index = HEIGHT*WIDTH*z + WIDTH*y + x.

The x is not multiplied by anything because the next x index is right after the previous one.

If you want to skip one Y row, you have to add whole row WIDTH, in this case 2, for example if you are at index 1, which has z=0,y=0 and x=1 and you add WIDTH=2 to index, you'll get index 3. Only y dimension has increased by 1.

To move from z=0 to z=1, you have to skip 4 indexes (look up at the index listing), the number is HEIGHT*WIDTH (in this example 2*2).

Performance

To gain speed its best to process your 3D data with z,y,x coordinates incrementing in a sequence so you don't have to recalculate the index so often. For example:

int z = 1, y=1, x=0;
int index = HEIGHT*WIDTH*z + WIDTH*y;
int data;

for(x=0;x<WIDTH;x++)
{
    Object obj = oneDArray[index+x];
}

In ideal case, all processing of data is independent from each other and you don't have to even calculate the index, just increment one index trough whole oneDArray. What's possible to precompute depends on your usage.

Answer 2

Here is a solution in Java that gives you both:

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

My own micro benchmark showed that 1D array is 50% faster to get/set values than through 3D array.

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 };
}

The code above could surely be factorised to be faster, but I left it as such to make it easier to understand the 2 way conversion ;)

Answer 3

use the formula index = x*height*depth + y*depth + z Sample java code illustration.

public class FlattenedArray {
    public static void main(String[] args) {
        int width = 2;
        int height = 3;
        int depth = 4;
        int[][][] d3 = new int[width][height][depth];
        int[] d1 = new int[width*height*depth];

        //3D Array :
        int w=0;
        for(int i=0;i<width;i++) 
            for(int j=0;j<height;j++)
                for(int k=0;k<depth;k++) {
                    d3[i][j][k] = ++w;
                    System.out.print(d3[i][j][k] + " ");
                }
        System.out.println();

        //1D Array :
        w=0;
        for(int i=0;i<width;i++) 
            for(int j=0;j<height;j++)
                for(int k=0;k<depth;k++) {
                    int index = i*height*depth + j*depth + k;
                    d1[index] = ++w;
                }

        for(int i=0;i<width*height*depth;i++) {
            System.out.print(d1[i] + " ");
        }
    }
}