Октодеревом называют древовидную структуру данных, каждый узел которой имеет восемь потомков. Октодеревья применяются для пространственной индексации, обнаружения столкновений в трехмерном пространстве, определения скрытых поверхностей, в трассировке лучей и методе конечных элементов.
Октодерево может быть представлено в виде иерархической структуры данных или линейно.
В иерархической структуре данных имеется корень дерева, узлы и листья. Каждый узел хранит указатели на его потомков.
При линейном представлении указатели не используются — применяются различные способы кодирования элементов и хранятся только листья дерева.
Одним из наиболее распространенных и эффективных способов кодирования является применение кривой Лебега (Z-кривой) и применение кривой Гильберта.
Достоинством кривой Гильберта является ее непрерывность — соседние элементы расположены последовательно. Преимуществом Z-кривой является простота и скорость вычисления, поэтому она чаще применяется на практике.
Двумерная кривая Лебега
Трехмерная кривая Лебега
Двумерная кривая Гильберта
Трехмерная кривая Гильберта
Для кодирования элементов с использованием Z-кривой используется код Мортона(обычно код вычисляется для узла с минимальными координатами). Код Мортона для Z-кривой вычисляется смещением и смешиванием бит двоичного представления каждой из координат.
Пример вычисления кода Мортона
С учетом свойств Z-кривой, для элементов необходимо хранить только глубину элемента (уровень в октодреве) и его порядок (расположение на Z-кривой). В элементы используемого массива для хранения ячеек сетки заносятся значения глубины элемента, а индекс элемента определяет его расположение на Z-кривой.
Для хранения глубины элемента достаточно использовать 1 байт(глубина дерева 256). Для многих задач может оказаться достаточной глубина дерева 16(размер минимальной ячейки будет в 2^15 = 32768 раз меньше исходной области). Тогда для хранения ячейки достаточно использовать 4 бита.
Для определения вещественных координат элемента необходимо выполнить следующие шаги:
1. вычисление кода Мортона для элемента
2. декодирование
3. перевод полученного индекса в вещественное значение каждой из координат
Рассмотрим алгоритм на примере кодирования каждой из координат 20-тью битами, то есть результирующий код всех трех координат будет занимать 60 бит.
Зная код и глубину предыдущего элемента, можно вычислить код текущего элемента. Код первого элемента всегда равен 0. Определим смещение для каждого уровня глубины:
Теперь будем определять индекс элемента через глубину и индекс предыдущего элемента:
Функция декодирования:
iXYZ[0], iXYZ[1], iXYZ[2] — определяют порядок кодирования(в данном случае сначала координата x, затем y, затем z).
Константы и количество шагов в функции decodeIndex определяются количеством бит и размерностью пространства(в данном примере константы приведены для трехмерного пространства и 20-ти бит на координату).
Существуют различные способы кодирования, примеры на
Bit Twiddling Hacks
How to compute a 3D Morton number (interleave the bits of 3 ints)
Для получения вещественных значений вершины ячейки с минимальными координатами, полученные индексы умножаются на величину шага. Величина шага — это размер минимальной допустимой ячейки сетки.
Размер ячейки можно определить по ее глубине. Остальные значения определяются прибавлением размера элементы к соответствующим минимальным координатам.
Деление элемента осуществляется путем увеличения его глубины и вставке после него 7 элементов этой же глубины.
Объединение — уменьшение глубины и удалении последующих 7 элементов.
Октодерево является активно изучаемой структурой данных и алгоритмы работы с ним(поиск соседей, интервалов, визуализация и тд) становятся темой докторских диссертаций и научных исследований.
Октодерево может быть представлено в виде иерархической структуры данных или линейно.
В иерархической структуре данных имеется корень дерева, узлы и листья. Каждый узел хранит указатели на его потомков.
При линейном представлении указатели не используются — применяются различные способы кодирования элементов и хранятся только листья дерева.
Одним из наиболее распространенных и эффективных способов кодирования является применение кривой Лебега (Z-кривой) и применение кривой Гильберта.
Достоинством кривой Гильберта является ее непрерывность — соседние элементы расположены последовательно. Преимуществом Z-кривой является простота и скорость вычисления, поэтому она чаще применяется на практике.
Двумерная кривая Лебега
Трехмерная кривая Лебега
Двумерная кривая Гильберта
Трехмерная кривая Гильберта
Для кодирования элементов с использованием Z-кривой используется код Мортона(обычно код вычисляется для узла с минимальными координатами). Код Мортона для Z-кривой вычисляется смещением и смешиванием бит двоичного представления каждой из координат.
Пример вычисления кода Мортона
С учетом свойств Z-кривой, для элементов необходимо хранить только глубину элемента (уровень в октодреве) и его порядок (расположение на Z-кривой). В элементы используемого массива для хранения ячеек сетки заносятся значения глубины элемента, а индекс элемента определяет его расположение на Z-кривой.
Для хранения глубины элемента достаточно использовать 1 байт(глубина дерева 256). Для многих задач может оказаться достаточной глубина дерева 16(размер минимальной ячейки будет в 2^15 = 32768 раз меньше исходной области). Тогда для хранения ячейки достаточно использовать 4 бита.
Для определения вещественных координат элемента необходимо выполнить следующие шаги:
1. вычисление кода Мортона для элемента
2. декодирование
3. перевод полученного индекса в вещественное значение каждой из координат
Рассмотрим алгоритм на примере кодирования каждой из координат 20-тью битами, то есть результирующий код всех трех координат будет занимать 60 бит.
Зная код и глубину предыдущего элемента, можно вычислить код текущего элемента. Код первого элемента всегда равен 0. Определим смещение для каждого уровня глубины:
for ( unsigned char i = 0; i < 21; ++i ) {
levelOffset[20 - i] = offset;
offset *= 8;
}
Теперь будем определять индекс элемента через глубину и индекс предыдущего элемента:
unsigned long getElementIndex( const unsigned long prevIndex, const unsigned char prevLevel ) {
return prevIndex + levelOffset[prevLevel];
}
Функция декодирования:
void decodeIndexXYZ( const unsigned long index, unsigned long iXYZ[3]) {
iXYZ[0] = decodeIndex( index );
iXYZ[1] = decodeIndex( index >> 1 );
iXYZ[2] = decodeIndex( index >> 2 );
}
unsigned long decodeIndex( const unsigned long index ) {
unsigned long ind = index & 0x0249249249249249;
ind = ( ind | ( ind >> 2 ) ) & 0x00C9219243248649;
ind = ( ind | ( ind >> 2 ) ) & 0x00386070C0E181C3;
ind = ( ind | ( ind >> 4 ) ) & 0x0003E007C00F801F;
ind = ( ind | ( ind >> 10 ) ) & 0x000000FFC00003FF;
ind = ( ind | ( ind >> 20 ) ) & 0x00000000000FFFFF;
return ind;
}
iXYZ[0], iXYZ[1], iXYZ[2] — определяют порядок кодирования(в данном случае сначала координата x, затем y, затем z).
Константы и количество шагов в функции decodeIndex определяются количеством бит и размерностью пространства(в данном примере константы приведены для трехмерного пространства и 20-ти бит на координату).
Существуют различные способы кодирования, примеры на
Bit Twiddling Hacks
How to compute a 3D Morton number (interleave the bits of 3 ints)
Для получения вещественных значений вершины ячейки с минимальными координатами, полученные индексы умножаются на величину шага. Величина шага — это размер минимальной допустимой ячейки сетки.
Размер ячейки можно определить по ее глубине. Остальные значения определяются прибавлением размера элементы к соответствующим минимальным координатам.
Деление элемента осуществляется путем увеличения его глубины и вставке после него 7 элементов этой же глубины.
Объединение — уменьшение глубины и удалении последующих 7 элементов.
Октодерево является активно изучаемой структурой данных и алгоритмы работы с ним(поиск соседей, интервалов, визуализация и тд) становятся темой докторских диссертаций и научных исследований.