Bullet Collision Detection & Physics Library
gim_box_set.cpp
Go to the documentation of this file.
1
2/*
3-----------------------------------------------------------------------------
4This source file is part of GIMPACT Library.
5
6For the latest info, see http://gimpact.sourceforge.net/
7
8Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
9email: 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
119void 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
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
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:292
#define btAssert(x)
Definition: btScalar.h:131
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 _sort_and_calc_splitting_index(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex, GUINT splitAxis)
Definition: gim_box_set.cpp:66
GUINT m_num_nodes
Definition: gim_box_set.h:136
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
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:84
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:487
Very simple array container with fast access and simd memory.
Definition: gim_array.h:44
GUINT size() const
Definition: gim_array.h:144
void swap(GUINT i, GUINT j)
Definition: gim_array.h:209
T * m_data
properties
Definition: gim_array.h:48
#define GUINT
Definition: gim_math.h:42