Bresenham's Line Algorithm

Published on

In 1965 Jack Elton Bresenham published the paper Algorithm for computer control of a digital plotter in the IBM Systems Journal, volume 4, number 1. It explained how a line could be approximated on an integer grid. The algorithm is still used today as a rasterization technique for rendering lines on video displays or printers. As Bresenham's paper suggests, however, it was originally devised for a plotter, capable of moving from one grid point to one of the adjacent eight grid points.

We consider drawing a line from (0,0)(0, 0) to (Δx,Δy)(\Delta x, \Delta y) on an integer grid by choosing the points that lie close to the true line. We also assume that Δx>0\Delta x > 0 and Δx≥Δy≥0\Delta x \geq \Delta y \geq 0. The method is easily extended to the general case with arbitrary starting and ending points.

The line has the form

y=f(x)=ΔyΔxxy = f(x) = \frac{\Delta y}{\Delta x} x

and we aim to sample the line at the grid points (xk,yk)(x_k, y_k) with xk=kx_k = k for k=0,1,…,Δxk = 0, 1, \ldots, \Delta x and y0=0y_0 = 0.

We now associate with each step an error term,

∇k=2Δx[f(xk)−(yk−1+12)]=2xkΔy−(2yk−1+1)Δx  .\nabla_k = 2\Delta x \left[f(x_k) - (y_{k-1} + \textstyle\frac{1}{2})\right] = 2x_k\Delta y - (2y_{k-1} + 1) \Delta x \; .

The interpretation of this error term is important: It expresses the difference at x=xkx = x_k between the line's true yy-coordinate, f(xk)f(x_k), and the midpoint between the previously chosen yy-coordinate, yk−1y_{k-1}, and its successor, yk−1+1y_{k-1}+1. The factor 2Δx2\Delta x is there to make all quantities integral. The sign of ∇k\nabla_k is thus crucial:

  • If ∇k≤0\nabla_k \leq 0 then yk=yk−1y_k = y_{k-1} lies closest to the line (it is a tie for ∇k=0\nabla_k = 0).
  • If ∇k>0\nabla_k > 0 then yk=yk−1+1y_k = y_{k-1}+1 should be chosen.

Note how the magnitude of ∇k\nabla_k also tells exactly how far from the true line the chosen grid point is. It is straightforward to show that −2Δx<∇k≤2Δx-2\Delta x < \nabla_k \leq 2\Delta x for k=1,2,…,Δxk = 1, 2, \ldots, \Delta x.

Figure 1. Given that the previous point is at (xk-1, yk-1), the dashed lines indicate the two extreme cases for the line being approximated. ∇k will be negative if the line goes through the red area and positive if it goes through the blue area.

To determine the ∇k\nabla_k's we start with the base case:

∇1=2⋅1⋅Δy−(2⋅0+1)Δx=2Δy−Δx  .\nabla_1 = 2\cdot 1\cdot \Delta y - (2\cdot 0 + 1) \Delta x = 2\Delta y - \Delta x \; .

For k=1,2,…,Δx−1k=1, 2, \ldots, \Delta x - 1 we get

∇k+1−∇k=2(xk+1−xk)Δy−2(yk−yk−1)Δx  .\nabla_{k+1} - \nabla_k = 2(x_{k+1}-x_k)\Delta y - 2(y_k-y_{k-1})\Delta x \; .

We now split into the two cases for ∇k\nabla_k and get

∇k+1={∇k+2Δyfor ∇k≤0  ,∇k+2Δy−2Δxfor ∇k>0  ,\nabla_{k+1} = \begin{cases} \nabla_k + 2\Delta y & \text{for } \nabla_k \leq 0 \; , \\ \nabla_k + 2\Delta y - 2\Delta x & \text{for } \nabla_k > 0 \; , \end{cases}

for k=1,2,…,Δx−1k=1, 2, \ldots, \Delta x - 1.

These expressions determine all the ∇k\nabla_k's which, in turn, determines all the yky_k's.

Feel free to leave any question, correction or comment in this Mastodon thread.