source: GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h @ 2176

Revision 2176, 9.4 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h

RevLine 
[2073]1#ifndef _TraversalTree_H__
2#define _TraversalTree_H__
3
4#include <functional>
[2176]5//
[2073]6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
10
11
12namespace GtpVisibilityPreprocessor {
13
14 
[2116]15class TraversalNode;
16class TraversalLeaf;
17class TraversalInterior;
18class Intersectable;
19class Beam;
[2073]20
[2116]21class TraversalTree;
[2073]22 
23
24// --------------------------------------------------------------
25// Static statistics for kd-tree search
26// --------------------------------------------------------------
27class TraversalTreeStatistics
28{
29public: 
30  // total number of nodes
31  int nodes;
32  // number of splits along each of the axes
33  int splits[7];
34  // totals number of rays
35  int rays;
36  // total number of query domains
37  int queryDomains;
38  // total number of ray references
39  int rayRefs;
40  // refs in non empty leafs
41  int rayRefsNonZeroQuery;
42  // total number of query references
43  int objectRefs;
44  // nodes with zero queries
45  int zeroQueryNodes;
46  // max depth nodes
47  int maxDepthNodes;
48  // max depth nodes
49  int minCostNodes;
50  // max number of rays per node
51  int maxObjectRefs;
[2124]52  // max number of rays per node
53  int totalObjectRefs;
[2073]54  // number of dynamically added ray refs
55  int addedRayRefs;
56  // number of dynamically removed ray refs
57  int removedRayRefs;
[2149]58  // number of nodes terminated on cost ratio
59  int costRatioNodes;
60
[2073]61  // Constructor
[2093]62  TraversalTreeStatistics()
63  {
64          Reset();
[2073]65  }
66
67  int Nodes() const {return nodes;}
68  int Interior() const { return nodes / 2; }
69  int Leaves() const { return (nodes / 2) + 1; }
70
[2093]71  void Reset()
72  {
73          nodes = 0;
74         
[2149]75          for (int i = 0; i < 7; ++ i)
[2093]76                  splits[i] = 0;
77         
78          rays = queryDomains = 0;
79          rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
80          zeroQueryNodes = 0;
81          maxDepthNodes = 0;
82          minCostNodes = 0;
83          maxObjectRefs = 0;
[2124]84          totalObjectRefs = 0;
[2093]85          addedRayRefs = removedRayRefs = 0;
[2149]86          costRatioNodes = 0;
[2073]87  }
88
[2176]89  void Print(std::ostream &app) const;
[2073]90
[2176]91  friend std::ostream &operator<<(std::ostream &s, const TraversalTreeStatistics &stat)
[2093]92  {
93          stat.Print(s);
94          return s;
[2073]95  }
96 
97};
98
99 
100class TraversalInterior;
[2093]101
102/** Abstract class for kd-tree node
103*/
104class TraversalNode
105{
[2073]106public:
107
[2093]108        virtual ~TraversalNode(){};
109       
110        TraversalNode(TraversalInterior *parent);
111        /** Determines whether this node is a leaf or interior node
112        @return true if leaf
113        */
114        virtual bool IsLeaf() const = 0;
115
116        /** Determines whether this node is the root of the tree
117        @return true if root
118        */
119        virtual bool IsRoot() const
120        {
121                return mParent == NULL;
[2073]122        }
123
[2124]124        /** Parent of the node - the parent is a little overhead for
125                maintanance of the tree, but allows various optimizations
126                of tree traversal algorithms
[2093]127        */
128        TraversalInterior *mParent;
[2073]129
130
[2093]131        ///////////////////
132        // mailing stuff
[2073]133
[2093]134public:
[2073]135
[2093]136        void Mail()
137        {
138                mMailbox = sMailId;
139        }
[2073]140
[2093]141        bool Mailed() const
142        {
143                return mMailbox == sMailId;
144        }
[2073]145
[2093]146        static void NewMail(const int reserve = 1)
147        {
148                sMailId += sReservedMailboxes;
149                sReservedMailboxes = reserve;
150        }
[2073]151
[2093]152        void Mail(const int mailbox)
153        {
154                mMailbox = sMailId + mailbox;
155        }
[2073]156
157
[2093]158        bool Mailed(const int mailbox) const
159        {
160                return mMailbox == sMailId + mailbox;
161        }
[2073]162
[2093]163        int mMailbox;
164
165        static int sMailId;
166        static int sReservedMailboxes;
[2073]167};
168
169
[2093]170/** Implementation of the kd-tree interior node
171*/
172class TraversalInterior : public TraversalNode
173{
174public:
[2073]175
[2093]176        TraversalInterior(TraversalInterior *parent);
177        ~TraversalInterior();
[2073]178
[2093]179        /** \sa TraversalNode::IsLeaf()
180        */
181        bool IsLeaf() const;
[2073]182
[2093]183        void SetupChildLinks(TraversalNode *b, TraversalNode *f);
[2073]184
[2093]185        void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);
[2073]186
187
[2093]188        //////////////////////////
[2073]189
[2093]190        /// splitting axis
191        int mAxis;
192        /// splitting position, absolute position within the bounding box of this node.
193        float mPosition;
194        /// bounding box of interior node
195        AxisAlignedBox3 mBox;
[2073]196
[2093]197        /// back node
198        TraversalNode *mBack;
199        /// front node
200        TraversalNode *mFront; 
[2073]201};
202
203 
[2093]204/** Implementation of the kd-tree leaf node
205*/
206class TraversalLeaf : public TraversalNode
207{
208public:
[2073]209
[2093]210        TraversalLeaf(TraversalInterior *parent, const int objects);
[2073]211
[2093]212        ~TraversalLeaf();
[2073]213
[2093]214        /** \sa TraversalNode::IsLeaf()
215        */
216        virtual bool IsLeaf() const;
[2073]217
[2093]218        /////////////////////////////////
[2073]219
[2093]220        // pointers to view cells contained in this node
[2124]221        ViewCellContainer mViewCells;
[2073]222
[2093]223        short mDepth;
224};
[2073]225
226
[2093]227/** TraversalTree for indexing scene entities - occluders/occludees/viewcells
228*/
229class TraversalTree
230{
[2073]231
[2093]232protected:
[2073]233
[2093]234        struct TraversalData
235        { 
236                TraversalNode *mNode;
237                AxisAlignedBox3 mBox;
238                int mDepth;
239                float mPriority;
[2073]240
[2124]241                TraversalData(): mNode(NULL), mPriority(0), mDepth(0) {}
[2073]242
[2093]243                TraversalData(TraversalNode *n, const float p):
[2124]244                mNode(n), mPriority(p), mDepth(0)
[2093]245                {}
[2073]246
[2093]247                TraversalData(TraversalNode *n,
[2124]248                                          const AxisAlignedBox3 &b,
249                                          const int d):
250                mNode(n), mBox(b), mDepth(d)
251                {}
[2073]252
253
[2093]254                bool operator<(const TraversalData &b) const
255                {
256                        TraversalLeaf *leafa = (TraversalLeaf *) mNode;
257                        TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
258                       
259                        return
[2124]260                                leafa->mViewCells.size() * mBox.SurfaceArea()
[2093]261                                <
[2124]262                                leafb->mViewCells.size() * b.mBox.SurfaceArea();
[2093]263                }
[2073]264
265
[2124]266                // comparator for the
267                struct less_priority: public
[2176]268                                std::binary_function<const TraversalData, const TraversalData, bool>
[2124]269                {
270                        bool operator()(const TraversalData a, const TraversalData b)
[2093]271                        {
[2124]272                                return a.mPriority < b.mPriority;
273                        }
274                };
[2093]275        };
[2073]276
277
[2093]278public:
[2073]279
[2093]280        enum {SPLIT_OBJECT_MEDIAN,
281                  SPLIT_SPATIAL_MEDIAN,
282                  SPLIT_SAH};
[2073]283
[2093]284        TraversalTree();
[2073]285
[2093]286        ~TraversalTree();
[2073]287
288
[2093]289        /** Casts line segment into tree.
290                @returns intersected view cells.
291        */
292        int CastLineSegment(const Vector3 &origin,
293                                                const Vector3 &termination,
294                                                ViewCellContainer &viewcells,
295                                                const bool useMailboxing);
[2073]296
[2124]297        virtual bool Construct(const ViewCellContainer &viewCells);
[2073]298
[2093]299        /** Check whether subdivision criteria are met for the given subtree.
300                If not subdivide the leafs of the subtree. The criteria are specified in
[2124]301                the environment as well as the subdivision method. By default surface area
[2093]302                heuristics is used.
[2073]303
[2093]304                @param subtree root of the subtree
[2073]305
[2093]306                @return true if subdivision was performed, false if subdivision criteria
307                were already met
308        */
309        virtual TraversalNode *Subdivide(const TraversalData &tdata);
[2073]310
[2093]311        /** Get the root of the tree
312        */
313        TraversalNode *GetRoot() const
314        {
315                return mRoot;
316        }
[2073]317
[2093]318        AxisAlignedBox3 GetBox() const
319        {
320                return mBox;
321        }
[2073]322
[2093]323        const TraversalTreeStatistics &GetStatistics() const
324        {
325                return mStat;
326        }
[2073]327
[2093]328        void CollectObjects(TraversalNode *n, ObjectContainer &objects);
[2073]329
[2093]330        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
[2073]331
[2093]332        void CollectLeaves(vector<TraversalLeaf *> &leaves);
[2073]333
[2093]334        float GetSurfaceArea(const TraversalNode *node) const
335        {
336                return GetBox(node).SurfaceArea();
337        }
[2073]338
[2093]339        AxisAlignedBox3 GetBox(const TraversalNode *node) const;
[2073]340
[2093]341
[2073]342protected:
343
[2093]344        /** Struct for traversing line segment.
345        */
346        struct LineTraversalData
347        {               
348                LineTraversalData () {}
349                LineTraversalData (TraversalNode *n, const Vector3 &p, const float maxt):
350                mNode(n), mExitPoint(p), mMaxT(maxt) {}
[2073]351
[2093]352                TraversalNode *mNode;
353                Vector3 mExitPoint;
354                float mMaxT;
355        };
[2073]356
[2093]357        // --------------------------------------------------------------
358        // For sorting objects
359        // --------------------------------------------------------------
360        struct SortableEntry
361        {
362                enum
363                {
364                        BOX_MIN,
365                        BOX_MAX
366                };
[2073]367
[2093]368                int type;
369                float value;
370                Intersectable *intersectable;
[2073]371
[2093]372                SortableEntry() {}
373                SortableEntry(const int t, const float v, Intersectable *i):
374                type(t), value(v), intersectable(i)
375                {}
[2073]376
[2124]377                /*bool operator<(const SortableEntry &b) const
[2093]378                {
[2124]379                        // view cells usually adjacent
380                        if (EpsilonEqual(value, b.value, 0.001))
381                                return (type == BOX_MAX);
382                       
[2093]383                        return value < b.value;
[2124]384                }*/
[2093]385        };
[2073]386
[2093]387        inline static bool iltS(SortableEntry *a, SortableEntry *b)
388        {
[2124]389                // view cells usually adjacent
390                //if (EpsilonEqual(a->value, b->value))
391                //      return false;
392                //      return (a->type == SortableEntry::BOX_MAX);
393                       
[2093]394                return a->value < b->value;
395        }
[2073]396
[2093]397        // reusable array of split candidates
398        vector<SortableEntry *> *splitCandidates;
[2073]399
[2093]400        float BestCostRatio(TraversalLeaf *node,
401                                                const AxisAlignedBox3 &box,
402                                                const int axis,
403                                                float &position,
404                                                int &objectsBack,
405                                                int &objectsFront);
[2073]406
[2093]407        void SortSubdivisionCandidates(TraversalLeaf *node, const int axis);
[2073]408
[2093]409        void EvaluateLeafStats(const TraversalData &data);
[2073]410
[2093]411        TraversalNode *SubdivideNode(TraversalLeaf *leaf,
412                                                                 const AxisAlignedBox3 &box,
413                                                                 AxisAlignedBox3 &backBBox,
414                                                                 AxisAlignedBox3 &frontBBox
415                                                                 );
[2073]416
[2093]417        bool TerminationCriteriaMet(const TraversalLeaf *leaf);
[2073]418
[2093]419        int SelectPlane(TraversalLeaf *leaf,
420                                        const AxisAlignedBox3 &box,
421                                        float &position);
[2073]422
[2124]423        int FindViewCellIntersections(const Vector3 &lStart,
424                                                                  const Vector3 &lEnd,
425                                                                  const ViewCellContainer &viewCells,
426                                                                  ViewCellContainer &hitViewCells,
427                                                                  const bool useMailboxing);
[2073]428
[2093]429        ////////////////////////
[2073]430
[2093]431        int mTermMaxNodes;
432        float mSplitBorder;
433        int mTermMaxDepth;
434        int mTermMinCost;
435        float mMaxCostRatio;
436        float mCt_div_ci;
437        int mSplitMethod;
438        bool mSahUseFaces;
[2073]439
[2093]440        /// root of the tree
441        TraversalNode *mRoot;
442        /// bounding box of the tree root
443        AxisAlignedBox3 mBox;
444        TraversalTreeStatistics mStat;
[2073]445
446};
447
448
449}
450
451#endif
Note: See TracBrowser for help on using the repository browser.