equal
deleted
inserted
replaced
64 { |
64 { |
65 if (isLeaf()) |
65 if (isLeaf()) |
66 delete getShapes(); |
66 delete getShapes(); |
67 } |
67 } |
68 |
68 |
|
69 const int KdTree::MAX_DEPTH = 32; |
|
70 |
69 // kd-tree recursive build algorithm, inspired by PBRT (www.pbrt.org) |
71 // kd-tree recursive build algorithm, inspired by PBRT (www.pbrt.org) |
70 void KdTree::recursive_build(KdNode *node, const BBox &bounds, int maxdepth) |
72 void KdTree::recursive_build(KdNode *node, const BBox &bounds, int maxdepth) |
71 { |
73 { |
72 ShapeList *shapes = node->getShapes(); |
74 ShapeList *shapes = node->getShapes(); |
73 |
75 |
197 dbgmsg(1, "* building kd-tree\n"); |
199 dbgmsg(1, "* building kd-tree\n"); |
198 root = new KdNode(); |
200 root = new KdNode(); |
199 ShapeList::iterator shape; |
201 ShapeList::iterator shape; |
200 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
202 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
201 root->addShape(*shape); |
203 root->addShape(*shape); |
202 recursive_build(root, bbox, max_depth); |
204 recursive_build(root, bbox, MAX_DEPTH); |
203 built = true; |
205 built = true; |
204 } |
206 } |
205 |
207 |
206 /* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */ |
208 /* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */ |
207 const Shape *KdTree::nearest_intersection(const Shape *origin_shape, const Ray &ray, |
209 const Shape *KdTree::nearest_intersection(const Shape *origin_shape, const Ray &ray, |
219 |
221 |
220 /* pointers to the far child node and current node */ |
222 /* pointers to the far child node and current node */ |
221 KdNode *farchild, *node; |
223 KdNode *farchild, *node; |
222 node = root; |
224 node = root; |
223 |
225 |
224 #ifdef MSVC |
226 StackElem stack[MAX_DEPTH]; |
225 // MSVC wants constant expression here... hope it won't overflow :) |
|
226 StackElem stack[64]; |
|
227 #else |
|
228 StackElem stack[max_depth]; |
|
229 #endif |
|
230 |
227 |
231 int entry = 0, exit = 1; |
228 int entry = 0, exit = 1; |
232 stack[entry].t = a; |
229 stack[entry].t = a; |
233 |
230 |
234 /* distinguish between internal and external origin of a ray*/ |
231 /* distinguish between internal and external origin of a ray*/ |
294 register int tmp = exit; |
291 register int tmp = exit; |
295 |
292 |
296 exit++; |
293 exit++; |
297 if (exit == entry) |
294 if (exit == entry) |
298 exit++; |
295 exit++; |
299 assert(exit < max_depth); |
296 assert(exit < MAX_DEPTH); |
300 |
297 |
301 stack[exit].prev = tmp; |
298 stack[exit].prev = tmp; |
302 stack[exit].t = t; |
299 stack[exit].t = t; |
303 stack[exit].node = farchild; |
300 stack[exit].node = farchild; |
304 stack[exit].pb[axis] = splitVal; |
301 stack[exit].pb[axis] = splitVal; |
365 |
362 |
366 /* pointers to the far child node and current node */ |
363 /* pointers to the far child node and current node */ |
367 KdNode *farchild, *node; |
364 KdNode *farchild, *node; |
368 node = root; |
365 node = root; |
369 |
366 |
370 #ifdef MSVC |
367 StackElem4 stack[MAX_DEPTH]; |
371 // MSVC wants constant expression here... hope it won't overflow :) |
|
372 StackElem4 stack[64]; |
|
373 #else |
|
374 StackElem4 stack[max_depth]; |
|
375 #endif |
|
376 |
368 |
377 int entry = 0, exit = 1; |
369 int entry = 0, exit = 1; |
378 stack[entry].t = a; |
370 stack[entry].t = a; |
379 |
371 |
380 /* distinguish between internal and external origin of a ray*/ |
372 /* distinguish between internal and external origin of a ray*/ |
474 register int tmp = exit; |
466 register int tmp = exit; |
475 |
467 |
476 exit++; |
468 exit++; |
477 if (exit == entry) |
469 if (exit == entry) |
478 exit++; |
470 exit++; |
479 assert(exit < max_depth); |
471 assert(exit < MAX_DEPTH); |
480 |
472 |
481 stack[exit].prev = tmp; |
473 stack[exit].prev = tmp; |
482 stack[exit].t = t; |
474 stack[exit].t = t; |
483 stack[exit].node = farchild; |
475 stack[exit].node = farchild; |
484 stack[exit].pb.ma[axis] = splitVal; |
476 stack[exit].pb.ma[axis] = splitVal; |