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

Revision 878, 11.6 KB checked in by bittner, 19 years ago (diff)

mesh inntersection bug fixed

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