[216] | 1 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 2 | /* |
---|
| 3 | * OPCODE - Optimized Collision Detection |
---|
| 4 | * Copyright (C) 2001 Pierre Terdiman |
---|
| 5 | * Homepage: http://www.codercorner.com/Opcode.htm |
---|
| 6 | */ |
---|
| 7 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 8 | |
---|
| 9 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 10 | /** |
---|
| 11 | * Contains code for a versatile AABB tree. |
---|
| 12 | * \file OPC_AABBTree.cpp |
---|
| 13 | * \author Pierre Terdiman |
---|
| 14 | * \date March, 20, 2001 |
---|
| 15 | */ |
---|
| 16 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 17 | |
---|
| 18 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 19 | /** |
---|
| 20 | * Contains a generic AABB tree node. |
---|
| 21 | * |
---|
| 22 | * \class AABBTreeNode |
---|
| 23 | * \author Pierre Terdiman |
---|
| 24 | * \version 1.3 |
---|
| 25 | * \date March, 20, 2001 |
---|
| 26 | */ |
---|
| 27 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 28 | |
---|
| 29 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 30 | /** |
---|
| 31 | * Contains a generic AABB tree. |
---|
| 32 | * This is a vanilla AABB tree, without any particular optimization. It contains anonymous references to |
---|
| 33 | * user-provided primitives, which can theoretically be anything - triangles, boxes, etc. Each primitive |
---|
| 34 | * is surrounded by an AABB, regardless of the primitive's nature. When the primitive is a triangle, the |
---|
| 35 | * resulting tree can be converted into an optimized tree. If the primitive is a box, the resulting tree |
---|
| 36 | * can be used for culling - VFC or occlusion -, assuming you cull on a mesh-by-mesh basis (modern way). |
---|
| 37 | * |
---|
| 38 | * \class AABBTree |
---|
| 39 | * \author Pierre Terdiman |
---|
| 40 | * \version 1.3 |
---|
| 41 | * \date March, 20, 2001 |
---|
| 42 | */ |
---|
| 43 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 44 | |
---|
| 45 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 46 | // Precompiled Header |
---|
| 47 | #include "Stdafx.h" |
---|
| 48 | |
---|
| 49 | using namespace Opcode; |
---|
| 50 | |
---|
| 51 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 52 | /** |
---|
| 53 | * Constructor. |
---|
| 54 | */ |
---|
| 55 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 56 | AABBTreeNode::AABBTreeNode() : |
---|
| 57 | mPos (null), |
---|
| 58 | #ifndef OPC_NO_NEG_VANILLA_TREE |
---|
| 59 | mNeg (null), |
---|
| 60 | #endif |
---|
| 61 | mNbPrimitives (0), |
---|
| 62 | mNodePrimitives (null) |
---|
| 63 | { |
---|
| 64 | #ifdef OPC_USE_TREE_COHERENCE |
---|
| 65 | mBitmask = 0; |
---|
| 66 | #endif |
---|
| 67 | } |
---|
| 68 | |
---|
| 69 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 70 | /** |
---|
| 71 | * Destructor. |
---|
| 72 | */ |
---|
| 73 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 74 | AABBTreeNode::~AABBTreeNode() |
---|
| 75 | { |
---|
| 76 | // Opcode 1.3: |
---|
| 77 | const AABBTreeNode* Pos = GetPos(); |
---|
| 78 | const AABBTreeNode* Neg = GetNeg(); |
---|
| 79 | #ifndef OPC_NO_NEG_VANILLA_TREE |
---|
| 80 | if(!(mPos&1)) DELETESINGLE(Pos); |
---|
| 81 | if(!(mNeg&1)) DELETESINGLE(Neg); |
---|
| 82 | #else |
---|
| 83 | if(!(mPos&1)) DELETEARRAY(Pos); |
---|
| 84 | #endif |
---|
| 85 | mNodePrimitives = null; // This was just a shortcut to the global list => no release |
---|
| 86 | mNbPrimitives = 0; |
---|
| 87 | } |
---|
| 88 | |
---|
| 89 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 90 | /** |
---|
| 91 | * Splits the node along a given axis. |
---|
| 92 | * The list of indices is reorganized according to the split values. |
---|
| 93 | * \param axis [in] splitting axis index |
---|
| 94 | * \param builder [in] the tree builder |
---|
| 95 | * \return the number of primitives assigned to the first child |
---|
| 96 | * \warning this method reorganizes the internal list of primitives |
---|
| 97 | */ |
---|
| 98 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 99 | udword AABBTreeNode::Split(udword axis, AABBTreeBuilder* builder) |
---|
| 100 | { |
---|
| 101 | // Get node split value |
---|
| 102 | float SplitValue = builder->GetSplittingValue(mNodePrimitives, mNbPrimitives, mBV, axis); |
---|
| 103 | |
---|
| 104 | udword NbPos = 0; |
---|
| 105 | // Loop through all node-related primitives. Their indices range from mNodePrimitives[0] to mNodePrimitives[mNbPrimitives-1]. |
---|
| 106 | // Those indices map the global list in the tree builder. |
---|
| 107 | for(udword i=0;i<mNbPrimitives;i++) |
---|
| 108 | { |
---|
| 109 | // Get index in global list |
---|
| 110 | udword Index = mNodePrimitives[i]; |
---|
| 111 | |
---|
| 112 | // Test against the splitting value. The primitive value is tested against the enclosing-box center. |
---|
| 113 | // [We only need an approximate partition of the enclosing box here.] |
---|
| 114 | float PrimitiveValue = builder->GetSplittingValue(Index, axis); |
---|
| 115 | |
---|
| 116 | // Reorganize the list of indices in this order: positive - negative. |
---|
| 117 | if(PrimitiveValue > SplitValue) |
---|
| 118 | { |
---|
| 119 | // Swap entries |
---|
| 120 | udword Tmp = mNodePrimitives[i]; |
---|
| 121 | mNodePrimitives[i] = mNodePrimitives[NbPos]; |
---|
| 122 | mNodePrimitives[NbPos] = Tmp; |
---|
| 123 | // Count primitives assigned to positive space |
---|
| 124 | NbPos++; |
---|
| 125 | } |
---|
| 126 | } |
---|
| 127 | return NbPos; |
---|
| 128 | } |
---|
| 129 | |
---|
| 130 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 131 | /** |
---|
| 132 | * Subdivides the node. |
---|
| 133 | * |
---|
| 134 | * N |
---|
| 135 | * / \ |
---|
| 136 | * / \ |
---|
| 137 | * N/2 N/2 |
---|
| 138 | * / \ / \ |
---|
| 139 | * N/4 N/4 N/4 N/4 |
---|
| 140 | * (etc) |
---|
| 141 | * |
---|
| 142 | * A well-balanced tree should have a O(log n) depth. |
---|
| 143 | * A degenerate tree would have a O(n) depth. |
---|
| 144 | * Note a perfectly-balanced tree is not well-suited to collision detection anyway. |
---|
| 145 | * |
---|
| 146 | * \param builder [in] the tree builder |
---|
| 147 | * \return true if success |
---|
| 148 | */ |
---|
| 149 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 150 | bool AABBTreeNode::Subdivide(AABBTreeBuilder* builder) |
---|
| 151 | { |
---|
| 152 | // Checkings |
---|
| 153 | if(!builder) return false; |
---|
| 154 | |
---|
| 155 | // Stop subdividing if we reach a leaf node. This is always performed here, |
---|
| 156 | // else we could end in trouble if user overrides this. |
---|
| 157 | if(mNbPrimitives==1) return true; |
---|
| 158 | |
---|
| 159 | // Let the user validate the subdivision |
---|
| 160 | if(!builder->ValidateSubdivision(mNodePrimitives, mNbPrimitives, mBV)) return true; |
---|
| 161 | |
---|
| 162 | bool ValidSplit = true; // Optimism... |
---|
| 163 | udword NbPos; |
---|
| 164 | if(builder->mSettings.mRules & SPLIT_LARGEST_AXIS) |
---|
| 165 | { |
---|
| 166 | // Find the largest axis to split along |
---|
| 167 | Point Extents; mBV.GetExtents(Extents); // Box extents |
---|
| 168 | udword Axis = Extents.LargestAxis(); // Index of largest axis |
---|
| 169 | |
---|
| 170 | // Split along the axis |
---|
| 171 | NbPos = Split(Axis, builder); |
---|
| 172 | |
---|
| 173 | // Check split validity |
---|
| 174 | if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; |
---|
| 175 | } |
---|
| 176 | else if(builder->mSettings.mRules & SPLIT_SPLATTER_POINTS) |
---|
| 177 | { |
---|
| 178 | // Compute the means |
---|
| 179 | Point Means(0.0f, 0.0f, 0.0f); |
---|
| 180 | for(udword i=0;i<mNbPrimitives;i++) |
---|
| 181 | { |
---|
| 182 | udword Index = mNodePrimitives[i]; |
---|
| 183 | Means.x+=builder->GetSplittingValue(Index, 0); |
---|
| 184 | Means.y+=builder->GetSplittingValue(Index, 1); |
---|
| 185 | Means.z+=builder->GetSplittingValue(Index, 2); |
---|
| 186 | } |
---|
| 187 | Means/=float(mNbPrimitives); |
---|
| 188 | |
---|
| 189 | // Compute variances |
---|
| 190 | Point Vars(0.0f, 0.0f, 0.0f); |
---|
| 191 | for(udword i=0;i<mNbPrimitives;i++) |
---|
| 192 | { |
---|
| 193 | udword Index = mNodePrimitives[i]; |
---|
| 194 | float Cx = builder->GetSplittingValue(Index, 0); |
---|
| 195 | float Cy = builder->GetSplittingValue(Index, 1); |
---|
| 196 | float Cz = builder->GetSplittingValue(Index, 2); |
---|
| 197 | Vars.x += (Cx - Means.x)*(Cx - Means.x); |
---|
| 198 | Vars.y += (Cy - Means.y)*(Cy - Means.y); |
---|
| 199 | Vars.z += (Cz - Means.z)*(Cz - Means.z); |
---|
| 200 | } |
---|
| 201 | Vars/=float(mNbPrimitives-1); |
---|
| 202 | |
---|
| 203 | // Choose axis with greatest variance |
---|
| 204 | udword Axis = Vars.LargestAxis(); |
---|
| 205 | |
---|
| 206 | // Split along the axis |
---|
| 207 | NbPos = Split(Axis, builder); |
---|
| 208 | |
---|
| 209 | // Check split validity |
---|
| 210 | if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; |
---|
| 211 | } |
---|
| 212 | else if(builder->mSettings.mRules & SPLIT_BALANCED) |
---|
| 213 | { |
---|
| 214 | // Test 3 axis, take the best |
---|
| 215 | float Results[3]; |
---|
| 216 | NbPos = Split(0, builder); Results[0] = float(NbPos)/float(mNbPrimitives); |
---|
| 217 | NbPos = Split(1, builder); Results[1] = float(NbPos)/float(mNbPrimitives); |
---|
| 218 | NbPos = Split(2, builder); Results[2] = float(NbPos)/float(mNbPrimitives); |
---|
| 219 | Results[0]-=0.5f; Results[0]*=Results[0]; |
---|
| 220 | Results[1]-=0.5f; Results[1]*=Results[1]; |
---|
| 221 | Results[2]-=0.5f; Results[2]*=Results[2]; |
---|
| 222 | udword Min=0; |
---|
| 223 | if(Results[1]<Results[Min]) Min = 1; |
---|
| 224 | if(Results[2]<Results[Min]) Min = 2; |
---|
| 225 | |
---|
| 226 | // Split along the axis |
---|
| 227 | NbPos = Split(Min, builder); |
---|
| 228 | |
---|
| 229 | // Check split validity |
---|
| 230 | if(!NbPos || NbPos==mNbPrimitives) ValidSplit = false; |
---|
| 231 | } |
---|
| 232 | else if(builder->mSettings.mRules & SPLIT_BEST_AXIS) |
---|
| 233 | { |
---|
| 234 | // Test largest, then middle, then smallest axis... |
---|
| 235 | |
---|
| 236 | // Sort axis |
---|
| 237 | Point Extents; mBV.GetExtents(Extents); // Box extents |
---|
| 238 | udword SortedAxis[] = { 0, 1, 2 }; |
---|
| 239 | float* Keys = (float*)&Extents.x; |
---|
| 240 | for(udword j=0;j<3;j++) |
---|
| 241 | { |
---|
| 242 | for(udword i=0;i<2;i++) |
---|
| 243 | { |
---|
| 244 | if(Keys[SortedAxis[i]]<Keys[SortedAxis[i+1]]) |
---|
| 245 | { |
---|
| 246 | udword Tmp = SortedAxis[i]; |
---|
| 247 | SortedAxis[i] = SortedAxis[i+1]; |
---|
| 248 | SortedAxis[i+1] = Tmp; |
---|
| 249 | } |
---|
| 250 | } |
---|
| 251 | } |
---|
| 252 | |
---|
| 253 | // Find the largest axis to split along |
---|
| 254 | udword CurAxis = 0; |
---|
| 255 | ValidSplit = false; |
---|
| 256 | while(!ValidSplit && CurAxis!=3) |
---|
| 257 | { |
---|
| 258 | NbPos = Split(SortedAxis[CurAxis], builder); |
---|
| 259 | // Check the subdivision has been successful |
---|
| 260 | if(!NbPos || NbPos==mNbPrimitives) CurAxis++; |
---|
| 261 | else ValidSplit = true; |
---|
| 262 | } |
---|
| 263 | } |
---|
| 264 | else if(builder->mSettings.mRules & SPLIT_FIFTY) |
---|
| 265 | { |
---|
| 266 | // Don't even bother splitting (mainly a performance test) |
---|
| 267 | NbPos = mNbPrimitives>>1; |
---|
| 268 | } |
---|
| 269 | else return false; // Unknown splitting rules |
---|
| 270 | |
---|
| 271 | // Check the subdivision has been successful |
---|
| 272 | if(!ValidSplit) |
---|
| 273 | { |
---|
| 274 | // Here, all boxes lie in the same sub-space. Two strategies: |
---|
| 275 | // - if the tree *must* be complete, make an arbitrary 50-50 split |
---|
| 276 | // - else stop subdividing |
---|
| 277 | // if(builder->mSettings.mRules&SPLIT_COMPLETE) |
---|
| 278 | if(builder->mSettings.mLimit==1) |
---|
| 279 | { |
---|
| 280 | builder->IncreaseNbInvalidSplits(); |
---|
| 281 | NbPos = mNbPrimitives>>1; |
---|
| 282 | } |
---|
| 283 | else return true; |
---|
| 284 | } |
---|
| 285 | |
---|
| 286 | // Now create children and assign their pointers. |
---|
| 287 | if(builder->mNodeBase) |
---|
| 288 | { |
---|
| 289 | // We use a pre-allocated linear pool for complete trees [Opcode 1.3] |
---|
| 290 | AABBTreeNode* Pool = (AABBTreeNode*)builder->mNodeBase; |
---|
| 291 | udword Count = builder->GetCount() - 1; // Count begins to 1... |
---|
| 292 | // Set last bit to tell it shouldn't be freed ### pretty ugly, find a better way. Maybe one bit in mNbPrimitives |
---|
| 293 | ASSERT(!(udword(&Pool[Count+0])&1)); |
---|
| 294 | ASSERT(!(udword(&Pool[Count+1])&1)); |
---|
| 295 | mPos = size_t(&Pool[Count+0])|1; |
---|
| 296 | #ifndef OPC_NO_NEG_VANILLA_TREE |
---|
| 297 | mNeg = size_t(&Pool[Count+1])|1; |
---|
| 298 | #endif |
---|
| 299 | } |
---|
| 300 | else |
---|
| 301 | { |
---|
| 302 | // Non-complete trees and/or Opcode 1.2 allocate nodes on-the-fly |
---|
| 303 | #ifndef OPC_NO_NEG_VANILLA_TREE |
---|
| 304 | mPos = (size_t)new AABBTreeNode; CHECKALLOC(mPos); |
---|
| 305 | mNeg = (size_t)new AABBTreeNode; CHECKALLOC(mNeg); |
---|
| 306 | #else |
---|
| 307 | AABBTreeNode* PosNeg = new AABBTreeNode[2]; |
---|
| 308 | CHECKALLOC(PosNeg); |
---|
| 309 | mPos = (size_t)PosNeg; |
---|
| 310 | #endif |
---|
| 311 | } |
---|
| 312 | |
---|
| 313 | // Update stats |
---|
| 314 | builder->IncreaseCount(2); |
---|
| 315 | |
---|
| 316 | // Assign children |
---|
| 317 | AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); |
---|
| 318 | AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); |
---|
| 319 | Pos->mNodePrimitives = &mNodePrimitives[0]; |
---|
| 320 | Pos->mNbPrimitives = NbPos; |
---|
| 321 | Neg->mNodePrimitives = &mNodePrimitives[NbPos]; |
---|
| 322 | Neg->mNbPrimitives = mNbPrimitives - NbPos; |
---|
| 323 | |
---|
| 324 | return true; |
---|
| 325 | } |
---|
| 326 | |
---|
| 327 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 328 | /** |
---|
| 329 | * Recursive hierarchy building in a top-down fashion. |
---|
| 330 | * \param builder [in] the tree builder |
---|
| 331 | */ |
---|
| 332 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 333 | void AABBTreeNode::_BuildHierarchy(AABBTreeBuilder* builder) |
---|
| 334 | { |
---|
| 335 | // 1) Compute the global box for current node. The box is stored in mBV. |
---|
| 336 | builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); |
---|
| 337 | |
---|
| 338 | // 2) Subdivide current node |
---|
| 339 | Subdivide(builder); |
---|
| 340 | |
---|
| 341 | // 3) Recurse |
---|
| 342 | AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); |
---|
| 343 | AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); |
---|
| 344 | if(Pos) Pos->_BuildHierarchy(builder); |
---|
| 345 | if(Neg) Neg->_BuildHierarchy(builder); |
---|
| 346 | } |
---|
| 347 | |
---|
| 348 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 349 | /** |
---|
| 350 | * Refits the tree (top-down). |
---|
| 351 | * \param builder [in] the tree builder |
---|
| 352 | */ |
---|
| 353 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 354 | void AABBTreeNode::_Refit(AABBTreeBuilder* builder) |
---|
| 355 | { |
---|
| 356 | // 1) Recompute the new global box for current node |
---|
| 357 | builder->ComputeGlobalBox(mNodePrimitives, mNbPrimitives, mBV); |
---|
| 358 | |
---|
| 359 | // 2) Recurse |
---|
| 360 | AABBTreeNode* Pos = (AABBTreeNode*)GetPos(); |
---|
| 361 | AABBTreeNode* Neg = (AABBTreeNode*)GetNeg(); |
---|
| 362 | if(Pos) Pos->_Refit(builder); |
---|
| 363 | if(Neg) Neg->_Refit(builder); |
---|
| 364 | } |
---|
| 365 | |
---|
| 366 | |
---|
| 367 | |
---|
| 368 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 369 | /** |
---|
| 370 | * Constructor. |
---|
| 371 | */ |
---|
| 372 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 373 | AABBTree::AABBTree() : mIndices(null), mTotalNbNodes(0), mPool(null) |
---|
| 374 | { |
---|
| 375 | } |
---|
| 376 | |
---|
| 377 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 378 | /** |
---|
| 379 | * Destructor. |
---|
| 380 | */ |
---|
| 381 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 382 | AABBTree::~AABBTree() |
---|
| 383 | { |
---|
| 384 | Release(); |
---|
| 385 | } |
---|
| 386 | |
---|
| 387 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 388 | /** |
---|
| 389 | * Releases the tree. |
---|
| 390 | */ |
---|
| 391 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 392 | void AABBTree::Release() |
---|
| 393 | { |
---|
| 394 | DELETEARRAY(mPool); |
---|
| 395 | DELETEARRAY(mIndices); |
---|
| 396 | } |
---|
| 397 | |
---|
| 398 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 399 | /** |
---|
| 400 | * Builds a generic AABB tree from a tree builder. |
---|
| 401 | * \param builder [in] the tree builder |
---|
| 402 | * \return true if success |
---|
| 403 | */ |
---|
| 404 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 405 | bool AABBTree::Build(AABBTreeBuilder* builder) |
---|
| 406 | { |
---|
| 407 | // Checkings |
---|
| 408 | if(!builder || !builder->mNbPrimitives) return false; |
---|
| 409 | |
---|
| 410 | // Release previous tree |
---|
| 411 | Release(); |
---|
| 412 | |
---|
| 413 | // Init stats |
---|
| 414 | builder->SetCount(1); |
---|
| 415 | builder->SetNbInvalidSplits(0); |
---|
| 416 | |
---|
| 417 | // Initialize indices. This list will be modified during build. |
---|
| 418 | mIndices = new udword[builder->mNbPrimitives]; |
---|
| 419 | CHECKALLOC(mIndices); |
---|
| 420 | // Identity permutation |
---|
| 421 | for(udword i=0;i<builder->mNbPrimitives;i++) mIndices[i] = i; |
---|
| 422 | |
---|
| 423 | // Setup initial node. Here we have a complete permutation of the app's primitives. |
---|
| 424 | mNodePrimitives = mIndices; |
---|
| 425 | mNbPrimitives = builder->mNbPrimitives; |
---|
| 426 | |
---|
| 427 | // Use a linear array for complete trees (since we can predict the final number of nodes) [Opcode 1.3] |
---|
| 428 | // if(builder->mRules&SPLIT_COMPLETE) |
---|
| 429 | if(builder->mSettings.mLimit==1) |
---|
| 430 | { |
---|
| 431 | // Allocate a pool of nodes |
---|
| 432 | mPool = new AABBTreeNode[builder->mNbPrimitives*2 - 1]; |
---|
| 433 | |
---|
| 434 | builder->mNodeBase = mPool; // ### ugly ! |
---|
| 435 | } |
---|
| 436 | |
---|
| 437 | // Build the hierarchy |
---|
| 438 | _BuildHierarchy(builder); |
---|
| 439 | |
---|
| 440 | // Get back total number of nodes |
---|
| 441 | mTotalNbNodes = builder->GetCount(); |
---|
| 442 | |
---|
| 443 | // For complete trees, check the correct number of nodes has been created [Opcode 1.3] |
---|
| 444 | if(mPool) ASSERT(mTotalNbNodes==builder->mNbPrimitives*2 - 1); |
---|
| 445 | |
---|
| 446 | return true; |
---|
| 447 | } |
---|
| 448 | |
---|
| 449 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 450 | /** |
---|
| 451 | * Computes the depth of the tree. |
---|
| 452 | * A well-balanced tree should have a log(n) depth. A degenerate tree O(n) depth. |
---|
| 453 | * \return depth of the tree |
---|
| 454 | */ |
---|
| 455 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 456 | udword AABBTree::ComputeDepth() const |
---|
| 457 | { |
---|
| 458 | return Walk(null, null); // Use the walking code without callback |
---|
| 459 | } |
---|
| 460 | |
---|
| 461 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 462 | /** |
---|
| 463 | * Walks the tree, calling the user back for each node. |
---|
| 464 | */ |
---|
| 465 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 466 | udword AABBTree::Walk(WalkingCallback callback, void* user_data) const |
---|
| 467 | { |
---|
| 468 | // Call it without callback to compute max depth |
---|
| 469 | udword MaxDepth = 0; |
---|
| 470 | udword CurrentDepth = 0; |
---|
| 471 | |
---|
| 472 | struct Local |
---|
| 473 | { |
---|
| 474 | static void _Walk(const AABBTreeNode* current_node, udword& max_depth, udword& current_depth, WalkingCallback callback, void* user_data) |
---|
| 475 | { |
---|
| 476 | // Checkings |
---|
| 477 | if(!current_node) return; |
---|
| 478 | // Entering a new node => increase depth |
---|
| 479 | current_depth++; |
---|
| 480 | // Keep track of max depth |
---|
| 481 | if(current_depth>max_depth) max_depth = current_depth; |
---|
| 482 | |
---|
| 483 | // Callback |
---|
| 484 | if(callback && !(callback)(current_node, current_depth, user_data)) return; |
---|
| 485 | |
---|
| 486 | // Recurse |
---|
| 487 | if(current_node->GetPos()) { _Walk(current_node->GetPos(), max_depth, current_depth, callback, user_data); current_depth--; } |
---|
| 488 | if(current_node->GetNeg()) { _Walk(current_node->GetNeg(), max_depth, current_depth, callback, user_data); current_depth--; } |
---|
| 489 | } |
---|
| 490 | }; |
---|
| 491 | Local::_Walk(this, MaxDepth, CurrentDepth, callback, user_data); |
---|
| 492 | return MaxDepth; |
---|
| 493 | } |
---|
| 494 | |
---|
| 495 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 496 | /** |
---|
| 497 | * Refits the tree in a top-down way. |
---|
| 498 | * \param builder [in] the tree builder |
---|
| 499 | */ |
---|
| 500 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 501 | bool AABBTree::Refit(AABBTreeBuilder* builder) |
---|
| 502 | { |
---|
| 503 | if(!builder) return false; |
---|
| 504 | _Refit(builder); |
---|
| 505 | return true; |
---|
| 506 | } |
---|
| 507 | |
---|
| 508 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 509 | /** |
---|
| 510 | * Refits the tree in a bottom-up way. |
---|
| 511 | * \param builder [in] the tree builder |
---|
| 512 | */ |
---|
| 513 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 514 | bool AABBTree::Refit2(AABBTreeBuilder* builder) |
---|
| 515 | { |
---|
| 516 | // Checkings |
---|
| 517 | if(!builder) return false; |
---|
| 518 | |
---|
| 519 | ASSERT(mPool); |
---|
| 520 | |
---|
| 521 | // Bottom-up update |
---|
| 522 | Point Min,Max; |
---|
| 523 | Point Min_,Max_; |
---|
| 524 | udword Index = mTotalNbNodes; |
---|
| 525 | while(Index--) |
---|
| 526 | { |
---|
| 527 | AABBTreeNode& Current = mPool[Index]; |
---|
| 528 | |
---|
| 529 | if(Current.IsLeaf()) |
---|
| 530 | { |
---|
| 531 | builder->ComputeGlobalBox(Current.GetPrimitives(), Current.GetNbPrimitives(), *(AABB*)Current.GetAABB()); |
---|
| 532 | } |
---|
| 533 | else |
---|
| 534 | { |
---|
| 535 | Current.GetPos()->GetAABB()->GetMin(Min); |
---|
| 536 | Current.GetPos()->GetAABB()->GetMax(Max); |
---|
| 537 | |
---|
| 538 | Current.GetNeg()->GetAABB()->GetMin(Min_); |
---|
| 539 | Current.GetNeg()->GetAABB()->GetMax(Max_); |
---|
| 540 | |
---|
| 541 | Min.Min(Min_); |
---|
| 542 | Max.Max(Max_); |
---|
| 543 | |
---|
| 544 | ((AABB*)Current.GetAABB())->SetMinMax(Min, Max); |
---|
| 545 | } |
---|
| 546 | } |
---|
| 547 | return true; |
---|
| 548 | } |
---|
| 549 | |
---|
| 550 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 551 | /** |
---|
| 552 | * Computes the number of bytes used by the tree. |
---|
| 553 | * \return number of bytes used |
---|
| 554 | */ |
---|
| 555 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 556 | udword AABBTree::GetUsedBytes() const |
---|
| 557 | { |
---|
| 558 | udword TotalSize = mTotalNbNodes*GetNodeSize(); |
---|
| 559 | if(mIndices) TotalSize+=mNbPrimitives*sizeof(udword); |
---|
| 560 | return TotalSize; |
---|
| 561 | } |
---|
| 562 | |
---|
| 563 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 564 | /** |
---|
| 565 | * Checks the tree is a complete tree or not. |
---|
| 566 | * A complete tree is made of 2*N-1 nodes, where N is the number of primitives in the tree. |
---|
| 567 | * \return true for complete trees |
---|
| 568 | */ |
---|
| 569 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 570 | bool AABBTree::IsComplete() const |
---|
| 571 | { |
---|
| 572 | return (GetNbNodes()==GetNbPrimitives()*2-1); |
---|
| 573 | } |
---|