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

Revision 492, 22.3 KB checked in by bittner, 19 years ago (diff)

Large merge - viewcells seem not functional now
Line 
1#include <stack>
2#include <algorithm>
3#include <queue>
4#include "Environment.h"
5#include "Mesh.h"
6#include "KdTree.h"
7#include "ViewCell.h"
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 -= (int)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 = (int)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*(int)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 = (int)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 = 1e20f;
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
608int KdTree::CastLineSegment(const Vector3 &origin,
609                                                        const Vector3 &termination,
610                                                        vector<ViewCell *> &viewcells)
611{
612        int hits = 0;
613
614        float mint = 0.0f, maxt = 1.0f;
615        const Vector3 dir = termination - origin;
616
617        stack<RayTraversalData> tStack;
618
619        Intersectable::NewMail();
620
621        //maxt += Limits::Threshold;
622
623        Vector3 entp = origin;
624        Vector3 extp = termination;
625
626        KdNode *node = mRoot;
627        KdNode *farChild;
628
629        float position;
630        int axis;
631
632        while (1)
633        {
634                if (!node->IsLeaf())
635                {
636                        KdInterior *in = dynamic_cast<KdInterior *>(node);
637                        position = in->mPosition;
638                        axis = in->mAxis;
639
640                        if (entp[axis] <= position)
641                        {
642                                if (extp[axis] <= position)
643                                {
644                                        node = in->mBack;
645                                        // cases N1,N2,N3,P5,Z2,Z3
646                                        continue;
647                                }
648                                else
649                                {
650                                        // case N4
651                                        node = in->mBack;
652                                        farChild = in->mFront;
653                                }
654                        }
655                        else
656                        {
657                                if (position <= extp[axis])
658                                {
659                                        node = in->mFront;
660                                        // cases P1,P2,P3,N5,Z1
661                                        continue;
662                                }
663                                else
664                                {
665                                        node = in->mFront;
666                                        farChild = in->mBack;
667                                        // case P4
668                                }
669                        }
670
671                        // $$ modification 3.5.2004 - hints from Kamil Ghais
672                        // case N4 or P4
673                        float tdist = (position - origin[axis]) / dir[axis];
674                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
675                        extp = origin + dir * tdist;
676                        maxt = tdist;
677                }
678                else
679                {
680                        // compute intersection with all objects in this leaf
681                        KdLeaf *leaf = dynamic_cast<KdLeaf *>(node);
682
683                        // add view cell to intersections
684                        ViewCell *vc = leaf->mViewCell;
685
686                        if (!vc->Mailed())
687                        {
688                                vc->Mail();
689                                viewcells.push_back(vc);
690                                ++ hits;
691                        }
692
693                        // get the next node from the stack
694                        if (tStack.empty())
695                                break;
696
697                        entp = extp;
698                        mint = maxt;
699                       
700                        RayTraversalData &s  = tStack.top();
701                        node = s.mNode;
702                        extp = s.mExitPoint;
703                        maxt = s.mMaxT;
704                        tStack.pop();
705                }
706        }
707
708        return hits;
709}
710
711
712void
713KdTree::CollectObjects(KdNode *n, ObjectContainer &objects)
714{
715  stack<KdNode *> nodeStack;
716
717  nodeStack.push(n);
718
719  while (!nodeStack.empty()) {
720    KdNode *node = nodeStack.top();
721    nodeStack.pop();
722    if (node->IsLeaf()) {
723      KdLeaf *leaf = (KdLeaf *)node;
724      for (int j=0; j < leaf->mObjects.size(); j++) {
725                                Intersectable *object = leaf->mObjects[j];
726                                if (!object->Mailed()) {
727                                        object->Mail();
728                                        objects.push_back(object);
729                                }
730      }
731    } else {
732      KdInterior *interior = (KdInterior *)node;
733      nodeStack.push(interior->mFront);
734      nodeStack.push(interior->mBack);
735    }
736  }
737}
738
739// Find random neighbor which was not mailed
740KdNode *
741KdTree::FindRandomNeighbor(KdNode *n,
742                                                                                                         bool onlyUnmailed
743                                                                                                         )
744{
745  stack<KdNode *> nodeStack;
746 
747  nodeStack.push(mRoot);
748
749  AxisAlignedBox3 box = GetBox(n);
750  int mask = rand();
751
752  while (!nodeStack.empty()) {
753    KdNode *node = nodeStack.top();
754    nodeStack.pop();
755    if (node->IsLeaf()) {
756      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
757        return node;
758    } else {
759      KdInterior *interior = (KdInterior *)node;
760      if (interior->mPosition > box.Max(interior->mAxis))
761        nodeStack.push(interior->mBack);
762      else
763        if (interior->mPosition < box.Min(interior->mAxis))
764          nodeStack.push(interior->mFront);
765        else {
766          // random decision
767          if (mask&1)
768            nodeStack.push(interior->mBack);
769          else
770            nodeStack.push(interior->mFront);
771          mask = mask>>1;
772        }
773    }
774  }
775 
776  return NULL;
777}
778
779int
780KdTree::FindNeighbors(KdNode *n,
781                      vector<KdNode *> &neighbors,
782                      bool onlyUnmailed
783                      )
784{
785  stack<KdNode *> nodeStack;
786 
787  nodeStack.push(mRoot);
788
789  AxisAlignedBox3 box = GetBox(n);
790
791  while (!nodeStack.empty()) {
792    KdNode *node = nodeStack.top();
793    nodeStack.pop();
794    if (node->IsLeaf()) {
795      if ( node != n && (!onlyUnmailed || !node->Mailed()) )
796        neighbors.push_back(node);
797    } else {
798      KdInterior *interior = (KdInterior *)node;
799      if (interior->mPosition > box.Max(interior->mAxis))
800                                nodeStack.push(interior->mBack);
801      else
802                                if (interior->mPosition < box.Min(interior->mAxis))
803                                        nodeStack.push(interior->mFront);
804                                else {
805                                        // random decision
806                                        nodeStack.push(interior->mBack);
807                                        nodeStack.push(interior->mFront);
808                                }
809    }
810  }
811 
812  return (int)neighbors.size();
813}
814
815// Find random neighbor which was not mailed
816KdNode *
817KdTree::GetRandomLeaf(const Plane3 &plane)
818{
819  stack<KdNode *> nodeStack;
820 
821  nodeStack.push(mRoot);
822 
823  int mask = rand();
824 
825  while (!nodeStack.empty()) {
826    KdNode *node = nodeStack.top();
827    nodeStack.pop();
828    if (node->IsLeaf()) {
829      return node;
830    } else {
831      KdInterior *interior = (KdInterior *)node;
832      KdNode *next;
833        if (GetBox(interior->mBack).Side(plane) < 0)
834          next = interior->mFront;
835        else
836          if (GetBox(interior->mFront).Side(plane) < 0)
837            next = interior->mBack;
838          else {
839            // random decision
840            if (mask&1)
841              next = interior->mBack;
842            else
843              next = interior->mFront;
844            mask = mask>>1;
845          }
846        nodeStack.push(next);
847    }
848  }
849 
850 
851  return NULL;
852}
853
854void
855KdTree::CollectLeaves(vector<KdLeaf *> &leaves)
856{
857  stack<KdNode *> nodeStack;
858  nodeStack.push(mRoot);
859
860  while (!nodeStack.empty()) {
861    KdNode *node = nodeStack.top();
862    nodeStack.pop();
863    if (node->IsLeaf()) {
864      KdLeaf *leaf = (KdLeaf *)node;
865      leaves.push_back(leaf);
866    } else {
867      KdInterior *interior = (KdInterior *)node;
868      nodeStack.push(interior->mBack);
869      nodeStack.push(interior->mFront);
870    }
871  }
872}
873
874void
875KdTree::CreateAndCollectViewCells(ViewCellContainer &vc) const
876{
877  stack<KdNode *> nodeStack;
878  nodeStack.push(mRoot);
879
880  while (!nodeStack.empty()) {
881    KdNode *node = nodeStack.top();
882    nodeStack.pop();
883    if (node->IsLeaf()) {
884      KdLeaf *leaf = (KdLeaf *)node;
885          // kdtree used as view cell container => create view cell
886          KdViewCell *viewCell = new KdViewCell();
887          leaf->mViewCell = viewCell;
888          // push back pointer to this leaf
889          viewCell->mLeaves.push_back(leaf);
890      vc.push_back(viewCell);
891    } else {
892      KdInterior *interior = (KdInterior *)node;
893      nodeStack.push(interior->mBack);
894      nodeStack.push(interior->mFront);
895    }
896  }
897}
898
899int
900KdTree::CollectLeafPvs()
901{
902  int totalPvsSize = 0;
903  stack<KdNode *> nodeStack;
904 
905  nodeStack.push(mRoot);
906 
907  while (!nodeStack.empty()) {
908    KdNode *node = nodeStack.top();
909    nodeStack.pop();
910    if (node->IsLeaf()) {
911      KdLeaf *leaf = (KdLeaf *)node;
912      for (int j=0; j < leaf->mObjects.size(); j++) {
913        Intersectable *object = leaf->mObjects[j];
914        if (!object->Mailed()) {
915          object->Mail();
916          // add this node to pvs of all nodes it can see
917          KdPvsMap::iterator ni = object->mKdPvs.mEntries.begin();
918          for (; ni != object->mKdPvs.mEntries.end(); ni++) {
919            KdNode *node = (*ni).first;
920            // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
921            // kd tree PVS
922                float contribution;
923                if (leaf->mKdPvs.AddSample(node, contribution))
924              totalPvsSize++;
925          }
926        }
927      }
928    } else {
929      KdInterior *interior = (KdInterior *)node;
930      nodeStack.push(interior->mFront);
931      nodeStack.push(interior->mBack);
932    }
933  }
934
935  return totalPvsSize;
936}
937
938
939KdNode *
940KdTree::GetRandomLeaf(const bool onlyUnmailed)
941{
942        stack<KdNode *> nodeStack;
943  nodeStack.push(mRoot);
944
945        int mask = rand();
946       
947  while (!nodeStack.empty()) {
948    KdNode *node = nodeStack.top();
949    nodeStack.pop();
950    if (node->IsLeaf()) {
951      if ( (!onlyUnmailed || !node->Mailed()) )
952                                return node;
953    } else {
954      KdInterior *interior = (KdInterior *)node;
955                        // random decision
956                        if (mask&1)
957                                nodeStack.push(interior->mBack);
958                        else
959                                nodeStack.push(interior->mFront);
960                        mask = mask>>1;
961                }
962        }
963  return NULL;
964}
Note: See TracBrowser for help on using the repository browser.