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