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

Revision 1715, 22.4 KB checked in by bittner, 18 years ago (diff)

new visibility filter support
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  // depth till which the regular splits are applied for hybrid split type
685  int mHybridDepth;
686 
687  // maximal number of rays maintained in the rss tree
688  int mMaxRays;
689 
690  // maximal size of the box on which the refdir splitting can be performed
691  // (relative to the scene bbox
692  float refDirBoxMaxSize;
693 
694  // maximum alovable memory in MB
695  float maxTotalMemory;
696
697  // maximum alovable memory for static kd tree in MB
698  float maxStaticMemory;
699
700  // this is used during the construction depending
701  // on the type of the tree and queries...
702  float maxMemory;
703
704
705  // minimal acess time for collapse
706  int accessTimeThreshold;
707
708  // minimal depth at which to perform collapse
709  int minCollapseDepth;
710
711  bool mImportanceBasedCost;
712
713  // sampling pass
714  int mCurrentPass;
715 
716  // reusable array of split candidates
717  vector<SortableEntry> *splitCandidates;
718  /////////////////////////////
719
720  RssStatistics stat;
721       
722 
723  RssTree();
724  virtual ~RssTree();
725
726  virtual void
727  Construct(
728                        ObjectContainer &objects,
729                        VssRayContainer &rays
730                        //                      AxisAlignedBox3 *forcedBoundingBox = NULL
731                        );
732       
733  // incemental construction
734  virtual void UpdateRays(VssRayContainer &remove,
735                                                  VssRayContainer &add
736                                                  );
737
738  virtual void AddRays(
739                                           VssRayContainer &add
740                                           )
741  {
742        VssRayContainer remove;
743        UpdateRays(remove, add);
744  }
745
746 
747       
748  RssTreeNode *
749  Locate(const Vector3 &v);
750       
751  RssTreeNode *
752  SubdivideNode(RssTreeLeaf *leaf,
753                                const AxisAlignedBox3 &box,
754                                AxisAlignedBox3 &backBox,
755                                AxisAlignedBox3 &frontBox
756                                );
757       
758  RssTreeNode *
759  Subdivide(const TraversalData &tdata);
760       
761
762  void
763  SortSubdivisionCandidates(
764                                          RssTreeLeaf *node,
765                                          const int axis
766                                          );
767       
768 
769  // return memory usage in MB
770  float GetMemUsage() const {
771    return
772      (sizeof(RssTree) +
773       stat.Leaves()*sizeof(RssTreeLeaf) +
774       stat.Interior()*sizeof(RssTreeInterior) +
775       stat.rayRefs*sizeof(RssTreeNode::RayInfo))/(1024.0f*1024.0f);
776  }
777       
778  float GetRayMemUsage() const {
779    return
780      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
781  }
782 
783  struct SplitInfo {
784       
785        int axis;
786        float position;
787        float costRatio;
788       
789        int rays;
790        int raysBack;
791        int raysFront;
792
793        int pvs;
794        int pvsBack;
795        int pvsFront;
796
797        float contribution;
798        float contributionBack;
799        float contributionFront;
800
801        int viewCells;
802        int viewCellsBack;
803        int viewCellsFront;
804
805        float volume;
806        float volumeBack;
807        float volumeFront;
808       
809  };
810 
811  void
812  BestCostRatio(
813                                RssTreeLeaf *node,
814                                SplitInfo &info
815//                              int &axis,
816//                              float &position,
817//                              int &raysBack,
818//                              int &raysFront,
819//                              int &pvsBack,
820//                              int &pvsFront
821                                );
822       
823 
824  void
825  EvalCostRatio(
826                                RssTreeLeaf *node,
827                                SplitInfo &info
828//                              const int axis,
829//                              const float position,
830//                              int &raysBack,
831//                              int &raysFront,
832//                              int &pvsBack,
833//                              int &pvsFront
834                                );
835
836  void
837  EvalCostRatioHeuristic(
838                                                 RssTreeLeaf *node,
839                                                 SplitInfo &info
840//                                               const int axis,
841//                                               float &position,
842//                                               int &raysBack,
843//                                               int &raysFront,
844//                                               int &pvsBack,
845//                                               int &pvsFront
846                                                 );
847
848  int
849  SelectPlane(RssTreeLeaf *leaf,
850                          const AxisAlignedBox3 &box,
851                          SplitInfo &info
852                          );
853 
854  void
855  GetCostRatio(
856                           RssTreeLeaf *leaf,
857                           SplitInfo &info
858                           //                      const int axis,
859                           //                      const float position,
860                           //                      const int raysBack,
861                           //                      const int raysFront,
862                           //                      const int pvsBack,
863                           //                      const int pvsFront
864                           );
865 
866  AxisAlignedBox3 GetBBox(const RssTreeNode *node) const {
867        return node->bbox;
868
869//     if (node->parent == NULL)
870//       return bbox;
871
872//     if (!node->IsLeaf())
873//       return ((RssTreeInterior *)node)->bbox;
874
875//     if (node->parent->axis >= 3)
876//       return node->parent->bbox;
877     
878//     AxisAlignedBox3 box(node->parent->bbox);
879//     if (node->parent->front == node)
880//       box.SetMin(node->parent->axis, node->parent->position);
881//     else
882//       box.SetMax(node->parent->axis, node->parent->position);
883//     return box;
884  }
885
886  AxisAlignedBox3 GetShrankedBBox(const RssTreeNode *node) const;
887
888  AxisAlignedBox3 GetDirBBox(const RssTreeNode *node) const {
889        return node->dirBBox;
890//     if (node->parent == NULL)
891//       return dirBBox;
892   
893//     if (!node->IsLeaf() )
894//       return ((RssTreeInterior *)node)->dirBBox;
895
896//     if (node->parent->axis < 3)
897//       return node->parent->dirBBox;
898   
899//     AxisAlignedBox3 dBBox(node->parent->dirBBox);
900
901//     if (node->parent->front == node)
902//       dBBox.SetMin(node->parent->axis - 3, node->parent->position);
903//     else
904//       dBBox.SetMax(node->parent->axis - 3, node->parent->position);
905//     return dBBox;
906  }
907 
908  int
909  ReleaseMemory(const int time);
910
911  int
912  CollapseSubtree(RssTreeNode *node, const int time);
913
914  void
915  CountAccess(RssTreeInterior *node, const long time) {
916    node->accesses++;
917    node->lastAccessTime = time;
918  }
919
920  RssTreeNode *
921  SubdivideLeaf(
922                                RssTreeLeaf *leaf
923                                );
924
925  void
926  RemoveRay(VssRay *ray,
927                        vector<RssTreeLeaf *> *affectedLeaves,
928                        const bool removeAllScheduledRays
929                        );
930
931  //  void
932  //  AddRay(VssRay *ray);
933  void
934  AddRay(RssTreeNode::RayInfo &info);
935 
936  void
937  TraverseInternalNode(
938                                           RayTraversalData &data,
939                                           stack<RayTraversalData> &tstack);
940
941  void
942  EvaluateLeafStats(const TraversalData &data);
943
944
945  int
946  GetRootPvsSize() const {
947        return GetPvsSize(bbox);
948  }
949 
950  int
951  GetPvsSize(const AxisAlignedBox3 &box) const;
952
953  int
954  CollectPvs(const AxisAlignedBox3 &box,
955                         ObjectContainer &pvs
956                         ) const;
957
958  int
959  CollectRootPvs(
960                                 ObjectContainer &pvs
961                                 ) const
962  {
963        return CollectPvs(bbox, pvs);
964  }
965 
966       
967  void
968  UpdateTreeStatistics();
969
970
971  int
972  GenerateRays(const float ratioPerLeaf,
973                           SimpleRayContainer &rays);
974
975  int
976  GenerateRays(const int numberOfRays,
977                           const int numberOfLeaves,
978                           SimpleRayContainer &rays);
979               
980  float
981  GetAvgPvsSize();
982
983  int
984  UpdateSubdivision();
985
986  bool
987  TerminationCriteriaSatisfied(RssTreeLeaf *leaf);
988
989  void
990  CollectLeaves(vector<RssTreeLeaf *> &leaves);
991
992  bool
993  ClipRay(
994                  RssTreeNode::RayInfo &rayInfo,
995                  const AxisAlignedBox3 &box
996                  );
997
998  RssTreeNode *GetRoot(Intersectable *object = NULL) const;
999
1000  bool
1001  ValidLeaf(RssTreeLeaf *leaf) const;
1002
1003  void
1004  GenerateLeafRays(RssTreeLeaf *leaf,
1005                                   const int numberOfRays,
1006                                   SimpleRayContainer &rays);
1007
1008  void
1009  GenerateLeafRaysSimple(RssTreeLeaf *leaf,
1010                                                 const int numberOfRays,
1011                                                 SimpleRayContainer &rays);
1012       
1013
1014  void
1015  PickEdgeRays(RssTreeLeaf *leaf,
1016                           int &r1,
1017                           int &r2
1018                           );
1019
1020  int
1021  CollectRays(VssRayContainer &rays,
1022                          const int number);
1023
1024  int
1025  CollectRays(VssRayContainer &rays
1026                          );
1027
1028  void
1029  UpdatePvsSize(RssTreeLeaf *leaf);
1030
1031  void
1032  ComputeImportance(RssTreeLeaf *leaf);
1033 
1034  void
1035  SetPass(const int p) {
1036        mCurrentPass = p;
1037  }
1038 
1039  void GetRayContribution(const RssTreeNode::RayInfo &info,
1040                                                  float &weight,
1041                                                  float &contribution);
1042
1043  float
1044  GetSampleWeight(const int pass);
1045
1046  int
1047  RemoveInteriorRays(
1048                                         RssTreeLeaf *leaf
1049                                         );
1050
1051  bool
1052  IsRayConvexCombination(const RssTreeNode::RayInfo &ray,
1053                                                 const RssTreeNode::RayInfo &r1,
1054                                                 const RssTreeNode::RayInfo &r2,
1055                                                 const RssTreeNode::RayInfo &r3);
1056
1057  int
1058  PruneRays(RssTreeLeaf *leaf,
1059                        const float contributionThreshold);
1060  int
1061  PruneRaysRandom(RssTreeLeaf *leaf,
1062                                  const float ratio);
1063
1064  int
1065  PruneRaysContribution(RssTreeLeaf *leaf,
1066                                                const float ratio);
1067
1068  int
1069  PruneRays(
1070                        const int desired
1071                        );
1072 
1073
1074  void
1075  FindSilhouetteRays(RssTreeLeaf *leaf,
1076                                         vector<RssTreeLeaf::SilhouetteRays> &rays
1077                                         );
1078
1079  void
1080  PushRoots(priority_queue<TraversalData> &stack) const;
1081
1082  void
1083  PushRoots(stack<RssTreeNode *> &st) const;
1084
1085  void
1086  PushRoots(stack<RayTraversalData> &st, RssTreeNode::RayInfo &info) const;
1087
1088
1089};
1090
1091};
1092
1093#endif // __RSSTREE_H__
1094
Note: See TracBrowser for help on using the repository browser.