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