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.
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.
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