Line intersection with AABB Rectangle?

Question

Preferably without using any kind of loop, as this'll be used in a game.

I wish to intersect a line with a rectangle, of arbitrary size. But I also wish for the intersection point[s] to be returned.

It's possible, I've done a little googling, but still have not worked it out.

The line is defined using (x1,y1,x2,y2). The rectangle has these two points too.

Answer 1

I would recommend simply doing a line-segment-line-segment intersection check on each line segment (edge) that makes up the rectangle. Here is a line segment intersection detection algorithm I wrote ages ago, dredged up from one of my old XNA projects:

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
    intersection = Vector2.Zero;

    Vector2 b = a2 - a1;
    Vector2 d = b2 - b1;
    float bDotDPerp = b.X * d.Y - b.Y * d.X;

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = b1 - a1;
    float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = a1 + t * b;

    return true;
}

I will leave inputting each edge into the above method and collecting the results as an exercise to the reader :)

---

Edit 1 year later now I've gone to university and done a Graphics course:

Take a look at the Cohen–Sutherland algorithm to do this efficiently when you have a large set of lines where most do not intersect the rectangle. It uses a 9 segment grid and you place each endpoint of the line in a region of said grid:

Using this we can tell if there will not be any line intersections:

For example here CD will not intersect the rectangle (shown in red in the first image) as both C and D are in the top row and neither will AB. For the ones where the line may intersect the the rectangle we have to try the line-line intersections.

They way the sections are numbered/labelled allows us to simply do x AND y != 0 (where x and y are the labels of the sections for each of the line's endpoints) to determine if there will not be an intersection.

Using this method means we have to many, many fewer line-line intersections which speeds up the whole thing massively.