Sem 4‎ > ‎CG LAB‎ > ‎0 Algorithms‎ > ‎

3 Bresenham's Circle Algo

posted Jan 7, 2012, 10:40 PM by Neil Mathew   [ updated Jan 8, 2012, 7:40 AM ]

Explanation:


File:Bresenham circle.svg




The program should make use of basic concept of circle generation algorithm.

This algorithm does only integer arithmetic which makes it faster than floating point. 

We are creating only one octant i.e. from 90 to 45 degree.
We derive other seven octants of circle by symmetry property.

The circle is generated by considering center point as origin with radius ‘r’.
The algorithm calculates one new pixel per step.


One Octant (1/8 circle):

 (x,y) 

symmetry points:

(-x,y)    (x,-y)     (-x,-y)     (y,x)     (-y,x)      (y,-x)     (-y,-x)

(Plotting need not be counterclockwise in what I've done)

The above is assuming the origin is at centre.  (0+x,0+y) 
When a centre (xc,yc) is provided by the user, the points are:

(xc+x, yc+y)    (xc-x, yc+y)      ( xc+x , yc-y )      ( xc-x , yc-y )    
 
 
xc+ y , yc+x )       xc+ y  y c+x )       xc+ y  yc-x)       xc+ y  yc-x )

Caution:
The xc,yc being centre coordinates, they should not be rearranged 
such that the x and ys are together.

 (yc+y,xc+x) = WRONG
(xc+Y, yc+X) = RIGHT



Algo:

1. Input the radius of circle and store end points in (x0,y0) = (0,r).

2. Load (x0,y0) into frame buffer and plot the first point.

3. Calculate the starting value for decision variable d=3-2r

4. At each xi along the circle starting i=0, perform:

if (di < 0)                                  
the next point is (xi+1,y)
di+1=di + 4xi + 6                     // another way to write: di+1=di + (4xi + 4) + 2 
else
the next point is (xi+1, yi-1)
di+1=di + 4(xi-yi) + 10            // another way to write: di+1=di + (4xi + 4) + 2 + ( - 4yi + 4)

5. repeat 4 while x<=y            //or write it as repeat until x>y



My Notes:

1. when decision variable d < 0, it means the next point is getting inside the circle.
    Therefore Y=y;

    when decision variable d > 0, it means the next point is getting outside the circle/
    There fore Y=y-1;

2. As compared to last time - Bresenham's Normal Line Algo, (but slightly different)
        the X is the regular inc one, while Y is the conditional dec one.

3. Also, in the algo, only one octant is made. Add symmetry points for the others too.



Reason behind the decision Variables


...