source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbtrav.cpp @ 2582

Revision 2582, 27.2 KB checked in by bittner, 17 years ago (diff)

Havran Ray Caster compiles and links, but still does not work

Line 
1// ===================================================================
2// $Id: $
3//
4// ktbtrav.cpp
5//
6// class: CKTBTraversal
7//
8// REPLACEMENT_STRING
9//
10// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
11// Initial coding by Vlasta Havran, February 2007 (copy from kdrtrav.cpp)
12
13// GOLEM headers
14#include "ktbtrav.h"
15#include "Intersectable.h"
16
17namespace GtpVisibilityPreprocessor {
18 
19//------------------------------------------------------------------
20// Robust statistically optimized algorithm for CKTB ray-traversal
21// original version 025. This algorithm was published at Journal of
22// Graphics Tools, 1997, Havran et al.
23
24// the depth of traversal when kd-trees are nested. The global (the highest
25// level) kd-tree is at the depth 0.
26int
27CKTBTraversal::traversalDepth = 0;
28
29// sets the stack pointers that are used for the traversal.
30void
31CKTBTraversal::GetStackPointers(struct SStackElem *&entryPointer,
32                                struct SStackElem *&exitPointer)
33{
34  assert(traversalDepth < MAX_NESTING);
35 
36  int index = traversalDepth * MAX_HEIGHT;
37  entryPointer = &(stack[index]);
38  exitPointer = &(stack[index + 1]);
39
40  traversalDepth++; 
41  return;
42}
43
44// sets the stack pointers that are used for the traversal.
45void
46CKTBTraversal::RestoreStackPointers()
47{
48  assert(traversalDepth >= 0);
49  traversalDepth--; 
50  return;
51}
52
53
54// default constructor
55CKTBTraversal::CKTBTraversal()
56{
57  bbox = AxisAlignedBox3(Vector3(MAXFLOAT),
58                         Vector3(-MAXFLOAT));
59  root = 0;
60  epsilon = 0;
61
62#ifdef __TRAVERSAL_STATISTICS
63  _allNodesTraversed = 0L;
64  _fullLeavesTraversed = 0L;
65  _emptyLeavesTraversed = 0L;
66#endif
67}
68
69// Here we find the node (preferably minbox node) containing
70// the point
71const SKTBNodeT*
72CKTBTraversal::Locate(const Vector3 &position)
73{
74  const SKTBNodeT *current, *next = root;
75  const SKTBNodeT *returnNode = 0;
76
77  do {
78    current = next;
79    switch (GetNodeType(current)) {
80      // -------------------------------------------------
81      case CKTBAxes::EE_X_axis: {
82        if (position[CKTBAxes::EE_X_axis] < current->splitPlane)
83          next =  GetLeft(current);
84        else
85          next = GetRight(current);
86        break;
87      }
88      case CKTBAxes::EE_Y_axis: {
89        if (position[CKTBAxes::EE_Y_axis] < current->splitPlane)
90          next =  GetLeft(current);
91        else
92          next = GetRight(current);
93        break;
94      }
95      case CKTBAxes::EE_Z_axis: {
96        if (position[CKTBAxes::EE_Z_axis] < current->splitPlane)
97          next =  GetLeft(current);
98        else
99          next = GetRight(current);
100        break;
101      }
102      case CKTBAxes::EE_X_axisBox: {
103        if (position[CKTBAxes::EE_X_axis] < current->splitPlane)
104          next =  GetLeft(current);
105        else
106          next = GetRight(current);
107        returnNode = current;
108        break;
109      }
110      case CKTBAxes::EE_Y_axisBox: {
111        if (position[CKTBAxes::EE_Y_axis] < current->splitPlane)
112          next =  GetLeft(current);
113        else
114          next = GetRight(current);
115        returnNode = current;
116        break;
117      }
118      case CKTBAxes::EE_Z_axisBox: {
119        if (position[CKTBAxes::EE_Z_axis] < current->splitPlane)
120          next =  GetLeft(current);
121        else
122          next = GetRight(current);
123        returnNode = current;
124        break;
125      }
126      case CKTBAxes::EE_Leaf: {
127        next = 0; // finishing
128        break;
129      }
130      case CKTBAxes::EE_Link:{
131        next = GetLinkNode(current);
132        // cout << "Link node was accessed" << endl;
133        break;
134      }
135    } // switch
136  }
137  while (next != NULL);
138
139  if (returnNode)
140    return returnNode;
141
142  // return the last (leaf node) visited on the path
143  return current;
144}
145
146#ifdef TRV000
147int
148CKTBTraversal::FindNearestI(const SimpleRay &ray)
149{
150  // passing through parameters
151  float tmin, tmax;
152 
153  // test if the whole CKTB tree is missed by the input ray
154  if ( (!root) ||
155       (!bbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) ||       
156       (tmin >= tmax) ||
157       (tmax < 0.f)
158     ) {
159    SimpleRay::IntersectionRes[0].intersectable = 0;
160    return 0; // no object can be intersected
161  }
162
163//#define _DEBUGKTB
164#ifdef _DEBUGKTB
165  int ib = 0;
166  int depth = 0;
167#endif
168 
169#ifdef __TRAVERSAL_STATISTICS
170  int allNodesTraversed = 0L;
171  int fullLeavesTraversed = 0L;
172  int emptyLeavesTraversed = 0L;
173#endif // __TRAVERSAL_STATISTICS
174
175#ifdef _COMPUTE_INVERTED_DIR_KTB 
176  Vector3 invertedDir;
177  invertedDir.x = 1.0f / ray.mDirection.x;
178  invertedDir.y = 1.0f / ray.mDirection.y;
179  invertedDir.z = 1.0f / ray.mDirection.z;
180#endif // _COMPUTE_INVERTED_DIR_KTB 
181
182  // start from the root node
183  SKTBNodeT *currNode = root;
184
185  struct SStackElem *entp, *extp;
186  GetStackPointers(entp, extp);
187  //struct SStackElem *entp = &(stack[0]);
188  //struct SStackElem *extp = &(stack[1]);
189
190  // exit point setting for the box and the ray
191  extp->x = ray.mOrigin.x + ray.mDirection.x * tmax;
192  extp->y = ray.mOrigin.y + ray.mDirection.y * tmax;
193  extp->z = ray.mOrigin.z + ray.mDirection.z * tmax;
194  extp->nodep = NULL;
195  extp->prev = NULL;
196  extp->t = tmax;
197
198  // entry point setting for the box and the ray
199  entp->nodep = NULL;
200  entp->prev = NULL;
201  if (tmin > 0.0) { // external node
202    entp->x = ray.mOrigin.x + ray.mDirection.x * tmin;
203    entp->y = ray.mOrigin.y + ray.mDirection.y * tmin;
204    entp->z = ray.mOrigin.z + ray.mDirection.z * tmin;
205    entp->t = tmin;
206  }
207  else { // internal node
208    entp->x = ray.mOrigin.x;
209    entp->y = ray.mOrigin.y;
210    entp->z = ray.mOrigin.z;
211    entp->t = 0.0;
212  }
213  SKTBNodeT *farChild;
214
215  // DEBUG << "A: c= " << currNode << "\n" << flush ;
216 
217  // traverse through whole CKTB tree
218  for (;;) {
219#ifndef _ALLOC_EMPTY_LEAVES
220    for (;;) {
221    // label for continuing the traversal
222#else
223    // we have to check the node
224    // current node is not the leaf, empty leaves are NULL pointers
225    while (currNode) {
226#endif
227
228#ifdef _DEBUGKTB
229      cout << "i = " << ib << " node = " << (void*)currNode
230           << " depth=" << depth << endl;
231      ib++;
232#endif     
233     
234#ifdef __TRAVERSAL_STATISTICS
235      allNodesTraversed++;
236#endif // __TRAVERSAL_STATISTICS
237      // the position of the splitting plane
238      float splitVal = GetSplitValue(currNode);
239      // decision based on the axis given by splitting plane
240      switch (GetNodeType(currNode) & 0x7) {
241        // -------------------------------------------------
242        case CKTBAxes::EE_X_axis: {
243#ifdef _DEBUGKTB
244          cout << "X-axis v=" << splitVal << endl;
245          depth++;
246#endif
247          if (entp->x <= splitVal) {
248            if (extp->x <= splitVal) {
249              currNode = GetLeft(currNode);
250              // cases N1,N2,N3,P5,Z2,Z3
251              continue;
252            }
253            // case N4
254            farChild = GetRight(currNode);
255            currNode = GetLeft(currNode);
256          }
257          else {
258            if (splitVal <= extp->x) {
259              currNode = GetRight(currNode);
260              continue; // cases P1,P2,P3,N5,Z1
261            }
262            farChild = GetLeft(currNode); // case P4
263            currNode = GetRight(currNode);
264          }
265#ifdef _DEBUGKTB
266          cout << "X-Push right node = " << farChild << endl;
267#endif   
268          // case N4 or P4
269#ifdef _COMPUTE_INVERTED_DIR_KTB
270          float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
271#else  // _COMPUTE_INVERTED_DIR_KTB
272          float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
273#endif // _COMPUTE_INVERTED_DIR_KTB
274         
275          struct SStackElem *tmp = extp;
276          if (++extp == entp)
277            extp++;
278#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
279          extp->dummy = depth+1;
280#endif
281          extp->prev = tmp;
282          extp->nodep = farChild;
283          extp->t = tdist;
284          extp->x = splitVal;
285          extp->y = ray.mOrigin.y +  tdist * ray.mDirection.y;
286          extp->z = ray.mOrigin.z +  tdist * ray.mDirection.z;
287          continue;
288        }
289        // -------------------------------------------------
290        case CKTBAxes::EE_Y_axis: {
291#ifdef _DEBUGKTB
292          cout << "Y-axis v=" << splitVal << endl;
293          depth++;
294#endif
295          if (entp->y <= splitVal) {
296            if (extp->y <= splitVal) {
297              currNode = GetLeft(currNode);
298              //case N1,N2,N3,P5,Z2,Z3
299              continue;
300            }
301            // case N4
302            farChild = GetRight(currNode);
303            currNode = GetLeft(currNode);
304          }
305          else {
306            if (splitVal <= extp->y) {
307              currNode = GetRight(currNode);
308              continue; // case P1,P2,P3,N5
309            }
310            farChild = GetLeft(currNode); // case P4
311            currNode = GetRight(currNode);
312          }
313#ifdef _DEBUGKTB
314          cout << "Y-Push right node = " << farChild << endl;
315#endif   
316          // case N4 or P4
317#ifdef _COMPUTE_INVERTED_DIR_KTB
318          float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
319#else  // _COMPUTE_INVERTED_DIR_KTB
320          float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
321#endif // _COMPUTE_INVERTED_DIR_KTB
322
323          struct SStackElem *tmp = extp;
324          if (++extp == entp)
325            extp++;
326#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
327          extp->dummy = depth+1;
328#endif           
329          extp->prev = tmp;
330          extp->nodep = farChild;
331          extp->t = tdist;
332          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
333          extp->y = splitVal;
334          extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
335          continue;
336        }
337        // -------------------------------------------------
338        case CKTBAxes::EE_Z_axis: {
339#ifdef _DEBUGKTB
340          cout << "Z-axis v=" << splitVal << endl;
341          depth++;
342#endif
343          if (entp->z <= splitVal) {
344            if (extp->z <= splitVal) {
345              currNode = GetLeft(currNode);
346              //case N1,N2,N3,P5,Z2,Z3
347              continue;
348            }
349            // case N4
350            farChild = GetRight(currNode);
351            currNode = GetLeft(currNode);
352          }
353          else {
354            if (splitVal <= extp->z) {
355              currNode = GetRight(currNode);
356              continue; // case P1,P2,P3,N5
357            }
358            farChild = GetLeft(currNode); // case P4
359            currNode = GetRight(currNode);
360          }
361#ifdef _DEBUGKTB
362          cout << "Z-Push right node = " << farChild << endl;
363#endif   
364          // case N4 or P4
365#ifdef _COMPUTE_INVERTED_DIR_KTB
366          float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
367#else  // _COMPUTE_INVERTED_DIR_KTB
368          float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
369#endif // _COMPUTE_INVERTED_DIR_KTB
370
371          struct SStackElem *tmp = extp;
372          if (++extp == entp)
373            extp++;
374#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
375          extp->dummy = depth+1;
376#endif   
377         
378          extp->prev = tmp;
379          extp->nodep = farChild;
380          extp->t = tdist;
381          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
382          extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
383          extp->z = splitVal;
384          continue;
385        }         
386        case CKTBAxes::EE_Leaf:
387        { // test objects for intersection
388#ifdef _DEBUGKTB
389          cout << "Leaf " << endl;
390          depth++;
391#endif
392          goto TEST_OBJECTS;
393        }
394        case CKTBAxes::EE_Link:{
395#ifdef _DEBUGKTB
396          cout << "Link " << endl;
397#endif   
398          currNode = GetLinkNode(currNode);
399          // cout << "Link node was accessed" << endl;
400          continue;
401        }
402        case CKTBAxes::EE_X_axisBox: {
403#ifdef _DEBUGKTB
404          cout << "X-axis Box v=" << splitVal << endl;
405          depth++;
406#endif
407          if (entp->x <= splitVal) {
408            if (extp->x <= splitVal) {
409              currNode = GetLeftMinBox(currNode);
410              // cases N1,N2,N3,P5,Z2,Z3
411              continue;
412            }
413            // case N4
414            farChild = GetRight(currNode);
415            currNode = GetLeftMinBox(currNode);
416          }
417          else {
418            if (splitVal <= extp->x) {
419              currNode = GetRight(currNode);
420              continue; // cases P1,P2,P3,N5,Z1
421            }
422            farChild = GetLeftMinBox(currNode); // case P4
423            currNode = GetRight(currNode);
424          }
425#ifdef _DEBUGKTB
426          cout << "X-Push (Box) right node = " << farChild << endl;
427#endif   
428          // case N4 or P4
429#ifdef _COMPUTE_INVERTED_DIR_KTB
430          float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
431#else  // _COMPUTE_INVERTED_DIR_KTB
432          float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
433#endif // _COMPUTE_INVERTED_DIR_KTB
434         
435          struct SStackElem *tmp = extp;
436          if (++extp == entp)
437            extp++;
438#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
439          extp->dummy = depth+1;
440#endif
441          extp->prev = tmp;
442          extp->nodep = farChild;
443          extp->t = tdist;
444          extp->x = splitVal;
445          extp->y = ray.mOrigin.y +  tdist * ray.mDirection.y;
446          extp->z = ray.mOrigin.z +  tdist * ray.mDirection.z;
447          continue;
448        }
449        // -------------------------------------------------
450        case CKTBAxes::EE_Y_axisBox: {
451#ifdef _DEBUGKTB
452          cout << "Y-axis Box v=" << splitVal << endl;
453          depth++;
454#endif
455          if (entp->y <= splitVal) {
456            if (extp->y <= splitVal) {
457              currNode = GetLeftMinBox(currNode);
458              //case N1,N2,N3,P5,Z2,Z3
459              continue;
460            }
461            // case N4
462            farChild = GetRight(currNode);
463            currNode = GetLeftMinBox(currNode);
464          }
465          else {
466            if (splitVal <= extp->y) {
467              currNode = GetRight(currNode);
468              continue; // case P1,P2,P3,N5
469            }
470            farChild = GetLeftMinBox(currNode); // case P4
471            currNode = GetRight(currNode);
472          }
473#ifdef _DEBUGKTB
474          cout << "Y-Push (Box) right node = " << farChild << endl;
475#endif   
476          // case N4 or P4
477#ifdef _COMPUTE_INVERTED_DIR_KTB
478          float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
479#else  // _COMPUTE_INVERTED_DIR_KTB
480          float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
481#endif // _COMPUTE_INVERTED_DIR_KTB
482
483          struct SStackElem *tmp = extp;
484          if (++extp == entp)
485            extp++;
486#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
487          extp->dummy = depth+1;
488#endif           
489          extp->prev = tmp;
490          extp->nodep = farChild;
491          extp->t = tdist;
492          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
493          extp->y = splitVal;
494          extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
495          continue;
496        }
497        // -------------------------------------------------
498        case CKTBAxes::EE_Z_axisBox: {
499#ifdef _DEBUGKTB
500          cout << "Z-axis Box v=" << splitVal << endl;
501          depth++;
502#endif
503          if (entp->z <= splitVal) {
504            if (extp->z <= splitVal) {
505              currNode = GetLeftMinBox(currNode);
506              //case N1,N2,N3,P5,Z2,Z3
507              continue;
508            }
509            // case N4
510            farChild = GetRight(currNode);
511            currNode = GetLeftMinBox(currNode);
512          }
513          else {
514            if (splitVal <= extp->z) {
515              currNode = GetRight(currNode);
516              continue; // case P1,P2,P3,N5
517            }
518            farChild = GetLeftMinBox(currNode); // case P4
519            currNode = GetRight(currNode);
520          }
521#ifdef _DEBUGKTB
522          cout << "Z-Push (Box) right node = " << farChild << endl;
523#endif   
524          // case N4 or P4
525#ifdef _COMPUTE_INVERTED_DIR_KTB
526          float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
527#else  // _COMPUTE_INVERTED_DIR_KTB
528          float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
529#endif // _COMPUTE_INVERTED_DIR_KTB
530
531          struct SStackElem *tmp = extp;
532          if (++extp == entp)
533            extp++;
534#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
535          extp->dummy = depth+1;
536#endif   
537         
538          extp->prev = tmp;
539          extp->nodep = farChild;
540          extp->t = tdist;
541          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
542          extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
543          extp->z = splitVal;
544          continue;
545        }         
546      } // switch
547    } // while current node is not the leaf
548
549    // leaf can be empty or full at this point
550TEST_OBJECTS:
551
552#ifdef _DEBUGKTB
553    DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
554          << " extp.t = " << extp->t << endl;
555#endif
556   
557    if (!IsEmptyLeaf_(currNode)) {
558#ifdef _DEBUGKTB
559      cout << "Full leaf at depth= " << depth << endl;
560#endif     
561
562#ifdef __TRAVERSAL_STATISTICS
563      fullLeavesTraversed++;
564#endif // __TRAVERSAL_STATISTICS
565      // test the objects in the full leaf against the ray
566     
567      SimpleRay::IntersectionRes[0].maxt = extp->t;
568      if (TestFullLeaf(ray, currNode)) {
569#ifdef _DEBUGKTB
570        cout << "Full leaf HIT " << endl;
571#endif 
572
573#ifdef __TRAVERSAL_STATISTICS
574        _allNodesTraversed += allNodesTraversed;
575        _fullLeavesTraversed += fullLeavesTraversed;
576        _emptyLeavesTraversed += emptyLeavesTraversed;
577#endif // __TRAVERSAL_STATISTICS
578       
579        // signed distance should be already set in TestFullLeaf
580        // the first object intersected was found       
581        RestoreStackPointers();
582        return 1;
583      }
584    }
585#ifdef __TRAVERSAL_STATISTICS
586    else {
587#ifdef _DEBUGKTB
588      cout << "Empty leaf at depth= " << depth << endl;
589#endif     
590      emptyLeavesTraversed++;
591    }
592#endif // __TRAVERSAL_STATISTICS
593
594
595#ifdef _DEBUGKTB
596    cout << "Pop the node" << endl;
597#endif     
598   
599    // pop farChild from the stack
600    // restore the current values
601    entp = extp;
602    currNode = entp->nodep;
603#ifdef _DEBUGKTB
604#ifdef _KTBEXTSTACK
605    depth = entp->dummy;
606    cout << "Popped node at depth = " << depth << endl;
607#endif   
608#endif
609
610    // DEBUG << "Pop c= " << currNode << "\n" << flush ;
611    if (currNode == NULL) {
612#ifdef _DEBUGKTB
613        cout << "NO HIT - EXIT " << endl;
614#endif 
615
616#ifdef __TRAVERSAL_STATISTICS
617        _allNodesTraversed += allNodesTraversed;
618        _fullLeavesTraversed += fullLeavesTraversed;
619        _emptyLeavesTraversed += emptyLeavesTraversed;
620#endif // __TRAVERSAL_STATISTICS
621
622      // no objects found along the ray path
623      RestoreStackPointers();
624      return 0;
625    }
626    extp = extp->prev;
627  } // for(;;)
628} // FindNearestI
629#endif // TRV000
630
631#ifdef TRV001
632int
633CKTBTraversal::FindNearestI(const SimpleRay &ray)
634{
635  // passing through parameters
636  float tmin, tmax;
637 
638  // test if the whole CKTB tree is missed by the input ray
639  if ( (!root) ||
640       (!bbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) ||
641       (tmin >= tmax) ||
642       (tmax <= 0.f)
643     ) {
644    SimpleRay::IntersectionRes[0].intersectable = 0;
645    return 0; // no object can be intersected
646  }
647
648//#define _DEBUGKTB
649#ifdef _DEBUGKTB
650  int ib = 0;
651  int depth = 0;
652#endif
653 
654#ifdef __TRAVERSAL_STATISTICS
655  int allNodesTraversed = 0L;
656  int fullLeavesTraversed = 0L;
657  int emptyLeavesTraversed = 0L;
658#endif // __TRAVERSAL_STATISTICS
659
660#ifdef _COMPUTE_INVERTED_DIR_KTB 
661  Vector3 invertedDir;
662  invertedDir.x = 1.0f / ray.mDirection.x;
663  invertedDir.y = 1.0f / ray.mDirection.y;
664  invertedDir.z = 1.0f / ray.mDirection.z;
665#endif // _COMPUTE_INVERTED_DIR_KTB 
666
667  // start from the root node
668  SKTBNodeT *currNode = root;
669
670  struct SStackElem *entp, *extp;
671  GetStackPointers(entp, extp);
672  //struct SStackElem *entp = &(stack[0]);
673  //struct SStackElem *extp = &(stack[1]);
674
675  // exit point setting for the box and the ray
676  extp->x = ray.mOrigin.x + ray.mDirection.x * tmax;
677  extp->y = ray.mOrigin.y + ray.mDirection.y * tmax;
678  extp->z = ray.mOrigin.z + ray.mDirection.z * tmax;
679  extp->nodep = NULL;
680  extp->prev = NULL;
681  extp->t = tmax;
682
683  // entry point setting for the box and the ray
684  entp->nodep = NULL;
685  entp->prev = NULL;
686  if (tmin > 0.0) { // external node
687    entp->x = ray.mOrigin.x + ray.mDirection.x * tmin;
688    entp->y = ray.mOrigin.y + ray.mDirection.y * tmin;
689    entp->z = ray.mOrigin.z + ray.mDirection.z * tmin;
690    entp->t = tmin;
691  }
692  else { // internal node
693    entp->x = ray.mOrigin.x;
694    entp->y = ray.mOrigin.y;
695    entp->z = ray.mOrigin.z;
696    entp->t = 0.0;
697  }
698  SKTBNodeT *farChild;
699
700  // DEBUG << "A: c= " << currNode << "\n" << flush ;
701 
702  // traverse through whole CKTB tree
703  for (;;) {
704#ifndef _ALLOC_EMPTY_LEAVES
705    for (;;) {
706    // label for continuing the traversal
707#else
708    // we have to check the node
709    // current node is not the leaf, empty leaves are NULL pointers
710    while (currNode) {
711#endif
712
713#ifdef _DEBUGKTB
714      cout << "i = " << ib << " node = " << (void*)currNode
715           << " depth=" << depth << endl;
716      ib++;
717#endif     
718     
719#ifdef __TRAVERSAL_STATISTICS
720      allNodesTraversed++;
721#endif // __TRAVERSAL_STATISTICS
722      // the position of the splitting plane
723      float splitVal = GetSplitValue(currNode);
724      // decision based on the axis given by splitting plane
725      switch (GetNodeType(currNode) & 0x07) {
726        // -------------------------------------------------
727        case CKTBAxes::EE_X_axis: {
728#ifdef _DEBUGKTB
729          cout << "X-axis v=" << splitVal << endl;
730          depth++;
731#endif
732          if (entp->x <= splitVal) {
733            if (extp->x <= splitVal) {
734              currNode = GetLeft(currNode);
735              // cases N1,N2,N3,P5,Z2,Z3
736              continue;
737            }
738            // case N4
739            farChild = GetRight(currNode);
740            currNode = GetLeft(currNode);
741          }
742          else {
743            if (splitVal <= extp->x) {
744              currNode = GetRight(currNode);
745              continue; // cases P1,P2,P3,N5,Z1
746            }
747            farChild = GetLeft(currNode); // case P4
748            currNode = GetRight(currNode);
749          }
750#ifdef _DEBUGKTB
751          cout << "X-Push right node = " << farChild << endl;
752#endif   
753          // case N4 or P4
754#ifdef _COMPUTE_INVERTED_DIR_KTB
755          float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
756#else  // _COMPUTE_INVERTED_DIR_KTB
757          float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
758#endif // _COMPUTE_INVERTED_DIR_KTB
759         
760          struct SStackElem *tmp = extp;
761          if (++extp == entp)
762            extp++;
763#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
764          extp->dummy = depth+1;
765#endif
766          extp->prev = tmp;
767          extp->nodep = farChild;
768          extp->t = tdist;
769          extp->x = splitVal;
770          extp->y = ray.mOrigin.y +  tdist * ray.mDirection.y;
771          extp->z = ray.mOrigin.z +  tdist * ray.mDirection.z;
772          continue;
773        }
774        // -------------------------------------------------
775        case CKTBAxes::EE_Y_axis: {
776#ifdef _DEBUGKTB
777          cout << "Y-axis v=" << splitVal << endl;
778          depth++;
779#endif
780          if (entp->y <= splitVal) {
781            if (extp->y <= splitVal) {
782              currNode = GetLeft(currNode);
783              //case N1,N2,N3,P5,Z2,Z3
784              continue;
785            }
786            // case N4
787            farChild = GetRight(currNode);
788            currNode = GetLeft(currNode);
789          }
790          else {
791            if (splitVal <= extp->y) {
792              currNode = GetRight(currNode);
793              continue; // case P1,P2,P3,N5
794            }
795            farChild = GetLeft(currNode); // case P4
796            currNode = GetRight(currNode);
797          }
798#ifdef _DEBUGKTB
799          cout << "Y-Push right node = " << farChild << endl;
800#endif   
801          // case N4 or P4
802#ifdef _COMPUTE_INVERTED_DIR_KTB
803          float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
804#else  // _COMPUTE_INVERTED_DIR_KTB
805          float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
806#endif // _COMPUTE_INVERTED_DIR_KTB
807
808          struct SStackElem *tmp = extp;
809          if (++extp == entp)
810            extp++;
811#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
812          extp->dummy = depth+1;
813#endif           
814          extp->prev = tmp;
815          extp->nodep = farChild;
816          extp->t = tdist;
817          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
818          extp->y = splitVal;
819          extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
820          continue;
821        }
822        // -------------------------------------------------
823        case CKTBAxes::EE_Z_axis: {
824#ifdef _DEBUGKTB
825          cout << "Z-axis v=" << splitVal << endl;
826          depth++;
827#endif
828          if (entp->z <= splitVal) {
829            if (extp->z <= splitVal) {
830              currNode = GetLeft(currNode);
831              //case N1,N2,N3,P5,Z2,Z3
832              continue;
833            }
834            // case N4
835            farChild = GetRight(currNode);
836            currNode = GetLeft(currNode);
837          }
838          else {
839            if (splitVal <= extp->z) {
840              currNode = GetRight(currNode);
841              continue; // case P1,P2,P3,N5
842            }
843            farChild = GetLeft(currNode); // case P4
844            currNode = GetRight(currNode);
845          }
846#ifdef _DEBUGKTB
847          cout << "Z-Push right node = " << farChild << endl;
848#endif   
849          // case N4 or P4
850#ifdef _COMPUTE_INVERTED_DIR_KTB
851          float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
852#else  // _COMPUTE_INVERTED_DIR_KTB
853          float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
854#endif // _COMPUTE_INVERTED_DIR_KTB
855
856          struct SStackElem *tmp = extp;
857          if (++extp == entp)
858            extp++;
859#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
860          extp->dummy = depth+1;
861#endif   
862         
863          extp->prev = tmp;
864          extp->nodep = farChild;
865          extp->t = tdist;
866          extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
867          extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
868          extp->z = splitVal;
869          continue;
870        }         
871        case CKTBAxes::EE_Leaf:
872        { // test objects for intersection
873#ifdef _DEBUGKTB
874          cout << "Leaf " << endl;
875          depth++;
876#endif
877          goto TEST_OBJECTS;
878        }
879        case CKTBAxes::EE_Link:{
880#ifdef _DEBUGKTB
881          cout << "Link " << endl;
882#endif   
883          currNode = GetLinkNode(currNode);
884          // cout << "Link node was accessed" << endl;
885          continue;
886        }
887      } // switch
888    } // while current node is not the leaf
889
890    // leaf can be empty or full at this point
891TEST_OBJECTS:
892
893#ifdef _DEBUGKTB
894    DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
895          << " extp.t = " << extp->t << endl;
896#endif
897   
898    if (!IsEmptyLeaf_(currNode)) {
899#ifdef _DEBUGKTB
900      cout << "Full leaf at depth= " << depth << endl;
901#endif     
902
903#ifdef __TRAVERSAL_STATISTICS
904      fullLeavesTraversed++;
905#endif // __TRAVERSAL_STATISTICS
906      // test the objects in the full leaf against the ray
907     
908      SimpleRay::IntersectionRes[0].maxt = extp->t;
909      if (TestFullLeaf(ray, currNode)) {
910#ifdef _DEBUGKTB
911        cout << "Full leaf HIT " << endl;
912#endif 
913
914#ifdef __TRAVERSAL_STATISTICS
915        _allNodesTraversed += allNodesTraversed;
916        _fullLeavesTraversed += fullLeavesTraversed;
917        _emptyLeavesTraversed += emptyLeavesTraversed;
918#endif // __TRAVERSAL_STATISTICS
919       
920        // signed distance should be already set in TestFullLeaf
921        // the first object intersected was found       
922        RestoreStackPointers();
923        return 1;
924      }
925    }
926#ifdef __TRAVERSAL_STATISTICS
927    else {
928#ifdef _DEBUGKTB
929      cout << "Empty leaf at depth= " << depth << endl;
930#endif     
931      emptyLeavesTraversed++;
932    }
933#endif // __TRAVERSAL_STATISTICS
934
935
936#ifdef _DEBUGKTB
937    cout << "Pop the node" << endl;
938#endif     
939   
940    // pop farChild from the stack
941    // restore the current values
942    entp = extp;
943    currNode = entp->nodep;
944#ifdef _DEBUGKTB
945#ifdef _KTBEXTSTACK
946    depth = entp->dummy;
947    cout << "Popped node at depth = " << depth << endl;
948#endif   
949#endif
950
951    // DEBUG << "Pop c= " << currNode << "\n" << flush ;
952    if (currNode == NULL) {
953#ifdef _DEBUGKTB
954        cout << "NO HIT - EXIT " << endl;
955#endif 
956
957#ifdef __TRAVERSAL_STATISTICS
958        _allNodesTraversed += allNodesTraversed;
959        _fullLeavesTraversed += fullLeavesTraversed;
960        _emptyLeavesTraversed += emptyLeavesTraversed;
961#endif // __TRAVERSAL_STATISTICS
962
963      // no objects found along the ray path
964      RestoreStackPointers();
965      return 0;
966    }
967    extp = extp->prev;
968  } // for(;;)
969} // FindNearestI
970
971#endif // TRV001
972
973#if defined(TRV000)||defined(TRV001)||defined(TRV002)||defined(TRV003)||defined(TRV004)||defined(TRV007)
974int
975CKTBTraversal::FindNearestI_16oneDir(SimpleRayContainer &rays)
976{
977  assert("NYI");
978}
979#endif
980
981#if defined(TRV000)||defined(TRV001)||defined(TRV002)||defined(TRV003)||defined(TRV004)||defined(TRV006)||defined(TRV007)||defined(TRV00F)
982int
983CKTBTraversal::FindNearestI_16twoDir(SimpleRayContainer &rays)
984{
985  assert("NYI");
986  return 0;
987}
988#endif
989
990#ifdef __SSE__
991#if defined(TRV000)||defined(TRV001)||defined(TRV002)||defined(TRV003)||defined(TRV004)||defined(TRV005)
992// The same operations for packets of rays, if implemented by
993// a particular ASDS, otherwise it is emulated by decomposition
994// of a packet to individual rays and traced individually.
995void
996CKTBTraversal::FindNearestI(RayPacket2x2 &raypack)
997{
998  for (int i = 0; i < 4; i++) {
999    cout << " orig = " << raypack.GetLoc(i) << " dir = "
1000         << raypack.GetDir(i) << endl;
1001  }
1002  // cout << "Not yet implemented" << endl;
1003}
1004#endif
1005#endif // __SSE__
1006 
1007} // namespace
1008
Note: See TracBrowser for help on using the repository browser.