Blender  V3.3
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 #include "gim_box_set.h"
32 
34  gim_array<GIM_AABB_DATA>& primitive_boxes, GUINT startIndex, GUINT endIndex)
35 {
36  GUINT i;
37 
38  btVector3 means(btScalar(0.), btScalar(0.), btScalar(0.));
39  btVector3 variance(btScalar(0.), btScalar(0.), btScalar(0.));
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 
64  gim_array<GIM_AABB_DATA>& primitive_boxes, GUINT startIndex,
65  GUINT endIndex, GUINT splitAxis)
66 {
67  GUINT i;
68  GUINT splitIndex = startIndex;
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
88  primitive_boxes.swap(i, splitIndex);
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;
103  bool unbalanced = ((splitIndex <= (startIndex + rangeBalancedIndices)) || (splitIndex >= (endIndex - 1 - rangeBalancedIndices)));
104 
105  if (unbalanced)
106  {
107  splitIndex = startIndex + (numIndices >> 1);
108  }
109 
110  btAssert(!((splitIndex == startIndex) || (splitIndex == (endIndex))));
111 
112  return splitIndex;
113 }
114 
115 void GIM_BOX_TREE::_build_sub_tree(gim_array<GIM_AABB_DATA>& primitive_boxes, GUINT startIndex, GUINT endIndex)
116 {
117  GUINT current_index = m_num_nodes++;
118 
119  btAssert((endIndex - startIndex) > 0);
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 
127  m_node_array[current_index].m_bound = primitive_boxes[startIndex].m_bound;
128  m_node_array[current_index].m_data = primitive_boxes[startIndex].m_data;
129  return;
130  }
131 
132  //configure inner node
133 
134  GUINT splitIndex;
135 
136  //calc this node bounding box
137  m_node_array[current_index].m_bound.invalidate();
138  for (splitIndex = startIndex; splitIndex < endIndex; splitIndex++)
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
146  splitIndex = _calc_splitting_axis(primitive_boxes, startIndex, endIndex);
147 
148  splitIndex = _sort_and_calc_splitting_index(
149  primitive_boxes, startIndex, endIndex, splitIndex);
150 
151  //configure this inner node : the left node index
152  m_node_array[current_index].m_left = m_num_nodes;
153  //build left child tree
154  _build_sub_tree(primitive_boxes, startIndex, splitIndex);
155 
156  //configure this inner node : the right node index
157  m_node_array[current_index].m_right = m_num_nodes;
158 
159  //build right child tree
160  _build_sub_tree(primitive_boxes, splitIndex, endIndex);
161 
162  //configure this inner node : the escape index
163  m_node_array[current_index].m_escapeIndex = m_num_nodes - current_index;
164 }
165 
168  gim_array<GIM_AABB_DATA>& primitive_boxes)
169 {
170  // initialize node count to 0
171  m_num_nodes = 0;
172  // allocate nodes
173  m_node_array.resize(primitive_boxes.size() * 2);
174 
175  _build_sub_tree(primitive_boxes, 0, primitive_boxes.size());
176 }
NSNotificationCenter * center
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:295
int numIndices() const
btVector3
btVector3 can be used to represent 3D points and vectors. It has an un-used w component to suit 16-by...
Definition: btVector3.h:82
GUINT _calc_splitting_axis(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex)
Definition: gim_box_set.cpp:33
gim_array< GIM_BOX_TREE_NODE > m_node_array
Definition: gim_box_set.h:111
GUINT _sort_and_calc_splitting_index(gim_array< GIM_AABB_DATA > &primitive_boxes, GUINT startIndex, GUINT endIndex, GUINT splitAxis)
Definition: gim_box_set.cpp:63
GUINT m_num_nodes
Definition: gim_box_set.h:110
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)
stackless build tree
Very simple array container with fast access and simd memory.
Definition: gim_array.h:43
GUINT size() const
Definition: gim_array.h:143
void swap(GUINT i, GUINT j)
Definition: gim_array.h:208
void resize(GUINT size, bool call_constructor=true, const T &fillData=T())
Definition: gim_array.h:287
T * m_data
Definition: gim_array.h:47
#define GUINT
Definition: gim_math.h:40