c++renderingcocos2d-xantialiasing

Xiaolin Wu circle algorithm renders circle with holes inside


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:

enter image description here

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:

enter image description here

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):

enter image description here

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:

enter image description here

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:

enter image description here

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


Solution

  • 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.