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

Revision 2643, 15.3 KB checked in by mattausch, 17 years ago (diff)

compiling under release internal

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