1 #ifndef BT_GIMPACT_BVH_H_INCLUDED 2 #define BT_GIMPACT_BVH_H_INCLUDED 3 4 /*! \file gim_box_set.h 5 \author Francisco Leon Najera 6 */ 7 /* 8 This source file is part of GIMPACT Library. 9 10 For the latest info, see http://gimpact.sourceforge.net/ 11 12 Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371. 13 email: projectileman@yahoo.com 14 15 16 This software is provided 'as-is', without any express or implied warranty. 17 In no event will the authors be held liable for any damages arising from the use of this software. 18 Permission is granted to anyone to use this software for any purpose, 19 including commercial applications, and to alter it and redistribute it freely, 20 subject to the following restrictions: 21 22 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 23 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 24 3. This notice may not be removed or altered from any source distribution. 25 */ 26 27 #include "LinearMath/btAlignedObjectArray.h" 28 29 #include "btBoxCollision.h" 30 #include "btTriangleShapeEx.h" 31 #include "btGImpactBvhStructs.h" 32 33 //! A pairset array 34 class btPairSet : public btAlignedObjectArray<GIM_PAIR> 35 { 36 public: btPairSet()37 btPairSet() 38 { 39 reserve(32); 40 } push_pair(int index1,int index2)41 inline void push_pair(int index1, int index2) 42 { 43 push_back(GIM_PAIR(index1, index2)); 44 } 45 push_pair_inv(int index1,int index2)46 inline void push_pair_inv(int index1, int index2) 47 { 48 push_back(GIM_PAIR(index2, index1)); 49 } 50 }; 51 52 class GIM_BVH_DATA_ARRAY : public btAlignedObjectArray<GIM_BVH_DATA> 53 { 54 }; 55 56 class GIM_BVH_TREE_NODE_ARRAY : public btAlignedObjectArray<GIM_BVH_TREE_NODE> 57 { 58 }; 59 60 //! Basic Box tree structure 61 class btBvhTree 62 { 63 protected: 64 int m_num_nodes; 65 GIM_BVH_TREE_NODE_ARRAY m_node_array; 66 67 protected: 68 int _sort_and_calc_splitting_index( 69 GIM_BVH_DATA_ARRAY& primitive_boxes, 70 int startIndex, int endIndex, int splitAxis); 71 72 int _calc_splitting_axis(GIM_BVH_DATA_ARRAY& primitive_boxes, int startIndex, int endIndex); 73 74 void _build_sub_tree(GIM_BVH_DATA_ARRAY& primitive_boxes, int startIndex, int endIndex); 75 76 public: btBvhTree()77 btBvhTree() 78 { 79 m_num_nodes = 0; 80 } 81 82 //! prototype functions for box tree management 83 //!@{ 84 void build_tree(GIM_BVH_DATA_ARRAY& primitive_boxes); 85 clearNodes()86 SIMD_FORCE_INLINE void clearNodes() 87 { 88 m_node_array.clear(); 89 m_num_nodes = 0; 90 } 91 92 //! node count getNodeCount()93 SIMD_FORCE_INLINE int getNodeCount() const 94 { 95 return m_num_nodes; 96 } 97 98 //! tells if the node is a leaf isLeafNode(int nodeindex)99 SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const 100 { 101 return m_node_array[nodeindex].isLeafNode(); 102 } 103 getNodeData(int nodeindex)104 SIMD_FORCE_INLINE int getNodeData(int nodeindex) const 105 { 106 return m_node_array[nodeindex].getDataIndex(); 107 } 108 getNodeBound(int nodeindex,btAABB & bound)109 SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB& bound) const 110 { 111 bound = m_node_array[nodeindex].m_bound; 112 } 113 setNodeBound(int nodeindex,const btAABB & bound)114 SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB& bound) 115 { 116 m_node_array[nodeindex].m_bound = bound; 117 } 118 getLeftNode(int nodeindex)119 SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const 120 { 121 return nodeindex + 1; 122 } 123 getRightNode(int nodeindex)124 SIMD_FORCE_INLINE int getRightNode(int nodeindex) const 125 { 126 if (m_node_array[nodeindex + 1].isLeafNode()) return nodeindex + 2; 127 return nodeindex + 1 + m_node_array[nodeindex + 1].getEscapeIndex(); 128 } 129 getEscapeNodeIndex(int nodeindex)130 SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const 131 { 132 return m_node_array[nodeindex].getEscapeIndex(); 133 } 134 135 SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE* get_node_pointer(int index = 0) const 136 { 137 return &m_node_array[index]; 138 } 139 140 //!@} 141 }; 142 143 //! Prototype Base class for primitive classification 144 /*! 145 This class is a wrapper for primitive collections. 146 This tells relevant info for the Bounding Box set classes, which take care of space classification. 147 This class can manage Compound shapes and trimeshes, and if it is managing trimesh then the Hierarchy Bounding Box classes will take advantage of primitive Vs Box overlapping tests for getting optimal results and less Per Box compairisons. 148 */ 149 class btPrimitiveManagerBase 150 { 151 public: ~btPrimitiveManagerBase()152 virtual ~btPrimitiveManagerBase() {} 153 154 //! determines if this manager consist on only triangles, which special case will be optimized 155 virtual bool is_trimesh() const = 0; 156 virtual int get_primitive_count() const = 0; 157 virtual void get_primitive_box(int prim_index, btAABB& primbox) const = 0; 158 //! retrieves only the points of the triangle, and the collision margin 159 virtual void get_primitive_triangle(int prim_index, btPrimitiveTriangle& triangle) const = 0; 160 }; 161 162 //! Structure for containing Boxes 163 /*! 164 This class offers an structure for managing a box tree of primitives. 165 Requires a Primitive prototype (like btPrimitiveManagerBase ) 166 */ 167 class btGImpactBvh 168 { 169 protected: 170 btBvhTree m_box_tree; 171 btPrimitiveManagerBase* m_primitive_manager; 172 173 protected: 174 //stackless refit 175 void refit(); 176 177 public: 178 //! this constructor doesn't build the tree. you must call buildSet btGImpactBvh()179 btGImpactBvh() 180 { 181 m_primitive_manager = NULL; 182 } 183 184 //! this constructor doesn't build the tree. you must call buildSet btGImpactBvh(btPrimitiveManagerBase * primitive_manager)185 btGImpactBvh(btPrimitiveManagerBase* primitive_manager) 186 { 187 m_primitive_manager = primitive_manager; 188 } 189 getGlobalBox()190 SIMD_FORCE_INLINE btAABB getGlobalBox() const 191 { 192 btAABB totalbox; 193 getNodeBound(0, totalbox); 194 return totalbox; 195 } 196 setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)197 SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase* primitive_manager) 198 { 199 m_primitive_manager = primitive_manager; 200 } 201 getPrimitiveManager()202 SIMD_FORCE_INLINE btPrimitiveManagerBase* getPrimitiveManager() const 203 { 204 return m_primitive_manager; 205 } 206 207 //! node manager prototype functions 208 ///@{ 209 210 //! this attemps to refit the box set. update()211 SIMD_FORCE_INLINE void update() 212 { 213 refit(); 214 } 215 216 //! this rebuild the entire set 217 void buildSet(); 218 219 //! returns the indices of the primitives in the m_primitive_manager 220 bool boxQuery(const btAABB& box, btAlignedObjectArray<int>& collided_results) const; 221 222 //! returns the indices of the primitives in the m_primitive_manager boxQueryTrans(const btAABB & box,const btTransform & transform,btAlignedObjectArray<int> & collided_results)223 SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB& box, 224 const btTransform& transform, btAlignedObjectArray<int>& collided_results) const 225 { 226 btAABB transbox = box; 227 transbox.appy_transform(transform); 228 return boxQuery(transbox, collided_results); 229 } 230 231 //! returns the indices of the primitives in the m_primitive_manager 232 bool rayQuery( 233 const btVector3& ray_dir, const btVector3& ray_origin, 234 btAlignedObjectArray<int>& collided_results) const; 235 236 //! tells if this set has hierarcht hasHierarchy()237 SIMD_FORCE_INLINE bool hasHierarchy() const 238 { 239 return true; 240 } 241 242 //! tells if this set is a trimesh isTrimesh()243 SIMD_FORCE_INLINE bool isTrimesh() const 244 { 245 return m_primitive_manager->is_trimesh(); 246 } 247 248 //! node count getNodeCount()249 SIMD_FORCE_INLINE int getNodeCount() const 250 { 251 return m_box_tree.getNodeCount(); 252 } 253 254 //! tells if the node is a leaf isLeafNode(int nodeindex)255 SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const 256 { 257 return m_box_tree.isLeafNode(nodeindex); 258 } 259 getNodeData(int nodeindex)260 SIMD_FORCE_INLINE int getNodeData(int nodeindex) const 261 { 262 return m_box_tree.getNodeData(nodeindex); 263 } 264 getNodeBound(int nodeindex,btAABB & bound)265 SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB& bound) const 266 { 267 m_box_tree.getNodeBound(nodeindex, bound); 268 } 269 setNodeBound(int nodeindex,const btAABB & bound)270 SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB& bound) 271 { 272 m_box_tree.setNodeBound(nodeindex, bound); 273 } 274 getLeftNode(int nodeindex)275 SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const 276 { 277 return m_box_tree.getLeftNode(nodeindex); 278 } 279 getRightNode(int nodeindex)280 SIMD_FORCE_INLINE int getRightNode(int nodeindex) const 281 { 282 return m_box_tree.getRightNode(nodeindex); 283 } 284 getEscapeNodeIndex(int nodeindex)285 SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const 286 { 287 return m_box_tree.getEscapeNodeIndex(nodeindex); 288 } 289 getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle)290 SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex, btPrimitiveTriangle& triangle) const 291 { 292 m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex), triangle); 293 } 294 295 SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE* get_node_pointer(int index = 0) const 296 { 297 return m_box_tree.get_node_pointer(index); 298 } 299 300 #ifdef TRI_COLLISION_PROFILING 301 static float getAverageTreeCollisionTime(); 302 #endif //TRI_COLLISION_PROFILING 303 304 static void find_collision(btGImpactBvh* boxset1, const btTransform& trans1, 305 btGImpactBvh* boxset2, const btTransform& trans2, 306 btPairSet& collision_pairs); 307 }; 308 309 #endif // BT_GIMPACT_BVH_H_INCLUDED 310