20 } |
20 } |
21 }; |
21 }; |
22 |
22 |
23 void KdNode::subdivide(BBox bbox, int depth) |
23 void KdNode::subdivide(BBox bbox, int depth) |
24 { |
24 { |
|
25 if (depth >= 10 || shapes.size() <= 2) |
|
26 { |
|
27 leaf = true; |
|
28 return; |
|
29 } |
|
30 |
25 // choose split axis |
31 // choose split axis |
26 axis = 0; |
32 axis = 0; |
27 if (bbox.R.y - bbox.L.y > bbox.R.x - bbox.L.x) |
33 if (bbox.h() > bbox.w() && bbox.h() > bbox.d()) |
28 axis = 1; |
34 axis = 1; |
29 if (bbox.R.z - bbox.L.z > bbox.R.y - bbox.L.y) |
35 if (bbox.d() > bbox.w() && bbox.d() > bbox.h()) |
30 axis = 2; |
36 axis = 2; |
31 |
37 |
32 // *** find optimal split position |
38 // *** find optimal split position |
33 SortableShapeList sslist(shapes, axis); |
39 SortableShapeList sslist(shapes, axis); |
34 sort(sslist.begin(), sslist.end()); |
40 sort(sslist.begin(), sslist.end()); |
35 |
41 |
36 SplitList splitlist = SplitList(); |
42 SplitList splitlist; |
37 |
43 |
38 SortableShapeList::iterator sh; |
44 SortableShapeList::iterator sh; |
39 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
45 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
40 { |
46 { |
41 splitlist.push_back(SplitPos(sh->bbox.L.cell[axis])); |
47 splitlist.push_back(SplitPos(sh->bbox.L.cell[axis])); |
42 splitlist.push_back(SplitPos(sh->bbox.R.cell[axis])); |
48 splitlist.push_back(SplitPos(sh->bbox.R.cell[axis])); |
43 } |
49 } |
44 sort(splitlist.begin(), splitlist.end()); |
50 sort(splitlist.begin(), splitlist.end()); |
|
51 // remove duplicate splits |
|
52 splitlist.resize(unique(splitlist.begin(), splitlist.end()) - splitlist.begin()); |
45 |
53 |
46 // find all posible splits |
54 // find all posible splits |
47 SplitList::iterator spl; |
55 SplitList::iterator spl; |
48 int rest; |
56 int rest; |
49 for (spl = splitlist.begin(); spl != splitlist.end(); spl++) |
57 for (spl = splitlist.begin(); spl != splitlist.end(); spl++) |
50 { |
58 { |
51 for (sh = sslist.begin(), rest = sslist.size(); sh != sslist.end(); sh++, rest--) |
59 for (sh = sslist.begin(), rest = sslist.size(); sh != sslist.end(); sh++, rest--) |
52 { |
60 { |
53 if (sh->hasMark()) |
61 if (sh->hasMark()) |
|
62 { |
|
63 spl->lnum++; |
54 continue; |
64 continue; |
|
65 } |
55 // if shape is completely contained in split plane |
66 // if shape is completely contained in split plane |
56 if (spl->pos == sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis]) |
67 if (spl->pos == sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis]) |
57 { |
68 { |
58 if (spl->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - spl->pos) |
69 if (spl->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - spl->pos) |
59 { |
70 { |
103 { |
115 { |
104 // calculate SAH cost of this split |
116 // calculate SAH cost of this split |
105 lbb.R.cell[axis] = spl->pos; |
117 lbb.R.cell[axis] = spl->pos; |
106 rbb.L.cell[axis] = spl->pos; |
118 rbb.L.cell[axis] = spl->pos; |
107 float SAL = 2*(lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
119 float SAL = 2*(lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
108 float SAR = 2*(rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
120 float SAR = 2*(rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
109 float splitcost = K + SAL/SAV*(K+spl->lnum) + SAR/SAV*(K+spl->rnum); |
121 float splitcost = K + SAL/SAV*(K+spl->lnum) + SAR/SAV*(K+spl->rnum); |
110 |
122 |
111 if (splitcost < cost) |
123 if (splitcost < cost) |
112 { |
124 { |
113 leaf = false; |
125 leaf = false; |
114 cost = splitcost; |
126 cost = splitcost; |
116 } |
128 } |
117 } |
129 } |
118 |
130 |
119 if (leaf) |
131 if (leaf) |
120 return; |
132 return; |
|
133 |
|
134 #if 1 |
|
135 // export kd-tree as .obj for visualization |
|
136 // this would be hard to reconstruct later |
|
137 static ofstream F("kdtree.obj"); |
|
138 Vector3 v; |
|
139 static int f=0; |
|
140 v.cell[axis] = splitpos->pos; |
|
141 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
|
142 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
|
143 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
|
144 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
|
145 v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3]; |
|
146 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
|
147 v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3]; |
|
148 v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3]; |
|
149 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
|
150 v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3]; |
|
151 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
|
152 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
|
153 F << "f " << f+1 << " " << f+2 << " " << f+3 << " " << f+4 << endl; |
|
154 f += 4; |
|
155 #endif |
121 |
156 |
122 split = splitpos->pos; |
157 split = splitpos->pos; |
123 float lnum = splitpos->lnum; |
158 float lnum = splitpos->lnum; |
124 float rnum = splitpos->rnum; |
159 float rnum = splitpos->rnum; |
125 |
160 |
182 |
217 |
183 children[0].subdivide(lbb, depth+1); |
218 children[0].subdivide(lbb, depth+1); |
184 children[1].subdivide(rbb, depth+1); |
219 children[1].subdivide(rbb, depth+1); |
185 } |
220 } |
186 |
221 |
187 void KdTree::build() |
222 void KdTree::optimize() |
188 { |
223 { |
189 root = new KdNode(); |
224 root = new KdNode(); |
190 root->shapes = shapes; |
225 root->shapes = shapes; |
191 root->subdivide(bbox, 0); |
226 root->subdivide(bbox, 0); |
|
227 built = true; |
192 } |
228 } |
|
229 |
|
230 void KdTree::save(ostream &str, KdNode *node) |
|
231 { |
|
232 if (!built) |
|
233 return; |
|
234 if (node == NULL) |
|
235 node = root; |
|
236 if (node->isLeaf()) |
|
237 str << "(leaf: " << node->shapes.size() << " shapes)"; |
|
238 else |
|
239 { |
|
240 str << "(split " << (char)('x'+node->getAxis()) << " at " << node->getSplit() << "; L="; |
|
241 save(str, node->getLeftChild()); |
|
242 str << "; R="; |
|
243 save(str, node->getRightChild()); |
|
244 str << ";)"; |
|
245 } |
|
246 } |