1 #ifndef GIM_QUANTIZED_SET_H_INCLUDED 2 #define GIM_QUANTIZED_SET_H_INCLUDED 3 4 /*! \file btGImpactQuantizedBvh.h 5 \author Francisco Leon Najera 6 */ 7 /* 8 This source file is part of GIMPACT Library. 9 10 For the latest info, see http://gimpact.sourceforge.net/ 11 12 Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371. 13 email: projectileman (at) yahoo.com 14 15 16 This software is provided 'as-is', without any express or implied warranty. 17 In no event will the authors be held liable for any damages arising from the use of this software. 18 Permission is granted to anyone to use this software for any purpose, 19 including commercial applications, and to alter it and redistribute it freely, 20 subject to the following restrictions: 21 22 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 23 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 24 3. This notice may not be removed or altered from any source distribution. 25 */ 26 27 #include "btGImpactBvh.h" 28 #include "btQuantization.h" 29 30 31 32 33 34 ///btQuantizedBvhNode is a compressed aabb node, 16 bytes. 35 ///Node can be used for leafnode or internal node. Leafnodes can point to 32-bit triangle index (non-negative range). 36 ATTRIBUTE_ALIGNED16 (struct) BT_QUANTIZED_BVH_NODE 37 { 38 //12 bytes 39 unsigned short int m_quantizedAabbMin[3]; 40 unsigned short int m_quantizedAabbMax[3]; 41 //4 bytes 42 int m_escapeIndexOrDataIndex; 43 44 BT_QUANTIZED_BVH_NODE() 45 { 46 m_escapeIndexOrDataIndex = 0; 47 } 48 49 SIMD_FORCE_INLINE bool isLeafNode() const 50 { 51 //skipindex is negative (internal node), triangleindex >=0 (leafnode) 52 return (m_escapeIndexOrDataIndex>=0); 53 } 54 55 SIMD_FORCE_INLINE int getEscapeIndex() const 56 { 57 //btAssert(m_escapeIndexOrDataIndex < 0); 58 return -m_escapeIndexOrDataIndex; 59 } 60 61 SIMD_FORCE_INLINE void setEscapeIndex(int index) 62 { 63 m_escapeIndexOrDataIndex = -index; 64 } 65 66 SIMD_FORCE_INLINE int getDataIndex() const 67 { 68 //btAssert(m_escapeIndexOrDataIndex >= 0); 69 70 return m_escapeIndexOrDataIndex; 71 } 72 73 SIMD_FORCE_INLINE void setDataIndex(int index) 74 { 75 m_escapeIndexOrDataIndex = index; 76 } 77 78 SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp( 79 unsigned short * quantizedMin,unsigned short * quantizedMax) const 80 { 81 if(m_quantizedAabbMin[0] > quantizedMax[0] || 82 m_quantizedAabbMax[0] < quantizedMin[0] || 83 m_quantizedAabbMin[1] > quantizedMax[1] || 84 m_quantizedAabbMax[1] < quantizedMin[1] || 85 m_quantizedAabbMin[2] > quantizedMax[2] || 86 m_quantizedAabbMax[2] < quantizedMin[2]) 87 { 88 return false; 89 } 90 return true; 91 } 92 93 }; 94 95 96 97 class GIM_QUANTIZED_BVH_NODE_ARRAY:public btAlignedObjectArray<BT_QUANTIZED_BVH_NODE> 98 { 99 }; 100 101 102 103 104 //! Basic Box tree structure 105 class btQuantizedBvhTree 106 { 107 protected: 108 int m_num_nodes; 109 GIM_QUANTIZED_BVH_NODE_ARRAY m_node_array; 110 btAABB m_global_bound; 111 btVector3 m_bvhQuantization; 112 protected: 113 void calc_quantization(GIM_BVH_DATA_ARRAY & primitive_boxes, btScalar boundMargin = btScalar(1.0) ); 114 115 int _sort_and_calc_splitting_index( 116 GIM_BVH_DATA_ARRAY & primitive_boxes, 117 int startIndex, int endIndex, int splitAxis); 118 119 int _calc_splitting_axis(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex, int endIndex); 120 121 void _build_sub_tree(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex, int endIndex); 122 public: 123 btQuantizedBvhTree() 124 { 125 m_num_nodes = 0; 126 } 127 128 //! prototype functions for box tree management 129 //!@{ 130 void build_tree(GIM_BVH_DATA_ARRAY & primitive_boxes); 131 132 SIMD_FORCE_INLINE void quantizePoint( 133 unsigned short * quantizedpoint, const btVector3 & point) const 134 { 135 bt_quantize_clamp(quantizedpoint,point,m_global_bound.m_min,m_global_bound.m_max,m_bvhQuantization); 136 } 137 138 139 SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp( 140 int node_index, 141 unsigned short * quantizedMin,unsigned short * quantizedMax) const 142 { 143 return m_node_array[node_index].testQuantizedBoxOverlapp(quantizedMin,quantizedMax); 144 } 145 146 SIMD_FORCE_INLINE void clearNodes() 147 { 148 m_node_array.clear(); 149 m_num_nodes = 0; 150 } 151 152 //! node count 153 SIMD_FORCE_INLINE int getNodeCount() const 154 { 155 return m_num_nodes; 156 } 157 158 //! tells if the node is a leaf 159 SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const 160 { 161 return m_node_array[nodeindex].isLeafNode(); 162 } 163 164 SIMD_FORCE_INLINE int getNodeData(int nodeindex) const 165 { 166 return m_node_array[nodeindex].getDataIndex(); 167 } 168 169 SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const 170 { 171 bound.m_min = bt_unquantize( 172 m_node_array[nodeindex].m_quantizedAabbMin, 173 m_global_bound.m_min,m_bvhQuantization); 174 175 bound.m_max = bt_unquantize( 176 m_node_array[nodeindex].m_quantizedAabbMax, 177 m_global_bound.m_min,m_bvhQuantization); 178 } 179 180 SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound) 181 { 182 bt_quantize_clamp( m_node_array[nodeindex].m_quantizedAabbMin, 183 bound.m_min, 184 m_global_bound.m_min, 185 m_global_bound.m_max, 186 m_bvhQuantization); 187 188 bt_quantize_clamp( m_node_array[nodeindex].m_quantizedAabbMax, 189 bound.m_max, 190 m_global_bound.m_min, 191 m_global_bound.m_max, 192 m_bvhQuantization); 193 } 194 195 SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const 196 { 197 return nodeindex+1; 198 } 199 200 SIMD_FORCE_INLINE int getRightNode(int nodeindex) const 201 { 202 if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2; 203 return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex(); 204 } 205 206 SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const 207 { 208 return m_node_array[nodeindex].getEscapeIndex(); 209 } 210 211 SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const 212 { 213 return &m_node_array[index]; 214 } 215 216 //!@} 217 }; 218 219 220 221 //! Structure for containing Boxes 222 /*! 223 This class offers an structure for managing a box tree of primitives. 224 Requires a Primitive prototype (like btPrimitiveManagerBase ) 225 */ 226 class btGImpactQuantizedBvh 227 { 228 protected: 229 btQuantizedBvhTree m_box_tree; 230 btPrimitiveManagerBase * m_primitive_manager; 231 232 protected: 233 //stackless refit 234 void refit(); 235 public: 236 237 //! this constructor doesn't build the tree. you must call buildSet 238 btGImpactQuantizedBvh() 239 { 240 m_primitive_manager = NULL; 241 } 242 243 //! this constructor doesn't build the tree. you must call buildSet 244 btGImpactQuantizedBvh(btPrimitiveManagerBase * primitive_manager) 245 { 246 m_primitive_manager = primitive_manager; 247 } 248 249 SIMD_FORCE_INLINE btAABB getGlobalBox() const 250 { 251 btAABB totalbox; 252 getNodeBound(0, totalbox); 253 return totalbox; 254 } 255 256 SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager) 257 { 258 m_primitive_manager = primitive_manager; 259 } 260 261 SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const 262 { 263 return m_primitive_manager; 264 } 265 266 267 //! node manager prototype functions 268 ///@{ 269 270 //! this attemps to refit the box set. 271 SIMD_FORCE_INLINE void update() 272 { 273 refit(); 274 } 275 276 //! this rebuild the entire set 277 void buildSet(); 278 279 //! returns the indices of the primitives in the m_primitive_manager 280 bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const; 281 282 //! returns the indices of the primitives in the m_primitive_manager 283 SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box, 284 const btTransform & transform, btAlignedObjectArray<int> & collided_results) const 285 { 286 btAABB transbox=box; 287 transbox.appy_transform(transform); 288 return boxQuery(transbox,collided_results); 289 } 290 291 //! returns the indices of the primitives in the m_primitive_manager 292 bool rayQuery( 293 const btVector3 & ray_dir,const btVector3 & ray_origin , 294 btAlignedObjectArray<int> & collided_results) const; 295 296 //! tells if this set has hierarcht 297 SIMD_FORCE_INLINE bool hasHierarchy() const 298 { 299 return true; 300 } 301 302 //! tells if this set is a trimesh 303 SIMD_FORCE_INLINE bool isTrimesh() const 304 { 305 return m_primitive_manager->is_trimesh(); 306 } 307 308 //! node count 309 SIMD_FORCE_INLINE int getNodeCount() const 310 { 311 return m_box_tree.getNodeCount(); 312 } 313 314 //! tells if the node is a leaf 315 SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const 316 { 317 return m_box_tree.isLeafNode(nodeindex); 318 } 319 320 SIMD_FORCE_INLINE int getNodeData(int nodeindex) const 321 { 322 return m_box_tree.getNodeData(nodeindex); 323 } 324 325 SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const 326 { 327 m_box_tree.getNodeBound(nodeindex, bound); 328 } 329 330 SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound) 331 { 332 m_box_tree.setNodeBound(nodeindex, bound); 333 } 334 335 336 SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const 337 { 338 return m_box_tree.getLeftNode(nodeindex); 339 } 340 341 SIMD_FORCE_INLINE int getRightNode(int nodeindex) const 342 { 343 return m_box_tree.getRightNode(nodeindex); 344 } 345 346 SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const 347 { 348 return m_box_tree.getEscapeNodeIndex(nodeindex); 349 } 350 351 SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const 352 { 353 m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle); 354 } 355 356 357 SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const 358 { 359 return m_box_tree.get_node_pointer(index); 360 } 361 362 #ifdef TRI_COLLISION_PROFILING 363 static float getAverageTreeCollisionTime(); 364 #endif //TRI_COLLISION_PROFILING 365 366 static void find_collision(const btGImpactQuantizedBvh * boxset1, const btTransform & trans1, 367 const btGImpactQuantizedBvh * boxset2, const btTransform & trans2, 368 btPairSet & collision_pairs); 369 }; 370 371 372 #endif // GIM_BOXPRUNING_H_INCLUDED 373
