CodeCat

Game development and others.

Line Representations 2

| Comments

This is a continuation of the previous post.

Implicit

This form is another way to extend the slope-intercept form. Instead of having a single “slope”, we split its numerator and denominator to different variables, $a, b$. Just by doing this, the form can represent vertical lines that the slope-intercept form cannot (set ). The reason why this is called implicit is that instead of having y “pop out” of the equation, we pop it back in so instead of having y = f(x), we have f(x,y) = 0.

By far, this is the most compact form of line representation, requiring only 3 numbers for storage. The vector〈a, b〉formed by coefficients of the equation is the “normal” of the line, the direction that is perpendicular to the direction of the line. Moreover, the direction is pointing to the “left” of the line. To illustrate, suppose we have the following equation:

The normal of the line is 〈 1,1 〉. Both line and normal look like the one below:

graph of x + y = 0

If we turn the equation to the normal will be 〈-1, -1〉which is still the same line but the normal will be facing the other way around.Actually, for any number s ≠ 0, equation will represent the same thing. Thus, the representation of the line is not unique. If you want to compare if two representations are the same, you’ll have to check if one is a multiple of the other (a mere equality test won’t work).

Another thing to note about this form is that linear implicit equations are “well-behaved”. By that, I mean that whenever is close to zero, you can be assured that somewhere near is the solution to f(x,y) = 0. This is how some anti-aliased software line renderers work. They evaluate k = f(x,y) at a point. If k is below an upper threshold, they start applying grayscale tint to that point, if k is below an even lower threshold, the point is assumed to be exactly in the line and color it black.

As a segway into the next line representation, what do you think will happen if we set a = b = 0 but c ≠ 0?

Homogenous

This form is very similar to the implicit form except with an additional coefficient, w, of the point (not of the line). Thus, the storage requirements for this representation is still 3 numbers. A shorthand of writing this representation of the line is [a, b, c]. The basis for this representation lies in the theory of projective geometries.

The central concept in projective geometry is the line-point duality: that what ever holds true for lines should also hold true for points. In particular, we know that in the euclidean geometry, there’s exactly one line passing through two distinct points. However, dual is not true since two lines does not always intersect at a point because if the two lines are parallel, it’s either they don’t intersect or they coincide, in which case, there are infinitely many points.

In order to make eculidean geometry projective, we include the notion of “points at infinity”. To visualize this, imagine you’re on a railroad track that extends to the horizon. Even if you very well know that the two rails of the track are parallel, at the horizon (which is very far away), they seem to intersect at a point. Moreover, if you rotate around and find another set of tracks, you’ll find that they intersect at a point distict from the previous one. This means that there is more than on point at infinity. Moreover, the line that contains all the points at infinity (the horizon in our example), is called the “line at infinity”.

They way to represent a projective n-dimensional eucledian geometry is to add another coordinate to it. We call this homogenous coordinates since we’ll be representing normal points and points at infinity in the same way (and makes certain calculations more uniform). So, in the case of 2D, we have 3 coordinates: x, y and w and in 3D, four coordinates: x, y, z and w. So how does it work?

First, to determine whether a point〈x, y, w〉is in the line [a, b, c], we have to check if ax + by + cw is 0. This is basically the inner product of the vectors [a, b, c] and [x, y, w]. For example, the point 〈1,1,1〉 is in the line [1, -1, 0] because 1(1) - 1(1) + 0(1) = 1 - 1 = 0.

Next in the implicit form, remember that if are the coefficients of the line, for any s ≠ 0, ((sax + sby + sc = s0 = 0$$ represents the same line. The same goes for points: for any s ≠ 0,〈sx, xy, sw〉represents the same point as〈x, y, w〉1. Similarly, [sa, sb, sc] represents the same line as [a, b, c].

As a definition, the point〈x,y,w〉 is a point at infinity if w = 0. Otherwise, it is a normal point. Observe that the only line [a,b,c] that satisfies the equation 〈ax + by + c(0) = 0〉 for every x and y is [0,0,c] where c ≠ 0. This is called the line at infinity (to answer the question I posted in the previous section).

To convert a point 〈x,y〉 from eucledian space to the projective euclidean space, simply assume w = 1, 〈x,y,1〉. This also makes our line representation in homogenous coordinates exactly the same as in implicit form. To convert a point 〈x,y,w〉 into normal euclidean space, we “normalize” the form into 〈x/w, y/w, 1〉 so that we’ll get a “1” in the last component (note that you can’t do this if the point is at infinity) then extract the first and second component.

If you need any clarifications, post them in the comments below. I’ve just started blogging about math it may take me some time to figure out how to properly organizing my thoughts.

  1. In linear algebra parlance, a point in projective geometry is represented by a one-dimensional vector space.

Comments