The basic ”line drawing” algorithm used in computer graphics is Bresenham’s Algorithm. This algorithm was developed to draw lines on digital plotters, but has found wide-spread usage in computer graphics. The algorithm is fast – it can be implemented with integer calculations only – and very simple to describe.
Consider a line with initial point (x1 , y1 ) and terminal point (x2 , y2 ) in device space.
If ∆x = x2 − x1 and ∆y = y2 − y1 , we define the slope as m = ∆y/∆x. It is very well known that, if 0 < slope < 1 i.e. when the line is plotted between 0° and 45°, the shadow falls more on X-axis i.e. the maximum movement takes place along X-axis ( see, fig-1 ) while for slope > 1 ( when line is plotted between 45° and 90° ), the shadow of line falls more on the Y-axis, thus making it the axis of maximum movement, as shown in fig-2.
In other words, If ∆x = x2 − x1 and ∆y = y2 − y1 , we define the driving axis (DA) to be the x-axis if |∆x| ≥ |∆y|, and the y-axis if |∆y| > |∆x|. The DA is used as the “axis of control” for the algorithm and is the axis of maximum movement. Within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit. The coordinate corresponding to the other axis (usually denoted the passive axis or PA) is only incremented as needed.
The Bresenham’s Line Algorithm for 0 < slope ≤ 1
● input: line endpoints at (X1,Y1) and (X2, Y2)
● X1 < X2
● line slope ≤ 45°, i.e. 0 < m ≤ 1
● x coordinate is incremented in steps of 1, y coordinate is computed
● generic line equation: y = mx + b
The choice for the start point is purely arbitrary, it can be either of (X1,Y1) and (X2,Y2) points. Here as we have restricted the slope m for now to 0 <= m <=1 and assumed X1 < X2, 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 ( xi, yi), the next ideal pixel must be chosen between ( xi+1 , yi) or ( xi+1, yi+1 ). These pixels represent the one just to the right and the one to the right and one up pixel, respectively as shown.
To find the best "next pixel", first we must find the distances to the two available choices from the ideal location (of the real line).
Distance between pixel-to-right and ideal pixel is:
d1 = y - yi
And the distance between pixel-to-right-and-up and ideal pixel is:
d2 = (yi+1) - y
So we can simply choose subsequent pixels based on the following:
- if d1<=d2 ( i.e. the pixel (xi+1, yi) shown in Fig-3 is closer to the ideal location of line ), then choose pixel-to-right: ( xi+1, yi )
- if d1>d2 ( i.e. the pixel (xi+1, yi+1) shown in Fig-3 is closer to the ideal location of line ), then choose pixel-to-right-and-up: ( xi+1, yi+1 )
In order 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.
Instead of comparing the two values to each other, we can simply evaluate d1-d2 and test the sign to determine which to choose.
- If d1 > d2 then d1-d2 will be strictly positive, and if d1-d2 is strictly positive, we will choose pixel-to-right-and-up.
- If d1-d2 is negative or zero, we will choose pixel-to-right.
d1-d2 = y - yi - ( (yi+1) - y ) = y - yi - (yi+1) + y
Geometric location of the line at x-coordinate xi+1 = xi + 1 is:
y = m(xi + 1 ) + b
Thus, substituting y = m(xi + 1) + b, we get
d1 – d2 = m(xi + 1 ) + b - yi - yi – 1 + m(xi + 1 ) + b = 2m(xi + 1 ) – 2yi + 2b – 1
The last equation can be reduced by the slope m and substituting as follows:
m = dY/dX
where dY = abs(Y2 – Y1 ) and dX = abs(X2 – X1), so now we have
d1-d2 = 2(dY/dX) (xi + 1) - 2yi + 2b - 1
d1-d2 = 2(dY/dX) xi + 2(dY/dX) - 2yi + 2b - 1
Multiplying this equation by dX will remove the divisions (all integer operations for faster and efficient computing) and will still keep the same sign for the decision because dX variable is always positive (dX = abs(X2 – X1) – absolute value).
This creats a new decision variable pi = dX (d1-d2).
pi = dX ( d1 – d2) = dX[ 2m(xi + 1 ) – 2yi + 2b – 1 ] = dX[ 2 ⋅ (dY / dX ) ⋅ (xi + 1 ) – 2yi + 2b – 1 ] = 2⋅dY⋅ (xi + 1 ) – 2⋅dX⋅yi + 2⋅dX⋅b – dX = 2⋅dY⋅xi + 2⋅dY – 2⋅dX⋅yi + 2⋅dX⋅b – dX = 2⋅dY⋅xi– 2⋅dX⋅yi + 2⋅dY + 2⋅dX⋅b – dX
Note that the underlined part is constant (it does not change during iteration), we call it c, i.e.
c = 2⋅dY + 2⋅dX⋅b – dX
Hence we can write an expression for pi as:
pi = 2⋅dY⋅xi– 2⋅dX⋅yi + c
Because the sign of pi is the same as the sign of d1 – d2, we could use it inside the loop to decide whether to select pixel at (xi + 1, yi ) or at (xi + 1, yi +1). Note that the loop will only include integer arithmetic. There are now 6 multiplications, two additions and one selection in each turn of the loop.
However, we can do better than this, by defining pi recursively.
pi+1 = 2⋅dY⋅xi+1– 2⋅dX⋅yi+1 + c pi+1 – pi = 2⋅dY⋅xi+1– 2⋅dX⋅yi+1 + c - (2⋅dY⋅xi – 2⋅dX⋅yi + c ) = 2dY ⋅ (xi+1 – xi) – 2dX ⋅ (yi+1 – yi) xi+1 – xi = 1, always pi+1 – pi = 2dY – 2dX ⋅ (yi+1 – yi)
Recursive definition for pi:
pi+1 = pi + 2dY – 2dX ⋅ (yi+1 – yi)
where yi+1 – yi can be either 0 ( when the next pixel is plotted at the same y-
coordinate, i.e. d1 – d2 < 0 ) ; or 1 ( when the next pixel is plotted at the next y-
coordinate, i.e. d1 – d2 > 0). Therefore the final recursive definition for pi will be
based on choice, as follows ( remember that the sign of pi is the same as the sign of d1 – d2 ):
if pi < 0, pi+1 = pi + 2∆y
if pi > 0, pi+1 = pi + 2∆y – 2∆x
At this stage the basic algorithm is defined. We only need to calculate the initial value for parameter pi.
pi = 2⋅dY⋅xi– 2⋅dX⋅yi + 2⋅dY + 2⋅dX⋅b – dX p0 = 2⋅dY⋅x0– 2⋅dX⋅y0 + 2⋅dY + 2dX⋅b – dX
For the initial point on the line:
y0 = mx0 + b
b = y0 – (dY/dX) ⋅ x0
Substituting the above for b, we get:
p0 = 2⋅dY⋅x0– 2⋅dX⋅y0 + 2⋅dY + 2dX⋅ [ y0 – (dY/dX) ⋅ x0 ] – dX = 2⋅dY⋅x0 – 2⋅dX⋅y0 + 2⋅dY + 2.dX⋅y0 – 2dX⋅ (dY/dX) ⋅ x0 – dX = 2⋅dY⋅x0 – 2⋅dX⋅y0 + 2⋅dY + 2dX⋅y0 – 2.dY⋅x0 – dX = 2⋅dY⋅x0 – 2dY⋅x0 – 2⋅dX⋅y0 + 2dX⋅y0 + 2⋅dY – ∆x = 2⋅dY – dX