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

Revision 1761, 13.7 KB checked in by bittner, 18 years ago (diff)

filter updates, kd + bvh PVS coexistence

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