### Drawing Circles

The algorithm used to draw circles is very similar to the Midpoint Line algorithm.8 way-symmetry - for a circle centered at (0,0) and given that point (x,y) is on the circle, the following points are also on the circle:

(-x, y) ( x,-y) (-x,-y) ( y, x) (-y, x) ( y,-x) (-y,-x)So it is only necessary to compute the pixels for 1/8 of the circle and then simply illuminate the appropriate pixels in the other 7/8.

given a circle centered at (0,0) with radius R:

- R^2 = X^2 + Y^2

F(X,Y) = X^2 + Y^2 - R^2

so for any point (Xi,Yi) we can plug Xi,Yi into the above equation and

- F(Xi,Yi) = 0 -> (Xi,Yi) is on the circle

F(Xi,Yi) > 0 -> (Xi,Yi) is outside the circle

F(Xi,Yi) < 0 -> (Xi,Yi) is inside the circle

Given that we have illuminated the pixel at (Xp,Yp) we will next either illuminate

- the pixel to the EAST (Xp + 1,Yp)

or the pixel to the SOUTHEAST (Xp+ 1,Yp - 1)

d = F(Xp + 1,Yp - 0.5)

We plug the midpoint into the above F() for the circle and see where the midpoint falls in relation to the circle.

- d > 0 (midpoint is outside) -> pick SOUTHEAST pixel

d < 0 (midpoint is inside) -> pick EAST pixel

d = 0 (midpoint is on circle) -> ***CHOOSE*** to pick SOUTHEAST pixel

dcurrent = (Xp + 1)^2 + (Yp - 0.5)^2 - R^2

dcurrent = Xp^2 + 2Xp + 1 + Yp^2 - Yp + 0.25 - R^2

if the EAST pixel is chosen then:

- dnew = F(Xp + 2, Yp
- 0.5)

dnew = (Xp + 2)^2 + (Yp - 0.5)^2 - R^2

dnew = Xp^2 + 4Xp + 4 + Yp^2 - Yp + 0.25 - R^2

dnew - dcurrent = deltaE = 2Xp + 3

- dnew = F(Xp + 2, Yp
- 1.5)

dnew = (Xp + 2)^2 + (Yp - 1.5)^2 - R^2

dnew = Xp^2 + 4Xp + 4 + Yp^2 - 3Yp + 2.25 - R^2

dnew - dcurrent = deltaSE = 2Xp - 2Yp + 5

initial point (Xo,Yo) is known to be (0,R)

so initial M is at (1, R - 0.5)

so initial d = F(1, R - 0.5)

- = 1^2 + (R - 0.5)^2 - R^2

= 1 + R^2 - R + 0.25 - R^2

= 1.25 - R

- h = d - 0.25

h is initialized as 1 - R (instead of 1.25 - R)

h is compared to as h < 0.25 (instead of d< 0)

- X = 0;

Y = radius;

d = 1 - radius;

draw8Points(X, Y);

while(Y > X)

- if (d< 0)

- add 2 * X + 3 to d

add 1 to X

- add 2 * (X-Y) + 5 to d

add 1 to X

subtract 1 from Y

The full algorithm is given (in C) in the white book as figure 3.16 on p.86.

This is still somewhat bad in that there is a multiplication to compute the new value of the decision variable. The book shows a more complicated algorithm which does this multiplication only once.

ellipses F(x,y) = b^2 X^2 + a^2 Y^2 - a^2 b^2 = 0 are handled in a similar manner, except that 1/4 of the ellipse must be dealt with at a time and that 1/4 must be broken into 2 parts based on where the slope of the tangent to the ellipse is -1 (in first quadrant.)

### Filling Circles

Circles have the advantage of being convex polygons, so each scan line will have a single span.The span extrema can be computed using the same method as was used to draw the pixels on the boundary of the circle, computing them for 1/8 of the circle and using 8-way symetry to get the other 7/8. These extrema can then be stored in an array of Xmin and Ymin indexed by Y