Home »
Computer Graphics
Bresenham's Line Drawing Algorithm in Computer Graphics
Computer Graphics | Bresenham's Line Drawing Algorithm: In this tutorial, we will learn about the Bresenham's line drawing algorithm. Also, we will be learning about how it is implemented in drawing a line by defining its entire algorithm, and also by taking some examples. Finally, we would be discussing the advantages and disadvantages of this algorithm.
By Monika Sharma Last updated : April 05, 2024
Bresenham's algorithm was proposed to overcome the drawbacks of the DDA algorithm. First, let us see what the drawbacks of DDA algorithm were,
Drawbacks of DDA algorithm:
The only drawback of the DDA algorithm was that it produces floating-point results which reduces the overall complexity. This problem was solved by Bresenham's line drawing algorithm.
Introduction to Bresenham's Algorithm
Bresenham's line drawing algorithm is a second method of generating a line that was proposed after the DDA algorithm to overcome its limitations and drawbacks. It was developed by J.E. Bresenham in 1962. This algorithm is used for calculating intermediate coordinate points between the given source and ending points by only using integer addition and subtraction.
This algorithm determines the points which should be selected to form a close approximation to a line between two points.
It is also an incremental method for creating a line.
It is faster than the DDA algorithm as it does not involves the use of heavy operations such as multiplication and division.
Working of the Bresenham's Algorithm
Suppose we have to draw a line PQ with coordinates P (x1, y1) and Q (x2, y2).
To draw the line using Breshenam's line drawing algorithm, first of all, calculate the slope of the line from the given coordinates by using,
m = dy/dx
Where,
dy = x2 - x1
dx = y2 - y1
There can be three values of slope (m) i.e.
a. m < 1
b. m > 1
c. m = 1
On the basis of the value of the slope, the decision parameter is calculated which gives the decision about the selection of the next pixel point which has the least distance from the true line.
We'll be deriving the decision parameter Pk for slope (m < 1), to make things clear.
Derivation of the decision parameter Pk
Let us consider a straight line passing through a point A (xk+1, y),
Where,
xk+1 = xk + 1
and y satisfies the equation of the line i.e.
y = m (xk + 1) + c ------(1)
The next pixel to the line will be either to its top or to its bottom.
If we choose the top pixel, the points at B will become,
xk+1 = xk + 1 and y = yk + 1
If we choose bottom pixel, the points at C will become,
xk+1 = xk + 1 and y = yk
Since Bresenham's algorithm depends upon the distance, let's calculate it between A and B; and A and C.
For A and B: let the distance be denoted as s.
s = ( yk + 1 ) - y
For A and C: let the distance be denoted as t.
t = y - yk
Now consider their difference:
(t – s) = y - yk - [ (yk + 1) - y]
= 2y - 2yk - 1 ------(2)
When (t - s) < 0 => t < s, then the closest pixel will be C.
When (t - s) > 0 => s < t, then the closest pixel will be B.
Putting the value of eq.(1) in eq.(2);
t – s = 2m ( xk + 1 ) + 2c - 2yk - 1
Now, substituting the value of m;
t – s = 2dy ( xk + 1 ) / dx + 2c - 2yk - 1
To remove dx from denominator, multiply dx on both sides;
dx (t - s) = dx ( 2dy ( xk + 1 ) / dx + 2c - 2yk – 1 )
let Pk = dx (t - s), thus introducing the decision variable
Pk = 2dy . xk - 2dx . yk + b
B = 2dy + dx ( 2c – 1 )
Let us calculate next decision variable:
Pk+1 = 2dy . xk+1 - 2dx . yk+1 + b
Now, solve the difference Pk+1 - Pk
Pk+1 - Pk = 2dy . xk+1 - 2dx . yk+1 + b - ( 2dy . xk - 2dx . yk + b )
= 2dy . xk+1 - 2dx . yk+1 - 2dy . xk - 2dx . yk
Since xk+1 = xk + 1
Pk+1 - Pk = 2dy . (xk + 1) - 2dx . yk+1 - 2dy . xk - 2dx . yk
Pk+1 = Pk + 2dy - 2dx . yk+1 - 2dx . yk
Special Cases:
When Pk >= 0 => yk+1 = yk + 1 i.e. point B is chosen
Pk+1 = Pk + 2dy - 2dx
When Pk < 0 => yk+1 = yk i.e. point C is chosen
Pk+1 = Pk +2dy
Now, we will calculate the initial decision variable by using
P0 = dx ( 2dy ( x0 + 1 ) / dx + 2c - 2y0 – 1 )
Put c = y0 - x0. ( dy / dx )
We get
P0 = 2dy – dx
Bresenham's Algorithm
Step1: Start
Step2: Declare x1, y1, x2, y2.
Step3: Calculate dx = x2 - x1
Dy = y2 - y1
Step 4: Calculate slope, m = dy / dx.
Step5: For m < 1: Calculate initial decision variable: P = 2dy - dx.
Step6: while (x1 <= x2)
if(P < 0):
xk = xk + 1
P = P + 2dy
yk = yk
else :
xk = xk + 1
P = P + 2dy - 2dx
yk = yk + 1
Step 7: Plot ( xk , yk )
Step 8: End
Advantages of Bresenham's Algorithm
- It is faster because it does not involve floating-point calculations.
- It involves only integer arithmetic. Hence, it is easier to implement.
Disadvantages of Bresenham's Algorithm
- It also does not provide smooth lines though accuracy has been improved.