## Tuesday, 1 October 2013

### 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;
draw8Points(X, Y);
while(Y > X)

if (d< 0)

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