1

I am a bit confused as I have tested a couple algorithms to compute z-indices and for (8, 8, 8) I get 3584 and for (7, 7, 7) I get 511, which is correct. The issue is 8*8*8 = 512, yet the z-index is 3584. That means if I use a one dimensional array to store things by the z-index, won't I be using more space and there will be empty slots in the array? Similarly 7*7*7 = 343, which is less than 511. If you look on the wikipedia page for z-indexing/Morton encoding, you will find a two dimensional example which is 8*8 with indices of x and y from 0 to 7. However, the largest z-index is 111111 which is 63, which when numbered from 0 is precisely the 64th element, so it does not use more space than necessary to store 64 elements. Is there something wrong here?

Thanks

Paul R
  • 208,748
  • 37
  • 389
  • 560
SwiftMatt
  • 949
  • 1
  • 9
  • 19

1 Answers1

1

It turns out that when you have z-indexing, the final index will only equal the index of regular indexing if the coordinate is on the edge of a power of two cube. The original issue of (7,7,7) having a z-index of 511 aligns with the fact that 8*8*8 = 512. Considering that coordinates of 0 are included, (7,7,7) is indeed the 8^3 index. The z-index of (3,3,3) can be calculated as follows. In binary, (3,3,3) is (011,011,011) By interleaving the bits, the z-index in binary is 000111111. This value in decimal is 63. What confused me was that 3*3*3 is only equal to 27, and I was wondering why I needed an index greater than 27, leaving some indices unused for a cube of 3x3x3. I later discovered that this is simply how z-indexing works. Only for cubes with sides of length equal to a perfect power of two will every z-index have coordinates that are <= (x,y,z)

SwiftMatt
  • 949
  • 1
  • 9
  • 19