janmr blog

Bresenham's Line Algorithm

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Δy0\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)(yk1+12)]=2xkΔy(2yk1+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, yk1y_{k-1}, and its successor, yk1+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 k0\nabla_k \leq 0 then yk=yk1y_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=yk1+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<k2Δ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=21Δy(20+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,,Δx1k=1, 2, \ldots, \Delta x - 1 we get

k+1k=2(xk+1xk)Δy2(ykyk1)Δ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 k0  ,k+2Δy2Δ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,,Δx1k=1, 2, \ldots, \Delta x - 1.

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