,
public void circleSimple(int xCenter, int yCenter, int radius, Color c) { int pix = c.getRGB(); int x, y, r2; r2 = radius * radius; for (x = -radius; x <= radius; x++) { y = (int) (Math.sqrt(r2 - x*x) + 0.5); raster.setPixel(pix, xCenter + x, yCenter + y); raster.setPixel(pix, xCenter + x, yCenter - y); } }
|
![]() |
As you can see the circles look fine in areas where only one pixel is required for each column, but in areas of the circle where the local slope is greater the one the circle appears discontinuous (where have we seen this before?).
We could take the approach of computing the derivative (i.e. the local slope) of the function at each point and then make a decision whether to step in the x direction or the y direction. But, we will explore a different approach here.
A circle exhibits a great deal of symmetry. We've already exploited this somewhat by plotting two pixels for each function evaluation; one for each possible sign of the square-root function. This symmetry was about the x-axis. The reason that a square-root function brings out this symmetry results from our predilection that the x-axis should be used as an independent variable in function evaluations while the y-axis is dependent. Thus, since a function can yield only one value per member of the domain, we are forced to make a choice between positive and negative square roots. The net result is that our simple circle-drawing algorithm exploits 2-way symmetry about the x-axis.
Obviously, a circle has a great deal more symmetry. Just as every point above an x-axis drawn through a circle's centre has a symmetric point an equal distance from, but on the other side of the x-axis, each point also has a symmetric point on the opposite side of a y-axis drawn through the circle's centre.
public void circleSym4(int xCenter, int yCenter, int radius, Color c) { int pix = c.getRGB(); int x, y, r2; r2 = radius * radius; raster.setPixel(pix, xCenter, yCenter + radius); raster.setPixel(pix, xCenter, yCenter - radius); for (x = 1; x <= radius; x++) { y = (int) (Math.sqrt(r2 - x*x) + 0.5); raster.setPixel(pix, xCenter + x, yCenter + y); raster.setPixel(pix, xCenter + x, yCenter - y); raster.setPixel(pix, xCenter - x, yCenter + y); raster.setPixel(pix, xCenter - x, yCenter - y); } }
|
![]() |
This circle-drawing algorithm uses 4-way symmetry.
This algorithm has all the problems of our previous algorithm, but it gives the same result with half as many function evaluations. So much for "making it work first" before optimizing. But, we're on a roll so let's push this symmetry thing as far as it will take us.
We can find any point's symmetric complement about these lines by permuting the indices. For example the point (x,y) has a complementary point (y,x) about the line x=y. And the total set of complements for the point (x,y) are
The following routine takes advantage of this 8-way symmetry. The algorithm loops over one-eighth of the circle. Specifically, it starts at the top of the circle and goes to the right by 45 degrees, where the slope of a radial line is 1. Thus, the stopping state is crossing the x=y line.
public void circleSym8(int xCenter, int yCenter, int radius, Color c) { int pix = c.getRGB(); int x, y, r2; r2 = radius * radius; raster.setPixel(pix, xCenter, yCenter + radius); raster.setPixel(pix, xCenter, yCenter - radius); raster.setPixel(pix, xCenter + radius, yCenter); raster.setPixel(pix, xCenter - radius, yCenter); x = 1; y = (int) (Math.sqrt(r2 - 1) + 0.5); while (x < y) { raster.setPixel(pix, xCenter + x, yCenter + y); raster.setPixel(pix, xCenter + x, yCenter - y); raster.setPixel(pix, xCenter - x, yCenter + y); raster.setPixel(pix, xCenter - x, yCenter - y); raster.setPixel(pix, xCenter + y, yCenter + x); raster.setPixel(pix, xCenter + y, yCenter - x); raster.setPixel(pix, xCenter - y, yCenter + x); raster.setPixel(pix, xCenter - y, yCenter - x); x += 1; y = (int) (Math.sqrt(r2 - x*x) + 0.5); } if (x == y) { raster.setPixel(pix, xCenter + x, yCenter + y); raster.setPixel(pix, xCenter + x, yCenter - y); raster.setPixel(pix, xCenter - x, yCenter + y); raster.setPixel(pix, xCenter - x, yCenter - y); } }
So now we get 8 points for every function evaluation, and this routine should be approximately 4-times faster than our initial circle-drawing algorithm. What's going on with the four pixels that are set outside the loop (both at the top and bottom)? Didn't I say that every point determines 7 others?
It seems suddenly that our circles appear continuous, and we added no special code to test for the slope. Symmetry has come to our rescue. (Actually, symmetry is also what saved us on lines, if you think about it.)
Let's simplify the function evaluation that takes place on each iteration of our circle-drawing algorithmSo our next objective is to simplify the function evaluation that takes place on each iteration of our circle-drawing algorithm. All those multiplies and square-root evaluations are expensive. We can do better. We translate our coordinate system so that the circle's center is at the originOne approach is to manipulate the circle equation slightly. First, we translate our coordinate system so that the circle's center is at the origin (the book leaves out this step), giving:
( ( x + x0 ) - x0 )2 + ( ( y - y0 ) - y0 )2 = r2We simplify and make the equation homogeneousNext, we simplify and make the equation homogeneous (i.e. independent of a scaling of the independent variables; making the whole equation equal to zero will accomplish this) by subtracting r2 from both sides. x2 + y2 - r2 = 0We can regard this expression as a function in x and y. Discriminating function : partition the domain, into one of three categoriesf( x, y ) = x2 + y2 - r2Functions of this sort are called discriminating functions in computer graphics. They have the property of partitioning the domain, pixel coordinates in our case, into one of three categories. When f(x,y) is equal to zero the point lies on the desired locus (a circle in this case), when f(x, y) evaluates to a positive result the point lies one side of the locus, and when f(x,y) evaluates to negative it lies on the other side. |
![]() |
What we'd like to do is to use this discriminating function to maintain our trajectory of drawn pixels as close as possible to the desired circle. Luckily, we can start with a point on the circle, (x0, y0+r) (or (0, r) in our adjusted coordinate system). As we move along in steps of x we note that the slope is less than zero and greater than negative one at points in the direction we're heading that are near our known point on a circle. Thus we need only to figure out at each step whether to step down in y or maintain y at each step.
We will compute points between x=0 and x=y and then draw the 8 matching pointsIn that area, the slope of the curve is between 0 and -1From each step/point (x, y), the next one is either (x+1, y) or (x+1, y-1)We decide about which one by looking at the midpoint M
|
![]() |
int x = 0;
int y = radius; int p = 1 - radius;
circlePoints(xCenter, yCenter, x, y, pix);
while (x < y) {
x++;
if (p < 0) {
p += 2*x+1;
} else {
y--;
p += 2*(x-y+1);
}
circlePoints(xCenter, yCenter, x, y, pix);
}