Scan Converting Circle

Compiled By:
Neha Aggarwal
Lecturer
www.chitkarauniversity.edu.in
CSE Dept.
1 24-02-2011
 Topics to be Covered
 Properties of Circle
 Bresenham’s Circle Drawing Algorithm
 Calculating decision parameter
 Midpoint Circle Algorithm
 Calculating decision parameter
 Examples

2 www.chitkarauniversity.edu.in 24-02-2011
 Properties of Circle
 A circle is defined as a set of points that are all at the
given distance from the centre position (xc,yc).
 This distance relationship is expressed by the
pythagorean theorem in Cartesian coordinates as
(x – xc)2 + (y – yc) 2 = r2
 This equation can be used to calculate the points on the
circle circumference by stepping along x-axis in unit
steps from xc-r to xc+r and calculate the corresponding
y values at each position as
y = yc +(- ) (r2 – (xc –x )2)1/2
 Problems with this method:
Considerable amount of computation.
Spacing between plotted pixels is not uniform.
3 www.chitkarauniversity.edu.in 24-02-2011
 Solution to the Problem
 Adjust the spacing by interchanging x and y whenever
the absolute value of slope of circle is greater than 1.
But, this will not reduce the computation.
 Solution could be to use Polar Coordinates of Circle.
 Polar coordinates of any circle are represented as r and
θ where
1. r represents the radius of the circle.
2. θ represents the angle of the circle with respect to any
axis.
 Then, the circle equations in parametric polar form
are: x = xc + r cosθ y = yc + r sinθ

4 www.chitkarauniversity.edu.in 24-02-2011
 Symmetry of Circle

5 www.chitkarauniversity.edu.in 24-02-2011
 Bresenham’s Circle Drawing Algo
Assumptions
1. Points are generated from 90 degree to 45 degree.
2. Moves are made only in +ve x- direction and –ve y-
direction.
3. If the points are generated from 90 to 45 degree, then
each new point closest to the true circle can be
found by taking either of the following two actions:
i. Move in the x-direction 1 unit.
ii. Move in the x-direction 1 unit and move in the –ve y-
direction 1 unit.

6 www.chitkarauniversity.edu.in 24-02-2011
 Calculating the Decision Parameter
 Assume that (xi, yi) are the coordinates yi T(xi+1, yi)
of the last scan converted pixel upon yi-1
entering the step i.
S(xi+1, yi-1)
 D(T) is the distance from the origin to
the pixel T squared minus the distance
to the true circle squared
i.e. D(T) = (xi+1)2 + yi2 – r2 O xi xi+1

 D(S) is the distance from the origin to

the pixel S squared minus the distance
to the true circle squared
i.e. D(S) = (xi+1)2 + (yi -1) 2 – r2
7 www.chitkarauniversity.edu.in 24-02-2011
Calculating the Decision Parameter (Contd…)
 D(T) will always be +ve and D(S)will always be –ve.
 Decision Parameter
di = D(T) + D(S)
di = ((xi+1)2 + yi2 – r2 ) + ((xi+1)2 + (yi -1) 2 – r2)
di = 2(xi+1)2 + yi2 + (yi -1) 2 –2 r2 ……(1)
 When di <0 i.e. |D(T)| < |D(S)|, pixel T is chosen
 When di >0 i.e. |D(T)| > |D(S)|, pixel S is chosen

8 www.chitkarauniversity.edu.in 24-02-2011
Calculating the Decision Parameter (Contd…)
 Decision Parameter for next pixel di+1
di+1 = 2(xi+1+1)2 + yi+12 + (yi+1 -1) 2 –2 r2
di+1 - di = {2(xi+1+1)2 + yi+12 + (yi+1 -1) 2 –2 r2} – {2(xi+1)2 + yi2 + (yi -
1) 2 –2 r2}
For next pixel, xi+1 = xi +1
di+1 = di + 4xi + 2(yi+12 - yi2)- 2(yi+1 -yi)+ 6
 If di < 0, yi+1 = yi
di+1 = di + 4xi + 6
 If di >= 0, yi+1 = yi - 1
di+1 = di + 4(xi – yi ) + 10
 Since, the circle is drawn from origin, so, (x,y) = (0,r)
Therefore, From Equation (1)
d0 = 2(0+1)2 + r2 + (r -1) 2 –2 r2
d0 = 3-2r
9 www.chitkarauniversity.edu.in 24-02-2011
 Algo for Bresenham’s Circle Drawing
Step 1: Set the initial values of the variables (h,k) =
coordinates of the circle centre i.e. (o,r)
Initial decision parameter is d=3-2r (as calculated)
Step 2: Test to determine whether the entire circle has been
scan converted. If x>y, stop.
Step 3: Plot the 8 points found by symmetry w.r.t. the
center (h,k) at the current (x,y) coordinates. Plot
(x+h,y+k).
Step 4: Compute the location of the next pixel.
If d<0, then d = d + 4x + 6 and x=x+1
If d>=0, then d = d + 4(x-y) +10 and x=x+1, y=y-1
Step 5: Goto step 2
10 www.chitkarauniversity.edu.in 24-02-2011
 Midpoint Circle Algorithm
Assumptions
 Calculate pixel positions for a circle centered around the origin
(0,0). Then, each calculated position (x,y) is moved to its proper
screen position by adding xc to x and yc to y
 Along the circle section from x=0 to x=y in the first octant, the
slope of the curve varies from 0 to -1
 By midpoint method, Circle function around the origin is given
by
fcircle(x,y) = x2 + y2 – r2
 Any point (x,y) on the boundary of the circle satisfies the
equation and circle function is zero.
 For a point in the interior of the circle, the circle function is
negative and for a point outside the circle, the function is
positive.
11 www.chitkarauniversity.edu.in 24-02-2011
12 www.chitkarauniversity.edu.in 24-02-2011
 Midpoint Circle Algorithm
 Thus,
 fcircle(x,y) < 0 if (x,y) is inside the circle boundary
 fcircle(x,y) = 0 if (x,y) is on the circle boundary
 fcircle(x,y) > 0 if (x,y) is outside the circle boundary

yk x2+y2-r2=0

yk-1

xk xk+1 xk+2
Midpoint

Midpoint between candidate pixels at

sampling position xk+1 along a circular path

13 www.chitkarauniversity.edu.in 24-02-2011
 Calculating the Decision Parameter
 Assuming we have just plotted the pixel at (xk,yk) , we
next need to determine whether the pixel at position
(xk + 1, yk-1) or (xk + 1, yk) is closer to the circle.
 Decision parameter is the circle function evaluated at
the midpoint between these two pixels
pk = fcircle (xk +1, yk-1/2) = (xk +1)2 + (yk -1/2)2 – r2
 If pk < 0 , this midpoint is inside the circle and the
pixel on the scan line yk is closer to the circle
boundary.
 Otherwise, the mid position is outside or on the circle
boundary, and pixel on the scan line yk-1 is selected.
14 www.chitkarauniversity.edu.in 24-02-2011
Calculating the Decision Parameter (Contd…)
 Successive decision parameters are obtained using
incremental calculations
pk+1 = fcircle(xk+1+1, yk+1-1/2)
= [(xk+1)+1]2 + (yk+1 -1/2)2 –r2
OR
pk+1 = pk+2(xK+1) + (yK+12 – yk2) – (yk+1- yk)+1
Where yk+1 is either yk or yk-1, depending on the sign of pk
 Increments for obtaining Pk+1:
2xk+1+1 if pk is -ve
2xk+1+1-2yk+1 , if pk is +ve
where xk+1 +1 = xk and yk+1 = yk -1
15 www.chitkarauniversity.edu.in 24-02-2011
Calculating the Decision Parameter (Contd…)
 Initial decision parameter is obtained from center (0,r) of
the circle i.e.
pk (0,r) = 5/4 – r
 If radius is integer, then pk = 1 – r

16 www.chitkarauniversity.edu.in 24-02-2011
 Midpoint Circle Algorithm
1. Input initial values i.e. radius r and circle center (xc,yc)
and obtain the first point on the circumference of the
circle centered on the origin as (x0,y0) = (0,r).
2. Calculate the initial value of the decision parameter as
p0 = 5/4 – r
3. At each xk , starting at k=0, perform the following test:
If pk < 0, the next position on the circle centered on
(0,0) is (xk+1 , yk) and pk+1 = pk+ 2(xK+1) + 1
Otherwise, the next point along the circle is (xk +1,yk-1)
and pk+1 = pk+ 2xk+1 + 1 – 2yk+1 where 2xk+1 = 2xk +2
and 2yk+1 = 2yk-2
www.chitkarauniversity.edu.in
Contd….
17 24-02-2011
 Midpoint Circle Algorithm
4. Determine symmetry points in other seven octants.
5. Move each calculated position (x, y) onto the circular
path centered on (xc, yc) and plot the coordinate
values as x = x + xc and y = y + yc
6. Repeat steps 3 through 5 until x>=y.

18 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point circle algorithm (Example)

 Given a circle radius r = 10, demonstrate the midpoint

circle algorithm by determining positions along the
circle octant in the first quadrant from x = 0 to x = y.
Solution:
 p0 =1 – r = – 9
 Plot the initial point (x0, y0 ) = (0, 10),
 2x0 = 0 and 2y0 =20.
 Successive decision parameter values and positions
along the circle path are calculated using the midpoint
method as appear in the next table:

19 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point circle algorithm (Example)
K Pk (xk+1, yk+1) 2 xk+1 2 yk+1
0 –9 (1, 10) 2 20
1 –6 (2, 10) 4 20
2 –1 (3, 10) 6 20
3 6 (4, 9) 8 18
4 –3 (5, 9) 10 18
5 8 (6,8) 12 16
6 5 (7,7) 14 14
20 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point circle algorithm (Example)

21 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point Circle Algorithm – Example (2)
 Given a circle radius r = 15, demonstrate the midpoint
circle algorithm by determining positions along the
circle octant in the first quadrant from x = 0 to x = y.

Solution:
 p0 = 1 – r = – 14
 plot the initial point (x0 , y0) = (0, 15),
 2x0 = 0 and 2y0 = 30.
 Successive decision parameter values and positions
along the circle path are calculated using the midpoint
method as:

22 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point Circle Algorithm – Example (2)
K Pk (xk+1, yk+1) 2 xk+1 2 yk+1

0 – 14 (1, 15) 2 30

1 – 11 (2, 15) 4 30

2 –6 (3, 15) 6 30

3 1 (4, 14) 8 28

4 – 18 (5, 14) 10 28

23 www.chitkarauniversity.edu.in 24-02-2011
 Mid-point Circle Algorithm – Example (2)

K Pk (xk+1, yk+1) 2 xk+1 2 yk+1

5 –7 (6,14) 12 28
6 6 (7,13) 14 26
7 –5 (8,13) 16 26
8 12 (9,12) 18 24
9 7 (10,11 ) 20 22
10 6 (11,10) 22 20

24 www.chitkarauniversity.edu.in 24-02-2011