Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

enter image description here

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!

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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!

share|improve this answer

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.

share|improve this answer
    
I've give this a shot and it works! Even though I don't really know how to properly calculate the Minkowski sum. However, I'm clocking 18 dot products for what should be a simple sweep, isn't that bad? –  Larolaro May 23 '12 at 21:13
    
I think you need up to 10 planes to represent the convex shape. You can think of it as sticking the AABB at the endpoints of the segment, then taking the convex hull of that (don't actually compute this, though!). You'll get up to three faces of AABB on each end contributing planes, and I think you get 4 planes along the "body" of the segment. If the segment is axis-aligned in any direction, some of the "body" places will be the same as the "AABB" planes. –  celion May 24 '12 at 1:29
    
If you need help visualizing the planes, I should be able to sketch it out in 2D. For other optimizations, your raycasting should early out in some cases, reducing the total number of work you have to do. And you might be able to special-case the planes that come from the AABB faces, since you know that they're axis aligned. –  celion May 24 '12 at 1:33
    
At the moment, for this, I have 6 planes, 2 on each end and 2 along the sweep (I'm working in 2D). The 3 dot products are for calculating the intersection for each plane. I'm feeling there can be a faster way to approach this. –  Larolaro May 24 '12 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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