Bresenham’s Line Drawing Algorithm in Computer Graphics
This algorithm was introduced by “Jack Elton Bresenham” in 1962. This algorithm helps us to perform scan conversion of a line. It is a powerful, useful, and accurate method. We use incremental integer calculations to draw a line. The integer calculations include addition, subtraction, and multiplication.
In Bresenham’s Line Drawing algorithm, we have to calculate the slope (m) between the starting point and the ending point.
![Bresenham’s Line Drawing Algorithm](https://www.tutorialandexample.com/wp-content/uploads/2020/02/Bresenham’s-Line-Drawing-Algorithm.png)
As shown in the above figure let, we have initial coordinates of a line = (xk, yk)
The next coordinates of a line = (xk+1, yk+1)
The intersection point between yk and yk+1 = y
Let we assume that the distance between y and yk = d1
The distance between y and yk+1 = d2
Now, we have to decide which point is nearest to the intersection point.
If m < 1
then x = xk+1 { Unit Interval}
y = yk+1 { Unit Interval}
As we know the equation of a line-
y = mx +b
Now we put the value of x into the line equation, then
y = m(xk+1) +b …………. (1)
The value of d1 = y - yk
Now we put the value of d1 in equation (1).
y = m (xk+1) +b - yk
Now, we again put the value of y in the previous equation then we got,
d2 = yk+1 – y
= yk + 1 – m (xk+1) – b
Now, we calculate the difference between d1 – d2
If d1 < d2
Then yk+1 = yk {we will choose the lower pixel as shown in figure}
If d1 => d2
Then yk+1 = yk+1 {we will choose the upper pixel as shown in figure}
Now, we calculate the values of d1 - d2
(d1 - d2)= m (xk+1) +b - yk - yk - 1 + m (xk+1) + b
We simplified the above equation and replaced the m with ?y/?x.
(d1 - d2) = 2 m (xk+1) -2yk + 2b-1
We multiplied ?x at both side then we got,
?x (d1 - d2) = ?x (2m (xk+1) -2yk + 2b-1)
We consider ?x (d1 - d2) as a decision parameter (Pk), so
pk = ?x (d1 - d2)
After calculation we got,
Pk = 2?yxk + 2?y - 2?xyk +?x (2b-1)
Then, the next coordinate of pk
pk+1 = 2?yxk+1 + 2?y - 2?xyk+1 +?x (2b-1)
Now, the difference between pk+1 – pk then,
pk+1 – pk = 2?y (xk+1-xk) – 2?x (yk+1-yk)
pk+1 = pk + 2?y (xk+1-xk) – 2?x (yk+1-yk) {Decision parameter coordinate}
Now, we put the value of xk+1 in above equation then we got,
pk+1 = pk + 2?y – 2?x (yk+1 - yk) {New decision parameter when m <1}
Similarly, if m >1, the new decision parameter for next coordinate will be
pk+1 = pk + 2?y – 2?x (xk+1 - xk) {New decision parameter when m >1}
If pk >= 0 {For coordinate y}
Then,
yk+1 = yk+1 {We will choose the nearest yk+1 pixel}
The next coordinate will be (xk+1, yk+1)
If pk < 0
Then,
yk+1 = yk {We will choose the nearest yk pixel}
The next coordinate will be (xk+1, yk)
Similarly,
If pk >= 0 {For coordinate x}
Then,
xk+1 = xk+1 {We will choose the nearest xk+1 pixel}
The next coordinate will be (xk+1, yk+1)
If pk < 0
Then,
xk+1 = xk {We will choose the nearest xk pixel}
The next coordinate will be (xk, yk+1)
Algorithm of Bresenham’s Line Drawing Algorithm
Step 1: Start.
Step 2: Now, we consider Starting point as (x1, y1) and endingpoint (x2, y2).
Step 3: Now, we have to calculate ?x and ?y.
?x = x2-x1
?y = y2-y1
m = ?y/?x
Step 4: Now, we will calculate the decision parameter pk with following formula.
pk = 2?y-?x
Step 5: Theinitial coordinates of the line are (xk, yk), and the next coordinatesare (xk+1, yk+1). Now, we are going to calculate two cases for decision parameter pk
Case 1: If
pk < 0
Then
pk+1 =pk +2?y
xk+1 = xk +1
yk+1 = yk
Case 2: If
pk >= 0
Then
pk+1 =pk +2?y-2?x
xk+1 =xk +1
yk+1 =yk +1
Step 6: We will repeat step 5 until we found the ending point of the line and the total number of iterations =?x-1.
Step 7: Stop.
Example: A line has a starting point (9,18) and ending point (14,22). Apply the Bresenham’s Line Drawing algorithm to plot a line.
Solution: We have two coordinates,
Starting Point = (x1, y1) = (9,18)
Ending Point = (x2, y2) = (14,22)
Step 1: First, we calculate ?x, ?y.
?x = x2 – x1 = 14-9 = 5
?y = y2 – y1 = 22-18 = 4
Step 2: Now, we are going to calculate the decision parameter (pk)
pk = 2?y-?x
= 2 x 4 – 5 = 3
The value of pk = 3
Step 3: Now, we will check both the cases.
If
pk >= 0
Then
Case 2 is satisfied. Thus
pk+1 = pk +2?y-2?x =3+ (2 x 4) - (2 x 5) = 1
xk+1 =xk +1 = 9 + 1 = 10
yk+1 =yk +1 = 18 +1 = 19
Step 4: Now move to next step. We will calculate the coordinates until we reach the end point of the line.
?x -1 = 5 – 1 = 4
pk | pk+1 | xk+1 | yk+1 |
9 | 18 | ||
3 | 1 | 10 | 19 |
1 | -1 | 11 | 20 |
-1 | 7 | 12 | 20 |
7 | 5 | 13 | 21 |
5 | 3 | 14 | 22 |
Step 5: Stop.
![Bresenham’s Line Drawing Algorithm](https://www.tutorialandexample.com/wp-content/uploads/2020/02/Bresenham’s-Line-Drawing-Algorithm2.png)
The Coordinates of drawn lines are-
P1 = (9, 18)
P2 = (10, 19)
P3 = (11, 20)
P4 = (12, 20)
P5 = (13, 21)
P6 = (14, 22)
Advantages of Bresenham’s Line Drawing Algorithm
- It is simple to implement because it only contains integers.
- It is quick and incremental
- It is fast to apply but not faster than the Digital Differential Analyzer (DDA) algorithm.
- The pointing accuracy is higher than the DDA algorithm.
Disadvantages of Bresenham’s Line Drawing Algorithm
- The Bresenham’s Line drawing algorithm only helps to draw the basic line.
- The resulted draw line is not smooth.
Related Posts:
- Bresenham’s Circle Drawing Algorithm in Computer Graphics
- Line Drawing Algorithm in Computer Graphics
- Mid-Point Line Drawing Algorithm in Computer Graphics
- Scan Conversion of a Circle Computer Graphics
- Midpoint Circle Drawing Algorithm in Computer Graphics
- Pointing and Positioning Technique Computer Graphics
- Line Clipping in Computer Graphics
- 3D Rotation in Computer Graphics
- Animation in Computer Graphics
- Image Representation in Computer Graphics