53 }; |
53 }; |
54 public: |
54 public: |
55 KdNode() { shapes = new ShapeList(); assert((flags & 3) == 0); setLeaf(); }; |
55 KdNode() { shapes = new ShapeList(); assert((flags & 3) == 0); setLeaf(); }; |
56 ~KdNode(); |
56 ~KdNode(); |
57 |
57 |
|
58 /** mark this node as leaf */ |
58 void setLeaf() { flags |= 3; }; |
59 void setLeaf() { flags |= 3; }; |
59 bool isLeaf() const { return (flags & 3) == 3; }; |
60 bool isLeaf() const { return (flags & 3) == 3; }; |
60 |
61 |
|
62 /** set split axis (this removes leaf flag) */ |
61 void setAxis(int aAxis) { flags &= ~3; flags |= aAxis; }; |
63 void setAxis(int aAxis) { flags &= ~3; flags |= aAxis; }; |
62 int getAxis() const { return flags & 3; }; |
64 int getAxis() const { return flags & 3; }; |
63 |
65 |
|
66 /** set split position (leaf) */ |
64 void setSplit(Float aSplit) { split = aSplit; }; |
67 void setSplit(Float aSplit) { split = aSplit; }; |
65 const Float& getSplit() const { return split; }; |
68 const Float& getSplit() const { return split; }; |
66 |
69 |
|
70 /** set children (non-leaf) */ |
67 void setChildren(KdNode *node) { children = node; assert((flags & 3) == 0); }; |
71 void setChildren(KdNode *node) { children = node; assert((flags & 3) == 0); }; |
68 KdNode* getLeftChild() const { return (KdNode*)((size_t)children & ~3); }; |
72 KdNode* getLeftChild() const { return (KdNode*)((size_t)children & ~3); }; |
69 KdNode* getRightChild() const { return (KdNode*)(((size_t)children & ~3) + 16); }; |
73 KdNode* getRightChild() const { return (KdNode*)(((size_t)children & ~3) + 16); }; |
70 |
74 |
|
75 /** get shape list of the leaf node*/ |
71 ShapeList* getShapes() const { return (ShapeList*)((size_t)shapes & ~3); }; |
76 ShapeList* getShapes() const { return (ShapeList*)((size_t)shapes & ~3); }; |
|
77 |
|
78 /** add shape to shape list */ |
72 void addShape(const Shape* aShape) { getShapes()->push_back(aShape); }; |
79 void addShape(const Shape* aShape) { getShapes()->push_back(aShape); }; |
73 }; |
80 }; |
74 |
81 |
75 /** |
82 /** |
76 * kd-tree |
83 * kd-tree |
83 bool built; |
90 bool built; |
84 |
91 |
85 void recursive_build(KdNode *node, const BBox &bbox, int maxdepth); |
92 void recursive_build(KdNode *node, const BBox &bbox, int maxdepth); |
86 void recursive_load(istream &st, KdNode *node); |
93 void recursive_load(istream &st, KdNode *node); |
87 public: |
94 public: |
|
95 /** default constructor, maximum depth is set to 32 */ |
88 KdTree(): Container(), mempool(64), root(NULL), max_depth(32), 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) */ |
89 KdTree(int maxdepth): Container(), mempool(64), root(NULL), max_depth(maxdepth), built(false) {}; |
99 KdTree(int maxdepth): Container(), mempool(64), root(NULL), max_depth(maxdepth), built(false) {}; |
90 ~KdTree() { if (root) delete root; }; |
100 ~KdTree() { if (root) delete root; }; |
|
101 |
|
102 /** add shape pointer to the container */ |
91 void addShape(const Shape* aShape) { Container::addShape(aShape); built = false; }; |
103 void addShape(const Shape* aShape) { Container::addShape(aShape); built = false; }; |
92 const Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |
104 const Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |
93 Float &nearest_distance); |
105 Float &nearest_distance); |
94 #ifndef NO_SIMD |
106 #ifndef NO_SIMD |
95 void packet_intersection(const Shape* const* origin_shapes, const RayPacket &rays, |
107 void packet_intersection(const Shape* const* origin_shapes, const RayPacket &rays, |
96 Float *nearest_distances, const Shape **nearest_shapes); |
108 Float *nearest_distances, const Shape **nearest_shapes); |
97 #endif |
109 #endif |
98 void optimize() { build(); }; |
110 void optimize() { build(); }; |
|
111 |
|
112 /** build the tree (alias for 'optimize') */ |
99 void build(); |
113 void build(); |
100 bool isBuilt() const { return built; }; |
114 bool isBuilt() const { return built; }; |
101 KdNode *getRootNode() const { return root; }; |
115 KdNode *getRootNode() const { return root; }; |
102 |
116 |
103 ostream & dump(ostream &st) const; |
117 ostream & dump(ostream &st) const; |