Derivation of Bresenham's Line Algorithm

Derivation for first octant based on version in Hearn & Baker's "Computer Graphics"

Explanations and Generalizations written by Kenny Hoff
September 2, 1995

Overview of Problem

Given to line endpoints, we are trying to find the "in-between" points on a pixel grid. Bresenham's line algorithm determines subsequent points from the start point by making a decision between the two next available points by determining which is closer to the ideal point.

Derivation of Algorithm

Given two endpoints (Ax,Ay) and (Bx,By). One can be chosen as the start point ( x(k),y(k) ). The choice is purely arbitrary. From this start point, we have eight possible choices for the next pixel in the line. We need to isolate these eight choices into only two. If we restrict the slope for now to (0<=slope<=1) and assume (Ax < Bx), we know that we can simply step in x one pixel at a time to the right and determine what y value to choose next. Given ( x(k),y(k) ), the next ideal point will be ( x(k)+1, y ) where y = m*(x(k)+1) + b. But we must choose between ( x(k)+1, y(k) ) or ( x(k)+1, y(k)+1 ). These points represent the one just to the right and the one to the right and one up respectively.
How do we decide between these points? We now have the following:
start point: ( x(k),y(k) )
next two available points: ( x(k)+1, y(k) ) and ( x(k)+1, y(k)+1 )
location of next ideal point: ( x(k)+1, y ) where y = m*(x(k)+1) + b (Point-Slope line equation)
We must choose the closest point to the ideal. So first we must find the distances to the two available choices from the ideal location.
Distance between point-to-right and ideal = d1 = y - y(k)
Distance between point-to-right-and-up and ideal = d2 = (y(k)+1) - y
So we can simply choose subseqent points based on the following:
if (d1<=d2) then choose point-to-right: ( x(k)+1, y(k) )
if (d1>d2) then choose point-to-right-and-up: ( x(k)+1, y(k)+1 )
However, since we are trying to develop a FAST way of doing this, we will not be comparing these values in such a manner; instead we will create a decision variable that can be used to quickly determine which point to use.
How do we do create this decision variable? First, instead of comparing the two values to each other, we can simply evaluate (d1-d2) and simply test the sign to determine which to choose. Make sense? If d1 > d2 then (d1-d2) will be positive, etc. So now if (d1-d2) is positive (greater than zero) choose point-to-right-and-up OR if (d1-d2) is negative or zero (less than or equal to zero) choose point-to-right. This is nice and clear, but I'm afraid we must complicate things a little in order to get a REAL speedups.
Evaluate (d1-d2) as follows: (d1-d2) = y - y(k) - ( (y(k)+1) - y ) = y - y(k) - (y(k)+1) + y
now substitute using y = m*(x(k)+1) + b. . .
(d1-d2) = m*(x(k)+1) + b - y(k) - (y(k)+1) + m*(x(k)+1) + b
= 2*m*(x(k)+1) - 2*y(k) + 2*b - 1
Reduce this evaluation by finding slope and substituting:
slope = m = dY/dX where dY = abs(By - Ay) and dX = abs(Bx - Ax)
so now (d1-d2) = 2*(dY/dX)*(x(k)+1) - 2*y(k) + 2*b - 1
expand first term so (d1-d2) = 2*(dY/dX)*x(k) + 2*(dY/dX) - 2*y(k) + 2*b - 1
To simplify this expression we will create a new decision variable P(k):
P(k) = dX * (d1-d2) this is will remove the divisions and will still keep the
same sign for the decision. Why? Because dX is always positive!
Evaluate P(k) as follows:
P(k) = dX * ( 2*(dY/dX)*x(k) + 2*(dY/dX) - 2*y(k) + 2*b - 1 )
= 2*dY*x(k) + 2*dY - 2*dX*y(k) + 2*dX*b - dX
rearrange terms to get P(k) = 2*dY*x(k) - 2*dX*y(k) + 2*dY + 2*dX*b - dX
OR P(k) = 2*dY*x(k) - 2*dX*y(k) + c where constant c = 2*dY + dX*(2*b - 1)
(this remains constant regardless of choice of x and y; this notation aids in computation of dP)
What now? We have a decision variable that can be calculated very quickly, but it still requires a complete evaluation of P(k) for each point along the line. Since changes in P(k) will be linear, we can evaluate subseqent P(k) values incrementally by finding a constant change in P(k) for each subsequent point. How? By evaluating an incremental change in the decision function using Forward-Differencing: change in P = dP = P(k+1) - P(k)
dP is evaluated as follows:
P(k+1) - P(k) = 2*dY*x(k+1) - 2*dX*y(k+1) + c - 2*dY*x(k) + 2*dX*y(k) - c
= 2*dY*x(k+1) - 2*dY*x(k) - 2*dX*y(k+1) + 2*dX*y(k)
= 2*dY*(x(k+1) - x(k)) - 2*dX*(y(k+1) - y(k))
observe that since we are stepping in x (by 1), (x(k+1) - x(k)) = 1
so, with substitution dP = 2*dY - 2*dX*(y(k+1) - y(k))
there are two possibilities for (y(k+1) - y(k)), 0 or 1 depending on if we choose point-to-right or point-to-right-and-up.
dP = 2*dY - 2*dX*(0) = 2*dY if point-to-right is chosen
dP = 2*dY - 2*dX*(1) = 2*dY - 2*dX if point-to-right-and-up is chosen
Now we know how much to increment the decision variable based on the point chosen, but now we must find the initial decision value P(0). We must evaluate using the FULL equation (with constant) for P(k).
P(k) = 2*dY*x(k) - 2*dX*y(k) + 2*dY + dX*(2*b - 1)
P(0) = 2*dY*x(0) - 2*dX*y(0) + 2*dY + dX*(2*b - 1)
what is b? using the point-slope line equation, y(0) = m*x(0) + b; so b = y - m*x(0)
substitute b. . .
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + dX*(2*(y(0) - m*x(0)) - 1)
substitute m = dY/dX. . .
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + dX*(2*(y(0) - (dY/dX)*x(0)) - 1)
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + 2*dX*(y(0) - (dY/dX)*x(0)) - dX
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + 2*dX*(y(0) - (dY/dX)*x(0)) - dX
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + 2*dX*y(0) - 2*dY*x(0) - dX
P(0) = 2*dY - dX
So there it is; the entire algorithm has been derived, but what now? We have the following "tools" to generate a line (only in the first octant):
- The endpoints: (Ax, Ay) and (Bx, By)
- change in x: dX = abs(Bx - Ax)
- change in y: dY = abs(By - Ay)
- start point (chosen arbitrarily): (Ax, Ay)
- initial decision value: P(0) = 2*dY - dX
- point choice conditions:
  - if (P <= 0) choose point-to-right
  - if (P > 0) choose point-to-right-and-up
- increments in P (dP) based on choices:
  - if point-to-right is chosen, increment P by (2*dY)
  - if point-to-right-and-up is chosen, increment P by (2*dY) - (2*dX)

Implementation of Algorithm for First Octant

Using the "tools" derived in the previous section it should be fairly simple to construct an algorithm that draws a line in the first octant (0 <= Slope <= 1). Before going on to the other octants, lets go through the necessary steps for this one:

Calculate and store absolute value of changes in X and Y between endpoints.
Calculate and Store initial decision value ( P(0) ).
Calculate and Store decision value increments; one for choosing point-to-right and one for choosing point-to-right-and-up.
Create loop that will process all points stepping in X (from Ax to Bx)as follows:
- Plot the pixel at the start point
- Check decision variable:
  - if decision variable P is positive (P>0), then point-to-right-AND-UP must be chosen; so start point x and y values must be incremented by one and decision variable (P) must be incremented by the appropriate dP value ( (2*dY) - (2*dY) ).
  - if decision variable P negative or zero (P<=0), then point-to-right must be chosen; so start point x-value must be incremented by one and decision variable (P) must be incremented by the other dP value (2*dY).

Implementation of Algorithm for Four Octants with Slopes -1 to 1

This one is easy. In the previous implementation when we checked the decision variable, we always incremented x and y by ONE (POSITIVE ONE). The dX and dY values are always positive regardless of which line is chosen (with slope -1 to 1). If we keep the start point as point A, we can determine the SIGN of the values to increment by. So if Ax < Bx, we know that x will be incremented by one, BUT if Bx < Ax, we know that x will be DECREMENTED by one. The same thing for the y values: if Ay < By, y will be incremented by one; and if By < Ay, y will be decremented by one. This one is quite easy to implement with only a few adjustments in the previous implementation. Since the decision variable and its possible increments are calculated by dX and dY, and they are always positive, we ONLY need to change the sign of the increments for x and y. So in essence, we deciding subsequent points based on the calculations for the first octant only, but instead of stepping in x and y in a positive direction we are checking to determine which way we should "step". We are simply moving these four octants into the first for calculations.

Generalized Implementation for all Directions

This one is a bit more complex and requires a careful examination of the four-octant version. Since the slope was restricted from -1 to 1, we were always able to step in x by one and simply determine the next y-value. This works because there is always one y value for each x value along the line. This does not work stepping in y for these slopes since there will be more than one x value for each y along the line. With slopes -1 to 1, y is said to be dependent on x; y being the dependent variable and x being the independent variable. With slopes greater than 1 or less than -1, y becomes the independent variable.

So what now? We must check for the slope of the line: is it within our previous bounds where x is independent or is it where y is independent. Each type must be drawn differently. If the slope is within -1 and 1, then the previous implementation will suffice, but if the slope is out of this range, we must take the previous implementation and swap all x and y values to "move" the calculations back into the first octant. This includes swapping dX and dY. Care must be taken to ensure that it will step in y and only step in x if the decision variable chooses point-to-right-and-up.

This completes the generalized version of the Bresenham's line drawing algorithm. The actual coded implementation will reveal many possible efficiency considerations. I have deliberately left out my version in this document to allow an unbiased interpretation of the Bresenham derivation. In the very least, the code should have no floating point numbers, multiplication or division operations, or even any comparisons to any number other than zero (they are slower); only additions, bit-shifts, and comparisons to zero are allowed. Good Luck!

written by Kenny Hoff (hoffkx@timewarp.uncg.edu)