source: trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp @ 376

Revision 376, 19.8 KB checked in by bittner, 19 years ago (diff)

vsspreprocessor kdtree meshkdtree optimization
Line 
1#include <stack>
2#include <algorithm>
3#include <queue>
4#include "Environment.h"
5#include "Mesh.h"
6#include "KdTree.h"
7
8
9int KdNode::mailID = 1;
10
11
12KdNode::KdNode(KdInterior *parent):mParent(parent), mailbox(0)
13{
14  if (parent)
15    mDepth = parent->mDepth+1;
16  else
17    mDepth = 0;
18}
19
20KdTree::KdTree()
21{
22  mRoot = new KdLeaf(NULL, 0);
23  environment->GetIntValue("KdTree.Termination.maxDepth", mTermMaxDepth);
24  environment->GetIntValue("KdTree.Termination.minCost", mTermMinCost);
25  environment->GetFloatValue("KdTree.Termination.maxCostRatio", mMaxCostRatio);
26  environment->GetFloatValue("KdTree.Termination.ct_div_ci", mCt_div_ci);
27  environment->GetFloatValue("KdTree.splitBorder", mSplitBorder);
28
29  environment->GetBoolValue("KdTree.sahUseFaces", mSahUseFaces);
30
31  char splitType[64];
32  environment->GetStringValue("KdTree.splitMethod", splitType);
33 
34  mSplitMethod = SPLIT_SPATIAL_MEDIAN;
35  if (strcmp(splitType, "spatialMedian") == 0)
36    mSplitMethod = SPLIT_SPATIAL_MEDIAN;
37  else
38    if (strcmp(splitType, "objectMedian") == 0)
39      mSplitMethod = SPLIT_OBJECT_MEDIAN;
40    else
41      if (strcmp(splitType, "SAH") == 0)
42        mSplitMethod = SPLIT_SAH;
43      else {
44        cerr<<"Wrong kd split type "<<splitType<<endl;
45        exit(1);
46      }
47  splitCandidates = NULL;
48}
49
50bool
51KdTree::Construct()
52{
53  if (!splitCandidates)
54    splitCandidates = new vector<SortableEntry>;
55
56  // first construct a leaf that will get subdivide
57  KdLeaf *leaf = (KdLeaf *) mRoot;
58
59  mStat.nodes = 1;
60
61  mBox.Initialize();
62 
63  ObjectContainer::const_iterator mi;
64  for ( mi = leaf->mObjects.begin();
65        mi != leaf->mObjects.end();
66        mi++) {
67    mBox.Include((*mi)->GetBox());
68  }
69
70  cout <<"KdTree Root Box:"<< mBox<<endl;
71  mRoot = Subdivide(TraversalData(leaf, mBox, 0));
72
73  // remove the allocated array
74  delete splitCandidates;
75
76  return true;
77}
78
79KdNode *
80KdTree::Subdivide(const TraversalData &tdata)
81{
82
83  KdNode *result = NULL;
84
85  priority_queue<TraversalData> tStack;
86  //  stack<STraversalData> tStack;
87 
88  tStack.push(tdata);
89  AxisAlignedBox3 backBox, frontBox;
90
91 
92  while (!tStack.empty()) {
93
94#if 0
95    if ( GetMemUsage() > maxMemory ) {
96      // count statistics on unprocessed leafs
97      while (!tStack.empty()) {
98        EvaluateLeafStats(tStack.top());
99        tStack.pop();
100      }
101      break;
102    }
103#endif
104
105    TraversalData data = tStack.top();
106    tStack.pop();
107   
108    KdNode *node = SubdivideNode((KdLeaf *) data.mNode,
109                                 data.mBox,
110                                 backBox,
111                                 frontBox
112                                 );
113    if (result == NULL)
114      result = node;
115   
116    if (!node->IsLeaf()) {
117
118      KdInterior *interior = (KdInterior *) node;
119      // push the children on the stack
120      tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1));
121      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1));
122     
123    } else {
124      EvaluateLeafStats(data);
125    }
126  }
127 
128  return result;
129
130}
131
132
133
134bool
135KdTree::TerminationCriteriaMet(const KdLeaf *leaf)
136{
137  //  cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
138  return
139    (leaf->mObjects.size() <= mTermMinCost) ||
140    (leaf->mDepth >= mTermMaxDepth);
141 
142}
143
144
145int
146KdTree::SelectPlane(KdLeaf *leaf,
147                    const AxisAlignedBox3 &box,
148                    float &position
149                    )
150{
151  int axis = -1;
152 
153  switch (mSplitMethod)
154    {
155    case SPLIT_SPATIAL_MEDIAN: {
156      axis = box.Size().DrivingAxis();
157      position = (box.Min()[axis] + box.Max()[axis])*0.5f;
158      break;
159    }
160    case SPLIT_SAH: {
161      int objectsBack, objectsFront;
162      float costRatio;
163      bool mOnlyDrivingAxis = false;
164      if (mOnlyDrivingAxis) {
165                                axis = box.Size().DrivingAxis();
166                                costRatio = BestCostRatio(leaf,
167                                                                                                                                        box,
168                                                                                                                                        axis,
169                                                                                                                                        position,
170                                                                                                                                        objectsBack,
171                                                                                                                                        objectsFront);
172      } else {
173                                costRatio = MAX_FLOAT;
174                                for (int i=0; i < 3; i++) {
175                                        float p;
176                                        float r = BestCostRatio(leaf,
177                                                                                                                                        box,
178                                                                                                                                        i,
179                                                                                                                                        p,
180                                                                                                                                        objectsBack,
181                                                                                                                                        objectsFront);
182                                        if (r < costRatio) {
183                                                costRatio = r;
184                                                axis = i;
185                                                position = p;
186                                        }
187                                }
188      }
189     
190      if (costRatio > mMaxCostRatio) {
191                                //      cout<<"Too big cost ratio "<<costRatio<<endl;
192                                axis = -1;
193      }
194      break;
195    }
196   
197    }
198  return axis;
199}
200
201KdNode *
202KdTree::SubdivideNode(
203                      KdLeaf *leaf,
204                      const AxisAlignedBox3 &box,
205                      AxisAlignedBox3 &backBBox,
206                      AxisAlignedBox3 &frontBBox
207                      )
208{
209 
210  if (TerminationCriteriaMet(leaf))
211    return leaf;
212 
213  float position;
214 
215  // select subdivision axis
216  int axis = SelectPlane( leaf, box, position );
217
218  if (axis == -1) {
219    return leaf;
220  }
221 
222  mStat.nodes+=2;
223  mStat.splits[axis]++;
224 
225  // add the new nodes to the tree
226  KdInterior *node = new KdInterior(leaf->mParent);
227
228  node->mAxis = axis;
229  node->mPosition = position;
230  node->mBox = box;
231 
232  backBBox = box;
233  frontBBox = box;
234 
235  // first count ray sides
236  int objectsBack = 0;
237  int objectsFront = 0;
238 
239  backBBox.SetMax(axis, position);
240  frontBBox.SetMin(axis, position);
241
242  ObjectContainer::const_iterator mi;
243
244  for ( mi = leaf->mObjects.begin();
245        mi != leaf->mObjects.end();
246        mi++) {
247    // determine the side of this ray with respect to the plane
248    AxisAlignedBox3 box = (*mi)->GetBox();
249    if (box.Max(axis) > position )
250      objectsFront++;
251   
252    if (box.Min(axis) < position )
253      objectsBack++;
254  }
255
256 
257  KdLeaf *back = new KdLeaf(node, objectsBack);
258  KdLeaf *front = new KdLeaf(node, objectsFront);
259
260  // replace a link from node's parent
261  if (  leaf->mParent )
262    leaf->mParent->ReplaceChildLink(leaf, node);
263
264  // and setup child links
265  node->SetupChildLinks(back, front);
266 
267  for (mi = leaf->mObjects.begin();
268       mi != leaf->mObjects.end();
269       mi++) {
270    // determine the side of this ray with respect to the plane
271    AxisAlignedBox3 box = (*mi)->GetBox();
272
273    if (box.Max(axis) >= position )
274      front->mObjects.push_back(*mi);
275   
276    if (box.Min(axis) < position )
277      back->mObjects.push_back(*mi);
278   
279    mStat.objectRefs -= leaf->mObjects.size();
280    mStat.objectRefs += objectsBack + objectsFront;
281  }
282 
283  delete leaf;
284  return node;
285}
286
287
288
289void
290KdTreeStatistics::Print(ostream &app) const
291{
292  app << "===== KdTree statistics ===============\n";
293
294  app << "#N_RAYS Number of rays )\n"
295      << rays <<endl;
296  app << "#N_DOMAINS  ( Number of query domains )\n"
297      << queryDomains <<endl;
298 
299  app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
300
301  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
302
303  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
304  for (int i=0; i<7; i++)
305    app << splits[i] <<" ";
306  app <<endl;
307
308  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
309    rayRefs << "\n";
310
311  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
312    rayRefs/(double)rays << "\n";
313
314  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
315    rayRefs/(double)Leaves() << "\n";
316
317  app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
318    maxObjectRefs << "\n";
319
320  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
321    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
322
323  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
324    objectRefs/(double)Leaves() << "\n";
325
326  //  app << setprecision(4);
327
328  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
329    zeroQueryNodes*100/(double)Leaves()<<endl;
330
331  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
332    maxDepthNodes*100/(double)Leaves()<<endl;
333
334  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
335    minCostNodes*100/(double)Leaves()<<endl;
336
337  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
338    addedRayRefs<<endl;
339
340  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
341    removedRayRefs<<endl;
342
343  //  app << setprecision(4);
344
345  //  app << "#N_CTIME  ( Construction time [s] )\n"
346  //      << Time() << " \n";
347
348  app << "===== END OF KdTree statistics ==========\n";
349
350}
351
352
353
354void
355KdTree::EvaluateLeafStats(const TraversalData &data)
356{
357
358  // the node became a leaf -> evaluate stats for leafs
359  KdLeaf *leaf = (KdLeaf *)data.mNode;
360
361  if (data.mDepth > mTermMaxDepth)
362    mStat.maxDepthNodes++;
363 
364  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
365    mStat.minCostNodes++;
366 
367 
368  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
369    mStat.maxObjectRefs = leaf->mObjects.size();
370 
371}
372
373
374
375void
376KdTree::SortSplitCandidates(
377                            KdLeaf *node,
378                            const int axis
379                            )
380{
381  splitCandidates->clear();
382 
383  int requestedSize = 2*node->mObjects.size();
384  // creates a sorted split candidates array
385  if (splitCandidates->capacity() > 500000 &&
386      requestedSize < (int)(splitCandidates->capacity()/10) ) {
387    delete splitCandidates;
388    splitCandidates = new vector<SortableEntry>;
389  }
390 
391  splitCandidates->reserve(requestedSize);
392 
393  // insert all queries
394  for(ObjectContainer::const_iterator mi = node->mObjects.begin();
395      mi != node->mObjects.end();
396      mi++) {
397    AxisAlignedBox3 box = (*mi)->GetBox();
398
399    splitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
400                                             box.Min(axis),
401                                             *mi)
402                               );
403   
404   
405    splitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
406                                             box.Max(axis),
407                                             *mi)
408                               );
409  }
410 
411  stable_sort(splitCandidates->begin(), splitCandidates->end());
412}
413
414
415float
416KdTree::BestCostRatio(
417                                                                                        KdLeaf *node,
418                                                                                        const AxisAlignedBox3 &box,
419                                                                                        const int axis,
420                                                                                        float &position,
421                                                                                        int &objectsBack,
422                                                                                        int &objectsFront
423                                                                                        )
424{
425
426  SortSplitCandidates(node, axis);
427 
428  // go through the lists, count the number of objects left and right
429  // and evaluate the following cost funcion:
430  // C = ct_div_ci  + (ol + or)/queries
431
432  float totalIntersections = 0.0f;
433  vector<SortableEntry>::const_iterator ci;
434
435  for(ci = splitCandidates->begin();
436      ci < splitCandidates->end();
437      ci++)
438    if ((*ci).type == SortableEntry::BOX_MIN) {
439      totalIntersections += (*ci).intersectable->IntersectionComplexity();
440    }
441       
442  float intersectionsLeft = 0;
443  float intersectionsRight = totalIntersections;
444       
445  int objectsLeft = 0, objectsRight = node->mObjects.size();
446 
447  float minBox = box.Min(axis);
448  float maxBox = box.Max(axis);
449  float boxArea = box.SurfaceArea();
450 
451  float minBand = minBox + mSplitBorder*(maxBox - minBox);
452  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
453 
454  float minSum = 1e20;
455 
456  for(ci = splitCandidates->begin();
457      ci < splitCandidates->end();
458      ci++) {
459    switch ((*ci).type) {
460    case SortableEntry::BOX_MIN:
461      objectsLeft++;
462      intersectionsLeft += (*ci).intersectable->IntersectionComplexity();
463      break;
464    case SortableEntry::BOX_MAX:
465      objectsRight--;
466      intersectionsRight -= (*ci).intersectable->IntersectionComplexity();
467      break;
468    }
469
470    if ((*ci).value > minBand && (*ci).value < maxBand) {
471      AxisAlignedBox3 lbox = box;
472      AxisAlignedBox3 rbox = box;
473      lbox.SetMax(axis, (*ci).value);
474      rbox.SetMin(axis, (*ci).value);
475
476      float sum;
477      if (mSahUseFaces)
478                                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
479      else
480                                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
481     
482      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
483      //      cout<<"cost= "<<sum<<endl;
484     
485      if (sum < minSum) {
486                                minSum = sum;
487                                position = (*ci).value;
488                               
489                                objectsBack = objectsLeft;
490                                objectsFront = objectsRight;
491      }
492    }
493  }
494 
495  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
496  float newCost = mCt_div_ci + minSum/boxArea;
497  float ratio = newCost/oldCost;
498 
499#if 0
500  cout<<"===================="<<endl;
501  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
502      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
503#endif
504  return ratio;
505}
506
507int
508KdTree::CastRay(
509                                                                Ray &ray
510                                                                )
511{
512  int hits = 0;
513 
514  stack<RayTraversalData> tStack;
515 
516  float maxt = 1e6;
517  float mint = 0;
518
519  Intersectable::NewMail();
520
521  if (!mBox.GetMinMaxT(ray, &mint, &maxt))
522    return 0;
523
524  if (mint < 0)
525    mint = 0;
526 
527  maxt += Limits::Threshold;
528 
529  Vector3 entp = ray.Extrap(mint);
530  Vector3 extp = ray.Extrap(maxt);
531 
532  KdNode *node = mRoot;
533  KdNode *farChild;
534  float position;
535  int axis;
536 
537  while (1) {
538    if (!node->IsLeaf()) {
539      KdInterior *in = (KdInterior *) node;
540      position = in->mPosition;
541      axis = in->mAxis;
542
543      if (entp[axis] <= position) {
544                                if (extp[axis] <= position) {
545                                        node = in->mBack;
546                                        // cases N1,N2,N3,P5,Z2,Z3
547                                        continue;
548                                } else {
549                                        // case N4
550                                        node = in->mBack;
551                                        farChild = in->mFront;
552                                }
553      }
554      else {
555                                if (position <= extp[axis]) {
556                                        node = in->mFront;
557                                        // cases P1,P2,P3,N5,Z1
558                                        continue;
559                                } else {
560                                        node = in->mFront;
561                                        farChild = in->mBack;
562                                        // case P4
563                                }
564                        }
565      // $$ modification 3.5.2004 - hints from Kamil Ghais
566      // case N4 or P4
567      float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
568      tStack.push(RayTraversalData(farChild, extp, maxt));
569      extp = ray.GetLoc() + ray.GetDir()*tdist;
570      maxt = tdist;
571                } else {
572                        // compute intersection with all objects in this leaf
573                        KdLeaf *leaf = (KdLeaf *) node;
574                        if (ray.mFlags & Ray::STORE_KDLEAVES)
575                                ray.kdLeaves.push_back(leaf);
576                       
577                        ObjectContainer::const_iterator mi;
578                        for ( mi = leaf->mObjects.begin();
579                                                mi != leaf->mObjects.end();
580                                                mi++) {
581                                Intersectable *object = *mi;
582                                if (!object->Mailed() ) {
583                                        object->Mail();
584                                        if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
585                                                ray.testedObjects.push_back(object);
586                                        hits += object->CastRay(ray);
587                                }
588                        }
589                       
590                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
591                                if (ray.intersections[0].mT <= maxt)
592                                        break;
593                       
594                        // get the next node from the stack
595                        if (tStack.empty())
596                                break;
597                       
598                        entp = extp;
599                        mint = maxt;
600                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
601                                break;
602                       
603                        RayTraversalData &s  = tStack.top();
604                        node = s.mNode;
605                        extp = s.mExitPoint;
606                        maxt = s.mMaxT;
607                        tStack.pop();
608                }
609  }
610  return hits;
611}
612
613void
614KdTree::CollectObjects(KdNode *n, ObjectContainer &objects)
615{
616  stack<KdNode *> nodeStack;
617
618  nodeStack.push(n);
619
620  while (!nodeStack.empty()) {
621    KdNode *node = nodeStack.top();
622    nodeStack.pop();
623    if (node->IsLeaf()) {
624      KdLeaf *leaf = (KdLeaf *)node;
625      for (int j=0; j < leaf->mObjects.size(); j++) {
626                                Intersectable *object = leaf->mObjects[j];
627                                if (!object->Mailed()) {
628                                        object->Mail();
629                                        objects.push_back(object);
630                                }
631      }
632    } else {
633      KdInterior *interior = (KdInterior *)node;
634      nodeStack.push(interior->mFront);
635      nodeStack.push(interior->mBack);
636    }
637  }
638}
639
640// Find random neighbor which was not mailed
641KdNode *
642KdTree::FindRandomNeighbor(KdNode *n,
643                                                                                                         bool onlyUnmailed
644                                                                                                         )
645{
646  stack<KdNode *> nodeStack;
647 
648  nodeStack.push(mRoot);
649
650  AxisAlignedBox3 box = GetBox(n);
651  int mask = rand();
652
653  while (!nodeStack.empty()) {
654    KdNode *node = nodeStack.top();
655    nodeStack.pop();
656    if (node->IsLeaf()) {
657      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
658        return node;
659    } else {
660      KdInterior *interior = (KdInterior *)node;
661      if (interior->mPosition > box.Max(interior->mAxis))
662        nodeStack.push(interior->mBack);
663      else
664        if (interior->mPosition < box.Min(interior->mAxis))
665          nodeStack.push(interior->mFront);
666        else {
667          // random decision
668          if (mask&1)
669            nodeStack.push(interior->mBack);
670          else
671            nodeStack.push(interior->mFront);
672          mask = mask>>1;
673        }
674    }
675  }
676 
677  return NULL;
678}
679
680int
681KdTree::FindNeighbors(KdNode *n,
682                      vector<KdNode *> &neighbors,
683                      bool onlyUnmailed
684                      )
685{
686  stack<KdNode *> nodeStack;
687 
688  nodeStack.push(mRoot);
689
690  AxisAlignedBox3 box = GetBox(n);
691
692  while (!nodeStack.empty()) {
693    KdNode *node = nodeStack.top();
694    nodeStack.pop();
695    if (node->IsLeaf()) {
696      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
697        neighbors.push_back(node);
698    } else {
699      KdInterior *interior = (KdInterior *)node;
700      if (interior->mPosition > box.Max(interior->mAxis))
701                                nodeStack.push(interior->mBack);
702      else
703                                if (interior->mPosition < box.Min(interior->mAxis))
704                                        nodeStack.push(interior->mFront);
705                                else {
706                                        // random decision
707                                        nodeStack.push(interior->mBack);
708                                        nodeStack.push(interior->mFront);
709                                }
710    }
711  }
712 
713  return neighbors.size();
714}
715
716// Find random neighbor which was not mailed
717KdNode *
718KdTree::GetRandomLeaf(const Plane3 &plane)
719{
720  stack<KdNode *> nodeStack;
721 
722  nodeStack.push(mRoot);
723 
724  int mask = rand();
725 
726  while (!nodeStack.empty()) {
727    KdNode *node = nodeStack.top();
728    nodeStack.pop();
729    if (node->IsLeaf()) {
730      return node;
731    } else {
732      KdInterior *interior = (KdInterior *)node;
733      KdNode *next;
734        if (GetBox(interior->mBack).Side(plane) < 0)
735          next = interior->mFront;
736        else
737          if (GetBox(interior->mFront).Side(plane) < 0)
738            next = interior->mBack;
739          else {
740            // random decision
741            if (mask&1)
742              next = interior->mBack;
743            else
744              next = interior->mFront;
745            mask = mask>>1;
746          }
747        nodeStack.push(next);
748    }
749  }
750 
751 
752  return NULL;
753}
754
755void
756KdTree::CollectLeaves(vector<KdLeaf *> &leaves)
757{
758  stack<KdNode *> nodeStack;
759  nodeStack.push(mRoot);
760
761  while (!nodeStack.empty()) {
762    KdNode *node = nodeStack.top();
763    nodeStack.pop();
764    if (node->IsLeaf()) {
765      KdLeaf *leaf = (KdLeaf *)node;
766      leaves.push_back(leaf);
767    } else {
768      KdInterior *interior = (KdInterior *)node;
769      nodeStack.push(interior->mBack);
770      nodeStack.push(interior->mFront);
771    }
772  }
773}
774
775
776int
777KdTree::CollectLeafPvs()
778{
779  int totalPvsSize = 0;
780  stack<KdNode *> nodeStack;
781 
782  nodeStack.push(mRoot);
783 
784  while (!nodeStack.empty()) {
785    KdNode *node = nodeStack.top();
786    nodeStack.pop();
787    if (node->IsLeaf()) {
788      KdLeaf *leaf = (KdLeaf *)node;
789      for (int j=0; j < leaf->mObjects.size(); j++) {
790        Intersectable *object = leaf->mObjects[j];
791        if (!object->Mailed()) {
792          object->Mail();
793          // add this node to pvs of all nodes it can see
794          KdPvsMap::iterator ni = object->mKdPvs.mEntries.begin();
795          for (; ni != object->mKdPvs.mEntries.end(); ni++) {
796            KdNode *node = (*ni).first;
797            // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
798            // kd tree PVS
799            if (leaf->mKdPvs.AddSample(node))
800              totalPvsSize++;
801          }
802        }
803      }
804    } else {
805      KdInterior *interior = (KdInterior *)node;
806      nodeStack.push(interior->mFront);
807      nodeStack.push(interior->mBack);
808    }
809  }
810
811  return totalPvsSize;
812}
813
814
815KdNode *
816KdTree::GetRandomLeaf(const bool onlyUnmailed)
817{
818        stack<KdNode *> nodeStack;
819  nodeStack.push(mRoot);
820
821        int mask = rand();
822       
823  while (!nodeStack.empty()) {
824    KdNode *node = nodeStack.top();
825    nodeStack.pop();
826    if (node->IsLeaf()) {
827      if ( (!onlyUnmailed || !node->Mailed()) )
828                                return node;
829    } else {
830      KdInterior *interior = (KdInterior *)node;
831                        // random decision
832                        if (mask&1)
833                                nodeStack.push(interior->mBack);
834                        else
835                                nodeStack.push(interior->mFront);
836                        mask = mask>>1;
837                }
838        }
839  return NULL;
840}
Note: See TracBrowser for help on using the repository browser.