57 |
57 |
58 void setAxis(int aAxis) { flags &= ~3; flags |= aAxis; }; |
58 void setAxis(int aAxis) { flags &= ~3; flags |= aAxis; }; |
59 short getAxis() { return flags & 3; }; |
59 short getAxis() { return flags & 3; }; |
60 |
60 |
61 void setSplit(Float aSplit) { split = aSplit; }; |
61 void setSplit(Float aSplit) { split = aSplit; }; |
62 Float getSplit() { return split; }; |
62 Float& getSplit() { return split; }; |
63 |
63 |
64 void setChildren(KdNode *node) { children = node; assert((flags & 3) == 0); }; |
64 void setChildren(KdNode *node) { children = node; assert((flags & 3) == 0); }; |
65 KdNode *getLeftChild() { return (KdNode*)((off_t)children & ~3); }; |
65 KdNode* getLeftChild() { return (KdNode*)((off_t)children & ~3); }; |
66 KdNode *getRightChild() { return (KdNode*)((off_t)children & ~3) + 1; }; |
66 KdNode* getRightChild() { return (KdNode*)((off_t)children & ~3) + 1; }; |
67 |
67 |
68 ShapeList *getShapes() { return (ShapeList*)((off_t)shapes & ~3); }; |
68 ShapeList* getShapes() { return (ShapeList*)((off_t)shapes & ~3); }; |
69 void addShape(Shape* aShape) { getShapes()->push_back(aShape); }; |
69 void addShape(Shape* aShape) { getShapes()->push_back(aShape); }; |
70 |
|
71 void subdivide(BBox bbox, int maxdepth); |
|
72 }; |
70 }; |
73 |
71 |
74 /** |
72 /** |
75 * kd-tree |
73 * kd-tree |
76 */ |
74 */ |
77 class KdTree: public Container |
75 class KdTree: public Container |
78 { |
76 { |
79 KdNode *root; |
77 KdNode *root; |
80 bool built; |
78 bool built; |
81 int max_depth; |
79 int max_depth; |
|
80 |
|
81 void recursive_build(KdNode *node, BBox bbox, int maxdepth); |
82 public: |
82 public: |
83 KdTree() : Container(), root(NULL), built(false), max_depth(32) {}; |
83 KdTree() : Container(), root(NULL), built(false), max_depth(32) {}; |
84 ~KdTree() { if (root) delete root; }; |
84 ~KdTree() { if (root) delete root; }; |
85 void addShape(Shape* aShape) { Container::addShape(aShape); built = false; }; |
85 void addShape(Shape* aShape) { Container::addShape(aShape); built = false; }; |
86 Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |
86 Shape *nearest_intersection(const Shape *origin_shape, const Ray &ray, |