1 /*
2 -----------------------------------------------------------------------------
3 This source file is part of OGRE
4 (Object-oriented Graphics Rendering Engine)
5 For the latest info, see http://www.ogre3d.org/
6 
7 Copyright (c) 2000-2014 Torus Knot Software Ltd
8 
9 Permission is hereby granted, free of charge, to any person obtaining a copy
10 of this software and associated documentation files (the "Software"), to deal
11 in the Software without restriction, including without limitation the rights
12 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 copies of the Software, and to permit persons to whom the Software is
14 furnished to do so, subject to the following conditions:
15 
16 The above copyright notice and this permission notice shall be included in
17 all copies or substantial portions of the Software.
18 
19 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 THE SOFTWARE.
26 -----------------------------------------------------------------------------
27 OgreOctree.h  -  description
28 -----------------------------------------------------------------------------
29 begin                : Mon Sep 30 2002
30 copyright            : (C) 2002 by Jon Anderson
31 email                : janders@users.sf.net
32 
33 Modified slightly for use with PCZSceneManager Octree Zones by Eric Cha
34 
35 -----------------------------------------------------------------------------
36 */
37 
38 #ifndef OCTREE_H
39 #define OCTREE_H
40 
41 #include "OgreAxisAlignedBox.h"
42 
43 #include <list>
44 
45 namespace Ogre
46 {
47 /** \addtogroup Plugins
48 *  @{
49 */
50 /** \addtogroup OctreeZone
51 *  @{
52     */
53 class PCZSceneNode;
54 class PCZone;
55 
56 typedef std::set< PCZSceneNode * > PCZSceneNodeList;
57 
58 
59 /** Octree datastructure for managing scene nodes.
60 @remarks
61 This is a loose octree implementation, meaning that each
62 octant child of the octree actually overlaps it's siblings by a factor
63 of .5.  This guarantees that any thing that is half the size of the parent will
64 fit completely into a child, with no splitting necessary.
65 */
66 
67 class Octree : public SceneCtlAllocatedObject
68 {
69 public:
70     Octree( PCZone * zone, Octree * p );
71     ~Octree();
72 
73     /** Adds an PCZscene node to this octree level.
74     @remarks
75     This is called by the OctreeZone after
76     it has determined the correct Octree to insert the node into.
77     */
78     void _addNode( PCZSceneNode * );
79 
80     /** Removes an PCZscene node to this octree level.
81     */
82     void _removeNode( PCZSceneNode * );
83 
84     /** Returns the number of scene nodes attached to this octree
85     */
numNodes()86     int numNodes()
87     {
88         return mNumNodes;
89     };
90 
91     /** The bounding box of the octree
92     @remarks
93     This is used for octant index determination and rendering, but not culling
94     */
95     AxisAlignedBox mBox;
96     WireBoundingBox* mWireBoundingBox;
97 
98     /** Creates the wire frame bounding box for this octant
99     */
100     WireBoundingBox* getWireBoundingBox();
101 
102     /** Vector containing the dimensions of this octree / 2
103     */
104     Vector3 mHalfSize;
105 
106     /** 3D array of children of this octree.
107     @remarks
108     Children are dynamically created as needed when nodes are inserted in the Octree.
109     If, later, all the nodes are removed from the child, it is still kept around.
110     */
111     Octree * mChildren[ 2 ][ 2 ][ 2 ];
112 
113     /** Determines if this octree is twice as big as the given box.
114     @remarks
115     This method is used by the OctreeSceneManager to determine if the given
116     box will fit into a child of this octree.
117     */
118     bool _isTwiceSize( const AxisAlignedBox &box ) const;
119 
120     /**  Returns the appropriate indexes for the child of this octree into which the box will fit.
121     @remarks
122     This is used by the OctreeSceneManager to determine which child to traverse next when
123     finding the appropriate octree to insert the box.  Since it is a loose octree, only the
124     center of the box is checked to determine the octant.
125     */
126     void _getChildIndexes( const AxisAlignedBox &, int *x, int *y, int *z ) const;
127 
128     /** Creates the AxisAlignedBox used for culling this octree.
129     @remarks
130     Since it's a loose octree, the culling bounds can be different than the actual bounds of the octree.
131     */
132     void _getCullBounds( AxisAlignedBox * ) const;
133 
134     /* Recurse through the Octree to find the scene nodes which intersect an aab
135     */
136     void _findNodes(const AxisAlignedBox &t,
137                     PCZSceneNodeList &list,
138                     PCZSceneNode *exclude,
139                     bool includeVisitors,
140                     bool full );
141 
142     /* Recurse through the Octree to find the scene nodes which intersect a ray
143     */
144     void _findNodes(const Ray &t,
145                     PCZSceneNodeList &list,
146                     PCZSceneNode *exclude,
147                     bool includeVisitors,
148                     bool full );
149 
150     /* Recurse through the Octree to find the scene nodes which intersect a sphere
151     */
152     void _findNodes(const Sphere &t,
153                     PCZSceneNodeList &list,
154                     PCZSceneNode *exclude,
155                     bool includeVisitors,
156                     bool full );
157 
158     /* Recurse through the Octree to find the scene nodes which intersect a PBV
159     */
160     void _findNodes(const PlaneBoundedVolume &t,
161                     PCZSceneNodeList &list,
162                     PCZSceneNode *exclude,
163                     bool includeVisitors,
164                     bool full );
165 
166     /** Public list of SceneNodes attached to this particular octree
167     */
168     PCZSceneNodeList mNodes;
169 
170     /* Zone that this octree is in */
171     PCZone * mZone;
172 
173 protected:
174 
175     /** Increments the overall node count of this octree and all its parents
176     */
_ref()177     inline void _ref()
178     {
179         mNumNodes++;
180 
181         if ( mParent != 0 ) mParent -> _ref();
182     };
183 
184     /** Decrements the overall node count of this octree and all its parents
185     */
_unref()186     inline void _unref()
187     {
188         mNumNodes--;
189 
190         if ( mParent != 0 ) mParent -> _unref();
191     };
192 
193     ///number of SceneNodes in this octree and all its children.
194     int mNumNodes;
195 
196     ///parent octree
197     Octree * mParent;
198 
199 };
200 /** @} */
201 /** @} */
202 }
203 
204 #endif
205 
206 
207