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

Revision 469, 18.0 KB checked in by mattausch, 19 years ago (diff)

updated view cells, view cell manager. changed rendersimulator

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