1 #include "kdtree.cc" |
1 #include <algorithm> |
2 |
2 |
3 void KdTree::KdTree(ShapeList &shapelist): |
3 #include "kdtree.h" |
|
4 |
|
5 void Container::addShape(Shape* aShape) |
|
6 { |
|
7 shapes.push_back(aShape); |
|
8 if (shapes.size() == 0) { |
|
9 /* initialize bounding box */ |
|
10 bbox = aShape->get_bbox(); |
|
11 } else { |
|
12 /* adjust bounding box */ |
|
13 BBox shapebb = aShape->get_bbox(); |
|
14 if (shapebb.L.x < bbox.L.x) bbox.L.x = shapebb.L.x; |
|
15 if (shapebb.L.y < bbox.L.y) bbox.L.y = shapebb.L.y; |
|
16 if (shapebb.L.z < bbox.L.z) bbox.L.z = shapebb.L.z; |
|
17 if (shapebb.R.x > bbox.R.x) bbox.R.x = shapebb.R.x; |
|
18 if (shapebb.R.y > bbox.R.y) bbox.R.y = shapebb.R.y; |
|
19 if (shapebb.R.z > bbox.R.z) bbox.R.z = shapebb.R.z; |
|
20 } |
|
21 }; |
|
22 |
|
23 void KdNode::subdivide(BBox bbox, int depth, int count) |
|
24 { |
|
25 int axis; |
|
26 float pos; |
|
27 |
|
28 //if (stopcriterionmet()) return |
|
29 |
|
30 // choose split axis |
|
31 axis = 0; |
|
32 if (bbox.R.y - bbox.L.y > bbox.R.x - bbox.L.x) |
|
33 axis = 1; |
|
34 if (bbox.R.z - bbox.L.z > bbox.R.y - bbox.L.y) |
|
35 axis = 2; |
|
36 |
|
37 // *** find optimal split position |
|
38 SortableShapeList sslist(shapes, axis); |
|
39 sort(sslist.begin(), sslist.end()); |
|
40 |
|
41 SplitList splitlist = SplitList(); |
|
42 |
|
43 SortableShapeList::iterator sh; |
|
44 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
|
45 { |
|
46 splitlist.push_back(SplitPos(sh->bbox.L.cell[axis])); |
|
47 splitlist.push_back(SplitPos(sh->bbox.R.cell[axis])); |
|
48 } |
|
49 sort(splitlist.begin(), splitlist.end()); |
|
50 |
|
51 // find all posible splits |
|
52 SplitList::iterator split; |
|
53 int rest; |
|
54 for (split = splitlist.begin(); split != splitlist.end(); split++) |
|
55 { |
|
56 for (sh = sslist.begin(), rest = sslist.size(); sh != sslist.end(); sh++, rest--) |
|
57 { |
|
58 if (sh->hasMark()) |
|
59 continue; |
|
60 // if shape is on left side of split plane |
|
61 if (sh->bbox.R.cell[axis] <= split->pos) |
|
62 { |
|
63 sh->setMark(); |
|
64 split->lnum++; |
|
65 } |
|
66 // if shape is completely contained in split plane |
|
67 if (sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis] == split->pos) |
|
68 { |
|
69 if (split->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - split->pos) |
|
70 { |
|
71 // left subcell is smaller -> if not empty, put shape here |
|
72 if (split->lnum) |
|
73 split->lnum++; |
|
74 else |
|
75 split->rnum++; |
|
76 } else { |
|
77 // right subcell is smaller |
|
78 if (split->rnum) |
|
79 split->rnum++; |
|
80 else |
|
81 split->lnum++; |
|
82 } |
|
83 } |
|
84 // if shape is on right side of split plane |
|
85 if (sh->bbox.L.cell[axis] >= split->pos) |
|
86 { |
|
87 split->rnum += rest; |
|
88 break; |
|
89 } |
|
90 // if shape occupies both sides of split plane |
|
91 if (sh->bbox.L.cell[axis] < split->pos && sh->bbox.R.cell[axis] > split->pos) |
|
92 { |
|
93 split->lnum++; |
|
94 split->rnum++; |
|
95 } |
|
96 } |
|
97 } |
|
98 |
|
99 // choose best split pos |
|
100 // ... // |
|
101 |
|
102 KdNode *children = new KdNode[2]; |
|
103 |
|
104 ShapeList::iterator shape; |
|
105 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
|
106 { |
|
107 if (((Triangle*)*shape)->A.cell[axis-1] < pos |
|
108 || ((Triangle*)*shape)->B.cell[axis-1] < pos |
|
109 || ((Triangle*)*shape)->C.cell[axis-1] < pos) |
|
110 children[0].addShape(*shape); |
|
111 if (((Triangle*)*shape)->A.cell[axis-1] >= pos |
|
112 || ((Triangle*)*shape)->B.cell[axis-1] >= pos |
|
113 || ((Triangle*)*shape)->C.cell[axis-1] >= pos) |
|
114 children[1].addShape(*shape); |
|
115 } |
|
116 |
|
117 bbox.R[axis-1] = pos; |
|
118 children[0].subdivide(bbox, depth+1, children[0].shapes.size()); |
|
119 |
|
120 bbox.L[axis-1] = pos; |
|
121 children[1].subdivide(bbox, depth+1, children[1].shapes.size()); |
|
122 } |
|
123 |
|
124 void KdTree::build() |
4 { |
125 { |
5 root = new KdNode(); |
126 root = new KdNode(); |
6 shapes = new vector<Shape*>(); |
127 root->shapes = shapes; |
7 ShapeList::iterator shape; |
128 root->subdivide(bbox, 0, shapes.size()); |
8 for (shape = shapelist.begin(); shape != shapes.end(); shape++) |
|
9 addShape(*shape); |
|
10 |
|
11 rebuild(); |
|
12 } |
129 } |
13 |
|
14 void KdTree::Subdivide(KdNode* node, AABB& bbox, int depth, int count) |
|
15 { |
|
16 |
|
17 /*if (stopcriterionmet()) return |
|
18 splitpos = findoptimalsplitposition() |
|
19 leftnode = new Node() |
|
20 rightnode = new Node() |
|
21 for (all primitives in node) |
|
22 { |
|
23 if (node->intersectleftnode()) leftnode->addprimitive( primitive ) |
|
24 if (node->intersectrightnode()) rightnode->addprimitive( primitive ) |
|
25 } |
|
26 buildkdtree( leftnode ) |
|
27 buildkdtree( rightnode )*/ |
|
28 } |
|
29 |
|
30 void KdTree::rebuild() |
|
31 { |
|
32 int count = shapes->size(); |
|
33 AABB bbox = shapes->extends(); |
|
34 |
|
35 Subdivide(root, bbox, 0, count); |
|
36 } |
|