Engine/lib/opcode/OPC_AABBTree.cpp

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