Blender  V3.3
btGImpactBvh.h
Go to the documentation of this file.
1 #ifndef BT_GIMPACT_BVH_H_INCLUDED
2 #define BT_GIMPACT_BVH_H_INCLUDED
3 
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 
28 
29 #include "btBoxCollision.h"
30 #include "btTriangleShapeEx.h"
31 #include "btGImpactBvhStructs.h"
32 
34 class btPairSet : public btAlignedObjectArray<GIM_PAIR>
35 {
36 public:
38  {
39  reserve(32);
40  }
41  inline void push_pair(int index1, int index2)
42  {
43  push_back(GIM_PAIR(index1, index2));
44  }
45 
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 
61 class btBvhTree
62 {
63 protected:
66 
67 protected:
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:
78  {
79  m_num_nodes = 0;
80  }
81 
84  void build_tree(GIM_BVH_DATA_ARRAY& primitive_boxes);
85 
87  {
89  m_num_nodes = 0;
90  }
91 
94  {
95  return m_num_nodes;
96  }
97 
99  SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
100  {
101  return m_node_array[nodeindex].isLeafNode();
102  }
103 
104  SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
105  {
106  return m_node_array[nodeindex].getDataIndex();
107  }
108 
109  SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB& bound) const
110  {
111  bound = m_node_array[nodeindex].m_bound;
112  }
113 
114  SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB& bound)
115  {
116  m_node_array[nodeindex].m_bound = bound;
117  }
118 
119  SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
120  {
121  return nodeindex + 1;
122  }
123 
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 
130  SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
131  {
132  return m_node_array[nodeindex].getEscapeIndex();
133  }
134 
136  {
137  return &m_node_array[index];
138  }
139 
141 };
142 
144 
150 {
151 public:
153 
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;
159  virtual void get_primitive_triangle(int prim_index, btPrimitiveTriangle& triangle) const = 0;
160 };
161 
163 
168 {
169 protected:
172 
173 protected:
174  //stackless refit
175  void refit();
176 
177 public:
180  {
182  }
183 
186  {
187  m_primitive_manager = primitive_manager;
188  }
189 
191  {
192  btAABB totalbox;
193  getNodeBound(0, totalbox);
194  return totalbox;
195  }
196 
198  {
199  m_primitive_manager = primitive_manager;
200  }
201 
203  {
204  return m_primitive_manager;
205  }
206 
209 
212  {
213  refit();
214  }
215 
217  void buildSet();
218 
220  bool boxQuery(const btAABB& box, btAlignedObjectArray<int>& collided_results) const;
221 
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 
232  bool rayQuery(
233  const btVector3& ray_dir, const btVector3& ray_origin,
234  btAlignedObjectArray<int>& collided_results) const;
235 
238  {
239  return true;
240  }
241 
244  {
246  }
247 
250  {
251  return m_box_tree.getNodeCount();
252  }
253 
255  SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
256  {
257  return m_box_tree.isLeafNode(nodeindex);
258  }
259 
260  SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
261  {
262  return m_box_tree.getNodeData(nodeindex);
263  }
264 
265  SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB& bound) const
266  {
267  m_box_tree.getNodeBound(nodeindex, bound);
268  }
269 
270  SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB& bound)
271  {
272  m_box_tree.setNodeBound(nodeindex, bound);
273  }
274 
275  SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
276  {
277  return m_box_tree.getLeftNode(nodeindex);
278  }
279 
280  SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
281  {
282  return m_box_tree.getRightNode(nodeindex);
283  }
284 
285  SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
286  {
287  return m_box_tree.getEscapeNodeIndex(nodeindex);
288  }
289 
290  SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex, btPrimitiveTriangle& triangle) const
291  {
293  }
294 
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
btAABB
Axis aligned box.
SIMD_FORCE_INLINE btVector3 transform(const btVector3 &point) const
#define SIMD_FORCE_INLINE
Definition: btScalar.h:280
btTransform
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition: btTransform.h:30
btVector3
btVector3 can be used to represent 3D points and vectors. It has an un-used w component to suit 16-by...
Definition: btVector3.h:82
Node Structure for trees.
SIMD_FORCE_INLINE void reserve(int _Count)
SIMD_FORCE_INLINE void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
SIMD_FORCE_INLINE void push_back(const GIM_PAIR &_Val)
Basic Box tree structure.
Definition: btGImpactBvh.h:62
void _build_sub_tree(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex)
SIMD_FORCE_INLINE int getNodeCount() const
node count
Definition: btGImpactBvh.h:93
int _calc_splitting_axis(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex)
GIM_BVH_TREE_NODE_ARRAY m_node_array
Definition: btGImpactBvh.h:65
int m_num_nodes
Definition: btGImpactBvh.h:64
SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
Definition: btGImpactBvh.h:124
SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB &bound)
Definition: btGImpactBvh.h:114
SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
tells if the node is a leaf
Definition: btGImpactBvh.h:99
SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
Definition: btGImpactBvh.h:130
SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
Definition: btGImpactBvh.h:104
SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
Definition: btGImpactBvh.h:119
SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB &bound) const
Definition: btGImpactBvh.h:109
SIMD_FORCE_INLINE void clearNodes()
Definition: btGImpactBvh.h:86
int _sort_and_calc_splitting_index(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex, int splitAxis)
SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index=0) const
Definition: btGImpactBvh.h:135
void build_tree(GIM_BVH_DATA_ARRAY &primitive_boxes)
stackless build tree
Structure for containing Boxes.
Definition: btGImpactBvh.h:168
void buildSet()
this rebuild the entire set
SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
tells if the node is a leaf
Definition: btGImpactBvh.h:255
SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB &box, const btTransform &transform, btAlignedObjectArray< int > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
Definition: btGImpactBvh.h:223
bool boxQuery(const btAABB &box, btAlignedObjectArray< int > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
Definition: btGImpactBvh.h:285
SIMD_FORCE_INLINE bool hasHierarchy() const
tells if this set has hierarcht
Definition: btGImpactBvh.h:237
SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
Definition: btGImpactBvh.h:260
SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex, btPrimitiveTriangle &triangle) const
Definition: btGImpactBvh.h:290
SIMD_FORCE_INLINE bool isTrimesh() const
tells if this set is a trimesh
Definition: btGImpactBvh.h:243
SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB &bound)
Definition: btGImpactBvh.h:270
SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase *primitive_manager)
Definition: btGImpactBvh.h:197
SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
Definition: btGImpactBvh.h:202
btGImpactBvh()
this constructor doesn't build the tree. you must call buildSet
Definition: btGImpactBvh.h:179
bool rayQuery(const btVector3 &ray_dir, const btVector3 &ray_origin, btAlignedObjectArray< int > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
Definition: btGImpactBvh.h:275
SIMD_FORCE_INLINE void update()
this attemps to refit the box set.
Definition: btGImpactBvh.h:211
btBvhTree m_box_tree
Definition: btGImpactBvh.h:170
btPrimitiveManagerBase * m_primitive_manager
Definition: btGImpactBvh.h:171
SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
Definition: btGImpactBvh.h:280
SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB &bound) const
Definition: btGImpactBvh.h:265
static void find_collision(btGImpactBvh *boxset1, const btTransform &trans1, btGImpactBvh *boxset2, const btTransform &trans2, btPairSet &collision_pairs)
btGImpactBvh(btPrimitiveManagerBase *primitive_manager)
this constructor doesn't build the tree. you must call buildSet
Definition: btGImpactBvh.h:185
SIMD_FORCE_INLINE const GIM_BVH_TREE_NODE * get_node_pointer(int index=0) const
Definition: btGImpactBvh.h:295
SIMD_FORCE_INLINE int getNodeCount() const
node count
Definition: btGImpactBvh.h:249
SIMD_FORCE_INLINE btAABB getGlobalBox() const
Definition: btGImpactBvh.h:190
A pairset array.
Definition: btGImpactBvh.h:35
void push_pair(int index1, int index2)
Definition: btGImpactBvh.h:41
void push_pair_inv(int index1, int index2)
Definition: btGImpactBvh.h:46
Prototype Base class for primitive classification.
Definition: btGImpactBvh.h:150
virtual void get_primitive_triangle(int prim_index, btPrimitiveTriangle &triangle) const =0
retrieves only the points of the triangle, and the collision margin
virtual ~btPrimitiveManagerBase()
Definition: btGImpactBvh.h:152
virtual bool is_trimesh() const =0
determines if this manager consist on only triangles, which special case will be optimized
virtual int get_primitive_count() const =0
virtual void get_primitive_box(int prim_index, btAABB &primbox) const =0
Overlapping pair.
Definition: gim_pair.h:7