Xiaolin Wu circle algorithm renders circle with holes inside

Question

I've implemented Xiaolin Wu circle algorithm from here: https://create.stephan-brumme.com/antialiased-circle/ in c++:

float radiusX = endRadius;
float radiusY = endRadius;
float radiusX2 = radiusX * radiusX;
float radiusY2 = radiusY * radiusY;

float maxTransparency = 127;

float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
for(float _x = 0; _x <= quarter; _x++) {
    float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
    float error = _y - floorf(_y);

    float transparency = roundf(error * maxTransparency);
    int alpha = transparency;
    int alpha2 = maxTransparency - transparency;

    setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, data, areasData, false);
    setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, data, areasData, false);
}

quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
for(float _y = 0; _y <= quarter; _y++) {
    float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
    float error = _x - floorf(_x);

    float transparency = roundf(error * maxTransparency);
    int alpha = transparency;
    int alpha2 = maxTransparency - transparency;

    setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, data, areasData, false);
    setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, data, areasData, false);
}

x, y are coordinates of center of the circle.

In my opinion it looks fine:

However, I need circle to be filled. Maybe I'm wrong, but I've developed a simple algorithm: iterate from 1 to radius and just draw a circle. It looks like this:

Strange. So, in order to fix this, I'm also setting transparency to the max until I reach the last radius (so it's an outer circle):

As you can see there are strange holes between outer and other layers. I've tried making two outer layers and similar stuff, but haven't got the right result.

Here's the final version of code:

for(int cradius = startRadius; cradius <= endRadius; cradius++) {
    bool last = cradius == endRadius;

    float radiusX = cradius;
    float radiusY = cradius;
    float radiusX2 = radiusX * radiusX;
    float radiusY2 = radiusY * radiusY;

    float maxTransparency = 127;

    float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
    for(float _x = 0; _x <= quarter; _x++) {
        float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
        float error = _y - floorf(_y);

        float transparency = roundf(error * maxTransparency);
        int alpha = transparency;
        int alpha2 = maxTransparency - transparency;

        if(!last) {
            alpha = maxTransparency;
            alpha2 = maxTransparency;
        }

        setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, data, areasData, false);
        setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, data, areasData, false);
    }

    quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
    for(float _y = 0; _y <= quarter; _y++) {
        float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
        float error = _x - floorf(_x);

        float transparency = roundf(error * maxTransparency);
        int alpha = transparency;
        int alpha2 = maxTransparency - transparency;

        if(!last) {
            alpha = maxTransparency;
            alpha2 = maxTransparency;
        }

        setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, data, areasData, false);
        setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, data, areasData, false);
    }
}

How can I fix this?

edit:

Because I cannot use flood-fill to fill the circle (area I draw on may not be one-colour background and I need to blend these colours) I've implemented simple method to connect points with lines:

I've added 2 drawLine calls in setPixel4 method:

void setPixel4(int x, int y, int deltaX, int deltaY, int r, int g, int b, int a, unsigned char* data, unsigned char* areasData, bool blendColor) {
    drawLine(x - deltaX, y - deltaY, x + deltaX, y + deltaY, r, g, b, 127, data, areasData); //maxTransparency
    drawLine(x + deltaX, y - deltaY, x - deltaX, y + deltaY, r, g, b, 127, data, areasData); //maxTransparency

    setPixelWithCheckingArea(x + deltaX, y + deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x - deltaX, y + deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x + deltaX, y - deltaY, r, g, b, a, data, areasData, blendColor);
    setPixelWithCheckingArea(x - deltaX, y - deltaY, r, g, b, a, data, areasData, blendColor);
}

and it looks exactly the same as third image. I think these white pixels inside are caused by outer circle (from xiaolin wu algorithm) itself.

edit 2:

Thanks to @JaMiT I've improved my code and it works for one circle, but fails when I have more on top of each other. First, new code:

void drawFilledCircle(int x, int y, int startRadius, int endRadius, int r, int g, int b, int a, unsigned char* data, unsigned char* areasData, int startAngle, int endAngle, bool blendColor) {
    assert(startAngle <= endAngle);
    assert(startRadius <= endRadius);

    dfBufferCounter = 0;

    for(int i = 0; i < DRAW_FILLED_CIRCLE_BUFFER_SIZE; i++) {
        drawFilledCircleBuffer[i] = -1;
    }

    for(int cradius = endRadius; cradius >= startRadius; cradius--) {
        bool last = cradius == endRadius;
        bool first = cradius == startRadius && cradius != 0;

        float radiusX = cradius;
        float radiusY = cradius;
        float radiusX2 = radiusX * radiusX;
        float radiusY2 = radiusY * radiusY;

        float maxTransparency = 127;

        float quarter = roundf(radiusX2 / sqrtf(radiusX2 + radiusY2));
        for(float _x = 0; _x <= quarter; _x++) {
            float _y = radiusY * sqrtf(1 - _x * _x / radiusX2);
            float error = _y - floorf(_y);

            float transparency = roundf(error * maxTransparency);
            int alpha = last ? transparency : maxTransparency;
            int alpha2 = first ? maxTransparency - transparency : maxTransparency;

            setPixel4(x, y, _x, floorf(_y), r, g, b, alpha, cradius, endRadius, data, areasData, blendColor);
            setPixel4(x, y, _x, floorf(_y) - 1, r, g, b, alpha2, cradius, endRadius, data, areasData, blendColor);
        }

        quarter = roundf(radiusY2 / sqrtf(radiusX2 + radiusY2));
        for(float _y = 0; _y <= quarter; _y++) {
            float _x = radiusX * sqrtf(1 - _y * _y / radiusY2);
            float error = _x - floorf(_x);

            float transparency = roundf(error * maxTransparency);
            int alpha = last ? transparency : maxTransparency;
            int alpha2 = first ? maxTransparency - transparency : maxTransparency;

            setPixel4(x, y, floorf(_x), _y, r, g, b, alpha, cradius, endRadius, data, areasData, blendColor);
            setPixel4(x, y, floorf(_x) - 1, _y, r, g, b, alpha2, cradius, endRadius, data, areasData, blendColor);
        }
    }
}

Without drawLine calls in setPixel4 it looks like this:

I've improved setPixel4 method to avoid redrawing the same pixel again:

void setPixel4(int x, int y, int deltaX, int deltaY, int r, int g, int b, int a, int radius, int maxRadius, unsigned char* data, unsigned char* areasData, bool blendColor) {

    for(int j = 0; j < 4; j++) {

        int px, py;
        if(j == 0) {
            px = x + deltaX;
            py = y + deltaY;
        } else if(j == 1) {
            px = x - deltaX;
            py = y + deltaY;
        } else if(j == 2) {
            px = x + deltaX;
            py = y - deltaY;
        } else if(j == 3) {
            px = x - deltaX;
            py = y - deltaY;
        }

        int index = (px + (img->getHeight() - py - 1) * img->getWidth()) * 4;

        bool alreadyInBuffer = false;
        for(int i = 0; i < dfBufferCounter; i++) {
            if(i >= DRAW_FILLED_CIRCLE_BUFFER_SIZE) break;
            if(drawFilledCircleBuffer[i] == index) {
                alreadyInBuffer = true;
                break;
            }
        }

        if(!alreadyInBuffer) {
            if(dfBufferCounter < DRAW_FILLED_CIRCLE_BUFFER_SIZE) {
                drawFilledCircleBuffer[dfBufferCounter++] = index;
            }

            setPixelWithCheckingArea(px, py, r, g, b, a, data, areasData, blendColor);
        }
    }

}

Then, finally:

It's almost perfect. However, I'm struggling for a lot of time to get rid of this white outline, but I can't.

Answer 1

For everyone still in need. I've just wrote a circle drawer function for my app (inspired mostly with this "thread").

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 doesn't use any additional memory (arrays) to store already handled pixels.

/*
* 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++;
    }
}

Also "Draw central filling" and "Draw top/bottom" parts can be optimized with some drawHorizontalLine function, but I don't have one at the moment.

Answer 2

You should draw only one outer circle with connect from left to right pixel side by solid horizontal simple lines.

]1

Answer 3

Think about what you are doing to get the third image (the one with the "strange holes" just inside the circumference). You have the inner disk drawn, and you want to draw a circle around it to make it a tiny bit bigger. Good idea. (Your calculus teacher should approve.)

However, You do not simply draw a circle around it; you draw an antialiased circle around it. What does that mean? It means that instead of simply drawing a point, you draw two, with different transparencies to fool the eye into thinking it's only one. One of those points (the inner one) is going to overwrite a point of the disk that you already drew.

When the outer point is more transparent, there is no problem other than maybe a bit of blurring. When the inner point is more transparent, though, you have this strange behavior where the disk starts mostly opaque, becomes more transparent, then returns to full opacity. You took a fully opaque point from the disk and made it mostly transparent. Your eye interprets this as a hole.

So how to fix this?

1) As long as your disk is supposed to be uniformly colored (accounting for transparency), your last attempt should work if you reverse the outer loop -- go from the largest radius to zero. Since only the outermost circle is being given antialiasing, only the first iteration of this reversed loop would overwrite a pixel with a more transparent one. And there is nothing to overwrite at that stage.

OR

2) In both places where you set alpha2, set it to maxTransparency. This is the transparency of the inner pixel, and you do not want the inner edge to be antialiased. Go ahead and loop through radii in either direction, building your disk out of circles. Keep setting both transparencies to the max when not drawing the outermost circle. This approach has the advantage of being able to put a hole in the middle of your disk; the startRadius does not have to be zero. When you are at startRadius (and startRadius is not zero), set alpha2 according to the anitaliasing algorithm, but set alpha to maxTransparency.

So your alpha setting logic would look something like

    bool first = cradius == startRadius  &&  cRadius != 0; // Done earlier
    int alpha = last ? transparency : maxTransparency;
    int alpha2 = first ? maxTransparency - transparency : maxTransparency;

Edit: Come to think on it, there would be division by zero if cRadius was zero. Since you apparently already accounted for that, you should be able to adapt the concept of "first" to mean "innermost circle and we are in fact leaving a hole".

OR

3) You could draw lines as had been suggested, but there are a few things to tweak to minimize artifacts. First, remove the second call to setPixel4 in each pair; we'll cover that case with the lines. This removes the need to have alpha2 (which was the cause of the holes anyway). Second, try drawing a box (four lines) instead of two parallel lines. With this algorithm, half the drawing is based on horizontal lines and half is based on vertical. By drawing both all the time, you have your bases covered. Third, if you still see artifacts, try drawing a second box inside the first.

Answer 4

Because you discretize circles some pixels are necessarily missing. The picture you obtained shows Moiré effect, which is well-known.

The best solution is to use any flood filling algorithm or to synthesize the trivial one that would draw lines in between point of circles on the same horizontal lines (or verticals if you prefer).