# Lines

We start from scratch again: we have a canvas of dimensions $$C_w$$ and $$C_h$$ and we can $$PutPixel()$$ on it.

Say we have two points $$P_0$$ and $$P_1$$, with coordinates $$(x_0, y_0)$$ and $$(x_1, y_1)$$ respectively. Drawing these two points individually is trivial; but how can we draw the straight line segment from $$P_0$$ to $$P_1$$?

Let’s start representing a line with parametric coordinates, just as we did with rays before (these “rays” were nothing but lines in 3D). Any point in the line can be obtained by starting at $$P_0$$ and moving some distance along the direction from $$P_0$$ to $$P_1$$:

$P = P_0 + t(P_1 - P_0)$

We can decompose this equation in two, one for each coordinate:

$x = x_0 + t(x_1 - x_0)$

$y = y_0 + t(y_1 - y_0)$

Let’s take the first equation and solve for $$t$$:

$x = x_0 + t(x_1 - x_0)$

$x - x_0 = t(x_1 - x_0)$

${{x - x_0} \over {x_1 - x_0}} = t$

We can now plug this expression for $$t$$ into the second equation:

$y = y_0 + t(y_1 - y_0)$

$y = y_0 + {{x - x_0} \over {x_1 - x_0}}(y_1 - y_0)$

Rearranging it a bit:

$y = y_0 + (x - x_0){{y_1 - y_0} \over {x_1 - x_0}}$

Notice that $${{y_1 - y_0} \over {x_1 - x_0}}$$ is a constant which depends only on the endpoints of the segment; let’s call it $$a$$:

$$y = y_0 + a(x - x_0)$$

What is $$a$$? Because of the way it’s defined, it measures the change in the $$y$$ coordinate per unit change in the $$x$$ coordinate; in other words, it’s a measure of the slope of the line.

Let’s go back to the equation. Distributing the multiplication:

$y = y_0 + ax - ax_0$

Grouping the constants:

$y = ax + (y_0 - ax_0)$

Again, $$(y_0 - ax_0)$$ depends only on the endpoints of the segment; let’s call it $$b$$, and we finally get

$y = ax + b$

This is the classic linear function, which can be used to represent almost all lines. It can’t represent vertical lines because these have an infinite number of values of $$y$$ for one value of $$x$$, and none for the rest. Somewhere in the process of obtaining this representation from the original parametric equation, these families of lines were lost; it happened when solving for $$t$$, since we ignored the fact that $$x_1 - x_0$$ could produce a division by zero. For now, let’s just ignore vertical lines; we’ll lift this restriction later.

So we now have a way to get the value of $$y$$ for each value of $$x$$ that interests us, thus obtaining a pair $$(x, y)$$ that satisfies the equation of the line. If we go from $$x_0$$ to $$x_1$$ and compute the value of $$y$$ for each value of $$x$$, we get the first approximation of our line drawing function:

DrawLine(P0, P1, color) {
a = (y1 - y0)/(x1 - x0)
b = y0 - a*x0
for x = x0 to x1 {
y = a*x + b
canvas.PutPixel(x, y, color)
}
}

In this fragment, x0 and y0 are the $$x$$ and $$y$$ coordinates of P0; I’ll be using this convenient notation from now on. Also note that the division operator / is expected to perform real division, not integer division.

This function is a direct, naive implementation of the equation above, so it clearly works; but can we make it faster?

Note that we aren’t calculating values of $$y$$ for any $$x$$: in fact, we’re calculating them only at integer increments of $$x$$, and we’re doing so in order: right after calculating $$y(x)$$, we calculate $$y(x+1)$$:

$y(x) = ax + b$

$y(x+1) = a(x+1) + b$

We can exploit this to make a faster algorithm. Let’s take the difference between the $$y$$ of consecutive pixels:

$y(x+1) - y(x) = (a(x+1) + b) - (ax + b)$

$= a(x+1) + b - ax - b$

$= ax + a - ax$

$= a$

This shouldn’t be so surprising; after all, the slope $$a$$ is the measure of how much $$y$$ changes for each unit increment in $$x$$, which is exactly what we’re doing here.

The interesting thing is that we can trivially get this

$y(x+1) = y(x) + a$

Which means we can compute the next value of $$y$$ using just the previous value of $$y$$ and adding the slope; no per-pixel multiplication is needed. We need to start somewhere (at the beginning there’s no “previous value of $$y$$”), so we start at $$(x_0, y_0)$$, and then add $$1$$ to $$x$$ and $$a$$ to $$y$$ until we get to $$x_0$$.

Assuming $$x_0 < x_1$$, we can rewrite the function as follows:

DrawLine(P0, P1, color) {
a = (y1 - y0)/(x1 - x0)
y = y0
for x = x0 to x1 {
canvas.PutPixel(x, y, color)
y = y + a
}
}

This new version of the function has a new restriction: it can only draw lines that go from left to right, that is, when $$x_0 < x_1$$. This is quite easy to overcome: since it doesn’t matter in what order we draw the individual pixels, if we get a right-to-left line, we just exchange P0 and P1 to transform it into the left-to-right version of the same line, and draw it as before:

DrawLine(P0, P1, color) {
# Make sure x0 < x1
if x0 > x1 {
swap(P0, P1)
}
a = (y1 - y0)/(x1 - x0)
y = y0
for x = x0 to x1 {
canvas.PutPixel(x, y, color)
y = y + a
}
}

Now we can draw a couple of lines. Here’s $$(-200, 100) - (240, 120)$$:

Here’s a close-up:

The jagged appearance is due to the fact that we can only draw pixels on integer coordinates, and mathematical lines actually have zero width; what we’re drawing is a quantized approximation of the ideal line from $$(-200, 100) - (240, 120)$$1.

Let’s try another one, $$(-50, -200) - (60, 240)$$:

And here’s a close-up:

Oops. What happened?

The algorithm is working as intended; it went from left to right, computed a value of $$y$$ for each value of $$x$$, and painted the corresponding pixel. The problem is that it computed one value of $$y$$ for each value of $$x$$, while we actually need several values of $$y$$ for some values of $$x$$.

This is a direct consequence of choosing a formulation where $$y = f(x)$$; it is in fact the same reason why we can’t draw vertical lines, an extreme case where there’s a single value of $$x$$ with many values of $$y$$.

We can draw horizontal lines without any problem; why can’t we draw vertical lines just as easily?

It turns out we can. Choosing $$y = f(x)$$ was an arbitrary decision, so there’s no reason not to express the line as $$x = f(y)$$, reworking all the equations exchanging $$x$$ and $$y$$, and coming up with the following algorithm:

DrawLine(P0, P1, color) {
# Make sure y0 < y1
if y0 > y1 {
swap(P0, P1)
}
a = (x1 - x0)/(y1 - y0)
x = x0
for y = y0 to y1 {
canvas.PutPixel(x, y, color)
x = x + a
}
}

This is identical to the previous DrawLine, except the $$x$$ and $$y$$ computations have been exchanged. This one can handle vertical lines and will draw $$(0, 0) - (50, 100)$$ correctly; of course, it can’t handle horizontal lines at all or draw $$(0, 0) - (100, 50)$$ correctly! What to do?

We just need to choose the appropriate version of the function depending on the line we’re trying to draw. And the criteria is quite simple; does the line have more different values of $$x$$ or different values of $$y$$? If there are more values of $$x$$ than $$y$$, we use the first version; otherwise, we use the second.

Here’s a version of DrawLine that handles all the cases:

DrawLine(P0, P1, color) {
dx = x1 - x0
dy = y1 - y0
if abs(dx) > abs(dy) {
# Line is horizontal-ish
# Make sure x0 < x1
if x0 > x1 {
swap(P0, P1)
}
a = dy/dx
y = y0
for x = x0 to x1 {
canvas.PutPixel(x, y, color)
y = y + a
}
} else {
# Line is vertical-ish
# Make sure y0 < y1
if y0 > y1 {
swap(P0, P1)
}
a = dx/dy
x = x0
for y = y0 to y1 {
canvas.PutPixel(x, y, color)
x = x + a
}
}
}

This certainly works, but it isn’t great code; there are two implementations of the code that computes a linear function incrementally, and this computation and the selection logic are mixed together. Since we’ll use linear functions a lot, separating the code is worth the extra work.

We have two functions $$y = f(x)$$ and $$x = f(y)$$. To abstract away the fact that we’re dealing with pixels, let’s write it generically as $$d = f(i)$$, where $$i$$ is the independent variable, the one we choose the values for, and $$d$$ is the dependent variable, the one whose value depends on the other, and we want to compute. In the horizontal-ish case $$x$$ is the independent variable and $$y$$ is the dependent variable; it’s the other way around in the vertical-ish case.

Of course, any function can be written as $$d = f(i)$$. We know two more things that completely define it: the fact that it’s linear, and two of its values; that is, $$d_0 = f(i_0)$$ and $$d_1 = f(i_1)$$. We can write a simple method that gets these values and returns the intermediate values of $$d$$, assuming as before that $$i1 < i0$$:

Interpolate (i0, d0, i1, d1) {
values = []
a = (d1 - d0) / (i1 - i0)
d = d0
for i = i0 to i1 {
values.append(d)
d = d + a
}
return values
}

Note that the value of $$d$$ corresponding to $$i_0$$ is in values, the value for $$i_0 + 1$$ is in values, and so on; in general, the value for $$i_n$$ is in values[i_n - i_0], assuming $$i_n$$ is in the range $$[i_0, i_1]$$.

There’s a corner case we need to consider; we may want to compute $$d = f(i)$$ for a single value of $$i$$, that is, when $$i0 = i1$$. In this case we can’t even compute $$a$$, so we’ll treat it as a special case:

Interpolate (i0, d0, i1, d1) {
if i0 == i1 {
return [ d0 ]
}
values = []
a = (d1 - d0) / (i1 - i0)
d = d0
for i = i0 to i1 {
values.append(d)
d = d + a
}
return values
}

Now we can write DrawLine using Interpolate:

DrawLine(P0, P1, color) {
if abs(x1 - x0) > abs(y1 - y0) {
# Line is horizontal-ish
# Make sure x0 < x1
if x0 > x1 {
swap(P0, P1)
}
ys = Interpolate(x0, y0, x1, y1)
for x = x0 to x1 {
canvas.PutPixel(x, ys[x - x0], color)
}
} else {
# Line is vertical-ish
# Make sure y0 < y1
if y0 > y1 {
swap(P0, P1)
}
xs = Interpolate(y0, x0, y1, x1)
for y = y0 to y1 {
canvas.PutPixel(xs[y - y0], y, color)
}
}
}

This DrawLine can handle all cases correctly:

Source code and live demo >>

While this version isn’t much shorter than the previous one, it cleanly separates the computation of the intermediate values of $$y$$ and $$x$$, and the decision of which is the independent variable plus the drawing code itself. The advantage may not be obvious, but Interpolate will be reused heavily in later chapters.

Note that this is not the best or the fastest line-drawing algorithm; the important product of this chapter is Interpolate, not DrawLine. The best line-drawing algorithm is probably Bresenham’s.

Found an error? Everything is in Github.

1. There are ways to draw prettier approximations of lines. We won’t go there for two reasons: 1) it’s slower, 2) our goal is not to draw pretty lines, but to develop some basic algorithms to render 3D scenes.