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

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

removed using namespace std from .h

RevLine 
[372]1// ================================================================
2// $Id$
3// ****************************************************************
4//
5// Initial coding by
6/**
7   @author Jiri Bittner
8*/
9
10#ifndef __VSSTREE_H__
11#define __VSSTREE_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"
[860]23#include "Statistics.h"
24#include "Ray.h"
[372]25
[860]26namespace GtpVisibilityPreprocessor {
[372]27
28#define USE_KDNODE_VECTORS 1
29#define _RSS_STATISTICS
30#define _RSS_TRAVERSAL_STATISTICS
31
[2105]32class SimpleRayContainer;
[372]33
34
35// --------------------------------------------------------------
36// Static statistics for kd-tree search
37// --------------------------------------------------------------
38class VssStatistics :
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;
[438]48  // initial size of the pvs
[382]49  int initialPvsSize;
[438]50  // total number of query domains
[372]51  int queryDomains;
52  // total number of ray references
53  int rayRefs;
[382]54
[438]55  // max depth nodes
[372]56  int maxDepthNodes;
57  // max depth nodes
[403]58  int minPvsNodes;
59  int minRaysNodes;
[438]60  // max ray contribution nodes
[382]61  int maxRayContribNodes;
[438]62  // max depth nodes
[382]63  int minSizeNodes;
[427]64  int maxCostRatioNodes;
65
[372]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  // Constructor
74  VssStatistics() {
75    Reset();
76  }
77
78  int Nodes() const {return nodes;}
79  int Interior() const { return nodes/2; }
80  int Leaves() const { return (nodes/2) + 1; }
81
82  void Reset() {
83    nodes = 0;
84    for (int i=0; i<7; i++)
85      splits[i] = 0;
86    rays = queryDomains = 0;
[382]87    rayRefs = 0;
[372]88    maxDepthNodes = 0;
[403]89    minPvsNodes = 0;
90    minRaysNodes = 0;
[372]91    maxRayRefs = 0;
92    addedRayRefs = removedRayRefs = 0;
[438]93        initialPvsSize = 0;
94        maxRayContribNodes = 0;
95        minSizeNodes = 0;
96        maxCostRatioNodes = 0;
[372]97  }
98
99 
100  void
[2176]101  Print(std::ostream &app) const;
[372]102
[2176]103  friend std::ostream &operator<<(std::ostream &s, const VssStatistics &stat) {
[372]104    stat.Print(s);
105    return s;
106  }
107 
108};
109
110
111
112
113class VssTreeInterior;
114
115
116// --------------------------------------------------------------
117// KD-tree node - abstract class
118// --------------------------------------------------------------
119class VssTreeNode
120{
121public:
122
[427]123#define USE_FIXEDPOINT_T 0
[372]124
[438]125  struct RayInfo
126  {
[372]127        // pointer to the actual ray
128        VssRay *mRay;
129       
130        // endpoints  - do we need them?
131#if USE_FIXEDPOINT_T
132        short mMinT, mMaxT;
133#else
134        float mMinT, mMaxT;
135#endif
136       
137        RayInfo():mRay(NULL) {}
138       
139        RayInfo(VssRay *r):mRay(r), mMinT(0),
140#if USE_FIXEDPOINT_T
141#define FIXEDPOINT_ONE 0x7FFE
[438]142                                           //                     mMaxT(0xFFFF)
143                                           mMaxT(FIXEDPOINT_ONE)
[372]144#else
[438]145          mMaxT(1.0f)
[372]146#endif
147        {}
148       
149        RayInfo(VssRay *r,
[438]150                        const float _min,
151                        const float _max
152                        ):mRay(r) {
153          SetMinT(_min);
154          SetMaxT(_max);
[372]155        }
156       
157        RayInfo(VssRay *r,
[438]158                        const short _min,
159                        const float _max
160                        ):mRay(r), mMinT(_min) {
161          SetMaxT(_max);
[372]162        }
163       
164        RayInfo(VssRay *r,
[438]165                        const float _min,
166                        const short _max
167                        ):mRay(r), mMaxT(_max) {
168          SetMinT(_min);
[372]169        }
[427]170
171        enum {
[438]172          SOURCE_RAY = 0,
173          TERMINATION_RAY,
174          PASSING_RAY,
175          CONTAINED_RAY
[427]176        };
[372]177       
[427]178        int GetRayClass() const {
179               
[438]180          bool startsBefore = GetMinT() > 0.0f;
181          bool terminatesAfter = GetMaxT() < 1.0f;
[427]182               
[438]183          if (startsBefore && terminatesAfter)
184                return PASSING_RAY;
[427]185
[438]186          if (!startsBefore && !terminatesAfter)
187                return CONTAINED_RAY;
[427]188               
[438]189          if (!startsBefore)
190                return SOURCE_RAY;
[427]191               
[438]192          return TERMINATION_RAY;
[427]193        }
194       
[372]195        friend bool operator<(const RayInfo &a, const RayInfo &b) {
[438]196          return a.mRay < b.mRay;
[372]197        }
198 
199       
200        float ExtrapOrigin(const int axis) const {
[438]201          return mRay->GetOrigin(axis) + GetMinT()*mRay->GetDir(axis);
[372]202        }
203       
204        float ExtrapTermination(const int axis) const {
[438]205          return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis);
[372]206        }
[434]207
208        Vector3 Extrap(const float t) const {
[438]209          return mRay->Extrap(t);
[434]210        }
[372]211       
212#if USE_FIXEDPOINT_T
213        float GetMinT () const { return mMinT/(float)(FIXEDPOINT_ONE); }
214        float GetMaxT () const { return mMaxT/(float)(FIXEDPOINT_ONE); }
215       
216        void SetMinT (const float t) {
[438]217          mMinT = (short) (t*(float)(FIXEDPOINT_ONE));
[372]218        }
219       
220        void SetMaxT (const float t) {
[438]221          mMaxT = (short) (t*(float)(FIXEDPOINT_ONE));
222          mMaxT++;
223          //      if (mMaxT!=0xFFFF)
224          //    mMaxT++;
[372]225        }
226#else
227        float GetMinT () const { return mMinT; }
228        float GetMaxT () const { return mMaxT; }
229       
230        void SetMinT (const float t) { mMinT = t; }
231        void SetMaxT (const float t) { mMaxT = t; }
232#endif
[382]233
234
[438]235        int ComputeRayIntersection(const int axis,
236                                                           const float position,
237                                                           float &t
238                                                           ) const {
[382]239               
[446]240#if 1
[438]241          // intersect the ray with the plane
242          float denom = mRay->GetDir(axis);
[382]243   
[438]244          if (fabs(denom) < 1e-20)
245                //if (denom == 0.0f)
246                return (mRay->GetOrigin(axis) > position) ? 1 : -1;
[382]247   
[438]248          t = (position - mRay->GetOrigin(axis))/denom;
[382]249
[438]250          if (t < GetMinT())
251                return (denom > 0) ? 1 : -1;
[382]252
[438]253          if (t > GetMaxT())
254                return (denom > 0) ? -1 : 1;
[382]255
[438]256          return 0;
[446]257#else
258          // subbdivision based only on the origin
259          t = 0;
260          float rpos = mRay->GetOrigin(axis);
261          return (rpos < position) ? -1 : 1;
262
263#endif
[382]264        }
265
266
[438]267  };
[372]268
[1259]269  void GetSampleData(const bool isTerminaton,
270                                  Vector3 &pt,
271                                  Intersectable **obj,
272                                  KdNode **node) const;
[372]273
[438]274  typedef vector<RayInfo> RayInfoContainer;
[372]275       
276  enum { EInterior, ELeaf };
277
278  /////////////////////////////////
279  // The actual data goes here
280 
281  // link to the parent
282  VssTreeInterior *parent;
283
284  enum {SPLIT_X=0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
285 
286  // splitting axis
287  char axis;
288       
289  // depth
290  unsigned char depth;
291 
292  //  short depth;
293  //
294  /////////////////////////////////
295 
296  inline VssTreeNode(VssTreeInterior *p);
297
298 
299  virtual ~VssTreeNode() {};
300  virtual int Type() const  = 0;
301 
302
303  bool IsLeaf() const { return axis == -1; }
304 
[2176]305  virtual void Print(std::ostream &s) const = 0;
[372]306
307  virtual int GetAccessTime() {
308    return 0x7FFFFFF;
309  }
310
311 
312       
313};
314
315// --------------------------------------------------------------
316// KD-tree node - interior node
317// --------------------------------------------------------------
318class VssTreeInterior :
319  public VssTreeNode
320{
321public:
322  // plane in local modelling coordinates
323  float position;
324
325  // pointers to children
326  VssTreeNode *back, *front;
327
328  // the bbox of the node
329  AxisAlignedBox3 bbox;
330
331  // the bbox of the node
332  AxisAlignedBox3 dirBBox;
333 
334  // data for caching
335  long accesses;
336  long lastAccessTime;
337 
338  VssTreeInterior(VssTreeInterior *p):VssTreeNode(p),
[438]339                                                                          back(NULL),
340                                                                          front(NULL),
341                                                                          accesses(0),
342                                                                          lastAccessTime(-1)
[372]343  { }
344
345  virtual int GetAccessTime() {
346    return lastAccessTime;
347  }
348
349  void SetupChildLinks(VssTreeNode *b, VssTreeNode *f) {
350    back = b;
351    front = f;
352    b->parent = f->parent = this;
353  }
354
355  void ReplaceChildLink(VssTreeNode *oldChild, VssTreeNode *newChild) {
356    if (back == oldChild)
357      back = newChild;
358    else
359      front = newChild;
360  }
361
362  virtual int Type() const  { return EInterior; }
363 
364  virtual ~VssTreeInterior() {
365    if (back)
366      delete back;
367    if (front)
368      delete front;
369  }
370 
[2176]371  virtual void Print(std::ostream &s) const {
[372]372    if (axis == 0)
373      s<<"x ";
374    else
375      if (axis == 1)
[438]376                s<<"y ";
[372]377      else
[438]378                s<<"z ";
[372]379    s<<position<<" ";
380    back->Print(s);
381    front->Print(s);
382  }
383
384 
[382]385       
[372]386  int ComputeRayIntersection(const RayInfo &rayData,
[438]387                                                         float &t
388                                                         ) {
389        return rayData.ComputeRayIntersection(axis, position, t);
[372]390  }
391
392};
393
394
395// --------------------------------------------------------------
396// KD-tree node - leaf node
397// --------------------------------------------------------------
398class VssTreeLeaf :
399  public VssTreeNode
400{
[395]401private:
[438]402  int mPvsSize;
[372]403public:
404  static int mailID;
405  int mailbox;
406 
407  RayInfoContainer rays;
[438]408  int mPassingRays;
[434]409       
[438]410  bool mValidPvs;
411  float mEntropyImportance;
412 
[395]413       
[382]414  VssTreeLeaf(VssTreeInterior *p,
[438]415                          const int nRays
416                          ):VssTreeNode(p), rays(), mPvsSize(0), mPassingRays(0), mValidPvs(false) {
[382]417    rays.reserve(nRays);
[372]418  }
419 
420  virtual ~VssTreeLeaf() { }
421
422  virtual int Type() const  { return ELeaf; }
423
[2176]424  virtual void Print(std::ostream &s) const {
425    s<<std::endl<<"L: r="<<(int)rays.size()<<std::endl;
[372]426  };
427 
428  void AddRay(const RayInfo &data) {
[438]429        mValidPvs = false;
[372]430    rays.push_back(data);
431    data.mRay->Ref();
[438]432        if (data.GetRayClass() == RayInfo::PASSING_RAY)
433          mPassingRays++;
[372]434  }
[395]435       
[438]436  int GetPvsSize() const {
437        return mPvsSize;
438  }
[372]439
[438]440  void SetPvsSize(const int s) {
441        mPvsSize = s;
442        mValidPvs = true;
443  }
[395]444
[438]445  void
446  UpdatePvsSize();
447
448  float
449  ComputePvsEntropy();
450 
451  float
452  ComputeRayLengthEntropy();
453 
454  float
455  ComputeRayTerminationEntropy();
456 
457  void
458  ComputeEntropyImportance();
459
[372]460  void Mail() { mailbox = mailID; }
461  static void NewMail() { mailID++; }
462  bool Mailed() const { return mailbox == mailID; }
463 
464  bool Mailed(const int mail) {
465    return mailbox >= mailID + mail;
466  }
467
[438]468  float GetAvgRayContribution() const {
469        return GetPvsSize()/((float)rays.size() + Limits::Small);
470  }
[403]471
[435]472  float GetImportance() const;
[438]473 
474  float GetSqrRayContribution() const {
475        return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
476  }
477 
478  // comparator for the
479  struct less_contribution : public
[2176]480  std::binary_function<const VssTreeLeaf *, const VssTreeLeaf *, bool> {
[438]481       
482        bool operator()(const VssTreeLeaf * a, const VssTreeLeaf *b) {
483          return a->GetAvgRayContribution() < b->GetAvgRayContribution();
[403]484        }
[438]485  };
486 
487  struct greater_contribution : public
[2176]488  std::binary_function<const VssTreeLeaf *, const VssTreeLeaf *, bool> {
[427]489       
[438]490        bool operator()(const VssTreeLeaf * a, const VssTreeLeaf *b) {
491          return a->GetAvgRayContribution() > b->GetAvgRayContribution();
[427]492        }
[438]493  };
494 
495  friend bool GreaterContribution(const VssTreeLeaf * a, const VssTreeLeaf *b) {
496        return a->GetAvgRayContribution() > b->GetAvgRayContribution();
497  }
498 
[372]499};
500
501// Inline functions
502inline
503VssTreeNode::VssTreeNode(VssTreeInterior *p):
504  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
505
506
507
508// ---------------------------------------------------------------
509// Main LSDS search class
510// ---------------------------------------------------------------
511class VssTree
512{
513  struct TraversalData
514  { 
515    VssTreeNode *node;
516    AxisAlignedBox3 bbox;
517    int depth;
518    float priority;
519   
520    TraversalData() {}
521
522    TraversalData(VssTreeNode *n, const float p):
523      node(n), priority(p)
524    {}
525
526    TraversalData(VssTreeNode *n,
[438]527                                  const AxisAlignedBox3 &b,
528                                  const int d):
[372]529      node(n), bbox(b), depth(d) {}
530   
531               
532    // comparator for the
533    struct less_priority : public
[2176]534    std::binary_function<const TraversalData, const TraversalData, bool> {
[372]535                       
536      bool operator()(const TraversalData a, const TraversalData b) {
[438]537                return a.priority < b.priority;
[372]538      }
539     
540    };
541
542    //    ~TraversalData() {}
543    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
544   
545    friend bool operator<(const TraversalData &a,
[438]546                                                  const TraversalData &b) {
[372]547      //      return a.node->queries.size() < b.node->queries.size();
548      VssTreeLeaf *leafa = (VssTreeLeaf *) a.node;
549      VssTreeLeaf *leafb = (VssTreeLeaf *) b.node;
[386]550#if 0
[438]551          return
552                leafa->rays.size()*a.bbox.GetVolume()
553                <
554                leafb->rays.size()*b.bbox.GetVolume();
[386]555#endif
[434]556#if 0
[438]557          return
558                leafa->GetPvsSize()*a.bbox.GetVolume()
559                <
560                leafb->GetPvsSize()*b.bbox.GetVolume();
[386]561#endif
562#if 0
[438]563          return
564                leafa->GetPvsSize()
565                <
566                leafb->GetPvsSize();
[386]567#endif
[387]568#if 0
[438]569          return
570                leafa->GetPvsSize()/(leafa->rays.size()+1)
571                >
572                leafb->GetPvsSize()/(leafb->rays.size()+1);
[386]573#endif
[434]574#if 1
[438]575          return
576                leafa->GetPvsSize()*leafa->rays.size()
577                <
578                leafb->GetPvsSize()*leafb->rays.size();
[386]579#endif
[372]580    }
581  };
582 
583  // simplified data for ray traversal only...
584
585  struct RayTraversalData {
586   
587    VssTreeNode::RayInfo rayData;
588    VssTreeNode *node;
589   
590    RayTraversalData() {}
591    RayTraversalData(VssTreeNode *n,
[438]592                                         const VssTreeNode::RayInfo &data):
[372]593      rayData(data), node(n) {}
594  };
595       
596public:
597  /////////////////////////////
598  // The core pointer
599  VssTreeNode *root;
600 
601  /////////////////////////////
602  // Basic properties
603
604  // total number of nodes of the tree
605  int nodes;
606  // axis aligned bounding box of the scene
607  AxisAlignedBox3 bbox;
608
609  // axis aligned bounding box of directions
610  AxisAlignedBox3 dirBBox;
611 
612  /////////////////////////////
613  // Construction parameters
614
615  // epsilon used for the construction
616  float epsilon;
617
618  // ratio between traversal and intersection costs
619  float ct_div_ci;
620  // max depth of the tree
621  int termMaxDepth;
622  // minimal ratio of the volume of the cell and the query volume
623  float termMinSize;
624
[438]625  // minimal pvs per node to still get subdivided
[382]626  int termMinPvs;
627
[438]628  // minimal ray number per node to still get subdivided
[403]629  int termMinRays;
630       
[382]631  // maximal cost ration to subdivide a node
632  float termMaxCostRatio;
633       
[438]634  // maximal contribution per ray to subdivide the node
635  float termMaxRayContribution;
[382]636
637       
[372]638  // randomized construction
639  bool randomize;
[438]640 
[372]641  // type of the splitting to use fo rthe tree construction
[434]642  enum {ESplitRegular, ESplitHeuristic, ESplitHybrid };
[372]643  int splitType;
[434]644
[438]645  bool mSplitUseOnlyDrivingAxis;
646 
647  // use ray space subdivision instead of view space subdivision
648  bool mUseRss;
[434]649
[438]650  // interleave directional and spatial splits based on their costs
651  // if false directional splits are only performed after spatial splits
652  bool mInterleaveDirSplits;
653
654  // depth at which directional splits are performed if mInterleaveDirSplits is false
655  int mDirSplitDepth;
656 
[372]657  // maximal size of the box on which the refdir splitting can be performed
658  // (relative to the scene bbox
659  float refDirBoxMaxSize;
660 
661  // maximum alovable memory in MB
662  float maxTotalMemory;
663
664  // maximum alovable memory for static kd tree in MB
665  float maxStaticMemory;
666
667  // this is used during the construction depending
668  // on the type of the tree and queries...
669  float maxMemory;
670
671
672  // minimal acess time for collapse
673  int accessTimeThreshold;
674
[438]675  // minimal depth at which to perform collapse
[372]676  int minCollapseDepth;
677
678 
679  // reusable array of split candidates
[382]680  vector<SortableEntry> *splitCandidates;
[372]681  /////////////////////////////
682
[438]683  VssStatistics stat;
[372]684       
685 
686  VssTree();
687  virtual ~VssTree();
688
689  virtual void
690  Construct(
[438]691                        VssRayContainer &rays,
692                        AxisAlignedBox3 *forcedBoundingBox = NULL
693                        );
[372]694       
695  // incemental construction
696  virtual void UpdateRays(VssRayContainer &remove,
[438]697                                                  VssRayContainer &add
698                                                  );
[401]699
[438]700  virtual void AddRays(
701                                           VssRayContainer &add
702                                           )
703  {
704        VssRayContainer remove;
705        UpdateRays(remove, add);
706  }
[401]707
[372]708 
709       
710  VssTreeNode *
711  Locate(const Vector3 &v);
712       
713  VssTreeNode *
714  SubdivideNode(VssTreeLeaf *leaf,
[438]715                                const AxisAlignedBox3 &box,
716                                AxisAlignedBox3 &backBox,
717                                AxisAlignedBox3 &frontBox
718                                );
[372]719       
720  VssTreeNode *
721  Subdivide(const TraversalData &tdata);
722       
723  int
724  SelectPlane(VssTreeLeaf *leaf,
[438]725                          const AxisAlignedBox3 &box,
726                          float &position,
727                          int &raysBack,
728                          int &raysFront,
729                          int &pvsBack,
730                          int &pvsFront
731                          );
[372]732
733  void
[1233]734  SortSubdivisionCandidates(
[438]735                                          VssTreeLeaf *node,
736                                          const int axis
737                                          );
[372]738       
739 
740  // return memory usage in MB
741  float GetMemUsage() const {
742    return
743      (sizeof(VssTree) +
744       stat.Leaves()*sizeof(VssTreeLeaf) +
745       stat.Interior()*sizeof(VssTreeInterior) +
746       stat.rayRefs*sizeof(VssTreeNode::RayInfo))/(1024.0f*1024.0f);
747  }
748       
749  float GetRayMemUsage() const {
750    return
751      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
752  }
753 
[386]754
[438]755  float
756  BestCostRatio(
757                                VssTreeLeaf *node,
758                                int &axis,
759                                float &position,
760                                int &raysBack,
761                                int &raysFront,
762                                int &pvsBack,
763                                int &pvsFront
764                                );
[382]765       
[438]766  float
767  EvalCostRatio(
768                                VssTreeLeaf *node,
769                                const int axis,
770                                const float position,
771                                int &raysBack,
772                                int &raysFront,
773                                int &pvsBack,
774                                int &pvsFront
775                                );
[372]776
[438]777  float
778  EvalCostRatioHeuristic(
779                                                 VssTreeLeaf *node,
780                                                 const int axis,
781                                                 float &position,
782                                                 int &raysBack,
783                                                 int &raysFront,
784                                                 int &pvsBack,
785                                                 int &pvsFront
786                                                 );
[434]787
[438]788  float
789  GetCostRatio(
790                           VssTreeLeaf *leaf,
791                           const int axis,
792                           const float position,
793                           const int raysBack,
794                           const int raysFront,
795                           const int pvsBack,
796                           const int pvsFront
797                           );
[434]798
799  AxisAlignedBox3 GetBBox(const VssTreeNode *node) const {
[372]800    if (node->parent == NULL)
801      return bbox;
802
803    if (!node->IsLeaf())
804      return ((VssTreeInterior *)node)->bbox;
805
806    if (node->parent->axis >= 3)
807      return node->parent->bbox;
808     
809    AxisAlignedBox3 box(node->parent->bbox);
810    if (node->parent->front == node)
811      box.SetMin(node->parent->axis, node->parent->position);
812    else
813      box.SetMax(node->parent->axis, node->parent->position);
814    return box;
815  }
816
[434]817  AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) const {
[372]818
819    if (node->parent == NULL)
820      return dirBBox;
821   
822    if (!node->IsLeaf() )
823      return ((VssTreeInterior *)node)->dirBBox;
824
825    if (node->parent->axis < 3)
826      return node->parent->dirBBox;
827   
828    AxisAlignedBox3 dBBox(node->parent->dirBBox);
829
830    if (node->parent->front == node)
831      dBBox.SetMin(node->parent->axis - 3, node->parent->position);
832    else
833      dBBox.SetMax(node->parent->axis - 3, node->parent->position);
834    return dBBox;
835  }
836 
837  int
838  ReleaseMemory(const int time);
839
840  int
841  CollapseSubtree(VssTreeNode *node, const int time);
842
843  void
844  CountAccess(VssTreeInterior *node, const long time) {
845    node->accesses++;
846    node->lastAccessTime = time;
847  }
848
849  VssTreeNode *
850  SubdivideLeaf(
[438]851                                VssTreeLeaf *leaf
852                                );
[372]853
854  void
855  RemoveRay(VssRay *ray,
[438]856                        vector<VssTreeLeaf *> *affectedLeaves,
857                        const bool removeAllScheduledRays
858                        );
[372]859
[438]860  //  void
861  //  AddRay(VssRay *ray);
[372]862  void
[438]863  AddRay(VssTreeNode::RayInfo &info);
864 
865  void
[372]866  TraverseInternalNode(
[438]867                                           RayTraversalData &data,
[2176]868                                           std::stack<RayTraversalData> &tstack);
[372]869
[438]870  void
[372]871  EvaluateLeafStats(const TraversalData &data);
872
[382]873
[438]874  int
875  GetRootPvsSize() const {
876        return GetPvsSize(bbox);
877  }
878 
879  int
880  GetPvsSize(const AxisAlignedBox3 &box) const;
[401]881
[438]882  void
883  GetRayContributionStatistics(
884                                                           float &minRayContribution,
885                                                           float &maxRayContribution,
886                                                           float &avgRayContribution
887                                                           );
[401]888
[438]889  int
890  GenerateRays(const float ratioPerLeaf,
891                           SimpleRayContainer &rays);
[401]892
[438]893  int
894  GenerateRays(const int numberOfRays,
895                           const int numberOfLeaves,
896                           SimpleRayContainer &rays);
[427]897               
[438]898  float
899  GetAvgPvsSize();
[401]900
[438]901  int
902  UpdateSubdivision();
[427]903
[438]904  bool
905  TerminationCriteriaSatisfied(VssTreeLeaf *leaf);
[427]906
[438]907  void
908  CollectLeaves(vector<VssTreeLeaf *> &leaves);
[427]909
[438]910  bool
911  ClipRay(
912                  VssTreeNode::RayInfo &rayInfo,
913                  const AxisAlignedBox3 &box
914                  );
[427]915
[438]916  VssTreeNode *GetRoot() const { return root; }
[434]917
[438]918  bool
919  ValidLeaf(VssTreeLeaf *leaf) const;
[434]920
[438]921  void
922  GenerateLeafRays(VssTreeLeaf *leaf,
923                                   const int numberOfRays,
924                                   SimpleRayContainer &rays);
[434]925
[466]926  int
927  CollectRays(VssRayContainer &rays,
928                          const int number);
[434]929
[466]930  int
[863]931  CollectRays(VssRayContainer &rays);
[466]932 
[372]933};
934
[863]935};
[372]936
937#endif // __LSDS_KDTREE_H__
938
Note: See TracBrowser for help on using the repository browser.