OPCODE/OPC_RayCollider.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 ray collider.
  12  *      \file           OPC_RayCollider.cpp
  13  *      \author         Pierre Terdiman
  14  *      \date           June, 2, 2001
  15  */
  16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      Contains a ray-vs-tree collider.
  21  *      This class performs a stabbing query on an AABB tree, i.e. does a ray-mesh collision.
  22  *
  23  *      HIGHER DISTANCE BOUND:
  24  *
  25  *              If P0 and P1 are two 3D points, let's define:
  26  *              - d = distance between P0 and P1
  27  *              - Origin        = P0
  28  *              - Direction     = (P1 - P0) / d = normalized direction vector
  29  *              - A parameter t such as a point P on the line (P0,P1) is P = Origin + t * Direction
  30  *              - t = 0  -->  P = P0
  31  *              - t = d  -->  P = P1
  32  *
  33  *              Then we can define a general "ray" as:
  34  *
  35  *                      struct Ray
  36  *                      {
  37  *                              Point   Origin;
  38  *                              Point   Direction;
  39  *                      };
  40  *
  41  *              But it actually maps three different things:
  42  *              - a segment,   when 0 <= t <= d
  43  *              - a half-line, when 0 <= t < +infinity, or -infinity < t <= d
  44  *              - a line,      when -infinity < t < +infinity
  45  *
  46  *              In Opcode, we support segment queries, which yield half-line queries by setting d = +infinity.
  47  *              We don't support line-queries. If you need them, shift the origin along the ray by an appropriate margin.
  48  *
  49  *              In short, the lower bound is always 0, and you can setup the higher bound "d" with RayCollider::SetMaxDist().
  50  *
  51  *              Query   |segment                        |half-line              |line
  52  *              --------|-------------------|---------------|----------------
  53  *              Usages  |-shadow feelers        |-raytracing    |-
  54  *                              |-sweep tests           |-in/out tests  |
  55  *
  56  *      FIRST CONTACT:
  57  *
  58  *              - You can setup "first contact" mode or "all contacts" mode with RayCollider::SetFirstContact().
  59  *              - In "first contact" mode we return as soon as the ray hits one face. If can be useful e.g. for shadow feelers, where
  60  *              you want to know whether the path to the light is free or not (a boolean answer is enough).
  61  *              - In "all contacts" mode we return all faces hit by the ray.
  62  *
  63  *      TEMPORAL COHERENCE:
  64  *
  65  *              - You can enable or disable temporal coherence with RayCollider::SetTemporalCoherence().
  66  *              - It currently only works in "first contact" mode.
  67  *              - If temporal coherence is enabled, the previously hit triangle is cached during the first query. Then, next queries
  68  *              start by colliding the ray against the cached triangle. If they still collide, we return immediately.
  69  *
  70  *      CLOSEST HIT:
  71  *
  72  *              - You can enable or disable "closest hit" with RayCollider::SetClosestHit().
  73  *              - It currently only works in "all contacts" mode.
  74  *              - If closest hit is enabled, faces are sorted by distance on-the-fly and the closest one only is reported.
  75  *
  76  *      BACKFACE CULLING:
  77  *
  78  *              - You can enable or disable backface culling with RayCollider::SetCulling().
  79  *              - If culling is enabled, ray will not hit back faces (only front faces).
  80  *
  81  *
  82  *
  83  *      \class          RayCollider
  84  *      \author         Pierre Terdiman
  85  *      \version        1.3
  86  *      \date           June, 2, 2001
  87 */
  88 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  89
  90 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  91 /**
  92  *      This class describes a face hit by a ray or segment.
  93  *      This is a particular class dedicated to stabbing queries.
  94  *
  95  *      \class          CollisionFace
  96  *      \author         Pierre Terdiman
  97  *      \version        1.3
  98  *      \date           March, 20, 2001
  99 */
 100 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 101
 102 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 103 /**
 104  *      This class is a dedicated collection of CollisionFace.
 105  *
 106  *      \class          CollisionFaces
 107  *      \author         Pierre Terdiman
 108  *      \version        1.3
 109  *      \date           March, 20, 2001
 110 */
 111 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 112
 113 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 114 // Precompiled Header
 115 #include "Stdafx.h"
 116
 117 using namespace Opcode;
 118
 119 #include "OPC_RayAABBOverlap.h"
 120 #include "OPC_RayTriOverlap.h"
 121
 122 #define SET_CONTACT(prim_index, flag)                                                                                   \
 123         mNbIntersections++;                                                                                                                     \
 124         /* Set contact status */                                                                                                        \
 125         mFlags |= flag;                                                                                                                         \
 126         /* In any case the contact has been found and recorded in mStabbedFace  */      \
 127         mStabbedFace.mFaceID = prim_index;
 128
 129 #ifdef OPC_RAYHIT_CALLBACK
 130
 131         #define HANDLE_CONTACT(prim_index, flag)                                                                                                        \
 132                 SET_CONTACT(prim_index, flag)                                                                                                                   \
 133                                                                                                                                                                                                 \
 134                 if(mHitCallback)        (mHitCallback)(mStabbedFace, mUserData);
 135
 136         #define UPDATE_CACHE                                    \
 137                 if(cache && GetContactStatus())         \
 138                 {                                                                       \
 139                         *cache  = mStabbedFace.mFaceID; \
 140                 }
 141 #else
 142
 143         #define HANDLE_CONTACT(prim_index, flag)                                                                                                        \
 144                 SET_CONTACT(prim_index, flag)                                                                                                                   \
 145                                                                                                                                                                                                 \
 146                 /* Now we can also record it in mStabbedFaces if available */                                                   \
 147                 if(mStabbedFaces)                                                                                                                                               \
 148                 {                                                                                                                                                                               \
 149                         /* If we want all faces or if that's the first one we hit */                                            \
 150                         if(!mClosestHit || !mStabbedFaces->GetNbFaces())                                                                        \
 151                         {                                                                                                                                                                       \
 152                                 mStabbedFaces->AddFace(mStabbedFace);                                                                                   \
 153                         }                                                                                                                                                                       \
 154                         else                                                                                                                                                            \
 155                         {                                                                                                                                                                       \
 156                                 /* We only keep closest hit */                                                                                                  \
 157                                 CollisionFace* Current = const_cast<CollisionFace*>(mStabbedFaces->GetFaces()); \
 158                                 if(Current && mStabbedFace.mDistance<Current->mDistance)                                                \
 159                                 {                                                                                                                                                               \
 160                                         *Current = mStabbedFace;                                                                                                        \
 161                                 }                                                                                                                                                               \
 162                         }                                                                                                                                                                       \
 163                 }
 164
 165         #define UPDATE_CACHE                                                                                            \
 166                 if(cache && GetContactStatus() && mStabbedFaces)                                \
 167                 {                                                                                                                               \
 168                         const CollisionFace* Current = mStabbedFaces->GetFaces();       \
 169                         if(Current)     *cache  = Current->mFaceID;                                             \
 170                         else            *cache  = INVALID_ID;                                                   \
 171                 }
 172 #endif
 173
 174 #define SEGMENT_PRIM(prim_index, flag)                                                                                                          \
 175         /* Request vertices from the app */                                                                                                             \
 176         VertexPointers VP;      ConversionArea VC;      mIMesh->GetTriangle(VP, prim_index, VC);                \
 177                                                                                                                                                                                         \
 178         /* Perform ray-tri overlap test and return */                                                                                   \
 179         if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2]))                                                  \
 180         {                                                                                                                                                                               \
 181                 /* Intersection point is valid if dist < segment's length */                                            \
 182                 /* We know dist>0 so we can use integers */                                                                                     \
 183                 if(IR(mStabbedFace.mDistance)<IR(mMaxDist))                                                                                     \
 184                 {                                                                                                                                                                       \
 185                         HANDLE_CONTACT(prim_index, flag)                                                                                                \
 186                 }                                                                                                                                                                       \
 187         }
 188
 189 #define RAY_PRIM(prim_index, flag)                                                                                                                      \
 190         /* Request vertices from the app */                                                                                                             \
 191         VertexPointers VP;      ConversionArea VC;      mIMesh->GetTriangle(VP, prim_index, VC);                \
 192                                                                                                                                                                                         \
 193         /* Perform ray-tri overlap test and return */                                                                                   \
 194         if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2]))                                                  \
 195         {                                                                                                                                                                               \
 196                 HANDLE_CONTACT(prim_index, flag)                                                                                                        \
 197         }
 198
 199
 200 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 201 /**
 202  *      Constructor.
 203  */
 204 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 205 RayCollider::RayCollider() :
 206 #ifdef OPC_RAYHIT_CALLBACK
 207         mHitCallback            (null),
 208         mUserData                       (0),
 209 #else
 210         mStabbedFaces           (null),
 211         mClosestHit                     (false),
 212 #endif
 213         mNbRayBVTests           (0),
 214         mNbRayPrimTests         (0),
 215         mNbIntersections        (0),
 216         mMaxDist                        (MAX_FLOAT),
 217         mCulling                        (true)
 218
 219 {
 220 }
 221
 222 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 223 /**
 224  *      Destructor.
 225  */
 226 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 227 RayCollider::~RayCollider()
 228 {
 229 }
 230
 231 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 232 /**
 233  *      Validates current settings. You should call this method after all the settings and callbacks have been defined.
 234  *      \return         null if everything is ok, else a string describing the problem
 235  */
 236 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 237 const char* RayCollider::ValidateSettings()
 238 {
 239         if(mMaxDist<0.0f)                                                                                       return "Higher distance bound must be positive!";
 240         if(TemporalCoherenceEnabled() && !FirstContactEnabled())        return "Temporal coherence only works with ""First contact"" mode!";
 241 #ifndef OPC_RAYHIT_CALLBACK
 242         if(mClosestHit && FirstContactEnabled())                                        return "Closest hit doesn't work with ""First contact"" mode!";
 243         if(TemporalCoherenceEnabled() && mClosestHit)                           return "Temporal coherence can't guarantee to report closest hit!";
 244 #endif
 245         if(SkipPrimitiveTests())                                                                        return "SkipPrimitiveTests not possible for RayCollider ! (not implemented)";
 246         return null;
 247 }
 248
 249 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 250 /**
 251  *      Generic stabbing query for generic OPCODE models. After the call, access the results:
 252  *      - with GetContactStatus()
 253  *      - in the user-provided destination array
 254  *
 255  *      \param          world_ray               [in] stabbing ray in world space
 256  *      \param          model                   [in] Opcode model to collide with
 257  *      \param          world                   [in] model's world matrix, or null
 258  *      \param          cache                   [in] a possibly cached face index, or null
 259  *      \return         true if success
 260  *      \warning        SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only.
 261  */
 262 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 263 bool RayCollider::Collide(const Ray& world_ray, const Model& model, const Matrix4x4* world, udword* cache)
 264 {
 265         // Checkings
 266         if(!Setup(&model))      return false;
 267
 268         // Init collision query
 269         if(InitQuery(world_ray, world, cache))  return true;
 270
 271         if(!model.HasLeafNodes())
 272         {
 273                 if(model.IsQuantized())
 274                 {
 275                         const AABBQuantizedNoLeafTree* Tree = static_cast<const AABBQuantizedNoLeafTree *>(model.GetTree());
 276
 277                         // Setup dequantization coeffs
 278                         mCenterCoeff    = Tree->mCenterCoeff;
 279                         mExtentsCoeff   = Tree->mExtentsCoeff;
 280
 281                         // Perform stabbing query
 282                         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)        _SegmentStab(Tree->GetNodes());
 283                         else                                                            _RayStab(Tree->GetNodes());
 284                 }
 285                 else
 286                 {
 287                         const AABBNoLeafTree* Tree = static_cast<const AABBNoLeafTree *>(model.GetTree());
 288
 289                         // Perform stabbing query
 290                         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)        _SegmentStab(Tree->GetNodes());
 291                         else                                                            _RayStab(Tree->GetNodes());
 292                 }
 293         }
 294         else
 295         {
 296                 if(model.IsQuantized())
 297                 {
 298                         const AABBQuantizedTree* Tree = static_cast<const AABBQuantizedTree *>(model.GetTree());
 299
 300                         // Setup dequantization coeffs
 301                         mCenterCoeff    = Tree->mCenterCoeff;
 302                         mExtentsCoeff   = Tree->mExtentsCoeff;
 303
 304                         // Perform stabbing query
 305                         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)        _SegmentStab(Tree->GetNodes());
 306                         else                                                            _RayStab(Tree->GetNodes());
 307                 }
 308                 else
 309                 {
 310                         const AABBCollisionTree* Tree = static_cast<const AABBCollisionTree *>(model.GetTree());
 311
 312                         // Perform stabbing query
 313                         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)        _SegmentStab(Tree->GetNodes());
 314                         else                                                            _RayStab(Tree->GetNodes());
 315                 }
 316         }
 317
 318         // Update cache if needed
 319         UPDATE_CACHE;
 320         return true;
 321 }
 322
 323
 324 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 325 /**
 326  *      Initializes a stabbing query :
 327  *      - reset stats & contact status
 328  *      - compute ray in local space
 329  *      - check temporal coherence
 330  *
 331  *      \param          world_ray       [in] stabbing ray in world space
 332  *      \param          world           [in] object's world matrix, or null
 333  *      \param          face_id         [in] index of previously stabbed triangle
 334  *      \return         TRUE if we can return immediately
 335  *      \warning        SCALE NOT SUPPORTED. The matrix must contain rotation & translation parts only.
 336  */
 337 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 338 BOOL RayCollider::InitQuery(const Ray& world_ray, const Matrix4x4* world, udword* face_id)
 339 {
 340         // Reset stats & contact status
 341         Collider::InitQuery();
 342         mNbRayBVTests           = 0;
 343         mNbRayPrimTests         = 0;
 344         mNbIntersections        = 0;
 345 #ifndef OPC_RAYHIT_CALLBACK
 346         if(mStabbedFaces)       mStabbedFaces->Reset();
 347 #endif
 348
 349         // Compute ray in local space
 350         // The (Origin/Dir) form is needed for the ray-triangle test anyway (even for segment tests)
 351         if(world)
 352         {
 353                 Matrix3x3 InvWorld = *world;
 354                 mDir = InvWorld * world_ray.mDir;
 355
 356                 Matrix4x4 World;
 357                 InvertPRMatrix(World, *world);
 358                 mOrigin = world_ray.mOrig * World;
 359         }
 360         else
 361         {
 362                 mDir    = world_ray.mDir;
 363                 mOrigin = world_ray.mOrig;
 364         }
 365
 366         // 4) Special case: 1-triangle meshes [Opcode 1.3]
 367         if(mCurrentModel && mCurrentModel->HasSingleNode())
 368         {
 369                 // We simply perform the BV-Prim overlap test each time. We assume single triangle has index 0.
 370                 if(!SkipPrimitiveTests())
 371                 {
 372                         // Perform overlap test between the unique triangle and the ray (and set contact status if needed)
 373                         SEGMENT_PRIM(udword(0), OPC_CONTACT)
 374
 375                         // Return immediately regardless of status
 376                         return TRUE;
 377                 }
 378         }
 379
 380         // Check temporal coherence :
 381
 382         // Test previously colliding primitives first
 383         if(TemporalCoherenceEnabled() && FirstContactEnabled() && face_id && *face_id!=INVALID_ID)
 384         {
 385 #ifdef OLD_CODE
 386 #ifndef OPC_RAYHIT_CALLBACK
 387                 if(!mClosestHit)
 388 #endif
 389                 {
 390                         // Request vertices from the app
 391                         VertexPointers VP;
 392                         ConversionArea VC;
 393                         mIMesh->GetTriangle(VP, *face_id, VC);
 394                         // Perform ray-cached tri overlap test
 395                         if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2]))
 396                         {
 397                                 // Intersection point is valid if:
 398                                 // - distance is positive (else it can just be a face behind the orig point)
 399                                 // - distance is smaller than a given max distance (useful for shadow feelers)
 400 //                              if(mStabbedFace.mDistance>0.0f && mStabbedFace.mDistance<mMaxDist)
 401                                 if(IR(mStabbedFace.mDistance)<IR(mMaxDist))     // The other test is already performed in RayTriOverlap
 402                                 {
 403                                         // Set contact status
 404                                         mFlags |= OPC_TEMPORAL_CONTACT;
 405
 406                                         mStabbedFace.mFaceID = *face_id;
 407
 408 #ifndef OPC_RAYHIT_CALLBACK
 409                                         if(mStabbedFaces)       mStabbedFaces->AddFace(mStabbedFace);
 410 #endif
 411                                         return TRUE;
 412                                 }
 413                         }
 414                 }
 415 #else
 416                 // New code
 417                 // We handle both Segment/ray queries with the same segment code, and a possible infinite limit
 418                 SEGMENT_PRIM(*face_id, OPC_TEMPORAL_CONTACT)
 419
 420                 // Return immediately if possible
 421                 if(GetContactStatus())  return TRUE;
 422 #endif
 423         }
 424
 425         // Precompute data (moved after temporal coherence since only needed for ray-AABB)
 426         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)
 427         {
 428                 // For Segment-AABB overlap
 429                 mData = 0.5f * mDir * mMaxDist;
 430                 mData2 = mOrigin + mData;
 431
 432                 // Precompute mFDir;
 433                 mFDir.x = fabsf(mData.x);
 434                 mFDir.y = fabsf(mData.y);
 435                 mFDir.z = fabsf(mData.z);
 436         }
 437         else
 438         {
 439                 // For Ray-AABB overlap
 440 //              udword x = SIR(mDir.x)-1;
 441 //              udword y = SIR(mDir.y)-1;
 442 //              udword z = SIR(mDir.z)-1;
 443 //              mData.x = FR(x);
 444 //              mData.y = FR(y);
 445 //              mData.z = FR(z);
 446
 447                 // Precompute mFDir;
 448                 mFDir.x = fabsf(mDir.x);
 449                 mFDir.y = fabsf(mDir.y);
 450                 mFDir.z = fabsf(mDir.z);
 451         }
 452
 453         return FALSE;
 454 }
 455
 456 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 457 /**
 458  *      Stabbing query for vanilla AABB trees.
 459  *      \param          world_ray               [in] stabbing ray in world space
 460  *      \param          tree                    [in] AABB tree
 461  *      \param          box_indices             [out] indices of stabbed boxes
 462  *      \return         true if success
 463  */
 464 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 465 bool RayCollider::Collide(const Ray& world_ray, const AABBTree* tree, Container& box_indices)
 466 {
 467         // ### bad design here
 468
 469         // This is typically called for a scene tree, full of -AABBs-, not full of triangles.
 470         // So we don't really have "primitives" to deal with. Hence it doesn't work with
 471         // "FirstContact" + "TemporalCoherence".
 472         ASSERT( !(FirstContactEnabled() && TemporalCoherenceEnabled()) );
 473
 474         // Checkings
 475         if(!tree)                                       return false;
 476
 477         // Init collision query
 478         // Basically this is only called to initialize precomputed data
 479         if(InitQuery(world_ray))        return true;
 480
 481         // Perform stabbing query
 482         if(IR(mMaxDist)!=IEEE_MAX_FLOAT)        _SegmentStab(tree, box_indices);
 483         else                                                            _RayStab(tree, box_indices);
 484
 485         return true;
 486 }
 487
 488
 489 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 490 /**
 491  *      Recursive stabbing query for normal AABB trees.
 492  *      \param          node    [in] current collision node
 493  */
 494 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 495 void RayCollider::_SegmentStab(const AABBCollisionNode* node)
 496 {
 497         // Perform Segment-AABB overlap test
 498         if(!SegmentAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents))      return;
 499
 500         if(node->IsLeaf())
 501         {
 502                 SEGMENT_PRIM(node->GetPrimitive(), OPC_CONTACT)
 503         }
 504         else
 505         {
 506                 _SegmentStab(node->GetPos());
 507
 508                 if(ContactFound()) return;
 509
 510                 _SegmentStab(node->GetNeg());
 511         }
 512 }
 513
 514 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 515 /**
 516  *      Recursive stabbing query for quantized AABB trees.
 517  *      \param          node    [in] current collision node
 518  */
 519 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 520 void RayCollider::_SegmentStab(const AABBQuantizedNode* node)
 521 {
 522         // Dequantize box
 523         const QuantizedAABB& Box = node->mAABB;
 524         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 525         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 526
 527         // Perform Segment-AABB overlap test
 528         if(!SegmentAABBOverlap(Center, Extents))        return;
 529
 530         if(node->IsLeaf())
 531         {
 532                 SEGMENT_PRIM(node->GetPrimitive(), OPC_CONTACT)
 533         }
 534         else
 535         {
 536                 _SegmentStab(node->GetPos());
 537
 538                 if(ContactFound()) return;
 539
 540                 _SegmentStab(node->GetNeg());
 541         }
 542 }
 543
 544 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 545 /**
 546  *      Recursive stabbing query for no-leaf AABB trees.
 547  *      \param          node    [in] current collision node
 548  */
 549 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 550 void RayCollider::_SegmentStab(const AABBNoLeafNode* node)
 551 {
 552         // Perform Segment-AABB overlap test
 553         if(!SegmentAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents))      return;
 554
 555         if(node->HasPosLeaf())
 556         {
 557                 SEGMENT_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
 558         }
 559         else _SegmentStab(node->GetPos());
 560
 561         if(ContactFound()) return;
 562
 563         if(node->HasNegLeaf())
 564         {
 565                 SEGMENT_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
 566         }
 567         else _SegmentStab(node->GetNeg());
 568 }
 569
 570 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 571 /**
 572  *      Recursive stabbing query for quantized no-leaf AABB trees.
 573  *      \param          node    [in] current collision node
 574  */
 575 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 576 void RayCollider::_SegmentStab(const AABBQuantizedNoLeafNode* node)
 577 {
 578         // Dequantize box
 579         const QuantizedAABB& Box = node->mAABB;
 580         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 581         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 582
 583         // Perform Segment-AABB overlap test
 584         if(!SegmentAABBOverlap(Center, Extents))        return;
 585
 586         if(node->HasPosLeaf())
 587         {
 588                 SEGMENT_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
 589         }
 590         else _SegmentStab(node->GetPos());
 591
 592         if(ContactFound()) return;
 593
 594         if(node->HasNegLeaf())
 595         {
 596                 SEGMENT_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
 597         }
 598         else _SegmentStab(node->GetNeg());
 599 }
 600
 601 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 602 /**
 603  *      Recursive stabbing query for vanilla AABB trees.
 604  *      \param          node            [in] current collision node
 605  *      \param          box_indices     [out] indices of stabbed boxes
 606  */
 607 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 608 void RayCollider::_SegmentStab(const AABBTreeNode* node, Container& box_indices)
 609 {
 610         // Test the box against the segment
 611         Point Center, Extents;
 612         node->GetAABB()->GetCenter(Center);
 613         node->GetAABB()->GetExtents(Extents);
 614         if(!SegmentAABBOverlap(Center, Extents))        return;
 615
 616         if(node->IsLeaf())
 617         {
 618                 box_indices.Add(node->GetPrimitives(), node->GetNbPrimitives());
 619         }
 620         else
 621         {
 622                 _SegmentStab(node->GetPos(), box_indices);
 623                 _SegmentStab(node->GetNeg(), box_indices);
 624         }
 625 }
 626
 627 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 628 /**
 629  *      Recursive stabbing query for normal AABB trees.
 630  *      \param          node    [in] current collision node
 631  */
 632 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 633 void RayCollider::_RayStab(const AABBCollisionNode* node)
 634 {
 635         // Perform Ray-AABB overlap test
 636         if(!RayAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents))  return;
 637
 638         if(node->IsLeaf())
 639         {
 640                 RAY_PRIM(node->GetPrimitive(), OPC_CONTACT)
 641         }
 642         else
 643         {
 644                 _RayStab(node->GetPos());
 645
 646                 if(ContactFound()) return;
 647
 648                 _RayStab(node->GetNeg());
 649         }
 650 }
 651
 652 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 653 /**
 654  *      Recursive stabbing query for quantized AABB trees.
 655  *      \param          node    [in] current collision node
 656  */
 657 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 658 void RayCollider::_RayStab(const AABBQuantizedNode* node)
 659 {
 660         // Dequantize box
 661         const QuantizedAABB& Box = node->mAABB;
 662         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 663         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 664
 665         // Perform Ray-AABB overlap test
 666         if(!RayAABBOverlap(Center, Extents))    return;
 667
 668         if(node->IsLeaf())
 669         {
 670                 RAY_PRIM(node->GetPrimitive(), OPC_CONTACT)
 671         }
 672         else
 673         {
 674                 _RayStab(node->GetPos());
 675
 676                 if(ContactFound()) return;
 677
 678                 _RayStab(node->GetNeg());
 679         }
 680 }
 681
 682 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 683 /**
 684  *      Recursive stabbing query for no-leaf AABB trees.
 685  *      \param          node    [in] current collision node
 686  */
 687 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 688 void RayCollider::_RayStab(const AABBNoLeafNode* node)
 689 {
 690         // Perform Ray-AABB overlap test
 691         if(!RayAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents))  return;
 692
 693         if(node->HasPosLeaf())
 694         {
 695                 RAY_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
 696         }
 697         else _RayStab(node->GetPos());
 698
 699         if(ContactFound()) return;
 700
 701         if(node->HasNegLeaf())
 702         {
 703                 RAY_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
 704         }
 705         else _RayStab(node->GetNeg());
 706 }
 707
 708 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 709 /**
 710  *      Recursive stabbing query for quantized no-leaf AABB trees.
 711  *      \param          node    [in] current collision node
 712  */
 713 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 714 void RayCollider::_RayStab(const AABBQuantizedNoLeafNode* node)
 715 {
 716         // Dequantize box
 717         const QuantizedAABB& Box = node->mAABB;
 718         const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
 719         const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
 720
 721         // Perform Ray-AABB overlap test
 722         if(!RayAABBOverlap(Center, Extents))    return;
 723
 724         if(node->HasPosLeaf())
 725         {
 726                 RAY_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
 727         }
 728         else _RayStab(node->GetPos());
 729
 730         if(ContactFound()) return;
 731
 732         if(node->HasNegLeaf())
 733         {
 734                 RAY_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
 735         }
 736         else _RayStab(node->GetNeg());
 737 }
 738
 739 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 740 /**
 741  *      Recursive stabbing query for vanilla AABB trees.
 742  *      \param          node            [in] current collision node
 743  *      \param          box_indices     [out] indices of stabbed boxes
 744  */
 745 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 746 void RayCollider::_RayStab(const AABBTreeNode* node, Container& box_indices)
 747 {
 748         // Test the box against the ray
 749         Point Center, Extents;
 750         node->GetAABB()->GetCenter(Center);
 751         node->GetAABB()->GetExtents(Extents);
 752         if(!RayAABBOverlap(Center, Extents))    return;
 753
 754         if(node->IsLeaf())
 755         {
 756                 mFlags |= OPC_CONTACT;
 757                 box_indices.Add(node->GetPrimitives(), node->GetNbPrimitives());
 758         }
 759         else
 760         {
 761                 _RayStab(node->GetPos(), box_indices);
 762                 _RayStab(node->GetNeg(), box_indices);
 763         }
 764 }