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

Revision 2539, 14.3 KB checked in by mattausch, 17 years ago (diff)

fixed obj loading error

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