OPCODE/OPC_OptimizedTree.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 optimized trees. Implements 4 trees:
  12  *      - normal
  13  *      - no leaf
  14  *      - quantized
  15  *      - no leaf / quantized
  16  *
  17  *      \file           OPC_OptimizedTree.cpp
  18  *      \author         Pierre Terdiman
  19  *      \date           March, 20, 2001
  20  */
  21 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  22
  23 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  24 /**
  25  *      A standard AABB tree.
  26  *
  27  *      \class          AABBCollisionTree
  28  *      \author         Pierre Terdiman
  29  *      \version        1.3
  30  *      \date           March, 20, 2001
  31 */
  32 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  33
  34 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  35 /**
  36  *      A no-leaf AABB tree.
  37  *
  38  *      \class          AABBNoLeafTree
  39  *      \author         Pierre Terdiman
  40  *      \version        1.3
  41  *      \date           March, 20, 2001
  42 */
  43 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  44
  45 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  46 /**
  47  *      A quantized AABB tree.
  48  *
  49  *      \class          AABBQuantizedTree
  50  *      \author         Pierre Terdiman
  51  *      \version        1.3
  52  *      \date           March, 20, 2001
  53 */
  54 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  55
  56 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  57 /**
  58  *      A quantized no-leaf AABB tree.
  59  *
  60  *      \class          AABBQuantizedNoLeafTree
  61  *      \author         Pierre Terdiman
  62  *      \version        1.3
  63  *      \date           March, 20, 2001
  64 */
  65 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  66
  67 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  68 // Precompiled Header
  69 #include "Stdafx.h"
  70
  71 using namespace Opcode;
  72
  73 //! Compilation flag:
  74 //! - true to fix quantized boxes (i.e. make sure they enclose the original ones)
  75 //! - false to see the effects of quantization errors (faster, but wrong results in some cases)
  76 static const bool gFixQuantized = true;
  77
  78 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  79 /**
  80  *      Builds an implicit tree from a standard one. An implicit tree is a complete tree (2*N-1 nodes) whose negative
  81  *      box pointers and primitive pointers have been made implicit, hence packing 3 pointers in one.
  82  *
  83  *      Layout for implicit trees:
  84  *      Node:
  85  *                      - box
  86  *                      - data (32-bits value)
  87  *
  88  *      if data's LSB = 1 =>    remaining bits are a primitive pointer
  89  *      else                                    remaining bits are a P-node pointer, and N = P + 1
  90  *
  91  *      \relates        AABBCollisionNode
  92  *      \fn                     _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
  93  *      \param          linear                  [in] base address of destination nodes
  94  *      \param          box_id                  [in] index of destination node
  95  *      \param          current_id              [in] current running index
  96  *      \param          current_node    [in] current node from input tree
  97  */
  98 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  99 static void _BuildCollisionTree(AABBCollisionNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
 100 {
 101         // Current node from input tree is "current_node". Must be flattened into "linear[boxid]".
 102
 103         // Store the AABB
 104         current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
 105         current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
 106         // Store remaining info
 107         if(current_node->IsLeaf())
 108         {
 109                 // The input tree must be complete => i.e. one primitive/leaf
 110                 ASSERT(current_node->GetNbPrimitives()==1);
 111                 // Get the primitive index from the input tree
 112                 udword PrimitiveIndex = current_node->GetPrimitives()[0];
 113                 // Setup box data as the primitive index, marked as leaf
 114                 linear[box_id].mData = (PrimitiveIndex<<1)|1;
 115         }
 116         else
 117         {
 118                 // To make the negative one implicit, we must store P and N in successive order
 119                 udword PosID = current_id++;    // Get a new id for positive child
 120                 udword NegID = current_id++;    // Get a new id for negative child
 121                 // Setup box data as the forthcoming new P pointer
 122                 linear[box_id].mData = (size_t)&linear[PosID];
 123                 // Make sure it's not marked as leaf
 124                 ASSERT(!(linear[box_id].mData&1));
 125                 // Recurse with new IDs
 126                 _BuildCollisionTree(linear, PosID, current_id, current_node->GetPos());
 127                 _BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg());
 128         }
 129 }
 130
 131 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 132 /**
 133  *      Builds a "no-leaf" tree from a standard one. This is a tree whose leaf nodes have been removed.
 134  *
 135  *      Layout for no-leaf trees:
 136  *
 137  *      Node:
 138  *                      - box
 139  *                      - P pointer => a node (LSB=0) or a primitive (LSB=1)
 140  *                      - N pointer => a node (LSB=0) or a primitive (LSB=1)
 141  *
 142  *      \relates        AABBNoLeafNode
 143  *      \fn                     _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
 144  *      \param          linear                  [in] base address of destination nodes
 145  *      \param          box_id                  [in] index of destination node
 146  *      \param          current_id              [in] current running index
 147  *      \param          current_node    [in] current node from input tree
 148  */
 149 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 150 static void _BuildNoLeafTree(AABBNoLeafNode* linear, const udword box_id, udword& current_id, const AABBTreeNode* current_node)
 151 {
 152         const AABBTreeNode* P = current_node->GetPos();
 153         const AABBTreeNode* N = current_node->GetNeg();
 154         // Leaf nodes here?!
 155         ASSERT(P);
 156         ASSERT(N);
 157         // Internal node => keep the box
 158         current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
 159         current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
 160
 161         if(P->IsLeaf())
 162         {
 163                 // The input tree must be complete => i.e. one primitive/leaf
 164                 ASSERT(P->GetNbPrimitives()==1);
 165                 // Get the primitive index from the input tree
 166                 udword PrimitiveIndex = P->GetPrimitives()[0];
 167                 // Setup prev box data as the primitive index, marked as leaf
 168                 linear[box_id].mPosData = (PrimitiveIndex<<1)|1;
 169         }
 170         else
 171         {
 172                 // Get a new id for positive child
 173                 udword PosID = current_id++;
 174                 // Setup box data
 175                 linear[box_id].mPosData = (size_t)&linear[PosID];
 176                 // Make sure it's not marked as leaf
 177                 ASSERT(!(linear[box_id].mPosData&1));
 178                 // Recurse
 179                 _BuildNoLeafTree(linear, PosID, current_id, P);
 180         }
 181
 182         if(N->IsLeaf())
 183         {
 184                 // The input tree must be complete => i.e. one primitive/leaf
 185                 ASSERT(N->GetNbPrimitives()==1);
 186                 // Get the primitive index from the input tree
 187                 udword PrimitiveIndex = N->GetPrimitives()[0];
 188                 // Setup prev box data as the primitive index, marked as leaf
 189                 linear[box_id].mNegData = (PrimitiveIndex<<1)|1;
 190         }
 191         else
 192         {
 193                 // Get a new id for negative child
 194                 udword NegID = current_id++;
 195                 // Setup box data
 196                 linear[box_id].mNegData = (size_t)&linear[NegID];
 197                 // Make sure it's not marked as leaf
 198                 ASSERT(!(linear[box_id].mNegData&1));
 199                 // Recurse
 200                 _BuildNoLeafTree(linear, NegID, current_id, N);
 201         }
 202 }
 203
 204 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 205 /**
 206  *      Constructor.
 207  */
 208 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 209 AABBCollisionTree::AABBCollisionTree() : mNodes(null)
 210 {
 211 }
 212
 213 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 214 /**
 215  *      Destructor.
 216  */
 217 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 218 AABBCollisionTree::~AABBCollisionTree()
 219 {
 220         DELETEARRAY(mNodes);
 221 }
 222
 223 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 224 /**
 225  *      Builds the collision tree from a generic AABB tree.
 226  *      \param          tree                    [in] generic AABB tree
 227  *      \return         true if success
 228  */
 229 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 230 bool AABBCollisionTree::Build(AABBTree* tree)
 231 {
 232         // Checkings
 233         if(!tree)       return false;
 234         // Check the input tree is complete
 235         udword NbTriangles      = tree->GetNbPrimitives();
 236         udword NbNodes          = tree->GetNbNodes();
 237         if(NbNodes!=NbTriangles*2-1)    return false;
 238
 239         // Get nodes
 240         if(mNbNodes!=NbNodes)   // Same number of nodes => keep moving
 241         {
 242                 mNbNodes = NbNodes;
 243                 DELETEARRAY(mNodes);
 244                 mNodes = new AABBCollisionNode[NbNodes];
 245                 CHECKALLOC(mNodes);
 246         }
 247
 248         // Build the tree
 249         udword CurID = 1;
 250         _BuildCollisionTree(mNodes, 0, CurID, tree);
 251         ASSERT(CurID==NbNodes);
 252
 253         return true;
 254 }
 255
 256 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 257 /**
 258  *      Refits the collision tree after vertices have been modified.
 259  *      \param          mesh_interface  [in] mesh interface for current model
 260  *      \return         true if success
 261  */
 262 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 263 bool AABBCollisionTree::Refit(const MeshInterface* /*mesh_interface*/)
 264 {
 265         ASSERT(!"Not implemented since AABBCollisionTrees have twice as more nodes to refit as AABBNoLeafTrees!");
 266         return false;
 267 }
 268
 269 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 270 /**
 271  *      Walks the tree and call the user back for each node.
 272  *      \param          callback        [in] walking callback
 273  *      \param          user_data       [in] callback's user data
 274  *      \return         true if success
 275  */
 276 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 277 bool AABBCollisionTree::Walk(GenericWalkingCallback callback, void* user_data) const
 278 {
 279         if(!callback)   return false;
 280
 281         struct Local
 282         {
 283                 static void _Walk(const AABBCollisionNode* current_node, GenericWalkingCallback callback, void* user_data)
 284                 {
 285                         if(!current_node || !(callback)(current_node, user_data))       return;
 286
 287                         if(!current_node->IsLeaf())
 288                         {
 289                                 _Walk(current_node->GetPos(), callback, user_data);
 290                                 _Walk(current_node->GetNeg(), callback, user_data);
 291                         }
 292                 }
 293         };
 294         Local::_Walk(mNodes, callback, user_data);
 295         return true;
 296 }
 297
 298
 299 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 300 /**
 301  *      Constructor.
 302  */
 303 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 304 AABBNoLeafTree::AABBNoLeafTree() : mNodes(null)
 305 {
 306 }
 307
 308 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 309 /**
 310  *      Destructor.
 311  */
 312 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 313 AABBNoLeafTree::~AABBNoLeafTree()
 314 {
 315         DELETEARRAY(mNodes);
 316 }
 317
 318 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 319 /**
 320  *      Builds the collision tree from a generic AABB tree.
 321  *      \param          tree                    [in] generic AABB tree
 322  *      \return         true if success
 323  */
 324 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 325 bool AABBNoLeafTree::Build(AABBTree* tree)
 326 {
 327         // Checkings
 328         if(!tree)       return false;
 329         // Check the input tree is complete
 330         udword NbTriangles      = tree->GetNbPrimitives();
 331         udword NbExistingNodes          = tree->GetNbNodes();
 332         if(NbExistingNodes!=NbTriangles*2-1)    return false;
 333
 334         udword NbNodes = NbTriangles-1;
 335         // Get nodes
 336         if(mNbNodes!=NbNodes)   // Same number of nodes => keep moving
 337         {
 338                 mNbNodes = NbNodes;
 339                 DELETEARRAY(mNodes);
 340                 mNodes = new AABBNoLeafNode[NbNodes];
 341                 CHECKALLOC(mNodes);
 342         }
 343
 344         // Build the tree
 345         udword CurID = 1;
 346         _BuildNoLeafTree(mNodes, 0, CurID, tree);
 347         ASSERT(CurID==NbNodes);
 348
 349         return true;
 350 }
 351
 352 inline_ void ComputeMinMax(Point& min, Point& max, const VertexPointers& vp)
 353 {
 354         // Compute triangle's AABB = a leaf box
 355 #ifdef OPC_USE_FCOMI    // a 15% speedup on my machine, not much
 356         min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
 357         max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
 358
 359         min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
 360         max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
 361
 362         min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
 363         max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
 364 #else
 365         min = *vp.Vertex[0];
 366         max = *vp.Vertex[0];
 367         min.Min(*vp.Vertex[1]);
 368         max.Max(*vp.Vertex[1]);
 369         min.Min(*vp.Vertex[2]);
 370         max.Max(*vp.Vertex[2]);
 371 #endif
 372 }
 373
 374 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 375 /**
 376  *      Refits the collision tree after vertices have been modified.
 377  *      \param          mesh_interface  [in] mesh interface for current model
 378  *      \return         true if success
 379  */
 380 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 381 bool AABBNoLeafTree::Refit(const MeshInterface* mesh_interface)
 382 {
 383         // Checkings
 384         if(!mesh_interface)     return false;
 385
 386         // Bottom-up update
 387         VertexPointers VP;
 388         ConversionArea VC;
 389         Point Min,Max;
 390         Point Min_,Max_;
 391         udword Index = mNbNodes;
 392         while(Index--)
 393         {
 394                 AABBNoLeafNode& Current = mNodes[Index];
 395
 396                 if(Current.HasPosLeaf())
 397                 {
 398                         mesh_interface->GetTriangle(VP, Current.GetPosPrimitive(), VC);
 399                         ComputeMinMax(Min, Max, VP);
 400                 }
 401                 else
 402                 {
 403                         const CollisionAABB& CurrentBox = Current.GetPos()->mAABB;
 404                         CurrentBox.GetMin(Min);
 405                         CurrentBox.GetMax(Max);
 406                 }
 407
 408                 if(Current.HasNegLeaf())
 409                 {
 410                         mesh_interface->GetTriangle(VP, Current.GetNegPrimitive(), VC);
 411                         ComputeMinMax(Min_, Max_, VP);
 412                 }
 413                 else
 414                 {
 415                         const CollisionAABB& CurrentBox = Current.GetNeg()->mAABB;
 416                         CurrentBox.GetMin(Min_);
 417                         CurrentBox.GetMax(Max_);
 418                 }
 419 #ifdef OPC_USE_FCOMI
 420                 Min.x = FCMin2(Min.x, Min_.x);
 421                 Max.x = FCMax2(Max.x, Max_.x);
 422                 Min.y = FCMin2(Min.y, Min_.y);
 423                 Max.y = FCMax2(Max.y, Max_.y);
 424                 Min.z = FCMin2(Min.z, Min_.z);
 425                 Max.z = FCMax2(Max.z, Max_.z);
 426 #else
 427                 Min.Min(Min_);
 428                 Max.Max(Max_);
 429 #endif
 430                 Current.mAABB.SetMinMax(Min, Max);
 431         }
 432         return true;
 433 }
 434
 435 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 436 /**
 437  *      Walks the tree and call the user back for each node.
 438  *      \param          callback        [in] walking callback
 439  *      \param          user_data       [in] callback's user data
 440  *      \return         true if success
 441  */
 442 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 443 bool AABBNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
 444 {
 445         if(!callback)   return false;
 446
 447         struct Local
 448         {
 449                 static void _Walk(const AABBNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
 450                 {
 451                         if(!current_node || !(callback)(current_node, user_data))       return;
 452
 453                         if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data);
 454                         if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data);
 455                 }
 456         };
 457         Local::_Walk(mNodes, callback, user_data);
 458         return true;
 459 }
 460
 461 // Quantization notes:
 462 // - We could use the highest bits of mData to store some more quantized bits. Dequantization code
 463 //   would be slightly more complex, but number of overlap tests would be reduced (and anyhow those
 464 //   bits are currently wasted). Of course it's not possible if we move to 16 bits mData.
 465 // - Something like "16 bits floats" could be tested, to bypass the int-to-float conversion.
 466 // - A dedicated BV-BV test could be used, dequantizing while testing for overlap. (i.e. it's some
 467 //   lazy-dequantization which may save some work in case of early exits). At the very least some
 468 //   muls could be saved by precomputing several more matrices. But maybe not worth the pain.
 469 // - Do we need to dequantize anyway? Not doing the extents-related muls only implies the box has
 470 //   been scaled, for example.
 471 // - The deeper we move into the hierarchy, the smaller the extents should be. May not need a fixed
 472 //   number of quantization bits. Even better, could probably be best delta-encoded.
 473
 474
 475 // Find max values. Some people asked why I wasn't simply using the first node. Well, I can't.
 476 // I'm not looking for (min, max) values like in a standard AABB, I'm looking for the extremal
 477 // centers/extents in order to quantize them. The first node would only give a single center and
 478 // a single extents. While extents would be the biggest, the center wouldn't.
 479 #define FIND_MAX_VALUES                                                                                                                                                 \
 480         /* Get max values */                                                                                                                                            \
 481         Point CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);                                                                                            \
 482         Point EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);                                                                                            \
 483         const udword NbNodes = mNbNodes;                                                            \
 484         for(udword i=0;i<NbNodes;i++)                                                                                                                           \
 485         {                                                                                                                                                                                       \
 486                 float cx = fabsf(Nodes[i].mAABB.mCenter.x); if(cx>CMax.x)       CMax.x = cx;                \
 487                 float cy = fabsf(Nodes[i].mAABB.mCenter.y); if(cy>CMax.y)       CMax.y = cy;                \
 488                 float cz = fabsf(Nodes[i].mAABB.mCenter.z); if(cz>CMax.z)       CMax.z = cz;                \
 489                 float ex = fabsf(Nodes[i].mAABB.mExtents.x); if(ex>EMax.x)      EMax.x = ex;                \
 490                 float ey = fabsf(Nodes[i].mAABB.mExtents.y); if(ey>EMax.y)      EMax.y = ey;                \
 491                 float ez = fabsf(Nodes[i].mAABB.mExtents.z); if(ez>EMax.z)      EMax.z = ez;                \
 492         }
 493
 494 #define INIT_QUANTIZATION                                                                                                       \
 495         udword nbc=15;  /* Keep one bit for sign */                                                             \
 496         udword nbe=15;  /* Keep one bit for fix */                                                              \
 497         if(!gFixQuantized) nbe++;                                                                                               \
 498                                                                                                                                                         \
 499         /* Compute quantization coeffs */                                                                               \
 500         Point CQuantCoeff, EQuantCoeff;                                                                                 \
 501         CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f;                 \
 502         CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f;                 \
 503         CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f;                 \
 504         EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f;                 \
 505         EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f;                 \
 506         EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f;                 \
 507         /* Compute and save dequantization coeffs */                                                    \
 508         mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f;             \
 509         mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f;             \
 510         mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f;             \
 511         mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f;    \
 512         mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f;    \
 513         mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f;    \
 514
 515 #define PERFORM_QUANTIZATION                                                                                                            \
 516         /* Quantize */                                                                                                                                  \
 517         mNodes[i].mAABB.mCenter[0] = sword(Nodes[i].mAABB.mCenter.x * CQuantCoeff.x);   \
 518         mNodes[i].mAABB.mCenter[1] = sword(Nodes[i].mAABB.mCenter.y * CQuantCoeff.y);   \
 519         mNodes[i].mAABB.mCenter[2] = sword(Nodes[i].mAABB.mCenter.z * CQuantCoeff.z);   \
 520         mNodes[i].mAABB.mExtents[0] = uword(Nodes[i].mAABB.mExtents.x * EQuantCoeff.x); \
 521         mNodes[i].mAABB.mExtents[1] = uword(Nodes[i].mAABB.mExtents.y * EQuantCoeff.y); \
 522         mNodes[i].mAABB.mExtents[2] = uword(Nodes[i].mAABB.mExtents.z * EQuantCoeff.z); \
 523         /* Fix quantized boxes */                                                                                                               \
 524         if(gFixQuantized)                                                                                                                               \
 525         {                                                                                                                                                               \
 526                 /* Make sure the quantized box is still valid */                                                        \
 527                 Point Max = Nodes[i].mAABB.mCenter + Nodes[i].mAABB.mExtents;                           \
 528                 Point Min = Nodes[i].mAABB.mCenter - Nodes[i].mAABB.mExtents;                           \
 529                 /* For each axis */                                                                                                                     \
 530                 for(udword j=0;j<3;j++)                                                                                                         \
 531                 {       /* Dequantize the box center */                                                                                 \
 532                         float qc = float(mNodes[i].mAABB.mCenter[j]) * mCenterCoeff[j];                 \
 533                         bool FixMe=true;                                                                                                                \
 534                         do                                                                                                                                              \
 535                         {       /* Dequantize the box extent */                                                                         \
 536                                 float qe = float(mNodes[i].mAABB.mExtents[j]) * mExtentsCoeff[j];       \
 537                                 /* Compare real & dequantized values */                                                         \
 538                                 if(qc+qe<Max[j] || qc-qe>Min[j])                                        \
 539                                 {                                                                   \
 540                                         mNodes[i].mAABB.mExtents[j]++;                                  \
 541                                         /* Prevent wrapping */                                                                                  \
 542                                         if(!mNodes[i].mAABB.mExtents[j])                                                                \
 543                                         {                                                                                                                               \
 544                                                 mNodes[i].mAABB.mExtents[j]=0xffff;                                                     \
 545                                                 FixMe=false;                                                                                            \
 546                                         }                                                                                                                               \
 547                                 }                                                                   \
 548                                 else FixMe=false;                                                   \
 549                         }while(FixMe);                                                                                                                  \
 550                 }                                                                                                                                                       \
 551         }
 552
 553 #define REMAP_DATA(member, NodeType)                                                            \
 554         /* Fix data */                                                                                                  \
 555         Data = Nodes[i].member;                                                                                 \
 556         if(!(Data&1))                                                                                                   \
 557         {                                                                                                                               \
 558                 /* Compute box number */                                                                        \
 559                 size_t Nb = ((NodeType *)(Data) - (Nodes));                     \
 560                 Data = (size_t) &mNodes[Nb];                                \
 561         }                                                               \
 562         /* ...remapped */                                                                                               \
 563         mNodes[i].member = Data;
 564
 565 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 566 /**
 567  *      Constructor.
 568  */
 569 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 570 AABBQuantizedTree::AABBQuantizedTree() : mNodes(null)
 571 {
 572 }
 573
 574 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 575 /**
 576  *      Destructor.
 577  */
 578 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 579 AABBQuantizedTree::~AABBQuantizedTree()
 580 {
 581         DELETEARRAY(mNodes);
 582 }
 583
 584 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 585 /**
 586  *      Builds the collision tree from a generic AABB tree.
 587  *      \param          tree                    [in] generic AABB tree
 588  *      \return         true if success
 589  */
 590 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 591 bool AABBQuantizedTree::Build(AABBTree* tree)
 592 {
 593         // Checkings
 594         if(!tree)       return false;
 595         // Check the input tree is complete
 596         udword NbTriangles      = tree->GetNbPrimitives();
 597         udword NbNodes          = tree->GetNbNodes();
 598         if(NbNodes!=NbTriangles*2-1)    return false;
 599
 600         // Get nodes
 601         mNbNodes = NbNodes;
 602         DELETEARRAY(mNodes);
 603         AABBCollisionNode* Nodes = new AABBCollisionNode[NbNodes];
 604         CHECKALLOC(Nodes);
 605
 606         // Build the tree
 607         udword CurID = 1;
 608         _BuildCollisionTree(Nodes, 0, CurID, tree);
 609
 610         // Quantize
 611         {
 612                 mNodes = new AABBQuantizedNode[NbNodes];
 613
 614                 if (mNodes != null)
 615                 {
 616                         // Get max values
 617                         FIND_MAX_VALUES
 618
 619                         // Quantization
 620                         INIT_QUANTIZATION
 621
 622                         // Quantize
 623                         size_t Data;
 624                         for(udword i=0;i<NbNodes;i++)
 625                         {
 626                                 PERFORM_QUANTIZATION
 627                                         REMAP_DATA(mData, AABBCollisionNode)
 628                         }
 629                 }
 630
 631                 DELETEARRAY(Nodes);
 632                 CHECKALLOC(mNodes);
 633         }
 634
 635         return true;
 636 }
 637
 638 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 639 /**
 640  *      Refits the collision tree after vertices have been modified.
 641  *      \param          mesh_interface  [in] mesh interface for current model
 642  *      \return         true if success
 643  */
 644 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 645 bool AABBQuantizedTree::Refit(const MeshInterface* /*mesh_interface*/)
 646 {
 647         ASSERT(!"Not implemented since requantizing is painful !");
 648         return false;
 649 }
 650
 651 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 652 /**
 653  *      Walks the tree and call the user back for each node.
 654  *      \param          callback        [in] walking callback
 655  *      \param          user_data       [in] callback's user data
 656  *      \return         true if success
 657  */
 658 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 659 bool AABBQuantizedTree::Walk(GenericWalkingCallback callback, void* user_data) const
 660 {
 661         if(!callback)   return false;
 662
 663         struct Local
 664         {
 665                 static void _Walk(const AABBQuantizedNode* current_node, GenericWalkingCallback callback, void* user_data)
 666                 {
 667                         if(!current_node || !(callback)(current_node, user_data))       return;
 668
 669                         if(!current_node->IsLeaf())
 670                         {
 671                                 _Walk(current_node->GetPos(), callback, user_data);
 672                                 _Walk(current_node->GetNeg(), callback, user_data);
 673                         }
 674                 }
 675         };
 676         Local::_Walk(mNodes, callback, user_data);
 677         return true;
 678 }
 679
 680
 681
 682 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 683 /**
 684  *      Constructor.
 685  */
 686 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 687 AABBQuantizedNoLeafTree::AABBQuantizedNoLeafTree() : mNodes(null)
 688 {
 689 }
 690
 691 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 692 /**
 693  *      Destructor.
 694  */
 695 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 696 AABBQuantizedNoLeafTree::~AABBQuantizedNoLeafTree()
 697 {
 698         DELETEARRAY(mNodes);
 699 }
 700
 701 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 702 /**
 703  *      Builds the collision tree from a generic AABB tree.
 704  *      \param          tree                    [in] generic AABB tree
 705  *      \return         true if success
 706  */
 707 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 708 bool AABBQuantizedNoLeafTree::Build(AABBTree* tree)
 709 {
 710         // Checkings
 711         if(!tree)       return false;
 712         // Check the input tree is complete
 713         udword NbTriangles      = tree->GetNbPrimitives();
 714         udword NbExistingNodes = tree->GetNbNodes();
 715         if(NbExistingNodes!=NbTriangles*2-1)    return false;
 716
 717         // Get nodes
 718         udword NbNodes = NbTriangles-1;
 719         mNbNodes = NbNodes;
 720         DELETEARRAY(mNodes);
 721         AABBNoLeafNode* Nodes = new AABBNoLeafNode[NbNodes];
 722         CHECKALLOC(Nodes);
 723
 724         // Build the tree
 725         udword CurID = 1;
 726         _BuildNoLeafTree(Nodes, 0, CurID, tree);
 727         ASSERT(CurID==NbNodes);
 728
 729         // Quantize
 730         {
 731                 mNodes = new AABBQuantizedNoLeafNode[NbNodes];
 732
 733                 if (mNodes != null)
 734                 {
 735                         // Get max values
 736                         FIND_MAX_VALUES
 737
 738                         // Quantization
 739                         INIT_QUANTIZATION
 740
 741                         // Quantize
 742                         size_t Data;
 743                         for(udword i=0;i<NbNodes;i++)
 744                         {
 745                                 PERFORM_QUANTIZATION
 746                                 REMAP_DATA(mPosData, AABBNoLeafNode)
 747                                 REMAP_DATA(mNegData, AABBNoLeafNode)
 748                         }
 749                 }
 750
 751                 DELETEARRAY(Nodes);
 752                 CHECKALLOC(mNodes);
 753         }
 754
 755         return true;
 756 }
 757
 758 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 759 /**
 760  *      Refits the collision tree after vertices have been modified.
 761  *      \param          mesh_interface  [in] mesh interface for current model
 762  *      \return         true if success
 763  */
 764 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 765 bool AABBQuantizedNoLeafTree::Refit(const MeshInterface* /*mesh_interface*/)
 766 {
 767         ASSERT(!"Not implemented since requantizing is painful !");
 768         return false;
 769 }
 770
 771 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 772 /**
 773  *      Walks the tree and call the user back for each node.
 774  *      \param          callback        [in] walking callback
 775  *      \param          user_data       [in] callback's user data
 776  *      \return         true if success
 777  */
 778 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 779 bool AABBQuantizedNoLeafTree::Walk(GenericWalkingCallback callback, void* user_data) const
 780 {
 781         if(!callback)   return false;
 782
 783         struct Local
 784         {
 785                 static void _Walk(const AABBQuantizedNoLeafNode* current_node, GenericWalkingCallback callback, void* user_data)
 786                 {
 787                         if(!current_node || !(callback)(current_node, user_data))       return;
 788
 789                         if(!current_node->HasPosLeaf()) _Walk(current_node->GetPos(), callback, user_data);
 790                         if(!current_node->HasNegLeaf()) _Walk(current_node->GetNeg(), callback, user_data);
 791                 }
 792         };
 793         Local::_Walk(mNodes, callback, user_data);
 794         return true;
 795 }