Bresenham’s Circle Generation Algorithm in Computer Graphics

This algorithm is used to generate only one octant of the circle. The other parts are obtained by successive reflections.

• This illustrated in figure. If the first octant ( 0 to 45¬o CCW) is generated, the second 

      octant is obtained by reflection through the line y  = x to yield the first quadrant.

• The results in the first quadrant are reflected through the line x = 0 to obtain those in  

      the 2nd quadrant.

• The combined results in the upper semi circle are reflected through the line y = 0 to 

      complete the circle.

• To derive Bresenham’s circle generation algorithm, consider the first quadrant of an 

      origin centered circle. Notice that if the algorithm begins at x =0 , y =r then for   

      clockwise generation of the circle y is monotonically decreasing function of x in the  

      first quadrant. 

• Similarly, if the algorithm begins at y =0 , x=R then for counter clock wise generation 

      of the circle x is a monotonically decreasing function of y. Here clockwise generation        

      starting at x=0, y=R is chosen.

• The center of the circle and the starting point are both assumed located precisely at 

      pixel element.

Algorithm:

Bresenham’s incremental circle algorithm for the first quadrant all variables are assumed integer.

Initialize the variables.

      xi = 0;

yi = R;

     ri = 2(1-R)

                  Limit =0

while yi ≥ Limit

call setpixel(xi,yi)

determine if case 1 or 2,4 or5 or 3

if  ri < 0 then

δ = 2ri + 2yi – 1

determine whether case 1 or 2

if  δ ≤ 0 then

call mh(xi,yi, ri)

else

call md(xi,yi, ri)

end if

else if ri > 0  then

δ1=2ri + 2xi – 1

determine whether case 4 or 5

if δ1≤0 then

call md(xi,yi, ri)

else

call mv(xi,yi, ri)

end if

else if ri =0 then

call md(xi,yi, ri)

end if

end while

        finish

• Move horizontally

subroutine mh(xi,yi, ri)

xi = xi + 1

ri = ri + 2xi +1

end sub

• Move diagonally

subroutine md(xi,yi, ri)

xi = xi + 1

yi = yi - 1

ri = ri + 2xi -2yi +2

end sub

• Move vertically

subroutine mv(xi,yi, ri)

yi = yi + 1

ri = ri  -2yi +1

end sub

Example:  To illustrate the circle generation algorithm, consider the origin-centered circle of radius 8. Only the first quadrant is generated.

Solution:  initial calculations

xi = 0;

yi = 8

     ri = 2(1-8)

                  Limit =0

     Incrementing through the main loop yields

yi > Limit

continue

setpixel(0,8)

ri<0

δ=2(-14)+2(8)-1=-13

δ<0

call mh(0,8,-14)

x = 0+1=1

ri= -14 +2(1)+1=-11

yi >Limit

continue

setpixel(1,8)

ri<0

δ=2(-11)+2(8)-1=-7

δ<0

call mh(1,8,-11)

x=1+1=2

ri= -11 +2(2)+1=-6

yi >Limit

continue

setpixel(2,8)

…

…

…

continue

Setpixel i δ δ1 x y

       -14 0 8

(0 , 8)

      -11 -13 1 8

(1 , 8)

      -6 -7 2 8

(2 ,8 )

   -12 3 3 7

(3 , 7)

     -3 -11 4 7

(4 ,7 )

     -3 7 5 6

( 5, 6)

      1 5 6 5

( 6,5 )

              9 -11       7 4

(7 ,4 )

      4 3       7 3

(7 , 3)

    18 -7           8 2

(8 ,2 )

    17 19          8 1

(8 ,1 )

     18 17       8 0

(8 ,0 )

---------------------------------------------------------------------

Article By:

GV Prasad
Assoc. Professor

CSE Department 

Sphoorthy Engineering College

Sphoorthy Engineering College