Extras/CDTestFramework/Opcode/OPC_LSSCollider.cpp

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