3 |
3 |
4 #include <vector> |
4 #include <vector> |
5 |
5 |
6 #include "scene.h" |
6 #include "scene.h" |
7 |
7 |
8 class SpaceDivider |
8 using namespace std; |
|
9 |
|
10 class ShapeList: public vector<Shape*> |
9 { |
11 { |
10 ShapeList *shapes; |
|
11 public: |
|
12 SpaceDivider(ShapeList &shapelist): shapes(shapelist) {}; |
|
13 }; |
12 }; |
14 |
13 |
15 class KdNode: |
14 class SortableShape |
|
15 { |
|
16 public: |
|
17 Shape *shape; |
|
18 BBox bbox; |
|
19 short axis; |
|
20 short mark; |
|
21 |
|
22 SortableShape(Shape *aShape, short &aAxis): shape(aShape), axis(aAxis), mark(0) |
|
23 { bbox = shape->get_bbox(); }; |
|
24 friend bool operator<(const SortableShape& a, const SortableShape& b) |
|
25 { return a.bbox.L.cell[a.axis] < b.bbox.L.cell[b.axis]; }; |
|
26 void setAxis(short aAxis) { axis = aAxis; }; |
|
27 void setMark() { mark = 1; }; |
|
28 short hasMark() { return mark; }; |
|
29 }; |
|
30 |
|
31 class SortableShapeList: public vector<SortableShape> |
|
32 { |
|
33 public: |
|
34 SortableShapeList(ShapeList &shapes, short axis) |
|
35 { |
|
36 ShapeList::iterator shape; |
|
37 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
|
38 push_back(SortableShape(*shape, axis)); |
|
39 }; |
|
40 }; |
|
41 |
|
42 class SplitPos |
|
43 { |
|
44 public: |
|
45 float pos; |
|
46 int lnum, rnum; |
|
47 SplitPos(float &aPos): pos(aPos) {}; |
|
48 friend bool operator<(const SplitPos& a, const SplitPos& b) |
|
49 { return a.pos < b.pos; }; |
|
50 }; |
|
51 |
|
52 class SplitList: public vector<SplitPos> |
|
53 { |
|
54 }; |
|
55 |
|
56 class Container |
|
57 { |
|
58 protected: |
|
59 ShapeList shapes; |
|
60 BBox bbox; |
|
61 public: |
|
62 Container(): shapes(), bbox() {}; |
|
63 void addShape(Shape* aShape); |
|
64 //void addShapeNoExtend(Shape* aShape) { shapes.push_back(aShape); }; |
|
65 }; |
|
66 |
|
67 class KdNode |
16 { |
68 { |
17 float split; |
69 float split; |
18 bool leaf; /* is this node a leaf? */ |
70 bool leaf; /* is this node a leaf? */ |
19 char axis; /* 0,1,2 => x,y,z */ |
71 char axis; /* 1,2,3 => x,y,z */ |
20 KdNode *leftchild, *rightchild; |
72 KdNode *leftchild; |
21 public: |
73 public: |
22 vector<Shape*> shapes; |
74 ShapeList shapes; |
23 |
75 |
24 KdNode() : leaf(true), axis(0), shapes() {}; |
76 KdNode() : leaf(true), axis(0), shapes() {}; |
25 |
77 |
26 setAxis(char aAxis) { axis = aAxis; }; |
78 void setAxis(char aAxis) { axis = aAxis; }; |
27 char getAxis() { return axis; }; |
79 char getAxis() { return axis; }; |
28 |
80 |
29 setSplit(float aSplit) { split = aSplit; }; |
81 void setSplit(float aSplit) { split = aSplit; }; |
30 float getSplit() { return split; }; |
82 float getSplit() { return split; }; |
31 |
83 |
32 setLeaf(bool aLeaf) { leaf = aLeaf; }; |
84 void setLeaf(bool aLeaf) { leaf = aLeaf; }; |
33 bool isLeaf() { return leaf; }; |
85 bool isLeaf() { return leaf; }; |
34 |
86 |
35 setLeftChild(KdNode *aLeft) { leftchild = aLeft; }; |
87 void setLeftChild(KdNode *aLeft) { leftchild = aLeft; }; |
36 KdNode *getLeftChild() { return leftchild; }; |
88 KdNode *getLeftChild() { return leftchild; }; |
37 setRightChild(KdNode *aRight) { rightchild = aRight; }; |
89 KdNode *getRightChild() { return leftchild+1; }; |
38 KdNode *getRightChild() { return rightchild; }; |
|
39 |
90 |
40 addShape(Shape* aShape) { shapes.push_back(aShape); }; |
91 void addShape(Shape* aShape) { shapes.push_back(aShape); }; |
|
92 |
|
93 void subdivide(BBox bbox, int depth, int count); |
41 }; |
94 }; |
42 |
95 |
43 class KdTree: public SpaceDivider |
96 class KdTree: public Container |
44 { |
97 { |
45 KdNote *root; |
98 KdNode *root; |
46 public: |
99 public: |
47 KdTree(ShapeList &shapelist); |
100 KdTree() {}; |
48 rebuild(); |
101 void build(); |
49 }; |
102 }; |
50 |
103 |
51 #endif |
104 #endif |