4
\$\begingroup\$

I'm experimenting with drawing circles and have brute-forced a very simple one:

Pseduocode:

r=7
d=r*2

for y = 0 to d
  for x = 0 to d
    if (x-r)^2 + (y-r)^2 <= (r)^2
      plot(x+r, y+r, c)
    endif
  next
next

The principal is simple. Step through every point in a square and plot every point which lies within the area of the circle.

I end up with something like this:

enter image description here

I don't want the single-pixels that appear on on each side so I adjusted this line from:

if (x-r)^2 + (y-r)^2 <= (r)^2

to:

if (x-r)^2 + (y-r)^2 < (r)^2

I end up with a circle like this:

enter image description here

While this IS a circle, it's not quite the circle that I want. The edges are too sharp and don't slope in a convincing way. Instead, I want to draw something little smoother like this:

enter image description here

But I'm not sure how to "relax" the the pixels to achieve this.

The code I posted is meant to illustrate how I'm drawing the circle-- I'm not looking for optimizations. I'm only interested in tweaking it to manipulate the smoothness of the circle being drawn.

This is more than an adjustment for the last pixel along each side. I want something that scales with the size of the circle.


UPDATE

I experimented with the code provided by @user1118321 an found that I could manipulate which pixels were drawn along the edge by considering the distance of the point being plotted from the center of the circle.

This allows me to apply a threshold on the points at the very edge of the circle and to decide which ones I want to skip over.

The results vary depending on a few different factors and would benefit from fine-tuning with a table for an optimal threshold for very small circles to taste.

Here is one solution which provided me with the circle I was looking for:

for y = 0 to r*2
  for x = 0 to r*2
    deltaX = r - x
    deltaY = r - y
    distance = sqr(deltaX^2 + deltaY^2)

    // Point lies outside of the circle
    if distance-radius > 1
      continue
    endif

    // Edge threshold
    if radius/distance < 0.9
      continue
    endif

    plot(x, y)
  next
next

Here are some examples of various circles I was able to create:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ have you thought about adding anti aliasing on the circle, you can do that with your calculation. At the moment you are plotting in integer space, but if you initially use floats and use the decimal component to assist in calculating the strength of the colour value at the edges, giving you a pseudo anti alias effect. It would also require you to change your loop so the steps weren't to real integers. Just a thought. \$\endgroup\$ – ErnieDingo Oct 4 '19 at 1:13
  • \$\begingroup\$ Are you open to considering alternative plotting algorithms? In particular, the mid-point algorithm side steps the problems you've encountered. If so, I could post an answer walking through an implementation. It's efficient, concise without being cryptic. \$\endgroup\$ – Pikalek Oct 4 '19 at 1:19
  • \$\begingroup\$ @Pikalek Yes, alternative algorithms are acceptable. I would love a walkthrough. \$\endgroup\$ – Zhro Oct 4 '19 at 3:01
  • \$\begingroup\$ @ErnieDingo You're right. But in this case, I don't want to add any anti-aliasing. \$\endgroup\$ – Zhro Oct 4 '19 at 3:03
  • \$\begingroup\$ Not a problem, was interested in whether you wanted that effect. Good luck with it all. \$\endgroup\$ – ErnieDingo Oct 4 '19 at 4:22
1
\$\begingroup\$

The midpoint circle algorithm calculates a raster path by selecting pixels which are as close as possible to solutions of \$x^2 + y^2 = r^2\$. At each step, the path is extended by choosing the adjacent pixel which satisfies \$x^2 + y^2 \leq r^2\$, but maximizes \$x^2 + y^2\$.

The algorithm takes advantage of the fact that a circle is symmetric. That is to say, if you can correctly draw any 45° section of the circle, all the remaining sections can be found by mirroring the pixels that you've already solved for. Thus, it draws all eight octants simultaneously, starting from each cardinal direction (0°, 90°, 180°, 270°) and extends both ways to reach the nearest multiple of 45°. This means it can stop when x == y, as that indicates it has traveled 45°.

Consider the following image:

enter image description here

Starting at 90°, note that as we follow the curve to the right, we need to decide when to take a step in the y direction. The algorithm essentially does this by tracking the accumulated error (similar to how Bresenham's line algorithm works). Also note that the image show calculations going from the middle of the center pixel to the middle of the edge pixels.

In terms of code, here's an implementation based on the (Java) code at RosettaCode.org:

public void drawCircle(int centerX, int centerY, int radius) {
    int d = (5 - r * 4)/4;
    int x = 0;
    int y = radius;

    do {
        plot(centerX + x, centerY + y);
        plot(centerX + x, centerY - y);
        plot(centerX - x, centerY + y);
        plot(centerX - x, centerY - y);
        plot(centerX + y, centerY + x);
        plot(centerX + y, centerY - x);
        plot(centerX - y, centerY + xr);
        plot(centerX - y, centerY - x);
        if (d < 0) {
            d += 2*x + 1;
        } else {
            d += 2*(x - y) + 1;
            y--;
        }
        x++;
    } while (x <= y);
}

The d variable is basically responsible for accumulating the drift between the ideal perfect circle & the raster location. When it accumulates enough, the code takes a step in the y direction. The block of plotting code is responsible for mirroring the x,y locations across all octants of the circle.

The code above will plot the outline. For my own purposes, I didn't just need the outline, I essentially needed a fill. To that end, I modified the code to give me an array holding the length of each row (the index for the array being the height) for a quarter section of the circle. Also, as a matter of personal preference, I converted the do loop into a while loop:

public int[] quarterCircleScanLineWidth(int radius){
    int[] result = new int[radius+1];
    int x = 0;
    int y = radius;
    int p = 1 - radius;

    quarterCircleScanLineWidthHelper(result, x, y);

    while(x < y){
        x++;
        if(p < 0){
            p += 2*x + 1;
        }
        else{
            y--;
            p += 2*(x-y) + 1;
        }
        quarterCircleScanLineWidthHelper(result, x, y);
    }
    quarterCircleScanLineWidthHelper(result, x, y);
    return result;
}

private void quarterCircleScanLineWidthHelper(int[] data, int x, int y){
    if(data[y] < x){
        data[y] = x;
    }
    if(data[x] < y){
        data[x] = y;
    }
}
\$\endgroup\$
  • \$\begingroup\$ I'm in love with this answer \$\endgroup\$ – JCM Oct 8 '19 at 19:55
2
\$\begingroup\$

If you think of the circle as a cone passing through the screen, with the point being in the center of the circle, you can reformulate it in a way that's pretty easy to code. The distance from the center will be between 0 and radius. But you want it to be 0 at the radius. So if you reverse it, you get something like this:

for (float y = 0; y < 2.0 * r; y++)
{
    for (float x = 0; x < 2 * r; x++)
    {
        float deltaX = r - x;
        float deltaY = r - y;
        float distance = sqrt(deltaX * deltaX + deltaY * deltaY);
        color = clamp (r - distance, 0, 1);
        plot(x, y, color);
    }
}

That produces output like this:

An antialiased circle.

\$\endgroup\$
  • \$\begingroup\$ Thank you for this great solution. But I'm not looking for anti-aliasing in this case. If you wish to provide another answer, please submit a new one. This is still very useful and helped me to derive my own solution. \$\endgroup\$ – Zhro Oct 4 '19 at 9:35
  • 1
    \$\begingroup\$ @Zhro if this is close to what you want, you might be able to tweak it to remove anti-aliasing. For instance if(color > threshold){ plot(x, y, 1); } Anything that's too faint would be discarded & everything else would get rendered at a solid color of 1. \$\endgroup\$ – Pikalek Oct 4 '19 at 19:36
0
\$\begingroup\$

The simplest thing to do is to exclude radii which don't agree with your idea of an ideal circle.

The way to do this is to use really any of the algorithms desired, but filter the input value r for certain ranges which produce unacceptable outputs: do not use the exact r, but rather snap to an acceptable nearby (higher or lower) value of r if within those ranges, using similar logic to Math.Round found in most languages.

When r has a small fractional part, something like values of 1.01, 2.01, 3.01, etc. (or 1.51, 2.51 depending on how your circle is drawn) , I believe that is when you will find these annoying edge pixels.

If you disallow those input values, you will avoid the issue entirely for all possible radii, though as the radius get larger and large, the problem will be less pronounced because you will no longer just see a single pixel at the edge, but rather more of them, and at that point it becomes a non-issue.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.