src/BulletCollision/Gimpact/btGImpactQuantizedBvh.h

   1 #ifndef GIM_QUANTIZED_SET_H_INCLUDED
   2 #define GIM_QUANTIZED_SET_H_INCLUDED
   3
   4 /*! \file btGImpactQuantizedBvh.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 "btGImpactBvh.h"
  28 #include "btQuantization.h"
  29
  30
  31
  32
  33
  34 ///btQuantizedBvhNode is a compressed aabb node, 16 bytes.
  35 ///Node can be used for leafnode or internal node. Leafnodes can point to 32-bit triangle index (non-negative range).
  36 ATTRIBUTE_ALIGNED16     (struct) BT_QUANTIZED_BVH_NODE
  37 {
  38         //12 bytes
  39         unsigned short int      m_quantizedAabbMin[3];
  40         unsigned short int      m_quantizedAabbMax[3];
  41         //4 bytes
  42         int     m_escapeIndexOrDataIndex;
  43
  44         BT_QUANTIZED_BVH_NODE()
  45         {
  46                 m_escapeIndexOrDataIndex = 0;
  47         }
  48
  49         SIMD_FORCE_INLINE bool isLeafNode() const
  50         {
  51                 //skipindex is negative (internal node), triangleindex >=0 (leafnode)
  52                 return (m_escapeIndexOrDataIndex>=0);
  53         }
  54
  55         SIMD_FORCE_INLINE int getEscapeIndex() const
  56         {
  57                 //btAssert(m_escapeIndexOrDataIndex < 0);
  58                 return -m_escapeIndexOrDataIndex;
  59         }
  60
  61         SIMD_FORCE_INLINE void setEscapeIndex(int index)
  62         {
  63                 m_escapeIndexOrDataIndex = -index;
  64         }
  65
  66         SIMD_FORCE_INLINE int getDataIndex() const
  67         {
  68                 //btAssert(m_escapeIndexOrDataIndex >= 0);
  69
  70                 return m_escapeIndexOrDataIndex;
  71         }
  72
  73         SIMD_FORCE_INLINE void setDataIndex(int index)
  74         {
  75                 m_escapeIndexOrDataIndex = index;
  76         }
  77
  78         SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
  79                 unsigned short * quantizedMin,unsigned short * quantizedMax) const
  80         {
  81                 if(m_quantizedAabbMin[0] > quantizedMax[0] ||
  82                    m_quantizedAabbMax[0] < quantizedMin[0] ||
  83                    m_quantizedAabbMin[1] > quantizedMax[1] ||
  84                    m_quantizedAabbMax[1] < quantizedMin[1] ||
  85                    m_quantizedAabbMin[2] > quantizedMax[2] ||
  86                    m_quantizedAabbMax[2] < quantizedMin[2])
  87                 {
  88                         return false;
  89                 }
  90                 return true;
  91         }
  92
  93 };
  94
  95
  96
  97 class GIM_QUANTIZED_BVH_NODE_ARRAY:public btAlignedObjectArray<BT_QUANTIZED_BVH_NODE>
  98 {
  99 };
 100
 101
 102
 103
 104 //! Basic Box tree structure
 105 class btQuantizedBvhTree
 106 {
 107 protected:
 108         int m_num_nodes;
 109         GIM_QUANTIZED_BVH_NODE_ARRAY m_node_array;
 110         btAABB m_global_bound;
 111         btVector3 m_bvhQuantization;
 112 protected:
 113         void calc_quantization(GIM_BVH_DATA_ARRAY & primitive_boxes, btScalar boundMargin = btScalar(1.0) );
 114
 115         int _sort_and_calc_splitting_index(
 116                 GIM_BVH_DATA_ARRAY & primitive_boxes,
 117                  int startIndex,  int endIndex, int splitAxis);
 118
 119         int _calc_splitting_axis(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
 120
 121         void _build_sub_tree(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
 122 public:
 123         btQuantizedBvhTree()
 124         {
 125                 m_num_nodes = 0;
 126         }
 127
 128         //! prototype functions for box tree management
 129         //!@{
 130         void build_tree(GIM_BVH_DATA_ARRAY & primitive_boxes);
 131
 132         SIMD_FORCE_INLINE void quantizePoint(
 133                 unsigned short * quantizedpoint, const btVector3 & point) const
 134         {
 135                 bt_quantize_clamp(quantizedpoint,point,m_global_bound.m_min,m_global_bound.m_max,m_bvhQuantization);
 136         }
 137
 138
 139         SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
 140                 int node_index,
 141                 unsigned short * quantizedMin,unsigned short * quantizedMax) const
 142         {
 143                 return m_node_array[node_index].testQuantizedBoxOverlapp(quantizedMin,quantizedMax);
 144         }
 145
 146         SIMD_FORCE_INLINE void clearNodes()
 147         {
 148                 m_node_array.clear();
 149                 m_num_nodes = 0;
 150         }
 151
 152         //! node count
 153         SIMD_FORCE_INLINE int getNodeCount() const
 154         {
 155                 return m_num_nodes;
 156         }
 157
 158         //! tells if the node is a leaf
 159         SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
 160         {
 161                 return m_node_array[nodeindex].isLeafNode();
 162         }
 163
 164         SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
 165         {
 166                 return m_node_array[nodeindex].getDataIndex();
 167         }
 168
 169         SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
 170         {
 171                 bound.m_min = bt_unquantize(
 172                         m_node_array[nodeindex].m_quantizedAabbMin,
 173                         m_global_bound.m_min,m_bvhQuantization);
 174
 175                 bound.m_max = bt_unquantize(
 176                         m_node_array[nodeindex].m_quantizedAabbMax,
 177                         m_global_bound.m_min,m_bvhQuantization);
 178         }
 179
 180         SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
 181         {
 182                 bt_quantize_clamp(      m_node_array[nodeindex].m_quantizedAabbMin,
 183                                                         bound.m_min,
 184                                                         m_global_bound.m_min,
 185                                                         m_global_bound.m_max,
 186                                                         m_bvhQuantization);
 187
 188                 bt_quantize_clamp(      m_node_array[nodeindex].m_quantizedAabbMax,
 189                                                         bound.m_max,
 190                                                         m_global_bound.m_min,
 191                                                         m_global_bound.m_max,
 192                                                         m_bvhQuantization);
 193         }
 194
 195         SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
 196         {
 197                 return nodeindex+1;
 198         }
 199
 200         SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
 201         {
 202                 if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
 203                 return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
 204         }
 205
 206         SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
 207         {
 208                 return m_node_array[nodeindex].getEscapeIndex();
 209         }
 210
 211         SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
 212         {
 213                 return &m_node_array[index];
 214         }
 215
 216         //!@}
 217 };
 218
 219
 220
 221 //! Structure for containing Boxes
 222 /*!
 223 This class offers an structure for managing a box tree of primitives.
 224 Requires a Primitive prototype (like btPrimitiveManagerBase )
 225 */
 226 class btGImpactQuantizedBvh
 227 {
 228 protected:
 229         btQuantizedBvhTree m_box_tree;
 230         btPrimitiveManagerBase * m_primitive_manager;
 231
 232 protected:
 233         //stackless refit
 234         void refit();
 235 public:
 236
 237         //! this constructor doesn't build the tree. you must call      buildSet
 238         btGImpactQuantizedBvh()
 239         {
 240                 m_primitive_manager = NULL;
 241         }
 242
 243         //! this constructor doesn't build the tree. you must call      buildSet
 244         btGImpactQuantizedBvh(btPrimitiveManagerBase * primitive_manager)
 245         {
 246                 m_primitive_manager = primitive_manager;
 247         }
 248
 249         SIMD_FORCE_INLINE btAABB getGlobalBox()  const
 250         {
 251                 btAABB totalbox;
 252                 getNodeBound(0, totalbox);
 253                 return totalbox;
 254         }
 255
 256         SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
 257         {
 258                 m_primitive_manager = primitive_manager;
 259         }
 260
 261         SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
 262         {
 263                 return m_primitive_manager;
 264         }
 265
 266
 267 //! node manager prototype functions
 268 ///@{
 269
 270         //! this attemps to refit the box set.
 271         SIMD_FORCE_INLINE void update()
 272         {
 273                 refit();
 274         }
 275
 276         //! this rebuild the entire set
 277         void buildSet();
 278
 279         //! returns the indices of the primitives in the m_primitive_manager
 280         bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
 281
 282         //! returns the indices of the primitives in the m_primitive_manager
 283         SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
 284                  const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
 285         {
 286                 btAABB transbox=box;
 287                 transbox.appy_transform(transform);
 288                 return boxQuery(transbox,collided_results);
 289         }
 290
 291         //! returns the indices of the primitives in the m_primitive_manager
 292         bool rayQuery(
 293                 const btVector3 & ray_dir,const btVector3 & ray_origin ,
 294                 btAlignedObjectArray<int> & collided_results) const;
 295
 296         //! tells if this set has hierarcht
 297         SIMD_FORCE_INLINE bool hasHierarchy() const
 298         {
 299                 return true;
 300         }
 301
 302         //! tells if this set is a trimesh
 303         SIMD_FORCE_INLINE bool isTrimesh()  const
 304         {
 305                 return m_primitive_manager->is_trimesh();
 306         }
 307
 308         //! node count
 309         SIMD_FORCE_INLINE int getNodeCount() const
 310         {
 311                 return m_box_tree.getNodeCount();
 312         }
 313
 314         //! tells if the node is a leaf
 315         SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
 316         {
 317                 return m_box_tree.isLeafNode(nodeindex);
 318         }
 319
 320         SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
 321         {
 322                 return m_box_tree.getNodeData(nodeindex);
 323         }
 324
 325         SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
 326         {
 327                 m_box_tree.getNodeBound(nodeindex, bound);
 328         }
 329
 330         SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
 331         {
 332                 m_box_tree.setNodeBound(nodeindex, bound);
 333         }
 334
 335
 336         SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
 337         {
 338                 return m_box_tree.getLeftNode(nodeindex);
 339         }
 340
 341         SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
 342         {
 343                 return m_box_tree.getRightNode(nodeindex);
 344         }
 345
 346         SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
 347         {
 348                 return m_box_tree.getEscapeNodeIndex(nodeindex);
 349         }
 350
 351         SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
 352         {
 353                 m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
 354         }
 355
 356
 357         SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
 358         {
 359                 return m_box_tree.get_node_pointer(index);
 360         }
 361
 362 #ifdef TRI_COLLISION_PROFILING
 363         static float getAverageTreeCollisionTime();
 364 #endif //TRI_COLLISION_PROFILING
 365
 366         static void find_collision(const btGImpactQuantizedBvh * boxset1, const btTransform & trans1,
 367                 const btGImpactQuantizedBvh * boxset2, const btTransform & trans2,
 368                 btPairSet & collision_pairs);
 369 };
 370
 371
 372 #endif // GIM_BOXPRUNING_H_INCLUDED