До сих пор я индексировал октри с помощью рекурсивной функции
i = p * 8 + c + 1
Где p - родительский индекс, а c - локальный индекс узла (0-7)
Это приводит к тому, что каждый узел октодерева имеет уникальный индекс, и позволяет мне избежать необходимости хранить дочерние индексы в родительском элементе - это экономит память, позволяя мне получить доступ к дочерним элементам узла просто путем вычисления ключа, который имеет узел, и доступа к нему таким образом.
Я храню свое октри на карте.
У меня есть проблема, которую, я думаю, можно решить, найдя другой способ индексации дерева. Я борюсь с этим самостоятельно, поэтому я думал, что вы, ребята, могли бы помочь!
https://duskydepths.com/images/quadtree.png
Это 2D аналогия проблемы, с которой я работаю. В этом конкретном случае каждый узел ветви имеет 4 дочерних элемента. Это широко используемый способ реализации сеток с адаптивным разрешением.
Я ищу способ использовать сгенерированные индексы для вычисления и поиска узлов в дереве, которые соответствуют позициям равномерной сетки на определенной глубине. Обычно я делаю это с помощью рекурсии, проверяя, больше или меньше целевая позиция в сетке, чем значение «ветви» дерева на каждой оси, но поскольку моя конечная цель - реализовать это на GPU, я не чувствую, что это лучшее решение. Я слышал, как графические процессоры сосут в ответвлении. Честно говоря, я просто хочу иметь возможность перейти к горлу - максимально разделить дерево, а затем получить доступ к узлам максимальной глубины, как я бы использовал пиксели, выполнив простой расчет для преобразования целочисленного вектора, представляющего пиксель pos, в индекс октерева.
Извините, если это очевидная и решенная проблема! Я никогда официально не изучал CS, поэтому я не знаю, к какой области это относится - если вы не хотите тратить время на ответ, достаточно подтолкнуть его в правильном направлении.