Circles

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

We choose to work in the 1/8 of the circle (45 degrees) from x=0 (y-axis) to x = y = R/sqrt(2) (45 degrees clockwise from the y-axis.)
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)

We again create a decision variable d set equal to the function evaluated at the midpoint (Xp+ 1,Yp - 0.5)
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 = F(Xp + 1, Yp - 0.5)
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

if the SOUTHEAST pixel is chosen then:

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

Unlike the algorithm for lines, deltaE and deltaSE are not constant.
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

unfortunately while deltaSE and deltaE are integral, d is still a real variable, not an integer so:

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)

but since h starts off as an integer (assuming an integral R) and h is only incremented by integral amounts (deltaE and deltaSE) we can ignore the 0.25 and compare h < 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
else

add 2 * (X-Y) + 5 to d
add 1 to X
subtract 1 from Y
draw8Points(X, Y);

The full algorithm ( was ? ) given (in C) in the red book ( version ??? ) as program 3.4 on p.83.
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