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

Revision 2618, 14.8 KB checked in by bittner, 17 years ago (diff)

skip cast line segment for consequent line segments with oposite dirs

RevLine 
[372]1#ifndef _KdTree_H__
2#define _KdTree_H__
3
4#include <functional>
[2176]5//
[372]6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
[2116]10//#include "ObjectPvs.h"
[2575]11#include "ViewCell.h"
[1184]12#include "VssRay.h"
[2116]13//#include "IntersectableWrapper.h"
14#include "gzstream.h"
[860]15
16namespace GtpVisibilityPreprocessor {
17
[2116]18class KdNode;
19class KdLeaf;
20class KdInterior;
21class Intersectable;
22class KdIntersectable;
23class Beam;
24class KdTree;
25//class KdViewCell;
[1112]26 
27  //  KdTree *SceneKdTree;
28
[372]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;}
[1176]68  int Interior() const { return nodes / 2; }
69  int Leaves() const { return (nodes / 2) + 1; }
[372]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
[2176]85  Print(std::ostream &app) const;
[372]86
[2176]87  friend std::ostream &operator<<(std::ostream &s, const KdTreeStatistics &stat) {
[372]88    stat.Print(s);
89    return s;
90  }
91 
92};
93
94 
95class KdInterior;
96/** Abstract class for kd-tree node */
97class KdNode {
[2575]98
99public: 
[1613]100  static int sMailId;
101  static int sReservedMailboxes;
[1176]102  int mMailbox;
[1761]103
104  KdIntersectable *mIntersectable;
[1176]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) {
[2575]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; }
[372]116
[1002]117  virtual ~KdNode(){};
[372]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;
[1989]135  short mDepth;
136  short mPvsTermination;
[372]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
[1002]146  ~KdInterior();
147
[372]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 
[1233]179class SubdivisionCandidate;
[372]180 
181/** Implementation of the kd-tree leaf node */
182class KdLeaf : public KdNode {
183public:
[469]184  KdLeaf(KdInterior *parent, const int objects):
[2575]185          KdNode(parent), mViewCell(NULL), mVboId(-1),
186          mIndexBufferStart(0), mIndexBufferSize(0) {
[372]187    mObjects.reserve(objects);
188  }
189 
[469]190  void AddPassingRay(const Ray &ray, const int contributions) {
[372]191    mPassingRays.AddRay(ray, contributions);
192                //              Debug << "adding passing ray" << endl;
193  }
194
[1999]195  ~KdLeaf();
[372]196       
[2575]197  void AddPassingRay2(const Ray &ray,
198                      const int objects,
199                      const int viewcells
200                      ) {
[372]201    mPassingRays.AddRay2(ray, objects, viewcells);
202                //              Debug << "adding passing ray" << endl;
203  }
204
[2117]205  /** \sa KdNode::IsLeaf()
206  */
[372]207  virtual bool IsLeaf() const { return true; }
208
209
[2117]210  /// pointers to occluders contained in this node
[372]211  ObjectContainer mObjects;
[2117]212  /// Ray set description of the rays passing through this node
[372]213  PassingRaySet mPassingRays;
[1144]214  /// pointer to view cell.
[469]215  KdViewCell *mViewCell;
[2538]216  /// rays intersecting this leaf
[1184]217  VssRayContainer mVssRays;
[1144]218   /// Objects that are referenced in more than one leaf.
219  ObjectContainer mMultipleObjects;
220  /// universal counter
221  int mCounter;
[2538]222
223  /// hack
224  unsigned int mVboId;
225
226  unsigned int mIndexBufferStart;
227  unsigned int mIndexBufferSize;
[372]228};
229
230
231/** KdTree for indexing scene entities - occluders/occludees/viewcells */
232class KdTree {
[878]233 
[372]234protected:
235  struct TraversalData
236  { 
237    KdNode *mNode;
238    AxisAlignedBox3 mBox;
239    int mDepth;
240    float mPriority;
241   
242    TraversalData() {}
243
244    TraversalData(KdNode *n, const float p):
245      mNode(n), mPriority(p)
246    {}
247   
248    TraversalData(KdNode *n,
[2575]249                  const AxisAlignedBox3 &b,
250                  const int d):
[372]251      mNode(n), mBox(b), mDepth(d) {}
252   
253
[2575]254    bool operator<(const TraversalData &b) const {
[372]255      KdLeaf *leafa = (KdLeaf *) mNode;
256      KdLeaf *leafb = (KdLeaf *) b.mNode;
257      return
[2575]258        leafa->mObjects.size()*mBox.SurfaceArea()
259        <
260        leafb->mObjects.size()*b.mBox.SurfaceArea();
[372]261    }
262
263
264    // comparator for the
265    struct less_priority : public
[2176]266    std::binary_function<const TraversalData, const TraversalData, bool> {
[372]267     
268      bool operator()(const TraversalData a, const TraversalData b) {
[2575]269        return a.mPriority < b.mPriority;
[372]270      }
271     
272    };
273
274  };
275
276 
277
278public:
279
280  enum {SPLIT_OBJECT_MEDIAN,
281        SPLIT_SPATIAL_MEDIAN,
282        SPLIT_SAH};
283 
284  KdTree();
[1002]285
286  ~KdTree();
[372]287   
288  /** Insert view cell into the tree */
289  virtual void InsertViewCell(ViewCell *viewCell) {
290    //      mRoot->mViewcells.push_back(viewCell);
291  }
292
293  virtual bool Construct();
294
295  /** Check whether subdivision criteria are met for the given subtree.
296      If not subdivide the leafs of the subtree. The criteria are specified in
297      the environment as well as the subdivision method. By default surface area
298      heuristics is used.
299       
300      @param subtree root of the subtree
301
302      @return true if subdivision was performed, false if subdivision criteria
303      were already met
304  */
305  virtual KdNode *Subdivide(const TraversalData &tdata);
306
307  /** Get the root of the tree */
308  KdNode *GetRoot() const {
309    return mRoot;
310  }
311
312
313  AxisAlignedBox3 GetBox() const { return mBox; }
314
315  int
316  CastRay(
[504]317                  Ray &ray
318                  );
319 
[372]320
[504]321  int
[505]322  CastBeam(
[512]323                   Beam &beam
[505]324                   );
[504]325 
326 
[469]327  /** Casts line segment into tree.
328          @returns intersected view cells.
329  */
330  int CastLineSegment(const Vector3 &origin,
[2575]331                      const Vector3 &termination,
332                      vector<ViewCell *> &viewcells);
[469]333
[2618]334  // old version
335  int CastLineSegment2(const Vector3 &origin,
336                                           const Vector3 &termination,
337                                           vector<ViewCell *> &viewcells);
[469]338
[372]339  const KdTreeStatistics &GetStatistics() const {
340    return mStat;
341  }
342
[1594]343  /** Returns or creates a new intersectable for use in a kd based pvs.
344  */
345  KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);
346
[1989]347
[372]348  void
[2538]349  SetPvsTerminationNodes(const float maxArea);
[2606]350
351  float
352  GetPvsArea() const;
[1989]353 
354  KdNode *
355  GetPvsNode(const Vector3 &point) const;
356 
357
358  void
[1974]359  CollectKdObjects(const AxisAlignedBox3 &box,
[2575]360                   ObjectContainer &objects
361                   );
[1974]362
[2606]363  // colect objects which are in the bounding box by explictly specifying the
364  // allowed size of the boxes. If this size is smaller than size used for pvs entries
365  // filtering will be more precise
[1974]366  void
[2606]367  CollectSmallKdObjects(const AxisAlignedBox3 &box,
368                                                ObjectContainer &objects,
369                                                const float maxArea
370                                                );
371
372  void
[372]373  CollectObjects(KdNode *n, ObjectContainer &objects);
[859]374
[372]375  void
[859]376  CollectObjects(const AxisAlignedBox3 &box,
[2575]377                 ObjectContainer &objects);
[859]378
379  void
[372]380  CollectLeaves(vector<KdLeaf *> &leaves);
381       
[469]382  /** If the kd tree is used as view cell container, this
383          methods creates the view cells.
384          @returns the newly created view cells in a view cell container
385  */
386  void
387  CreateAndCollectViewCells(ViewCellContainer &viewCells) const;
388
[372]389  AxisAlignedBox3 GetBox(const KdNode *node) const {
390    KdInterior *parent = node->mParent;
391    if (parent == NULL)
392      return mBox;
393   
394    if (!node->IsLeaf())
395      return ((KdInterior *)node)->mBox;
396   
397    AxisAlignedBox3 box(parent->mBox);
398    if (parent->mFront == node)
399      box.SetMin(parent->mAxis, parent->mPosition);
400    else
401      box.SetMax(parent->mAxis, parent->mPosition);
402    return box;
403  }
[1594]404
405  float GetSurfaceArea(const KdNode *node) const {
[2575]406    return GetBox(node).SurfaceArea();
[1594]407  }
408
409 
[372]410  KdNode *
411  FindRandomNeighbor(KdNode *n,
[2575]412                     bool onlyUnmailed
413                     );
[372]414 
415  KdNode *
[2575]416  GetRandomLeaf(const Plane3 &halfspace);
[372]417
[859]418  KdNode *
419  GetRandomLeaf(const bool onlyUnmailed = false);
[1594]420
421
422  KdNode *
423  GetNode(const Vector3 &point, const float maxArea) const;
424
[1999]425  void GetBoxIntersections(const AxisAlignedBox3 &box,
[2575]426                           vector<KdLeaf *> &leaves);
[1999]427
[372]428  int
429  FindNeighbors(KdNode *n,
[2575]430                vector<KdNode *> &neighbors,
431                bool onlyUnmailed
432                );
[372]433
[2176]434  bool ExportBinTree(const std::string &filename);
[2539]435  /** loads kd tree from disk. note: sorts objects by id
436  */
437  bool ImportBinTree(const std::string &filename, ObjectContainer &object);
[2332]438
[372]439protected:
440
441  struct RayData {
442    // pointer to the actual ray
443    Ray *ray;
444   
445    // endpoints  - do we need them?
446#if USE_FIXEDPOINT_T
447    short tmin, tmax;
448#else
449    float tmin, tmax;
450#endif
451
452    RayData():ray(NULL) {}
453    RayData(Ray *r):ray(r), tmin(0),
454
455#if USE_FIXEDPOINT_T
456#define FIXEDPOINT_ONE 0x7FFE
[2575]457                    //                    tmax(0xFFFF)
458                    tmax(FIXEDPOINT_ONE)
[372]459#else
460      tmax(1.0f)
461#endif
462    {}
463
464    RayData(Ray *r,
465            const float _min,
466            const float _max
467            ):ray(r) {
468      SetTMin(_min);
469      SetTMax(_max);
470    }
471
472    RayData(Ray *r,
473            const short _min,
474            const float _max
475            ):ray(r), tmin(_min) {
476      SetTMax(_max);
477    }
478
479    RayData(Ray *r,
480            const float _min,
481            const short _max
482            ):ray(r), tmax(_max) {
483      SetTMin(_min);
484    }
485
486    friend bool operator<(const RayData &a, const RayData &b) {
487      return a.ray < b.ray;
488    }
489   
490   
491    float ExtrapOrigin(const int axis) const {
492      return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis);
493    }
494   
495    float ExtrapTermination(const int axis) const {
496      return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis);
497    }
498   
499#if USE_FIXEDPOINT_T
500    float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); }
501    float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); }
502
503    void SetTMin (const float t) {
504      tmin = (short) (t*(float)(FIXEDPOINT_ONE));
505    }
506   
507    void SetTMax (const float t) {
508      tmax = (short) (t*(float)(FIXEDPOINT_ONE));
509      tmax++;
510      //      if (tmax!=0xFFFF)
511      //        tmax++;
512    }
513#else
514    float GetTMin () const { return tmin; }
515    float GetTMax () const { return tmax; }
516
517    void SetTMin (const float t) { tmin = t; }
518    void SetTMax (const float t) { tmax = t; }
519#endif
520  };
521
522  struct RayTraversalData {
523    KdNode *mNode;
524    Vector3 mExitPoint;
525    float mMaxT;
526   
527    RayTraversalData() {}
528    RayTraversalData(KdNode *n,
529                     const Vector3 &p,
530                     const float maxt):
531      mNode(n), mExitPoint(p), mMaxT(maxt) {}
532  };
533
534  // --------------------------------------------------------------
535  // For sorting objects
536  // --------------------------------------------------------------
537  struct  SortableEntry
538  {
539    enum {
540      BOX_MIN,
541      BOX_MAX
542    };
543   
544    int type;
545    float value;
546    Intersectable *intersectable;
547   
548    SortableEntry() {}
[2575]549    SortableEntry(const int t, const float v, Intersectable *i):
550      type(t), value(v), intersectable(i)
551    { }
[372]552   
553    bool operator<(const SortableEntry &b) const {
554      return value < b.value;
555    }
556   
557  };
[2066]558
559  inline static bool iltS(SortableEntry *a, SortableEntry *b)
560  {
561          return a->value < b->value;
562  }
563
[372]564  // reusable array of split candidates
[2003]565  vector<SortableEntry *> *splitCandidates;
[372]566
567  float
568  BestCostRatio(
569                KdLeaf *node,
570                const AxisAlignedBox3 &box,
571                const int axis,
572                float &position,
573                int &objectsBack,
574                int &objectsFront
575                );
576
577  void
[1233]578  SortSubdivisionCandidates(
[2575]579                            KdLeaf *node,
580                            const int axis
581                           );
[372]582
583  void
584  EvaluateLeafStats(const TraversalData &data);
585
586  KdNode *
587  SubdivideNode(
588                KdLeaf *leaf,
589                const AxisAlignedBox3 &box,
590                AxisAlignedBox3 &backBBox,
591                AxisAlignedBox3 &frontBBox
592                );
593
594  bool
595  TerminationCriteriaMet(const KdLeaf *leaf);
596 
597  int
598  SelectPlane(KdLeaf *leaf,
599              const AxisAlignedBox3 &box,
600              float &position
601              );
602
[2575]603  /** does some post processing on the objects in the new child leaves.
604   */
605  void ProcessMultipleRefs(KdLeaf *leaf) const;
[372]606
[2539]607
[2575]608  //////////
609  // binary import / export
610 
611  void ExportBinLeaf(OUT_STREAM  &stream, KdLeaf *leaf);
[2539]612       
[2575]613  void ExportBinInterior(OUT_STREAM &stream, KdInterior *interior);
614 
615  KdLeaf *ImportBinLeaf(IN_STREAM &stream, KdInterior *parent,
616                        const ObjectContainer &objects);
[2539]617       
[2575]618  KdInterior *ImportBinInterior(IN_STREAM  &stream, KdInterior *parent);
619 
620  KdNode *ImportNextNode(IN_STREAM  &stream, KdInterior *parent,
621                         const ObjectContainer &objects);
[1633]622       
[2575]623  /** Adds this objects to the kd leaf objects.
624      @warning: Can corrupt the tree
625  */
626  void InsertObjects(KdNode *node, const ObjectContainer &objects);
[1194]627
[752]628  int mTermMaxNodes;
[372]629  float mSplitBorder;
630  int mTermMaxDepth;
631  int mTermMinCost;
632  float mMaxCostRatio;
633  float mCt_div_ci;
634  int mSplitMethod;
635  bool mSahUseFaces;
[2524]636  float mKdPvsArea;
[372]637  /// root of the tree
638  KdNode *mRoot;
639  /// bounding box of the tree root
640  AxisAlignedBox3 mBox;
641  KdTreeStatistics mStat;
[2116]642
[1614]643public:
[1594]644  /// stores the kd node intersectables used for pvs
[1761]645  vector<KdIntersectable *> mKdIntersectables;
646 
[372]647};
648
649
[860]650}
[372]651
652#endif
Note: See TracBrowser for help on using the repository browser.