source: trunk/VUT/GtpVisibilityPreprocessor/src/RssTree.h @ 511

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