0
\$\begingroup\$

I would like to intersect a thick ray (actually a cylinder) with an AABB. The current code to perform intersection with the ray is the following.

template <class RealT>
bool CAABB<RealT>::Pick(const CPoint3T & base, const CVector3T & dir) const
{
    // SLAB based optimized ray/AABB intersection routine
    // Idea taken from http://ompf.org/ray/

    RealT l1 = (_minPnt.x - base.x) / dir.x;
    RealT l2 = (_maxPnt.x - base.x) / dir.x;
    RealT lmin = minT( l1, l2 );
    RealT lmax = maxT( l1, l2 );

    l1 = (_minPnt.y - base.y) / dir.y;
    l2 = (_maxPnt.y - base.y) / dir.y;
    lmin = maxT( minT( l1, l2 ), lmin );
    lmax = minT( maxT( l1, l2 ), lmax );

    l1 = (_minPnt.z - base.z) / dir.z;
    l2 = (_maxPnt.z - base.z) / dir.z;
    lmin = maxT( minT( l1, l2 ), lmin );
    lmax = minT( maxT( l1, l2 ), lmax );

    if( (lmax >= 0.0f) & (lmax >= lmin) )
    {
        // Consider length
        const CVector3T rayDest = base + dir;
        CPoint3T rayMins( minT( rayDest.x, base.x), minT( rayDest.y, base.y ), minT( rayDest.z, base.z ) );
        CPoint3T rayMaxs( maxT( rayDest.x, base.x), maxT( rayDest.y, base.y ), maxT( rayDest.z, base.z ) );
        return 
            (rayMins.x < _maxPnt.x) && (rayMaxs.x > _minPnt.x) &&
            (rayMins.y < _maxPnt.y) && (rayMaxs.y > _minPnt.y) &&
            (rayMins.z < _maxPnt.z) && (rayMaxs.z > _minPnt.z);
    }
    else
        return false;
}

I would like to write a routine that takes an additional parameter for ray_thickness (diameter of the cylinder) and compute the intersection.

\$\endgroup\$
1
1
\$\begingroup\$

I see 2 naive approaches, I don't know which one is faster:

  1. You could project the AABB on the plan which is orthonormal to the direction of the ray, then resolve the problem of intersection of a 2D sphere with the projected AABB.

  2. You could project your cylinder on each of the 3 axis and check for intersection with the 2D rectangle (which is the projection of the AABB), then combine the 3 results to decide on the 3D intersection.

\$\endgroup\$
0
0
\$\begingroup\$

I think you'd find that doing several ray checks would be faster and conceptually simpler than checking several manifolds against each other. They call these ray packets in raytracing literature.

I'd suggest using 6 rays for the cylinder's radius, and one for the centre, totalling 7. You could even get away with as few as 4 or 5 rays, depending on how you want approximate the cylinder shape. This will be fast for non-axis-aligned objects, and can be blisteringly fast for AABBs. Provided the distance between each ray in the packet is small enough (slightly smaller than the diameter of your smallest detectable entity), you'd never miss anything. Here's a picture of a 7-ray cylinder end-on:

       o
 o           o
       o
 o           o
       o

I'd go so far as to say this is the more common approach in games due to cost.

\$\endgroup\$
5
  • \$\begingroup\$ Unfortunately I suspect this will not give accurate results, for example what if the top left corner of the AABB was between the two lower right rays? the ray cast will fail, yet the cylinder hits the AABB. Actually I think any sampling solution will fail at some point. \$\endgroup\$ – concept3d Feb 11 '14 at 9:17
  • \$\begingroup\$ @concept3d This is the difference between theory and engineering. Strict definitions of "failure" are often pushed out somewhat in order to improve performance. As I noted, "provided the distance between each ray... is small enough..." You get the drift. This includes spacing on the cylinder perimeter. One matches the resolution of the rays to suit specific implementation requirements. Where performance is a concern, you don't want to be doing manifold-manifold checks. \$\endgroup\$ – Engineer Feb 11 '14 at 9:27
  • \$\begingroup\$ I agree with what you said. This is a practical solution especially if you want performance increase. It really depends on what the OP's concern actually is. \$\endgroup\$ – concept3d Feb 11 '14 at 9:33
  • \$\begingroup\$ The problem is the results are not reliable. The "holes" in the packed rays will always result in behavior that is not consistent. \$\endgroup\$ – Ram Feb 12 '14 at 9:28
  • \$\begingroup\$ @Ram You might consider just how much accuracy you need; e.g. a cylinder of radius 1 foot, with rays packed 1 inch apart, to detect objects of a minimum diameter 10cm is certainly reliable enough, though it may not be all that performant. Ray-packing resolution depends on granularity of the objects you are trying to detect. But perhaps you are right and O(M*N) is faster than checking several rays, where M is the number of objects, N is the (variable) number of triangles per object, each to be oriented to the cylinder's coordinate system and then tested for inside/outsideness using the radius. \$\endgroup\$ – Engineer Feb 12 '14 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.