263 farchild = node->getRightChild(); |
265 farchild = node->getRightChild(); |
264 node = node->getLeftChild(); |
266 node = node->getLeftChild(); |
265 } |
267 } |
266 else |
268 else |
267 { /* (stack[entry].pb[axis] > splitVal) */ |
269 { /* (stack[entry].pb[axis] > splitVal) */ |
268 if (splitVal < stack[exit].pb[axis]) |
270 if (stack[exit].pb[axis] > splitVal) |
269 { |
271 { |
270 /* case P1, P2, P3, and N5 */ |
272 /* case P1, P2, P3, and N5 */ |
271 node = node->getRightChild(); |
273 node = node->getRightChild(); |
272 continue; |
274 continue; |
273 } |
275 } |
303 Shape *nearest_shape = NULL; |
305 Shape *nearest_shape = NULL; |
304 Float dist = stack[exit].t; |
306 Float dist = stack[exit].t; |
305 ShapeList::iterator shape; |
307 ShapeList::iterator shape; |
306 for (shape = node->getShapes()->begin(); shape != node->getShapes()->end(); shape++) |
308 for (shape = node->getShapes()->begin(); shape != node->getShapes()->end(); shape++) |
307 if (*shape != origin_shape && (*shape)->intersect(ray, dist) |
309 if (*shape != origin_shape && (*shape)->intersect(ray, dist) |
308 && dist >= stack[entry].t) |
310 && dist >= stack[entry].t - Eps) |
309 { |
311 { |
310 nearest_shape = *shape; |
312 nearest_shape = *shape; |
311 nearest_distance = dist; |
313 nearest_distance = dist; |
312 } |
314 } |
313 |
315 |
324 |
326 |
325 /* ray leaves the scene */ |
327 /* ray leaves the scene */ |
326 return NULL; |
328 return NULL; |
327 } |
329 } |
328 |
330 |
329 // this should save whole kd-tree with triangles distributed into leaves |
331 ostream & operator<<(ostream &st, KdNode &node) |
330 void KdTree::save(ostream &str, KdNode *node) |
332 { |
|
333 if (node.isLeaf()) |
|
334 { |
|
335 st << "(l," << node.getShapes()->size(); |
|
336 ShapeList::iterator shape; |
|
337 for (shape = node.getShapes()->begin(); shape != node.getShapes()->end(); shape++) |
|
338 st << "," << shape_index[*shape]; |
|
339 st << ")"; |
|
340 } |
|
341 else |
|
342 { |
|
343 st << "(s," << (char)('x'+node.getAxis()) << "," << node.getSplit() << ","; |
|
344 st << *node.getLeftChild() << ","; |
|
345 st << *node.getRightChild() << ")"; |
|
346 } |
|
347 return st; |
|
348 } |
|
349 |
|
350 ostream & KdTree::dump(ostream &st) |
331 { |
351 { |
332 if (!built) |
352 if (!built) |
333 return; |
353 return Container::dump(st); |
334 if (node == NULL) |
354 |
335 node = root; |
355 st << "(kdtree," << shapes.size(); |
336 if (node->isLeaf()) |
356 ShapeList::iterator shape; |
337 str << "(leaf: " << node->getShapes()->size() << " shapes)"; |
357 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
338 else |
358 { |
339 { |
359 int idx; |
340 str << "(split " << (char)('x'+node->getAxis()) << " at " << node->getSplit() << "; L="; |
360 if (!shape_index.get(*shape, idx)) |
341 save(str, node->getLeftChild()); |
361 st << "," << endl << **shape; |
342 str << "; R="; |
362 } |
343 save(str, node->getRightChild()); |
363 return st << "," << endl << *getRootNode() << ")"; |
344 str << ";)"; |
364 } |
345 } |
365 |
346 } |
366 void KdTree::recursive_load(istream &st, KdNode *node) |
347 |
367 { |
348 // load kd-tree from file/stream |
368 string s; |
349 void KdTree::load(istream &str, KdNode *node) |
369 istringstream is; |
350 { |
370 |
351 |
371 getline(st, s, ','); |
352 } |
372 trim(s); |
|
373 |
|
374 if (s.compare("(s") == 0) |
|
375 { |
|
376 // split |
|
377 int axis; |
|
378 Float split; |
|
379 |
|
380 delete node->getShapes(); |
|
381 node->setChildren(new KdNode[2]); |
|
382 |
|
383 getline(st, s, ','); |
|
384 axis = s.c_str()[0]-'x'; |
|
385 node->setAxis(axis); |
|
386 |
|
387 st >> split; |
|
388 getline(st, s, ','); |
|
389 node->setSplit(split); |
|
390 |
|
391 recursive_load(st, node->getLeftChild()); |
|
392 getline(st, s, ','); |
|
393 recursive_load(st, node->getRightChild()); |
|
394 getline(st, s, ')'); |
|
395 } |
|
396 |
|
397 if (s.compare("(l") == 0) |
|
398 { |
|
399 // leaf |
|
400 int count, idx; |
|
401 |
|
402 node->setLeaf(); |
|
403 |
|
404 st >> count; |
|
405 for (int i = 0; i < count; i++) |
|
406 { |
|
407 getline(st, s, ','); |
|
408 st >> idx; |
|
409 node->addShape(shapes[idx]); |
|
410 } |
|
411 getline(st, s, ')'); |
|
412 } |
|
413 } |
|
414 |
|
415 istream & KdTree::load(istream &st) |
|
416 { |
|
417 string s; |
|
418 istringstream is; |
|
419 |
|
420 getline(st, s, ','); |
|
421 if (s.compare("(kdtree") != 0) |
|
422 return st; |
|
423 |
|
424 shapes.clear(); |
|
425 if (root) delete root; |
|
426 root = new KdNode(); |
|
427 |
|
428 getline(st, s, ','); |
|
429 int shape_count; |
|
430 is.str(s); |
|
431 is >> shape_count; |
|
432 |
|
433 Shape *shape; |
|
434 for (int i = 0; i < shape_count; i++) |
|
435 { |
|
436 shape = loadShape(st); |
|
437 Container::addShape(shape); |
|
438 getline(st, s, ','); |
|
439 } |
|
440 |
|
441 recursive_load(st, root); |
|
442 |
|
443 built = true; |
|
444 return st; |
|
445 } |