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

Revision 1884, 23.5 KB checked in by bittner, 18 years ago (diff)

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