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#include "gim_box_set.h"
32
35{
36 GUINT i;
37
40 GUINT numIndices = endIndex - startIndex;
41
42 for (i = startIndex; i < endIndex; i++)
43 {
44 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
45 primitive_boxes[i].m_bound.m_min);
46 means += center;
47 }
48 means *= (btScalar(1.) / (btScalar)numIndices);
49
50 for (i = startIndex; i < endIndex; i++)
51 {
52 btVector3 center = btScalar(0.5) * (primitive_boxes[i].m_bound.m_max +
53 primitive_boxes[i].m_bound.m_min);
54 btVector3 diff2 = center - means;
55 diff2 = diff2 * diff2;
56 variance += diff2;
57 }
58 variance *= (btScalar(1.) / ((btScalar)numIndices - 1));
59
60 return variance.maxAxis();
61}
62
66{
67 GUINT i;
69 GUINT numIndices = endIndex - startIndex;
70
71 // average of centers
72 btScalar splitValue = 0.0f;
73 for (i = startIndex; i < endIndex; i++)
74 {
75 splitValue += 0.5f * (primitive_boxes[i].m_bound.m_max[splitAxis] +
76 primitive_boxes[i].m_bound.m_min[splitAxis]);
77 }
78 splitValue /= (btScalar)numIndices;
79
80 //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
81 for (i = startIndex; i < endIndex; i++)
82 {
83 btScalar center = 0.5f * (primitive_boxes[i].m_bound.m_max[splitAxis] +
84 primitive_boxes[i].m_bound.m_min[splitAxis]);
85 if (center > splitValue)
86 {
87 //swap
89 splitIndex++;
90 }
91 }
92
93 //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
94 //otherwise the tree-building might fail due to stack-overflows in certain cases.
95 //unbalanced1 is unsafe: it can cause stack overflows
96 //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));
97
98 //unbalanced2 should work too: always use center (perfect balanced trees)
99 //bool unbalanced2 = true;
100
101 //this should be safe too:
102 GUINT rangeBalancedIndices = numIndices / 3;
104
105 if (unbalanced)
106 {
107 splitIndex = startIndex + (numIndices >> 1);
108 }
109
111
112 return splitIndex;
113}
114
116{
118
120
121 if ((endIndex - startIndex) == 1) //we got a leaf
122 {
123 m_node_array[current_index].m_left = 0;
124 m_node_array[current_index].m_right = 0;
125 m_node_array[current_index].m_escapeIndex = 0;
126
129 return;
130 }
131
132 //configure inner node
133
135
136 //calc this node bounding box
137 m_node_array[current_index].m_bound.invalidate();
139 {
140 m_node_array[current_index].m_bound.merge(primitive_boxes[splitIndex].m_bound);
141 }
142
143 //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
144
145 //split axis
147
150
151 //configure this inner node : the left node index
153 //build left child tree
155
156 //configure this inner node : the right node index
158
159 //build right child tree
161
162 //configure this inner node : the escape index
164}
165
169{
170 // initialize node count to 0
171 m_num_nodes = 0;
172 // allocate nodes
174
176}
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition btScalar.h:314
#define btAssert(x)
Definition btScalar.h:153
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 _sort_and_calc_splitting_index(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex, GUINT splitAxis)
GUINT m_num_nodes
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: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
Very simple array container with fast access and simd memory.
Definition gim_array.h:43
void resize(GUINT size, bool call_constructor=true, const T &fillData=T())
Definition gim_array.h:287
T * m_data
properties
Definition gim_array.h:47
#define GUINT
Definition gim_math.h:40
GUINT m_data
primitive index if apply
Definition gim_box_set.h:90