Efficient Ellipse Drawing - Part 2

[images coming later]

In Part 1, I discussed drawing lines. Drawing an ellipse, pixel-by-pixel, shares some comments with line drawing, so I covered that there.

In this part, I discuss drawing a circle.

In the next part, I'll discuss complications and provide a more complete circle-drawing algorithm. The final part(s) will cover ellipses.

Symmetry

Circles are handy because they are symmetric. Since we're rendering a circle onto a square grid, the symmetry that's useful to us here is horizontal symmetry and vertical symmetry. We'll also make use of the fact that you can rotate a circle 90º and still have a circle. Combine all the symmetries together, and we really only need to draw one-eighth of the circle.
[insert image here]

Hence, most circle-drawing algorithms will only draw an eight of the circle, and use this symmetry to plot the other 7/8ths. Which eighth you draw is up to you. I'll be drawing the eight from straight up (like 12 o'clock) clockwise to 45º (1:30 on an analog clock).

void PlotEightPoints(int x, int y)
{
PlotPixel(x,y);
PlotPixel(y,x);
PlotPixel(-x,y);
PlotPixel(-y,x);
PlotPixel(x,-y);
PlotPixel(y,-x);
PlotPixel(-x,-y);
PlotPixel(-y,-x);
}

This code can be easily tweaked to draw points centered anywhere in the screen; just add a constant offset to x and y in each case. Something like:

void PlotEightPoints(int x, int y, int xCenter, int yCenter)
{
PlotPixel(x+xCenter,y+yCenter);
etc...

or, if this code is part of a class:

void PlotEightPoints(int x, int y)
{
PlotPixel(x+this.xCenter,y+this.yCenter);
etc...

Borders

A perfect circle on a square grid can either be centered on a pixel, or centered on the border between two pixels.
[insert image here]

It's easy to start the first one. Say our circle is centered at the pixel 0,0, and has a radius of 10. We can conclude that the pixels (10,0), (0,10), (-10,0), and (0,-10) are all points that we want to draw. There's no fractions here, and the logic is fairly simple.

The second example -- when our circle is centered on the border between two pixels -- is a bit more complex, but much of the same logic (below) is the same. I'll cover this case in the next post.

Tricks

The trick to circle drawing is to note that, over this eighth of the circle that we are going to draw, we're only going to draw one pixel per column. Furthermore, as we move from pixel to pixel, we'll either move straight to the right (dy=0), or diagonally down one pixel (dy=-1). Hence: we just need to figure out which of those two choices is closer to our circle!
[insert image here]

The formula for a circle (centered at 0,0) is

x² + y² = r²

where 'r' is our radius.

Let's say we plot our first point at (0,10). Should our next point be (1,9) or (1,10)? We can calculate the radius at those two points easily:

r = sqrt(x² + y²)

Here's another trick: we don't really need to do the square root. We can just pick the point such that (x²+y²) is closest to r², or 100 in our sample case. For (1,9) that value is (1*1 + 9*9), or 82, and for (1,10) the value is (1*1+10*10), or 101. Our goal is 100, so obviously 101 is closer.
[insert image here]

And now for the code:

void DrawCircle( int r )
{
int x = 0;
int y = r;
while (y >= x)
{
PlotEightPoints(x,y);
x++; // always move over one column
int rAcross = x*x + y*y;
int rDown = x*x + (y-1) * (y-1);
int acrossDelta = r*r - rAcross;
int downDelta = r*r - rDown;
int absoluteAcrossDelta = Math.Abs(acrossDelta);
int absoluteDownDelta = Math.Abs(downDelta);
if (absoluteDownDelta < absoluteAcrossDelta)
y--; // sometimes move down one row
}
}

This will draw your circle. In the next post in this series, I'll cover drawing a circle that isn't centered on a pixel, provide a code snippet for drawing a circle anywhere on screen, and handle cases where part of our circle is off-screen.