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

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

removed using namespace std from .h

Line 
1#ifndef _KdTree_H__
2#define _KdTree_H__
3
4#include <functional>
5//
6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
10//#include "ObjectPvs.h"
11#include "Viewcell.h"
12#include "VssRay.h"
13//#include "IntersectableWrapper.h"
14#include "gzstream.h"
15
16namespace GtpVisibilityPreprocessor {
17
18class KdNode;
19class KdLeaf;
20class KdInterior;
21class Intersectable;
22class KdIntersectable;
23class Beam;
24class KdTree;
25//class KdViewCell;
26 
27  //  KdTree *SceneKdTree;
28
29// --------------------------------------------------------------
30// Static statistics for kd-tree search
31// --------------------------------------------------------------
32class KdTreeStatistics
33{
34public: 
35  // total number of nodes
36  int nodes;
37  // number of splits along each of the axes
38  int splits[7];
39  // totals number of rays
40  int rays;
41  // total number of query domains
42  int queryDomains;
43  // total number of ray references
44  int rayRefs;
45  // refs in non empty leafs
46  int rayRefsNonZeroQuery;
47  // total number of query references
48  int objectRefs;
49  // nodes with zero queries
50  int zeroQueryNodes;
51  // max depth nodes
52  int maxDepthNodes;
53  // max depth nodes
54  int minCostNodes;
55  // max number of rays per node
56  int maxObjectRefs;
57  // number of dynamically added ray refs
58  int addedRayRefs;
59  // number of dynamically removed ray refs
60  int removedRayRefs;
61 
62  // Constructor
63  KdTreeStatistics() {
64    Reset();
65  }
66
67  int Nodes() const {return nodes;}
68  int Interior() const { return nodes / 2; }
69  int Leaves() const { return (nodes / 2) + 1; }
70
71  void Reset() {
72    nodes = 0;
73    for (int i=0; i<7; i++)
74      splits[i] = 0;
75    rays = queryDomains = 0;
76    rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
77    zeroQueryNodes = 0;
78    maxDepthNodes = 0;
79    minCostNodes = 0;
80    maxObjectRefs = 0;
81    addedRayRefs = removedRayRefs = 0;
82  }
83
84  void
85  Print(std::ostream &app) const;
86
87  friend std::ostream &operator<<(std::ostream &s, const KdTreeStatistics &stat) {
88    stat.Print(s);
89    return s;
90  }
91 
92};
93
94 
95class KdInterior;
96/** Abstract class for kd-tree node */
97class KdNode {
98public:
99 
100  static int sMailId;
101  static int sReservedMailboxes;
102  int mMailbox;
103
104  KdIntersectable *mIntersectable;
105 
106  void Mail() { mMailbox = sMailId; }
107  //static void NewMail() { sMailId ++; }
108  bool Mailed() const { return mMailbox == sMailId; }
109 
110  static void NewMail(const int reserve = 1) {
111                sMailId += sReservedMailboxes;
112                sReservedMailboxes = reserve;
113        }
114        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
115        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
116
117  virtual ~KdNode(){};
118  KdNode(KdInterior *parent);
119
120  /** Determines whether this node is a leaf or interior node
121      @return true if leaf
122  */
123  virtual bool IsLeaf() const = 0;
124
125  /** Determines whether this node is the root of the tree
126      @return true if root
127  */
128  virtual bool IsRoot() const {
129    return mParent == NULL;
130  }
131
132  /** Parent of the node - the parent is a little overhead for maintanance of the tree,
133      but allows various optimizations of tree traversal algorithms */
134  KdInterior *mParent;
135  short mDepth;
136  short mPvsTermination;
137};
138
139/** Implementation of the kd-tree interior node */
140class KdInterior : public KdNode {
141
142public:
143   
144  KdInterior(KdInterior *parent):KdNode(parent), mBack(NULL), mFront(NULL) {}
145
146  ~KdInterior();
147
148  /** \sa KdNode::IsLeaf() */
149  virtual bool IsLeaf() const { return false; }
150
151  /** splitting axis */
152  int mAxis;
153  /** splitting position, absolute position within the bounding box of this node */
154  float mPosition;
155  /** bounding box of interior node */
156  AxisAlignedBox3 mBox;
157
158  /** back node */
159  KdNode *mBack;
160  /** front node */
161  KdNode *mFront;
162
163  void SetupChildLinks(KdNode *b, KdNode *f) {
164    mBack = b;
165    mFront = f;
166    b->mParent = f->mParent = this;
167  }
168 
169  void ReplaceChildLink(KdNode *oldChild, KdNode *newChild) {
170    if (mBack == oldChild)
171      mBack = newChild;
172    else
173      mFront = newChild;
174  }
175 
176 
177};
178 
179class SubdivisionCandidate;
180 
181/** Implementation of the kd-tree leaf node */
182class KdLeaf : public KdNode {
183public:
184  KdLeaf(KdInterior *parent, const int objects):
185          KdNode(parent), mViewCell(NULL) {
186    mObjects.reserve(objects);
187  }
188 
189  void AddPassingRay(const Ray &ray, const int contributions) {
190    mPassingRays.AddRay(ray, contributions);
191                //              Debug << "adding passing ray" << endl;
192  }
193
194  ~KdLeaf();
195       
196        void AddPassingRay2(const Ray &ray,
197                                                const int objects,
198                                                const int viewcells
199                                                ) {
200    mPassingRays.AddRay2(ray, objects, viewcells);
201                //              Debug << "adding passing ray" << endl;
202  }
203
204  /** \sa KdNode::IsLeaf()
205  */
206  virtual bool IsLeaf() const { return true; }
207
208
209  /// pointers to occluders contained in this node
210  ObjectContainer mObjects;
211
212  /// Ray set description of the rays passing through this node
213  PassingRaySet mPassingRays;
214       
215  /// PVS consisting of visible KdTree nodes
216  //KdPvs mKdPvs;
217
218  /// pvs of view cells seeing this node.
219  SubdivisionCandidate *mSubdivisionCandidate;
220
221  /// pointer to view cell.
222  KdViewCell *mViewCell;
223
224  VssRayContainer mVssRays;
225
226   /// Objects that are referenced in more than one leaf.
227  ObjectContainer mMultipleObjects;
228
229  /// universal counter
230  int mCounter;
231};
232
233
234/** KdTree for indexing scene entities - occluders/occludees/viewcells */
235class KdTree {
236 
237protected:
238  struct TraversalData
239  { 
240    KdNode *mNode;
241    AxisAlignedBox3 mBox;
242    int mDepth;
243    float mPriority;
244   
245    TraversalData() {}
246
247    TraversalData(KdNode *n, const float p):
248      mNode(n), mPriority(p)
249    {}
250   
251    TraversalData(KdNode *n,
252                   const AxisAlignedBox3 &b,
253                   const int d):
254      mNode(n), mBox(b), mDepth(d) {}
255   
256
257    bool operator<(
258                                   const TraversalData &b) const {
259      KdLeaf *leafa = (KdLeaf *) mNode;
260      KdLeaf *leafb = (KdLeaf *) b.mNode;
261      return
262                leafa->mObjects.size()*mBox.SurfaceArea()
263                <
264                leafb->mObjects.size()*b.mBox.SurfaceArea();
265    }
266
267
268    // comparator for the
269    struct less_priority : public
270    std::binary_function<const TraversalData, const TraversalData, bool> {
271     
272      bool operator()(const TraversalData a, const TraversalData b) {
273                                return a.mPriority < b.mPriority;
274      }
275     
276    };
277
278  };
279
280 
281
282public:
283
284  enum {SPLIT_OBJECT_MEDIAN,
285        SPLIT_SPATIAL_MEDIAN,
286        SPLIT_SAH};
287 
288  KdTree();
289
290  ~KdTree();
291   
292  /** Insert view cell into the tree */
293  virtual void InsertViewCell(ViewCell *viewCell) {
294    //      mRoot->mViewcells.push_back(viewCell);
295  }
296
297  virtual bool Construct();
298
299  /** Check whether subdivision criteria are met for the given subtree.
300      If not subdivide the leafs of the subtree. The criteria are specified in
301      the environment as well as the subdivision method. By default surface area
302      heuristics is used.
303       
304      @param subtree root of the subtree
305
306      @return true if subdivision was performed, false if subdivision criteria
307      were already met
308  */
309  virtual KdNode *Subdivide(const TraversalData &tdata);
310
311  /** Get the root of the tree */
312  KdNode *GetRoot() const {
313    return mRoot;
314  }
315
316
317  AxisAlignedBox3 GetBox() const { return mBox; }
318
319  int
320  CastRay(
321                  Ray &ray
322                  );
323 
324
325  int
326  CastBeam(
327                   Beam &beam
328                   );
329 
330 
331  /** Casts line segment into tree.
332          @returns intersected view cells.
333  */
334  int CastLineSegment(const Vector3 &origin,
335                                          const Vector3 &termination,
336                                          vector<ViewCell *> &viewcells);
337
338
339  const KdTreeStatistics &GetStatistics() const {
340    return mStat;
341  }
342
343  /** Returns or creates a new intersectable for use in a kd based pvs.
344          The OspTree is responsible for destruction of the intersectable.
345  */
346  KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);
347
348
349  void
350  SetPvsTerminationNodes(
351                                                 const float maxArea);
352 
353  KdNode *
354  GetPvsNode(const Vector3 &point) const;
355 
356
357  void
358  CollectKdObjects(const AxisAlignedBox3 &box,
359                                   ObjectContainer &objects
360                                   );
361
362  void
363  CollectObjects(KdNode *n, ObjectContainer &objects);
364
365  void
366  CollectObjects(const AxisAlignedBox3 &box,
367                                 ObjectContainer &objects);
368
369  void
370  CollectLeaves(vector<KdLeaf *> &leaves);
371       
372  /** If the kd tree is used as view cell container, this
373          methods creates the view cells.
374          @returns the newly created view cells in a view cell container
375  */
376  void
377  CreateAndCollectViewCells(ViewCellContainer &viewCells) const;
378
379  AxisAlignedBox3 GetBox(const KdNode *node) const {
380    KdInterior *parent = node->mParent;
381    if (parent == NULL)
382      return mBox;
383   
384    if (!node->IsLeaf())
385      return ((KdInterior *)node)->mBox;
386   
387    AxisAlignedBox3 box(parent->mBox);
388    if (parent->mFront == node)
389      box.SetMin(parent->mAxis, parent->mPosition);
390    else
391      box.SetMax(parent->mAxis, parent->mPosition);
392    return box;
393  }
394
395  float GetSurfaceArea(const KdNode *node) const {
396        return GetBox(node).SurfaceArea();
397  }
398
399 
400  KdNode *
401  FindRandomNeighbor(KdNode *n,
402                                         bool onlyUnmailed
403                                         );
404 
405  KdNode *
406  KdTree::GetRandomLeaf(const Plane3 &halfspace);
407
408  KdNode *
409  GetRandomLeaf(const bool onlyUnmailed = false);
410
411
412  KdNode *
413  GetNode(const Vector3 &point, const float maxArea) const;
414
415  void GetBoxIntersections(const AxisAlignedBox3 &box,
416                                                   vector<KdLeaf *> &leaves);
417
418  int
419  FindNeighbors(KdNode *n,
420                                vector<KdNode *> &neighbors,
421                                bool onlyUnmailed
422                                );
423
424  int
425  CollectLeafPvs();
426
427  bool ExportBinTree(const std::string &filename);
428  bool LoadBinTree(const std::string &filename, ObjectContainer &object);
429
430protected:
431
432  struct RayData {
433    // pointer to the actual ray
434    Ray *ray;
435   
436    // endpoints  - do we need them?
437#if USE_FIXEDPOINT_T
438    short tmin, tmax;
439#else
440    float tmin, tmax;
441#endif
442
443    RayData():ray(NULL) {}
444    RayData(Ray *r):ray(r), tmin(0),
445
446#if USE_FIXEDPOINT_T
447#define FIXEDPOINT_ONE 0x7FFE
448                          //                      tmax(0xFFFF)
449                          tmax(FIXEDPOINT_ONE)
450#else
451      tmax(1.0f)
452#endif
453    {}
454
455    RayData(Ray *r,
456            const float _min,
457            const float _max
458            ):ray(r) {
459      SetTMin(_min);
460      SetTMax(_max);
461    }
462
463    RayData(Ray *r,
464            const short _min,
465            const float _max
466            ):ray(r), tmin(_min) {
467      SetTMax(_max);
468    }
469
470    RayData(Ray *r,
471            const float _min,
472            const short _max
473            ):ray(r), tmax(_max) {
474      SetTMin(_min);
475    }
476
477    friend bool operator<(const RayData &a, const RayData &b) {
478      return a.ray < b.ray;
479    }
480   
481   
482    float ExtrapOrigin(const int axis) const {
483      return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis);
484    }
485   
486    float ExtrapTermination(const int axis) const {
487      return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis);
488    }
489   
490#if USE_FIXEDPOINT_T
491    float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); }
492    float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); }
493
494    void SetTMin (const float t) {
495      tmin = (short) (t*(float)(FIXEDPOINT_ONE));
496    }
497   
498    void SetTMax (const float t) {
499      tmax = (short) (t*(float)(FIXEDPOINT_ONE));
500      tmax++;
501      //      if (tmax!=0xFFFF)
502      //        tmax++;
503    }
504#else
505    float GetTMin () const { return tmin; }
506    float GetTMax () const { return tmax; }
507
508    void SetTMin (const float t) { tmin = t; }
509    void SetTMax (const float t) { tmax = t; }
510#endif
511  };
512
513  struct RayTraversalData {
514    KdNode *mNode;
515    Vector3 mExitPoint;
516    float mMaxT;
517   
518    RayTraversalData() {}
519    RayTraversalData(KdNode *n,
520                     const Vector3 &p,
521                     const float maxt):
522      mNode(n), mExitPoint(p), mMaxT(maxt) {}
523  };
524
525  // --------------------------------------------------------------
526  // For sorting objects
527  // --------------------------------------------------------------
528  struct  SortableEntry
529  {
530    enum {
531      BOX_MIN,
532      BOX_MAX
533    };
534   
535    int type;
536    float value;
537    Intersectable *intersectable;
538   
539    SortableEntry() {}
540    SortableEntry(const int t, const float v, Intersectable *i):type(t),
541                                                                value(v),
542                                                                intersectable(i) {}
543   
544    bool operator<(const SortableEntry &b) const {
545      return value < b.value;
546    }
547   
548  };
549
550  inline static bool iltS(SortableEntry *a, SortableEntry *b)
551  {
552          return a->value < b->value;
553  }
554
555  // reusable array of split candidates
556  vector<SortableEntry *> *splitCandidates;
557
558  float
559  BestCostRatio(
560                KdLeaf *node,
561                const AxisAlignedBox3 &box,
562                const int axis,
563                float &position,
564                int &objectsBack,
565                int &objectsFront
566                );
567
568  void
569  SortSubdivisionCandidates(
570                      KdLeaf *node,
571                      const int axis
572                      );
573
574  void
575  EvaluateLeafStats(const TraversalData &data);
576
577  KdNode *
578  SubdivideNode(
579                KdLeaf *leaf,
580                const AxisAlignedBox3 &box,
581                AxisAlignedBox3 &backBBox,
582                AxisAlignedBox3 &frontBBox
583                );
584
585  bool
586  TerminationCriteriaMet(const KdLeaf *leaf);
587 
588  int
589  SelectPlane(KdLeaf *leaf,
590              const AxisAlignedBox3 &box,
591              float &position
592              );
593
594        /** does some post processing on the objects in the new child leaves.
595        */
596        void ProcessMultipleRefs(KdLeaf *leaf) const;
597
598        void ExportBinLeaf(OUT_STREAM  &stream, KdLeaf *leaf);
599        void ExportBinInterior(OUT_STREAM &stream, KdInterior *interior);
600        KdLeaf *ImportBinLeaf(IN_STREAM &stream, KdInterior *parent, const ObjectContainer &objects);
601        KdInterior *ImportBinInterior(IN_STREAM  &stream, KdInterior *parent);
602        KdNode *LoadNextNode(IN_STREAM  &stream, KdInterior *parent, const ObjectContainer &objects);
603       
604        /** Adds this objects to the kd leaf objects.
605                @warning: Can corrupt the tree
606        */
607        void InsertObjects(KdNode *node, const ObjectContainer &objects);
608
609  int mTermMaxNodes;
610  float mSplitBorder;
611  int mTermMaxDepth;
612  int mTermMinCost;
613  float mMaxCostRatio;
614  float mCt_div_ci;
615  int mSplitMethod;
616  bool mSahUseFaces;
617  /// root of the tree
618  KdNode *mRoot;
619  /// bounding box of the tree root
620  AxisAlignedBox3 mBox;
621  KdTreeStatistics mStat;
622
623public:
624  /// stores the kd node intersectables used for pvs
625  vector<KdIntersectable *> mKdIntersectables;
626 
627};
628
629
630}
631
632#endif
Note: See TracBrowser for help on using the repository browser.