Алгоритм круга Xiaolin Wu отображает круг с отверстиями внутри

Question

Я реализовал алгоритм окружности Сяолинь Ву отсюда: https://create.stephan -brumme.com / antialiased-circle / в 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 - координатыцентр круга.

На мой взгляд, все выглядит хорошо:

Однако мне необходимо заполнить круг.Возможно, я ошибаюсь, но я разработал простой алгоритм: итерируйте от 1 до радиуса и просто нарисуйте круг.Выглядит это так:

Странно.Итак, чтобы это исправить, я также устанавливаю прозрачность на максимум, пока не достигну последнего радиуса (так что это внешний круг):

Как видите, между внешним и другими слоями есть странные дыры.Я пытался сделать два внешних слоя и подобные вещи, но не получил правильный результат.

Вот окончательная версия кода:

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);
    }
}

Как это исправить?

edit:

Поскольку я не могу использовать заливку длязаполнить круг (область, на которой я рисую, может быть не одноцветным, и мне нужно смешать эти цвета) Я реализовал простой метод для соединения точек линиями:

Я добавил 2 вызова drawLine в setPixel4Метод:

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);
}

и выглядит точно так же, как третье изображение.Я думаю, что эти белые пиксели внутри вызваны самим внешним кругом (из алгоритма xiaolin wu).

edit 2:

Благодаря @JaMiT я улучшил свой коди это работает для одного круга, но терпит неудачу, когда у меня есть больше друг на друга.Во-первых, новый код:

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);
        }
    }
}

Без вызовов drawLine в setPixel4 это выглядит так:

Я улучшил setPixel4метод, чтобы избежать перерисовки того же пикселя снова:

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);
        }
    }

}

Затем, наконец:

Это почти идеально.Тем не менее, я изо всех сил пытаюсь избавиться от этого белого контура, но я не могу.

Answer 1

Подумайте о том, что вы делаете, чтобы получить третье изображение (изображение со "странными дырами" прямо внутри окружности).У вас нарисован внутренний диск, и вы хотите нарисовать круг вокруг него, чтобы сделать его чуть больше.Отличная идея.(Ваш учитель исчисления должен одобрить.)

Однако, Вы не просто рисуете вокруг него круг;вы рисуете сглаженный круг вокруг него.Что это значит?Это означает, что вместо того, чтобы просто рисовать точку, вы рисуете две с разной прозрачностью, чтобы обмануть глаз, думая, что это только одна.Одна из этих точек (внутренняя) будет перезаписывать точку диска, которую вы уже нарисовали.

Когда внешняя точка более прозрачна, нет никаких проблем, кроме, возможно, небольшого размытия.Однако, когда точка внутренняя становится более прозрачной, происходит странное поведение, когда диск становится в основном непрозрачным, становится более прозрачным, а затем возвращается к полной непрозрачности.Вы взяли с диска полностью непрозрачную точку и сделали ее в основном прозрачной.Ваш глаз интерпретирует это как дыру.

Итак как это исправить ?

1) Пока ваш диск должен быть однородно окрашен (учитывая прозрачность)Ваша последняя попытка должна сработать, если вы перевернете внешний цикл - перейдите от наибольшего радиуса к нулю.Поскольку сглаживанию дается только самый внешний круг, только первая итерация этого обратного цикла перезапишет пиксель более прозрачным.И нечего перезаписывать на этом этапе.

ИЛИ

2) В обоих местах, где вы установили alpha2, установите его на maxTransparency.Это прозрачность внутреннего пикселя, и вы не хотите, чтобы внутренний край был сглаженным.Идите вперед и переберите радиусы в любом направлении, создавая свой диск из кругов.Держите обе пленки прозрачными на максимуме, когда не рисуете крайний круг.Этот подход имеет преимущество в том, что он может сделать дыру в середине вашего диска;startRadius не должно быть нулем.Когда вы находитесь на startRadius (и startRadius не ноль), установите alpha2 в соответствии с алгоритмом сглаживания, но установите alpha на maxTransparency.

Таким образом, ваша логика настройки альфа будет выглядетьчто-то вроде

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

Редактировать: Если подумать, было бы деление на ноль, если бы cRadius было ноль.Поскольку вы, очевидно, уже учли это, вы должны иметь возможность адаптировать понятие «первый» для обозначения «самого внутреннего круга, и мы фактически оставляем дыру».

ИЛИ

3) Вы можете рисовать линии, как было предложено, но есть несколько вещей, которые нужно настроить, чтобы минимизировать артефакты.Во-первых, удалите второй вызов setPixel4 в каждой паре;мы рассмотрим этот случай с помощью линий.Это устраняет необходимость иметь alpha2 (что в любом случае было причиной дыр).Во-вторых, попробуйте нарисовать прямоугольник (четыре линии) вместо двух параллельных линий.С помощью этого алгоритма половина рисунка основана на горизонтальных линиях, а половина - на вертикальных.Рисуя все время, вы покрываете свои базы.В-третьих, если вы все еще видите артефакты, попробуйте нарисовать вторую рамку внутри первой.

Answer 2

Поскольку вы дискретизируете круги, некоторые пиксели обязательно отсутствуют.На полученном рисунке показан эффект Муара, который хорошо известен.

Лучшее решение - использовать любой алгоритм заливки или синтезировать тривиальный алгоритм, который бы рисовал линии между точками окружностей на одинаковых горизонтальных линиях.(или вертикали, если вы предпочитаете).