Bresenham Circle Drawing Algorithm


Computer Graphics / Monday, November 5th, 2018
(Last Updated On: November 5, 2018)

We have already discussed DDA and Bresenham Line Drawing Algorithm, now in this article we are going to learn Bresenham Circle Drawing Algorithm.

Bresenham Circle Drawing Algorithm

We know, circle itself has eight-way symmetry where any point P on the boundary is reflected seven times shown in fig (A) as a result, scan conversion of 1/8 th of the circle is enough to generate its remaining seven octants.

Bresenhams Circle 01
Fig (A)

Bresenham has modified line scan conversion algorithm using mid-point to generate circles. For circle with radius R and origin at (0, 0), the equation is given by

\[f(x,y)={{x}^{2}}+{{y}^{2}}-{{R}^{2}}\]

Bresenhams Circle 02
Fig (B)

Referring to fig(B) for the current mid-point MC,

\[f\left( {{M}_{C}} \right)=f\left( x+1,y-\frac{1}{2} \right)\]

\[\Rightarrow f\left( {{M}_{C}} \right)={{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}}……..(1)\]

If f(MC) < 0, E is chosen, else SE is selected. Let us consider these two cases separately. If E is chosen, for the next mid-point MnE,

\[f\left( M_{n}^{E} \right)=f\left( x+2,y-\frac{1}{2} \right)\]

\[\Rightarrow f\left( M_{n}^{E} \right)={{\left( x+2 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}}……..(2)\]

Therefore, in this case, the increment is

\[\Delta E=f\left( M_{n}^{E} \right)-f\left( {{M}_{C}} \right)\]

\[=\left\{ {{\left( x+2 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}-\left\{ {{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}\]

\[\therefore \Delta E=2x+3……..(3)\]

If SE is chosen, again for the next mid-point MnSE,

\[f\left( M_{n}^{SE} \right)=f\left( x+2,y-\frac{3}{2} \right)\]

\[\Rightarrow f\left( M_{n}^{E} \right)={{\left( x+2 \right)}^{2}}+{{\left( y-\frac{3}{2} \right)}^{2}}-{{R}^{2}}……..(4)\]

Therefore, the increment in this case is

\[\Delta SE=f\left( M_{n}^{SE} \right)-f\left( {{M}_{C}} \right)\]

\[=\left\{ {{\left( x+2 \right)}^{2}}+{{\left( y-\frac{3}{2} \right)}^{2}}-{{R}^{2}} \right\}-\left\{ {{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}\]

\[\therefore \Delta SE=2x-2y+5……..(5)\]

Now similar to line scan conversion, the problem remains to detect the first mid-point which should be at (1. R – ½ ) for circle of radius R and at center (0, 0).

Bresenhams Circle 03

Then,

\[f\left( 1,R-\frac{1}{2} \right)=1+{{R}^{2}}-R+\frac{1}{4}-{{R}^{2}}=\frac{5}{4}-R\]

Bresenham Circle Drawing Algorithm Implementation in C

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *