1

I'm working on an octree implementation where the tree nodes are templated with their dimensional length (as a power of 2):

template<long N>
struct node_t {
    enum { DIM = 1 << N };
    node_t<N+1> * parent;
    node_t<N-1> * children[8];
    long count;
}

And specialized for N = 0 (leaves) to point to data.

struct node_t<0> {
    enum { DIM = 1 };
    node_t<1> * parent;
    data_t data;
    long count;
}

(Aside: I suppose I probably also need a specialization for N_MAX that excludes a parent pointer, or else C++ will generate types of increasing N ad finitum? But that's not really relevant to my question.)

I'd like to create a function that steps along a ray in the 3D space that my octree occupies, so ostensibly I could just keep a pointer to the root node (which has a known type) and traverse the octree from the root at every step. However, I would prefer a more 'local' option, in which I can keep track of the current node so that I can start lower in the tree when possible and thus avoid unnecessarily traversing the upper nodes of the octree.

But I don't know what that type pointer could be (or any other way of implementing this) so that I don't experience slicing.

I'm not tied down to templates, as the dimension can simply be implemented as a long const. But then I don't know how to make it so that the leaves have a different child type than inodes.

Thanks for your help!

Update

The reason I'd like to do it this way rather than something similar to this is because of the count variable in each node: if the count is 0, I'd like to jump through the whole cube, rather wasting time going through leaves that I know to be empty. (This is for a raytracing voxel engine.)

Community
  • 1
  • 1
ben_reilly
  • 11
  • 3

1 Answers1

0

As much as I love templates, your code might actually be simpler with:

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

This has the advantage that the tree can be whatever depth you want, including some subtrees can be deeper than others. It has the downside that dim must be computed at runtime, but even that has the silver lining that you can make it a double if your tree gets really big.

dspeyer
  • 2,904
  • 1
  • 18
  • 24
  • I had considered doing something like this, but I don't want to mix raytracing with the world's representation: ideally, the two would be separate. – ben_reilly Jan 26 '13 at 01:34
  • In that case you can have virtual bool isLeaf(); and split and cast your raytracing on it. – dspeyer Jan 26 '13 at 05:45