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

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

per object rss tree support - changes in glrenderer.cpp so tha it compiles; unix2dos on glrenderer.*

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