source: trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.h @ 395

Revision 395, 16.5 KB checked in by bittner, 19 years ago (diff)

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