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

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