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!