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

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