source: GTP/trunk/Lib/Vis/Preprocessing/src/RssTree.h @ 1112

Revision 1112, 22.2 KB checked in by bittner, 18 years ago (diff)

Merge with Olivers code
Line 
1// ================================================================
2// $Id$
3// ****************************************************************
4//
5// Initial coding by
6/**
7   @author Jiri Bittner
8*/
9
10#ifndef __RSSTREE_H__
11#define __RSSTREE_H__
12
13// Standard headers
14#include <iomanip>
15#include <vector>
16#include <functional>
17#include <stack>
18
19
20// User headers
21#include "VssRay.h"
22#include "AxisAlignedBox3.h"
23#include "Halton.h"
24#include "Beam.h"
25#include "Statistics.h"
26#include "Ray.h"
27
28#include "Containers.h"
29
30namespace GtpVisibilityPreprocessor {
31
32#define USE_KDNODE_VECTORS 1
33#define _RSS_STATISTICS
34#define _RSS_TRAVERSAL_STATISTICS
35
36
37// --------------------------------------------------------------
38// Static statistics for kd-tree search
39// --------------------------------------------------------------
40class RssStatistics :
41  public StatisticsBase
42{
43public: 
44  // total number of nodes
45  int nodes;
46  // number of leaves
47  int leaves;
48  // number of splits along each of the axes
49  int splits[7];
50  // totals number of rays
51  int rays;
52  // initial size of the pvs
53  int initialPvsSize;
54  // total number of query domains
55  int queryDomains;
56  // total number of ray references
57  int rayRefs;
58
59  // max depth nodes
60  int maxDepthNodes;
61  // max depth nodes
62  int minPvsNodes;
63  int minRaysNodes;
64  // max ray contribution nodes
65  int maxRayContribNodes;
66  // max depth nodes
67  int minSizeNodes;
68  int maxCostRatioNodes;
69
70  // max number of rays per node
71  int maxRayRefs;
72  // number of dynamically added ray refs
73  int addedRayRefs;
74  // number of dynamically removed ray refs
75  int removedRayRefs;
76
77
78
79  // dynamically updated values
80  float avgPvsSize;
81  float avgRays;
82  float avgRayContribution;
83  float avgPvsEntropy;
84  float avgRayLengthEntropy;
85  float avgImportance;
86
87  float avgWeightedRayContribution;
88
89  // Constructor
90  RssStatistics() {
91    Reset();
92  }
93
94  int Nodes() const {return nodes;}
95  int Interior() const { return nodes/2; }
96  int Leaves() const { return Nodes() - Interior(); }
97
98  void Reset() {
99    nodes = 0;
100    for (int i=0; i<7; i++)
101      splits[i] = 0;
102    rays = queryDomains = 0;
103    rayRefs = 0;
104    maxDepthNodes = 0;
105    minPvsNodes = 0;
106    minRaysNodes = 0;
107    maxRayRefs = 0;
108    addedRayRefs = removedRayRefs = 0;
109        initialPvsSize = 0;
110        maxRayContribNodes = 0;
111        minSizeNodes = 0;
112        maxCostRatioNodes = 0;
113  }
114
115 
116  void
117  Print(ostream &app) const;
118
119  friend ostream &operator<<(ostream &s, const RssStatistics &stat) {
120    stat.Print(s);
121    return s;
122  }
123 
124};
125
126
127
128
129class RssTreeInterior;
130
131
132// --------------------------------------------------------------
133// KD-tree node - abstract class
134// --------------------------------------------------------------
135class RssTreeNode
136{
137public:
138
139  struct RayInfo
140  {
141        // pointer to the actual ray
142        VssRay *mRay;
143       
144        RayInfo():mRay(NULL) {}
145       
146        RayInfo(VssRay *r):mRay(r)
147        {}
148       
149        enum {
150          SOURCE_RAY = 0,
151          TERMINATION_RAY,
152          PASSING_RAY,
153          CONTAINED_RAY
154        };
155       
156        int GetRayClass() const {
157          return SOURCE_RAY;
158        }
159       
160        friend bool operator<(const RayInfo &a, const RayInfo &b) {
161          return a.mRay < b.mRay;
162        }
163
164#define USE_ORIGIN 1
165       
166        Vector3 GetOrigin() const {
167#if USE_ORIGIN
168          return mRay->GetOrigin();
169#else
170          return mRay->GetTermination();
171#endif
172        }
173
174        Vector3 GetTermination() const {
175#if USE_ORIGIN
176          return mRay->GetTermination();
177#else
178          return mRay->GetOrigin();
179#endif
180        }
181
182        float GetOrigin(const int axis) const {
183#if USE_ORIGIN
184          return mRay->GetOrigin(axis);
185#else
186          return mRay->GetTermination(axis);
187#endif
188        }
189
190        Vector3 GetDir() const {
191#if USE_ORIGIN
192          return mRay->GetDir();
193#else
194          return -mRay->GetDir();
195#endif
196        }
197
198        float GetDirParametrization(const int axis) const {
199#if USE_ORIGIN
200          return mRay->GetDirParametrization(axis);
201#else
202          return mRay->GetOpositeDirParametrization(axis);
203#endif
204        }
205
206       
207//      Vector3 GetTermination() const {
208//        return mRay->GetOrigin();
209//      }
210       
211//      float GetTermination(const int axis) const {
212//        return mRay->GetTermination(axis);
213//      }
214
215        Intersectable *GetObject() const {
216#if USE_ORIGIN
217          return mRay->mTerminationObject;
218#else
219          return mRay->mOriginObject;
220#endif
221        }
222       
223        Intersectable *GetSourceObject() const {
224#if USE_ORIGIN
225          return mRay->mOriginObject;
226#else
227          return mRay->mTerminationObject;
228#endif
229        }
230
231        //      Vector3 Extrap(const float t) const {
232        //        return mRay->Extrap(t);
233        //      }
234       
235        int
236        ComputeRaySide(const int axis,
237                                   const float position
238                                   ) const {
239         
240          // only compare the side of the origin
241          float rpos = (axis < 3) ? GetOrigin(axis) : GetDirParametrization(axis - 3);
242          return (rpos <= position) ? -1 : 1;
243        }
244
245        static bool GreaterWeightedPvsContribution(const RayInfo &a,
246                                                                                           const RayInfo &b) {
247          return a.mRay->mWeightedPvsContribution > b.mRay->mWeightedPvsContribution;
248        }
249
250        static float Distance(const RayInfo &a,
251                                                 const RayInfo &b)
252        {
253          if (a.mRay->mTerminationObject == b.mRay->mTerminationObject)
254                return MAX_FLOAT;
255         
256          return Min(a.mRay->SqrDistance(b.GetTermination()),
257                                 b.mRay->SqrDistance(a.GetTermination()));
258        }
259
260       
261        static float SqrDistance5D(const RayInfo &a,
262                                                           const RayInfo &b,
263                                                           const Vector3 &spatialDerivative,
264                                                           const Vector3 &directionalDerivative
265                                                           )
266        {
267          Vector3 spatialDiff = b.GetOrigin() - a.GetOrigin();
268          Vector3 directionalDiff = b.GetDir() - a.GetDir();
269         
270          return DotProd(spatialDiff, spatialDerivative) +
271                DotProd(directionalDiff, directionalDerivative);
272        }
273
274       
275  };
276
277  struct SilhouetteRays {
278        RayInfo *a;
279        RayInfo *b;
280        SilhouetteRays() {}
281        SilhouetteRays(RayInfo *_a, RayInfo *_b):a(_a), b(_b) {
282        }
283  };
284 
285  typedef vector<RayInfo> RayInfoContainer;
286       
287  enum { EInterior, ELeaf };
288
289  /////////////////////////////////
290  // The actual data goes here
291 
292  // link to the parent
293  RssTreeInterior *parent;
294
295  enum {SPLIT_X=0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
296 
297  // splitting axis
298  char axis;
299       
300  // depth
301  unsigned char depth;
302 
303  //  short depth;
304  //
305  /////////////////////////////////
306
307
308  // the bbox of the node
309  AxisAlignedBox3 bbox;
310 
311  // the bbox of the node
312  AxisAlignedBox3 dirBBox;
313
314 
315  inline RssTreeNode(RssTreeInterior *p);
316
317 
318  virtual ~RssTreeNode() {};
319  virtual int Type() const  = 0;
320 
321
322  bool IsLeaf() const { return axis == -1; }
323 
324  virtual void Print(ostream &s) const = 0;
325
326  virtual int GetAccessTime() {
327    return 0x7FFFFFF;
328  }
329
330 
331       
332};
333
334// --------------------------------------------------------------
335// KD-tree node - interior node
336// --------------------------------------------------------------
337class RssTreeInterior :
338  public RssTreeNode
339{
340public:
341  // plane in local modelling coordinates
342  float position;
343
344  // pointers to children
345  RssTreeNode *back, *front;
346
347
348  // data for caching
349  long accesses;
350  long lastAccessTime;
351 
352  RssTreeInterior(RssTreeInterior *p):RssTreeNode(p),
353                                                                          back(NULL),
354                                                                          front(NULL),
355                                                                          accesses(0),
356                                                                          lastAccessTime(-1)
357  { }
358
359  virtual int GetAccessTime() {
360    return lastAccessTime;
361  }
362
363  void SetupChildLinks(RssTreeNode *b, RssTreeNode *f) {
364    back = b;
365    front = f;
366    b->parent = f->parent = this;
367  }
368
369  void ReplaceChildLink(RssTreeNode *oldChild, RssTreeNode *newChild) {
370    if (back == oldChild)
371      back = newChild;
372    else
373      front = newChild;
374  }
375
376  virtual int Type() const  { return EInterior; }
377 
378  virtual ~RssTreeInterior() {
379    if (back)
380      delete back;
381    if (front)
382      delete front;
383  }
384 
385  virtual void Print(ostream &s) const {
386    if (axis == 0)
387      s<<"x ";
388    else
389      if (axis == 1)
390                s<<"y ";
391      else
392                s<<"z ";
393    s<<position<<" ";
394    back->Print(s);
395    front->Print(s);
396  }
397
398 
399       
400  int ComputeRaySide(const
401                                         RayInfo &rayData
402                                         ) {
403        return rayData.ComputeRaySide(axis, position);
404  }
405
406};
407
408
409// --------------------------------------------------------------
410// KD-tree node - leaf node
411// --------------------------------------------------------------
412class RssTreeLeaf :
413  public RssTreeNode
414{
415private:
416  int mPvsSize;
417public:
418  static int mailID;
419  int mailbox;
420 
421  RayInfoContainer rays;
422  int mTotalRays;
423       
424  bool mValidPvs;
425  float mImportance;
426 
427  HaltonSequence halton;
428
429  Beam mBeam;
430 
431  RssTreeLeaf(RssTreeInterior *p,
432                          const int nRays
433                          ):RssTreeNode(p), rays(), mPvsSize(0), mTotalRays(0), mValidPvs(false) {
434    rays.reserve(nRays);
435  }
436 
437  virtual ~RssTreeLeaf() { }
438
439  virtual int Type() const  { return ELeaf; }
440
441  virtual void Print(ostream &s) const {
442    s<<
443          "L: rays="<<(int)rays.size()<<
444          " pvs="<<mPvsSize<<" importance="<<mImportance<<endl;
445  };
446 
447  void AddRay(const RayInfo &data) {
448        mValidPvs = false;
449    rays.push_back(data);
450        mTotalRays++;
451        data.mRay->Ref();
452  }
453       
454  int GetPvsSize() const {
455        return mPvsSize;
456  }
457
458  void SetPvsSize(const int s) {
459        mPvsSize = s;
460        mValidPvs = true;
461  }
462
463
464  float
465  ComputePvsEntropy() const;
466 
467  float
468  ComputeRayLengthEntropy() const;
469 
470  float
471  ComputeRayTerminationEntropy() const;
472 
473
474  float
475  ComputeEntropyImportance() const;
476 
477  float
478  ComputeRayContributionImportance() const;
479
480  void Mail() { mailbox = mailID; }
481  static void NewMail() { mailID++; }
482  bool Mailed() const { return mailbox == mailID; }
483 
484  bool Mailed(const int mail) {
485    return mailbox >= mailID + mail;
486  }
487
488  float GetAvgRayContribution() const {
489        return GetPvsSize()/((float)rays.size() + Limits::Small);
490  }
491
492  float GetImportance() const;
493 
494  float GetSqrRayContribution() const {
495        return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
496  }
497 
498  // comparator for the
499  struct less_contribution : public
500  binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
501       
502        bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
503          return a->GetAvgRayContribution() < b->GetAvgRayContribution();
504        }
505  };
506 
507  struct greater_contribution : public
508  binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
509       
510        bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
511          return a->GetAvgRayContribution() > b->GetAvgRayContribution();
512        }
513  };
514 
515  friend bool GreaterContribution(const RssTreeLeaf * a, const RssTreeLeaf *b) {
516        return a->GetAvgRayContribution() > b->GetAvgRayContribution();
517  }
518
519 
520};
521
522// Inline functions
523inline
524RssTreeNode::RssTreeNode(RssTreeInterior *p):
525  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
526
527
528
529// ---------------------------------------------------------------
530// Main LSDS search class
531// ---------------------------------------------------------------
532class RssTree
533{
534  struct TraversalData
535  { 
536    RssTreeNode *node;
537    AxisAlignedBox3 bbox;
538    int depth;
539    float priority;
540   
541    TraversalData() {}
542
543    TraversalData(RssTreeNode *n, const float p):
544      node(n), priority(p)
545    {}
546
547    TraversalData(RssTreeNode *n,
548                                  const AxisAlignedBox3 &b,
549                                  const int d):
550      node(n), bbox(b), depth(d) {}
551   
552               
553    // comparator for the
554    struct less_priority : public
555    binary_function<const TraversalData, const TraversalData, bool> {
556                       
557      bool operator()(const TraversalData a, const TraversalData b) {
558                return a.priority < b.priority;
559      }
560     
561    };
562
563    //    ~TraversalData() {}
564    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
565   
566    friend bool operator<(const TraversalData &a,
567                                                  const TraversalData &b) {
568      //      return a.node->queries.size() < b.node->queries.size();
569      RssTreeLeaf *leafa = (RssTreeLeaf *) a.node;
570      RssTreeLeaf *leafb = (RssTreeLeaf *) b.node;
571#if 0
572          return
573                leafa->rays.size()*a.bbox.GetVolume()
574                <
575                leafb->rays.size()*b.bbox.GetVolume();
576#endif
577#if 0
578          return
579                leafa->GetPvsSize()*a.bbox.GetVolume()
580                <
581                leafb->GetPvsSize()*b.bbox.GetVolume();
582#endif
583#if 0
584          return
585                leafa->GetPvsSize()
586                <
587                leafb->GetPvsSize();
588#endif
589#if 0
590          return
591                leafa->GetPvsSize()/(leafa->rays.size()+1)
592                >
593                leafb->GetPvsSize()/(leafb->rays.size()+1);
594#endif
595#if 1
596          return
597                leafa->GetPvsSize()*leafa->rays.size()
598                <
599                leafb->GetPvsSize()*leafb->rays.size();
600#endif
601    }
602  };
603 
604  // simplified data for ray traversal only...
605
606  struct RayTraversalData {
607   
608    RssTreeNode::RayInfo rayData;
609    RssTreeNode *node;
610   
611    RayTraversalData() {}
612    RayTraversalData(RssTreeNode *n,
613                                         const RssTreeNode::RayInfo &data):
614      rayData(data), node(n) {}
615  };
616       
617public:
618  /////////////////////////////
619  // The core pointer
620  vector<RssTreeNode *> mRoots;
621 
622 
623 
624  /////////////////////////////
625  // Basic properties
626
627  // total number of nodes of the tree
628  int nodes;
629
630  // axis aligned bounding box of the scene
631  AxisAlignedBox3 bbox;
632
633  // axis aligned bounding box of directions
634  AxisAlignedBox3 dirBBox;
635
636  // forced bounding box for from viewcell visibility
637  //  AxisAlignedBox3 *mForcedBoundingBox;
638
639  /////////////////////////////
640  // Construction parameters
641
642  // epsilon used for the construction
643  float epsilon;
644
645  // ratio between traversal and intersection costs
646  float ct_div_ci;
647  // max depth of the tree
648  int termMaxDepth;
649  // minimal ratio of the volume of the cell and the query volume
650  float termMinSize;
651
652  // minimal pvs per node to still get subdivided
653  int termMinPvs;
654
655  // minimal ray number per node to still get subdivided
656  int termMinRays;
657       
658  // maximal cost ration to subdivide a node
659  float termMaxCostRatio;
660       
661  // maximal contribution per ray to subdivide the node
662  float termMaxRayContribution;
663
664  // randomized construction
665  bool randomize;
666
667  // use a root per object in the tree
668  bool mPerObjectTree;
669 
670  // type of the splitting to use fo rthe tree construction
671  enum {ESplitRegular, ESplitHeuristic, ESplitHybrid };
672  int splitType;
673
674  bool mSplitUseOnlyDrivingAxis;
675 
676
677  // interleave directional and spatial splits based on their costs
678  // if false directional splits are only performed after spatial splits
679  bool mInterleaveDirSplits;
680
681  // depth at which directional splits are performed if mInterleaveDirSplits is false
682  int mDirSplitDepth;
683
684  // maximal number of rays maintained in the rss tree
685  int mMaxRays;
686 
687  // maximal size of the box on which the refdir splitting can be performed
688  // (relative to the scene bbox
689  float refDirBoxMaxSize;
690 
691  // maximum alovable memory in MB
692  float maxTotalMemory;
693
694  // maximum alovable memory for static kd tree in MB
695  float maxStaticMemory;
696
697  // this is used during the construction depending
698  // on the type of the tree and queries...
699  float maxMemory;
700
701
702  // minimal acess time for collapse
703  int accessTimeThreshold;
704
705  // minimal depth at which to perform collapse
706  int minCollapseDepth;
707
708  bool mImportanceBasedCost;
709
710  // sampling pass
711  int mCurrentPass;
712 
713  // reusable array of split candidates
714  vector<SortableEntry> *splitCandidates;
715  /////////////////////////////
716
717  RssStatistics stat;
718       
719 
720  RssTree();
721  virtual ~RssTree();
722
723  virtual void
724  Construct(
725                        ObjectContainer &objects,
726                        VssRayContainer &rays
727                        //                      AxisAlignedBox3 *forcedBoundingBox = NULL
728                        );
729       
730  // incemental construction
731  virtual void UpdateRays(VssRayContainer &remove,
732                                                  VssRayContainer &add
733                                                  );
734
735  virtual void AddRays(
736                                           VssRayContainer &add
737                                           )
738  {
739        VssRayContainer remove;
740        UpdateRays(remove, add);
741  }
742
743 
744       
745  RssTreeNode *
746  Locate(const Vector3 &v);
747       
748  RssTreeNode *
749  SubdivideNode(RssTreeLeaf *leaf,
750                                const AxisAlignedBox3 &box,
751                                AxisAlignedBox3 &backBox,
752                                AxisAlignedBox3 &frontBox
753                                );
754       
755  RssTreeNode *
756  Subdivide(const TraversalData &tdata);
757       
758
759  void
760  SortSplitCandidates(
761                                          RssTreeLeaf *node,
762                                          const int axis
763                                          );
764       
765 
766  // return memory usage in MB
767  float GetMemUsage() const {
768    return
769      (sizeof(RssTree) +
770       stat.Leaves()*sizeof(RssTreeLeaf) +
771       stat.Interior()*sizeof(RssTreeInterior) +
772       stat.rayRefs*sizeof(RssTreeNode::RayInfo))/(1024.0f*1024.0f);
773  }
774       
775  float GetRayMemUsage() const {
776    return
777      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
778  }
779 
780  struct SplitInfo {
781       
782        int axis;
783        float position;
784        float costRatio;
785       
786        int rays;
787        int raysBack;
788        int raysFront;
789
790        int pvs;
791        int pvsBack;
792        int pvsFront;
793
794        float contribution;
795        float contributionBack;
796        float contributionFront;
797
798        int viewCells;
799        int viewCellsBack;
800        int viewCellsFront;
801
802        float volume;
803        float volumeBack;
804        float volumeFront;
805       
806  };
807 
808  void
809  BestCostRatio(
810                                RssTreeLeaf *node,
811                                SplitInfo &info
812//                              int &axis,
813//                              float &position,
814//                              int &raysBack,
815//                              int &raysFront,
816//                              int &pvsBack,
817//                              int &pvsFront
818                                );
819       
820 
821  void
822  EvalCostRatio(
823                                RssTreeLeaf *node,
824                                SplitInfo &info
825//                              const int axis,
826//                              const float position,
827//                              int &raysBack,
828//                              int &raysFront,
829//                              int &pvsBack,
830//                              int &pvsFront
831                                );
832
833  void
834  EvalCostRatioHeuristic(
835                                                 RssTreeLeaf *node,
836                                                 SplitInfo &info
837//                                               const int axis,
838//                                               float &position,
839//                                               int &raysBack,
840//                                               int &raysFront,
841//                                               int &pvsBack,
842//                                               int &pvsFront
843                                                 );
844
845  int
846  SelectPlane(RssTreeLeaf *leaf,
847                          const AxisAlignedBox3 &box,
848                          SplitInfo &info
849                          );
850 
851  void
852  GetCostRatio(
853                           RssTreeLeaf *leaf,
854                           SplitInfo &info
855                           //                      const int axis,
856                           //                      const float position,
857                           //                      const int raysBack,
858                           //                      const int raysFront,
859                           //                      const int pvsBack,
860                           //                      const int pvsFront
861                           );
862 
863  AxisAlignedBox3 GetBBox(const RssTreeNode *node) const {
864        return node->bbox;
865
866//     if (node->parent == NULL)
867//       return bbox;
868
869//     if (!node->IsLeaf())
870//       return ((RssTreeInterior *)node)->bbox;
871
872//     if (node->parent->axis >= 3)
873//       return node->parent->bbox;
874     
875//     AxisAlignedBox3 box(node->parent->bbox);
876//     if (node->parent->front == node)
877//       box.SetMin(node->parent->axis, node->parent->position);
878//     else
879//       box.SetMax(node->parent->axis, node->parent->position);
880//     return box;
881  }
882
883  AxisAlignedBox3 GetShrankedBBox(const RssTreeNode *node) const;
884
885  AxisAlignedBox3 GetDirBBox(const RssTreeNode *node) const {
886        return node->dirBBox;
887//     if (node->parent == NULL)
888//       return dirBBox;
889   
890//     if (!node->IsLeaf() )
891//       return ((RssTreeInterior *)node)->dirBBox;
892
893//     if (node->parent->axis < 3)
894//       return node->parent->dirBBox;
895   
896//     AxisAlignedBox3 dBBox(node->parent->dirBBox);
897
898//     if (node->parent->front == node)
899//       dBBox.SetMin(node->parent->axis - 3, node->parent->position);
900//     else
901//       dBBox.SetMax(node->parent->axis - 3, node->parent->position);
902//     return dBBox;
903  }
904 
905  int
906  ReleaseMemory(const int time);
907
908  int
909  CollapseSubtree(RssTreeNode *node, const int time);
910
911  void
912  CountAccess(RssTreeInterior *node, const long time) {
913    node->accesses++;
914    node->lastAccessTime = time;
915  }
916
917  RssTreeNode *
918  SubdivideLeaf(
919                                RssTreeLeaf *leaf
920                                );
921
922  void
923  RemoveRay(VssRay *ray,
924                        vector<RssTreeLeaf *> *affectedLeaves,
925                        const bool removeAllScheduledRays
926                        );
927
928  //  void
929  //  AddRay(VssRay *ray);
930  void
931  AddRay(RssTreeNode::RayInfo &info);
932 
933  void
934  TraverseInternalNode(
935                                           RayTraversalData &data,
936                                           stack<RayTraversalData> &tstack);
937
938  void
939  EvaluateLeafStats(const TraversalData &data);
940
941
942  int
943  GetRootPvsSize() const {
944        return GetPvsSize(bbox);
945  }
946 
947  int
948  GetPvsSize(const AxisAlignedBox3 &box) const;
949
950  int
951  CollectPvs(const AxisAlignedBox3 &box,
952                         ObjectContainer &pvs
953                         ) const;
954
955  int
956  CollectRootPvs(
957                                 ObjectContainer &pvs
958                                 ) const
959  {
960        return CollectPvs(bbox, pvs);
961  }
962 
963       
964  void
965  UpdateTreeStatistics();
966
967
968  int
969  GenerateRays(const float ratioPerLeaf,
970                           SimpleRayContainer &rays);
971
972  int
973  GenerateRays(const int numberOfRays,
974                           const int numberOfLeaves,
975                           SimpleRayContainer &rays);
976               
977  float
978  GetAvgPvsSize();
979
980  int
981  UpdateSubdivision();
982
983  bool
984  TerminationCriteriaSatisfied(RssTreeLeaf *leaf);
985
986  void
987  CollectLeaves(vector<RssTreeLeaf *> &leaves);
988
989  bool
990  ClipRay(
991                  RssTreeNode::RayInfo &rayInfo,
992                  const AxisAlignedBox3 &box
993                  );
994
995  RssTreeNode *GetRoot(Intersectable *object = NULL) const;
996
997  bool
998  ValidLeaf(RssTreeLeaf *leaf) const;
999
1000  void
1001  GenerateLeafRays(RssTreeLeaf *leaf,
1002                                   const int numberOfRays,
1003                                   SimpleRayContainer &rays);
1004
1005
1006  void
1007  PickEdgeRays(RssTreeLeaf *leaf,
1008                           int &r1,
1009                           int &r2
1010                           );
1011
1012    int
1013  CollectRays(VssRayContainer &rays,
1014                          const int number);
1015
1016  int
1017  CollectRays(VssRayContainer &rays
1018                          );
1019
1020  void
1021  UpdatePvsSize(RssTreeLeaf *leaf);
1022
1023  void
1024  ComputeImportance(RssTreeLeaf *leaf);
1025 
1026  void
1027  SetPass(const int p) {
1028        mCurrentPass = p;
1029  }
1030 
1031  void GetRayContribution(const RssTreeNode::RayInfo &info,
1032                                                  float &weight,
1033                                                  float &contribution);
1034
1035  float
1036  GetSampleWeight(const int pass);
1037
1038  int
1039  RemoveInteriorRays(
1040                                         RssTreeLeaf *leaf
1041                                         );
1042
1043  bool
1044  IsRayConvexCombination(const RssTreeNode::RayInfo &ray,
1045                                                 const RssTreeNode::RayInfo &r1,
1046                                                 const RssTreeNode::RayInfo &r2,
1047                                                 const RssTreeNode::RayInfo &r3);
1048
1049  int
1050  PruneRays(RssTreeLeaf *leaf,
1051                        const float contributionThreshold);
1052  int
1053  PruneRaysRandom(RssTreeLeaf *leaf,
1054                                  const float ratio);
1055
1056  int
1057  PruneRaysContribution(RssTreeLeaf *leaf,
1058                                                const float ratio);
1059
1060  int
1061  PruneRays(
1062                        const int desired
1063                        );
1064 
1065
1066  void
1067  FindSilhouetteRays(RssTreeLeaf *leaf,
1068                                         vector<RssTreeLeaf::SilhouetteRays> &rays
1069                                         );
1070
1071  void
1072  PushRoots(priority_queue<TraversalData> &stack) const;
1073
1074  void
1075  PushRoots(stack<RssTreeNode *> &st) const;
1076
1077  void
1078  PushRoots(stack<RayTraversalData> &st, RssTreeNode::RayInfo &info) const;
1079
1080
1081};
1082
1083};
1084
1085#endif // __RSSTREE_H__
1086
Note: See TracBrowser for help on using the repository browser.