Algorithm for drawing an anti-aliased circle?

Question

What's a good algorithm for drawing anti-aliased circles? (Filled and not filled.)

Peskoff

Answer 1

Bresenham (of the line algorithm fame) also had a circle algorithm.

Xiaolin Wu adapted the line algorithm for anti-aliasing, and likewise did the same to the circle algorithm.

http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

You can find the circle algorithm with this search:

http://www.google.com/search?q=Xiaolin%20Wu%20circle

-Adam

Forrestforrester

Actually, what is popularly known as "Bresenham's circle algorithm" wasn't Bresenham's own work. en.wikipedia.org/wiki/Midpoint_circle_algorithm But still.... – Inconclusive

Answer 2

If you want an easy one, make a soft blur from pixel matrix A to pixel matrix B.

This is one I have used (here in pseudo-code).
This really is a very simple one:

anti_alised_matrix[x][y] = point[x][y] / 2
                         + point[x+1][y]/8
                         + point[x-1][y]/8
                         + point[x][y-1]/8
                         + point[x][y+1]/8;

Of course this is applied to grayscale, but you can easily do the same in RGB.
You can also add the diagonals i.e. [x+1][y+1] and split it by 16 or 32.

Tanagra

Answer 3

For everyone in need. I've just wrote a circle drawer function for my app.

Unfortunately it draws only odd diameter circles, but it's very fast for drawing on CPU.

Also it can be easily ported on any other language since no special syntax/constructions are used.

The main advantage is that it can work with the blending, avoiding layering of pixels (which is leading to dark spots on the circle).

/*
* void drawPixel(int32_t x, int32_t y, uint32_t color)
*
* The algorithm's been written assuming this function to work with alpha-blending
* and packed RGBA colors, but you can change the color system easily.
* 
* AA - anti-aliasing 
*/

static inline void draw8Symmetry(int32_t cX, int32_t cY, int32_t x, int32_t y, int32_t color) {
    drawPixel(cX + x, cY + y, color);
    drawPixel(cX + x, cY - y, color);
    if (x != 0) {  // No repeating on top/bottom
        drawPixel(cX - x, cY + y, color);
        drawPixel(cX - x, cY - y, color);
    }
    if (x != y) { // No repeating on corners (45 deg)
        drawPixel(cX + y, cY + x, color);
        drawPixel(cX - y, cY + x, color);
        if (x != 0) { // No repeating on left/right sides
            drawPixel(cX + y, cY - x, color);
            drawPixel(cX - y, cY - x, color);
        }
    }
}

void drawCircle(int32_t cX, int32_t cY, int32_t r, uint32_t color) {
    int32_t i = 0;
    int32_t j = r + 1;
    int32_t rr = r * r;

    double lastFadeAmount = 0;
    double fadeAmount = 0;
    int32_t fadeAmountI;

    const int32_t maxOpaque = color >> 24;
    const int32_t noAlphaColor = color & 0x00FFFFFF;

    while (i < j) {
        double height = sqrt(rr - i * i);
        fadeAmount = (double)maxOpaque * (1.0 - (ceil(height) - height));

        // If fade amount is dropping, then, obviously, it's a new step
        if (fadeAmount > lastFadeAmount)
            j--;
        lastFadeAmount = fadeAmount;
        
        // Draw the semi-transparent circle around the filling
        draw8Symmetry(cX, cY, i, j, noAlphaColor | ((int32_t)fadeAmount << 24));

        // Draw central filling
        if (i != 0)
            for (int32_t x = -j + 1; x < j; x++) {
                drawPixel(cX + x, cY + i, color);
                drawPixel(cX + x, cY - i, color);
            }
        else
            for (int32_t x = -j + 1; x < j; x++)
                drawPixel(cX + x, cY + i, color);

        i++;
    }

    // Draw top and bottom parts
    while (i < r) {
        int32_t lineLength = ceil(sqrt(rr - i * i));

        for (int32_t x = -lineLength + 1; x < lineLength; x++) {
            drawPixel(cX + x, cY + i, color);
            drawPixel(cX + x, cY - i, color);
        }

        i++;
    }
}

Epigraph

Answer 4

Create a Graphics object g. Do

g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;

Draw your anti aliased circle with g.FillEllipse or g.DrawEllipse

Improve

Did he ever say he was on .NET? – Vermicide

Nope. But did he ever say he was not :?) – Improve

He asked for an algorithm, not a platform-specific sample of how to use something that does it for you. – Mannered

"how to use something that does it for you" sounds like an algorithm to me. Maybe a better answer would involve a stick in a sand, rope and a nail :?) – Improve

"how to use something that does it for you" sounds like the exact opposite of an "algorithm" to me. Algorithms usually involve math and work everywhere, you just set a property to a predefined value. ;-) – Vermicide

Spikolynn, what you gave is a ritual; what he asked for is reason. – Finegan

hehe, these are funny comments. :) (I would take the easy option if i could but...) – Peskoff

I actually found this comment useful as I DID need to know how to do this in .NET – Bingaman

Is also found this useful even if it's not an answer to this question – Orthopedics