source: GTP/trunk/Lib/Geom/OgreStuff/include/opt/OgreBspNode.h @ 1809

Revision 1809, 10.5 KB checked in by gumbau, 18 years ago (diff)
Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of OGRE
4    (Object-oriented Graphics Rendering Engine)
5For the latest info, see http://www.ogre3d.org/
6
7Copyright (c) 2000-2005 The OGRE Team
8Also see acknowledgements in Readme.html
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25#ifndef _BspNode_H__
26#define _BspNode_H__
27
28#include "OgreBspPrerequisites.h"
29#include "OgrePlane.h"
30#include "OgreAxisAlignedBox.h"
31#include "OgreSceneQuery.h"
32
33namespace Ogre {
34
35    /** Encapsulates a node in a BSP tree.
36        A BSP tree represents space partitioned by planes . The space which is
37        partitioned is either the world (in the case of the root node) or the space derived
38        from their parent node. Each node can have elements which are in front or behind it, which are
39        it's children and these elements can either be further subdivided by planes,
40        or they can be undivided spaces or 'leaf nodes' - these are the nodes which actually contain
41        objects and world geometry.The leaves of the tree are the stopping point of any tree walking algorithm,
42        both for rendering and collision detection etc.</p>
43        Ogre chooses not to represent splitting nodes and leaves as separate structures, but to merge the two for simplicity
44        of the walking algorithm. If a node is a leaf, the isLeaf() method returns true and both getFront() and
45        getBack() return null pointers. If the node is a partitioning plane isLeaf() returns false and getFront()
46        and getBack() will return the corresponding BspNode objects.
47    */
48    class BspNode
49    {
50        friend class BspLevel;
51
52    public:
53        /** Constructor, only to be used by BspLevel. */
54        BspNode(BspLevel* owner, bool isLeaf);
55
56        BspNode();
57        ~BspNode();
58
59        /** Returns true if this node is a leaf (i.e. contains geometry) or false if it is a splitting plane.
60            A BspNode can either be a splitting plane (the typical representation of a BSP node) or an undivided
61            region contining geometry (a leaf node). Ogre represents both using the same class for simplicity
62            of tree walking. However it is important that you use this method to determine which type you are dealing
63            with, since certain methods are only supported with one of the subtypes. Details are given in the individual methods.
64            Note that I could have represented splitting / leaf nodes as a class hierarchy but the
65            virtual methods / run-time type identification would have a performance hit, and it would not make the
66            code much (any?) simpler anyway. I think this is a fair trade-off in this case.
67        */
68        bool isLeaf(void) const;
69
70        /** Returns a pointer to a BspNode containing the subspace on the positive side of the splitting plane.
71            This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this
72            method on a leaf node will throw an exception.
73        */
74        BspNode* getFront(void) const;
75
76        /** Returns a pointer to a BspNode containing the subspace on the negative side of the splitting plane.
77            This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this
78            method on a leaf node will throw an exception.
79        */
80        BspNode* getBack(void) const;
81
82        /** Determines which side of the splitting plane a worldspace point is.
83            This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this
84            method on a leaf node will throw an exception.
85        */
86        Plane::Side getSide (const Vector3& point) const;
87
88        /** Gets the next node down in the tree, with the intention of
89            locating the leaf containing the given point.
90            This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this
91            method on a leaf node will throw an exception.
92        */
93        BspNode* getNextNode(const Vector3& point) const;
94
95
96        /** Returns details of the plane which is used to subdivide the space of his node's children.
97            This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this
98            method on a leaf node will throw an exception.
99        */
100        const Plane& getSplitPlane(void) const;
101
102        /** Returns the axis-aligned box which contains this node if it is a leaf.
103            This method should only be called on a leaf node. It returns a box which can be used in calls like
104            Camera::isVisible to determine if the leaf node is visible in the view.
105        */
106        const AxisAlignedBox& getBoundingBox(void) const;
107
108        /** Returns the number of faces contained in this leaf node.
109            Should only be called on a leaf node.
110        */
111        int getNumFaceGroups(void) const;
112        /** Returns the index to the face group index list for this leaf node.
113            The contents of this buffer is a list of indexes which point to the
114            actual face groups held in a central buffer in the BspLevel class (in
115            actual fact for efficency the indexes themselves are also held in a single
116            buffer in BspLevel too). The reason for this indirection is that the buffer
117            of indexes to face groups is organised in chunks relative to nodes, whilst the
118            main buffer of face groups may not be.
119            Should only be called on a leaf node.
120        */
121        int getFaceGroupStart(void) const;
122
123        /** Determines if the passed in node (must also be a leaf) is visible from this leaf.
124            Must only be called on a leaf node, and the parameter must also be a leaf node. If
125            this method returns true, then the leaf passed in is visible from this leaf.
126            Note that internally this uses the Potentially Visible Set (PVS) which is precalculated
127            and stored with the BSP level.
128        */
129        bool isLeafVisible(const BspNode* leaf) const;
130
131        friend std::ostream& operator<< (std::ostream& o, BspNode& n);
132
133        /// Internal method for telling the node that a movable intersects it
134        void _addMovable(const MovableObject* mov);
135
136        /// Internal method for telling the node that a movable no longer intersects it
137        void _removeMovable(const MovableObject* mov);
138
139        /// Gets the signed distance to the dividing plane
140        Real getDistance(const Vector3& pos) const;
141
142        typedef std::set<const MovableObject*> IntersectingObjectSet;
143
144        struct Brush
145        {
146            std::list<Plane> planes;
147            SceneQuery::WorldFragment fragment; // For query reporting
148        };
149        typedef std::vector<Brush*> NodeBrushList; // Main brush memory held on level
150
151        /** Get the list of solid Brushes for this node.
152        @remarks Only applicable for leaf nodes.
153        */
154        const NodeBrushList& getSolidBrushes(void) const;
155    protected:
156        BspLevel* mOwner; // Back-reference to containing level
157        bool mIsLeaf;
158
159        // Node-only members
160        /** The plane which splits space in a non-leaf node.
161            Note that nodes do not allocate the memory for other nodes - for simplicity and bulk-allocation
162            of memory the BspLevel is responsible for assigning enough memory for all nodes in one go.
163        */
164        Plane mSplitPlane;
165        /** Pointer to the node in front of this non-leaf node. */
166        BspNode* mFront;
167        /** Pointer to the node behind this non-leaf node. */
168        BspNode* mBack;
169
170        // Leaf-only members
171        /** The cluster number of this leaf.
172            Leaf nodes are assigned to 'clusters' of nodes, which are used to group nodes together for
173            visibility testing. There is a lookup table which is used to determine if one cluster of leaves
174            is visible from another cluster. Whilst it would be possible to expand all this out so that
175            each node had a list of pointers to other visible nodes, this would be very expensive in terms
176            of storage (using the cluster method there is a table which is 1-bit squared per cluster, rounded
177            up to the nearest byte obviously, which uses far less space than 4-bytes per linked node per source
178            node). Of course the limitation here is that you have to each leaf in turn to determine if it is visible
179            rather than just following a list, but since this is only done once per frame this is not such a big
180            overhead.
181        */
182        int mVisCluster;
183
184        /** The axis-aligned box which bounds node if it is a leaf. */
185        AxisAlignedBox mBounds;
186        /** Number of face groups in this node if it is a leaf. */
187        int mNumFaceGroups;
188        /** Index to the part of the main leaf facegroup index buffer(held in BspLevel) for this leaf.
189            This leaf uses mNumFaceGroups from this pointer onwards. From here you use the index
190            in this buffer to look up the actual face.
191            Note that again for simplicity and bulk memory allocation the face
192            group list itself is allocated by the BspLevel for all nodes, and each leaf node is given a section of it to
193            work on. This saves lots of small memory allocations / deallocations which limits memory fragmentation.
194        */
195        int mFaceGroupStart;
196
197        IntersectingObjectSet mMovables;
198
199        NodeBrushList mSolidBrushes;
200    public:
201        const IntersectingObjectSet& getObjects(void) const { return mMovables; }
202
203
204    };
205
206
207}
208
209#endif
Note: See TracBrowser for help on using the repository browser.