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

Revision 569, 22.1 KB checked in by bittner, 19 years ago (diff)

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