Я работаю над реализацией октодерева, где узлы дерева имеют размерную длину (как степень 2):
template<long N>
struct node_t {
enum { DIM = 1 << N };
node_t<N+1> * parent;
node_t<N-1> * children[8];
long count;
}
И специализируется на N = 0 (уходит), чтобы указывать на данные.
struct node_t<0> {
enum { DIM = 1 };
node_t<1> * parent;
data_t data;
long count;
}
(В сторону: Я полагаю, мне, вероятно, также нужна специализация для N_MAX, которая исключает родительский указатель, иначе C ++ будет генерировать типы возрастающего N ad finitum? Но это не совсем относится к моему вопросу.)
Я хотел бы создать функцию, которая шагает вдоль луча в трехмерном пространстве, которое занимает мое октри, так что якобы я мог бы просто держать указатель на корневой узел (который имеет известный тип) и проходить октре от корня на каждом шаг. Однако я бы предпочел более «локальный» вариант, в котором я могу отслеживать текущий узел, чтобы я мог по возможности начинать с нижнего уровня дерева и, таким образом, избегать ненужного обхода верхних узлов октодерева.
Но я не знаю, каким может быть этот указатель типа (или каким-либо другим способом реализации этого), чтобы я не испытывал нарезку.
Я не привязан к шаблонам, так как измерение может быть просто реализовано как long const
, Но тогда я не знаю, как сделать так, чтобы листья имели дочерний тип, отличный от инодов.
Спасибо за вашу помощь!
Причина, по которой я хотел бы сделать это таким образом, а не что-то похожее на этот из-за count
переменная в каждом узле: если счетчик равен 0, я бы хотел прыгать через весь куб, а не тратить время на прохождение листьев, которые, как я знаю, пусты. (Это для воксельного движка трассировки лучей.)
Как бы я ни любил шаблоны, ваш код может быть проще с:
class node {
node* parent; // NULL for root node
long dim;
long count;
virtual rayTrace(Ray) = 0;
};
class leafNode : node {
data_t data;
virtual rayTrace(Ray);
};
class nonLeafNode : node {
vector<node*> children;
virtual rayTrace(Ray);
};
Это имеет то преимущество, что дерево может быть любой глубины, которую вы хотите, в том числе некоторые поддеревья могут быть глубже, чем другие. Недостатком является то, что дим должен вычисляться во время выполнения, но даже у него есть серебряная подкладка, которую вы можете сделать двойным, если ваше дерево станет действительно большим.
Других решений пока нет …