Bresenham’s Circle Drawing Algorithm in Computer Graphics
Bresenham’s algorithm is also used for circle drawing. It is known as Bresenham’s circle drawing algorithm. It helps us to draw a circle. The circle generation is more complicated than drawing a line. In this algorithm, we will select the closest pixel position to complete the arc. We cannot represent the continuous arc in the raster display system. The different part of this algorithm is that we only use arithmetic integer. We can perform the calculation faster than other algorithms.
Let us assume we have a point p (x, y) on the boundary of the circle and with r radius satisfying the equation f_{c }(x, y) = 0
As we know the equation of the circle is –
f_{c }(x, y) = x^{2 }+ y^{2} = r^{2}
If
f_{c }(x, y) < 0
then
The point is inside the circle boundary.
If
f_{c }(x, y) = 0
then
The point is on the circle boundary.
If
f_{c }(x, y) > 0
then
The point is outside the circle boundary.
We assume,
The distance between point P_{3} and circle boundary = d_{1}
The distance between point P_{2} and circle boundary = d_{2}
Now, if we select point P_{3} then circle equation will be-
d_{1 }= (x_{k }+1)^{2} + (y_{k})^{2 }– r^{2 } {Value is +ve, because the point is outside the circle}
if we select point P_{2} then circle equation will be-
d_{2 }= (x_{k }+1)^{2} + (y_{k }-1)^{2 }– r^{2 }{Value is -ve, because the point is inside the circle}
Now, we will calculate the decision parameter (d_{k}) = d_{1 }+ d_{2}
d_{k }=(x_{k }+1)^{2} + (y_{k})^{2 }– r^{2 }+ d_{2 }+ (x_{k }+1)^{2} + (y_{k }-1)^{2 }– r^{2}
= 2(x_{k }+1)^{2} + (y_{k})^{2}+ (y_{k }-1)^{2 }– 2r^{2} …………………… (1)
If
d_{k }< 0
then
Point P_{3} is closer to circle boundary, and the final coordinates are-
(x_{k +1}, y_{k}) = (x_{k }+1, y_{k})
If
d_{k }>= 0
then
Point P_{2} is closer to circle boundary, and the final coordinates are-
(x_{k +1}, y_{k}) = (x_{k }+1, y_{k }-1)
Now, we will find the next decision parameter (d_{k+1})
(d_{k+1}) = 2(x_{k+1 }+1)^{2} + (y_{k+1})^{2}+ (y_{k+1 }-1)^{2 }– 2r^{2} …………………… (2)
Now, we find the difference between decision parameter equation (2) - equation (1) (d_{k+1}) – (d_{k}) = 2(x_{k+1}+1)^{2} + (y_{k+1})^{2}+ (y_{k+1 }–1)^{2 }– 2r^{2 }– 2(x_{k }+1)^{2} + (y_{k})^{2}+ (y_{k}– 1)^{2 }– 2r^{2} (d_{k+1}) = d_{k }+ 4x_{k }+ 2(y_{k+1}^{2}– y_{k}^{2}) – (y_{k+1 }– y_{k}) + 6
Now, we check two conditions for decision parameter-
Condition 1: If
d_{k }< 0
then
y_{k+1 }= y_{k} (We select point P_{3})
Condition 2: If
d_{k }>= 0
then
y_{k+1 }= y_{k}-1 (We select point P_{3})
Now, we calculate initial decision parameter (d_{0})
d_{0 }= d_{1 }+ d_{2}_{}
d_{0} = {1^{2 }+r^{2}– r^{2}} + {1^{2 }+(r – 1)^{2} – r^{2}}
d_{0} = 3 – 2r
Algorithm of Bresenham’s Circle Drawing
Step 1: Start.
Step 2: First, we allot the starting coordinates (x_{1}, y_{1}) as follows-
x_{1} = 0
y_{1 }=r
Step 3: Now, we calculate the initial decision parameter d_{0 }-
_{ }d_{0 }= 3 – 2 x r
Step 4: Assume,the initial coordinates are (x_{k}, y_{k})
The next coordinates will be (x_{k+1}, y_{k+1})
Now, we will find the next point of the first octant according to the value of the decision parameter (d_{k}).
Step 5: Now, we follow two cases-
Case 1: If
d_{k }< 0
then
x_{k+1 }=x_{k }+ 1
y_{k+1 }=y_{k }
d_{k+1 }= d_{k }+ 4x_{k+1 }+ 6
Case 2: If
d_{k }>= 0
then
x_{k+1 }=x_{k }+ 1
y_{k+1 }=y_{k }–1
d_{k+1 }= d_{k }+ 4(x_{k+1 }– y_{k+1})+ 10
Step 6: If the center coordinates (x_{1}, y_{1}) is not at the origin (0, 0), then we will draw the points as follow-
X coordinate = x_{c }+ x_{1 }
y coordinate = y_{c }+ y_{1 }{x_{c }andy_{c }representsthe current value of x and y coordinate}
Step 7: We repeat step 5 and 6 until we get x>=y.
Step 8: Stop.
Example: The radius of a circle is 8, and center point coordinates are (0, 0). Apply bresenham’s circle drawing algorithm to plot all points of the circle.
Solution:
Step 1: The given stating points of the circle (x_{1, }y_{1}) = (0, 0)
Radius of the circle (r) = 8
Step 2: Now, we will assign the starting point (x_{1, }y_{1}) as follows-
x_{1 }= 0
y_{1 }= r (radius) = 8
Step 3: Now, we will calculate the initial decision parameter (d_{0})
_{ }d_{0 }= 3 – 2 x r
d_{0} = 3 – 2 x 8
d_{0} = -13
Step 4: The value of initial parameter d_{0 }< 0. So, case 1 is satisfied.
Thus,
x_{k+1 }=x_{k }+ 1 = 0 + 1 = 1
y_{k+1 }=y_{k }= 8
d_{k+1 }= d_{k }+ 4x_{k+1 }+ 6 = -13 + (4 x 1) + 6 = -3
Step 5: The center coordinates are already (0, 0) so we will move to next step.
Step 6: Follow step 4 until we get x >= y.
Table for all points of octant 1:
d_{k} | d_{k+1} | (x_{k+1},y_{k+1}) |
(0, 8) | ||
-13 | -3 | (1, 8) |
-3 | 11 | (2, 8) |
11 | 5 | (3, 7) |
5 | 7 | (4, 6) |
7 | (5, 5) |
Now, we will calculate the coordinates of the octant 2 by swapping the x and y coordinates.
Coordinates of Octant 1 | Coordinates of Octant 2 |
(0, 8) | (5, 5) |
(1, 8) | (6, 4) |
(2, 8) | (7, 3) |
(3, 7) | (8, 2) |
(4, 6) | (8, 1) |
(5, 5) | (8, 0) |
Thus, we will calculate all points of the circle with respect to octant 1.
Quadrant 1 (x, y) | Quadrant 2 (-x, y) | Quadrant 3 (-x, -y) | Quadrant 4 (x, -y) |
(0, 8) | (0, 8) | (0, -8) | (0, -8) |
(1, 8) | (-1, 8) | (-1, -8) | (1, -8) |
(2, 8) | (-2, 8) | (-2, -8) | (2, -8) |
(3, 7) | (-3, 7) | (-3, -7) | (3, -7) |
(4, 6) | (-4, 6) | (-4, -6) | (4, -6) |
(5, 5) | (-5, 5) | (-5, -5) | (5, -5) |
(6, 4) | (-6, 4) | (-6, -4) | (6, -4) |
(7, 3) | (-7, 3) | (-7, -3) | (7, -3) |
(8, 2) | (-8, 2) | (-8, -2) | (8, -2) |
(8, 1) | (-8, 1) | (-8, -1) | (8, -1) |
(8, 0) | (-8, 0) | (-8, 0) | (8, 0) |
Advantages of Bresenham’s Circle Drawing Algorithm
- It is simple and easy to implement.
- The algorithm is based on simple equation x^{2 }+ y^{2 }= r^{2}.
Disadvantages of Bresenham’s Circle Drawing Algorithm
- The plotted points are less accurate than the midpoint circle drawing.
- It is not so good for complex images and high graphics images.
Related Posts:
- Bresenham’s Line Drawing Algorithm in Computer Graphics
- Line Drawing Algorithm in Computer Graphics
- Mid-Point Line Drawing Algorithm in Computer Graphics
- Midpoint Circle Drawing Algorithm in Computer Graphics
- DDA line Drawing Algorithm in Computer Graphics
- Line Clipping in Computer Graphics
- Animation in Computer Graphics
- Image Representation in Computer Graphics
- Pointing and Positioning Technique Computer Graphics
- Scan Conversion of a Circle Computer Graphics