source: GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.cpp @ 2543

Revision 2543, 34.7 KB checked in by mattausch, 17 years ago (diff)
RevLine 
[372]1#include <stack>
2#include <algorithm>
3#include <queue>
4#include "Environment.h"
5#include "Mesh.h"
6#include "KdTree.h"
[469]7#include "ViewCell.h"
[505]8#include "Beam.h"
[2116]9#include "ViewCell.h"
10#include "IntersectableWrapper.h"
[372]11
12
[2176]13using namespace std;
14
[372]15
[2332]16#define TYPE_INTERIOR -2
17#define TYPE_LEAF -3
18
19
[863]20namespace GtpVisibilityPreprocessor {
[860]21
[1176]22int KdNode::sMailId = 1;
23int KdNode::sReservedMailboxes = 1;
[863]24
[2066]25
[1197]26inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
27{
28        return obj1->mId < obj2->mId;
29}
30
31
[2539]32KdNode::KdNode(KdInterior *parent):
33mParent(parent), mMailbox(0), mIntersectable(NULL)
[372]34{
[2539]35        if (parent)
36                mDepth = parent->mDepth+1;
37        else
38                mDepth = 0;
[372]39}
40
[1002]41
42KdInterior::~KdInterior()
43{
44        // recursivly destroy children
45        DEL_PTR(mFront);
46        DEL_PTR(mBack);
47}
48
49
[1999]50KdLeaf::~KdLeaf()
51{
52        DEL_PTR(mViewCell); 
53}
54
55
[372]56KdTree::KdTree()
[2539]57{
[372]58  mRoot = new KdLeaf(NULL, 0);
[1004]59  Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxNodes", mTermMaxNodes);
60  Environment::GetSingleton()->GetIntValue("KdTree.Termination.maxDepth", mTermMaxDepth);
61  Environment::GetSingleton()->GetIntValue("KdTree.Termination.minCost", mTermMinCost);
62  Environment::GetSingleton()->GetFloatValue("KdTree.Termination.maxCostRatio", mMaxCostRatio);
63  Environment::GetSingleton()->GetFloatValue("KdTree.Termination.ct_div_ci", mCt_div_ci);
64  Environment::GetSingleton()->GetFloatValue("KdTree.splitBorder", mSplitBorder);
[2524]65  Environment::GetSingleton()->GetFloatValue("KdTree.pvsArea", mKdPvsArea);
[372]66
[1004]67  Environment::GetSingleton()->GetBoolValue("KdTree.sahUseFaces", mSahUseFaces);
[372]68
69  char splitType[64];
[1004]70  Environment::GetSingleton()->GetStringValue("KdTree.splitMethod", splitType);
[372]71 
72  mSplitMethod = SPLIT_SPATIAL_MEDIAN;
73  if (strcmp(splitType, "spatialMedian") == 0)
74    mSplitMethod = SPLIT_SPATIAL_MEDIAN;
75  else
76    if (strcmp(splitType, "objectMedian") == 0)
77      mSplitMethod = SPLIT_OBJECT_MEDIAN;
78    else
79      if (strcmp(splitType, "SAH") == 0)
80        mSplitMethod = SPLIT_SAH;
81      else {
82        cerr<<"Wrong kd split type "<<splitType<<endl;
83        exit(1);
84      }
85  splitCandidates = NULL;
86}
87
[1002]88
89KdTree::~KdTree()
90{
[1999]91    DEL_PTR(mRoot);
92        CLEAR_CONTAINER(mKdIntersectables);
[1002]93}
94
95
[372]96bool
97KdTree::Construct()
98{
[1076]99
[372]100  if (!splitCandidates)
[2003]101    splitCandidates = new vector<SortableEntry *>;
[372]102
103  // first construct a leaf that will get subdivide
104  KdLeaf *leaf = (KdLeaf *) mRoot;
105
106  mStat.nodes = 1;
107
108  mBox.Initialize();
109  ObjectContainer::const_iterator mi;
110  for ( mi = leaf->mObjects.begin();
111        mi != leaf->mObjects.end();
112        mi++) {
[752]113        //      cout<<(*mi)->GetBox()<<endl;
114        mBox.Include((*mi)->GetBox());
[372]115  }
116
[752]117  cout <<"KdTree Root Box:"<<mBox<<endl;
[372]118  mRoot = Subdivide(TraversalData(leaf, mBox, 0));
119
120  // remove the allocated array
[2003]121  CLEAR_CONTAINER(*splitCandidates);
[372]122  delete splitCandidates;
123
[2524]124  float area = GetBox().SurfaceArea()*mKdPvsArea;
[1989]125
126  SetPvsTerminationNodes(area);
127 
[372]128  return true;
129}
130
131KdNode *
132KdTree::Subdivide(const TraversalData &tdata)
133{
134
135  KdNode *result = NULL;
136
137  priority_queue<TraversalData> tStack;
138  //  stack<STraversalData> tStack;
139 
140  tStack.push(tdata);
141  AxisAlignedBox3 backBox, frontBox;
142
143  while (!tStack.empty()) {
[752]144        //      cout<<mStat.Nodes()<<" "<<mTermMaxNodes<<endl;
145        if (mStat.Nodes() > mTermMaxNodes) {
146          //    if ( GetMemUsage() > maxMemory ) {
[372]147      // count statistics on unprocessed leafs
148      while (!tStack.empty()) {
[752]149                EvaluateLeafStats(tStack.top());
150                tStack.pop();
[372]151      }
152      break;
153    }
[752]154         
155       
[372]156    TraversalData data = tStack.top();
157    tStack.pop();
158   
159    KdNode *node = SubdivideNode((KdLeaf *) data.mNode,
[752]160                                                                 data.mBox,
161                                                                 backBox,
162                                                                 frontBox
163                                                                 );
164
165        if (result == NULL)
[372]166      result = node;
167   
168    if (!node->IsLeaf()) {
169
170      KdInterior *interior = (KdInterior *) node;
171      // push the children on the stack
172      tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1));
173      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1));
174     
175    } else {
176      EvaluateLeafStats(data);
177    }
178  }
179 
180  return result;
181
182}
183
184
185bool
186KdTree::TerminationCriteriaMet(const KdLeaf *leaf)
187{
[2066]188        const bool criteriaMet =
189                ((int)leaf->mObjects.size() <= mTermMinCost) ||
190                 (leaf->mDepth >= mTermMaxDepth);
191 
[2539]192        if (0 && criteriaMet)
[2124]193                cerr<<"\n OBJECTS="<<(int)leaf->mObjects.size()<<endl;
[2066]194
195        return criteriaMet;
[372]196}
197
198
199int
200KdTree::SelectPlane(KdLeaf *leaf,
[752]201                                        const AxisAlignedBox3 &box,
202                                        float &position
203                                        )
[372]204{
205  int axis = -1;
206 
207  switch (mSplitMethod)
208    {
209    case SPLIT_SPATIAL_MEDIAN: {
210      axis = box.Size().DrivingAxis();
211      position = (box.Min()[axis] + box.Max()[axis])*0.5f;
212      break;
213    }
214    case SPLIT_SAH: {
215      int objectsBack, objectsFront;
216      float costRatio;
[1584]217      bool mOnlyDrivingAxis = true;
[1387]218
219          if (mOnlyDrivingAxis) {
[752]220                axis = box.Size().DrivingAxis();
221                costRatio = BestCostRatio(leaf,
222                                                                  box,
223                                                                  axis,
224                                                                  position,
225                                                                  objectsBack,
226                                                                  objectsFront);
[372]227      } else {
[752]228                costRatio = MAX_FLOAT;
229                for (int i=0; i < 3; i++) {
230                  float p;
231                  float r = BestCostRatio(leaf,
232                                                                  box,
233                                                                  i,
234                                                                  p,
235                                                                  objectsBack,
236                                                                  objectsFront);
237                  if (r < costRatio) {
238                        costRatio = r;
239                        axis = i;
240                        position = p;
241                  }
242                }
[372]243      }
244     
245      if (costRatio > mMaxCostRatio) {
[752]246                //cout<<"Too big cost ratio "<<costRatio<<endl;
247                axis = -1;
[372]248      }
249      break;
250    }
251   
252    }
253  return axis;
254}
255
256KdNode *
257KdTree::SubdivideNode(
258                      KdLeaf *leaf,
259                      const AxisAlignedBox3 &box,
260                      AxisAlignedBox3 &backBBox,
261                      AxisAlignedBox3 &frontBBox
262                      )
263{
264 
265  if (TerminationCriteriaMet(leaf))
[469]266          return leaf;
267
[372]268  float position;
269 
270  // select subdivision axis
271  int axis = SelectPlane( leaf, box, position );
272
273  if (axis == -1) {
274    return leaf;
275  }
276 
277  mStat.nodes+=2;
278  mStat.splits[axis]++;
279 
280  // add the new nodes to the tree
281  KdInterior *node = new KdInterior(leaf->mParent);
282
283  node->mAxis = axis;
284  node->mPosition = position;
285  node->mBox = box;
286 
287  backBBox = box;
288  frontBBox = box;
289 
290  // first count ray sides
291  int objectsBack = 0;
292  int objectsFront = 0;
293 
294  backBBox.SetMax(axis, position);
295  frontBBox.SetMin(axis, position);
296
297  ObjectContainer::const_iterator mi;
298
299  for ( mi = leaf->mObjects.begin();
300        mi != leaf->mObjects.end();
301        mi++) {
302    // determine the side of this ray with respect to the plane
303    AxisAlignedBox3 box = (*mi)->GetBox();
304    if (box.Max(axis) > position )
305      objectsFront++;
306   
307    if (box.Min(axis) < position )
308      objectsBack++;
309  }
310
311 
312  KdLeaf *back = new KdLeaf(node, objectsBack);
313  KdLeaf *front = new KdLeaf(node, objectsFront);
314
[1074]315 
[372]316  // replace a link from node's parent
317  if (  leaf->mParent )
318    leaf->mParent->ReplaceChildLink(leaf, node);
319
320  // and setup child links
321  node->SetupChildLinks(back, front);
322 
323  for (mi = leaf->mObjects.begin();
324       mi != leaf->mObjects.end();
325       mi++) {
326    // determine the side of this ray with respect to the plane
327    AxisAlignedBox3 box = (*mi)->GetBox();
[1736]328       
329        // matt: no more ref
[1143]330        // for handling multiple objects: keep track of references
[1736]331        //if (leaf->IsRoot())
332        //      (*mi)->mReferences = 1; // initialise references at root
[1143]333       
[1736]334        // matt: no more ref
335        //-- (*mi)->mReferences; // remove parent ref
[372]336
[1143]337
338        if (box.Max(axis) >= position )
339        {
[372]340      front->mObjects.push_back(*mi);
[1736]341          //++ (*mi)->mReferences;
[1143]342        }
343       
[372]344    if (box.Min(axis) < position )
[1143]345        {
[372]346      back->mObjects.push_back(*mi);
[1736]347        // matt: no more ref
348        //  ++ (*mi)->mReferences;
[1143]349        }
350
[1144]351    mStat.objectRefs -= (int)leaf->mObjects.size();
352    mStat.objectRefs += objectsBack + objectsFront;
353  }
354
[1143]355        // store objects referenced in more than one leaf
356        // for easy access
357        ProcessMultipleRefs(back);
358        ProcessMultipleRefs(front);
359
[1286]360        delete leaf;
361        return node;
[372]362}
363
364
[1143]365void KdTree::ProcessMultipleRefs(KdLeaf *leaf) const
366{
367        // find objects from multiple kd-leaves
368        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
369
370        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
371        {
372                Intersectable *object = *oit;
373               
[1736]374                // matt: no more ref
375                /*if (object->mReferences > 1)
[1143]376                {
377                        leaf->mMultipleObjects.push_back(object);
[1736]378                }*/
[1143]379        }
380}
381
382
[372]383void
384KdTreeStatistics::Print(ostream &app) const
385{
386  app << "===== KdTree statistics ===============\n";
387
388  app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
389
390  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
391
[667]392  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
[372]393  for (int i=0; i<7; i++)
394    app << splits[i] <<" ";
395  app <<endl;
396
397  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
398    rayRefs << "\n";
399
400  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
401    rayRefs/(double)rays << "\n";
402
403  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
404    rayRefs/(double)Leaves() << "\n";
405
[1184]406  app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
[372]407    maxObjectRefs << "\n";
408
409  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
410    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
411
412  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
413    objectRefs/(double)Leaves() << "\n";
414
415  //  app << setprecision(4);
416
417  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
418    zeroQueryNodes*100/(double)Leaves()<<endl;
419
420  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
421    maxDepthNodes*100/(double)Leaves()<<endl;
422
423  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
424    minCostNodes*100/(double)Leaves()<<endl;
425
426  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
427    addedRayRefs<<endl;
428
429  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
430    removedRayRefs<<endl;
431
432  //  app << setprecision(4);
433
434  //  app << "#N_CTIME  ( Construction time [s] )\n"
435  //      << Time() << " \n";
436
437  app << "===== END OF KdTree statistics ==========\n";
438
439}
440
441
442
443void
444KdTree::EvaluateLeafStats(const TraversalData &data)
445{
446
447  // the node became a leaf -> evaluate stats for leafs
448  KdLeaf *leaf = (KdLeaf *)data.mNode;
449
450  if (data.mDepth > mTermMaxDepth)
451    mStat.maxDepthNodes++;
452 
453  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
454    mStat.minCostNodes++;
455 
456 
457  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
[469]458    mStat.maxObjectRefs = (int)leaf->mObjects.size();
[372]459 
460}
461
462
463
464void
[1233]465KdTree::SortSubdivisionCandidates(
[372]466                            KdLeaf *node,
467                            const int axis
468                            )
469{
[2003]470        CLEAR_CONTAINER(*splitCandidates);
[2066]471        //splitCandidates->clear();
472
473    int requestedSize = 2*(int)node->mObjects.size();
474       
475        // creates a sorted split candidates array
476        if (splitCandidates->capacity() > 500000 &&
477                requestedSize < (int)(splitCandidates->capacity()/10) ) {               
478                        delete splitCandidates;
479                        splitCandidates = new vector<SortableEntry *>;
[372]480  }
481 
482  splitCandidates->reserve(requestedSize);
483 
484  // insert all queries
485  for(ObjectContainer::const_iterator mi = node->mObjects.begin();
486      mi != node->mObjects.end();
[2066]487      mi++)
488  {
489          AxisAlignedBox3 box = (*mi)->GetBox();
[372]490
[2066]491          splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
492                                                                 box.Min(axis),
493                                                                 *mi)
494                                                                 );
[372]495   
[2066]496      splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
497                                                                 box.Max(axis),
498                                                                 *mi)
499                                                                 );
[372]500  }
501 
[2066]502  stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
[372]503}
504
505
506float
507KdTree::BestCostRatio(
[752]508                                          KdLeaf *node,
509                                          const AxisAlignedBox3 &box,
510                                          const int axis,
511                                          float &position,
512                                          int &objectsBack,
513                                          int &objectsFront
514                                          )
[372]515{
516
[1387]517#define DEBUG_COST 0
518
519#if DEBUG_COST
520  static int nodeId = -1;
521  char filename[256];
522 
523  static int lastAxis = 100;
524  if (axis <= lastAxis)
525        nodeId++;
526
527  lastAxis = axis;
528 
529  sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
530  ofstream costStream;
531 
532  if (nodeId < 100)
533        costStream.open(filename);
534
535#endif
536 
[1233]537  SortSubdivisionCandidates(node, axis);
[372]538 
539  // go through the lists, count the number of objects left and right
540  // and evaluate the following cost funcion:
541  // C = ct_div_ci  + (ol + or)/queries
542
543  float totalIntersections = 0.0f;
[2003]544  vector<SortableEntry *>::const_iterator ci;
[372]545
546  for(ci = splitCandidates->begin();
547      ci < splitCandidates->end();
548      ci++)
[2003]549    if ((*ci)->type == SortableEntry::BOX_MIN) {
550      totalIntersections += (*ci)->intersectable->IntersectionComplexity();
[372]551    }
552       
553  float intersectionsLeft = 0;
554  float intersectionsRight = totalIntersections;
555       
[469]556  int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
[372]557 
558  float minBox = box.Min(axis);
559  float maxBox = box.Max(axis);
560  float boxArea = box.SurfaceArea();
561 
562  float minBand = minBox + mSplitBorder*(maxBox - minBox);
563  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
564 
[469]565  float minSum = 1e20f;
[372]566 
567  for(ci = splitCandidates->begin();
568      ci < splitCandidates->end();
569      ci++) {
[2003]570    switch ((*ci)->type) {
[372]571    case SortableEntry::BOX_MIN:
572      objectsLeft++;
[2003]573      intersectionsLeft += (*ci)->intersectable->IntersectionComplexity();
[372]574      break;
575    case SortableEntry::BOX_MAX:
576      objectsRight--;
[2003]577      intersectionsRight -= (*ci)->intersectable->IntersectionComplexity();
[372]578      break;
579    }
580
[2003]581    if ((*ci)->value > minBand && (*ci)->value < maxBand) {
[372]582      AxisAlignedBox3 lbox = box;
583      AxisAlignedBox3 rbox = box;
[2003]584      lbox.SetMax(axis, (*ci)->value);
585      rbox.SetMin(axis, (*ci)->value);
[372]586
587      float sum;
588      if (mSahUseFaces)
[752]589                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
[372]590      else
[752]591                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
[372]592     
593      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
594      //      cout<<"cost= "<<sum<<endl;
[1387]595
596#if DEBUG_COST
597  if (nodeId < 100) {
598        float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
599        float newCost = mCt_div_ci + sum/boxArea;
600        float ratio = newCost/oldCost;
[2003]601        costStream<<(*ci)->value<<" "<<ratio<<endl;
[1387]602  }
603#endif
604         
[372]605      if (sum < minSum) {
[752]606                minSum = sum;
[2003]607                position = (*ci)->value;
[752]608               
609                objectsBack = objectsLeft;
610                objectsFront = objectsRight;
[372]611      }
612    }
613  }
614 
615  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
616  float newCost = mCt_div_ci + minSum/boxArea;
617  float ratio = newCost/oldCost;
618 
619#if 0
620  cout<<"===================="<<endl;
621  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
622      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
623#endif
624  return ratio;
625}
626
627int
628KdTree::CastRay(
[462]629                                Ray &ray
630                                )
[372]631{
[1984]632 
[372]633  int hits = 0;
634 
635  stack<RayTraversalData> tStack;
636 
637  float maxt = 1e6;
638  float mint = 0;
[1583]639
[1584]640  //  ray.ComputeInvertedDir();
[372]641  Intersectable::NewMail();
642
643  if (!mBox.GetMinMaxT(ray, &mint, &maxt))
644    return 0;
645
646  if (mint < 0)
647    mint = 0;
[1584]648
[372]649 
650  maxt += Limits::Threshold;
651 
652  Vector3 entp = ray.Extrap(mint);
653  Vector3 extp = ray.Extrap(maxt);
654 
655  KdNode *node = mRoot;
656  KdNode *farChild;
657  float position;
658  int axis;
[752]659
[372]660 
661  while (1) {
662    if (!node->IsLeaf()) {
663      KdInterior *in = (KdInterior *) node;
664      position = in->mPosition;
665      axis = in->mAxis;
666
667      if (entp[axis] <= position) {
[752]668                if (extp[axis] <= position) {
669                  node = in->mBack;
670                  // cases N1,N2,N3,P5,Z2,Z3
671                  continue;
672                } else {
673                  // case N4
674                  node = in->mBack;
675                  farChild = in->mFront;
676                }
[372]677      }
678      else {
[752]679                if (position <= extp[axis]) {
680                  node = in->mFront;
681                  // cases P1,P2,P3,N5,Z1
682                  continue;
683                } else {
684                  node = in->mFront;
685                  farChild = in->mBack;
686                  // case P4
687                }
688          }
[372]689      // $$ modification 3.5.2004 - hints from Kamil Ghais
690      // case N4 or P4
691      float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
692      tStack.push(RayTraversalData(farChild, extp, maxt));
693      extp = ray.GetLoc() + ray.GetDir()*tdist;
694      maxt = tdist;
[752]695        } else {
696          // compute intersection with all objects in this leaf
697          KdLeaf *leaf = (KdLeaf *) node;
698          if (ray.mFlags & Ray::STORE_KDLEAVES)
699                ray.kdLeaves.push_back(leaf);
700         
701          ObjectContainer::const_iterator mi;
702          for ( mi = leaf->mObjects.begin();
[1867]703                        mi != leaf->mObjects.end();
704                        mi++) {
705                Intersectable *object = *mi;
706                if (!object->Mailed() ) {
707                  object->Mail();
708                  if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
709                        ray.testedObjects.push_back(object);
710                 
711                  static int oi=1;
712                  if (MeshDebug)
713                        cout<<"Object "<<oi++;
714                 
715                  hits += object->CastRay(ray);
716                 
717                  if (MeshDebug) {
718                        if (!ray.intersections.empty())
719                          cout<<"nearest t="<<ray.intersections[0].mT<<endl;
720                        else
721                          cout<<"nearest t=-INF"<<endl;
722                  }       
723                }
[752]724          }
725         
726          if (hits && ray.GetType() == Ray::LOCAL_RAY)
[1867]727                if (ray.intersections[0].mT <= maxt)
728                  break;
[752]729         
730          // get the next node from the stack
731          if (tStack.empty())
[1867]732                break;
[752]733         
734          entp = extp;
735          mint = maxt;
736          if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
[1867]737                break;
[752]738         
739          RayTraversalData &s  = tStack.top();
740          node = s.mNode;
741          extp = s.mExitPoint;
742          maxt = s.mMaxT;
743          tStack.pop();
744        }
[372]745  }
746  return hits;
747}
748
[469]749int KdTree::CastLineSegment(const Vector3 &origin,
750                                                        const Vector3 &termination,
[882]751                                                        ViewCellContainer &viewcells)
[469]752{
753        int hits = 0;
[2017]754
[469]755        float mint = 0.0f, maxt = 1.0f;
756        const Vector3 dir = termination - origin;
757
[475]758        stack<RayTraversalData> tStack;
[469]759
760        Intersectable::NewMail();
761
762        //maxt += Limits::Threshold;
763
764        Vector3 entp = origin;
765        Vector3 extp = termination;
766
767        KdNode *node = mRoot;
768        KdNode *farChild;
769
770        float position;
771        int axis;
772
773        while (1)
774        {
[2017]775                if (!node->IsLeaf())
776                {
777                        KdInterior *in = static_cast<KdInterior *>(node);
778                        position = in->mPosition;
779                        axis = in->mAxis;
780
781                        if (entp[axis] <= position)
782                        {
783                                if (extp[axis] <= position)
784                                {
785                                        node = in->mBack;
786                                        // cases N1,N2,N3,P5,Z2,Z3
787                                        continue;
788                                }
789                                else
790                                {
791                                        // case N4
792                                        node = in->mBack;
793                                        farChild = in->mFront;
794                                }
795                        }
[469]796                        else
[2017]797                        {
798                                if (position <= extp[axis])
799                                {
800                                        node = in->mFront;
801                                        // cases P1,P2,P3,N5,Z1
802                                        continue;
803                                }
804                                else
805                                {
806                                        node = in->mFront;
807                                        farChild = in->mBack;
808                                        // case P4
809                                }
810                        }
811
812                        // $$ modification 3.5.2004 - hints from Kamil Ghais
813                        // case N4 or P4
814                        float tdist = (position - origin[axis]) / dir[axis];
815                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
816                        extp = origin + dir * tdist;
817                        maxt = tdist;
818                }
[469]819                else
820                {
[2017]821                        // compute intersection with all objects in this leaf
822                        KdLeaf *leaf = static_cast<KdLeaf *>(node);
823
824                        // add view cell to intersections
825                        ViewCell *vc = leaf->mViewCell;
826
827                        if (!vc->Mailed())
828                        {
829                                vc->Mail();
830                                viewcells.push_back(vc);
831                                ++ hits;
832                        }
833
834                        // get the next node from the stack
835                        if (tStack.empty())
836                                break;
837
838                        entp = extp;
839                        mint = maxt;
840                       
841                        RayTraversalData &s  = tStack.top();
842                        node = s.mNode;
843                        extp = s.mExitPoint;
844                        maxt = s.mMaxT;
845                        tStack.pop();
[469]846                }
847        }
[2017]848
[469]849        return hits;
850}
851
[1974]852void
853KdTree::CollectKdObjects(const AxisAlignedBox3 &box,
[1989]854                                                 ObjectContainer &objects
[1974]855                                                 )
856{
857  stack<KdNode *> nodeStack;
858 
859  nodeStack.push(mRoot);
[469]860
[1974]861  while (!nodeStack.empty()) {
862    KdNode *node = nodeStack.top();
863    nodeStack.pop();
[1989]864        if (node->IsLeaf() || node->mPvsTermination == 1)  {
[1974]865          Intersectable *object = GetOrCreateKdIntersectable(node);
[2543]866          if (!node->Mailed()) {
867                node->Mail();
[1974]868                objects.push_back(object);
869          }
870        } else {
871      KdInterior *interior = (KdInterior *)node;
872         
873          if ( box.Max()[interior->mAxis] > interior->mPosition )
874                nodeStack.push(interior->mFront);
875         
876          if (box.Min()[interior->mAxis] < interior->mPosition)
877                nodeStack.push(interior->mBack);
878    }
879  }
880}
881
[372]882void
[859]883KdTree::CollectObjects(const AxisAlignedBox3 &box,
884                                           ObjectContainer &objects)
885{
886  stack<KdNode *> nodeStack;
887
888  nodeStack.push(mRoot);
889
890  while (!nodeStack.empty()) {
891    KdNode *node = nodeStack.top();
892    nodeStack.pop();
893    if (node->IsLeaf()) {
894      KdLeaf *leaf = (KdLeaf *)node;
895      for (int j=0; j < leaf->mObjects.size(); j++) {
896                Intersectable *object = leaf->mObjects[j];
[904]897                if (!object->Mailed() && Overlap(box, object->GetBox())) {
[859]898                  object->Mail();
899                  objects.push_back(object);
900                }
901      }
902    } else {
903      KdInterior *interior = (KdInterior *)node;
904
905          if ( box.Max()[interior->mAxis] > interior->mPosition )
906                nodeStack.push(interior->mFront);
907 
908          if (box.Min()[interior->mAxis] < interior->mPosition)
909                nodeStack.push(interior->mBack);
910    }
911  }
912}
913
914void
[372]915KdTree::CollectObjects(KdNode *n, ObjectContainer &objects)
916{
917  stack<KdNode *> nodeStack;
918
919  nodeStack.push(n);
920
921  while (!nodeStack.empty()) {
922    KdNode *node = nodeStack.top();
923    nodeStack.pop();
924    if (node->IsLeaf()) {
925      KdLeaf *leaf = (KdLeaf *)node;
926      for (int j=0; j < leaf->mObjects.size(); j++) {
[374]927                                Intersectable *object = leaf->mObjects[j];
928                                if (!object->Mailed()) {
929                                        object->Mail();
930                                        objects.push_back(object);
931                                }
[372]932      }
933    } else {
934      KdInterior *interior = (KdInterior *)node;
935      nodeStack.push(interior->mFront);
936      nodeStack.push(interior->mBack);
937    }
938  }
939}
940
941// Find random neighbor which was not mailed
942KdNode *
943KdTree::FindRandomNeighbor(KdNode *n,
[1286]944                                                   bool onlyUnmailed
945                                                   )
[372]946{
947  stack<KdNode *> nodeStack;
948 
949  nodeStack.push(mRoot);
950
951  AxisAlignedBox3 box = GetBox(n);
952  int mask = rand();
953
954  while (!nodeStack.empty()) {
955    KdNode *node = nodeStack.top();
956    nodeStack.pop();
957    if (node->IsLeaf()) {
958      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
959        return node;
960    } else {
961      KdInterior *interior = (KdInterior *)node;
962      if (interior->mPosition > box.Max(interior->mAxis))
963        nodeStack.push(interior->mBack);
964      else
965        if (interior->mPosition < box.Min(interior->mAxis))
966          nodeStack.push(interior->mFront);
967        else {
968          // random decision
969          if (mask&1)
970            nodeStack.push(interior->mBack);
971          else
972            nodeStack.push(interior->mFront);
973          mask = mask>>1;
974        }
975    }
976  }
977 
978  return NULL;
979}
980
981int
982KdTree::FindNeighbors(KdNode *n,
983                      vector<KdNode *> &neighbors,
984                      bool onlyUnmailed
985                      )
986{
987  stack<KdNode *> nodeStack;
988 
989  nodeStack.push(mRoot);
990
991  AxisAlignedBox3 box = GetBox(n);
992
993  while (!nodeStack.empty()) {
994    KdNode *node = nodeStack.top();
995    nodeStack.pop();
996    if (node->IsLeaf()) {
997      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
998        neighbors.push_back(node);
999    } else {
1000      KdInterior *interior = (KdInterior *)node;
1001      if (interior->mPosition > box.Max(interior->mAxis))
[374]1002                                nodeStack.push(interior->mBack);
[372]1003      else
[374]1004                                if (interior->mPosition < box.Min(interior->mAxis))
1005                                        nodeStack.push(interior->mFront);
1006                                else {
1007                                        // random decision
1008                                        nodeStack.push(interior->mBack);
1009                                        nodeStack.push(interior->mFront);
1010                                }
[372]1011    }
1012  }
1013 
[469]1014  return (int)neighbors.size();
[372]1015}
1016
1017// Find random neighbor which was not mailed
1018KdNode *
1019KdTree::GetRandomLeaf(const Plane3 &plane)
1020{
1021  stack<KdNode *> nodeStack;
1022 
1023  nodeStack.push(mRoot);
1024 
1025  int mask = rand();
1026 
1027  while (!nodeStack.empty()) {
1028    KdNode *node = nodeStack.top();
1029    nodeStack.pop();
1030    if (node->IsLeaf()) {
1031      return node;
1032    } else {
1033      KdInterior *interior = (KdInterior *)node;
1034      KdNode *next;
1035        if (GetBox(interior->mBack).Side(plane) < 0)
1036          next = interior->mFront;
1037        else
1038          if (GetBox(interior->mFront).Side(plane) < 0)
1039            next = interior->mBack;
1040          else {
1041            // random decision
1042            if (mask&1)
1043              next = interior->mBack;
1044            else
1045              next = interior->mFront;
1046            mask = mask>>1;
1047          }
1048        nodeStack.push(next);
1049    }
1050  }
1051 
1052 
1053  return NULL;
1054}
1055
1056void
1057KdTree::CollectLeaves(vector<KdLeaf *> &leaves)
1058{
1059  stack<KdNode *> nodeStack;
1060  nodeStack.push(mRoot);
1061
1062  while (!nodeStack.empty()) {
1063    KdNode *node = nodeStack.top();
1064    nodeStack.pop();
1065    if (node->IsLeaf()) {
1066      KdLeaf *leaf = (KdLeaf *)node;
1067      leaves.push_back(leaf);
1068    } else {
1069      KdInterior *interior = (KdInterior *)node;
1070      nodeStack.push(interior->mBack);
1071      nodeStack.push(interior->mFront);
1072    }
1073  }
1074}
1075
[469]1076void
1077KdTree::CreateAndCollectViewCells(ViewCellContainer &vc) const
1078{
1079  stack<KdNode *> nodeStack;
1080  nodeStack.push(mRoot);
[372]1081
[469]1082  while (!nodeStack.empty()) {
1083    KdNode *node = nodeStack.top();
1084    nodeStack.pop();
1085    if (node->IsLeaf()) {
1086      KdLeaf *leaf = (KdLeaf *)node;
1087          // kdtree used as view cell container => create view cell
[471]1088          KdViewCell *viewCell = new KdViewCell();
1089          leaf->mViewCell = viewCell;
1090          // push back pointer to this leaf
[1551]1091          viewCell->mLeaves[0] = leaf;
[471]1092      vc.push_back(viewCell);
[469]1093    } else {
1094      KdInterior *interior = (KdInterior *)node;
1095      nodeStack.push(interior->mBack);
1096      nodeStack.push(interior->mFront);
1097    }
1098  }
1099}
1100
[1736]1101
[372]1102KdNode *
1103KdTree::GetRandomLeaf(const bool onlyUnmailed)
1104{
[507]1105  stack<KdNode *> nodeStack;
[372]1106  nodeStack.push(mRoot);
[507]1107 
1108  int mask = rand();
[372]1109       
1110  while (!nodeStack.empty()) {
1111    KdNode *node = nodeStack.top();
1112    nodeStack.pop();
1113    if (node->IsLeaf()) {
1114      if ( (!onlyUnmailed || !node->Mailed()) )
1115                                return node;
1116    } else {
1117      KdInterior *interior = (KdInterior *)node;
1118                        // random decision
1119                        if (mask&1)
1120                                nodeStack.push(interior->mBack);
1121                        else
1122                                nodeStack.push(interior->mFront);
1123                        mask = mask>>1;
1124                }
1125        }
1126  return NULL;
1127}
[504]1128
1129
[2539]1130int KdTree::CastBeam(Beam &beam)
[504]1131{
[507]1132  stack<KdNode *> nodeStack;
1133  nodeStack.push(mRoot);
[504]1134 
[507]1135  while (!nodeStack.empty()) {
1136    KdNode *node = nodeStack.top();
1137    nodeStack.pop();
1138       
1139        int side = beam.ComputeIntersection(GetBox(node));
1140        switch (side) {
1141        case -1:
1142          beam.mKdNodes.push_back(node);
1143          break;
1144        case 0:
1145          if (node->IsLeaf())
1146                beam.mKdNodes.push_back(node);
1147          else {
1148                KdInterior *interior = (KdInterior *)node;
1149                KdNode *first = interior->mBack;
1150                KdNode *second = interior->mFront;
1151               
1152                if (interior->mAxis < 3) {
1153                  // spatial split -> decide on the order of the nodes
1154                  if (beam.mPlanes[0].mNormal[interior->mAxis] > 0)
1155                        swap(first, second);
1156                }
[504]1157
[507]1158                nodeStack.push(first);
1159                nodeStack.push(second);
1160          }
1161          break;
1162          // default: cull
1163        }
1164  }
1165
[532]1166  if (beam.mFlags & Beam::STORE_OBJECTS)
1167  {
1168          vector<KdNode *>::const_iterator it, it_end = beam.mKdNodes.end();
[535]1169       
[532]1170          Intersectable::NewMail();
1171          for (it = beam.mKdNodes.begin(); it != it_end; ++ it)
1172          {
1173                  CollectObjects(*it, beam.mObjects);
1174          }
1175  }
1176
[837]1177  return (int)beam.mKdNodes.size();
[504]1178}
[860]1179
[1074]1180
[1201]1181void KdTree::ExportBinLeaf(OUT_STREAM &stream, KdLeaf *leaf)
[1194]1182{
1183        ObjectContainer::const_iterator it, it_end = leaf->mObjects.end();
1184       
[1196]1185        int type = TYPE_LEAF;
1186        int size = (int)leaf->mObjects.size();
1187
1188        stream.write(reinterpret_cast<char *>(&type), sizeof(int));
1189        stream.write(reinterpret_cast<char *>(&size), sizeof(int));
1190
[1194]1191        for (it = leaf->mObjects.begin(); it != it_end; ++ it)
1192        {       
1193                Intersectable *obj = *it;
1194                int id = obj->mId;             
[1196]1195       
[1194]1196                //stream.write(reinterpret_cast<char *>(&origin), sizeof(Vector3));
1197                stream.write(reinterpret_cast<char *>(&id), sizeof(int));
1198    }
[878]1199}
[1194]1200
1201
[1201]1202KdLeaf *KdTree::ImportBinLeaf(IN_STREAM &stream,
[1197]1203                                                          KdInterior *parent,
1204                                                          const ObjectContainer &objects)
[1194]1205{
[1196]1206        int leafId = TYPE_LEAF;
[1194]1207        int objId = leafId;
[1196]1208        int size;
1209
1210        stream.read(reinterpret_cast<char *>(&size), sizeof(int));
1211        KdLeaf *leaf = new KdLeaf(parent, size);
1212
[1197]1213        MeshInstance dummyInst(NULL);
[1633]1214       
[1196]1215        // read object ids
[2539]1216        // note: this can also be done geometrically
[1196]1217        for (int i = 0; i < size; ++ i)
[1194]1218        {       
1219                stream.read(reinterpret_cast<char *>(&objId), sizeof(int));
[1197]1220                dummyInst.SetId(objId);
[1196]1221
[1197]1222                ObjectContainer::const_iterator oit =
1223                        lower_bound(objects.begin(), objects.end(), (Intersectable *)&dummyInst, ilt);
1224                                                               
1225                if ((oit != objects.end()) && ((*oit)->GetId() == objId))
[2539]1226                        leaf->mObjects.push_back(*oit);
[1197]1227                else
1228                        Debug << "error: object with id " << objId << " does not exist" << endl;
1229        }
1230
[1196]1231        return leaf;
[1194]1232}
1233
1234
[1201]1235void KdTree::ExportBinInterior(OUT_STREAM &stream, KdInterior *interior)
[1194]1236{
[1196]1237        int interiorid = TYPE_INTERIOR;
[1194]1238        stream.write(reinterpret_cast<char *>(&interiorid), sizeof(int));
1239
1240        int axis = interior->mAxis;
[1196]1241        float pos = interior->mPosition;
[1194]1242
1243        stream.write(reinterpret_cast<char *>(&axis), sizeof(int));
[1196]1244        stream.write(reinterpret_cast<char *>(&pos), sizeof(float));
[1194]1245}
1246
1247
[1201]1248KdInterior *KdTree::ImportBinInterior(IN_STREAM  &stream, KdInterior *parent)
[1194]1249{
[1196]1250        KdInterior *interior = new KdInterior(parent);
[1194]1251
[2539]1252        int axis;
1253        float pos;
[1194]1254
1255        stream.read(reinterpret_cast<char *>(&axis), sizeof(int));
[1196]1256        stream.read(reinterpret_cast<char *>(&pos), sizeof(float));
1257
1258        interior->mAxis = axis;
1259        interior->mPosition = pos;
1260
1261        return interior;
[1194]1262}
1263
1264
1265bool KdTree::ExportBinTree(const string &filename)
1266{
[1201]1267        OUT_STREAM stream(filename.c_str(), OUT_BIN_MODE);
[1194]1268       
[2332]1269        if (!stream.is_open()) return false;
[1194]1270
1271        // export binary version of mesh
[1197]1272        queue<KdNode *> tStack;
[1194]1273        tStack.push(mRoot);
1274
1275        while(!tStack.empty())
1276        {
[1197]1277                KdNode *node = tStack.front();
[1196]1278                tStack.pop();
1279               
1280                if (node->IsLeaf())
1281                {
[1197]1282                        //Debug << "l";
[2017]1283                        ExportBinLeaf(stream, static_cast<KdLeaf *>(node));
[1196]1284                }
1285                else
1286                {
[1197]1287                        //Debug << "i";
[2017]1288                        KdInterior *interior = static_cast<KdInterior *>(node);
[1194]1289
[1196]1290                        ExportBinInterior(stream, interior);
1291                       
1292                        tStack.push(interior->mFront);
1293                        tStack.push(interior->mBack);
[1194]1294                }
1295        }
1296
1297        return true;
1298}
1299
1300
[2539]1301KdNode *KdTree::ImportNextNode(IN_STREAM &stream,
1302                                                           KdInterior *parent,
1303                                                           const ObjectContainer &objects)
[1194]1304{
[1196]1305        int nodeType;
1306        stream.read(reinterpret_cast<char *>(&nodeType), sizeof(int));
1307
1308        if (nodeType == TYPE_LEAF)
[2017]1309                return ImportBinLeaf(stream, static_cast<KdInterior *>(parent), objects);
[1196]1310
1311        if (nodeType == TYPE_INTERIOR)
[2017]1312                return ImportBinInterior(stream, static_cast<KdInterior *>(parent));
[1196]1313
1314        Debug << "error! loading failed!" << endl;
1315        return NULL;
1316}
1317
1318
[2539]1319bool KdTree::ImportBinTree(const string &filename, ObjectContainer &objects)
[1196]1320{
1321        // export binary version of mesh
[1197]1322        queue<TraversalData> tStack;
[1201]1323        IN_STREAM stream(filename.c_str(), IN_BIN_MODE);
[1197]1324
[1286]1325        if (!stream.is_open()) return false;
[1194]1326
[1414]1327        // sort objects by their id
[2539]1328//      if (!is_sorted(objects.begin(), objects.end(), ilt))
1329                sort(objects.begin(), objects.end(), ilt);
[1194]1330
[1197]1331        mBox.Initialize();
[1196]1332        ObjectContainer::const_iterator oit, oit_end = objects.end();
[1194]1333
[1414]1334        ///////////////////////////
1335        //-- compute bounding box of object space
[1633]1336
[1196]1337    for (oit = objects.begin(); oit != oit_end; ++ oit)
1338        {
[1414]1339                const AxisAlignedBox3 box = (*oit)->GetBox();
1340                mBox.Include(box);
[1196]1341        }
1342
[1414]1343        // hack: we make a new root
1344        DEL_PTR(mRoot);
[1197]1345 
[2539]1346        mRoot = ImportNextNode(stream, NULL, objects);
[1196]1347
[2332]1348        tStack.push(TraversalData(mRoot, mBox, 0));
[1196]1349        mStat.Reset();
1350        mStat.nodes = 1;
1351
[1194]1352        while(!tStack.empty())
1353        {
[1197]1354                TraversalData tData = tStack.front();
[1196]1355                tStack.pop();
[1194]1356
[1196]1357                KdNode *node = tData.mNode;
1358
1359                if (!node->IsLeaf())
[1194]1360                {
[1196]1361                        mStat.nodes += 2;
1362
[1197]1363                        //Debug << "i" ;
[2017]1364                        KdInterior *interior = static_cast<KdInterior *>(node);
[1196]1365                        interior->mBox = tData.mBox;
[1194]1366
[2539]1367            KdNode *front = ImportNextNode(stream, interior, objects);
1368                        KdNode *back = ImportNextNode(stream, interior, objects);
[1196]1369       
1370                        interior->SetupChildLinks(back, front);
1371
1372                        ++ mStat.splits[interior->mAxis];
1373
1374                        // compute new bounding box
1375                        AxisAlignedBox3 frontBox, backBox;
[1194]1376                       
[1196]1377                        tData.mBox.Split(interior->mAxis,
1378                                                         interior->mPosition,
1379                                                         frontBox,
1380                                                         backBox);
1381
1382                        tStack.push(TraversalData(front, frontBox, tData.mDepth + 1));                 
[1197]1383                        tStack.push(TraversalData(back, backBox, tData.mDepth + 1));
[1194]1384                }
[1196]1385                else
1386                {
1387                        EvaluateLeafStats(tData);
[1415]1388                        //cout << "l";
[1196]1389                }
[1194]1390        }
[1415]1391
[2524]1392        float area = GetBox().SurfaceArea()*mKdPvsArea;
[1989]1393       
1394        SetPvsTerminationNodes(area);
1395
[1196]1396        Debug << mStat << endl;
1397
[1194]1398        return true;
1399}
1400
[1999]1401
[1594]1402KdIntersectable *
1403KdTree::GetOrCreateKdIntersectable(KdNode *node)
1404{
[2116]1405        if (node == NULL)
1406                return NULL;
[1194]1407
[2116]1408        if (node->mIntersectable == NULL)
1409        {
1410                // not in map => create new entry
[2117]1411                const int id = (int)mKdIntersectables.size();
1412                KdIntersectable *kdObj = new KdIntersectable(node, GetBox(node));;
1413                node->mIntersectable = kdObj;
1414               
1415                mKdIntersectables.push_back(kdObj);
1416                kdObj->SetId(id);
1417
1418#ifdef USE_BIT_PVS
1419                // hack: for kd pvs the kd intersecables are the pvs objects
1420                ObjectPvsIterator::sObjects.push_back(kdObj);
1421#endif
[2116]1422        }
[1761]1423
[2116]1424        return node->mIntersectable;
[1387]1425}
[1594]1426
[1989]1427
1428void
1429KdTree::SetPvsTerminationNodes(
1430                                                           const float maxArea)
1431{
1432  stack<KdNode *> nodeStack;
1433 
1434  nodeStack.push(mRoot);
1435
[1995]1436  float area = 0.0f;
1437  float radius = 0.0f;
1438  int nodes = 0;
1439 
[1989]1440  while (!nodeStack.empty()) {
1441    KdNode *node = nodeStack.top();
1442        nodeStack.pop();
1443
1444        node->mPvsTermination = 0;
1445        if (node->IsLeaf() || (GetSurfaceArea(node) <= maxArea) ) {
[1995]1446          area += GetSurfaceArea(node);
1447          radius += GetBox(node).Radius();
1448          nodes++;
[1989]1449          node->mPvsTermination = 1;
1450          // create dummy kd intersectable
1451          Intersectable *object = GetOrCreateKdIntersectable(node);
1452        } else {
1453          KdInterior *interior = (KdInterior *)node;
1454          nodeStack.push(interior->mFront);
1455          nodeStack.push(interior->mBack);
1456    }
1457  }
[1995]1458
1459  if (nodes) {
1460        area /= nodes;
1461        radius /= nodes;
1462        cout<<"Number of nodes for storing in the PVS = "<<nodes<<endl;
1463        cout<<"Average rel. node area = "<<area/GetSurfaceArea(mRoot)<<endl;
1464        cout<<"Average rel. node radius = "<<radius/GetBox(mRoot).Radius()<<endl;
1465        cout<<"Avg node radius = "<<radius<<endl;
1466  }
1467 
[1989]1468}
1469
[1594]1470KdNode *
[1989]1471KdTree::GetPvsNode(const Vector3 &point) const
1472{
1473  KdNode *node = mRoot;
1474 
1475  while (node->mPvsTermination == 0 ) {
1476        KdInterior *inter = (KdInterior *)node;
1477        if (point[inter->mAxis] < inter->mPosition)
1478          node = inter->mBack;
1479        else
1480          node = inter->mFront;
1481  }
1482 
1483  return node;
1484}
1485
1486KdNode *
[1594]1487KdTree::GetNode(const Vector3 &point,
1488                                const float maxArea) const
1489{
1490  KdNode *node = mRoot;
1491 
1492  while (!node->IsLeaf() && (GetSurfaceArea(node) > maxArea) ) {
1493        KdInterior *inter = (KdInterior *)node;
1494        if (point[inter->mAxis] < inter->mPosition)
1495          node = inter->mBack;
1496        else
1497          node = inter->mFront;
1498  }
1499 
1500  return node;
1501}
1502
1503
[1999]1504void KdTree::GetBoxIntersections(const AxisAlignedBox3 &box,
1505                                                                 vector<KdLeaf *> &leaves)
1506{
1507        stack<KdNode *> tStack;
[1633]1508
[1999]1509        tStack.push(mRoot);
1510
[1633]1511        while (!tStack.empty())
1512        {
[1999]1513                KdNode *node = tStack.top();
1514                tStack.pop();
[1633]1515               
1516                if (node->IsLeaf())
1517                {
[2017]1518                        leaves.push_back(static_cast<KdLeaf *>(node));
[1633]1519                }
1520                else // interior
1521                {
[2017]1522                        KdInterior *interior = static_cast<KdInterior *>(node);
[1633]1523
[1999]1524                        if (box.Max(interior->mAxis) >= interior->mPosition)
[1633]1525                        {
[1999]1526                                tStack.push(interior->mFront);
[1633]1527                        }
1528
[1999]1529                        if (box.Min(interior->mAxis) < interior->mPosition)
1530                        {
1531                                tStack.push(interior->mBack);
1532                        }
[1633]1533                }
[1999]1534        }
[1594]1535}
[1633]1536
[1999]1537
1538
[1633]1539}
Note: See TracBrowser for help on using the repository browser.