Morton Encoding Z-indexing Использование пространства

Question

Я немного сбит с толку, так как я протестировал пару алгоритмов для вычисления z-индексов и для (8, 8, 8) я получаю 3584, а для (7, 7, 7) я получаю 511, что правильно. Проблема в 8*8*8 = 512, но z-index равен 3584. Это означает, что если я буду использовать одномерный массив для хранения вещей по z-index, я не буду использовать больше места и там будет пусто слоты в массиве? Точно так же 7*7*7 = 343, что меньше 511. Если вы посмотрите на странице википедии z-indexing/Morton кодирование, вы найдете двумерный пример, который 8 * 8 с индексами x и y от 0 до 7. Однако самый большой z-индекс равен 111111, то есть 63, который при нумерации от 0 является точно 64-м элементом, поэтому он не использует больше места, чем необходимо для хранения 64 элементов. Здесь что-то не так?

Спасибо

Answer 1

Оказывается, что при z-индексации конечный индекс будет равен индексу регулярной индексации только в том случае, если координата находится на границе степени двух кубов. Первоначальная проблема (7,7,7) с z-индексом 511 совпадает с тем фактом, что 8*8*8 = 512. Учитывая, что включены координаты 0, (7,7,7) действительно является 8^3 указатель. Z-индекс (3,3,3) можно рассчитать следующим образом. В двоичном коде (3,3,3) равно (011,011,011). При чередовании битов z-индекс в двоичном виде равен 000111111. Это значение в десятичном виде равно 63. Меня смутило то, что 3*3*3 равно только 27 и мне было интересно, почему мне нужен индекс больше 27, оставив некоторые индексы неиспользованными для куба 3x3x3. Позже я обнаружил, что это просто, как работает z-indexing. Только для кубов со сторонами длины, равными совершенной степени двух, каждый z-индекс будет иметь координаты <= (x,y,z)