OPCODE/OPC_PlanesCollider.cpp

   1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   2 /*
   3  *      OPCODE - Optimized Collision Detection
   4  *      Copyright (C) 2001 Pierre Terdiman
   5  *      Homepage: http://www.codercorner.com/Opcode.htm
   6  */
   7 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   8
   9 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  10 /**
  11  *      Contains code for a planes collider.
  12  *      \file           OPC_PlanesCollider.cpp
  13  *      \author         Pierre Terdiman
  14  *      \date           January, 1st, 2002
  15  */
  16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      Contains a Planes-vs-tree collider.
  21  *
  22  *      \class          PlanesCollider
  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_PlanesAABBOverlap.h"
  36 #include "OPC_PlanesTriOverlap.h"
  37
  38 #define SET_CONTACT(prim_index, flag)           \
  39         /* Set contact status */                                \
  40         mFlags |= flag;                                                 \
  41         mTouchedPrimitives->Add(udword(prim_index));
  42
  43 //! Planes-triangle test
  44 #define PLANES_PRIM(prim_index, flag)           \
  45         /* Request vertices from the app */             \
  46         mIMesh->GetTriangle(mVP, prim_index, mVC);      \
  47         /* Perform triangle-box overlap test */ \
  48         if(PlanesTriOverlap(clip_mask))                 \
  49         {                                                                               \
  50                 SET_CONTACT(prim_index, flag)           \
  51         }
  52
  53 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  54 /**
  55  *      Constructor.
  56  */
  57 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  58 PlanesCollider::PlanesCollider() :
  59         mNbPlanes       (0),
  60         mPlanes         (null)
  61 {
  62 }
  63
  64 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  65 /**
  66  *      Destructor.
  67  */
  68 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  69 PlanesCollider::~PlanesCollider()
  70 {
  71         DELETEARRAY(mPlanes);
  72 }
  73
  74 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  75 /**
  76  *      Validates current settings. You should call this method after all the settings and callbacks have been defined.
  77  *      \return         null if everything is ok, else a string describing the problem
  78  */
  79 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  80 const char* PlanesCollider::ValidateSettings()
  81 {
  82         if(TemporalCoherenceEnabled() && !FirstContactEnabled())        return "Temporal coherence only works with ""First contact"" mode!";
  83
  84         return VolumeCollider::ValidateSettings();
  85 }
  86
  87 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  88 /**
  89  *      Generic collision query for generic OPCODE models. After the call, access the results:
  90  *      - with GetContactStatus()
  91  *      - with GetNbTouchedPrimitives()
  92  *      - with GetTouchedPrimitives()
  93  *
  94  *      \param          cache           [in/out] a planes cache
  95  *      \param          planes          [in] list of planes in world space
  96  *      \param          nb_planes       [in] number of planes
  97  *      \param          model           [in] Opcode model to collide with
  98  *      \param          worldm          [in] model's world matrix, or null
  99  *      \return         true if success
 100  *      \warning        SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only.
 101  */
 102 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 103 bool PlanesCollider::Collide(PlanesCache& cache, const Plane* planes, udword nb_planes, const Model& model, const Matrix4x4* worldm)
 104 {
 105         // Checkings
 106         if(!Setup(&model))      return false;
 107
 108         // Init collision query
 109         if(InitQuery(cache, planes, nb_planes, worldm)) return true;
 110
 111         udword PlaneMask = (1<<nb_planes)-1;
 112
 113         if(!model.HasLeafNodes())
 114         {
 115                 if(model.IsQuantized())
 116                 {
 117                         const AABBQuantizedNoLeafTree* Tree = static_cast<const AABBQuantizedNoLeafTree *>(model.GetTree());
 118
 119                         // Setup dequantization coeffs
 120                         mCenterCoeff    = Tree->mCenterCoeff;
 121                         mExtentsCoeff   = Tree->mExtentsCoeff;
 122
 123                         // Perform collision query
 124                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 125                         else                                            _Collide(Tree->GetNodes(), PlaneMask);
 126                 }
 127                 else
 128                 {
 129                         const AABBNoLeafTree* Tree = static_cast<const AABBNoLeafTree *>(model.GetTree());
 130
 131                         // Perform collision query
 132                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 133                         else                                            _Collide(Tree->GetNodes(), PlaneMask);
 134                 }
 135         }
 136         else
 137         {
 138                 if(model.IsQuantized())
 139                 {
 140                         const AABBQuantizedTree* Tree = static_cast<const AABBQuantizedTree *>(model.GetTree());
 141
 142                         // Setup dequantization coeffs
 143                         mCenterCoeff    = Tree->mCenterCoeff;
 144                         mExtentsCoeff   = Tree->mExtentsCoeff;
 145
 146                         // Perform collision query
 147                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 148                         else                                            _Collide(Tree->GetNodes(), PlaneMask);
 149                 }
 150                 else
 151                 {
 152                         const AABBCollisionTree* Tree = static_cast<const AABBCollisionTree *>(model.GetTree());
 153
 154                         // Perform collision query
 155                         if(SkipPrimitiveTests())        _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 156                         else                                            _Collide(Tree->GetNodes(), PlaneMask);
 157                 }
 158         }
 159         return true;
 160 }
 161
 162 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 163 /**
 164  *      Initializes a collision query :
 165  *      - reset stats & contact status
 166  *      - compute planes in model space
 167  *      - check temporal coherence
 168  *
 169  *      \param          cache           [in/out] a planes cache
 170  *      \param          planes          [in] list of planes
 171  *      \param          nb_planes       [in] number of planes
 172  *      \param          worldm          [in] model's world matrix, or null
 173  *      \return         TRUE if we can return immediately
 174  *      \warning        SCALE NOT SUPPORTED. The matrix must contain rotation & translation parts only.
 175  */
 176 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 177 BOOL PlanesCollider::InitQuery(PlanesCache& cache, const Plane* planes, udword nb_planes, const Matrix4x4* worldm)
 178 {
 179         // 1) Call the base method
 180         VolumeCollider::InitQuery();
 181
 182         // 2) Compute planes in model space
 183         if(nb_planes>mNbPlanes)
 184         {
 185                 DELETEARRAY(mPlanes);
 186                 mPlanes = new Plane[nb_planes];
 187         }
 188         mNbPlanes = nb_planes;
 189
 190         if(worldm)
 191         {
 192                 Matrix4x4 InvWorldM;
 193                 InvertPRMatrix(InvWorldM, *worldm);
 194
 195 //              for(udword i=0;i<nb_planes;i++) mPlanes[i] = planes[i] * InvWorldM;
 196                 for(udword i=0;i<nb_planes;i++) TransformPlane(mPlanes[i], planes[i], InvWorldM);
 197         }
 198         else CopyMemory(mPlanes, planes, nb_planes*sizeof(Plane));
 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 planes (and set contact status if needed)
 212                         udword clip_mask = (1<<mNbPlanes)-1;
 213                         PLANES_PRIM(udword(0), OPC_CONTACT)
 214
 215                         // Return immediately regardless of status
 216                         return TRUE;
 217                 }
 218         }
 219
 220         // 4) Check temporal coherence:
 221         if(TemporalCoherenceEnabled())
 222         {
 223                 // Here we use temporal coherence
 224                 // => check results from previous frame before performing the collision query
 225                 if(FirstContactEnabled())
 226                 {
 227                         // We're only interested in the first contact found => test the unique previously touched face
 228                         if(mTouchedPrimitives->GetNbEntries())
 229                         {
 230                                 // Get index of previously touched face = the first entry in the array
 231                                 udword PreviouslyTouchedFace = mTouchedPrimitives->GetEntry(0);
 232
 233                                 // Then reset the array:
 234                                 // - if the overlap test below is successful, the index we'll get added back anyway
 235                                 // - if it isn't, then the array should be reset anyway for the normal query
 236                                 mTouchedPrimitives->Reset();
 237
 238                                 // Perform overlap test between the cached triangle and the planes (and set contact status if needed)
 239                                 udword clip_mask = (1<<mNbPlanes)-1;
 240                                 PLANES_PRIM(PreviouslyTouchedFace, OPC_TEMPORAL_CONTACT)
 241
 242                                 // Return immediately if possible
 243                                 if(GetContactStatus())  return TRUE;
 244                         }
 245                         // else no face has been touched during previous query
 246                         // => we'll have to perform a normal query
 247                 }
 248                 else mTouchedPrimitives->Reset();
 249         }
 250         else
 251         {
 252                 // Here we don't use temporal coherence => do a normal query
 253                 mTouchedPrimitives->Reset();
 254         }
 255
 256         return FALSE;
 257 }
 258
 259 #define TEST_CLIP_MASK                                                                                                                                                                  \
 260         /* If the box is completely included, so are its children. We don't need to do extra tests, we */       \
 261         /* can immediately output a list of visible children. Those ones won't need to be clipped. */           \
 262         if(!OutClipMask)                                                                                                                                                                        \
 263         {                                                                                                                                                                                                       \
 264                 /* Set contact status */                                                                                                                                                \
 265                 mFlags |= OPC_CONTACT;                                                                                                                                                  \
 266                 _Dump(node);                                                                                                                                                                    \
 267                 return;                                                                                                                                                                                 \
 268         }
 269
 270 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 271 /**
 272  *      Recursive collision query for normal AABB trees.
 273  *      \param          node    [in] current collision node
 274  */
 275 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 276 void PlanesCollider::_Collide(const AABBCollisionNode* node, udword clip_mask)
 277 {
 278         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 279         udword OutClipMask;
 280         if(!PlanesAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents, OutClipMask, clip_mask))       return;
 281
 282         TEST_CLIP_MASK
 283
 284         // Else the box straddles one or several planes, so we need to recurse down the tree.
 285         if(node->IsLeaf())
 286         {
 287                 PLANES_PRIM(node->GetPrimitive(), OPC_CONTACT)
 288         }
 289         else
 290         {
 291                 _Collide(node->GetPos(), OutClipMask);
 292
 293                 if(ContactFound()) return;
 294
 295                 _Collide(node->GetNeg(), OutClipMask);
 296         }
 297 }
 298
 299 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 300 /**
 301  *      Recursive collision query for normal AABB trees.
 302  *      \param          node    [in] current collision node
 303  */
 304 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 305 void PlanesCollider::_CollideNoPrimitiveTest(const AABBCollisionNode* node, udword clip_mask)
 306 {
 307         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 308         udword OutClipMask;
 309         if(!PlanesAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents, OutClipMask, clip_mask))       return;
 310
 311         TEST_CLIP_MASK
 312
 313         // Else the box straddles one or several planes, so we need to recurse down the tree.
 314         if(node->IsLeaf())
 315         {
 316                 SET_CONTACT(node->GetPrimitive(), OPC_CONTACT)
 317         }
 318         else
 319         {
 320                 _CollideNoPrimitiveTest(node->GetPos(), OutClipMask);
 321
 322                 if(ContactFound()) return;
 323
 324                 _CollideNoPrimitiveTest(node->GetNeg(), OutClipMask);
 325         }
 326 }
 327
 328 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 329 /**
 330  *      Recursive collision query for quantized AABB trees.
 331  *      \param          node    [in] current collision node
 332  */
 333 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 334 void PlanesCollider::_Collide(const AABBQuantizedNode* node, udword clip_mask)
 335 {
 336         // Dequantize box
 337         const QuantizedAABB& Box = node->mAABB;
 338         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 339         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 340
 341         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 342         udword OutClipMask;
 343         if(!PlanesAABBOverlap(Center, Extents, OutClipMask, clip_mask)) return;
 344
 345         TEST_CLIP_MASK
 346
 347         // Else the box straddles one or several planes, so we need to recurse down the tree.
 348         if(node->IsLeaf())
 349         {
 350                 PLANES_PRIM(node->GetPrimitive(), OPC_CONTACT)
 351         }
 352         else
 353         {
 354                 _Collide(node->GetPos(), OutClipMask);
 355
 356                 if(ContactFound()) return;
 357
 358                 _Collide(node->GetNeg(), OutClipMask);
 359         }
 360 }
 361
 362 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 363 /**
 364  *      Recursive collision query for quantized AABB trees.
 365  *      \param          node    [in] current collision node
 366  */
 367 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 368 void PlanesCollider::_CollideNoPrimitiveTest(const AABBQuantizedNode* node, udword clip_mask)
 369 {
 370         // Dequantize box
 371         const QuantizedAABB& Box = node->mAABB;
 372         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 373         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 374
 375         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 376         udword OutClipMask;
 377         if(!PlanesAABBOverlap(Center, Extents, OutClipMask, clip_mask)) return;
 378
 379         TEST_CLIP_MASK
 380
 381         // Else the box straddles one or several planes, so we need to recurse down the tree.
 382         if(node->IsLeaf())
 383         {
 384                 SET_CONTACT(node->GetPrimitive(), OPC_CONTACT)
 385         }
 386         else
 387         {
 388                 _CollideNoPrimitiveTest(node->GetPos(), OutClipMask);
 389
 390                 if(ContactFound()) return;
 391
 392                 _CollideNoPrimitiveTest(node->GetNeg(), OutClipMask);
 393         }
 394 }
 395
 396 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 397 /**
 398  *      Recursive collision query for no-leaf AABB trees.
 399  *      \param          node    [in] current collision node
 400  */
 401 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 402 void PlanesCollider::_Collide(const AABBNoLeafNode* node, udword clip_mask)
 403 {
 404         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 405         udword OutClipMask;
 406         if(!PlanesAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents, OutClipMask, clip_mask))       return;
 407
 408         TEST_CLIP_MASK
 409
 410         // Else the box straddles one or several planes, so we need to recurse down the tree.
 411         if(node->HasPosLeaf())  { PLANES_PRIM(node->GetPosPrimitive(), OPC_CONTACT) }
 412         else                                    _Collide(node->GetPos(), OutClipMask);
 413
 414         if(ContactFound()) return;
 415
 416         if(node->HasNegLeaf())  { PLANES_PRIM(node->GetNegPrimitive(), OPC_CONTACT) }
 417         else                                    _Collide(node->GetNeg(), OutClipMask);
 418 }
 419
 420 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 421 /**
 422  *      Recursive collision query for no-leaf AABB trees.
 423  *      \param          node    [in] current collision node
 424  */
 425 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 426 void PlanesCollider::_CollideNoPrimitiveTest(const AABBNoLeafNode* node, udword clip_mask)
 427 {
 428         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 429         udword OutClipMask;
 430         if(!PlanesAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents, OutClipMask, clip_mask))       return;
 431
 432         TEST_CLIP_MASK
 433
 434         // Else the box straddles one or several planes, so we need to recurse down the tree.
 435         if(node->HasPosLeaf())  { SET_CONTACT(node->GetPosPrimitive(), OPC_CONTACT) }
 436         else                                    _CollideNoPrimitiveTest(node->GetPos(), OutClipMask);
 437
 438         if(ContactFound()) return;
 439
 440         if(node->HasNegLeaf())  { SET_CONTACT(node->GetNegPrimitive(), OPC_CONTACT) }
 441         else                                    _CollideNoPrimitiveTest(node->GetNeg(), OutClipMask);
 442 }
 443
 444 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 445 /**
 446  *      Recursive collision query for quantized no-leaf AABB trees.
 447  *      \param          node    [in] current collision node
 448  */
 449 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 450 void PlanesCollider::_Collide(const AABBQuantizedNoLeafNode* node, udword clip_mask)
 451 {
 452         // Dequantize box
 453         const QuantizedAABB& Box = node->mAABB;
 454         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 455         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 456
 457         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 458         udword OutClipMask;
 459         if(!PlanesAABBOverlap(Center, Extents, OutClipMask, clip_mask)) return;
 460
 461         TEST_CLIP_MASK
 462
 463         // Else the box straddles one or several planes, so we need to recurse down the tree.
 464         if(node->HasPosLeaf())  { PLANES_PRIM(node->GetPosPrimitive(), OPC_CONTACT) }
 465         else                                    _Collide(node->GetPos(), OutClipMask);
 466
 467         if(ContactFound()) return;
 468
 469         if(node->HasNegLeaf())  { PLANES_PRIM(node->GetNegPrimitive(), OPC_CONTACT) }
 470         else                                    _Collide(node->GetNeg(), OutClipMask);
 471 }
 472
 473 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 474 /**
 475  *      Recursive collision query for quantized no-leaf AABB trees.
 476  *      \param          node    [in] current collision node
 477  */
 478 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 479 void PlanesCollider::_CollideNoPrimitiveTest(const AABBQuantizedNoLeafNode* node, udword clip_mask)
 480 {
 481         // Dequantize box
 482         const QuantizedAABB& Box = node->mAABB;
 483         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 484         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 485
 486         // Test the box against the planes. If the box is completely culled, so are its children, hence we exit.
 487         udword OutClipMask;
 488         if(!PlanesAABBOverlap(Center, Extents, OutClipMask, clip_mask)) return;
 489
 490         TEST_CLIP_MASK
 491
 492         // Else the box straddles one or several planes, so we need to recurse down the tree.
 493         if(node->HasPosLeaf())  { SET_CONTACT(node->GetPosPrimitive(), OPC_CONTACT) }
 494         else                                    _CollideNoPrimitiveTest(node->GetPos(), OutClipMask);
 495
 496         if(ContactFound()) return;
 497
 498         if(node->HasNegLeaf())  { SET_CONTACT(node->GetNegPrimitive(), OPC_CONTACT) }
 499         else                                    _CollideNoPrimitiveTest(node->GetNeg(), OutClipMask);
 500 }
 501
 502
 503
 504
 505
 506
 507
 508 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 509 /**
 510  *      Constructor.
 511  */
 512 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 513 HybridPlanesCollider::HybridPlanesCollider()
 514 {
 515 }
 516
 517 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 518 /**
 519  *      Destructor.
 520  */
 521 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 522 HybridPlanesCollider::~HybridPlanesCollider()
 523 {
 524 }
 525
 526 bool HybridPlanesCollider::Collide(PlanesCache& cache, const Plane* planes, udword nb_planes, const HybridModel& model, const Matrix4x4* worldm)
 527 {
 528         // We don't want primitive tests here!
 529         mFlags |= OPC_NO_PRIMITIVE_TESTS;
 530
 531         // Checkings
 532         if(!Setup(&model))      return false;
 533
 534         // Init collision query
 535         if(InitQuery(cache, planes, nb_planes, worldm)) return true;
 536
 537         // Special case for 1-leaf trees
 538         if(mCurrentModel && mCurrentModel->HasSingleNode())
 539         {
 540                 // Here we're supposed to perform a normal query, except our tree has a single node, i.e. just a few triangles
 541                 udword Nb = mIMesh->GetNbTriangles();
 542
 543                 // Loop through all triangles
 544                 udword clip_mask = (1<<mNbPlanes)-1;
 545                 for(udword i=0;i<Nb;i++)
 546                 {
 547                         PLANES_PRIM(i, OPC_CONTACT)
 548                 }
 549                 return true;
 550         }
 551
 552         // Override destination array since we're only going to get leaf boxes here
 553         mTouchedBoxes.Reset();
 554         mTouchedPrimitives = &mTouchedBoxes;
 555
 556         udword PlaneMask = (1<<nb_planes)-1;
 557
 558         // Now, do the actual query against leaf boxes
 559         if(!model.HasLeafNodes())
 560         {
 561                 if(model.IsQuantized())
 562                 {
 563                         const AABBQuantizedNoLeafTree* Tree = static_cast<const AABBQuantizedNoLeafTree *>(model.GetTree());
 564
 565                         // Setup dequantization coeffs
 566                         mCenterCoeff    = Tree->mCenterCoeff;
 567                         mExtentsCoeff   = Tree->mExtentsCoeff;
 568
 569                         // Perform collision query - we don't want primitive tests here!
 570                         _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 571                 }
 572                 else
 573                 {
 574                         const AABBNoLeafTree* Tree = static_cast<const AABBNoLeafTree *>(model.GetTree());
 575
 576                         // Perform collision query - we don't want primitive tests here!
 577                         _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 578                 }
 579         }
 580         else
 581         {
 582                 if(model.IsQuantized())
 583                 {
 584                         const AABBQuantizedTree* Tree = static_cast<const AABBQuantizedTree *>(model.GetTree());
 585
 586                         // Setup dequantization coeffs
 587                         mCenterCoeff    = Tree->mCenterCoeff;
 588                         mExtentsCoeff   = Tree->mExtentsCoeff;
 589
 590                         // Perform collision query - we don't want primitive tests here!
 591                         _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 592                 }
 593                 else
 594                 {
 595                         const AABBCollisionTree* Tree = static_cast<const AABBCollisionTree *>(model.GetTree());
 596
 597                         // Perform collision query - we don't want primitive tests here!
 598                         _CollideNoPrimitiveTest(Tree->GetNodes(), PlaneMask);
 599                 }
 600         }
 601
 602         // We only have a list of boxes so far
 603         if(GetContactStatus())
 604         {
 605                 // Reset contact status, since it currently only reflects collisions with leaf boxes
 606                 Collider::InitQuery();
 607
 608                 // Change dest container so that we can use built-in overlap tests and get collided primitives
 609                 cache.TouchedPrimitives.Reset();
 610                 mTouchedPrimitives = &cache.TouchedPrimitives;
 611
 612                 // Read touched leaf boxes
 613                 udword Nb = mTouchedBoxes.GetNbEntries();
 614                 const udword* Touched = mTouchedBoxes.GetEntries();
 615
 616                 const LeafTriangles* LT = model.GetLeafTriangles();
 617                 const udword* Indices = model.GetIndices();
 618
 619                 // Loop through touched leaves
 620                 udword clip_mask = (1<<mNbPlanes)-1;
 621                 while(Nb--)
 622                 {
 623                         const LeafTriangles& CurrentLeaf = LT[*Touched++];
 624
 625                         // Each leaf box has a set of triangles
 626                         udword NbTris = CurrentLeaf.GetNbTriangles();
 627                         if(Indices)
 628                         {
 629                                 const udword* T = &Indices[CurrentLeaf.GetTriangleIndex()];
 630
 631                                 // Loop through triangles and test each of them
 632                                 while(NbTris--)
 633                                 {
 634                                         udword TriangleIndex = *T++;
 635                                         PLANES_PRIM(TriangleIndex, OPC_CONTACT)
 636                                 }
 637                         }
 638                         else
 639                         {
 640                                 udword BaseIndex = CurrentLeaf.GetTriangleIndex();
 641
 642                                 // Loop through triangles and test each of them
 643                                 while(NbTris--)
 644                                 {
 645                                         udword TriangleIndex = BaseIndex++;
 646                                         PLANES_PRIM(TriangleIndex, OPC_CONTACT)
 647                                 }
 648                         }
 649                 }
 650         }
 651
 652         return true;
 653 }