CodeCat

Game development and others.

Line Intersection With Homogenous Coordinates

| Comments

There are a couple of ways to compute the intersection of two lines in two dimensions. Usually, computing them when they exist is easy, the hard part is handling the special cases where they don’t intersect or when they’re coincident. You’ll end up with all sorts of branches in your code which checks for parallelism which may slow it down (especially if you’re implementing it in a GPU).

Using the tools from projective geometry, particularly homogenous coordinates (as in the previous post), the line intersection and all the additional checks are elegantly handled by a single operation. Basically, let line a point is the intersection of two lines if and only if

where x, y, and w are not all zeroes. One way is to directly solve for this system, the other way is to simply

Solving for the determinant yields:

then simply equate x, y and z to the coefficients of respectively. In other words:

If w is zero, then the lines are parallel and x, y gives the normal of the lines. Else, if w is non-zero, then the lines intersect at x/w, y/w.

Why it works

Note the following:

  1. A matrix is singular iff its determinant is zero.
  2. A matrix is singular iff not all of its rows or columns are linearly independent.
  3. Given vectors u, v and d. d is orthogonal to u and v iff d is orthogonal to au + bv ∀ a, b ∈ ℜ

Appending to the matrix and setting its determinant to zero means that “if R is linearly dependent on either of the two previous rows, then this equation must be satisfied”. This means that ANY vector that is a linear combination of will satisfy the equation. This is convenient for us because this means that the coefficients of the resulting equation is orthogonal to the coordinates of both lines… which is exactly what were looking for!

x, y and w are, of course, in homogenous coordinates, so if the lines are parallel, they “intersect” at a “point at infinity”, represented by a point whose w = 0, which is basically the normal of the line. Note that this also works if you try to intersect a line at infinity with a normal line. If your application uses homogenous coordinates, you don’t really need to mind this (OpenGL already uses homogenous coordinates in drawing). However, if you need to do additional calculations in euclidean space (like for physics simlatuions), you may need to perform the said checks to the w (you’ll get a division by error if you just divide blindly).

We just saw how using homogenous coordinates made calculation of line intersections straightforward and mechanical (good for the processor). In total, it has 6 multiplies, 3 subtractions and optionally two divisions.

Comments