дерево — Как построить октодерево в переполнении стека
Я реализую Octree в C ++, который позже должен содержать сетку для рендеринга. Но в данный момент я борюсь со строительством Октри. Точнее говоря, это функция addNode (), которая вызывает проблемы. Я подумал о рекурсивной реализации, похожей на двоичное дерево:
Реализация двоичного дерева C ++
Однако в октрее у каждого узла есть 8 сыновей, а не только 2. Кроме того, поэтому я не могу использовать простой переключатель (влево / вправо), как в двоичном дереве, чтобы решить, куда добавить узел. Мне нужно проверить, является ли один из 8 сыновей пустым (указатель равен NULL), и если указатель не равен NULL, мне нужно вызвать функцию add с одним из сыновей в качестве аргумента. Тем не менее, это приведет к октре, где всегда первый сын будет содержать все последующие субдеревья. Как эта функция добавления обычно реализуется и этой проблемы избегают?
Решение
Вам необходимо проверить размерность объекта по x, y, z, а также октябрь может сохранить ограниченное количество объектов.
Другие решения
У вас есть правильная идея, вам просто нужно расширить концепцию до трех измерений. Вместо того, чтобы определять, нужно ли вставлять дочерний элемент слева или справа (x-размерность), вы также должны выбрать выше или ниже (y-размерность) и впереди или сзади (z-размерность). Вы могли бы использовать трехмерный массив как это:
Node* children[2][2][2];
И ваши внутренние узлы (те с ветвями) должны иметь трехмерный центр и размер. При принятии решения о том, где значение должно быть вставлено в октодерево, вам нужно сравнить позицию, в которую вставляется или ищется, с центром текущего октанта:
children[position.x > center.x][position.y > center.y][position.z > center.z]
Это дает указатель, куда вы вставите. Если в этой позиции есть узел, вам нужно выполнить рекурсию, если это другая ветвь, создать новый узел, если он нулевой, или создать ветвь и заново вставить, если это листовой узел.
Вы можете найти трехмерный массив громоздким при переборе по дочерним элементам. Вместо этого вы можете использовать одномерный массив и индексировать, как если бы он имел три измерения:
Node* children[8];
int index = (position.x > center.x) << 2 |
(position.y > center.y) << 1 |
(position.z > center.z);
Это генерирует индекс [0-7] путем установки битов в соответствии с положением относительно центра октанта.