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

Revision 2168, 9.4 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _TraversalTree_H__
2#define _TraversalTree_H__
3
4#include <functional>
5//using namespace std;
6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
10
11
12namespace GtpVisibilityPreprocessor {
13
14 
15class TraversalNode;
16class TraversalLeaf;
17class TraversalInterior;
18class Intersectable;
19class Beam;
20
21class TraversalTree;
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;
52  // max number of rays per node
53  int totalObjectRefs;
54  // number of dynamically added ray refs
55  int addedRayRefs;
56  // number of dynamically removed ray refs
57  int removedRayRefs;
58  // number of nodes terminated on cost ratio
59  int costRatioNodes;
60
61  // Constructor
62  TraversalTreeStatistics()
63  {
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  {
73          nodes = 0;
74         
75          for (int i = 0; i < 7; ++ i)
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;
84          totalObjectRefs = 0;
85          addedRayRefs = removedRayRefs = 0;
86          costRatioNodes = 0;
87  }
88
89  void Print(ostream &app) const;
90
91  friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat)
92  {
93          stat.Print(s);
94          return s;
95  }
96 
97};
98
99 
100class TraversalInterior;
101
102/** Abstract class for kd-tree node
103*/
104class TraversalNode
105{
106public:
107
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;
122        }
123
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
127        */
128        TraversalInterior *mParent;
129
130
131        ///////////////////
132        // mailing stuff
133
134public:
135
136        void Mail()
137        {
138                mMailbox = sMailId;
139        }
140
141        bool Mailed() const
142        {
143                return mMailbox == sMailId;
144        }
145
146        static void NewMail(const int reserve = 1)
147        {
148                sMailId += sReservedMailboxes;
149                sReservedMailboxes = reserve;
150        }
151
152        void Mail(const int mailbox)
153        {
154                mMailbox = sMailId + mailbox;
155        }
156
157
158        bool Mailed(const int mailbox) const
159        {
160                return mMailbox == sMailId + mailbox;
161        }
162
163        int mMailbox;
164
165        static int sMailId;
166        static int sReservedMailboxes;
167};
168
169
170/** Implementation of the kd-tree interior node
171*/
172class TraversalInterior : public TraversalNode
173{
174public:
175
176        TraversalInterior(TraversalInterior *parent);
177        ~TraversalInterior();
178
179        /** \sa TraversalNode::IsLeaf()
180        */
181        bool IsLeaf() const;
182
183        void SetupChildLinks(TraversalNode *b, TraversalNode *f);
184
185        void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);
186
187
188        //////////////////////////
189
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;
196
197        /// back node
198        TraversalNode *mBack;
199        /// front node
200        TraversalNode *mFront; 
201};
202
203 
204/** Implementation of the kd-tree leaf node
205*/
206class TraversalLeaf : public TraversalNode
207{
208public:
209
210        TraversalLeaf(TraversalInterior *parent, const int objects);
211
212        ~TraversalLeaf();
213
214        /** \sa TraversalNode::IsLeaf()
215        */
216        virtual bool IsLeaf() const;
217
218        /////////////////////////////////
219
220        // pointers to view cells contained in this node
221        ViewCellContainer mViewCells;
222
223        short mDepth;
224};
225
226
227/** TraversalTree for indexing scene entities - occluders/occludees/viewcells
228*/
229class TraversalTree
230{
231
232protected:
233
234        struct TraversalData
235        { 
236                TraversalNode *mNode;
237                AxisAlignedBox3 mBox;
238                int mDepth;
239                float mPriority;
240
241                TraversalData(): mNode(NULL), mPriority(0), mDepth(0) {}
242
243                TraversalData(TraversalNode *n, const float p):
244                mNode(n), mPriority(p), mDepth(0)
245                {}
246
247                TraversalData(TraversalNode *n,
248                                          const AxisAlignedBox3 &b,
249                                          const int d):
250                mNode(n), mBox(b), mDepth(d)
251                {}
252
253
254                bool operator<(const TraversalData &b) const
255                {
256                        TraversalLeaf *leafa = (TraversalLeaf *) mNode;
257                        TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
258                       
259                        return
260                                leafa->mViewCells.size() * mBox.SurfaceArea()
261                                <
262                                leafb->mViewCells.size() * b.mBox.SurfaceArea();
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                        {
272                                return a.mPriority < b.mPriority;
273                        }
274                };
275        };
276
277
278public:
279
280        enum {SPLIT_OBJECT_MEDIAN,
281                  SPLIT_SPATIAL_MEDIAN,
282                  SPLIT_SAH};
283
284        TraversalTree();
285
286        ~TraversalTree();
287
288
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);
296
297        virtual bool Construct(const ViewCellContainer &viewCells);
298
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
301                the environment as well as the subdivision method. By default surface area
302                heuristics is used.
303
304                @param subtree root of the subtree
305
306                @return true if subdivision was performed, false if subdivision criteria
307                were already met
308        */
309        virtual TraversalNode *Subdivide(const TraversalData &tdata);
310
311        /** Get the root of the tree
312        */
313        TraversalNode *GetRoot() const
314        {
315                return mRoot;
316        }
317
318        AxisAlignedBox3 GetBox() const
319        {
320                return mBox;
321        }
322
323        const TraversalTreeStatistics &GetStatistics() const
324        {
325                return mStat;
326        }
327
328        void CollectObjects(TraversalNode *n, ObjectContainer &objects);
329
330        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
331
332        void CollectLeaves(vector<TraversalLeaf *> &leaves);
333
334        float GetSurfaceArea(const TraversalNode *node) const
335        {
336                return GetBox(node).SurfaceArea();
337        }
338
339        AxisAlignedBox3 GetBox(const TraversalNode *node) const;
340
341
342protected:
343
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) {}
351
352                TraversalNode *mNode;
353                Vector3 mExitPoint;
354                float mMaxT;
355        };
356
357        // --------------------------------------------------------------
358        // For sorting objects
359        // --------------------------------------------------------------
360        struct SortableEntry
361        {
362                enum
363                {
364                        BOX_MIN,
365                        BOX_MAX
366                };
367
368                int type;
369                float value;
370                Intersectable *intersectable;
371
372                SortableEntry() {}
373                SortableEntry(const int t, const float v, Intersectable *i):
374                type(t), value(v), intersectable(i)
375                {}
376
377                /*bool operator<(const SortableEntry &b) const
378                {
379                        // view cells usually adjacent
380                        if (EpsilonEqual(value, b.value, 0.001))
381                                return (type == BOX_MAX);
382                       
383                        return value < b.value;
384                }*/
385        };
386
387        inline static bool iltS(SortableEntry *a, SortableEntry *b)
388        {
389                // view cells usually adjacent
390                //if (EpsilonEqual(a->value, b->value))
391                //      return false;
392                //      return (a->type == SortableEntry::BOX_MAX);
393                       
394                return a->value < b->value;
395        }
396
397        // reusable array of split candidates
398        vector<SortableEntry *> *splitCandidates;
399
400        float BestCostRatio(TraversalLeaf *node,
401                                                const AxisAlignedBox3 &box,
402                                                const int axis,
403                                                float &position,
404                                                int &objectsBack,
405                                                int &objectsFront);
406
407        void SortSubdivisionCandidates(TraversalLeaf *node, const int axis);
408
409        void EvaluateLeafStats(const TraversalData &data);
410
411        TraversalNode *SubdivideNode(TraversalLeaf *leaf,
412                                                                 const AxisAlignedBox3 &box,
413                                                                 AxisAlignedBox3 &backBBox,
414                                                                 AxisAlignedBox3 &frontBBox
415                                                                 );
416
417        bool TerminationCriteriaMet(const TraversalLeaf *leaf);
418
419        int SelectPlane(TraversalLeaf *leaf,
420                                        const AxisAlignedBox3 &box,
421                                        float &position);
422
423        int FindViewCellIntersections(const Vector3 &lStart,
424                                                                  const Vector3 &lEnd,
425                                                                  const ViewCellContainer &viewCells,
426                                                                  ViewCellContainer &hitViewCells,
427                                                                  const bool useMailboxing);
428
429        ////////////////////////
430
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;
439
440        /// root of the tree
441        TraversalNode *mRoot;
442        /// bounding box of the tree root
443        AxisAlignedBox3 mBox;
444        TraversalTreeStatistics mStat;
445
446};
447
448
449}
450
451#endif
Note: See TracBrowser for help on using the repository browser.