Поиск соседей соседей

Question

У меня есть октет, который хранит жидкость на вокселе. Когда я имитирую жидкость, мне нужно получить доступ к листьям вокруг текущего узла, как я могу реализовать такой поиск?

Можно предположить, Узел хранит указатель на родительском узел. (Требуется, возможно, другие данные?)

Answer 1

Предполагая, что каждый октодерево узел также имеет свои 3D индекс [1] в октодереве (и его глубина).

1. Создайте 3D-индексы для соседних узлов узла запроса (просто увеличивайте/уменьшайте 3D-индекс узла запроса в каждом измерении).
2. Для каждого потенциального соседа, проведите по октету от корня, используя сгенерированные 3D-индексы, чтобы выбрать, какой путь следует принимать в каждом узле с дочерними элементами.

В случае, если текущий узел имеет сосед на большой глубине только (октодерева не являются полным/совершенным), обход сделан в 2. остановятся на максимальной достижимой глубине в октодереве, которое меньше или равно, чем глубина узла запроса.

Если узлы содержат указатель на своих родителей, 2. может быть улучшено путем поиска самого низкого общего предка текущего узла и каждого из его соседей (это делается путем нахождения самого длинного общего двоичного префикса в их трехмерных индексах) и начать обход, чтобы достичь соседа только с этого узла-предка.

[1]: 3D-индекс - это просто координаты x/y/z узла в октете. Например, восемь детей корня имеют 3D-индексы с 1 двоичной цифрой (эти узлы расположены на глубине 1 в октете): 0/0/0, 1/0/0, 0/1/0, 1/1/0, ... Шестьдесят четыре внушающих ребенка корня имеют трехмерные индексы с двумя двоичными цифрами (эти узлы расположены на глубине 2 в октете): 00/00/00, 01/00/00, 10/00/00, 11/00/00, 00/01/00, 01/00/00 ...