Extras/CDTestFramework/Opcode/OPC_AABBTree.cpp

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