##

**Bresenham's Circle Drawing Algorithm Derivation**

**Bresenham circle drawing algorithm is used to determine the next pixel of screen to be illuminated while drawing a circle by determining the closest nearby pixel.**

**Let us first take a look how a circle is drawn on a pixel screen**

**(this is how pixel graph is represented)**

**As Circles are symmetrical so the values of y-intercept and x-intercept are**

*Here,*

*Radius = OA = r*

*Due to symmetrical property of Circle we don't need to calculate all the pixels of all the octets and quadrants*

*We need to find the pixels of only one octet, rest we can conclude through this.*

^{Lets take the Octet 2 which is in quadrant 1}**here both x and y are positive**

**here the initial pixel would be (0,y) coordinate**

^{}

^{At point R both the value of both x and y coordinates would be same as R is at same distance of Both X and Y axis.}

^{ }

^{ }##
**Derivation of Bresenham circle algorithm:**

**Let's say our circle is at some random pixel**

**P**

**whose coordinates are**

**(x**

_{k, }y_{k})**.**

**Now we need to find out our next pixel.**

**Note- This is octet 2 so here x can never be decremented as per properties of a circle but y either needs to decremented or to be kept same. y is needed to be decided.**

**Here it needs to decide whether go with N or S.**

**For this bresenham's circle drawing algorithm will help us to decide by calculating the difference between radius and the coordinates of the next pixels.**

**The shortest of d1 and d2 will help us Decide our next pixel.**

**note-**

^{ }**x**

_{k+1 }= x_{k }+1**As**

**x**

_{k+1}

_{ }**is the next consecutive pixel of**

**x**

_{k}**similarly**

**y**

_{k-1}

_{ }**=**

**y**

_{k }-1

**Equation of Circle with Radius**

**r**

**(x– h)**

^{2}+ (y – k)^{2}= r^{2}

*When coordinates of centre are at Origin i.e.,*

*(h=0, k=0)*

**x**

^{2}+ y^{2}= r^{2}

^{ }**(Pythagoras theorem)**

**Function of Circle Equation**

*F(C)*

*=*

**x**

^{2}+ y^{2}- r^{2}**Function of Circle at N**

**F(N)**

**=**

**(**

**x**

_{k+1})^{2 }+ (

**y**)_{k}^{2 }– r^{2 }

^{ }**(**

**Positive**

**)**

**Here the value of F(N) will be positive because N is out-side the circle**

**that makes (**

**x**)_{k+1}

^{2 }+ (

**y**)_{k}^{2}

^{ }**Greater than**

**r**

^{2}**Function of Circle at S**

####
** F(S) ****= ****(****x**_{k+1})^{2 }+ (**y**_{k-1})^{2 }– r^{2}^{ }**(****Negative****)**

**x**)

_{k+1}^{2 }+ (

**y**)

_{k-1}^{2 }– r

^{2}

^{ }

####
**Here the value of F(S) will be Negative because S is in-side the circle** **that makes**** ****(****x**_{k+1})^{2 }+ (**y**_{k-1})^{2 }**Less than**** ****r**^{2}

**x**)

_{k+1}^{2 }+ (

**y**)

_{k-1}^{2 }

^{2}

**Now we need a decision parameter which help us decide the next pixel**

**Say**

**D**

_{k}_{}

**And ,**

**D**

_{k }**=**

*F(N)+F(S)***Here either we will get the positive or negative value of**

**D**

_{k}**So if**

**D**

_{k }< 0**that means the negative**

**F(S)**

**is bigger then the positive**

**F(N)**

**, that implies Point**

**N**

**is closer to the circle than point**

**S**

**. So we will select pixel**

**N**

**as our next pixel.**

**and if**

**D**

_{k }> 0**that means positive**

**F(N)**

**is bigger and**

**S**

**is more closer as**

**F(S)**

**is smaller. So we will Select**

**S**

**as our next pixel.**

**Now lets find**

**D**

_{k}

_{}####
**D**_{k}_{ }**=**** ****(****x**_{k+1})^{2 }+ (**y**_{k})^{2 }– r^{2 }**+ (****x**_{k+1})^{2 }+ (**y**_{k-1})^{2 }– r^{2}

_{k}

_{ }

**x**)

_{k+1}^{2 }+ (

_{k})

^{2 }– r

^{2 }

**x**)

_{k+1}^{2 }+ (

**y**)

_{k-1}^{2 }– r

^{2}

^{ }**(**

**replacing**

^{ }**x**

_{k+1}

_{ }**with**

**x**

_{k }+ 1

**and**

**y**

_{k-1}

_{ }**with**

**y**

_{k }-1**)**

**=**

**(**

**x**

_{k }+ 1)^{2 }+ (

**y**)_{k}^{2 }– r^{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}

**----- (**

*i)***Now lets find**

**D**

_{k+1}

**(Replacing every k with k+1)**

####
** ****D**_{k+1 }= 2(**x**_{k+1 }+ 1)^{2 }+(**y**_{k+1})^{2 }+ (y_{k+1 }-1)^{2 }– 2r^{2}

_{k+1 }= 2(

_{k+1 }+ 1)

^{2 }+(

**y**)

_{k+1}^{2 }+ (y

_{k+1 }-1)

^{2 }– 2r

^{2}

**= 2(**

**x**

_{k+1 }+ 1)^{2 }+ (

**y**)_{k+1}^{2 }+ (y_{k+1 }-1)^{2 }– 2r^{2}**(Replacing**

**x**

_{k+1}

**with**

**x**

_{k }+ 1

**but now we can’t replace**

**y**

_{k+1}

**because we don’t know the exact value of**

**y**

_{k}

_{ }**)**

**=**

**2(**

**x**

_{k}+1+ 1)^{2 }+ (

**y**)_{k+1}^{2 }+ (y_{k+1 }-1)^{2 }– 2r^{2}

^{ }**=**

**2(**

**x**

_{k}+2)^{2 }+ (

**y**)_{k+1}^{2 }+ (y_{k+1 }-1)^{2 }– 2r^{2}

^{ }**----- (**

*ii)*

^{}

^{ }**Now to find out the decision parameter of next pixel i.e.**

**D**

_{k+1}**We need to find**

**D**

_{k+1 }- D_{k}

**= (**

*ii) - (i)*

####
** ****= 2(****x**_{k}+2)^{2 }+ (**y**_{k+1})^{2 }+ (y_{k+1 }-1)^{2 }– 2r^{2 }

_{k}+2)

^{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}]

_{k }+ 1)

^{2 }+ (

**y**)

_{k}^{2 }+ (y

_{k }-1)

^{2 }– 2r

^{2}]

**= 2**

**(**

**x**)_{k}^{2}_{ }+ 8x_{k }+ 8 + (

**y**)_{k+1}^{2 }+ (

**y**)_{k+1}^{2 }- 2y_{k+1 }+ 1 - 2r^{2}####
** - ****2****x**_{k }- 4x_{k}^{ }– 2 - (**y**_{k})^{2 }- (**y**_{k})^{2} + 2y_{k}^{ }- 1 ^{ }+ 2r^{2 }

_{k }- 4x

_{k}

^{ }– 2 - (

_{k})

^{2 }- (

**y**)

_{k}^{2}+ 2y

_{k}

^{ }- 1

^{ }+ 2r

^{2 }

**= 4**

**x**

_{k }+ 2(

**y**)_{k+1}^{2 }- 2y_{k+1 }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6**D**

_{k+1 }= D_{k }+ 4**x**

_{k }+ 2(

**y**)_{k+1}^{2 }- 2y_{k+1 }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6

**----- (**

*iii)*

**If**

**(**

**D**

_{k }< 0**)**

**then we will choose N point as discussed.**

**i.e.**

**(**

**x**

_{k+1},_{ }y_{k}**)**

**that means our next**

**x**

**coordinate is**

**x**

_{k+1}

_{ }**and next y coordinate is**

**y**

_{k}

_{ }**i.e.**

**y**

_{k+1}

_{ }**=**

**y**

_{k}

_{, }**putting**

**y**

_{k}

_{ }**in**

**(**

*iii)***in replace of**

**y**

_{k+1}

**now,**

**D**

_{k+1 }=_{ }D_{k }+ 4**x**

_{k }+ 2(

**y**)_{k}^{2 }- 2y_{k }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6

**= D**

_{k }+ 4**x**

_{k }+ 6**If**

**(**

**D**

_{k }> 0**)**

**then we will choose S point.**

**i.e.**

**(**

**x**

_{k+1},_{ }y_{k-1}**)**

**that means our next**

**x**

**coordinate is**

**x**

_{k+1}

_{ }**and next y coordinate is**

**y**

_{k}

_{ }**i.e.**

**y**

_{k+1 }**=**

**y**

_{k-1}

_{ }**putting**

**y**

_{k-1}

_{ }**in**

**(**

*iii)***in replace of**

**y**

_{k+1}

_{}**now,**

**D**

_{k+1 }= D_{k }+ 4**x**

_{k }+ 2(

**y**)_{k-1}^{2 }- 2y_{k-1 }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6**Now we know**

**y**

_{k-1 }= y_{k }– 1**therefore,**

**D**

_{k+1 }= D_{k }+ 4**x**

_{k }+ 2(y_{k }-1)^{2 }- 2(y_{k }-1)_{ }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6**=**

**D**

_{k }+ 4**x**

_{k }+ 2(**y**

_{k})_{ }^{2 }+ 2 - 4y_{k}^{ }- 2y_{k }+2_{ }- 2(

**y**)_{k}^{2 }- 2y_{k}+ 6**=**

**D**

_{k }+ 4**x**

_{k }- 4y_{k }+ 10

_{ }**=**

_{ }**D**

_{k }+ 4(**x**

_{k }- y_{k})_{ }+ 10

**Now to find initial decision parameter means starting point that is**

**(0,r)**

**,**

**value of**

**y**

**is**

**r**

**Putting**

**(0,r)**

**in**

**(**

*i)*

**D**

_{k}= 2(**x**

_{k }+ 1)^{2 }+ (

**y**)_{k}^{2 }+ (y_{k }-1)^{2 }– 2r^{2}**D**

_{0}**= 2(**

**0**

_{ }+ 1)^{2 }+ r^{2 }+ (r_{ }-1)^{2 }– 2r^{2}

^{ }**= 2 + r**

^{2 }+r^{2}+ 1 – 2r**– 2r**

^{2}

^{ }**= 3-2r**

**Hence we have derived the bresenham’s Circle drawing technique.**

**More>>**

**Bresenham circle drawing algorithm**

**Bresenhams Circle drawing program in C**

**Bresenhams line drawing derivation**

**Bresenhams Line drawing program in C**

**Mid point circle drawing algorithm's derivation**

**What is computer graphics**

## Comments

## Post a Comment