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

Revision 403, 19.7 KB checked in by bittner, 19 years ago (diff)

vvs preprocessor update
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_NODES ( Number of nodes )\n" << nodes << "\n";
295
296  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
297
298  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
299  for (int i=0; i<7; i++)
300    app << splits[i] <<" ";
301  app <<endl;
302
303  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
304    rayRefs << "\n";
305
306  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
307    rayRefs/(double)rays << "\n";
308
309  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
310    rayRefs/(double)Leaves() << "\n";
311
312  app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
313    maxObjectRefs << "\n";
314
315  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
316    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
317
318  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
319    objectRefs/(double)Leaves() << "\n";
320
321  //  app << setprecision(4);
322
323  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
324    zeroQueryNodes*100/(double)Leaves()<<endl;
325
326  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
327    maxDepthNodes*100/(double)Leaves()<<endl;
328
329  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
330    minCostNodes*100/(double)Leaves()<<endl;
331
332  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
333    addedRayRefs<<endl;
334
335  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
336    removedRayRefs<<endl;
337
338  //  app << setprecision(4);
339
340  //  app << "#N_CTIME  ( Construction time [s] )\n"
341  //      << Time() << " \n";
342
343  app << "===== END OF KdTree statistics ==========\n";
344
345}
346
347
348
349void
350KdTree::EvaluateLeafStats(const TraversalData &data)
351{
352
353  // the node became a leaf -> evaluate stats for leafs
354  KdLeaf *leaf = (KdLeaf *)data.mNode;
355
356  if (data.mDepth > mTermMaxDepth)
357    mStat.maxDepthNodes++;
358 
359  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
360    mStat.minCostNodes++;
361 
362 
363  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
364    mStat.maxObjectRefs = leaf->mObjects.size();
365 
366}
367
368
369
370void
371KdTree::SortSplitCandidates(
372                            KdLeaf *node,
373                            const int axis
374                            )
375{
376  splitCandidates->clear();
377 
378  int requestedSize = 2*node->mObjects.size();
379  // creates a sorted split candidates array
380  if (splitCandidates->capacity() > 500000 &&
381      requestedSize < (int)(splitCandidates->capacity()/10) ) {
382    delete splitCandidates;
383    splitCandidates = new vector<SortableEntry>;
384  }
385 
386  splitCandidates->reserve(requestedSize);
387 
388  // insert all queries
389  for(ObjectContainer::const_iterator mi = node->mObjects.begin();
390      mi != node->mObjects.end();
391      mi++) {
392    AxisAlignedBox3 box = (*mi)->GetBox();
393
394    splitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
395                                             box.Min(axis),
396                                             *mi)
397                               );
398   
399   
400    splitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
401                                             box.Max(axis),
402                                             *mi)
403                               );
404  }
405 
406  stable_sort(splitCandidates->begin(), splitCandidates->end());
407}
408
409
410float
411KdTree::BestCostRatio(
412                                                                                        KdLeaf *node,
413                                                                                        const AxisAlignedBox3 &box,
414                                                                                        const int axis,
415                                                                                        float &position,
416                                                                                        int &objectsBack,
417                                                                                        int &objectsFront
418                                                                                        )
419{
420
421  SortSplitCandidates(node, axis);
422 
423  // go through the lists, count the number of objects left and right
424  // and evaluate the following cost funcion:
425  // C = ct_div_ci  + (ol + or)/queries
426
427  float totalIntersections = 0.0f;
428  vector<SortableEntry>::const_iterator ci;
429
430  for(ci = splitCandidates->begin();
431      ci < splitCandidates->end();
432      ci++)
433    if ((*ci).type == SortableEntry::BOX_MIN) {
434      totalIntersections += (*ci).intersectable->IntersectionComplexity();
435    }
436       
437  float intersectionsLeft = 0;
438  float intersectionsRight = totalIntersections;
439       
440  int objectsLeft = 0, objectsRight = node->mObjects.size();
441 
442  float minBox = box.Min(axis);
443  float maxBox = box.Max(axis);
444  float boxArea = box.SurfaceArea();
445 
446  float minBand = minBox + mSplitBorder*(maxBox - minBox);
447  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
448 
449  float minSum = 1e20;
450 
451  for(ci = splitCandidates->begin();
452      ci < splitCandidates->end();
453      ci++) {
454    switch ((*ci).type) {
455    case SortableEntry::BOX_MIN:
456      objectsLeft++;
457      intersectionsLeft += (*ci).intersectable->IntersectionComplexity();
458      break;
459    case SortableEntry::BOX_MAX:
460      objectsRight--;
461      intersectionsRight -= (*ci).intersectable->IntersectionComplexity();
462      break;
463    }
464
465    if ((*ci).value > minBand && (*ci).value < maxBand) {
466      AxisAlignedBox3 lbox = box;
467      AxisAlignedBox3 rbox = box;
468      lbox.SetMax(axis, (*ci).value);
469      rbox.SetMin(axis, (*ci).value);
470
471      float sum;
472      if (mSahUseFaces)
473                                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
474      else
475                                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
476     
477      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
478      //      cout<<"cost= "<<sum<<endl;
479     
480      if (sum < minSum) {
481                                minSum = sum;
482                                position = (*ci).value;
483                               
484                                objectsBack = objectsLeft;
485                                objectsFront = objectsRight;
486      }
487    }
488  }
489 
490  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
491  float newCost = mCt_div_ci + minSum/boxArea;
492  float ratio = newCost/oldCost;
493 
494#if 0
495  cout<<"===================="<<endl;
496  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
497      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
498#endif
499  return ratio;
500}
501
502int
503KdTree::CastRay(
504                                                                Ray &ray
505                                                                )
506{
507  int hits = 0;
508 
509  stack<RayTraversalData> tStack;
510 
511  float maxt = 1e6;
512  float mint = 0;
513
514  Intersectable::NewMail();
515
516  if (!mBox.GetMinMaxT(ray, &mint, &maxt))
517    return 0;
518
519  if (mint < 0)
520    mint = 0;
521 
522  maxt += Limits::Threshold;
523 
524  Vector3 entp = ray.Extrap(mint);
525  Vector3 extp = ray.Extrap(maxt);
526 
527  KdNode *node = mRoot;
528  KdNode *farChild;
529  float position;
530  int axis;
531 
532  while (1) {
533    if (!node->IsLeaf()) {
534      KdInterior *in = (KdInterior *) node;
535      position = in->mPosition;
536      axis = in->mAxis;
537
538      if (entp[axis] <= position) {
539                                if (extp[axis] <= position) {
540                                        node = in->mBack;
541                                        // cases N1,N2,N3,P5,Z2,Z3
542                                        continue;
543                                } else {
544                                        // case N4
545                                        node = in->mBack;
546                                        farChild = in->mFront;
547                                }
548      }
549      else {
550                                if (position <= extp[axis]) {
551                                        node = in->mFront;
552                                        // cases P1,P2,P3,N5,Z1
553                                        continue;
554                                } else {
555                                        node = in->mFront;
556                                        farChild = in->mBack;
557                                        // case P4
558                                }
559                        }
560      // $$ modification 3.5.2004 - hints from Kamil Ghais
561      // case N4 or P4
562      float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
563      tStack.push(RayTraversalData(farChild, extp, maxt));
564      extp = ray.GetLoc() + ray.GetDir()*tdist;
565      maxt = tdist;
566                } else {
567                        // compute intersection with all objects in this leaf
568                        KdLeaf *leaf = (KdLeaf *) node;
569                        if (ray.mFlags & Ray::STORE_KDLEAVES)
570                                ray.kdLeaves.push_back(leaf);
571                       
572                        ObjectContainer::const_iterator mi;
573                        for ( mi = leaf->mObjects.begin();
574                                                mi != leaf->mObjects.end();
575                                                mi++) {
576                                Intersectable *object = *mi;
577                                if (!object->Mailed() ) {
578                                        object->Mail();
579                                        if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
580                                                ray.testedObjects.push_back(object);
581                                        hits += object->CastRay(ray);
582                                }
583                        }
584                       
585                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
586                                if (ray.intersections[0].mT <= maxt)
587                                        break;
588                       
589                        // get the next node from the stack
590                        if (tStack.empty())
591                                break;
592                       
593                        entp = extp;
594                        mint = maxt;
595                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
596                                break;
597                       
598                        RayTraversalData &s  = tStack.top();
599                        node = s.mNode;
600                        extp = s.mExitPoint;
601                        maxt = s.mMaxT;
602                        tStack.pop();
603                }
604  }
605  return hits;
606}
607
608void
609KdTree::CollectObjects(KdNode *n, ObjectContainer &objects)
610{
611  stack<KdNode *> nodeStack;
612
613  nodeStack.push(n);
614
615  while (!nodeStack.empty()) {
616    KdNode *node = nodeStack.top();
617    nodeStack.pop();
618    if (node->IsLeaf()) {
619      KdLeaf *leaf = (KdLeaf *)node;
620      for (int j=0; j < leaf->mObjects.size(); j++) {
621                                Intersectable *object = leaf->mObjects[j];
622                                if (!object->Mailed()) {
623                                        object->Mail();
624                                        objects.push_back(object);
625                                }
626      }
627    } else {
628      KdInterior *interior = (KdInterior *)node;
629      nodeStack.push(interior->mFront);
630      nodeStack.push(interior->mBack);
631    }
632  }
633}
634
635// Find random neighbor which was not mailed
636KdNode *
637KdTree::FindRandomNeighbor(KdNode *n,
638                                                                                                         bool onlyUnmailed
639                                                                                                         )
640{
641  stack<KdNode *> nodeStack;
642 
643  nodeStack.push(mRoot);
644
645  AxisAlignedBox3 box = GetBox(n);
646  int mask = rand();
647
648  while (!nodeStack.empty()) {
649    KdNode *node = nodeStack.top();
650    nodeStack.pop();
651    if (node->IsLeaf()) {
652      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
653        return node;
654    } else {
655      KdInterior *interior = (KdInterior *)node;
656      if (interior->mPosition > box.Max(interior->mAxis))
657        nodeStack.push(interior->mBack);
658      else
659        if (interior->mPosition < box.Min(interior->mAxis))
660          nodeStack.push(interior->mFront);
661        else {
662          // random decision
663          if (mask&1)
664            nodeStack.push(interior->mBack);
665          else
666            nodeStack.push(interior->mFront);
667          mask = mask>>1;
668        }
669    }
670  }
671 
672  return NULL;
673}
674
675int
676KdTree::FindNeighbors(KdNode *n,
677                      vector<KdNode *> &neighbors,
678                      bool onlyUnmailed
679                      )
680{
681  stack<KdNode *> nodeStack;
682 
683  nodeStack.push(mRoot);
684
685  AxisAlignedBox3 box = GetBox(n);
686
687  while (!nodeStack.empty()) {
688    KdNode *node = nodeStack.top();
689    nodeStack.pop();
690    if (node->IsLeaf()) {
691      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
692        neighbors.push_back(node);
693    } else {
694      KdInterior *interior = (KdInterior *)node;
695      if (interior->mPosition > box.Max(interior->mAxis))
696                                nodeStack.push(interior->mBack);
697      else
698                                if (interior->mPosition < box.Min(interior->mAxis))
699                                        nodeStack.push(interior->mFront);
700                                else {
701                                        // random decision
702                                        nodeStack.push(interior->mBack);
703                                        nodeStack.push(interior->mFront);
704                                }
705    }
706  }
707 
708  return neighbors.size();
709}
710
711// Find random neighbor which was not mailed
712KdNode *
713KdTree::GetRandomLeaf(const Plane3 &plane)
714{
715  stack<KdNode *> nodeStack;
716 
717  nodeStack.push(mRoot);
718 
719  int mask = rand();
720 
721  while (!nodeStack.empty()) {
722    KdNode *node = nodeStack.top();
723    nodeStack.pop();
724    if (node->IsLeaf()) {
725      return node;
726    } else {
727      KdInterior *interior = (KdInterior *)node;
728      KdNode *next;
729        if (GetBox(interior->mBack).Side(plane) < 0)
730          next = interior->mFront;
731        else
732          if (GetBox(interior->mFront).Side(plane) < 0)
733            next = interior->mBack;
734          else {
735            // random decision
736            if (mask&1)
737              next = interior->mBack;
738            else
739              next = interior->mFront;
740            mask = mask>>1;
741          }
742        nodeStack.push(next);
743    }
744  }
745 
746 
747  return NULL;
748}
749
750void
751KdTree::CollectLeaves(vector<KdLeaf *> &leaves)
752{
753  stack<KdNode *> nodeStack;
754  nodeStack.push(mRoot);
755
756  while (!nodeStack.empty()) {
757    KdNode *node = nodeStack.top();
758    nodeStack.pop();
759    if (node->IsLeaf()) {
760      KdLeaf *leaf = (KdLeaf *)node;
761      leaves.push_back(leaf);
762    } else {
763      KdInterior *interior = (KdInterior *)node;
764      nodeStack.push(interior->mBack);
765      nodeStack.push(interior->mFront);
766    }
767  }
768}
769
770
771int
772KdTree::CollectLeafPvs()
773{
774  int totalPvsSize = 0;
775  stack<KdNode *> nodeStack;
776 
777  nodeStack.push(mRoot);
778 
779  while (!nodeStack.empty()) {
780    KdNode *node = nodeStack.top();
781    nodeStack.pop();
782    if (node->IsLeaf()) {
783      KdLeaf *leaf = (KdLeaf *)node;
784      for (int j=0; j < leaf->mObjects.size(); j++) {
785        Intersectable *object = leaf->mObjects[j];
786        if (!object->Mailed()) {
787          object->Mail();
788          // add this node to pvs of all nodes it can see
789          KdPvsMap::iterator ni = object->mKdPvs.mEntries.begin();
790          for (; ni != object->mKdPvs.mEntries.end(); ni++) {
791            KdNode *node = (*ni).first;
792            // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
793            // kd tree PVS
794            if (leaf->mKdPvs.AddSample(node))
795              totalPvsSize++;
796          }
797        }
798      }
799    } else {
800      KdInterior *interior = (KdInterior *)node;
801      nodeStack.push(interior->mFront);
802      nodeStack.push(interior->mBack);
803    }
804  }
805
806  return totalPvsSize;
807}
808
809
810KdNode *
811KdTree::GetRandomLeaf(const bool onlyUnmailed)
812{
813        stack<KdNode *> nodeStack;
814  nodeStack.push(mRoot);
815
816        int mask = rand();
817       
818  while (!nodeStack.empty()) {
819    KdNode *node = nodeStack.top();
820    nodeStack.pop();
821    if (node->IsLeaf()) {
822      if ( (!onlyUnmailed || !node->Mailed()) )
823                                return node;
824    } else {
825      KdInterior *interior = (KdInterior *)node;
826                        // random decision
827                        if (mask&1)
828                                nodeStack.push(interior->mBack);
829                        else
830                                nodeStack.push(interior->mFront);
831                        mask = mask>>1;
832                }
833        }
834  return NULL;
835}
Note: See TracBrowser for help on using the repository browser.