3d -> 1D array indexing

Question

in C++, what is the indexing value for a W * H * D sized 3D array?

for a particular i, j, k is this the correct indexing:

i*W*H+j*W+k

Answer 1

What you have written is equivalent to the pointer arithmetic that this would do:

T x[D][H][W];

x[i][j][k];  // Pointer arithmetic done here

Obviously, depending on how you order D, H and W (or i, j, k), the calculation will differ.

Answer 2

Width, height and depth are meaningless in this context. What you need to know is that multidimensional arrays are stored in row-major order.

Answer 3

If you need to to iterarate over all elements it is best to do in

for i
    for j
        for k

order. This way, it would be fastest, because index of array is incremented by one each time and values could be precached. There is no only one correct way to do this but you probably chose best one.

Answer 4

There is no one "correct" order, but the version you've given should work. The order in which you apply the indices will determine whether you do row-major or column-major indexing. If you're porting Fortran code (for example) it can make sense to reverse the "normal" C order.

Answer 5

Yes, assuming i varies from 0 ... D-1, j varies from 0 ... H-1, and k varies from 0 ... W-1.

Usually, though, the purpose of having an indexer, I thought, was to express relations within a sparse matrix so you didn't need to deal with the whole thing (and expend memory for it). If your data span the whole matrix, you might look into creating the 3d matrix as a pointer to an array of pointers, which themselves each point to an array of pointers. Using this allows you to use the x[i][j][k] notation but may be faster.

See http://www.nr.com/cpppages/chapappsel.pdf for a description.