source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTree.h @ 1173

Revision 1173, 13.8 KB checked in by szydlowski, 18 years ago (diff)

Finished kdtree hierarchy interface, started modifications to kdtree scene manager
Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of the GameTools Project
4http://www.gametools.org
5
6Author: Martin Szydlowski
7-----------------------------------------------------------------------------
8*/
9
10#ifndef _OgreKdTree_H__
11#define _OgreKdTree_H__
12
13#define KDNODE_CAST(a) (static_cast<KdTree::Node>(a))
14#define KDBRANCH_CAST(a) (static_cast<KdTree::Branch>(a))
15#define KDLEAF_CAST(a) (static_cast<KdTree::Leaf>(a))
16#define KDNODEPTR_CAST(a) (static_cast<KdTree::Node *>(a))
17#define KDBRANCHPTR_CAST(a) (static_cast<KdTree::Branch *>(a))
18#define KDLEAFPTR_CAST(a) (static_cast<KdTree::Leaf *>(a))
19
20#include <OgreAxisAlignedBox.h>
21#include <OgreWireBoundingBox.h>
22#include <OgrePlane.h>
23#include <OgreVector3.h>
24
25#include <OgreRoot.h>
26
27#include <stack>
28
29
30
31namespace Ogre
32{
33        class KdRenderable;
34        struct SplitInfo;
35
36        class PlaneEvent
37        {
38        public:
39                enum Type
40                {
41                        PET_END,
42                        PET_ON,
43                        PET_START
44                };
45
46                enum Dimension
47                {
48                        PED_X,
49                        PED_Y,
50                        PED_Z
51                };
52
53                enum Side
54                {
55                        PES_LEFT = 0x01,
56                        PES_RIGHT = 0x02,
57                        PES_BOTH = PES_LEFT | PES_RIGHT
58                };
59
60                PlaneEvent(): mRenderable(0), mPosition(Vector3()), mDimension(PED_X), mType(PET_ON)
61                { };
62
63                PlaneEvent(KdRenderable *rend, const Vector3& pos, PlaneEvent::Dimension dim, PlaneEvent::Type type):
64                        mRenderable(rend), mPosition(pos), mDimension(dim), mType(type)
65                { };
66
67                ~PlaneEvent() {};
68
69                // the less operator for plane events
70                // first sort by position, then by dimension and finally by type
71                bool operator < (const PlaneEvent& e) const
72                {
73                        if(mPosition[mDimension] < e.mPosition[e.mDimension])
74                        {
75                                return true;
76                        }
77
78                        if(mPosition[mDimension] == e.mPosition[e.mDimension])
79                        {
80                                if (mDimension < e.mDimension)
81                                {
82                                        return true;
83                                }
84                                if (mDimension == e.mDimension)
85                                {
86                                        if (mType < e.mType)
87                                        {
88                                                return true;
89                                        }
90                                }
91                        }
92
93                        return false;
94                };
95
96                // the equals operator for tree events
97                bool operator == (const PlaneEvent& e) const
98                {
99                        return  (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
100                                (mDimension == e.mDimension) &&
101                                (mType == e.mType);
102                };
103
104                bool equalsType(const PlaneEvent& e, PlaneEvent::Type t)
105                {
106                        return  (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
107                                (mDimension == e.mDimension) &&
108                                (mType == t);
109                };
110
111                void classify(const PlaneEvent& e, PlaneEvent::Side side);
112
113                PlaneEvent clip(AxisAlignedBox& box, PlaneEvent::Dimension dim);
114
115                Plane * getSplitPlane() const
116                {
117                        Vector3 normal(0,0,0);
118                        normal[mDimension] = 1;
119                        return new Plane(normal, mPosition);
120                }
121
122                KdRenderable * getRenderable() const //??
123                {
124                        return mRenderable;
125                };
126
127                PlaneEvent::Dimension getDimension() const //??
128                {
129                        return mDimension;
130                };
131
132                // DEBUG
133                String print();
134        protected:
135                // event info
136                KdRenderable *                  mRenderable;
137                Vector3                                 mPosition;
138                PlaneEvent::Dimension   mDimension;
139                PlaneEvent::Type                mType;
140
141                // ------------------------------------------------------------------------------//
142                // functions to determine the cost of splitting the node parent with the plane
143                // represented by this event
144                // TODO discuss if these functions really belong here, OO & SE - wise
145                // pros: convenient, don't have to pass internal data to the outside
146                // cons: SplitInfo ...
147        public:
148                // compute "global" surface area heuristic (SAH) for the plane represented by this event
149                // use only with priority queue build method
150                void pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, SplitInfo& split);
151                static Real pqSplitCost(Real p, Real pl, Real pr, int nLeft, int nRight, Real mu);
152
153                // compute the surface area heuristic (SAH) for the plane represented by this event
154                void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split);
155                // the variables determining the cost of a branch traversal (KT) and a leaf intersection (KI)
156                static Real KT;
157                static Real KI;
158                // helper functions
159                static Real splitCost(Real pl, Real pr, int nLeft, int nRight);
160                static Real splitCost(Real pl, Real pr, int nLeft, int nRight, Real mu);
161                static Real surfaceArea(const AxisAlignedBox& box);
162                static Real lookupPenalty(Real p);
163        protected:
164                Real splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right);
165        };
166
167        // Holds all the important information on a split
168        struct SplitInfo
169        {
170                AxisAlignedBox bleft;
171                AxisAlignedBox bright;
172                int nleft;
173                int nright;
174                Real cost;
175                PlaneEvent::Side side;
176                PlaneEvent event;
177
178                // DEBUG
179                String print();
180        };
181
182        typedef std::list<PlaneEvent> PlaneEventList;
183        typedef std::list<KdRenderable *> KdRenderableList;
184       
185        class KdTree
186        {
187        protected:
188                class Branch;
189                class Leaf;
190
191                class Node
192                {
193                public:
194                        Node(int level, AxisAlignedBox& aabb, Branch * parent):
195                        mLevel(level),
196                        mAABB(aabb),
197                        mParent(parent),
198                        mWBB(0)
199                        { };
200
201                        virtual ~Node()
202                        {
203                                delete mWBB;
204                        };
205
206                        virtual bool isLeaf() const = 0;
207                        virtual bool isEmpty() const = 0;
208                        virtual bool hasGeometry() const = 0;
209                       
210                        // consider using typesafe callback functions
211                        //virtual void cbInsert(KdTree * caller, KdRenderable * rend) = 0;
212
213                        WireBoundingBox * getWireBoundingBox()
214                        {
215                                if (mWBB == 0)
216                                        mWBB = new WireBoundingBox();
217
218                                mWBB->setupBoundingBox(mAABB);
219                               
220#ifdef KDTREE_DEBUG
221                                int level = -1;
222                                bool boxes = false;
223                                if (Root::getSingleton()._getCurrentSceneManager()->getOption("HighlightLevel",&level))
224                                {
225                                        if (mLevel == level)
226                                        {
227                                                //mWBB->setMaterial("BaseGreenNoLighting");
228                                                mWBB->setMaterial("aabbHiLite");
229                                                return mWBB;
230                                        }
231                                        else
232                                        {
233                                                mWBB->setMaterial("BaseWhiteNoLighting");
234                                                if (Root::getSingleton()._getCurrentSceneManager()->getOption("ShowAllBoxes", &boxes))
235                                                {
236                                                        if (boxes)
237                                                                return mWBB;
238                                                        else
239                                                                return 0;
240                                                }
241                                        }
242                                }
243#else
244                                mWBB->setMaterial("BaseWhiteNoLighting");
245#endif // KDTREE_DEBUG
246                                return mWBB;
247
248                        }
249
250                        // functions for the CHC hierarchy interface
251
252                        /** Returns last visited frame id. */
253                        unsigned int lastVisited(void) { return mLastVisited; };
254                        /** Set to current frame id.
255                        @param current frame id.
256                        */
257                        void setLastVisited(unsigned int frameid) { mLastVisited = frameid; };
258                        /** Makes this octree become visible / invisble.
259                        @param visible Whether this node is to be made visible or invisible
260                        */
261                        void setNodeVisible(bool visible) { mVisible = visible; };
262                        /** Returns true if this node is marked visible, false otherwise.
263                        */
264                        bool isNodeVisible(void) { return mVisible; };
265                        /** Frame id when this octree was last rendered.
266                        @return last rendered frame id
267                        */     
268                        unsigned int lastRendered(void) { return mLastRendered; };
269                        /** Sets frame id when this octree was last rendered.
270                        @param last rendered frame id
271                        */
272                        void setLastRendered(unsigned int frameid) { mLastRendered = frameid; };
273                        /** Gets this node's parent (NULL if this is the root).
274                        */     
275                        KdTree::Branch *getParent(void) { return mParent; };
276                        /** Returns real extent of the kdtree, i.e., the merged extent of the bounding boxes.
277                        */
278                        AxisAlignedBox _getWorldAABB(void) const { return mWorldAABB; };
279                        /** Updates bound of the real aabb of kdtree
280                        */
281                        virtual void _updateBounds() = 0;
282
283
284                        Branch * mParent;
285                        int mLevel;
286                        AxisAlignedBox mAABB;
287                protected:
288                        WireBoundingBox * mWBB;
289
290                        // for the CHC hierarchy interface
291                        /** the real extent of the node. */
292                        AxisAlignedBox mWorldAABB;
293                       
294                        unsigned int mLastRendered;
295                        unsigned int mLastVisited;
296                        bool mVisible;
297                };
298
299                class Branch : public Node
300                {
301                public:
302                        Branch(int level, AxisAlignedBox& aabb, Branch * parent, Plane * splitplane, PlaneEvent::Side side):
303                                Node(level, aabb, parent),
304                                mSplitPlane(splitplane),
305                                mLeft(0),
306                                mRight(0),
307                                mPlaneSide(side)
308                        { };
309
310                        virtual ~Branch()
311                        {
312                                delete mLeft;
313                                delete mRight;
314                                delete mSplitPlane;
315                        };
316
317                        // a branch is not a leaf
318                        virtual bool isLeaf() const { return false; };
319
320                        // s branch is empty when it does not have children
321                        virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
322
323                        // a branch never has geometry
324                        virtual bool hasGeometry() const { return false; };
325
326                        // branches do not posses geometry => just merge child aabbs
327                        virtual void _updateBounds()
328                        {
329                                // reset box
330                                mWorldAABB.setNull();
331
332                                if (mLeft)
333                                        mWorldAABB.merge(mLeft->_getWorldAABB());
334                                if (mRight)
335                                        mWorldAABB.merge(mRight->_getWorldAABB());
336
337                                // update parent recursively
338                                if (mParent)
339                                        mParent->_updateBounds();
340                        }
341                       
342                        Node * mLeft;
343                        Node * mRight;
344                        Plane  * mSplitPlane;
345                        PlaneEvent::Side mPlaneSide;
346                };
347
348                class Leaf : public Node
349                {
350                public:
351                        Leaf(int level, AxisAlignedBox& aabb, Branch * parent):
352                          Node(level, aabb, parent)
353                        {};
354
355                        virtual ~Leaf();
356
357                        // a leaf is a leaf, dammit
358                        virtual bool isLeaf() const { return true; };
359
360                        // a leaf is empty when it does not posses renderables
361                        virtual bool isEmpty() const { return mKdRenderables.empty(); };
362
363                        // a leaf has geometry when it has renderables
364                        virtual bool hasGeometry() const { return !mKdRenderables.empty(); };
365
366                        // update the world aabb based on the contained geometry
367                        virtual void _updateBounds();
368
369                        virtual void remove(KdRenderable * rend)
370                        {
371                                mKdRenderables.remove(rend);
372                                //mKdRenderables.erase(find(mKdRenderables.begin(), mKdRenderables.end(), rend));
373                        };
374
375                        virtual void insert(KdRenderable * rend)
376                        {
377                                mKdRenderables.push_back(rend);
378                        };
379
380                        KdRenderableList mKdRenderables;
381                };
382
383                struct SplitCandidate
384                {
385                        SplitCandidate(PlaneEventList * e, int n, AxisAlignedBox& a, KdTree::Branch * p, Real c, Real d, SplitInfo * b, PlaneEvent::Side s):
386                                events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s) { };
387
388                        bool operator < (const SplitCandidate& rhs) const
389                        {
390                                return decrease < rhs.decrease;
391                        };
392
393                        void operator = (const SplitCandidate& rhs)
394                        {
395                                decrease = rhs.decrease;
396                                cost = rhs.cost;
397                                nObjects = rhs.nObjects;
398                                side = rhs.side;
399                                aabb = rhs.aabb;
400                                events = rhs.events;
401                                parent = rhs.parent;
402                                best = rhs.best;
403                        };
404
405                        // DEBUG
406                        String print();
407
408                        Real decrease;
409                        Real cost;
410                        int nObjects;
411                        PlaneEvent::Side side;
412                        AxisAlignedBox aabb;
413                        PlaneEventList * events;
414                        KdTree::Branch * parent;
415                        SplitInfo * best;
416                };
417
418                // typedef std::stack<SplitCandidate> SplitCandidatePQ;
419                typedef std::priority_queue<SplitCandidate> SplitCandidatePQ;
420
421                // nodestack for the stack-based rendering function
422                typedef std::stack<KdTree::Node *> NodeStack;
423        public:
424                friend class KdTreeHierarchyInterface;
425
426                typedef KdTree::Leaf * LeafPtr;
427                typedef std::set<LeafPtr> LeafSet;
428
429                enum RenderMethod
430                {
431                        KDRM_RECURSE,
432                        KDRM_STACK,
433                        KDRM_SAW,
434                        KDRM_CHC
435                };
436
437                enum BuildMethod
438                {
439                        KDBM_RECURSIVE,
440                        KDBM_PRIORITYQUEUE
441                };
442               
443                KdTree(int maxdepth);
444                virtual ~KdTree();
445
446                // DEBUG
447                void dump();
448                void calcCost();
449
450                // insert a new scene node into an existing kd-tree
451                void insert(KdRenderable * rend);
452                // remove a scene node from the tree
453                void remove(KdRenderable * rend);
454                // function to initialize a kd-tree based on the contents of the scene
455                void build(KdRenderable * sceneRoot);
456
457                // test visibility of objects and add to render queue
458                void queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters,
459                        RenderMethod renderMethod, bool showBoxes = false);
460
461                // self-explanatory ...
462                int getMaxDepth() { return mMaxDepth; };
463                AxisAlignedBox getBox() { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); };
464                void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
465        protected:
466                // recursive insert funciton
467                void recInsert(KdTree::Node * node, KdRenderable * rend);
468                // helper functions for insert
469                void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
470                void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
471                void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
472                // build scene from a list of nodes rather than a hierarchy
473                KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
474                void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);
475
476                // recursively delete empty nodes
477                void recDelete(KdTree::Node * node);
478
479                // find the best plane for node division
480                SplitInfo * pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
481
482                // priority queue based build function
483                KdTree::Node * pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
484                // recursive build function
485                KdTree::Node * recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
486
487                // recursive rendering function
488                void recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame,
489                        Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);
490                // stack based rendering function
491                void stackQueueVisibleObjects(KdTree::Node * root, unsigned long currentFrame,
492                        Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);
493
494                // the root node of the kdtree
495                KdTree::Node * mKdRoot;
496                // Maximum depth of the tree
497                int mMaxDepth;
498
499                // how to build the tree
500                BuildMethod mBuildMethod;
501
502                // logfile for tree creation
503                Log * mBuildLog;
504
505                // DEBUG
506                void KdTree::dump(KdTree::Node * node);
507                Real KdTree::calcCost(KdTree::Node * node, Real vs);
508        }; // class KdTree
509
510} // namespace Ogre
511
512#endif // _OgreKdTree_H__
Note: See TracBrowser for help on using the repository browser.