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

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