Bullet Collision Detection & Physics Library
gim_box_set.cpp
Go to the documentation of this file.
1 
2 /*
3 -----------------------------------------------------------------------------
4 This source file is part of GIMPACT Library.
5 
6 For the latest info, see http://gimpact.sourceforge.net/
7 
8 Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
9 email: projectileman@yahoo.com
10 
11  This library is free software; you can redistribute it and/or
12  modify it under the terms of EITHER:
13  (1) The GNU Lesser General Public License as published by the Free
14  Software Foundation; either version 2.1 of the License, or (at
15  your option) any later version. The text of the GNU Lesser
16  General Public License is included with this library in the
17  file GIMPACT-LICENSE-LGPL.TXT.
18  (2) The BSD-style license that is included with this library in
19  the file GIMPACT-LICENSE-BSD.TXT.
20  (3) The zlib/libpng license that is included with this library in
21  the file GIMPACT-LICENSE-ZLIB.TXT.
22 
23  This library is distributed in the hope that it will be useful,
24  but WITHOUT ANY WARRANTY; without even the implied warranty of
25  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
26  GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
27 
28 -----------------------------------------------------------------------------
29 */
30 
31 
32 #include "gim_box_set.h"
33 
34 
36  gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex, GUINT endIndex)
37 {
38  GUINT i;
39 
40  btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.));
41  btVector3 variance(btScalar(0.),btScalar(0.),btScalar(0.));
42  GUINT numIndices = endIndex-startIndex;
43 
44  for (i=startIndex;i<endIndex;i++)
45  {
46  btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
47  primitive_boxes[i].m_bound.m_min);
48  means+=center;
49  }
50  means *= (btScalar(1.)/(btScalar)numIndices);
51 
52  for (i=startIndex;i<endIndex;i++)
53  {
54  btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
55  primitive_boxes[i].m_bound.m_min);
56  btVector3 diff2 = center-means;
57  diff2 = diff2 * diff2;
58  variance += diff2;
59  }
60  variance *= (btScalar(1.)/ ((btScalar)numIndices-1) );
61 
62  return variance.maxAxis();
63 }
64 
65 
67  gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,
68  GUINT endIndex, GUINT splitAxis)
69 {
70  GUINT i;
71  GUINT splitIndex =startIndex;
72  GUINT numIndices = endIndex - startIndex;
73 
74  // average of centers
75  btScalar splitValue = 0.0f;
76  for (i=startIndex;i<endIndex;i++)
77  {
78  splitValue+= 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
79  primitive_boxes[i].m_bound.m_min[splitAxis]);
80  }
81  splitValue /= (btScalar)numIndices;
82 
83  //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
84  for (i=startIndex;i<endIndex;i++)
85  {
86  btScalar center = 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
87  primitive_boxes[i].m_bound.m_min[splitAxis]);
88  if (center > splitValue)
89  {
90  //swap
91  primitive_boxes.swap(i,splitIndex);
92  splitIndex++;
93  }
94  }
95 
96  //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
97  //otherwise the tree-building might fail due to stack-overflows in certain cases.
98  //unbalanced1 is unsafe: it can cause stack overflows
99  //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));
100 
101  //unbalanced2 should work too: always use center (perfect balanced trees)
102  //bool unbalanced2 = true;
103 
104  //this should be safe too:
105  GUINT rangeBalancedIndices = numIndices/3;
106  bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices)));
107 
108  if (unbalanced)
109  {
110  splitIndex = startIndex+ (numIndices>>1);
111  }
112 
113  btAssert(!((splitIndex==startIndex) || (splitIndex == (endIndex))));
114 
115  return splitIndex;
116 }
117 
118 
119 void GIM_BOX_TREE::_build_sub_tree(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex, GUINT endIndex)
120 {
121  GUINT current_index = m_num_nodes++;
122 
123  btAssert((endIndex-startIndex)>0);
124 
125  if((endIndex-startIndex) == 1) //we got a leaf
126  {
127  m_node_array[current_index].m_left = 0;
128  m_node_array[current_index].m_right = 0;
129  m_node_array[current_index].m_escapeIndex = 0;
130 
131  m_node_array[current_index].m_bound = primitive_boxes[startIndex].m_bound;
132  m_node_array[current_index].m_data = primitive_boxes[startIndex].m_data;
133  return;
134  }
135 
136  //configure inner node
137 
138  GUINT splitIndex;
139 
140  //calc this node bounding box
141  m_node_array[current_index].m_bound.invalidate();
142  for (splitIndex=startIndex;splitIndex<endIndex;splitIndex++)
143  {
144  m_node_array[current_index].m_bound.merge(primitive_boxes[splitIndex].m_bound);
145  }
146 
147  //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
148 
149  //split axis
150  splitIndex = _calc_splitting_axis(primitive_boxes,startIndex,endIndex);
151 
152  splitIndex = _sort_and_calc_splitting_index(
153  primitive_boxes,startIndex,endIndex,splitIndex);
154 
155  //configure this inner node : the left node index
156  m_node_array[current_index].m_left = m_num_nodes;
157  //build left child tree
158  _build_sub_tree(primitive_boxes, startIndex, splitIndex );
159 
160  //configure this inner node : the right node index
161  m_node_array[current_index].m_right = m_num_nodes;
162 
163  //build right child tree
164  _build_sub_tree(primitive_boxes, splitIndex ,endIndex);
165 
166  //configure this inner node : the escape index
167  m_node_array[current_index].m_escapeIndex = m_num_nodes - current_index;
168 }
169 
172  gim_array<GIM_AABB_DATA> & primitive_boxes)
173 {
174  // initialize node count to 0
175  m_num_nodes = 0;
176  // allocate nodes
177  m_node_array.resize(primitive_boxes.size()*2);
178 
179  _build_sub_tree(primitive_boxes, 0, primitive_boxes.size());
180 }
181 
182 
void build_tree(gim_array< GIM_AABB_DATA > &primitive_boxes)
prototype functions for box tree management
#define btAssert(x)
Definition: btScalar.h:101
void resize(GUINT size, bool call_constructor=true, const T &fillData=T())
Definition: gim_array.h:288
GUINT m_num_nodes
Definition: gim_box_set.h:136
T * m_data
properties
Definition: gim_array.h:48
Very simple array container with fast access and simd memory.
Definition: gim_array.h:43
void swap(GUINT i, GUINT j)
Definition: gim_array.h:209
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:83
GUINT _sort_and_calc_splitting_index(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex, GUINT splitAxis)
Definition: gim_box_set.cpp:66
#define GUINT
Definition: gim_math.h:42
GUINT _calc_splitting_axis(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex)
Definition: gim_box_set.cpp:35
gim_array< GIM_BOX_TREE_NODE > m_node_array
Definition: gim_box_set.h:137
GUINT size() const
Definition: gim_array.h:144
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:266
void _build_sub_tree(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex)
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:475