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

Revision 2176, 23.7 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h
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(std::ostream &app) const;
119
120  friend std::ostream &operator<<(std::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  // importance requires update
321  //bool mRequiresUpdate;
322
323  inline RssTreeNode(RssTreeInterior *p);
324
325 
326  virtual ~RssTreeNode() {};
327  virtual int Type() const  = 0;
328 
329
330  bool IsLeaf() const { return axis == -1; }
331 
332  virtual void Print(std::ostream &s) const = 0;
333
334  virtual int GetAccessTime() {
335    return 0x7FFFFFF;
336  }
337
338  float GetImportance() const;
339
340       
341};
342
343// --------------------------------------------------------------
344// KD-tree node - interior node
345// --------------------------------------------------------------
346class RssTreeInterior :
347  public RssTreeNode
348{
349public:
350  // plane in world coordinates
351  float position;
352
353  // pointers to children
354  RssTreeNode *back, *front;
355
356
357  // data for caching
358  long accesses;
359  long lastAccessTime;
360 
361  RssTreeInterior(RssTreeInterior *p):RssTreeNode(p),
362                                                                          back(NULL),
363                                                                          front(NULL),
364                                                                          accesses(0),
365                                                                          lastAccessTime(-1)
366  { }
367
368  virtual int GetAccessTime() {
369    return lastAccessTime;
370  }
371
372  float GetRelativePosition() const {
373        if (axis < 3)
374          return (position - bbox.Min(axis))/bbox.Size(axis);
375        else
376          return (position - dirBBox.Min(axis-3))/dirBBox.Size(axis-3);
377  }
378
379  void SetupChildLinks(RssTreeNode *b, RssTreeNode *f) {
380    back = b;
381    front = f;
382    b->parent = f->parent = this;
383  }
384
385  void ReplaceChildLink(RssTreeNode *oldChild, RssTreeNode *newChild) {
386    if (back == oldChild)
387      back = newChild;
388    else
389      front = newChild;
390  }
391
392  virtual int Type() const  { return EInterior; }
393 
394  virtual ~RssTreeInterior() {
395    if (back)
396      delete back;
397    if (front)
398      delete front;
399  }
400 
401  virtual void Print(std::ostream &s) const {
402    if (axis == 0)
403      s<<"x ";
404    else
405      if (axis == 1)
406                s<<"y ";
407      else
408                s<<"z ";
409    s<<position<<" ";
410    back->Print(s);
411    front->Print(s);
412  }
413
414 
415       
416  int ComputeRaySide(const
417                                         RayInfo &rayData
418                                         ) {
419        return rayData.ComputeRaySide(axis, position);
420  }
421
422};
423
424
425// --------------------------------------------------------------
426// KD-tree node - leaf node
427// --------------------------------------------------------------
428class RssTreeLeaf :
429  public RssTreeNode
430{
431private:
432  int mPvsSize;
433public:
434  static int mailID;
435  int mailbox;
436 
437  RayInfoContainer rays;
438  int mTotalRays;
439  float mTotalContribution;
440 
441  bool mValidPvs;
442 
443  Beam mBeam;
444 
445  RssTreeLeaf(RssTreeInterior *p,
446                          const int nRays
447                          ):RssTreeNode(p), rays(), mPvsSize(0), mTotalRays(0),
448                                mTotalContribution(0.0f), mValidPvs(false) {
449    rays.reserve(nRays);
450  }
451 
452  virtual ~RssTreeLeaf() { }
453
454  virtual int Type() const  { return ELeaf; }
455
456  virtual void Print(std::ostream &s) const {
457    s<<
458          "L: rays="<<(int)rays.size()<<
459          " pvs="<<mPvsSize<<" importance="<<mImportance<<std::endl;
460  };
461 
462  void AddRay(const RayInfo &data) {
463        mValidPvs = false;
464        rays.push_back(data);
465        mTotalRays++;
466        mTotalContribution +=
467          ABS_CONTRIBUTION_WEIGHT*data.mRay->mPvsContribution +
468          (1.0f - ABS_CONTRIBUTION_WEIGHT)*data.mRay->mRelativePvsContribution;
469        data.mRay->Ref();
470  }
471       
472  int GetPvsSize() const {
473        return mPvsSize;
474  }
475
476  void SetPvsSize(const int s) {
477        mPvsSize = s;
478        mValidPvs = true;
479  }
480
481
482  float
483  ComputePvsEntropy() const;
484 
485  float
486  ComputeRayLengthEntropy() const;
487 
488  float
489  ComputeRayTerminationEntropy() const;
490 
491
492  float
493  ComputeEntropyImportance() const;
494 
495  float
496  ComputeRayContributionImportance() const;
497
498  void Mail() { mailbox = mailID; }
499  static void NewMail() { mailID++; }
500  bool Mailed() const { return mailbox == mailID; }
501 
502  bool Mailed(const int mail) {
503    return mailbox >= mailID + mail;
504  }
505
506  float GetAvgRayContribution() const {
507        return GetPvsSize()/((float)rays.size() + Limits::Small);
508  }
509
510 
511  float GetSqrRayContribution() const {
512        return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
513  }
514 
515  // comparator for the
516  struct less_contribution : public
517  std::binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
518       
519        bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
520          return a->GetAvgRayContribution() < b->GetAvgRayContribution();
521        }
522  };
523 
524  struct greater_contribution : public
525  std::binary_function<const RssTreeLeaf *, const RssTreeLeaf *, bool> {
526       
527        bool operator()(const RssTreeLeaf * a, const RssTreeLeaf *b) {
528          return a->GetAvgRayContribution() > b->GetAvgRayContribution();
529        }
530  };
531 
532  friend bool GreaterContribution(const RssTreeLeaf * a, const RssTreeLeaf *b) {
533        return a->GetAvgRayContribution() > b->GetAvgRayContribution();
534  }
535
536 
537};
538
539// Inline functions
540inline
541RssTreeNode::RssTreeNode(RssTreeInterior *p):
542  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
543
544
545
546// ---------------------------------------------------------------
547// Main LSDS search class
548// ---------------------------------------------------------------
549class RssTree
550{
551  struct TraversalData
552  { 
553    RssTreeNode *node;
554    AxisAlignedBox3 bbox;
555    int depth;
556    float priority;
557   
558    TraversalData() {}
559
560    TraversalData(RssTreeNode *n, const float p):
561      node(n), priority(p)
562    {}
563
564    TraversalData(RssTreeNode *n,
565                                  const AxisAlignedBox3 &b,
566                                  const int d):
567      node(n), bbox(b), depth(d) {}
568   
569               
570    // comparator for the
571    struct less_priority : public
572    std::binary_function<const TraversalData, const TraversalData, bool> {
573                       
574      bool operator()(const TraversalData a, const TraversalData b) {
575                return a.priority < b.priority;
576      }
577     
578    };
579
580    //    ~TraversalData() {}
581    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
582   
583    friend bool operator<(const TraversalData &a,
584                                                  const TraversalData &b) {
585      //      return a.node->queries.size() < b.node->queries.size();
586      RssTreeLeaf *leafa = (RssTreeLeaf *) a.node;
587      RssTreeLeaf *leafb = (RssTreeLeaf *) b.node;
588#if 0
589          return
590                leafa->rays.size()*a.bbox.GetVolume()
591                <
592                leafb->rays.size()*b.bbox.GetVolume();
593#endif
594#if 0
595          return
596                leafa->GetPvsSize()*a.bbox.GetVolume()
597                <
598                leafb->GetPvsSize()*b.bbox.GetVolume();
599#endif
600#if 0
601          return
602                leafa->GetPvsSize()
603                <
604                leafb->GetPvsSize();
605#endif
606#if 0
607          return
608                leafa->GetPvsSize()/(leafa->rays.size()+1)
609                >
610                leafb->GetPvsSize()/(leafb->rays.size()+1);
611#endif
612#if 1
613          return
614                leafa->GetPvsSize()*leafa->rays.size()
615                <
616                leafb->GetPvsSize()*leafb->rays.size();
617#endif
618    }
619  };
620 
621  // simplified data for ray traversal only...
622
623  struct RayTraversalData {
624   
625    RssTreeNode::RayInfo rayData;
626    RssTreeNode *node;
627   
628    RayTraversalData() {}
629    RayTraversalData(RssTreeNode *n,
630                                         const RssTreeNode::RayInfo &data):
631      rayData(data), node(n) {}
632  };
633       
634public:
635  /////////////////////////////
636  // The core pointer
637  vector<RssTreeNode *> mRoots;
638 
639 
640  HaltonSequence mHalton;
641 
642
643  /////////////////////////////
644  // Basic properties
645
646  // total number of nodes of the tree
647  int nodes;
648
649  // axis aligned bounding box of the scene
650  AxisAlignedBox3 bbox;
651
652  // axis aligned bounding box of directions
653  AxisAlignedBox3 dirBBox;
654
655  // forced bounding box for from viewcell visibility
656  //  AxisAlignedBox3 *mForcedBoundingBox;
657
658  /////////////////////////////
659  // Construction parameters
660
661  // epsilon used for the construction
662  float epsilon;
663
664  // ratio between traversal and intersection costs
665  float ct_div_ci;
666  // max depth of the tree
667  int termMaxDepth;
668  // minimal ratio of the volume of the cell and the query volume
669  float termMinSize;
670
671  // minimal pvs per node to still get subdivided
672  int termMinPvs;
673
674  // minimal ray number per node to still get subdivided
675  int termMinRays;
676       
677  // maximal cost ration to subdivide a node
678  float termMaxCostRatio;
679       
680  // maximal contribution per ray to subdivide the node
681  float termMaxRayContribution;
682
683  // randomized construction
684  bool randomize;
685
686  // use a root per object in the tree
687  bool mPerObjectTree;
688 
689  // type of the splitting to use fo rthe tree construction
690  enum {ESplitRegular, ESplitHeuristic, ESplitHybrid };
691  int splitType;
692
693  bool mSplitUseOnlyDrivingAxis;
694 
695
696  // interleave directional and spatial splits based on their costs
697  // if false directional splits are only performed after spatial splits
698  bool mInterleaveDirSplits;
699
700  // depth at which directional splits are performed if mInterleaveDirSplits is false
701  int mDirSplitDepth;
702
703  // depth till which the regular splits are applied for hybrid split type
704  int mHybridDepth;
705 
706  // maximal number of rays maintained in the rss tree
707  int mMaxRays;
708 
709  // maximal size of the box on which the refdir splitting can be performed
710  // (relative to the scene bbox
711  float refDirBoxMaxSize;
712 
713  // maximum alovable memory in MB
714  float maxTotalMemory;
715
716  // maximum alovable memory for static kd tree in MB
717  float maxStaticMemory;
718
719  // this is used during the construction depending
720  // on the type of the tree and queries...
721  float maxMemory;
722
723
724  // minimal acess time for collapse
725  int accessTimeThreshold;
726
727  // minimal depth at which to perform collapse
728  int minCollapseDepth;
729
730  bool mImportanceBasedCost;
731
732  // sampling pass
733  int mCurrentPass;
734 
735  // reusable array of split candidates
736  vector<SortableEntry> *splitCandidates;
737  /////////////////////////////
738
739  RssStatistics stat;
740       
741 
742  RssTree();
743  virtual ~RssTree();
744
745  virtual void
746  Construct(
747                        ObjectContainer &objects,
748                        VssRayContainer &rays
749                        //                      AxisAlignedBox3 *forcedBoundingBox = NULL
750                        );
751       
752  // incemental construction
753  virtual void UpdateRays(VssRayContainer &remove,
754                                                  VssRayContainer &add
755                                                  );
756
757  virtual void AddRays(
758                                           VssRayContainer &add
759                                           )
760  {
761        VssRayContainer remove;
762        UpdateRays(remove, add);
763  }
764
765 
766       
767  RssTreeNode *
768  Locate(const Vector3 &v);
769       
770  RssTreeNode *
771  SubdivideNode(RssTreeLeaf *leaf,
772                                const AxisAlignedBox3 &box,
773                                AxisAlignedBox3 &backBox,
774                                AxisAlignedBox3 &frontBox
775                                );
776       
777  RssTreeNode *
778  Subdivide(const TraversalData &tdata);
779       
780
781  void
782  SortSubdivisionCandidates(
783                                          RssTreeLeaf *node,
784                                          const int axis
785                                          );
786       
787 
788  // return memory usage in MB
789  float GetMemUsage() const {
790    return
791      (sizeof(RssTree) +
792       stat.Leaves()*sizeof(RssTreeLeaf) +
793       stat.Interior()*sizeof(RssTreeInterior) +
794       stat.rayRefs*sizeof(RssTreeNode::RayInfo))/(1024.0f*1024.0f);
795  }
796       
797  float GetRayMemUsage() const {
798    return
799      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
800  }
801 
802  struct SplitInfo {
803       
804        int axis;
805        float position;
806        float costRatio;
807       
808        int rays;
809        int raysBack;
810        int raysFront;
811
812        int pvs;
813        int pvsBack;
814        int pvsFront;
815
816        float contribution;
817        float contributionBack;
818        float contributionFront;
819
820        int viewCells;
821        int viewCellsBack;
822        int viewCellsFront;
823
824        float volume;
825        float volumeBack;
826        float volumeFront;
827       
828  };
829 
830  void
831  BestCostRatio(
832                                RssTreeLeaf *node,
833                                SplitInfo &info
834//                              int &axis,
835//                              float &position,
836//                              int &raysBack,
837//                              int &raysFront,
838//                              int &pvsBack,
839//                              int &pvsFront
840                                );
841       
842 
843  void
844  EvalCostRatio(
845                                RssTreeLeaf *node,
846                                SplitInfo &info
847//                              const int axis,
848//                              const float position,
849//                              int &raysBack,
850//                              int &raysFront,
851//                              int &pvsBack,
852//                              int &pvsFront
853                                );
854
855  void
856  EvalCostRatioHeuristic(
857                                                 RssTreeLeaf *node,
858                                                 SplitInfo &info
859//                                               const int axis,
860//                                               float &position,
861//                                               int &raysBack,
862//                                               int &raysFront,
863//                                               int &pvsBack,
864//                                               int &pvsFront
865                                                 );
866
867  int
868  SelectPlane(RssTreeLeaf *leaf,
869                          const AxisAlignedBox3 &box,
870                          SplitInfo &info
871                          );
872 
873  void
874  GetCostRatio(
875                           RssTreeLeaf *leaf,
876                           SplitInfo &info
877                           //                      const int axis,
878                           //                      const float position,
879                           //                      const int raysBack,
880                           //                      const int raysFront,
881                           //                      const int pvsBack,
882                           //                      const int pvsFront
883                           );
884 
885  AxisAlignedBox3 GetBBox(const RssTreeNode *node) const {
886        return node->bbox;
887
888//     if (node->parent == NULL)
889//       return bbox;
890
891//     if (!node->IsLeaf())
892//       return ((RssTreeInterior *)node)->bbox;
893
894//     if (node->parent->axis >= 3)
895//       return node->parent->bbox;
896     
897//     AxisAlignedBox3 box(node->parent->bbox);
898//     if (node->parent->front == node)
899//       box.SetMin(node->parent->axis, node->parent->position);
900//     else
901//       box.SetMax(node->parent->axis, node->parent->position);
902//     return box;
903  }
904
905  AxisAlignedBox3 GetShrankedBBox(const RssTreeNode *node) const;
906
907  AxisAlignedBox3 GetDirBBox(const RssTreeNode *node) const {
908        return node->dirBBox;
909//     if (node->parent == NULL)
910//       return dirBBox;
911   
912//     if (!node->IsLeaf() )
913//       return ((RssTreeInterior *)node)->dirBBox;
914
915//     if (node->parent->axis < 3)
916//       return node->parent->dirBBox;
917   
918//     AxisAlignedBox3 dBBox(node->parent->dirBBox);
919
920//     if (node->parent->front == node)
921//       dBBox.SetMin(node->parent->axis - 3, node->parent->position);
922//     else
923//       dBBox.SetMax(node->parent->axis - 3, node->parent->position);
924//     return dBBox;
925  }
926 
927  int
928  ReleaseMemory(const int time);
929
930  int
931  CollapseSubtree(RssTreeNode *node, const int time);
932
933  void
934  CountAccess(RssTreeInterior *node, const long time) {
935    node->accesses++;
936    node->lastAccessTime = time;
937  }
938
939  RssTreeNode *
940  SubdivideLeaf(
941                                RssTreeLeaf *leaf
942                                );
943
944  void
945  RemoveRay(VssRay *ray,
946                        vector<RssTreeLeaf *> *affectedLeaves,
947                        const bool removeAllScheduledRays
948                        );
949
950  //  void
951  //  AddRay(VssRay *ray);
952  void
953  AddRay(RssTreeNode::RayInfo &info);
954 
955  void
956  TraverseInternalNode(
957                                           RayTraversalData &data,
958                                           std::stack<RayTraversalData> &tstack);
959
960  void
961  EvaluateLeafStats(const TraversalData &data);
962
963
964  int
965  GetRootPvsSize() const {
966        return GetPvsSize(bbox);
967  }
968 
969  int
970  GetPvsSize(const AxisAlignedBox3 &box) const;
971
972  int
973  CollectPvs(const AxisAlignedBox3 &box,
974                         ObjectContainer &pvs
975                         ) const;
976
977  int
978  CollectRootPvs(
979                                 ObjectContainer &pvs
980                                 ) const
981  {
982        return CollectPvs(bbox, pvs);
983  }
984 
985       
986  void
987  UpdateTreeStatistics();
988
989
990  int
991  GenerateRays(const float ratioPerLeaf,
992                           SimpleRayContainer &rays);
993
994  int
995  GenerateRays(const int numberOfRays,
996                           const int numberOfLeaves,
997                           SimpleRayContainer &rays);
998               
999  float
1000  GetAvgPvsSize();
1001
1002  int
1003  UpdateSubdivision();
1004
1005  bool
1006  TerminationCriteriaSatisfied(RssTreeLeaf *leaf);
1007
1008  void
1009  CollectLeaves(vector<RssTreeLeaf *> &leaves);
1010
1011  bool
1012  ClipRay(
1013                  RssTreeNode::RayInfo &rayInfo,
1014                  const AxisAlignedBox3 &box
1015                  );
1016
1017  RssTreeNode *GetRoot(Intersectable *object = NULL) const;
1018
1019  bool
1020  ValidLeaf(RssTreeLeaf *leaf) const;
1021
1022  void
1023  GenerateLeafRays(RssTreeLeaf *leaf,
1024                                   const int numberOfRays,
1025                                   SimpleRayContainer &rays);
1026
1027  void
1028  GenerateLeafRaysSimple(RssTreeLeaf *leaf,
1029                                                 const int numberOfRays,
1030                                                 SimpleRayContainer &rays);
1031       
1032
1033  void
1034  PickEdgeRays(RssTreeLeaf *leaf,
1035                           int &r1,
1036                           int &r2
1037                           );
1038
1039  int
1040  CollectRays(VssRayContainer &rays,
1041                          const int number);
1042
1043  int
1044  CollectRays(VssRayContainer &rays
1045                          );
1046
1047  void
1048  UpdatePvsSize(RssTreeLeaf *leaf);
1049
1050  void
1051  ComputeImportance(RssTreeLeaf *leaf);
1052 
1053  void
1054  SetPass(const int p) {
1055        mCurrentPass = p;
1056  }
1057 
1058  void GetRayContribution(const RssTreeNode::RayInfo &info,
1059                                                  float &weight,
1060                                                  float &contribution);
1061
1062  float
1063  GetSampleWeight(const int pass);
1064
1065  int
1066  RemoveInteriorRays(
1067                                         RssTreeLeaf *leaf
1068                                         );
1069
1070  bool
1071  IsRayConvexCombination(const RssTreeNode::RayInfo &ray,
1072                                                 const RssTreeNode::RayInfo &r1,
1073                                                 const RssTreeNode::RayInfo &r2,
1074                                                 const RssTreeNode::RayInfo &r3);
1075
1076  int
1077  PruneRaysRandom(RssTreeLeaf *leaf,
1078                                  const float ratio);
1079
1080  int
1081  PruneRaysContribution(RssTreeLeaf *leaf,
1082                                                const float ratio);
1083
1084  int
1085  PruneRays(
1086                        const int desired
1087                        );
1088 
1089
1090  void
1091  FindSilhouetteRays(RssTreeLeaf *leaf,
1092                                         vector<RssTreeLeaf::SilhouetteRays> &rays
1093                                         );
1094
1095  void
1096  PushRoots(std::priority_queue<TraversalData> &stack) const;
1097
1098  void
1099  PushRoots(std::stack<RssTreeNode *> &st) const;
1100
1101  void
1102  PushRoots(std::stack<RayTraversalData> &st, RssTreeNode::RayInfo &info) const;
1103
1104  void
1105  UpdateImportance(
1106                                   RssTreeNode *node);
1107
1108  void
1109  GenerateRay(float *params, SimpleRayContainer &rays);
1110
1111  void
1112  GenerateLeafRay(
1113                                  float *params,
1114                                  SimpleRayContainer &rays,
1115                                  const AxisAlignedBox3 &box,
1116                                  const AxisAlignedBox3 &dirBBox
1117                                  );
1118       
1119};
1120
1121
1122class RssBasedDistribution: public SamplingStrategy
1123{
1124 public:
1125  HaltonSequence mHalton;
1126  RssTree *mRssTree;
1127  // id of sampling pass (a pass is defined by two consecutive updates)
1128  int mPass;
1129
1130  RssBasedDistribution(Preprocessor &preprocessor):
1131        SamplingStrategy(preprocessor){
1132        mType = RSS_BASED_DISTRIBUTION;
1133        mRssTree = NULL;
1134        mPass = 0;
1135  }
1136 
1137  virtual void Update(VssRayContainer &vssRays);
1138  virtual bool RequiresRays() { return true; }
1139 
1140private:
1141
1142  virtual bool GenerateSample(SimpleRay &ray);
1143 
1144};
1145
1146
1147};
1148
1149#endif // __RSSTREE_H__
1150
Note: See TracBrowser for help on using the repository browser.