2 * OPCODE - Optimized Collision Detection
3 * http://www.codercorner.com/Opcode.htm
5 * Copyright (c) 2001-2008 Pierre Terdiman, pierre@codercorner.com
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:
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.
18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
20 * Contains code for a ray collider.
21 * \file OPC_RayCollider.cpp
22 * \author Pierre Terdiman
25 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
27 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
29 * Contains a ray-vs-tree collider.
30 * This class performs a stabbing query on an AABB tree, i.e. does a ray-mesh collision.
32 * HIGHER DISTANCE BOUND:
34 * If P0 and P1 are two 3D points, let's define:
35 * - d = distance between P0 and P1
37 * - Direction = (P1 - P0) / d = normalized direction vector
38 * - A parameter t such as a point P on the line (P0,P1) is P = Origin + t * Direction
42 * Then we can define a general "ray" as:
50 * But it actually maps three different things:
51 * - a segment, when 0 <= t <= d
52 * - a half-line, when 0 <= t < +infinity, or -infinity < t <= d
53 * - a line, when -infinity < t < +infinity
55 * In Opcode, we support segment queries, which yield half-line queries by setting d = +infinity.
56 * We don't support line-queries. If you need them, shift the origin along the ray by an appropriate margin.
58 * In short, the lower bound is always 0, and you can setup the higher bound "d" with RayCollider::SetMaxDist().
60 * Query |segment |half-line |line
61 * --------|-------------------|---------------|----------------
62 * Usages |-shadow feelers |-raytracing |-
63 * |-sweep tests |-in/out tests |
67 * - You can setup "first contact" mode or "all contacts" mode with RayCollider::SetFirstContact().
68 * - In "first contact" mode we return as soon as the ray hits one face. If can be useful e.g. for shadow feelers, where
69 * you want to know whether the path to the light is free or not (a boolean answer is enough).
70 * - In "all contacts" mode we return all faces hit by the ray.
74 * - You can enable or disable temporal coherence with RayCollider::SetTemporalCoherence().
75 * - It currently only works in "first contact" mode.
76 * - If temporal coherence is enabled, the previously hit triangle is cached during the first query. Then, next queries
77 * start by colliding the ray against the cached triangle. If they still collide, we return immediately.
81 * - You can enable or disable "closest hit" with RayCollider::SetClosestHit().
82 * - It currently only works in "all contacts" mode.
83 * - If closest hit is enabled, faces are sorted by distance on-the-fly and the closest one only is reported.
87 * - You can enable or disable backface culling with RayCollider::SetCulling().
88 * - If culling is enabled, ray will not hit back faces (only front faces).
93 * \author Pierre Terdiman
97 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
99 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
101 * This class describes a face hit by a ray or segment.
102 * This is a particular class dedicated to stabbing queries.
104 * \class CollisionFace
105 * \author Pierre Terdiman
107 * \date March, 20, 2001
109 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
111 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
113 * This class is a dedicated collection of CollisionFace.
115 * \class CollisionFaces
116 * \author Pierre Terdiman
118 * \date March, 20, 2001
120 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
122 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
123 // Precompiled Header
126 using namespace Opcode;
128 #include "OPC_RayAABBOverlap.h"
129 #include "OPC_RayTriOverlap.h"
131 #define SET_CONTACT(prim_index, flag) \
132 mNbIntersections++; \
133 /* Set contact status */ \
135 /* In any case the contact has been found and recorded in mStabbedFace */ \
136 mStabbedFace.mFaceID = prim_index;
138 #ifdef OPC_RAYHIT_CALLBACK
140 #define HANDLE_CONTACT(prim_index, flag) \
141 SET_CONTACT(prim_index, flag) \
143 if(mHitCallback) (mHitCallback)(mStabbedFace, mUserData);
145 #define UPDATE_CACHE \
146 if(cache && GetContactStatus()) \
148 *cache = mStabbedFace.mFaceID; \
152 #define HANDLE_CONTACT(prim_index, flag) \
153 SET_CONTACT(prim_index, flag) \
155 /* Now we can also record it in mStabbedFaces if available */ \
158 /* If we want all faces or if that's the first one we hit */ \
159 if(!mClosestHit || !mStabbedFaces->GetNbFaces()) \
161 mStabbedFaces->AddFace(mStabbedFace); \
165 /* We only keep closest hit */ \
166 CollisionFace* Current = const_cast<CollisionFace*>(mStabbedFaces->GetFaces()); \
167 if(Current && mStabbedFace.mDistance<Current->mDistance) \
169 *Current = mStabbedFace; \
174 #define UPDATE_CACHE \
175 if(cache && GetContactStatus() && mStabbedFaces) \
177 const CollisionFace* Current = mStabbedFaces->GetFaces(); \
178 if(Current) *cache = Current->mFaceID; \
179 else *cache = INVALID_ID; \
183 #define SEGMENT_PRIM(prim_index, flag) \
184 /* Request vertices from the app */ \
185 VertexPointers VP; mIMesh->GetTriangle(VP, prim_index); \
187 /* Perform ray-tri overlap test and return */ \
188 if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2])) \
190 /* Intersection point is valid if dist < segment's length */ \
191 /* We know dist>0 so we can use integers */ \
192 if(IR(mStabbedFace.mDistance)<IR(mMaxDist)) \
194 HANDLE_CONTACT(prim_index, flag) \
198 #define RAY_PRIM(prim_index, flag) \
199 /* Request vertices from the app */ \
200 VertexPointers VP; mIMesh->GetTriangle(VP, prim_index); \
202 /* Perform ray-tri overlap test and return */ \
203 if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2])) \
205 HANDLE_CONTACT(prim_index, flag) \
209 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
213 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
214 RayCollider::RayCollider() :
217 mNbIntersections (0),
219 #ifdef OPC_RAYHIT_CALLBACK
224 mStabbedFaces (null),
230 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
234 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
235 RayCollider::~RayCollider()
239 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
241 * Validates current settings. You should call this method after all the settings and callbacks have been defined.
242 * \return null if everything is ok, else a string describing the problem
244 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
245 const char* RayCollider::ValidateSettings()
247 if(mMaxDist<0.0f) return "Higher distance bound must be positive!";
248 if(TemporalCoherenceEnabled() && !FirstContactEnabled()) return "Temporal coherence only works with ""First contact"" mode!";
249 #ifndef OPC_RAYHIT_CALLBACK
250 if(mClosestHit && FirstContactEnabled()) return "Closest hit doesn't work with ""First contact"" mode!";
251 if(TemporalCoherenceEnabled() && mClosestHit) return "Temporal coherence can't guarantee to report closest hit!";
253 if(SkipPrimitiveTests()) return "SkipPrimitiveTests not possible for RayCollider ! (not implemented)";
257 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
259 * Generic stabbing query for generic OPCODE models. After the call, access the results:
260 * - with GetContactStatus()
261 * - in the user-provided destination array
263 * \param world_ray [in] stabbing ray in world space
264 * \param model [in] Opcode model to collide with
265 * \param world [in] model's world matrix, or null
266 * \param cache [in] a possibly cached face index, or null
267 * \return true if success
268 * \warning SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only.
270 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
271 bool RayCollider::Collide(const Ray& world_ray, const Model& model, const Matrix4x4* world, udword* cache)
274 if(!Setup(&model)) return false;
276 // Init collision query
277 if(InitQuery(world_ray, world, cache)) return true;
279 if(!model.HasLeafNodes())
281 if(model.IsQuantized())
283 const AABBQuantizedNoLeafTree* Tree = (const AABBQuantizedNoLeafTree*)model.GetTree();
285 // Setup dequantization coeffs
286 mCenterCoeff = Tree->mCenterCoeff;
287 mExtentsCoeff = Tree->mExtentsCoeff;
289 // Perform stabbing query
290 if(IR(mMaxDist)!=IEEE_MAX_FLOAT) _SegmentStab(Tree->GetNodes());
291 else _RayStab(Tree->GetNodes());
295 const AABBNoLeafTree* Tree = (const AABBNoLeafTree*)model.GetTree();
297 // Perform stabbing query
298 if(IR(mMaxDist)!=IEEE_MAX_FLOAT) _SegmentStab(Tree->GetNodes());
299 else _RayStab(Tree->GetNodes());
304 if(model.IsQuantized())
306 const AABBQuantizedTree* Tree = (const AABBQuantizedTree*)model.GetTree();
308 // Setup dequantization coeffs
309 mCenterCoeff = Tree->mCenterCoeff;
310 mExtentsCoeff = Tree->mExtentsCoeff;
312 // Perform stabbing query
313 if(IR(mMaxDist)!=IEEE_MAX_FLOAT) _SegmentStab(Tree->GetNodes());
314 else _RayStab(Tree->GetNodes());
318 const AABBCollisionTree* Tree = (const AABBCollisionTree*)model.GetTree();
320 // Perform stabbing query
321 if(IR(mMaxDist)!=IEEE_MAX_FLOAT) _SegmentStab(Tree->GetNodes());
322 else _RayStab(Tree->GetNodes());
326 // Update cache if needed
332 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
334 * Initializes a stabbing query :
335 * - reset stats & contact status
336 * - compute ray in local space
337 * - check temporal coherence
339 * \param world_ray [in] stabbing ray in world space
340 * \param world [in] object's world matrix, or null
341 * \param face_id [in] index of previously stabbed triangle
342 * \return TRUE if we can return immediately
343 * \warning SCALE NOT SUPPORTED. The matrix must contain rotation & translation parts only.
345 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
346 BOOL RayCollider::InitQuery(const Ray& world_ray, const Matrix4x4* world, udword* face_id)
348 // Reset stats & contact status
349 Collider::InitQuery();
352 mNbIntersections = 0;
353 #ifndef OPC_RAYHIT_CALLBACK
354 if(mStabbedFaces) mStabbedFaces->Reset();
357 // Compute ray in local space
358 // The (Origin/Dir) form is needed for the ray-triangle test anyway (even for segment tests)
361 Matrix3x3 InvWorld = *world;
362 mDir = InvWorld * world_ray.mDir;
365 InvertPRMatrix(World, *world);
366 mOrigin = world_ray.mOrig * World;
370 mDir = world_ray.mDir;
371 mOrigin = world_ray.mOrig;
374 // 4) Special case: 1-triangle meshes [Opcode 1.3]
375 if(mCurrentModel && mCurrentModel->HasSingleNode())
377 // We simply perform the BV-Prim overlap test each time. We assume single triangle has index 0.
378 if(!SkipPrimitiveTests())
380 // Perform overlap test between the unique triangle and the ray (and set contact status if needed)
381 SEGMENT_PRIM(udword(0), OPC_CONTACT)
383 // Return immediately regardless of status
388 // Check temporal coherence :
390 // Test previously colliding primitives first
391 if(TemporalCoherenceEnabled() && FirstContactEnabled() && face_id && *face_id!=INVALID_ID)
394 #ifndef OPC_RAYHIT_CALLBACK
398 // Request vertices from the app
400 mIMesh->GetTriangle(VP, *face_id);
401 // Perform ray-cached tri overlap test
402 if(RayTriOverlap(*VP.Vertex[0], *VP.Vertex[1], *VP.Vertex[2]))
404 // Intersection point is valid if:
405 // - distance is positive (else it can just be a face behind the orig point)
406 // - distance is smaller than a given max distance (useful for shadow feelers)
407 // if(mStabbedFace.mDistance>0.0f && mStabbedFace.mDistance<mMaxDist)
408 if(IR(mStabbedFace.mDistance)<IR(mMaxDist)) // The other test is already performed in RayTriOverlap
410 // Set contact status
411 mFlags |= OPC_TEMPORAL_CONTACT;
413 mStabbedFace.mFaceID = *face_id;
415 #ifndef OPC_RAYHIT_CALLBACK
416 if(mStabbedFaces) mStabbedFaces->AddFace(mStabbedFace);
424 // We handle both Segment/ray queries with the same segment code, and a possible infinite limit
425 SEGMENT_PRIM(*face_id, OPC_TEMPORAL_CONTACT)
427 // Return immediately if possible
428 if(GetContactStatus()) return TRUE;
432 // Precompute data (moved after temporal coherence since only needed for ray-AABB)
433 if(IR(mMaxDist)!=IEEE_MAX_FLOAT)
435 // For Segment-AABB overlap
436 mData = 0.5f * mDir * mMaxDist;
437 mData2 = mOrigin + mData;
440 mFDir.x = fabsf(mData.x);
441 mFDir.y = fabsf(mData.y);
442 mFDir.z = fabsf(mData.z);
446 // For Ray-AABB overlap
447 // udword x = SIR(mDir.x)-1;
448 // udword y = SIR(mDir.y)-1;
449 // udword z = SIR(mDir.z)-1;
455 mFDir.x = fabsf(mDir.x);
456 mFDir.y = fabsf(mDir.y);
457 mFDir.z = fabsf(mDir.z);
463 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
465 * Stabbing query for vanilla AABB trees.
466 * \param world_ray [in] stabbing ray in world space
467 * \param tree [in] AABB tree
468 * \param box_indices [out] indices of stabbed boxes
469 * \return true if success
471 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
472 bool RayCollider::Collide(const Ray& world_ray, const AABBTree* tree, Container& box_indices)
474 // ### bad design here
476 // This is typically called for a scene tree, full of -AABBs-, not full of triangles.
477 // So we don't really have "primitives" to deal with. Hence it doesn't work with
478 // "FirstContact" + "TemporalCoherence".
479 ASSERT( !(FirstContactEnabled() && TemporalCoherenceEnabled()) );
482 if(!tree) return false;
484 // Init collision query
485 // Basically this is only called to initialize precomputed data
486 if(InitQuery(world_ray)) return true;
488 // Perform stabbing query
489 if(IR(mMaxDist)!=IEEE_MAX_FLOAT) _SegmentStab(tree, box_indices);
490 else _RayStab(tree, box_indices);
496 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
498 * Recursive stabbing query for normal AABB trees.
499 * \param node [in] current collision node
501 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
502 void RayCollider::_SegmentStab(const AABBCollisionNode* node)
504 // Perform Segment-AABB overlap test
505 if(!SegmentAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents)) return;
509 SEGMENT_PRIM(node->GetPrimitive(), OPC_CONTACT)
513 _SegmentStab(node->GetPos());
515 if(ContactFound()) return;
517 _SegmentStab(node->GetNeg());
521 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
523 * Recursive stabbing query for quantized AABB trees.
524 * \param node [in] current collision node
526 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
527 void RayCollider::_SegmentStab(const AABBQuantizedNode* node)
530 const QuantizedAABB& Box = node->mAABB;
531 const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
532 const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
534 // Perform Segment-AABB overlap test
535 if(!SegmentAABBOverlap(Center, Extents)) return;
539 SEGMENT_PRIM(node->GetPrimitive(), OPC_CONTACT)
543 _SegmentStab(node->GetPos());
545 if(ContactFound()) return;
547 _SegmentStab(node->GetNeg());
551 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
553 * Recursive stabbing query for no-leaf AABB trees.
554 * \param node [in] current collision node
556 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
557 void RayCollider::_SegmentStab(const AABBNoLeafNode* node)
559 // Perform Segment-AABB overlap test
560 if(!SegmentAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents)) return;
562 if(node->HasPosLeaf())
564 SEGMENT_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
566 else _SegmentStab(node->GetPos());
568 if(ContactFound()) return;
570 if(node->HasNegLeaf())
572 SEGMENT_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
574 else _SegmentStab(node->GetNeg());
577 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
579 * Recursive stabbing query for quantized no-leaf AABB trees.
580 * \param node [in] current collision node
582 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
583 void RayCollider::_SegmentStab(const AABBQuantizedNoLeafNode* node)
586 const QuantizedAABB& Box = node->mAABB;
587 const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
588 const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
590 // Perform Segment-AABB overlap test
591 if(!SegmentAABBOverlap(Center, Extents)) return;
593 if(node->HasPosLeaf())
595 SEGMENT_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
597 else _SegmentStab(node->GetPos());
599 if(ContactFound()) return;
601 if(node->HasNegLeaf())
603 SEGMENT_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
605 else _SegmentStab(node->GetNeg());
608 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
610 * Recursive stabbing query for vanilla AABB trees.
611 * \param node [in] current collision node
612 * \param box_indices [out] indices of stabbed boxes
614 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
615 void RayCollider::_SegmentStab(const AABBTreeNode* node, Container& box_indices)
617 // Test the box against the segment
618 Point Center, Extents;
619 node->GetAABB()->GetCenter(Center);
620 node->GetAABB()->GetExtents(Extents);
621 if(!SegmentAABBOverlap(Center, Extents)) return;
625 box_indices.Add(node->GetPrimitives(), node->GetNbPrimitives());
629 _SegmentStab(node->GetPos(), box_indices);
630 _SegmentStab(node->GetNeg(), box_indices);
634 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
636 * Recursive stabbing query for normal AABB trees.
637 * \param node [in] current collision node
639 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
640 void RayCollider::_RayStab(const AABBCollisionNode* node)
642 // Perform Ray-AABB overlap test
643 if(!RayAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents)) return;
647 RAY_PRIM(node->GetPrimitive(), OPC_CONTACT)
651 _RayStab(node->GetPos());
653 if(ContactFound()) return;
655 _RayStab(node->GetNeg());
659 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
661 * Recursive stabbing query for quantized AABB trees.
662 * \param node [in] current collision node
664 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
665 void RayCollider::_RayStab(const AABBQuantizedNode* node)
668 const QuantizedAABB& Box = node->mAABB;
669 const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
670 const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
672 // Perform Ray-AABB overlap test
673 if(!RayAABBOverlap(Center, Extents)) return;
677 RAY_PRIM(node->GetPrimitive(), OPC_CONTACT)
681 _RayStab(node->GetPos());
683 if(ContactFound()) return;
685 _RayStab(node->GetNeg());
689 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
691 * Recursive stabbing query for no-leaf AABB trees.
692 * \param node [in] current collision node
694 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
695 void RayCollider::_RayStab(const AABBNoLeafNode* node)
697 // Perform Ray-AABB overlap test
698 if(!RayAABBOverlap(node->mAABB.mCenter, node->mAABB.mExtents)) return;
700 if(node->HasPosLeaf())
702 RAY_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
704 else _RayStab(node->GetPos());
706 if(ContactFound()) return;
708 if(node->HasNegLeaf())
710 RAY_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
712 else _RayStab(node->GetNeg());
715 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
717 * Recursive stabbing query for quantized no-leaf AABB trees.
718 * \param node [in] current collision node
720 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
721 void RayCollider::_RayStab(const AABBQuantizedNoLeafNode* node)
724 const QuantizedAABB& Box = node->mAABB;
725 const Point Center(float(Box.mCenter[0]) * mCenterCoeff.x, float(Box.mCenter[1]) * mCenterCoeff.y, float(Box.mCenter[2]) * mCenterCoeff.z);
726 const Point Extents(float(Box.mExtents[0]) * mExtentsCoeff.x, float(Box.mExtents[1]) * mExtentsCoeff.y, float(Box.mExtents[2]) * mExtentsCoeff.z);
728 // Perform Ray-AABB overlap test
729 if(!RayAABBOverlap(Center, Extents)) return;
731 if(node->HasPosLeaf())
733 RAY_PRIM(node->GetPosPrimitive(), OPC_CONTACT)
735 else _RayStab(node->GetPos());
737 if(ContactFound()) return;
739 if(node->HasNegLeaf())
741 RAY_PRIM(node->GetNegPrimitive(), OPC_CONTACT)
743 else _RayStab(node->GetNeg());
746 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
748 * Recursive stabbing query for vanilla AABB trees.
749 * \param node [in] current collision node
750 * \param box_indices [out] indices of stabbed boxes
752 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
753 void RayCollider::_RayStab(const AABBTreeNode* node, Container& box_indices)
755 // Test the box against the ray
756 Point Center, Extents;
757 node->GetAABB()->GetCenter(Center);
758 node->GetAABB()->GetExtents(Extents);
759 if(!RayAABBOverlap(Center, Extents)) return;
763 mFlags |= OPC_CONTACT;
764 box_indices.Add(node->GetPrimitives(), node->GetNbPrimitives());
768 _RayStab(node->GetPos(), box_indices);
769 _RayStab(node->GetNeg(), box_indices);