У меня есть октодерево, в котором хранится жидкость на основе вокселей. Когда я моделирую жидкость, мне нужно получить доступ к листьям вокруг текущего узла, как я могу реализовать такой поиск?
Вы можете предположить, что узел хранит указатель на свой родительский узел. (Возможно, нужны другие данные?)
Предположим, что каждый узел октодерева также содержит свой трехмерный индекс[1] в октодереве (и его глубину).
В случае, если текущий узел имеет соседей только на более высокой глубине (октодерево не является полным/идеальным), обход, выполненный в 2., остановится на максимально достижимой глубине в октодереве, которая меньше или равна глубине узла запроса.
Если узлы содержат указатель на своих родителей, 2. можно улучшить, найдя сначала наименьшего общего предка текущего узла и каждого из его соседей (это делается путем нахождения самого длинного общего двоичного префикса в их трехмерных индексах) и запуская обход для достижения соседа только от этого узла-предка.
[1]: Трехмерный индекс — это просто координаты x/y/z узла в октодереве. Например, восемь дочерних элементов корня имеют трехмерные индексы с 1 двоичной цифрой (эти узлы расположены на глубине 1 в октодереве): 0/0/0, 1/0/0, 0/1/0, 1/1. /0, ... Шестьдесят четыре внука корня имеют трехмерные индексы с 2 двоичными цифрами (эти узлы расположены на глубине 2 в октодереве): 00/00/00, 01/00/00, 10/ 00.00, 00.11.00, 01.00.00, 00.01.00...
