83 ShapeList::iterator shape; |
83 ShapeList::iterator shape; |
84 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
84 for (shape = shapes.begin(); shape != shapes.end(); shape++) |
85 if (*shape != origin_shape && (*shape)->intersect(ray, nearest_distance)) |
85 if (*shape != origin_shape && (*shape)->intersect(ray, nearest_distance)) |
86 nearest_shape = *shape; |
86 nearest_shape = *shape; |
87 return nearest_shape; |
87 return nearest_shape; |
|
88 } |
|
89 |
|
90 KdNode::~KdNode() |
|
91 { |
|
92 if (isLeaf()) |
|
93 ;//delete shapes; // this sigsegvs for unknown reason |
|
94 else |
|
95 delete[] children; |
88 } |
96 } |
89 |
97 |
90 void KdNode::subdivide(BBox bbox, int depth) |
98 void KdNode::subdivide(BBox bbox, int depth) |
91 { |
99 { |
92 if (depth >= 20 || shapes->size() <= 4) |
100 if (depth >= 20 || shapes->size() <= 4) |
227 split = splitpos->pos; |
235 split = splitpos->pos; |
228 float lnum = splitpos->lnum; |
236 float lnum = splitpos->lnum; |
229 float rnum = splitpos->rnum; |
237 float rnum = splitpos->rnum; |
230 |
238 |
231 // split this node |
239 // split this node |
|
240 //delete shapes; |
232 children = new KdNode[2]; |
241 children = new KdNode[2]; |
233 int state = 0; |
242 int state = 0; |
234 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
243 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
235 { |
244 { |
236 // if shape is on left side of split plane |
245 // if shape is on left side of split plane |
309 return Container::nearest_intersection(origin_shape, ray, nearest_distance); |
318 return Container::nearest_intersection(origin_shape, ray, nearest_distance); |
310 |
319 |
311 if (!bbox.intersect(ray, a, b)) |
320 if (!bbox.intersect(ray, a, b)) |
312 return NULL; |
321 return NULL; |
313 |
322 |
314 stack<StackElem*> st; |
|
315 |
|
316 /* pointers to the far child node and current node */ |
323 /* pointers to the far child node and current node */ |
317 KdNode *farchild, *node; |
324 KdNode *farchild, *node; |
318 node = root; /* start from the kd-tree root node */ |
325 node = root; /* start from the kd-tree root node */ |
|
326 |
|
327 stack<StackElem*> st; |
319 |
328 |
320 StackElem *enPt = new StackElem(); |
329 StackElem *enPt = new StackElem(); |
321 enPt->t = a; /* set the signed distance */ |
330 enPt->t = a; /* set the signed distance */ |
322 enPt->node = NULL; |
331 enPt->node = NULL; |
323 |
332 |
330 /* setup initial exit point in the stack */ |
339 /* setup initial exit point in the stack */ |
331 StackElem *exPt = new StackElem(); |
340 StackElem *exPt = new StackElem(); |
332 exPt->t = b; |
341 exPt->t = b; |
333 exPt->pb = ray.o + ray.dir * b; |
342 exPt->pb = ray.o + ray.dir * b; |
334 exPt->node = NULL; /* set termination flag */ |
343 exPt->node = NULL; /* set termination flag */ |
335 |
344 st.push(exPt); |
336 st.push(enPt); |
|
337 |
345 |
338 /* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */ |
346 /* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */ |
339 while (node) |
347 while (node) |
340 { |
348 { |
|
349 exPt = st.top(); |
341 /* loop until a leaf is found */ |
350 /* loop until a leaf is found */ |
342 while (!node->isLeaf()) |
351 while (!node->isLeaf()) |
343 { |
352 { |
344 /* retrieve position of splitting plane */ |
353 /* retrieve position of splitting plane */ |
345 float splitVal = node->getSplit(); |
354 float splitVal = node->getSplit(); |
377 /* case P4 or N4 . . . traverse both children */ |
386 /* case P4 or N4 . . . traverse both children */ |
378 |
387 |
379 /* signed distance to the splitting plane */ |
388 /* signed distance to the splitting plane */ |
380 t = (splitVal - ray.o.cell[axis]) / ray.dir.cell[axis]; |
389 t = (splitVal - ray.o.cell[axis]) / ray.dir.cell[axis]; |
381 |
390 |
382 /* setup the new exit point */ |
391 /* setup the new exit point and push it onto stack */ |
383 st.push(exPt); |
|
384 exPt = new StackElem(); |
392 exPt = new StackElem(); |
385 |
|
386 /* push values onto the stack */ |
|
387 exPt->t = t; |
393 exPt->t = t; |
388 exPt->node = farchild; |
394 exPt->node = farchild; |
389 exPt->pb[axis] = splitVal; |
395 exPt->pb[axis] = splitVal; |
390 exPt->pb[(axis+1)%3] = ray.o.cell[(axis+1)%3] + t * ray.dir.cell[(axis+1)%3]; |
396 exPt->pb[(axis+1)%3] = ray.o.cell[(axis+1)%3] + t * ray.dir.cell[(axis+1)%3]; |
391 exPt->pb[(axis+2)%3] = ray.o.cell[(axis+2)%3] + t * ray.dir.cell[(axis+2)%3]; |
397 exPt->pb[(axis+2)%3] = ray.o.cell[(axis+2)%3] + t * ray.dir.cell[(axis+2)%3]; |
|
398 st.push(exPt); |
392 } /* while */ |
399 } /* while */ |
393 |
400 |
394 /* current node is the leaf . . . empty or full */ |
401 /* current node is the leaf . . . empty or full */ |
395 /* "intersect ray with each object in the object list, discarding " |
402 /* "intersect ray with each object in the object list, discarding " |
396 "those lying before stack[enPt].t or farther than stack[exPt].t" */ |
403 "those lying before stack[enPt].t or farther than stack[exPt].t" */ |
400 for (shape = node->shapes->begin(); shape != node->shapes->end(); shape++) |
407 for (shape = node->shapes->begin(); shape != node->shapes->end(); shape++) |
401 if (*shape != origin_shape && (*shape)->intersect(ray, dist) |
408 if (*shape != origin_shape && (*shape)->intersect(ray, dist) |
402 && dist >= enPt->t) |
409 && dist >= enPt->t) |
403 nearest_shape = *shape; |
410 nearest_shape = *shape; |
404 |
411 |
|
412 delete enPt; |
|
413 |
405 if (nearest_shape) |
414 if (nearest_shape) |
406 { |
415 { |
|
416 while (!st.empty()) |
|
417 { |
|
418 delete st.top(); |
|
419 st.pop(); |
|
420 } |
407 nearest_distance = dist; |
421 nearest_distance = dist; |
408 return nearest_shape; |
422 return nearest_shape; |
409 } |
423 } |
410 |
424 |
411 /* pop from the stack */ |
425 enPt = exPt; |
412 delete enPt; |
|
413 enPt = exPt; /* the signed distance intervals are adjacent */ |
|
414 |
426 |
415 /* retrieve the pointer to the next node, it is possible that ray traversal terminates */ |
427 /* retrieve the pointer to the next node, it is possible that ray traversal terminates */ |
416 node = enPt->node; |
428 node = enPt->node; |
417 |
|
418 // pop |
|
419 exPt = st.top(); |
|
420 st.pop(); |
429 st.pop(); |
421 } /* while */ |
430 } /* while */ |
422 |
431 |
423 delete enPt; |
432 delete enPt; |
424 |
433 |