Why Does Bresenham’s Line Drawing Algorithm Work?

I created a C# implementation of Bresenham’s line drawing algorithm in Visual Studio. You can view/download the source code from my github.

bresenham1

Given two integer endpoint coordinates, Bresenham’s line drawing algorithm determines what other integer coordinates best approximate the ideal line segment that they define.

Here is the (modified) pseudocode from Wikipedia:

plotLine(x0,y0, x1,y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    y = y0

    for x from x0 to x1
        plot(x,y)
        if D > 0
            y = y + 1
            D = D - 2*dx
        end if
        D = D + 2*dy

Remarkably, this algorithm uses only integer arithmetic. Earlier computers motivated this property because non whole number operations, like division, were then relatively slow to compute.

The algorithm encodes the following intuitive logic:

  • Provided I am currently on a pixel that best approximates the ideal line, I should proceed to the adjacent pixel that also best approximates the ideal line. That pixel is either straight ahead, or diagonal from the current pixel.
  • By repeating this logic I can always begin at one endpoint and, selecting the pixel that best approximates the ideal line at each step, arrive at the other endpoint.
  • Since the pixels that best approximate the ideal line are always selected at each step, the entire line approximates the ideal line segment as best as possible.

bresenhamcloseup

But from looking at the code, that’s not at all apparent. So why does Bresenham’s line drawing algorithm work?

Derivation:

Endpoints, (x_0,y_0) and (x_1,y_1) define the ideal line:

\begin{aligned} y(x)&=mx+b \\ m &= \frac{(y_1-y_0)}{(x_1-x_0)} = \frac{\Delta y}{\Delta x} \end{aligned}

Denote the current coordinate:

(x_i,y_i)

To measure \alpha_i, the error in proceeding from the current coordinate the diagonal coordinate, and \beta_i, the error in proceeding instead to the adjacent coordinate:

\begin{aligned} \alpha_i &= y_i+1-y(x_i+1) \\ &= y_i+1-m(x_i+1)-b \\ \beta_i &= y(x_i+1)-y_i \\ &= m(x_i+1)+b-y_i \end{aligned}

If the error in proceeding to the diagonal coordinate is less than the error in proceeding to the adjacent coordinate, then I should proceed to the diagonal coordinate, otherwise I should proceed to the adjacent coordinate.

\begin{aligned} \alpha_i < \beta_i &\implies diagonal \\ \alpha_i \geq \beta_i &\implies adjacent \end{aligned}

If I instead take the difference of the two errors,

\begin{aligned} \beta_i - \alpha_i = &m(x_i+1)+b-y_i \\ +&m(x_i+1)+b-y_i-1 \\ = &2m(x_i+1)+2b-2y_i-1 \\ = &2mx_i+2m+2b-2y_i-1 \end{aligned}

I can follow the equivalent logic:

\begin{aligned} \beta_i - \alpha_i < 0 &\implies adjacent \\ \beta_i -\alpha_i \geq 0 &\implies diagonal \end{aligned}

Since the slope of the line, m, is a rational number, the decision still can not be made using just integer arithmetic.

\begin{aligned} \beta_i - \alpha_i &= 2mx_i+2m+2b-2y_i-1 \\ &= 2[\frac{\Delta y}{\Delta x}]x_i+2[\frac{\Delta y}{\Delta x}]+2b-2y_i-1\end{aligned}

But I can multiply the equality by \Delta x

\Delta x(\beta_i - \alpha_i) = 2\Delta y x_i + 2\Delta y + 2\Delta x b - 2 \Delta x y_i - \Delta x

and now follow the equivalent, integer arithmetic only logic:

\begin{aligned} \Delta x(\beta_i - \alpha_i) < 0 &\implies adjacent \\ \Delta x(\beta_i -\alpha_i) \geq 0 &\implies diagonal \end{aligned}

I’ll give this expression a name:

\begin{aligned} D_i &= \Delta x(\beta_i - \alpha_i) \\ &= 2\Delta y x_i + 2\Delta y + 2\Delta x b - 2 \Delta x y_i - \Delta x \end{aligned}

But rather than making all these calculations at every iteration of the algorithm, observe that the difference between successive terms is

\begin{aligned} D_{i+1} - D_i &= 2\Delta y x_{i+1} + 2\Delta y + 2\Delta x b - 2 \Delta x y_{i+1} - \Delta x \\ &-(2\Delta y x_i + 2\Delta y + 2\Delta x b - 2 \Delta x y_i - \Delta x) \\ &= 2\Delta y(x_{i+1} - x_i) - 2 \Delta x(y_{i+1} - y_i) \\ &= 2\Delta y - 2 \Delta x(y_{i+1} - y_i)\end{aligned}

Then I only have to track changes to this quantity at each iteration. This requires fewer calculations. Since at every iteration, the x-coordinate increases by one, x_{i+1} - x_i is always one. Since the y-coordinate increases by one only when D_i \geq 0

\begin{cases} & D_i < 0 \implies D_{i+1} = D_i + 2\Delta y \\ &D_i \geq 0 \implies D_{i+1} = D_i + 2\Delta y - 2 \Delta x \end{cases}

So when D is less than zero, add 2\Delta y to D and keep the y-coordinate the same. Otherwise, if D is greater than zero, add 2\Delta y - 2 \Delta x to D and increase the y-coordinate by one.
Now all that remains is to find the initial value, D_0:

\begin{aligned} D_0 &= 2\Delta y x_0 + 2\Delta y + 2\Delta x b - 2 \Delta x y_0 - \Delta x \\ &= 2\Delta y x_0 + 2\Delta y + 2\Delta x [y_0 - \frac{\Delta y}{\Delta x} x_0] - 2 \Delta x y_0 - \Delta x \\ &= 2 \Delta y - \Delta x \end{aligned}

And that’s all there is to it!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s