Swept AABB vs Line Segment 2D

Question

I've really exhausted as much as Google has to give, I've spent a solid week googling every combination of words for an "AABBvsLine sweep", downloaded countless collision demos, dissected SAT intersection examples and an AABBvsAABB sweep trying to figure out how to approach this. I've not found a single thing covering this specific pairing.

Can anyone shed any light on how to get the hit time of a swept AABB vs a Line segment in 2D? I'm still getting familiar with the SAT but I do know how to implement it to a degree, I'm just not sure how to extract the hit time from the velocity in the non axis aligned separating axes for the sweep.

I really would appreciate anything at the moment, some code or even some helpful links, I'm at my wits end!

Answer 1

After a gruelling mind destroying week working on this, I managed to figure it out by myself, I would have killed for some help online somewhere, there is so little information on swept checks on anything but an AABB.

Wish I didn't have to answer my own questions on here, a few minutes from someone could have saved me days on this bloody nightmare.

Anyway! :p

What I did,

First I calculate an AABB constructed from the extents of the line segment.

I then calculate the radius of the Box in respect to the line direction. (covered in Gomez's simple intersection for games article)

Following that I projected a vector from the line to the Box and the velocity onto the normal of the line segment, I then divide the distance projection by the velocity projection for the velocity intersection. For the first hit time I minus the radius from the distance projection and for last hit time I add the radius.

I also had to add a small check for when the velocity is facing away from the line to flip the Box's radius calculation (sign flipping error).

After that I run a standard AABBvsAABB sweep against an AABB constructed from the extents of the line segment. (Christer Ericson's AABB sweep)

Here's my code.

private bool SweepBoxLine( Box a, Line l, Vector2 v, out Vector2 outVel, out Vector2 hitNormal  )
{
    Vector2 lineDir = l.b - l.a;
    Vector2 lineMin = new Vector2(0,0);
    Vector2 lineMax = new Vector2(0,0);

    if(lineDir.x > 0.0f) //right
    {
        lineMin.x = l.a.x;
        lineMax.x = l.b.x;
    }
    else //left
    {
        lineMin.x = l.b.x;
        lineMax.x = l.a.x;
    }

    if(lineDir.y > 0.0f) //up
    {
        lineMin.y = l.a.y;
        lineMax.y = l.b.y;
    }
    else //down
    {
        lineMin.y = l.b.y;
        lineMax.y = l.a.y;
    }

    //Initialise out info
    outVel = v;
    hitNormal = new Vector2(0,0);

    float hitTime = 0.0f;
    float outTime = 1.0f;
    Vector2 overlapTime = new Vector2(0,0);

    float r = a.extent.x * Mathf.Abs(l.n.x) + a.extent.y * Mathf.Abs(l.n.y); //radius to Line
    float boxProj = Vector2.Dot(l.a - a.center, l.n); //projected Line distance to N
    float velProj = Vector2.Dot(vel, l.n); //projected Velocity to N

    if(velProj < 0f) r *= -1f;

    hitTime = Mathf.Max( (boxProj - r ) / velProj, hitTime);
    outTime = Mathf.Min( (boxProj + r ) / velProj, outTime);

    // X axis overlap
    if( v.x < 0 ) //Sweeping left
    {
        if( a.max.x < lineMin.x ) return false;
        hitTime = Mathf.Max( (lineMax.x - a.min.x) / v.x, hitTime);
        outTime = Mathf.Min( (lineMin.x - a.max.x) / v.x, outTime);
    }
    else if( v.x > 0 ) //Sweeping right
    {
        if( a.min.x > lineMax.x ) return false;
        hitTime = Mathf.Max( (lineMin.x - a.max.x) / v.x, hitTime);
        outTime = Mathf.Min( (lineMax.x - a.min.x) / v.x, outTime);
    }
    else
    {
        if(lineMin.x > a.max.x || lineMax.x < a.min.x) return false;
    }

    if( hitTime > outTime ) return false;

    // Y axis overlap
    if( v.y < 0 ) //Sweeping down
    {
        if( a.max.y < lineMin.y ) return false;
        hitTime = Mathf.Max( (lineMax.y - a.min.y) / v.y, hitTime);
        outTime = Mathf.Min( (lineMin.y - a.max.y) / v.y, outTime);
    }
    else if( v.y > 0 ) //Sweeping up
    {
        if( a.min.y > lineMax.y ) return false;
        hitTime = Mathf.Max( (lineMin.y - a.max.y) / v.y, hitTime);
        outTime = Mathf.Min( (lineMax.y - a.min.y) / v.y, outTime);
    }
    else
    {
        if(lineMin.y > a.max.y || lineMax.y < a.min.y) return false;
    }

    if( hitTime > outTime ) return false;

    outVel = v * hitTime;

    return true;
}

I'm pleased that it came out with only simple float comparison and just two dot products, nice and fast! I hope it helps someone as hopelessly stuck as I was!

Answer 2

This should be equivalent to testing the ray of the AABB path against the Minkowski sum of the line segment and the AABB. The Minkowski sum in this case should be pretty simple - it's a convex polyhedron formed by sweeping the AABB from one endpoint of the segment to the other.

Once you can figure out the planes that define the polyhedron, you can use e.g. 5.3.8 from Christer Erison's RTCD book. The hit fraction from the raycast is the same as the hit fraction for the AABB cast.