1

我正在研究一个八叉树实现，其中树节点使用它们的维度长度（作为 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 的类型？但这与我的问题并不真正相关。）

我想创建一个函数，它沿着我的八叉树占据的 3D 空间中的一条射线前进，所以表面上我可以只保留一个指向根节点（具有已知类型）的指针，并在每次从根节点遍历八叉树步。但是，我更喜欢“本地”选项，我可以在其中跟踪当前节点，以便尽可能从树的较低位置开始，从而避免不必要地遍历八叉树的上层节点。

但我不知道该类型指针可能是什么（或任何其他实现方式），因此我不会体验切片。

我不受模板的束缚，因为维度可以简单地实现为long const. 但是我不知道如何使叶子具有与 inode 不同的子类型。

谢谢你的帮助！

更新

我想这样做而不是类似的原因是因为count每个节点中的变量：如果计数为 0，我想跳过整个立方体，而不是浪费时间通过叶子我知道是空的。（这是针对光线追踪体素引擎的。）

4

1 回答 1

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);
};

这样做的好处是树可以是你想要的任何深度，包括一些子树可以比其他的更深。它的缺点是必须在运行时计算 dim ，但即使这样也有一线希望，如果你的树变得非常大，你可以将其设为双倍。

于 2013-01-25T22:52:38.520 回答