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

Revision 1876, 22.9 KB checked in by bittner, 18 years ago (diff)

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