OPCODE/OPC_AABBCollider.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 an AABB collider.
  12  *      \file           OPC_AABBCollider.cpp
  13  *      \author         Pierre Terdiman
  14  *      \date           January, 1st, 2002
  15  */
  16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      Contains an AABB-vs-tree collider.
  21  *
  22  *      \class          AABBCollider
  23  *      \author         Pierre Terdiman
  24  *      \version        1.3
  25  *      \date           January, 1st, 2002
  26 */
  27 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  28
  29 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  30 // Precompiled Header
  31 #include "Stdafx.h"
  32
  33 using namespace Opcode;
  34
  35 #include "OPC_BoxBoxOverlap.h"
  36 #include "OPC_TriBoxOverlap.h"
  37
  38 #define SET_CONTACT(prim_index, flag)                                           \
  39         /* Set contact status */                                                                \
  40         mFlags |= flag;                                                                                 \
  41         mTouchedPrimitives->Add(udword(prim_index));
  42
  43 //! AABB-triangle test
  44 #define AABB_PRIM(prim_index, flag)                                                     \
  45         /* Request vertices from the app */                                             \
  46         VertexPointers VP;      ConversionArea VC;      mIMesh->GetTriangle(VP, prim_index, VC); \
  47         mLeafVerts[0] = *VP.Vertex[0];                                                  \
  48         mLeafVerts[1] = *VP.Vertex[1];                                                  \
  49         mLeafVerts[2] = *VP.Vertex[2];                                                  \
  50         /* Perform triangle-box overlap test */                                 \
  51         if(TriBoxOverlap())                                                                             \
  52         {                                                                                                               \
  53                 SET_CONTACT(prim_index, flag)                                           \
  54         }
  55
  56 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  57 /**
  58  *      Constructor.
  59  */
  60 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  61 AABBCollider::AABBCollider()
  62 {
  63 }
  64
  65 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  66 /**
  67  *      Destructor.
  68  */
  69 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  70 AABBCollider::~AABBCollider()
  71 {
  72 }
  73
  74 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  75 /**
  76  *      Generic collision query for generic OPCODE models. After the call, access the results:
  77  *      - with GetContactStatus()
  78  *      - with GetNbTouchedPrimitives()
  79  *      - with GetTouchedPrimitives()
  80  *
  81  *      \param          cache           [in/out] a box cache
  82  *      \param          box                     [in] collision AABB in world space
  83  *      \param          model           [in] Opcode model to collide with
  84  *      \return         true if success
  85  *      \warning        SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only.
  86  */
  87 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  88 bool AABBCollider::Collide(AABBCache& cache, const CollisionAABB& box, const Model& model)
  89 {
  90         // Checkings
  91         if(!Setup(&model))      return false;
  92
  93         // Init collision query
  94         if(InitQuery(cache, box))       return true;
  95
  96         if(!model.HasLeafNodes())
  97         {
  98                 if(model.IsQuantized())
  99                 {
 100                         const AABBQuantizedNoLeafTree* Tree = static_cast<const AABBQuantizedNoLeafTree *>(model.GetTree());
 101
 102                         // Setup dequantization coeffs
 103                         mCenterCoeff    = Tree->mCenterCoeff;
 104                         mExtentsCoeff   = Tree->mExtentsCoeff;
 105
 106                         // Perform collision query
 107                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes());
 108                         else                                            _Collide(Tree->GetNodes());
 109                 }
 110                 else
 111                 {
 112                         const AABBNoLeafTree* Tree = static_cast<const AABBNoLeafTree *>(model.GetTree());
 113
 114                         // Perform collision query
 115                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes());
 116                         else                                            _Collide(Tree->GetNodes());
 117                 }
 118         }
 119         else
 120         {
 121                 if(model.IsQuantized())
 122                 {
 123                         const AABBQuantizedTree* Tree = static_cast<const AABBQuantizedTree *>(model.GetTree());
 124
 125                         // Setup dequantization coeffs
 126                         mCenterCoeff    = Tree->mCenterCoeff;
 127                         mExtentsCoeff   = Tree->mExtentsCoeff;
 128
 129                         // Perform collision query
 130                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes());
 131                         else                                            _Collide(Tree->GetNodes());
 132                 }
 133                 else
 134                 {
 135                         const AABBCollisionTree* Tree = static_cast<const AABBCollisionTree *>(model.GetTree());
 136
 137                         // Perform collision query
 138                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes());
 139                         else                                            _Collide(Tree->GetNodes());
 140                 }
 141         }
 142         return true;
 143 }
 144
 145 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 146 /**
 147  *      Initializes a collision query :
 148  *      - reset stats & contact status
 149  *      - check temporal coherence
 150  *
 151  *      \param          cache           [in/out] a box cache
 152  *      \param          box                     [in] AABB in world space
 153  *      \return         TRUE if we can return immediately
 154  */
 155 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 156 BOOL AABBCollider::InitQuery(AABBCache& cache, const CollisionAABB& box)
 157 {
 158         // 1) Call the base method
 159         VolumeCollider::InitQuery();
 160
 161         // 2) Keep track of the query box
 162         mBox = box;
 163
 164         // 3) Setup destination pointer
 165         mTouchedPrimitives = &cache.TouchedPrimitives;
 166
 167         // 4) Special case: 1-triangle meshes [Opcode 1.3]
 168         if(mCurrentModel && mCurrentModel->HasSingleNode())
 169         {
 170                 if(!SkipPrimitiveTests())
 171                 {
 172                         // We simply perform the BV-Prim overlap test each time. We assume single triangle has index 0.
 173                         mTouchedPrimitives->Reset();
 174
 175                         // Perform overlap test between the unique triangle and the box (and set contact status if needed)
 176                         AABB_PRIM(udword(0), OPC_CONTACT)
 177
 178                         // Return immediately regardless of status
 179                         return TRUE;
 180                 }
 181         }
 182
 183         // 5) Check temporal coherence :
 184         if(TemporalCoherenceEnabled())
 185         {
 186                 // Here we use temporal coherence
 187                 // => check results from previous frame before performing the collision query
 188                 if(FirstContactEnabled())
 189                 {
 190                         // We're only interested in the first contact found => test the unique previously touched face
 191                         if(mTouchedPrimitives->GetNbEntries())
 192                         {
 193                                 // Get index of previously touched face = the first entry in the array
 194                                 udword PreviouslyTouchedFace = mTouchedPrimitives->GetEntry(0);
 195
 196                                 // Then reset the array:
 197                                 // - if the overlap test below is successful, the index we'll get added back anyway
 198                                 // - if it isn't, then the array should be reset anyway for the normal query
 199                                 mTouchedPrimitives->Reset();
 200
 201                                 // Perform overlap test between the cached triangle and the box (and set contact status if needed)
 202                                 AABB_PRIM(PreviouslyTouchedFace, OPC_TEMPORAL_CONTACT)
 203
 204                                 // Return immediately if possible
 205                                 if(GetContactStatus())  return TRUE;
 206                         }
 207                         // else no face has been touched during previous query
 208                         // => we'll have to perform a normal query
 209                 }
 210                 else
 211                 {
 212                         // We're interested in all contacts =>test the new real box N(ew) against the previous fat box P(revious):
 213                         if(IsCacheValid(cache) && mBox.IsInside(cache.FatBox))
 214                         {
 215                                 // - if N is included in P, return previous list
 216                                 // => we simply leave the list (mTouchedFaces) unchanged
 217
 218                                 // Set contact status if needed
 219                                 if(mTouchedPrimitives->GetNbEntries())  mFlags |= OPC_TEMPORAL_CONTACT;
 220
 221                                 // In any case we don't need to do a query
 222                                 return TRUE;
 223                         }
 224                         else
 225                         {
 226                                 // - else do the query using a fat N
 227
 228                                 // Reset cache since we'll about to perform a real query
 229                                 mTouchedPrimitives->Reset();
 230
 231                                 // Make a fat box so that coherence will work for subsequent frames
 232                                 mBox.mExtents *= cache.FatCoeff;
 233
 234                                 // Update cache with query data (signature for cached faces)
 235                                 cache.FatBox = mBox;
 236                         }
 237                 }
 238         }
 239         else
 240         {
 241                 // Here we don't use temporal coherence => do a normal query
 242                 mTouchedPrimitives->Reset();
 243         }
 244
 245         // 5) Precompute min & max bounds if needed
 246         mMin = box.mCenter - box.mExtents;
 247         mMax = box.mCenter + box.mExtents;
 248
 249         return FALSE;
 250 }
 251
 252 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 253 /**
 254  *      Collision query for vanilla AABB trees.
 255  *      \param          cache           [in/out] a box cache
 256  *      \param          box                     [in] collision AABB in world space
 257  *      \param          tree            [in] AABB tree
 258  *      \return         true if success
 259  */
 260 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 261 bool AABBCollider::Collide(AABBCache& cache, const CollisionAABB& box, const AABBTree* tree)
 262 {
 263         // This is typically called for a scene tree, full of -AABBs-, not full of triangles.
 264         // So we don't really have "primitives" to deal with. Hence it doesn't work with
 265         // "FirstContact" + "TemporalCoherence".
 266         ASSERT( !(FirstContactEnabled() && TemporalCoherenceEnabled()) );
 267
 268         // Checkings
 269         if(!tree)       return false;
 270
 271         // Init collision query
 272         if(InitQuery(cache, box))       return true;
 273
 274         // Perform collision query
 275         _Collide(tree);
 276
 277         return true;
 278 }
 279
 280 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 281 /**
 282  *      Checks the AABB completely contains the box. In which case we can end the query sooner.
 283  *      \param          bc      [in] box center
 284  *      \param          be      [in] box extents
 285  *      \return         true if the AABB contains the whole box
 286  */
 287 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 288 inline_ BOOL AABBCollider::AABBContainsBox(const Point& bc, const Point& be)
 289 {
 290         if(mMin.x > bc.x - be.x)        return FALSE;
 291         if(mMin.y > bc.y - be.y)        return FALSE;
 292         if(mMin.z > bc.z - be.z)        return FALSE;
 293
 294         if(mMax.x < bc.x + be.x)        return FALSE;
 295         if(mMax.y < bc.y + be.y)        return FALSE;
 296         if(mMax.z < bc.z + be.z)        return FALSE;
 297
 298         return TRUE;
 299 }
 300
 301 #define TEST_BOX_IN_AABB(center, extents)       \
 302         if(AABBContainsBox(center, extents))    \
 303         {                                                                               \
 304                 /* Set contact status */                        \
 305                 mFlags |= OPC_CONTACT;                          \
 306                 _Dump(node);                                            \
 307                 return;                                                         \
 308         }
 309
 310 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 311 /**
 312  *      Recursive collision query for normal AABB trees.
 313  *      \param          node    [in] current collision node
 314  */
 315 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 316 void AABBCollider::_Collide(const AABBCollisionNode* node)
 317 {
 318         // Perform AABB-AABB overlap test
 319         if(!AABBAABBOverlap(node->mAABB.mExtents, node->mAABB.mCenter)) return;
 320
 321         TEST_BOX_IN_AABB(node->mAABB.mCenter, node->mAABB.mExtents)
 322
 323         if(node->IsLeaf())
 324         {
 325                 AABB_PRIM(node->GetPrimitive(), OPC_CONTACT)
 326         }
 327         else
 328         {
 329                 _Collide(node->GetPos());
 330
 331                 if(ContactFound()) return;
 332
 333                 _Collide(node->GetNeg());
 334         }
 335 }
 336
 337 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 338 /**
 339  *      Recursive collision query for normal AABB trees, without primitive tests.
 340  *      \param          node    [in] current collision node
 341  */
 342 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 343 void AABBCollider::_CollideNoPrimitiveTest(const AABBCollisionNode* node)
 344 {
 345         // Perform AABB-AABB overlap test
 346         if(!AABBAABBOverlap(node->mAABB.mExtents, node->mAABB.mCenter)) return;
 347
 348         TEST_BOX_IN_AABB(node->mAABB.mCenter, node->mAABB.mExtents)
 349
 350         if(node->IsLeaf())
 351         {
 352                 SET_CONTACT(node->GetPrimitive(), OPC_CONTACT)
 353         }
 354         else
 355         {
 356                 _CollideNoPrimitiveTest(node->GetPos());
 357
 358                 if(ContactFound()) return;
 359
 360                 _CollideNoPrimitiveTest(node->GetNeg());
 361         }
 362 }
 363
 364 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 365 /**
 366  *      Recursive collision query for quantized AABB trees.
 367  *      \param          node    [in] current collision node
 368  */
 369 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 370 void AABBCollider::_Collide(const AABBQuantizedNode* node)
 371 {
 372         // Dequantize box
 373         const QuantizedAABB& Box = node->mAABB;
 374         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 375         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 376
 377         // Perform AABB-AABB overlap test
 378         if(!AABBAABBOverlap(Extents, Center))   return;
 379
 380         TEST_BOX_IN_AABB(Center, Extents)
 381
 382         if(node->IsLeaf())
 383         {
 384                 AABB_PRIM(node->GetPrimitive(), OPC_CONTACT)
 385         }
 386         else
 387         {
 388                 _Collide(node->GetPos());
 389
 390                 if(ContactFound()) return;
 391
 392                 _Collide(node->GetNeg());
 393         }
 394 }
 395
 396 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 397 /**
 398  *      Recursive collision query for quantized AABB trees, without primitive tests.
 399  *      \param          node    [in] current collision node
 400  */
 401 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 402 void AABBCollider::_CollideNoPrimitiveTest(const AABBQuantizedNode* node)
 403 {
 404         // Dequantize box
 405         const QuantizedAABB& Box = node->mAABB;
 406         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 407         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 408
 409         // Perform AABB-AABB overlap test
 410         if(!AABBAABBOverlap(Extents, Center))   return;
 411
 412         TEST_BOX_IN_AABB(Center, Extents)
 413
 414         if(node->IsLeaf())
 415         {
 416                 SET_CONTACT(node->GetPrimitive(), OPC_CONTACT)
 417         }
 418         else
 419         {
 420                 _CollideNoPrimitiveTest(node->GetPos());
 421
 422                 if(ContactFound()) return;
 423
 424                 _CollideNoPrimitiveTest(node->GetNeg());
 425         }
 426 }
 427
 428 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 429 /**
 430  *      Recursive collision query for no-leaf AABB trees.
 431  *      \param          node    [in] current collision node
 432  */
 433 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 434 void AABBCollider::_Collide(const AABBNoLeafNode* node)
 435 {
 436         // Perform AABB-AABB overlap test
 437         if(!AABBAABBOverlap(node->mAABB.mExtents, node->mAABB.mCenter)) return;
 438
 439         TEST_BOX_IN_AABB(node->mAABB.mCenter, node->mAABB.mExtents)
 440
 441         if(node->HasPosLeaf())  { AABB_PRIM(node->GetPosPrimitive(), OPC_CONTACT) }
 442         else                                    _Collide(node->GetPos());
 443
 444         if(ContactFound()) return;
 445
 446         if(node->HasNegLeaf())  { AABB_PRIM(node->GetNegPrimitive(), OPC_CONTACT) }
 447         else                                    _Collide(node->GetNeg());
 448 }
 449
 450 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 451 /**
 452  *      Recursive collision query for no-leaf AABB trees, without primitive tests.
 453  *      \param          node    [in] current collision node
 454  */
 455 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 456 void AABBCollider::_CollideNoPrimitiveTest(const AABBNoLeafNode* node)
 457 {
 458         // Perform AABB-AABB overlap test
 459         if(!AABBAABBOverlap(node->mAABB.mExtents, node->mAABB.mCenter)) return;
 460
 461         TEST_BOX_IN_AABB(node->mAABB.mCenter, node->mAABB.mExtents)
 462
 463         if(node->HasPosLeaf())  { SET_CONTACT(node->GetPosPrimitive(), OPC_CONTACT) }
 464         else                                    _CollideNoPrimitiveTest(node->GetPos());
 465
 466         if(ContactFound()) return;
 467
 468         if(node->HasNegLeaf())  { SET_CONTACT(node->GetNegPrimitive(), OPC_CONTACT) }
 469         else                                    _CollideNoPrimitiveTest(node->GetNeg());
 470 }
 471
 472 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 473 /**
 474  *      Recursive collision query for quantized no-leaf AABB trees.
 475  *      \param          node    [in] current collision node
 476  */
 477 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 478 void AABBCollider::_Collide(const AABBQuantizedNoLeafNode* node)
 479 {
 480         // Dequantize box
 481         const QuantizedAABB& Box = node->mAABB;
 482         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 483         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 484
 485         // Perform AABB-AABB overlap test
 486         if(!AABBAABBOverlap(Extents, Center))   return;
 487
 488         TEST_BOX_IN_AABB(Center, Extents)
 489
 490         if(node->HasPosLeaf())  { AABB_PRIM(node->GetPosPrimitive(), OPC_CONTACT) }
 491         else                                    _Collide(node->GetPos());
 492
 493         if(ContactFound()) return;
 494
 495         if(node->HasNegLeaf())  { AABB_PRIM(node->GetNegPrimitive(), OPC_CONTACT) }
 496         else                                    _Collide(node->GetNeg());
 497 }
 498
 499 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 500 /**
 501  *      Recursive collision query for quantized no-leaf AABB trees, without primitive tests.
 502  *      \param          node    [in] current collision node
 503  */
 504 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 505 void AABBCollider::_CollideNoPrimitiveTest(const AABBQuantizedNoLeafNode* node)
 506 {
 507         // Dequantize box
 508         const QuantizedAABB& Box = node->mAABB;
 509         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 510         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 511
 512         // Perform AABB-AABB overlap test
 513         if(!AABBAABBOverlap(Extents, Center))   return;
 514
 515         TEST_BOX_IN_AABB(Center, Extents)
 516
 517         if(node->HasPosLeaf())  { SET_CONTACT(node->GetPosPrimitive(), OPC_CONTACT) }
 518         else                                    _CollideNoPrimitiveTest(node->GetPos());
 519
 520         if(ContactFound()) return;
 521
 522         if(node->HasNegLeaf())  { SET_CONTACT(node->GetNegPrimitive(), OPC_CONTACT) }
 523         else                                    _CollideNoPrimitiveTest(node->GetNeg());
 524 }
 525
 526 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 527 /**
 528  *      Recursive collision query for vanilla AABB trees.
 529  *      \param          node    [in] current collision node
 530  */
 531 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 532 void AABBCollider::_Collide(const AABBTreeNode* node)
 533 {
 534         // Perform AABB-AABB overlap test
 535         Point Center, Extents;
 536         node->GetAABB()->GetCenter(Center);
 537         node->GetAABB()->GetExtents(Extents);
 538         if(!AABBAABBOverlap(Center, Extents))   return;
 539
 540         if(node->IsLeaf() || AABBContainsBox(Center, Extents))
 541         {
 542                 mFlags |= OPC_CONTACT;
 543                 mTouchedPrimitives->Add(node->GetPrimitives(), node->GetNbPrimitives());
 544         }
 545         else
 546         {
 547                 _Collide(node->GetPos());
 548                 _Collide(node->GetNeg());
 549         }
 550 }
 551
 552
 553
 554
 555 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 556 /**
 557  *      Constructor.
 558  */
 559 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 560 HybridAABBCollider::HybridAABBCollider()
 561 {
 562 }
 563
 564 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 565 /**
 566  *      Destructor.
 567  */
 568 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 569 HybridAABBCollider::~HybridAABBCollider()
 570 {
 571 }
 572
 573 bool HybridAABBCollider::Collide(AABBCache& cache, const CollisionAABB& box, const HybridModel& model)
 574 {
 575         // We don't want primitive tests here!
 576         mFlags |= OPC_NO_PRIMITIVE_TESTS;
 577
 578         // Checkings
 579         if(!Setup(&model))      return false;
 580
 581         // Init collision query
 582         if(InitQuery(cache, box))       return true;
 583
 584         // Special case for 1-leaf trees
 585         if(mCurrentModel && mCurrentModel->HasSingleNode())
 586         {
 587                 // Here we're supposed to perform a normal query, except our tree has a single node, i.e. just a few triangles
 588                 udword Nb = mIMesh->GetNbTriangles();
 589
 590                 // Loop through all triangles
 591                 for(udword i=0;i<Nb;i++)
 592                 {
 593                         AABB_PRIM(i, OPC_CONTACT)
 594                 }
 595                 return true;
 596         }
 597
 598         // Override destination array since we're only going to get leaf boxes here
 599         mTouchedBoxes.Reset();
 600         mTouchedPrimitives = &mTouchedBoxes;
 601
 602         // Now, do the actual query against leaf boxes
 603         if(!model.HasLeafNodes())
 604         {
 605                 if(model.IsQuantized())
 606                 {
 607                         const AABBQuantizedNoLeafTree* Tree = static_cast<const AABBQuantizedNoLeafTree *>(model.GetTree());
 608
 609                         // Setup dequantization coeffs
 610                         mCenterCoeff    = Tree->mCenterCoeff;
 611                         mExtentsCoeff   = Tree->mExtentsCoeff;
 612
 613                         // Perform collision query - we don't want primitive tests here!
 614                         _CollideNoPrimitiveTest(Tree->GetNodes());
 615                 }
 616                 else
 617                 {
 618                         const AABBNoLeafTree* Tree = static_cast<const AABBNoLeafTree *>(model.GetTree());
 619
 620                         // Perform collision query - we don't want primitive tests here!
 621                         _CollideNoPrimitiveTest(Tree->GetNodes());
 622                 }
 623         }
 624         else
 625         {
 626                 if(model.IsQuantized())
 627                 {
 628                         const AABBQuantizedTree* Tree = static_cast<const AABBQuantizedTree *>(model.GetTree());
 629
 630                         // Setup dequantization coeffs
 631                         mCenterCoeff    = Tree->mCenterCoeff;
 632                         mExtentsCoeff   = Tree->mExtentsCoeff;
 633
 634                         // Perform collision query - we don't want primitive tests here!
 635                         _CollideNoPrimitiveTest(Tree->GetNodes());
 636                 }
 637                 else
 638                 {
 639                         const AABBCollisionTree* Tree = static_cast<const AABBCollisionTree *>(model.GetTree());
 640
 641                         // Perform collision query - we don't want primitive tests here!
 642                         _CollideNoPrimitiveTest(Tree->GetNodes());
 643                 }
 644         }
 645
 646         // We only have a list of boxes so far
 647         if(GetContactStatus())
 648         {
 649                 // Reset contact status, since it currently only reflects collisions with leaf boxes
 650                 Collider::InitQuery();
 651
 652                 // Change dest container so that we can use built-in overlap tests and get collided primitives
 653                 cache.TouchedPrimitives.Reset();
 654                 mTouchedPrimitives = &cache.TouchedPrimitives;
 655
 656                 // Read touched leaf boxes
 657                 udword Nb = mTouchedBoxes.GetNbEntries();
 658                 const udword* Touched = mTouchedBoxes.GetEntries();
 659
 660                 const LeafTriangles* LT = model.GetLeafTriangles();
 661                 const udword* Indices = model.GetIndices();
 662
 663                 // Loop through touched leaves
 664                 while(Nb--)
 665                 {
 666                         const LeafTriangles& CurrentLeaf = LT[*Touched++];
 667
 668                         // Each leaf box has a set of triangles
 669                         udword NbTris = CurrentLeaf.GetNbTriangles();
 670                         if(Indices)
 671                         {
 672                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
 673
 674                                 // Loop through triangles and test each of them
 675                                 while(NbTris--)
 676                                 {
 677                                         udword TriangleIndex = *T++;
 678                                         AABB_PRIM(TriangleIndex, OPC_CONTACT)
 679                                 }
 680                         }
 681                         else
 682                         {
 683                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
 684
 685                                 // Loop through triangles and test each of them
 686                                 while(NbTris--)
 687                                 {
 688                                         udword TriangleIndex = BaseIndex++;
 689                                         AABB_PRIM(TriangleIndex, OPC_CONTACT)
 690                                 }
 691                         }
 692                 }
 693         }
 694
 695         return true;
 696 }