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 (at) 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 183
