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;
}
It looks like you deliberately excluded discussion of a few points of detail that were not relevant to your particular purpose. But for anyone wanting to code up a complete version of the algorithm, as I did, a couple of refinements seem to be necessary.
[A] First, we need to be clear about whether points lying on the edge of the rectangle are to be regarded as inside or outside it. When I code to your specifications I get inconsistent results. (1) When the line segment lies on a rectangle edge but does not include either corner it is regarded as inside. The moment it includes one or both corners it is regarded as outside. (2) A line segment starting outside the rectangle and ending on its edge is regarded as not intersecting the rectangle: apparently the endpoint lying on the rectangle edge is regarded as being outside the rectangle. But should this same line segment travel one unit further inside the rectangle we now do regard it as entering the rectangle; its intersection point is the same point that the previous case regarded as outside. But does that make sense? Don't we regard all intersection points of the line with the rectangle as being inside the rectangle?
[B] Your four cases for interpreting u_1 and u_2 look as if they are meant to be exhaustive but in fact there are two more cases. (1) Before starting on your four we need to consider u_1 = u_2. In this case the line segment passes through a corner of the rectangle and according to the values of u_1 and u_2 there are three subcases, exit, entry or traversal. (2) It is also possible when u_1 ~= u_2 to fall through your list of cases into a fifth case in which the line segment is wholly outside the rectangle. This happens because your first case (u_1 > u_2) eliminates a line segment wholly outside the rectangle only when the infinite line also does not intersect the rectangle. In the new fifth case the infinite line does pass through the rectangle, it's just the line segment that doesn't.
[C] The implementation I'm working on hopes to resolve all these issues as listed below. I regard all points on a rectangle edge as inside the rectangle. My cases (1) to (4) correspond to your four cases. For clarity, I rename u_1 as entryTime and u_2 as exitTime.
Precondition: the line segment (LS) is not parallel to any rectangle (R) edge.
(0) entryTime = exitTime ==> the LS passes through a corner of R. Subcases:
(a) entryTime = exitTime = 0 : LS begins at the corner. Classify this an intersection which exits R.
(b) entryTime = exitTime = 1 : LS ends at the corner. Classify this as an intersection which enters R.
(c) Otherwise classify as a traversal of R (i.e. LS both enters and exits).
(1) entryTime > exitTime ==> the LS is wholly outside R. The infinite line does not pass through R either.
(2) entryTime <= 0 and exitTime >= 1 ==> the LS is wholly inside R
(3) entryTime >= 0 and exitTime <= 1 ==> the LS traverses R (i.e. both enters and exits it)
(4a) 0 < entryTime <= 1 ==> the LS enters R (started outside, ends inside)
(4b) 0 <= exitTime < 1 ==> the LS exits R (started inside, ends outside)
Can only get here when entryTime < exitTime
(5) The LS is wholly outside R. The infinite line does pass through R. Subcases:
(a) entryTime > 1 ==> the LS is heading towards R
(b) exitTime < 0 ==> the LS is heading away from R
There are no further cases.