82 /** |
82 /** |
83 * kd-tree |
83 * kd-tree |
84 */ |
84 */ |
85 class KdTree: public Container |
85 class KdTree: public Container |
86 { |
86 { |
|
87 static const int MAX_DEPTH; |
87 MemoryPool<KdNode> mempool; |
88 MemoryPool<KdNode> mempool; |
88 KdNode *root; |
89 KdNode *root; |
89 const int max_depth; |
|
90 bool built; |
90 bool built; |
91 |
91 |
92 void recursive_build(KdNode *node, const BBox &bbox, int maxdepth); |
92 void recursive_build(KdNode *node, const BBox &bbox, int maxdepth); |
93 void recursive_load(istream &st, KdNode *node); |
93 void recursive_load(istream &st, KdNode *node); |
94 public: |
94 public: |
95 /** default constructor, maximum depth is set to 32 */ |
95 KdTree(): Container(), mempool(64), root(NULL), built(false) {}; |
96 KdTree(): Container(), mempool(64), root(NULL), max_depth(32), built(false) {}; |
|
97 |
|
98 /** constructor which allows to se maximum tree depth (cannot be changed later) */ |
|
99 KdTree(int maxdepth): Container(), mempool(64), root(NULL), max_depth(maxdepth), built(false) {}; |
|
100 ~KdTree() { if (root) delete root; }; |
96 ~KdTree() { if (root) delete root; }; |
101 |
97 |
102 /** add shape pointer to the container */ |
98 /** add shape pointer to the container */ |
103 void addShape(const Shape* aShape) { Container::addShape(aShape); built = false; }; |
99 void addShape(const Shape* aShape) { Container::addShape(aShape); built = false; }; |
104 const Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |
100 const Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |