Одна альтернатива древовидному методу: используйте Morton-Order для кодирования ваших данных.
В трех измерениях это выглядит так: взять компоненты координат и перемежать каждый бит двумя нулевыми битами. Здесь показано в двоичном виде: 11111b становится 1001001001b
C-функция для этого выглядит следующим образом (показана для ясности и только для 11 битов):
int morton3 (int a)
{
int result = 0;
int i;
for (i=0; i<11; i++)
{
// check if the i'th bit is set.
int bit = a&(1<<i);
if (bit)
{
// if so set the 3*i'th bit in the result:
result |= 1<<(i*3);
}
}
return result;
}
Вы можете использовать эту функцию, чтобы объединить ваши позиции следующим образом:
index = morton3 (position.x) +
morton3 (position.y)*2 +
morton3 (position.z)*4;
Это превращает ваш трехмерный индекс в одномерный. Лучшая часть этого: значения, которые близки в трехмерном пространстве, близки и в одномерном пространстве. Если вы часто обращаетесь к значениям, близким друг к другу, вы также получите очень хорошее ускорение, потому что кодировка порядка следования является оптимальной с точки зрения локальности кэша.
Для morton3 вам лучше не использовать код выше. Используйте небольшую таблицу, чтобы найти 4 или 8 бит за раз и объединить их вместе.
Надеюсь, это поможет,
Nils