Bullet Collision Detection & Physics Library
gim_box_set.h
Go to the documentation of this file.
1#ifndef GIM_BOX_SET_H_INCLUDED
2#define GIM_BOX_SET_H_INCLUDED
3
7/*
8-----------------------------------------------------------------------------
9This source file is part of GIMPACT Library.
10
11For the latest info, see http://gimpact.sourceforge.net/
12
13Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
14email: projectileman@yahoo.com
15
16 This library is free software; you can redistribute it and/or
17 modify it under the terms of EITHER:
18 (1) The GNU Lesser General Public License as published by the Free
19 Software Foundation; either version 2.1 of the License, or (at
20 your option) any later version. The text of the GNU Lesser
21 General Public License is included with this library in the
22 file GIMPACT-LICENSE-LGPL.TXT.
23 (2) The BSD-style license that is included with this library in
24 the file GIMPACT-LICENSE-BSD.TXT.
25 (3) The zlib/libpng license that is included with this library in
26 the file GIMPACT-LICENSE-ZLIB.TXT.
27
28 This library is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
31 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
32
33-----------------------------------------------------------------------------
34*/
35
36#include "gim_array.h"
37#include "gim_radixsort.h"
38#include "gim_box_collision.h"
39#include "gim_tri_collision.h"
40#include "gim_pair.h"
41
43class gim_pair_set : public gim_array<GIM_PAIR>
44{
45public:
47 {
48 }
50 {
52 }
53
55 {
57 }
58};
59
61
67{
68public:
71 virtual bool is_trimesh() = 0;
75};
76
78{
81};
82
85{
91
93 {
94 m_left = 0;
95 m_right = 0;
96 m_escapeIndex = 0;
97 m_data = 0;
98 }
99
101 {
102 return (!m_left && !m_right);
103 }
104};
105
108{
109protected:
112
113protected:
117
119
121
122public:
124 {
125 m_num_nodes = 0;
126 }
127
131
133 {
135 m_num_nodes = 0;
136 }
137
140 {
141 return m_num_nodes;
142 }
143
146 {
147 return m_node_array[nodeindex].is_leaf_node();
148 }
149
151 {
153 }
154
156 {
157 bound = m_node_array[nodeindex].m_bound;
158 }
159
161 {
162 m_node_array[nodeindex].m_bound = bound;
163 }
164
166 {
167 return m_node_array[nodeindex].m_left;
168 }
169
171 {
172 return m_node_array[nodeindex].m_right;
173 }
174
176 {
177 return m_node_array[nodeindex].m_escapeIndex;
178 }
179
181};
182
184
189template <typename _GIM_PRIMITIVE_MANAGER_PROTOTYPE, typename _GIM_BOX_TREE_PROTOTYPE>
191{
192protected:
195
196protected:
197 //stackless refit
199 {
201 while (nodecount--)
202 {
204 {
208 }
209 else
210 {
211 //get left bound
215 //get right bound
219 bound.merge(bound2);
220
222 }
223 }
224 }
225
226public:
228 {
229 }
230
232 {
235 return totalbox;
236 }
237
239 {
241 }
242
244 {
245 return m_primitive_manager;
246 }
247
249 {
250 return m_primitive_manager;
251 }
252
255
258 {
259 refit();
260 }
261
264 {
265 //obtain primitive boxes
267 primitive_boxes.resize(m_primitive_manager.get_primitive_count(), false);
268
269 for (GUINT i = 0; i < primitive_boxes.size(); i++)
270 {
271 m_primitive_manager.get_primitive_box(i, primitive_boxes[i].m_bound);
272 primitive_boxes[i].m_data = i;
273 }
274
275 m_box_tree.build_tree(primitive_boxes);
276 }
277
280 {
281 GUINT curIndex = 0;
283
284 while (curIndex < numNodes)
285 {
288
289 //catch bugs in tree data
290
291 bool aabbOverlap = bound.has_collision(box);
293
294 if (isleafnode && aabbOverlap)
295 {
297 }
298
299 if (aabbOverlap || isleafnode)
300 {
301 //next subnode
302 curIndex++;
303 }
304 else
305 {
306 //skip node
308 }
309 }
310 if (collided_results.size() > 0) return true;
311 return false;
312 }
313
316 const btTransform& transform, gim_array<GUINT>& collided_results) const
317 {
319 transbox.appy_transform(transform);
321 }
322
325 const btVector3& ray_dir, const btVector3& ray_origin,
327 {
328 GUINT curIndex = 0;
330
331 while (curIndex < numNodes)
332 {
335
336 //catch bugs in tree data
337
338 bool aabbOverlap = bound.collide_ray(ray_origin, ray_dir);
340
341 if (isleafnode && aabbOverlap)
342 {
344 }
345
346 if (aabbOverlap || isleafnode)
347 {
348 //next subnode
349 curIndex++;
350 }
351 else
352 {
353 //skip node
355 }
356 }
357 if (collided_results.size() > 0) return true;
358 return false;
359 }
360
363 {
364 return true;
365 }
366
369 {
370 return m_primitive_manager.is_trimesh();
371 }
372
375 {
376 return m_box_tree.getNodeCount();
377 }
378
381 {
382 return m_box_tree.isLeafNode(nodeindex);
383 }
384
386 {
387 return m_box_tree.getNodeData(nodeindex);
388 }
389
391 {
392 m_box_tree.getNodeBound(nodeindex, bound);
393 }
394
396 {
397 m_box_tree.setNodeBound(nodeindex, bound);
398 }
399
401 {
402 return m_box_tree.getLeftNodeIndex(nodeindex);
403 }
404
406 {
407 return m_box_tree.getRightNodeIndex(nodeindex);
408 }
409
411 {
412 return m_box_tree.getScapeNodeIndex(nodeindex);
413 }
414
416 {
417 m_primitive_manager.get_primitive_triangle(getNodeData(nodeindex), triangle);
418 }
419};
420
422
425template <typename _GIM_PRIMITIVE_MANAGER_PROTOTYPE>
426class GIM_BOX_TREE_SET : public GIM_BOX_TREE_TEMPLATE_SET<_GIM_PRIMITIVE_MANAGER_PROTOTYPE, GIM_BOX_TREE>
427{
428public:
429};
430
432template <typename BOX_SET_CLASS0, typename BOX_SET_CLASS1>
434{
435public:
455
456public:
458 {
461 }
462
463protected:
465 {
466 if (node0_has_triangle) return;
467 m_boxset0->getNodeTriangle(node0, m_tri0);
468 //transform triangle
473
474 node0_has_triangle = true;
475 }
476
478 {
479 if (node1_has_triangle) return;
480 m_boxset1->getNodeTriangle(node1, m_tri1);
481 //transform triangle
486
487 node1_has_triangle = true;
488 }
489
491 {
492 if (node0 == current_node0) return;
493 m_boxset0->getNodeBound(node0, m_box0);
494 node0_is_leaf = m_boxset0->isLeafNode(node0);
495 node0_has_triangle = false;
497 }
498
500 {
501 if (node1 == current_node1) return;
502 m_boxset1->getNodeBound(node1, m_box1);
503 node1_is_leaf = m_boxset1->isLeafNode(node1);
504 node1_has_triangle = false;
506 }
507
509 {
513 if (!result) return false;
514
516 {
517 //perform primitive vs box collision
519 //do triangle vs box collision
521
524
526
527 if (!result) return false;
528 return true;
529 }
530 else if (t1_is_trimesh && node1_is_leaf)
531 {
532 //perform primitive vs box collision
534 //do triangle vs box collision
536
539
541
542 if (!result) return false;
543 return true;
544 }
545 return true;
546 }
547
548 //stackless collision routine
550 {
553
554 //add the first pair
555 stack_collisions.push_pair(0, 0);
556
557 while (stack_collisions.size())
558 {
559 //retrieve the last pair and pop
560 GUINT node0 = stack_collisions.back().m_index1;
561 GUINT node1 = stack_collisions.back().m_index2;
562 stack_collisions.pop_back();
563 if (node_collision(node0, node1)) // a collision is found
564 {
565 if (node0_is_leaf)
566 {
567 if (node1_is_leaf)
568 {
569 m_collision_pairs->push_pair(m_boxset0->getNodeData(node0), m_boxset1->getNodeData(node1));
570 }
571 else
572 {
573 //collide left
574 stack_collisions.push_pair(node0, m_boxset1->getLeftNodeIndex(node1));
575
576 //collide right
577 stack_collisions.push_pair(node0, m_boxset1->getRightNodeIndex(node1));
578 }
579 }
580 else
581 {
582 if (node1_is_leaf)
583 {
584 //collide left
585 stack_collisions.push_pair(m_boxset0->getLeftNodeIndex(node0), node1);
586 //collide right
587 stack_collisions.push_pair(m_boxset0->getRightNodeIndex(node0), node1);
588 }
589 else
590 {
591 GUINT left0 = m_boxset0->getLeftNodeIndex(node0);
592 GUINT right0 = m_boxset0->getRightNodeIndex(node0);
593 GUINT left1 = m_boxset1->getLeftNodeIndex(node1);
594 GUINT right1 = m_boxset1->getRightNodeIndex(node1);
595 //collide left
596 stack_collisions.push_pair(left0, left1);
597 //collide right
598 stack_collisions.push_pair(left0, right1);
599 //collide left
600 stack_collisions.push_pair(right0, left1);
601 //collide right
602 stack_collisions.push_pair(right0, right1);
603
604 } // else if node1 is not a leaf
605 } // else if node0 is not a leaf
606
607 } // if(node_collision(node0,node1))
608 } //while(stack_collisions.size())
609 }
610
611public:
615 {
619
621
624
626 {
627 t0_is_trimesh = boxset1->getPrimitiveManager().is_trimesh();
628 t1_is_trimesh = boxset2->getPrimitiveManager().is_trimesh();
629 }
630 else
631 {
632 t0_is_trimesh = false;
633 t1_is_trimesh = false;
634 }
635
637 }
638};
639
640#endif // GIM_BOXPRUNING_H_INCLUDED
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
#define SIMD_FORCE_INLINE
Definition btScalar.h:98
Axis aligned box.
bool overlapping_trans_cache(const GIM_AABB &box, const GIM_BOX_BOX_TRANSFORM_CACHE &transcache, bool fulltest)
transcache is the transformation cache from box to this AABB
bool collide_triangle_exact(const btVector3 &p1, const btVector3 &p2, const btVector3 &p3, const btVector4 &triangle_plane)
test for a triangle, with edges
void appy_transform(const btTransform &trans)
Apply a transform to an AABB.
void increment_margin(btScalar margin)
Class for transforming a model1 to the space of model0.
btVector3 transform(const btVector3 &point)
void calc_from_homogenic(const btTransform &trans0, const btTransform &trans1)
Calc the transformation relative 1 to 0. Inverts matrics by transposing.
Class for Box Tree Sets.
Generic Box Tree Template.
_GIM_PRIMITIVE_MANAGER_PROTOTYPE m_primitive_manager
GUINT getNodeData(GUINT nodeindex) const
GUINT getLeftNodeIndex(GUINT nodeindex) const
void setPrimitiveManager(const _GIM_PRIMITIVE_MANAGER_PROTOTYPE &primitive_manager)
const _GIM_PRIMITIVE_MANAGER_PROTOTYPE & getPrimitiveManager() const
_GIM_PRIMITIVE_MANAGER_PROTOTYPE & getPrimitiveManager()
void buildSet()
this rebuild the entire set
bool boxQuery(const GIM_AABB &box, gim_array< GUINT > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
bool isLeafNode(GUINT nodeindex) const
tells if the node is a leaf
bool hasHierarchy() const
tells if this set has hierarcht
GUINT getRightNodeIndex(GUINT nodeindex) const
void update()
node manager prototype functions
_GIM_BOX_TREE_PROTOTYPE m_box_tree
bool isTrimesh() const
tells if this set is a trimesh
GUINT getNodeCount() const
node count
bool rayQuery(const btVector3 &ray_dir, const btVector3 &ray_origin, gim_array< GUINT > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
void getNodeTriangle(GUINT nodeindex, GIM_TRIANGLE &triangle) const
void setNodeBound(GUINT nodeindex, const GIM_AABB &bound)
GIM_AABB getGlobalBox() const
void getNodeBound(GUINT nodeindex, GIM_AABB &bound) const
bool boxQueryTrans(const GIM_AABB &box, const btTransform &transform, gim_array< GUINT > &collided_results) const
returns the indices of the primitives in the m_primitive_manager
GUINT getScapeNodeIndex(GUINT nodeindex) const
Basic Box tree structure.
GUINT getScapeNodeIndex(GUINT nodeindex) const
void getNodeBound(GUINT nodeindex, GIM_AABB &bound) const
void setNodeBound(GUINT nodeindex, const GIM_AABB &bound)
void clearNodes()
GUINT _calc_splitting_axis(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex)
gim_array< GIM_BOX_TREE_NODE > m_node_array
GUINT getLeftNodeIndex(GUINT nodeindex) const
GUINT getRightNodeIndex(GUINT nodeindex) const
GUINT getNodeData(GUINT nodeindex) const
bool isLeafNode(GUINT nodeindex) const
tells if the node is a leaf
GUINT _sort_and_calc_splitting_index(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex, GUINT splitAxis)
GUINT m_num_nodes
GUINT getNodeCount() const
node count
void _build_sub_tree(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex)
void build_tree(gim_array< GIM_AABB_DATA > &primitive_boxes)
prototype functions for box tree management
Prototype Base class for primitive classification.
Definition gim_box_set.h:67
virtual void get_primitive_box(GUINT prim_index, GIM_AABB &primbox)=0
virtual GUINT get_primitive_count()=0
virtual bool is_trimesh()=0
determines if this manager consist on only triangles, which special case will be optimized
virtual void get_primitive_triangle(GUINT prim_index, GIM_TRIANGLE &triangle)=0
GIM_BOX_SET collision methods.
bool node_collision(GUINT node0, GUINT node1)
BOX_SET_CLASS1 * m_boxset1
void find_collision(BOX_SET_CLASS0 *boxset1, const btTransform &trans1, BOX_SET_CLASS1 *boxset2, const btTransform &trans2, gim_pair_set &collision_pairs, bool complete_primitive_tests=true)
void retrieve_node1_triangle(GUINT node1)
void retrieve_node0_triangle(GUINT node0)
GIM_BOX_BOX_TRANSFORM_CACHE trans_cache_1to0
BOX_SET_CLASS0 * m_boxset0
void retrieve_node0_info(GUINT node0)
void retrieve_node1_info(GUINT node1)
btTransform trans_cache_0to1
gim_pair_set * m_collision_pairs
Class for colliding triangles.
btVector3 m_vertices[3]
void get_plane(btVector4 &plane) const
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition btTransform.h:30
btTransform inverse() const
Return the inverse of this transform.
btVector3 can be used to represent 3D points and vectors.
Definition btVector3.h:82
Very simple array container with fast access and simd memory.
Definition gim_array.h:43
void push_back(const GIM_PAIR &obj)
Definition gim_array.h:213
bool reserve(GUINT size)
public operations
Definition gim_array.h:96
void resize(GUINT size, bool call_constructor=true, const T &fillData=T())
Definition gim_array.h:287
void clear()
Definition gim_array.h:110
T * m_data
properties
Definition gim_array.h:47
A pairset array.
Definition gim_box_set.h:44
void push_pair(GUINT index1, GUINT index2)
Definition gim_box_set.h:49
void push_pair_inv(GUINT index1, GUINT index2)
Definition gim_box_set.h:54
#define GUINT
Definition gim_math.h:40
#define G_UINT_INFINITY
A very very high value.
Definition gim_math.h:53
GIM_AABB m_bound
Definition gim_box_set.h:79
Node Structure for trees.
Definition gim_box_set.h:85
GUINT m_escapeIndex
Scape index for traversing.
Definition gim_box_set.h:89
GUINT m_left
Left subtree.
Definition gim_box_set.h:87
GUINT m_right
Right subtree.
Definition gim_box_set.h:88
GUINT m_data
primitive index if apply
Definition gim_box_set.h:90
bool is_leaf_node() const
Overlapping pair.
Definition gim_pair.h:7