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-2013 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 */
28 /***************************************************************************
29 octree.h  -  description
30 -------------------
31 begin                : Mon Sep 30 2002
32 copyright            : (C) 2002 by Jon Anderson
33 email                : janders@users.sf.net
34 
35 ***************************************************************************/
36 
37 #ifndef OCTREE_H
38 #define OCTREE_H
39 
40 #include <OgreAxisAlignedBox.h>
41 #include <OgreWireBoundingBox.h>
42 
43 #include <list>
44 
45 namespace Ogre
46 {
47 
48 class OctreeNode;
49 
50 /** Octree datastructure for managing scene nodes.
51 @remarks
52 This is a loose octree implementation, meaning that each
53 octant child of the octree actually overlaps it's siblings by a factor
54 of .5.  This guarantees that any thing that is half the size of the parent will
55 fit completely into a child, with no splitting necessary.
56 */
57 
58 class Octree : public NodeAlloc
59 {
60 public:
61     Octree( Octree * p );
62     ~Octree();
63 
64     /** Adds an Octree scene node to this octree level.
65     @remarks
66     This is called by the OctreeSceneManager after
67     it has determined the correct Octree to insert the node into.
68     */
69     void _addNode( OctreeNode * );
70 
71     /** Removes an Octree scene node to this octree level.
72     */
73     void _removeNode( OctreeNode * );
74 
75     /** Returns the number of scene nodes attached to this octree
76     */
numNodes()77     int numNodes()
78     {
79         return mNumNodes;
80     };
81 
82     /** The bounding box of the octree
83     @remarks
84     This is used for octant index determination and rendering, but not culling
85     */
86     AxisAlignedBox mBox;
87     WireBoundingBox* mWireBoundingBox;
88 
89     /** Creates the wire frame bounding box for this octant
90     */
91     WireBoundingBox* getWireBoundingBox();
92 
93     /** Vector containing the dimensions of this octree / 2
94     */
95     Vector3 mHalfSize;
96 
97     /** 3D array of children of this octree.
98     @remarks
99     Children are dynamically created as needed when nodes are inserted in the Octree.
100     If, later, all the nodes are removed from the child, it is still kept around.
101     */
102     Octree * mChildren[ 2 ][ 2 ][ 2 ];
103 
104     /** Determines if this octree is twice as big as the given box.
105     @remarks
106     This method is used by the OctreeSceneManager to determine if the given
107     box will fit into a child of this octree.
108     */
109     bool _isTwiceSize( const AxisAlignedBox &box ) const;
110 
111     /**  Returns the appropriate indexes for the child of this octree into which the box will fit.
112     @remarks
113     This is used by the OctreeSceneManager to determine which child to traverse next when
114     finding the appropriate octree to insert the box.  Since it is a loose octree, only the
115     center of the box is checked to determine the octant.
116     */
117     void _getChildIndexes( const AxisAlignedBox &, int *x, int *y, int *z ) const;
118 
119     /** Creates the AxisAlignedBox used for culling this octree.
120     @remarks
121     Since it's a loose octree, the culling bounds can be different than the actual bounds of the octree.
122     */
123     void _getCullBounds( AxisAlignedBox * ) const;
124 
125 
126 	typedef list< OctreeNode * >::type NodeList;
127     /** Public list of SceneNodes attached to this particular octree
128     */
129     NodeList mNodes;
130 
131 protected:
132 
133     /** Increments the overall node count of this octree and all its parents
134     */
_ref()135     inline void _ref()
136     {
137         mNumNodes++;
138 
139         if ( mParent != 0 ) mParent -> _ref();
140     };
141 
142     /** Decrements the overall node count of this octree and all its parents
143     */
_unref()144     inline void _unref()
145     {
146         mNumNodes--;
147 
148         if ( mParent != 0 ) mParent -> _unref();
149     };
150 
151     ///number of SceneNodes in this octree and all its children.
152     int mNumNodes;
153 
154     ///parent octree
155     Octree * mParent;
156 
157 };
158 
159 }
160 
161 #endif
162 
163 
164