src/BulletCollision/Gimpact/gim_box_set.cpp

   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
  35 GUINT GIM_BOX_TREE::_calc_splitting_axis(
  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
  66 GUINT GIM_BOX_TREE::_sort_and_calc_splitting_index(
  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
 170 //! stackless build tree
 171 void GIM_BOX_TREE::build_tree(
 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