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

Revision 387, 16.3 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{
377public:
378  static int mailID;
379  int mailbox;
380 
381  RayInfoContainer rays;
382        int mPvsSize;
383 
384  VssTreeLeaf(VssTreeInterior *p,
385                                                        const int nRays
386                                                        ):VssTreeNode(p), rays(), mPvsSize(0) {
387    rays.reserve(nRays);
388  }
389 
390  virtual ~VssTreeLeaf() { }
391
392  virtual int Type() const  { return ELeaf; }
393
394  virtual void Print(ostream &s) const {
395    s<<endl<<"L: r="<<rays.size()<<endl;
396  };
397 
398  void AddRay(const RayInfo &data) {
399    rays.push_back(data);
400    data.mRay->Ref();
401  }
402
403  void Mail() { mailbox = mailID; }
404  static void NewMail() { mailID++; }
405  bool Mailed() const { return mailbox == mailID; }
406 
407  bool Mailed(const int mail) {
408    return mailbox >= mailID + mail;
409  }
410
411        float GetAvgRayContribution() const {
412                return mPvsSize/(float)rays.size();
413        }
414};
415
416// Inline functions
417inline
418VssTreeNode::VssTreeNode(VssTreeInterior *p):
419  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
420
421
422
423// ---------------------------------------------------------------
424// Main LSDS search class
425// ---------------------------------------------------------------
426class VssTree
427{
428  struct TraversalData
429  { 
430    VssTreeNode *node;
431    AxisAlignedBox3 bbox;
432    int depth;
433    float priority;
434   
435    TraversalData() {}
436
437    TraversalData(VssTreeNode *n, const float p):
438      node(n), priority(p)
439    {}
440
441    TraversalData(VssTreeNode *n,
442                   const AxisAlignedBox3 &b,
443                   const int d):
444      node(n), bbox(b), depth(d) {}
445   
446               
447    // comparator for the
448    struct less_priority : public
449    binary_function<const TraversalData, const TraversalData, bool> {
450                       
451      bool operator()(const TraversalData a, const TraversalData b) {
452                                return a.priority < b.priority;
453      }
454     
455    };
456
457    //    ~TraversalData() {}
458    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
459   
460    friend bool operator<(const TraversalData &a,
461                                                                                                        const TraversalData &b) {
462      //      return a.node->queries.size() < b.node->queries.size();
463      VssTreeLeaf *leafa = (VssTreeLeaf *) a.node;
464      VssTreeLeaf *leafb = (VssTreeLeaf *) b.node;
465#if 0
466                        return
467                                leafa->rays.size()*a.bbox.GetVolume()
468                                <
469                                leafb->rays.size()*b.bbox.GetVolume();
470#endif
471#if 1
472                        return
473                                leafa->mPvsSize*a.bbox.GetVolume()
474                                <
475                                leafb->mPvsSize*b.bbox.GetVolume();
476#endif
477#if 0
478                        return
479                                leafa->mPvsSize
480                                <
481                                leafb->mPvsSize;
482#endif
483#if 0
484                        return
485                                leafa->mPvsSize/(leafa->rays.size()+1)
486                                >
487                                leafb->mPvsSize/(leafb->rays.size()+1);
488#endif
489#if 0
490                        return
491                                leafa->mPvsSize*leafa->rays.size()
492                                <
493                                leafb->mPvsSize*leafb->rays.size();
494#endif
495    }
496  };
497 
498  // simplified data for ray traversal only...
499
500  struct RayTraversalData {
501   
502    VssTreeNode::RayInfo rayData;
503    VssTreeNode *node;
504   
505    RayTraversalData() {}
506    RayTraversalData(VssTreeNode *n,
507                                                                                 const VssTreeNode::RayInfo &data):
508      rayData(data), node(n) {}
509  };
510       
511public:
512  /////////////////////////////
513  // The core pointer
514  VssTreeNode *root;
515 
516  /////////////////////////////
517  // Basic properties
518
519  // total number of nodes of the tree
520  int nodes;
521  // axis aligned bounding box of the scene
522  AxisAlignedBox3 bbox;
523
524  // axis aligned bounding box of directions
525  AxisAlignedBox3 dirBBox;
526 
527  /////////////////////////////
528  // Construction parameters
529
530  // epsilon used for the construction
531  float epsilon;
532
533  // ratio between traversal and intersection costs
534  float ct_div_ci;
535  // max depth of the tree
536  int termMaxDepth;
537  // minimal ratio of the volume of the cell and the query volume
538  float termMinSize;
539
540        // minimal pvs per node to still get subdivided
541  int termMinPvs;
542
543  // maximal cost ration to subdivide a node
544  float termMaxCostRatio;
545       
546        // maximal contribution per ray to subdivide the node
547        float termMaxRayContribution;
548
549       
550  // randomized construction
551  bool randomize;
552
553  // type of the splitting to use fo rthe tree construction
554  enum {ESplitRegular, ESplitHeuristic };
555  int splitType;
556       
557  // maximal size of the box on which the refdir splitting can be performed
558  // (relative to the scene bbox
559  float refDirBoxMaxSize;
560 
561  // maximum alovable memory in MB
562  float maxTotalMemory;
563
564  // maximum alovable memory for static kd tree in MB
565  float maxStaticMemory;
566
567  // this is used during the construction depending
568  // on the type of the tree and queries...
569  float maxMemory;
570
571
572  // minimal acess time for collapse
573  int accessTimeThreshold;
574
575        // minimal depth at which to perform collapse
576  int minCollapseDepth;
577
578 
579  // reusable array of split candidates
580  vector<SortableEntry> *splitCandidates;
581  /////////////////////////////
582
583        VssStatistics stat;
584       
585 
586  VssTree();
587  virtual ~VssTree();
588
589  virtual void
590  Construct(
591                                                VssRayContainer &rays,
592                                                AxisAlignedBox3 *forcedBoundingBox = NULL
593                                                );
594       
595  // incemental construction
596  virtual void UpdateRays(VssRayContainer &remove,
597                                                                                                        VssRayContainer &add
598                                                                                                        );
599       
600 
601       
602  VssTreeNode *
603  Locate(const Vector3 &v);
604       
605  VssTreeNode *
606  SubdivideNode(VssTreeLeaf *leaf,
607                                                                const AxisAlignedBox3 &box,
608                                                                AxisAlignedBox3 &backBox,
609                                                                AxisAlignedBox3 &frontBox
610                                                                );
611       
612  VssTreeNode *
613  Subdivide(const TraversalData &tdata);
614       
615  int
616  SelectPlane(VssTreeLeaf *leaf,
617                                                        const AxisAlignedBox3 &box,
618                                                        float &position,
619                                                        int &raysBack,
620                                                        int &raysFront,
621                                                        int &pvsBack,
622                                                        int &pvsFront
623                                                        );
624
625  void
626  SortSplitCandidates(
627                                                                                        VssTreeLeaf *node,
628                                                                                        const int axis
629                                                                                        );
630       
631 
632  // return memory usage in MB
633  float GetMemUsage() const {
634    return
635      (sizeof(VssTree) +
636       stat.Leaves()*sizeof(VssTreeLeaf) +
637       stat.Interior()*sizeof(VssTreeInterior) +
638       stat.rayRefs*sizeof(VssTreeNode::RayInfo))/(1024.0f*1024.0f);
639  }
640       
641  float GetRayMemUsage() const {
642    return
643      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
644  }
645 
646        float
647        BestCostRatioHeuristic(
648                                                                                                 VssTreeLeaf *node,
649                                                                                                 int &axis,
650                                                                                                 float &position,
651                                                                                                 int &raysBack,
652                                                                                                 int &raysFront,
653                                                                                                 int &pvsBack,
654                                                                                                 int &pvsFront
655                                                                                                 );
656
657        float
658        BestCostRatioRegular(
659                                                                                         VssTreeLeaf *node,
660                                                                                         int &axis,
661                                                                                         float &position,
662                                                                                         int &raysBack,
663                                                                                         int &raysFront,
664                                                                                         int &pvsBack,
665                                                                                         int &pvsFront
666
667                                                                                         );
668       
669        float
670        EvalCostRatio(
671                                                                VssTreeLeaf *node,
672                                                                const int axis,
673                                                                const float position,
674                                                                int &raysBack,
675                                                                int &raysFront,
676                                                                int &pvsBack,
677                                                                int &pvsFront
678                                                                );
679
680  AxisAlignedBox3 GetBBox(const VssTreeNode *node) {
681    if (node->parent == NULL)
682      return bbox;
683
684    if (!node->IsLeaf())
685      return ((VssTreeInterior *)node)->bbox;
686
687    if (node->parent->axis >= 3)
688      return node->parent->bbox;
689     
690    AxisAlignedBox3 box(node->parent->bbox);
691    if (node->parent->front == node)
692      box.SetMin(node->parent->axis, node->parent->position);
693    else
694      box.SetMax(node->parent->axis, node->parent->position);
695    return box;
696  }
697
698  AxisAlignedBox3 GetDirBBox(const VssTreeNode *node) {
699
700    if (node->parent == NULL)
701      return dirBBox;
702   
703    if (!node->IsLeaf() )
704      return ((VssTreeInterior *)node)->dirBBox;
705
706    if (node->parent->axis < 3)
707      return node->parent->dirBBox;
708   
709    AxisAlignedBox3 dBBox(node->parent->dirBBox);
710
711    if (node->parent->front == node)
712      dBBox.SetMin(node->parent->axis - 3, node->parent->position);
713    else
714      dBBox.SetMax(node->parent->axis - 3, node->parent->position);
715    return dBBox;
716  }
717 
718  int
719  ReleaseMemory(const int time);
720
721  int
722  CollapseSubtree(VssTreeNode *node, const int time);
723
724  void
725  CountAccess(VssTreeInterior *node, const long time) {
726    node->accesses++;
727    node->lastAccessTime = time;
728  }
729
730  VssTreeNode *
731  SubdivideLeaf(
732                                                                VssTreeLeaf *leaf,
733                                                                const float SAThreshold
734                                                                );
735
736  void
737  RemoveRay(VssRay *ray,
738                                                vector<VssTreeLeaf *> *affectedLeaves,
739                                                const bool removeAllScheduledRays
740                                                );
741
742  void
743  AddRay(VssRay *ray);
744       
745  void
746  TraverseInternalNode(
747                                                                                         RayTraversalData &data,
748                                                                                         stack<RayTraversalData> &tstack);
749
750        void
751  EvaluateLeafStats(const TraversalData &data);
752
753        void
754        EvalLeafPvs(VssTreeLeaf *leaf);
755
756        int
757        GetRootPvsSize() const {
758                return GetPvsSize(root, bbox);
759        }
760       
761        int
762        GetPvsSize(VssTreeNode *node, const AxisAlignedBox3 &box) const;
763       
764};
765
766
767#endif // __LSDS_KDTREE_H__
768
Note: See TracBrowser for help on using the repository browser.