kDTree.hxx

   1 #ifndef KDTREE_HXX
   2 #define KDTREE_HXX
   3
   4 #include <vector>
   5
   6 #include "Box.hxx"
   7 #include "Primitive.hxx"
   8
   9 //! Interface for tree nodes
  10 class kDTreeNode
  11 {
  12 public:
  13   virtual ~kDTreeNode(){;};
  14   // interface for the traversal. [t0,t1] code the active ray interval.
  15   virtual bool Traverse(Ray &ray, float& t0, float& t1) = 0;
  16 };
  17
  18 //! An inner node of the kD-tree
  19 class kDTreeInnerNode : public kDTreeNode
  20 {
  21 public:
  22   kDTreeInnerNode(float split, int axis);
  23   virtual ~kDTreeInnerNode();
  24
  25   virtual bool Traverse(Ray& ray, float& t0, float& t1);
  26
  27   void setChildren(kDTreeNode* left, kDTreeNode* right);
  28 private:
  29   kDTreeInnerNode();
  30   kDTreeInnerNode(const kDTreeInnerNode& );
  31   kDTreeInnerNode& operator=(const kDTreeInnerNode& );
  32
  33   // pointer to the children
  34   kDTreeNode* m_children[2];
  35   // encodes the position of the splitting plane on the splitting axis
  36   float m_split;
  37   // encodes the splitting axis
  38   int m_axis;
  39 };
  40
  41 //! A leaf node of the kD-tree
  42 class kDTreeLeafNode : public kDTreeNode
  43 {
  44 public:
  45   kDTreeLeafNode(const std::vector<Primitive*>& prim);
  46   virtual ~kDTreeLeafNode();
  47
  48   virtual bool Traverse(Ray& ray, float& t0, float& t1);
  49
  50 private:
  51   kDTreeLeafNode();
  52   kDTreeLeafNode(const kDTreeLeafNode& );
  53   kDTreeLeafNode& operator=(const kDTreeLeafNode& );
  54
  55   std::vector<Primitive *> m_primitives;
  56 };
  57
  58 //! The actual kDTree interface
  59 class kDTree
  60 {
  61 public:
  62   kDTree(const Box& bounds, const std::vector<Primitive*>& prim);
  63   ~kDTree();
  64
  65   kDTreeNode* BuildTree(const Box& bounds,
  66                         const std::vector<Primitive *>& prim,
  67                         int depth);
  68
  69   bool Intersect(Ray &ray);
  70
  71 private:
  72   kDTree();
  73   kDTree(const kDTree& );
  74   kDTree& operator=(const kDTree& );
  75
  76   // root node
  77   kDTreeNode* m_root;
  78   // bounding box of the entire tree
  79   Box m_bounds;
  80   // maximal recursion depth
  81   int m_maxDepth;
  82   // minimal number of triangles per node
  83   int m_minTri;
  84 };
  85 #endif