Bullet Collision Detection & Physics Library
btGImpactQuantizedBvh.cpp
Go to the documentation of this file.
1
4/*
5This source file is part of GIMPACT Library.
6
7For the latest info, see http://gimpact.sourceforge.net/
8
9Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371.
10email: projectileman@yahoo.com
11
12
13This software is provided 'as-is', without any express or implied warranty.
14In no event will the authors be held liable for any damages arising from the use of this software.
15Permission is granted to anyone to use this software for any purpose,
16including commercial applications, and to alter it and redistribute it freely,
17subject to the following restrictions:
18
191. 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.
202. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
213. This notice may not be removed or altered from any source distribution.
22*/
23
26
27#ifdef TRI_COLLISION_PROFILING
29
32
34{
36}
37
39{
40 g_q_accum_tree_collision_time += g_q_tree_clock.getTimeMicroseconds();
42}
43
45float btGImpactQuantizedBvh::getAverageTreeCollisionTime()
46{
47 if (g_q_count_traversing == 0) return 0;
48
51
54 return avgtime;
55
56 // float avgtime = g_q_count_traversing;
57 // g_q_count_traversing = 0;
58 // return avgtime;
59}
60
61#endif //TRI_COLLISION_PROFILING
62
64
67{
68 //calc globa box
71
72 for (int i = 0; i < primitive_boxes.size(); i++)
73 {
74 global_bound.merge(primitive_boxes[i].m_bound);
75 }
76
79}
80
83{
84 int i;
85
88 int numIndices = endIndex - startIndex;
89
90 for (i = startIndex; i < endIndex; i++)
91 {
92 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
93 primitive_boxes[i].m_bound.m_min);
94 means += center;
95 }
96 means *= (btScalar(1.) / (btScalar)numIndices);
97
98 for (i = startIndex; i < endIndex; i++)
99 {
100 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
101 primitive_boxes[i].m_bound.m_min);
102 btVector3 diff2 = center - means;
103 diff2 = diff2 * diff2;
104 variance += diff2;
105 }
106 variance *= (btScalar(1.) / ((btScalar)numIndices - 1));
107
108 return variance.maxAxis();
109}
110
113 int endIndex, int splitAxis)
114{
115 int i;
117 int numIndices = endIndex - startIndex;
118
119 // average of centers
120 btScalar splitValue = 0.0f;
121
123 for (i = startIndex; i < endIndex; i++)
124 {
125 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
126 primitive_boxes[i].m_bound.m_min);
127 means += center;
128 }
129 means *= (btScalar(1.) / (btScalar)numIndices);
130
132
133 //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
134 for (i = startIndex; i < endIndex; i++)
135 {
136 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
137 primitive_boxes[i].m_bound.m_min);
138 if (center[splitAxis] > splitValue)
139 {
140 //swap
142 //swapLeafNodes(i,splitIndex);
143 splitIndex++;
144 }
145 }
146
147 //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
148 //otherwise the tree-building might fail due to stack-overflows in certain cases.
149 //unbalanced1 is unsafe: it can cause stack overflows
150 //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));
151
152 //unbalanced2 should work too: always use center (perfect balanced trees)
153 //bool unbalanced2 = true;
154
155 //this should be safe too:
156 int rangeBalancedIndices = numIndices / 3;
158
159 if (unbalanced)
160 {
161 splitIndex = startIndex + (numIndices >> 1);
162 }
163
165
166 return splitIndex;
167}
168
170{
171 int curIndex = m_num_nodes;
172 m_num_nodes++;
173
175
176 if ((endIndex - startIndex) == 1)
177 {
178 //We have a leaf node
180 m_node_array[curIndex].setDataIndex(primitive_boxes[startIndex].m_data);
181
182 return;
183 }
184 //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
185
186 //split axis
188
191 splitIndex //split axis
192 );
193
194 //calc this node bounding box
195
198
199 for (int i = startIndex; i < endIndex; i++)
200 {
201 node_bound.merge(primitive_boxes[i].m_bound);
202 }
203
205
206 //build left branch
208
209 //build right branch
211
212 m_node_array[curIndex].setEscapeIndex(m_num_nodes - curIndex);
213}
214
218{
220 // initialize node count to 0
221 m_num_nodes = 0;
222 // allocate nodes
224
226}
227
229
231{
232 int nodecount = getNodeCount();
233 while (nodecount--)
234 {
236 {
240 }
241 else
242 {
243 //const GIM_BVH_TREE_NODE * nodepointer = get_node_pointer(nodecount);
244 //get left bound
247
249
251 if (child_node)
252 {
254 bound.merge(temp_box);
255 }
256
258 if (child_node)
259 {
261 bound.merge(temp_box);
262 }
263
265 }
266 }
267}
268
271{
272 //obtain primitive boxes
275
276 for (int i = 0; i < primitive_boxes.size(); i++)
277 {
279 primitive_boxes[i].m_data = i;
280 }
281
283}
284
287{
288 int curIndex = 0;
289 int numNodes = getNodeCount();
290
291 //quantize box
292
293 unsigned short quantizedMin[3];
294 unsigned short quantizedMax[3];
295
298
299 while (curIndex < numNodes)
300 {
301 //catch bugs in tree data
302
305
306 if (isleafnode && aabbOverlap)
307 {
309 }
310
311 if (aabbOverlap || isleafnode)
312 {
313 //next subnode
314 curIndex++;
315 }
316 else
317 {
318 //skip node
320 }
321 }
322 if (collided_results.size() > 0) return true;
323 return false;
324}
325
328 const btVector3& ray_dir, const btVector3& ray_origin,
330{
331 int curIndex = 0;
332 int numNodes = getNodeCount();
333
334 while (curIndex < numNodes)
335 {
338
339 //catch bugs in tree data
340
341 bool aabbOverlap = bound.collide_ray(ray_origin, ray_dir);
343
344 if (isleafnode && aabbOverlap)
345 {
347 }
348
349 if (aabbOverlap || isleafnode)
350 {
351 //next subnode
352 curIndex++;
353 }
354 else
355 {
356 //skip node
358 }
359 }
360 if (collided_results.size() > 0) return true;
361 return false;
362}
363
366 const BT_BOX_BOX_TRANSFORM_CACHE& trans_cache_1to0,
367 int node0, int node1, bool complete_primitive_tests)
368{
369 btAABB box0;
370 boxset0->getNodeBound(node0, box0);
371 btAABB box1;
372 boxset1->getNodeBound(node1, box1);
373
375 // box1.appy_transform_trans_cache(trans_cache_1to0);
376 // return box0.has_collision(box1);
377}
378
379//stackless recursive collision routine
383 const BT_BOX_BOX_TRANSFORM_CACHE& trans_cache_1to0,
384 int node0, int node1, bool complete_primitive_tests)
385{
387 boxset0, boxset1, trans_cache_1to0,
388 node0, node1, complete_primitive_tests) == false) return; //avoid colliding internal nodes
389
390 if (boxset0->isLeafNode(node0))
391 {
392 if (boxset1->isLeafNode(node1))
393 {
394 // collision result
395 collision_pairs->push_pair(
396 boxset0->getNodeData(node0), boxset1->getNodeData(node1));
397 return;
398 }
399 else
400 {
401 //collide left recursive
402
405 collision_pairs, trans_cache_1to0,
406 node0, boxset1->getLeftNode(node1), false);
407
408 //collide right recursive
411 collision_pairs, trans_cache_1to0,
412 node0, boxset1->getRightNode(node1), false);
413 }
414 }
415 else
416 {
417 if (boxset1->isLeafNode(node1))
418 {
419 //collide left recursive
422 collision_pairs, trans_cache_1to0,
423 boxset0->getLeftNode(node0), node1, false);
424
425 //collide right recursive
426
429 collision_pairs, trans_cache_1to0,
430 boxset0->getRightNode(node0), node1, false);
431 }
432 else
433 {
434 //collide left0 left1
435
438 collision_pairs, trans_cache_1to0,
439 boxset0->getLeftNode(node0), boxset1->getLeftNode(node1), false);
440
441 //collide left0 right1
442
445 collision_pairs, trans_cache_1to0,
446 boxset0->getLeftNode(node0), boxset1->getRightNode(node1), false);
447
448 //collide right0 left1
449
452 collision_pairs, trans_cache_1to0,
453 boxset0->getRightNode(node0), boxset1->getLeftNode(node1), false);
454
455 //collide right0 right1
456
459 collision_pairs, trans_cache_1to0,
460 boxset0->getRightNode(node0), boxset1->getRightNode(node1), false);
461
462 } // else if node1 is not a leaf
463 } // else if node0 is not a leaf
464}
465
469{
470 if (boxset0->getNodeCount() == 0 || boxset1->getNodeCount() == 0) return;
471
472 BT_BOX_BOX_TRANSFORM_CACHE trans_cache_1to0;
473
474 trans_cache_1to0.calc_from_homogenic(trans0, trans1);
475
476#ifdef TRI_COLLISION_PROFILING
478#endif //TRI_COLLISION_PROFILING
479
482 &collision_pairs, trans_cache_1to0, 0, 0, true);
483#ifdef TRI_COLLISION_PROFILING
485#endif //TRI_COLLISION_PROFILING
486}
bool _quantized_node_collision(const btGImpactQuantizedBvh *boxset0, const btGImpactQuantizedBvh *boxset1, const BT_BOX_BOX_TRANSFORM_CACHE &trans_cache_1to0, int node0, int node1, bool complete_primitive_tests)
static void _find_quantized_collision_pairs_recursive(const btGImpactQuantizedBvh *boxset0, const btGImpactQuantizedBvh *boxset1, btPairSet *collision_pairs, const BT_BOX_BOX_TRANSFORM_CACHE &trans_cache_1to0, int node0, int node1, bool complete_primitive_tests)
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
void bt_calc_quantization_parameters(btVector3 &outMinBound, btVector3 &outMaxBound, btVector3 &bvhQuantization, const btVector3 &srcMinBound, const btVector3 &srcMaxBound, btScalar quantizationMargin)
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition btScalar.h:314
#define SIMD_FORCE_INLINE
Definition btScalar.h:98
#define btAssert(x)
Definition btScalar.h:153
Class for transforming a model1 to the space of model0.
void calc_from_homogenic(const btTransform &trans0, const btTransform &trans1)
Calc the transformation relative 1 to 0. Inverts matrics by transposing.
Axis aligned box.
bool overlapping_trans_cache(const btAABB &box, const BT_BOX_BOX_TRANSFORM_CACHE &transcache, bool fulltest) const
transcache is the transformation cache from box to this AABB
btVector3 m_min
btVector3 m_max
void invalidate()
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
void resize(int newsize, const T &fillData=T())
The btClock is a portable basic clock that measures accurate time in seconds, use for profiling.
Definition btQuickprof.h:23
void reset()
Resets the initial reference time.
Structure for containing Boxes.
int getNodeData(int nodeindex) const
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
btPrimitiveManagerBase * m_primitive_manager
void buildSet()
this rebuild the entire set
bool boxQuery(const btAABB &box, btAlignedObjectArray< int > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
bool isLeafNode(int nodeindex) const
tells if the node is a leaf
btQuantizedBvhTree m_box_tree
void setNodeBound(int nodeindex, const btAABB &bound)
int getNodeCount() const
node count
int getRightNode(int nodeindex) const
int getEscapeNodeIndex(int nodeindex) const
void getNodeBound(int nodeindex, btAABB &bound) const
int getLeftNode(int nodeindex) const
static void find_collision(const btGImpactQuantizedBvh *boxset1, const btTransform &trans1, const btGImpactQuantizedBvh *boxset2, const btTransform &trans2, btPairSet &collision_pairs)
A pairset array.
virtual int get_primitive_count() const =0
virtual void get_primitive_box(int prim_index, btAABB &primbox) const =0
void setNodeBound(int nodeindex, const btAABB &bound)
void _build_sub_tree(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex)
void quantizePoint(unsigned short *quantizedpoint, const btVector3 &point) const
void calc_quantization(GIM_BVH_DATA_ARRAY &primitive_boxes, btScalar boundMargin=btScalar(1.0))
void build_tree(GIM_BVH_DATA_ARRAY &primitive_boxes)
prototype functions for box tree management
GIM_QUANTIZED_BVH_NODE_ARRAY m_node_array
int _sort_and_calc_splitting_index(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex, int splitAxis)
int _calc_splitting_axis(GIM_BVH_DATA_ARRAY &primitive_boxes, int startIndex, int endIndex)
bool testQuantizedBoxOverlapp(int node_index, unsigned short *quantizedMin, unsigned short *quantizedMax) const
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition btTransform.h:30
btVector3 can be used to represent 3D points and vectors.
Definition btVector3.h:82
int maxAxis() const
Return the axis with the largest value Note return values are 0,1,2 for x, y, or z.
Definition btVector3.h:477