The Liang-Barsky algorithm is a cheap way to find the intersection points between a line segment and an axis-aligned rectangle. It's a simple algorithm, but the resources I was pointed to didn't have particularly good explanations, so I tried to write a better one.
Consider a rectangle defined by x_min ≤ x ≤ x_max and y_min ≤ y ≤ y_max, and a line segment from (x_0, y_0) to (x_0 + Δ_x, y_0 + Δ_y). We'll be assuming at least one of Δ_x and Δ_y is nonzero.
(I'm working with Flash, so I'll be using the convention that y increases as you go down.)
We want to distinguish between the following cases:
- The line segment is entirely outside the rectangle.
- The line segment is entirely inside the rectangle.
- One end of the line segment is inside and the other is outside.
- The line segment starts outside the rectangle, enters it, and leaves it again.
In the latter two cases, we want to know the points of intersection.
For k = 1,2,3,4, we define p_k and q_k as follows. Each value of k corresponds to a different side of the rectangle.
- p_1 = -Δ_x, q_1 = x_0 - x_min (left).
- p_2 = Δ_x, q_2 = x_max - x_0 (right).
- p_3 = -Δ_y, q_3 = y_0 - y_min (top).
- p_4 = Δ_y, q_4 = y_max - y_0 (bottom).
For each k, if the line crosses that boundary, it will be travelling inside -> outside if p_k > 0 and outside -> inside if p_k < 0. (If p_k = 0, the line moves parallel to that boundary, and we consider it never to cross.)
Note also that the signs of q_k depend on the position of (x_0, y_0) with respect to the rectangle. For example, if x_0 < x_min, then q_1 < 0 and q_2 > 0. If x_0 > x_max then q_1 > 0 and q_2 < 0. If x_min < x_0 < x_max, then both q_1 > 0 and q_2 > 0.
From this it follows that for each k, if p_k = 0 and q_k < 0, the line is entirely outside the rectangle. This corresponds to a vertical line passing the rectangle to the left (k=1) or right (k=2), or a horizontal line passing to the top (k=3) or bottom (k=4).
Now consider an infinite line γ, defined by γ(t) = (x_0, y_0) + t * (Δ_x, Δ_y), u ∈ ℝ. The line segment we're testing is clearly contained in γ, with endpoints at γ(0) and γ(1). t can be considered a time, of sorts; we'll be asking, "does γ intersect the rectangle, and if so, at what times do they intersect?"
For each value of k for which p_k != 0, define t_k = q_k / p_k. t_k is the time at which γ(t_k) is on the line extended from boundary k. (That is, γ(t_1) has x=x_min, γ(t_2) has x=x_max, γ(t_3) has y=y_min, and γ(t_4) has y=y_max.)
Now let u_1 be the largest value of t_k for which p_k < 0. Recall that the edges for which p_k < 0 are the ones which are crossed (if they are crossed at all) from the outside to the inside. It follows that if γ enters the rectangle, it will enter it at time t_1.
Similarly, let u_2 be the smallest value of t_k for which p_k > 0. This is the time at which γ leaves the rectangle, if it ever entered.
(An example is probably in order. Look at the image above, in which p_1 and p_4 are positive and p_2 and p_3 are negative. It happens that in this case, u_4 < u_1 < u_3 < u_2. At time u_4, γ crosses to the left of the bottommost edge of the rectangle. Then at u_1, γ enters the rectangle, crossing the leftmost edge between y_min and y_max. At u_3, γ leaves again, crossing the topmost edge between x_min and x_max; and at u_4 it crosses above the rightmost edge. Note also that in this case, u_4 < 0 < u_1 and u_3 < 1 < u_2.)
We can now distinguish between the four cases:
- If u_1 > u_2, the line segment is entirely outside the rectangle.
- If u_1 < 0 < 1 < u_2, the line segment is entirely inside the rectangle.
- If 0 < u_1 < u_2 < 1, the line segment both starts and finishes outside the rectangle; but they intersect at points γ(u_1) and γ(u_2).
- Otherwise, one end is inside and one end is outside. Two subcases:
-
- If 0 < u_1 < 1, the line starts outside and moves inside, intersecting at γ(u_1).
-
- If 0 < u_2 < 1, the line starts inside and moves outside, intersecting at γ(u_2).
Depending on your situation, you might not need to consider all these. For example, I'm doing collision detection: I can assume that the line segment starts outside, and if there's a collision I don't care where it would have finished. So if u_1 < u_2, I'm only interested in γ(u_1).
Since everything depends on u_1 and u_2, we should verify that they will always be well-defined. That's easy to check. Recall that u_1 is
- the maximum value of t_k,
- for which p_k < 0.
So if there is no k for which p_k < 0, or if there is k such that p_k < 0 but t_k is undefined, we'll run into problems. But t_k is just q_k / p_k, so t_k is defined whenever p_k != 0. And since sign(p_1) = -sign(p_2) and sign(p_3) = -sign(p_4), if there's no p_k < 0 there's also no p_k > 0. This implies Δ_x = Δ_y = 0, and we're not dealing with a line segment at all.
(It might still be worth considering what happens when Δ_x = Δ_y = 0. If the point is outside the rectangle, one of the q_k will be negative, and we'll correctly find no collision. If the point is inside the rectangle, anything could happen. You'll want to treat that case seperately, if it might occur.)
As written, it might sound like the algorithm would be quite ugly to implement: define the p_k and q_k; loop to check whether any p_k = 0 with q_k < 0; then loop to define the t_k; then loop to define u_1 and loop again to define u_2. But it's okay: those can all be squashed into a single loop with a short body.
Here's my implementation in Haxe. (And the context.) It returns a boolean, and if there is a collision it stores it in a variable which the caller can then read. I don't worry about the case Δ_x = Δ_y = 0, because in this particular game that shouldn't ever happen with the point inside the rectangle. (Famous last words... if it does happen, it will report a collision at (-∞, -∞), and that's about as good a response as any.) Variable mapping: x_0 and y_0 are just x and y; Δ_x and Δ_y are vx and vy; x_min etc. are left etc.; k is i; t_k are only needed in the scope of a for loop, so they're each just called t.
public function collides () : Bool {
var p = [-vx, vx, -vy, vy];
var q = [x - left, right - x, y - top, bottom - y];
var u1 = Math.NEGATIVE_INFINITY;
var u2 = Math.POSITIVE_INFINITY;
for (i in 0...4) {
if (p[i] == 0) {
if (q[i] < 0)
return false;
}
else {
var t = q[i] / p[i];
if (p[i] < 0 && u1 < t)
u1 = t;
else if (p[i] > 0 && u2 > t)
u2 = t;
}
}
if (u1 > u2 || u1 > 1 || u1 < 0)
return false;
collision.x = x + u1*vx;
collision.y = y + u1*vy;
return true;
}
Thanks, your explanation and code are great !
Just a little mistake :
var q = [x - left, right - x, y - top, bottom - y];
should be
var q = [x - left, right - x, y - bottom, top - y];