Bresenham's Algorithm to Draw a Line

Theory

Assume we are drawing a line from (x₁, y₁) to (x₂, y₂) on an discrete grid, for example, computer screen. The blue real line will then be drawn as a set of green points shown below.

Assuming that the line is drawn towards lager values of x and y, it is easily seen that, drawing the line point-by-point, the next point to plot after (x, y) is either (x, y+1) or (x+1, y) or (x+1, y+1), depending on which of them is closer to the real line.

To figure this out, consider the equation of a line passing through (x₁, y₁) and (x₂, y₂):

If we denote by D(x, y) the quantity in the left hand side of the above equality, to make a decision concerning the next point we have to find the minimum among the absolute values of D(x, y+1), D(x+1, y), and D(x+1, y+1). It turns out that if we denote

one has

The conclusion is also true if one applies the integer division in the above formulas. The value of D must be updated for the new point as follows:

Note, that the values |x₂ - x₁|, |y₂ - y₁|, v₁, and v₂ can be computed just once at the beginning of the algorithm. Any line will require using either only diagonal and horizontal moves, or only diagonal and vertical moves, depending on the slope. This implies that the number of steps in the line drawing process is max {|x₂ - x₁|, |y₂ - y₁| } + 1.

Implementation

Here is a pseudocode for drawing a line from (x₁, y₁) to (x₂, y₂)

dx = |x2 - x1|          // absolute values
dy = |y2 - y1|
stepX = sign(x2 - x1)   // +1 or -1 or 0
stepY = sign(y2 - y1)
v1 = -dy + dx/2         // integer division
v2 = dx - dy/2
count = max{dx, dy} + 1 // # of line points

x = x1                  // (x,y) is a point to plot
y = y1
D = 0
n = 0                   // points counter
do {
   plot(x, y)           // plot a point
   n++

   if (D < v1) {
      x = x + stepX     // horizontal move
      D = D + dy
   }
   else if (D > v2) {
      y = y + stepY     // vertical move
      D = D - dx
   else {
      x = x + stepX     // diagonal move
      y = y + stepY
      D = D + dy - dx
   }
while (n <= count)

... and its assembler implementation. The code draws a series of lines sliding at a corner.

Algorithm in action