dali-physics/third-party/bullet3/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 #include "gim_box_set.h"
  32
  33 GUINT GIM_BOX_TREE::_calc_splitting_axis(
  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
  63 GUINT GIM_BOX_TREE::_sort_and_calc_splitting_index(
  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
 166 //! stackless build tree
 167 void GIM_BOX_TREE::build_tree(
 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 }