source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreBiHierarchy.h @ 2402

Revision 2402, 22.2 KB checked in by mattausch, 17 years ago (diff)
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 _OgreBiHierarchy_H__
11#define _OgreBiHierarchy_H__
12
13#define BIHNODE_CAST(a) (static_cast<BiHierarchy::Node>(a))
14#define BIHBRANCH_CAST(a) (static_cast<BiHierarchy::Branch>(a))
15#define BIHLEAF_CAST(a) (static_cast<BiHierarchy::Leaf>(a))
16#define BIHNODEPTR_CAST(a) (static_cast<BiHierarchy::Node *>(a))
17#define BIHBRANCHPTR_CAST(a) (static_cast<BiHierarchy::Branch *>(a))
18#define BIHLEAFPTR_CAST(a) (static_cast<BiHierarchy::Leaf *>(a))
19
20#define BiHierarchy_LOGNAME "BiHierarchyBuild.log"
21
22#include <OgreAxisAlignedBox.h>
23#include <OgreWireBoundingBox.h>
24#include <OgrePlane.h>
25#include <OgreVector3.h>
26
27#include <OgreRoot.h>
28
29#include <stack>
30
31#include "OgreBiHierarchyCamera.h"
32#include "HierarchyInterface.h"
33#include "OgreKdTree.h"
34
35namespace Ogre
36{
37        class BiHierarchyCamera;
38        class BihRenderable;
39        struct BihSplitInfo;
40       
41        class BihPlaneEvent
42        {
43        public:
44                enum Type
45                {
46                        PET_END,
47                        PET_ON,
48                        PET_START
49                };
50
51                enum Dimension
52                {
53                        PED_X,
54                        PED_Y,
55                        PED_Z
56                };
57
58                enum Side
59                {
60                        PES_LEFT = 0x01,
61                        PES_RIGHT = 0x02,
62                        PES_BOTH = PES_LEFT | PES_RIGHT
63                };
64
65                BihPlaneEvent(): mRenderable(0), mPosition(Vector3()), mDimension(PED_X), mType(PET_ON)
66                { };
67
68                BihPlaneEvent(BihRenderable *rend, const Vector3& pos, BihPlaneEvent::Dimension dim, BihPlaneEvent::Type type):
69                        mRenderable(rend), mPosition(pos), mDimension(dim), mType(type)
70                { };
71
72                ~BihPlaneEvent() {};
73
74                // the less operator for plane events
75                // first sort by position, then by dimension and finally by type
76                bool operator < (const BihPlaneEvent& e) const
77                {
78                        if(mPosition[mDimension] < e.mPosition[e.mDimension])
79                        {
80                                return true;
81                        }
82
83                        if(mPosition[mDimension] == e.mPosition[e.mDimension])
84                        {
85                                if (mDimension < e.mDimension)
86                                {
87                                        return true;
88                                }
89                                if (mDimension == e.mDimension)
90                                {
91                                        if (mType < e.mType)
92                                        {
93                                                return true;
94                                        }
95                                }
96                        }
97
98                        return false;
99                };
100
101                // the equals operator for tree events
102                bool operator == (const BihPlaneEvent& e) const
103                {
104                        return  (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
105                                (mDimension == e.mDimension) &&
106                                (mType == e.mType);
107                };
108
109                bool equalsType(const BihPlaneEvent& e, BihPlaneEvent::Type t)
110                {
111                        return  (mPosition[mDimension] == e.mPosition[e.mDimension]) &&
112                                (mDimension == e.mDimension) &&
113                                (mType == t);
114                };
115
116                void classify(const BihPlaneEvent& e, BihPlaneEvent::Side side, bool absolute);
117
118                BihPlaneEvent clip(AxisAlignedBox& box, BihPlaneEvent::Dimension dim);
119
120                BihPlaneEvent::Type GetType() { return mType;};
121
122                void ClearGrowBB()
123                {
124                        IncBB.setNull();
125                }
126
127                void GrowBB(AxisAlignedBox bb)
128                {
129                        IncBB.merge(bb);
130                }
131
132                AxisAlignedBox GetGrowBB()
133                {
134                        return IncBB;
135                }
136
137
138
139
140
141                Plane * getSplitPlane() const
142                {
143                        Vector3 normal(0,0,0);
144                        normal[mDimension] = 1;
145                        return new Plane(normal, mPosition);
146                }
147
148            Vector3 getPosition()
149                {
150                        return mPosition;
151                }
152
153                BihRenderable * getRenderable() const //??
154                {
155                        return mRenderable;
156                };
157
158                BihPlaneEvent::Dimension getDimension() const //??
159                {
160                        return mDimension;
161                };
162
163                // DEBUG
164                String print();
165        protected:
166                // event info
167                BihRenderable *                 mRenderable;
168                Vector3                                 mPosition;
169                BihPlaneEvent::Dimension        mDimension;
170                BihPlaneEvent::Type             mType;
171                AxisAlignedBox IncBB;
172
173                // ------------------------------------------------------------------------------//
174                // functions to determine the cost of splitting the node parent with the plane
175                // represented by this event
176                // TODO discuss if these functions really belong here, OO & SE - wise
177                // pros: convenient, don't have to pass internal data to the outside
178                // cons: BihSplitInfo ...
179        public:
180                // compute "global" surface area heuristic (SAH) for the plane represented by this event
181                // use only with priority queue build method
182                void pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, BihSplitInfo& split);
183                static Real pqSplitCost(Real p, Real pl, Real pr, int nLeft, int nRight, Real mu);
184
185                // compute the surface area heuristic (SAH) for the plane represented by this event
186                void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split);
187                void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split,AxisAlignedBox left,AxisAlignedBox right);
188
189                // the variables determining the cost of a branch traversal (KT) and a leaf intersection (KI)
190                static Real KT;
191                static Real KI;
192                // helper functions
193                static Real splitCost(Real pl, Real pr, int nLeft, int nRight);
194                static Real splitCost(Real pl, Real pr, int nLeft, int nRight, Real mu);
195                static Real surfaceArea(const AxisAlignedBox& box);
196                static Real lookupPenalty(Real p);
197        protected:
198                Real splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right);
199        };
200
201        // Holds all the important information on a split
202        struct BihSplitInfo
203        {
204                AxisAlignedBox bleft;
205                AxisAlignedBox bright;
206                int nleft;
207                int nright;
208                Real cost;
209                BihPlaneEvent::Side side;
210                BihPlaneEvent event;
211
212                // DEBUG
213                String print();
214        };
215
216        typedef std::list<BihRenderable *> BihRenderableList;
217        typedef std::list<BihPlaneEvent> BihPlaneEventList;
218       
219        class BiHierarchy
220        {
221        protected:
222                class Branch;
223                class Leaf;
224
225                class Node
226                {
227                public:
228                        Node(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch * parent):
229                        mOwner(owner),
230                        mLevel(level),
231                        mAABB(aabb),
232                        mParent(parent),
233                        mWBB(0),
234                        m_iSide(0)
235                        { };
236
237                        virtual ~Node()
238                        {
239                                delete mWBB;
240                        };
241
242                        virtual bool isLeaf() const = 0;
243                        virtual bool isEmpty() const = 0;
244                        virtual bool hasGeometry() const = 0;
245                       
246                        virtual void mergeLeaves(std::set<Leaf *>& leaves) = 0;
247
248                        // Gets this node's parent (NULL if this is the root).
249                        BiHierarchy::Node *getParent(void) const { return mParent; };
250
251                        // Gets the nodes left & right child nodes, or NULL if not present or node is leaf
252                        virtual BiHierarchy::Node *getLeftChild(void) const = 0;
253                        virtual BiHierarchy::Node *getRightChild(void) const = 0;
254
255                        // add contained objects to render queue
256                        virtual void queueVisibleObjects(unsigned long currentFrame,
257                                Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false) = 0;
258
259                        // add contained geometry (Entities) to list
260                        virtual void getGeometryList(GeometryVector *geometryList) = 0;
261                       
262                        // create (when necessary), setup and return wire bounding box representing the node
263                        WireBoundingBox * getWireBoundingBox()
264                        {
265                                if (mWBB == 0)
266                                        mWBB = new WireBoundingBox();
267
268                                if (mOwner->getShowNodes())
269                                        mWBB->setupBoundingBox(mAABB);
270                                else
271                                        mWBB->setupBoundingBox(mWorldAABB);
272
273                                // cse
274                                if (mOwner->getHiLiteLevel() == mLevel)
275                                        switch (m_iSide)
276                                        {
277                                        case 0:
278                                                {
279                                                        mWBB->setMaterial("BiHierarchy/BoxViz"); break;
280                                                }
281                                        case 1: {
282                                                     mWBB->setMaterial("BiHierarchy/BoxLeft"); break;
283                                                        }
284                                        default:
285                                                {
286                                                        mWBB->setMaterial("BiHierarchy/BoxRight");
287                                                }
288                                        }
289                                 else if (mOwner->getHiLiteLevel() == (mLevel+1))
290                                 {
291                                       
292                                                        mWBB->setMaterial("BiHierarchy/BoxViz");
293                                       
294                                       
295                                 } else
296                                 {
297                                        switch (m_iSide)
298                                        {
299                                        case 0:
300                                                {
301                                                        mWBB->setMaterial("BiHierarchy/BoxViz"); break;
302                                                }
303                                        case 1: {
304                                                     mWBB->setMaterial("BiHierarchy/BoxLeftDark"); break;
305                                                        }
306                                        default:
307                                                {
308                                                        mWBB->setMaterial("BiHierarchy/BoxRightDark");
309                                                }
310                                        }
311                               
312                                       
313                                 }
314                               
315                                return mWBB;
316                        }
317
318                        // returns the level the node is on
319                        int getLevel(void) const { return mLevel; };
320
321                        void SetToLeft() {
322                                m_iSide=1;
323                        };
324                        void SetToRight() {
325                                m_iSide=2;
326                        };
327                        int GetSide() { return m_iSide; };
328
329
330                        // functions for the CHC hierarchy interface
331
332                        /** Returns last visited frame id. */
333                        unsigned int lastVisited(void) { return mLastVisited; };
334                        /** Set to current frame id.
335                        @param current frame id.
336                        */
337                        void setLastVisited(unsigned int frameid) { mLastVisited = frameid; };
338                        /** Makes this octree become visible / invisble.
339                        @param visible Whether this node is to be made visible or invisible
340                        */
341                        void setNodeVisible(bool visible) { mVisible = visible; };
342                        /** Returns true if this node is marked visible, false otherwise.
343                        */
344                        bool isNodeVisible(void) { return mVisible; };
345                        /** Frame id when this octree was last rendered.
346                        @return last rendered frame id
347                        */     
348                        unsigned int lastRendered(void) { return mLastRendered; };
349                        /** Sets frame id when this octree was last rendered.
350                        @param last rendered frame id
351                        */
352                        void setLastRendered(unsigned int frameid) { mLastRendered = frameid; };
353                        /** Returns real extent of the BiHierarchy, i.e., the merged extent of the bounding boxes.
354                        */
355                        AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
356                        /** Updates bound of the real aabb of BiHierarchy
357                        */
358                        virtual void _updateBounds(bool recurse = true) = 0;
359                       
360                        /** bounding box of the node
361                        */
362                        AxisAlignedBox mAABB;
363
364                        /** bounding box of all objects inside the node
365                        */
366                        AxisAlignedBox mWorldAABB;
367
368
369                protected:
370                        BiHierarchy * mOwner;
371                        Branch * mParent;
372                        int mLevel;
373                        int m_iSide; // defines the side ( left / right ) for better debugging.
374
375                        WireBoundingBox * mWBB;
376                       
377                        // for the CHC hierarchy interface
378                        unsigned int mLastRendered;
379                        unsigned int mLastVisited;
380                        bool mVisible;
381                };
382
383                class Branch : public Node
384                {
385                public:
386                        Branch(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch * parent,
387                                Plane * splitplane, BihPlaneEvent::Side side):
388                        Node(owner, level, aabb, parent),
389                        mSplitPlane(splitplane),
390                        mLeft(0),
391                        mRight(0),
392                        mPlaneSide(side)
393                        { };
394
395                        virtual ~Branch()
396                        {
397                                delete mLeft;
398                                delete mRight;
399                                delete mSplitPlane;
400                        };
401
402                        // a branch is not a leaf
403                        virtual bool isLeaf() const { return false; };
404
405                        // s branch is empty when it does not have children
406                        virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
407
408                        // a branch never has geometry
409                        virtual bool hasGeometry() const { return false; };
410
411                        virtual void mergeLeaves(std::set<Leaf *>& leaves)
412                        {
413                                for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it++)
414                                        leaves.insert(*it);
415                        }
416
417                        // a branch should have at least one child
418                        virtual BiHierarchy::Node * getLeftChild() const { return mLeft; };
419                        virtual BiHierarchy::Node * getRightChild() const { return mRight; };
420
421                        virtual void queueVisibleObjects(unsigned long currentFrame,
422                                Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false)
423                        {
424                                // cse
425                                showBoxes=true;
426                                if (showBoxes)
427                                {
428                                        /*
429                                        if (mLevel == mOwner->getHiLiteLevel()|| (mLevel-1) == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
430                                        queue->addRenderable(getWireBoundingBox());
431                                        */
432                                       
433                                        if (mLevel == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
434                                                queue->addRenderable(getWireBoundingBox());
435                                       
436                                }
437
438                                if (fullVis)
439                                        for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it ++)
440                                                (*it)->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, fullVis);
441                        }
442
443                        // a branch has no geometry, do nothing
444                        virtual void getGeometryList(GeometryVector *geometryList) { }
445
446                        // branches do not posses geometry => just merge child aabbs
447                        virtual void _updateBounds(bool recurse = true)
448                        {
449                                // reset box
450                                mWorldAABB.setNull();
451
452                                // merge box & leaves
453                                if (mLeft)
454                                {
455                                        mWorldAABB.merge(mLeft->mWorldAABB);
456                                        mLeft->mergeLeaves(mLeaves);
457                                }
458                                if (mRight)
459                                {
460                                        mWorldAABB.merge(mRight->mWorldAABB);
461                                        mRight->mergeLeaves(mLeaves);
462                                }
463
464                                // update parent recursively
465                                if (recurse && mParent)
466                                        mParent->_updateBounds(recurse);
467                        }
468                       
469                        Node * mLeft;
470                        Node * mRight;
471                        Plane  * mSplitPlane;
472                        BihPlaneEvent::Side mPlaneSide;
473                protected:
474                        std::set<Leaf *> mLeaves;
475                };
476
477                class Leaf : public Node
478                {
479                public:
480                        Leaf(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch *parent):
481                        Node(owner, level, aabb, parent)
482                        {};
483
484                        virtual ~Leaf();
485
486                        // a leaf is a leaf, dammit
487                        virtual bool isLeaf() const { return true; }
488
489                        // a leaf is empty when it does not posses renderables
490                        virtual bool isEmpty() const { return mBihRenderables.empty(); }
491
492                        // a leaf has geometry when it has renderables
493                        virtual bool hasGeometry() const { return !mBihRenderables.empty(); }
494
495                        // a leaf adds itself to the leaf set
496                        virtual void mergeLeaves(std::set<Leaf *>& leaves)      { leaves.insert(this); }
497
498                        // a leaf never has children
499                        virtual BiHierarchy::Node * getLeftChild() const { return 0; };
500                        virtual BiHierarchy::Node * getRightChild() const { return 0; };
501
502                        virtual void queueVisibleObjects(unsigned long currentFrame,
503                                Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false);
504
505                        virtual void getGeometryList(GeometryVector *geometryList);
506
507                        // update the world aabb based on the contained geometry
508                        virtual void _updateBounds(bool recurse = true);
509
510                        virtual void remove(BihRenderable * rend)
511                        {
512                                mBihRenderables.remove(rend);
513                                //mBihRenderables.erase(find(mBihRenderables.begin(), mBihRenderables.end(), rend));
514                        };
515
516                        virtual void insert(BihRenderable * rend)
517                        {
518                                mBihRenderables.push_back(rend);
519                        };
520
521                        BihRenderableList mBihRenderables;
522                };
523
524                struct BihSubdivisionCandidate
525                {
526                        BihSubdivisionCandidate(BihPlaneEventList * e, int n, AxisAlignedBox& a,
527                                BiHierarchy::Branch * p, Real c, Real d, BihSplitInfo * b, BihPlaneEvent::Side s):
528                        events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s)
529                        { };
530
531                        bool operator < (const BihSubdivisionCandidate& rhs) const
532                        {
533                                return decrease < rhs.decrease;
534                        };
535
536                        void operator = (const BihSubdivisionCandidate& rhs)
537                        {
538                                decrease = rhs.decrease;
539                                cost = rhs.cost;
540                                nObjects = rhs.nObjects;
541                                side = rhs.side;
542                                aabb = rhs.aabb;
543                                events = rhs.events;
544                                parent = rhs.parent;
545                                best = rhs.best;
546                        };
547
548                        // DEBUG
549                        String print();
550
551                        Real decrease;
552                        Real cost;
553                        int nObjects;
554                        BihPlaneEvent::Side side;
555                        AxisAlignedBox aabb;
556                        BihPlaneEventList *events;
557                        BiHierarchy::Branch * parent;
558                        BihSplitInfo * best;
559                };
560
561                // typedef std::stack<BihSubdivisionCandidate> SplitCandidatePQ;
562                typedef std::priority_queue<BihSubdivisionCandidate> SplitCandidatePQ;
563
564                // nodestack for the stack-based rendering function
565                typedef std::stack<BiHierarchy::Node *> NodeStack;
566        public:
567                friend class BiHierarchyInterface;
568
569                typedef BiHierarchy::Node * NodePtr;
570                typedef BiHierarchy::Branch * BranchPtr;
571                typedef BiHierarchy::Leaf * LeafPtr;
572
573                typedef std::list<NodePtr> NodeList;
574                typedef std::set<LeafPtr> LeafSet;
575
576                struct TreeStats
577                {
578                        unsigned int mNumNodes;
579                        unsigned int mNumLeaves;
580                        unsigned int mNumSceneNodes;
581
582                        void clear(void)
583                        {
584                                mNumNodes = 0;
585                                mNumLeaves = 0;
586                                mNumSceneNodes = 0;
587                        }
588                };
589
590                struct FrameStats
591                {
592                        unsigned int mTraversedNodes;
593                        unsigned int mRenderedNodes;
594                        unsigned int mFrustumCulledNodes;
595
596                        void clear(void)
597                        {
598                                mTraversedNodes = 0;
599                                mRenderedNodes = 0;
600                                mFrustumCulledNodes = 0;
601                        }
602                };
603
604                enum RenderMethod
605                {
606                        BIHRM_INTERNAL,
607                        BIHRM_GTP_VFC,
608                        BIHRM_GTP_SWC,
609                        BIHRM_GTP_CHC,
610                        BIHRM_GTP_RU,
611                        // invalid modes, just for convenience
612                        BIHRM_SIZE,
613                        BIHRM_NOTSET
614                };
615
616                enum BuildMethod
617                {
618                        BIHBM_RECURSIVE,
619                        BIHBM_PRIORITYQUEUE,
620                        // invalid modes, just for convenience
621                        BIHBM_SIZE,
622                        BIHBM_NOTSET
623                };
624
625                enum PlaneAlorithm
626                {
627                        BIHAL_SAH,
628                        BIHAL_MID
629                };
630
631
632                const static int HILITE_OFF  = -1;
633               
634                BiHierarchy(int maxdepth, BuildMethod bm);
635                BiHierarchy(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes);
636                virtual ~BiHierarchy();
637
638                // DEBUG
639                void dump(void);
640                Real calcCost(void);
641
642                // sets the level to highlight or turns it off (when hilite < 0)
643                inline void setHiLiteLevel(int hilite) { mHiLiteLevel = hilite; };
644                inline int  getHiLiteLevel(void) { return mHiLiteLevel; };
645
646                // toggles displaying the BiHierarchy boxes
647                inline void setShowAllBoxes(bool show) { mShowAllBoxes = show; };
648                inline bool getShowAllBoxes(void) { return mShowAllBoxes; };
649
650                // toggles between displaying the bounding box of the node and
651                // the box of the contained scene nodes
652                inline void setShowNodes(bool show = true) { mShowNodes = show; };
653                inline bool getShowNodes(void) { return mShowNodes; };
654
655                // changes vis mode (simple/enhanced with NONE/PART/FULL vis)
656                void setEnhancedVis(bool enh);
657                bool getEnhancedVis(void);
658
659                NodePtr getRoot(void) const { return mBihRoot; };
660
661                // insert a new scene node into an existing Bihierarchy
662                void insert(BihRenderable * rend);
663                // remove a scene node from the tree
664                void remove(BihRenderable * rend);
665                // function to initialize a kd-tree based on the contents of the scene
666                void build(BihRenderable * sceneRoot);
667
668                // test visibility of objects and add to render queue
669                void queueVisibleObjects(BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters,
670                        bool showBoxes, BiHierarchy::NodeList& visibleNodes);
671
672                // find visible nodes & place in list
673                //void findVisibleNodes(NodeList& visibleNodes, Camera * cam);
674
675                /** Recurses the BiHierarchy, adding any nodes intersecting with the
676                box/sphere/volume/ray into the given list.
677                It ignores the exclude scene node.
678                */
679                void findNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude = 0);
680                void findNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude = 0);
681                void findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude = 0);
682                void findNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude = 0);
683
684                // self-explanatory ...
685                int getMaxDepth(void) { return mMaxDepth; }
686                const TreeStats& getTreeStats(void) const { return mTreeStats; }
687                const FrameStats& getFramesStats(void) const { return mFrameStats; }
688                AxisAlignedBox getBox(void) { if (mBihRoot) return mBihRoot->mAABB; else return AxisAlignedBox(); }
689                void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
690        protected:
691                // init materials, logs and stuff
692                void init();
693                // recursive insert funciton
694                void recInsert(BiHierarchy::Node * node, BihRenderable * rend);
695                // helper functions for insert
696                void recInsertNew(BiHierarchy::Branch * parent, BihPlaneEvent::Side side, BihRenderable * rend);
697                void splitBox(const BiHierarchy::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
698                void rebuildSubtree(BiHierarchy::Node * node, BihRenderable * rend);
699                // build scene from a list of nodes rather than a hierarchy
700                BiHierarchy::Node * buildFromList(BihRenderableList& nodelist, BiHierarchy::Branch * parent, AxisAlignedBox& aabb);
701                void addRendToList(BiHierarchy::Node * node, BihRenderableList& nodelist);
702
703                // recursively delete empty nodes
704                void recDelete(BiHierarchy::Node * node);
705
706                // find the best plane for node division
707                BihSplitInfo * pqFindPlane(BihPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
708
709                // priority queue based build function
710                BiHierarchy::Node * pqBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent);
711                // recursive build function
712                BiHierarchy::Node * recBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent);
713
714                // recursive rendering function
715                void recQueueVisibleObjects(BiHierarchy::Node * node, unsigned long currentFrame, BiHierarchyCamera* cam,
716                        RenderQueue* queue, bool onlyShadowCasters, bool showBoxes,
717                        BiHierarchy::NodeList& visibleNodes, bool fullVis = false);
718
719                // recursively find visible nodes
720                //void recFindVisibleNodes(BiHierarchy::Node * node, NodeList& visibleNodes, Camera * cam);
721
722                /** Recurses the BiHierarchy, adding any nodes intersecting with the
723                box/sphere/volume/ray into the given list.
724                It ignores the exclude scene node.
725                */
726                void recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
727                void recFindNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
728                void recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
729                void recFindNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
730
731                // the root node of the BiHierarchy
732                BiHierarchy::Node * mBihRoot;
733                // Maximum depth of the tree
734                int mMaxDepth;
735
736                // how to build the tree
737                BuildMethod mBuildMethod;
738
739                // what algorithm will be used to find the split plane
740                PlaneAlorithm mAlgorithm;
741
742                // logfile for tree creation
743                Log * mBuildLog;
744
745                // statistical information on the tree
746                TreeStats mTreeStats;
747
748                // statistical info on a single rendered frame
749                FrameStats mFrameStats;
750
751                /** Visualization flags **/
752                // show/highlight selected level in BiHierarchy
753                int mHiLiteLevel;
754                // show whole kd-tree
755                bool mShowAllBoxes;
756                // show node or object boxes
757                bool mShowNodes;
758
759                // function pointer to the getVisibility function
760                // allows choosing between regular vis (NONE/PART, same es isVisible)
761                // and enhaced vis (NONE/PART/FULL) for early traversal abort
762                BiHierarchyCamera::NodeVisibility (BiHierarchyCamera::*getVisibility)(const AxisAlignedBox& box) const;
763
764                // DEBUG
765                void BiHierarchy::dump(BiHierarchy::Node * node);
766                Real BiHierarchy::calcCost(BiHierarchy::Node * node, Real vs);
767        }; // class BiHierarchy
768
769} // namespace Ogre
770
771#endif // _OgreBiHierarchy_H__
Note: See TracBrowser for help on using the repository browser.