src/BulletCollision/Gimpact/btGImpactBvh.h

   1 #ifndef GIM_BOX_SET_H_INCLUDED
   2 #define GIM_BOX_SET_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
  28 #include "LinearMath/btAlignedObjectArray.h"
  29
  30 #include "btBoxCollision.h"
  31 #include "btTriangleShapeEx.h"
  32
  33
  34
  35
  36
  37 //! Overlapping pair
  38 struct GIM_PAIR
  39 {
  40     int m_index1;
  41     int m_index2;
  42     GIM_PAIR()
  43     {}
  44
  45     GIM_PAIR(const GIM_PAIR & p)
  46     {
  47         m_index1 = p.m_index1;
  48         m_index2 = p.m_index2;
  49         }
  50
  51         GIM_PAIR(int index1, int index2)
  52     {
  53         m_index1 = index1;
  54         m_index2 = index2;
  55         }
  56 };
  57
  58 //! A pairset array
  59 class btPairSet: public btAlignedObjectArray<GIM_PAIR>
  60 {
  61 public:
  62         btPairSet()
  63         {
  64                 reserve(32);
  65         }
  66         inline void push_pair(int index1,int index2)
  67         {
  68                 push_back(GIM_PAIR(index1,index2));
  69         }
  70
  71         inline void push_pair_inv(int index1,int index2)
  72         {
  73                 push_back(GIM_PAIR(index2,index1));
  74         }
  75 };
  76
  77
  78 ///GIM_BVH_DATA is an internal GIMPACT collision structure to contain axis aligned bounding box
  79 struct GIM_BVH_DATA
  80 {
  81         btAABB m_bound;
  82         int m_data;
  83 };
  84
  85 //! Node Structure for trees
  86 class GIM_BVH_TREE_NODE
  87 {
  88 public:
  89         btAABB m_bound;
  90 protected:
  91         int     m_escapeIndexOrDataIndex;
  92 public:
  93         GIM_BVH_TREE_NODE()
  94         {
  95                 m_escapeIndexOrDataIndex = 0;
  96         }
  97
  98         SIMD_FORCE_INLINE bool isLeafNode() const
  99         {
 100                 //skipindex is negative (internal node), triangleindex >=0 (leafnode)
 101                 return (m_escapeIndexOrDataIndex>=0);
 102         }
 103
 104         SIMD_FORCE_INLINE int getEscapeIndex() const
 105         {
 106                 //btAssert(m_escapeIndexOrDataIndex < 0);
 107                 return -m_escapeIndexOrDataIndex;
 108         }
 109
 110         SIMD_FORCE_INLINE void setEscapeIndex(int index)
 111         {
 112                 m_escapeIndexOrDataIndex = -index;
 113         }
 114
 115         SIMD_FORCE_INLINE int getDataIndex() const
 116         {
 117                 //btAssert(m_escapeIndexOrDataIndex >= 0);
 118
 119                 return m_escapeIndexOrDataIndex;
 120         }
 121
 122         SIMD_FORCE_INLINE void setDataIndex(int index)
 123         {
 124                 m_escapeIndexOrDataIndex = index;
 125         }
 126
 127 };
 128
 129
 130 class GIM_BVH_DATA_ARRAY:public btAlignedObjectArray<GIM_BVH_DATA>
 131 {
 132 };
 133
 134
 135 class GIM_BVH_TREE_NODE_ARRAY:public btAlignedObjectArray<GIM_BVH_TREE_NODE>
 136 {
 137 };
 138
 139
 140
 141
 142 //! Basic Box tree structure
 143 class btBvhTree
 144 {
 145 protected:
 146         int m_num_nodes;
 147         GIM_BVH_TREE_NODE_ARRAY m_node_array;
 148 protected:
 149         int _sort_and_calc_splitting_index(
 150                 GIM_BVH_DATA_ARRAY & primitive_boxes,
 151                  int startIndex,  int endIndex, int splitAxis);
 152
 153         int _calc_splitting_axis(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
 154
 155         void _build_sub_tree(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
 156 public:
 157         btBvhTree()
 158         {
 159                 m_num_nodes = 0;
 160         }
 161
 162         //! prototype functions for box tree management
 163         //!@{
 164         void build_tree(GIM_BVH_DATA_ARRAY & primitive_boxes);
 165
 166         SIMD_FORCE_INLINE void clearNodes()
 167         {
 168                 m_node_array.clear();
 169                 m_num_nodes = 0;
 170         }
 171
 172         //! node count
 173         SIMD_FORCE_INLINE int getNodeCount() const
 174         {
 175                 return m_num_nodes;
 176         }
 177
 178         //! tells if the node is a leaf
 179         SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
 180         {
 181                 return m_node_array[nodeindex].isLeafNode();
 182         }
 183
 184         SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
 185         {
 186                 return m_node_array[nodeindex].getDataIndex();
 187         }
 188
 189         SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
 190         {
 191                 bound = m_node_array[nodeindex].m_bound;
 192         }
 193
 194         SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
 195         {
 196                 m_node_array[nodeindex].m_bound = bound;
 197         }
 198
 199         SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
 200         {
 201                 return nodeindex+1;
 202         }
 203
 204         SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
 205         {
 206                 if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
 207                 return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
 208         }
 209
 210         SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
 211         {
 212                 return m_node_array[nodeindex].getEscapeIndex();
 213         }
 214
 215         SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index = 0) const
 216         {
 217                 return &m_node_array[index];
 218         }
 219
 220         //!@}
 221 };
 222
 223
 224 //! Prototype Base class for primitive classification
 225 /*!
 226 This class is a wrapper for primitive collections.
 227 This tells relevant info for the Bounding Box set classes, which take care of space classification.
 228 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.
 229 */
 230 class btPrimitiveManagerBase
 231 {
 232 public:
 233
 234         virtual ~btPrimitiveManagerBase() {}
 235
 236         //! determines if this manager consist on only triangles, which special case will be optimized
 237         virtual bool is_trimesh() const = 0;
 238         virtual int get_primitive_count() const = 0;
 239         virtual void get_primitive_box(int prim_index ,btAABB & primbox) const = 0;
 240         //! retrieves only the points of the triangle, and the collision margin
 241         virtual void get_primitive_triangle(int prim_index,btPrimitiveTriangle & triangle) const= 0;
 242 };
 243
 244
 245 //! Structure for containing Boxes
 246 /*!
 247 This class offers an structure for managing a box tree of primitives.
 248 Requires a Primitive prototype (like btPrimitiveManagerBase )
 249 */
 250 class btGImpactBvh
 251 {
 252 protected:
 253         btBvhTree m_box_tree;
 254         btPrimitiveManagerBase * m_primitive_manager;
 255
 256 protected:
 257         //stackless refit
 258         void refit();
 259 public:
 260
 261         //! this constructor doesn't build the tree. you must call      buildSet
 262         btGImpactBvh()
 263         {
 264                 m_primitive_manager = NULL;
 265         }
 266
 267         //! this constructor doesn't build the tree. you must call      buildSet
 268         btGImpactBvh(btPrimitiveManagerBase * primitive_manager)
 269         {
 270                 m_primitive_manager = primitive_manager;
 271         }
 272
 273         SIMD_FORCE_INLINE btAABB getGlobalBox()  const
 274         {
 275                 btAABB totalbox;
 276                 getNodeBound(0, totalbox);
 277                 return totalbox;
 278         }
 279
 280         SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
 281         {
 282                 m_primitive_manager = primitive_manager;
 283         }
 284
 285         SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
 286         {
 287                 return m_primitive_manager;
 288         }
 289
 290
 291 //! node manager prototype functions
 292 ///@{
 293
 294         //! this attemps to refit the box set.
 295         SIMD_FORCE_INLINE void update()
 296         {
 297                 refit();
 298         }
 299
 300         //! this rebuild the entire set
 301         void buildSet();
 302
 303         //! returns the indices of the primitives in the m_primitive_manager
 304         bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
 305
 306         //! returns the indices of the primitives in the m_primitive_manager
 307         SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
 308                  const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
 309         {
 310                 btAABB transbox=box;
 311                 transbox.appy_transform(transform);
 312                 return boxQuery(transbox,collided_results);
 313         }
 314
 315         //! returns the indices of the primitives in the m_primitive_manager
 316         bool rayQuery(
 317                 const btVector3 & ray_dir,const btVector3 & ray_origin ,
 318                 btAlignedObjectArray<int> & collided_results) const;
 319
 320         //! tells if this set has hierarcht
 321         SIMD_FORCE_INLINE bool hasHierarchy() const
 322         {
 323                 return true;
 324         }
 325
 326         //! tells if this set is a trimesh
 327         SIMD_FORCE_INLINE bool isTrimesh()  const
 328         {
 329                 return m_primitive_manager->is_trimesh();
 330         }
 331
 332         //! node count
 333         SIMD_FORCE_INLINE int getNodeCount() const
 334         {
 335                 return m_box_tree.getNodeCount();
 336         }
 337
 338         //! tells if the node is a leaf
 339         SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
 340         {
 341                 return m_box_tree.isLeafNode(nodeindex);
 342         }
 343
 344         SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
 345         {
 346                 return m_box_tree.getNodeData(nodeindex);
 347         }
 348
 349         SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
 350         {
 351                 m_box_tree.getNodeBound(nodeindex, bound);
 352         }
 353
 354         SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
 355         {
 356                 m_box_tree.setNodeBound(nodeindex, bound);
 357         }
 358
 359
 360         SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
 361         {
 362                 return m_box_tree.getLeftNode(nodeindex);
 363         }
 364
 365         SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
 366         {
 367                 return m_box_tree.getRightNode(nodeindex);
 368         }
 369
 370         SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
 371         {
 372                 return m_box_tree.getEscapeNodeIndex(nodeindex);
 373         }
 374
 375         SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
 376         {
 377                 m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
 378         }
 379
 380
 381         SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index = 0) const
 382         {
 383                 return m_box_tree.get_node_pointer(index);
 384         }
 385
 386 #ifdef TRI_COLLISION_PROFILING
 387         static float getAverageTreeCollisionTime();
 388 #endif //TRI_COLLISION_PROFILING
 389
 390         static void find_collision(btGImpactBvh * boxset1, const btTransform & trans1,
 391                 btGImpactBvh * boxset2, const btTransform & trans2,
 392                 btPairSet & collision_pairs);
 393 };
 394
 395
 396 #endif // GIM_BOXPRUNING_H_INCLUDED