| |
| /* |
| ----------------------------------------------------------------------------- |
| This source file is part of GIMPACT Library. |
| |
| For the latest info, see http://gimpact.sourceforge.net/ |
| |
| Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371. |
| email: projectileman@yahoo.com |
| |
| This library is free software; you can redistribute it and/or |
| modify it under the terms of EITHER: |
| (1) The GNU Lesser General Public License as published by the Free |
| Software Foundation; either version 2.1 of the License, or (at |
| your option) any later version. The text of the GNU Lesser |
| General Public License is included with this library in the |
| file GIMPACT-LICENSE-LGPL.TXT. |
| (2) The BSD-style license that is included with this library in |
| the file GIMPACT-LICENSE-BSD.TXT. |
| (3) The zlib/libpng license that is included with this library in |
| the file GIMPACT-LICENSE-ZLIB.TXT. |
| |
| This library is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files |
| GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details. |
| |
| ----------------------------------------------------------------------------- |
| */ |
| |
| |
| #include "BulletCollision/Gimpact/gim_box_set.h" |
| |
| |
| GUINT GIM_BOX_TREE::_calc_splitting_axis( |
| gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex, GUINT endIndex) |
| { |
| GUINT i; |
| |
| btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.)); |
| btVector3 variance(btScalar(0.),btScalar(0.),btScalar(0.)); |
| GUINT numIndices = endIndex-startIndex; |
| |
| for (i=startIndex;i<endIndex;i++) |
| { |
| btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max + |
| primitive_boxes[i].m_bound.m_min); |
| means+=center; |
| } |
| means *= (btScalar(1.)/(btScalar)numIndices); |
| |
| for (i=startIndex;i<endIndex;i++) |
| { |
| btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max + |
| primitive_boxes[i].m_bound.m_min); |
| btVector3 diff2 = center-means; |
| diff2 = diff2 * diff2; |
| variance += diff2; |
| } |
| variance *= (btScalar(1.)/ ((btScalar)numIndices-1) ); |
| |
| return variance.maxAxis(); |
| } |
| |
| |
| GUINT GIM_BOX_TREE::_sort_and_calc_splitting_index( |
| gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex, |
| GUINT endIndex, GUINT splitAxis) |
| { |
| GUINT i; |
| GUINT splitIndex =startIndex; |
| GUINT numIndices = endIndex - startIndex; |
| |
| // average of centers |
| btScalar splitValue = 0.0f; |
| for (i=startIndex;i<endIndex;i++) |
| { |
| splitValue+= 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] + |
| primitive_boxes[i].m_bound.m_min[splitAxis]); |
| } |
| splitValue /= (btScalar)numIndices; |
| |
| //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'. |
| for (i=startIndex;i<endIndex;i++) |
| { |
| btScalar center = 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] + |
| primitive_boxes[i].m_bound.m_min[splitAxis]); |
| if (center > splitValue) |
| { |
| //swap |
| primitive_boxes.swap(i,splitIndex); |
| splitIndex++; |
| } |
| } |
| |
| //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex |
| //otherwise the tree-building might fail due to stack-overflows in certain cases. |
| //unbalanced1 is unsafe: it can cause stack overflows |
| //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1))); |
| |
| //unbalanced2 should work too: always use center (perfect balanced trees) |
| //bool unbalanced2 = true; |
| |
| //this should be safe too: |
| GUINT rangeBalancedIndices = numIndices/3; |
| bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices))); |
| |
| if (unbalanced) |
| { |
| splitIndex = startIndex+ (numIndices>>1); |
| } |
| |
| btAssert(!((splitIndex==startIndex) || (splitIndex == (endIndex)))); |
| |
| return splitIndex; |
| } |
| |
| |
| void GIM_BOX_TREE::_build_sub_tree(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex, GUINT endIndex) |
| { |
| GUINT current_index = m_num_nodes++; |
| |
| btAssert((endIndex-startIndex)>0); |
| |
| if((endIndex-startIndex) == 1) //we got a leaf |
| { |
| m_node_array[current_index].m_left = 0; |
| m_node_array[current_index].m_right = 0; |
| m_node_array[current_index].m_escapeIndex = 0; |
| |
| m_node_array[current_index].m_bound = primitive_boxes[startIndex].m_bound; |
| m_node_array[current_index].m_data = primitive_boxes[startIndex].m_data; |
| return; |
| } |
| |
| //configure inner node |
| |
| GUINT splitIndex; |
| |
| //calc this node bounding box |
| m_node_array[current_index].m_bound.invalidate(); |
| for (splitIndex=startIndex;splitIndex<endIndex;splitIndex++) |
| { |
| m_node_array[current_index].m_bound.merge(primitive_boxes[splitIndex].m_bound); |
| } |
| |
| //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'. |
| |
| //split axis |
| splitIndex = _calc_splitting_axis(primitive_boxes,startIndex,endIndex); |
| |
| splitIndex = _sort_and_calc_splitting_index( |
| primitive_boxes,startIndex,endIndex,splitIndex); |
| |
| //configure this inner node : the left node index |
| m_node_array[current_index].m_left = m_num_nodes; |
| //build left child tree |
| _build_sub_tree(primitive_boxes, startIndex, splitIndex ); |
| |
| //configure this inner node : the right node index |
| m_node_array[current_index].m_right = m_num_nodes; |
| |
| //build right child tree |
| _build_sub_tree(primitive_boxes, splitIndex ,endIndex); |
| |
| //configure this inner node : the escape index |
| m_node_array[current_index].m_escapeIndex = m_num_nodes - current_index; |
| } |
| |
| //! stackless build tree |
| void GIM_BOX_TREE::build_tree( |
| gim_array<GIM_AABB_DATA> & primitive_boxes) |
| { |
| // initialize node count to 0 |
| m_num_nodes = 0; |
| // allocate nodes |
| m_node_array.resize(primitive_boxes.size()*2); |
| |
| _build_sub_tree(primitive_boxes, 0, primitive_boxes.size()); |
| } |
| |
| |