Xiaolin Wu 圆算法渲染圆里面有洞

Question

我从这里实现了 Xiaolin Wu 圆算法：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为圆心坐标

在我看来它看起来不错：

但是，我需要填充圆圈。也许我错了，但我开发了一个简单的算法：从 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);
    }
}

我该如何解决这个问题？

编辑：

因为我不能使用flood-fill填充圆圈（我绘制的区域可能不是单色背景，我需要混合这些颜色）我实现了简单的方法来连接点和线：

我在 setPixel4 方法中添加了 2 个 drawLine 调用：

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算法）本身造成的。

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

在 setPixel4 中没有 drawLine 调用，它看起来像这样：

我改进了 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

因为您将圆圈离散化，所以一些像素必然会丢失。你得到的图片有莫尔效应，这是众所周知的。

最好的解决方案是使用任何洪水填充算法或合成简单的算法，该算法会在同一水平线（如果您愿意，也可以是垂直线）上的圆点之间画线。

Answer 2

想想你正在做什么来获得第三张图片（圆周内有 "strange holes" 的图片）。您已经绘制了内圆盘，您想要围绕它画一个圆圈以使其稍微大一点。好主意。（你的微积分老师应该会批准。）

但是，您不只是简单地围绕它画一个圆圈；你在它周围画了一个 抗锯齿 圆圈。那是什么意思？这意味着你不是简单地画一个点，而是画两个，用不同的透明度来欺骗眼睛，让它认为它只是一个。其中一个点（内部点）将覆盖您已经绘制的圆盘上的一个点。

当外点更透明时，除了可能有点模糊之外没有问题。但是，当 inner 点更透明时，您会遇到这种奇怪的行为，即磁盘开始大部分不透明，变得更透明，然后 returns 完全不透明。您从圆盘上取了一个完全不透明的点并使其大部分透明。你的眼睛将其解释为一个洞。

那么如何解决这个问题？

1) 只要您的磁盘应该是统一着色的（考虑到透明度），如果您反转外环，您最后的尝试应该会成功——从最大半径到零。由于只有最外面的圆被赋予抗锯齿功能，因此只有这个反向循环的第一次迭代会用更透明的像素覆盖像素。在那个阶段没有什么可以覆盖的。

或

2) 在设置alpha2的两个地方，都设置为maxTransparency。这是内部像素的透明度，您不希望内部边缘被抗锯齿。继续并沿任一方向循环半径，从圆圈中构建您的磁盘。不绘制最外圈时，请将两个透明度都设置为最大。这种方法的优点是可以在磁盘中间打一个洞； startRadius 不必为零。当你在startRadius（且startRadius不为零）时，根据反锯齿算法设置alpha2，但将alpha设置为maxTransparency。

所以你的 alpha 设置逻辑看起来像

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

编辑： 仔细想想，如果 cRadius 为零，就会被零除。由于您显然已经考虑到了这一点，因此您应该能够将 "first" 的概念调整为表示 "innermost circle and we are in fact leaving a hole".

或

3) 您可以按照建议绘制线条，但需要进行一些调整以最大程度地减少伪影。首先，删除每对中对 setPixel4 的第二次调用；我们将用台词覆盖这种情况。这消除了 alpha2 的需要（无论如何这是漏洞的原因）。其次，尝试画一个方框（四条线）而不是两条平行线。使用此算法，绘图的一半基于水平线，一半基于垂直线。通过始终绘制两者，您可以覆盖基础。第三，如果您仍然看到瑕疵，请尝试在第一个框内绘制第二个框。

Answer 3

你应该只画一个外圆，用简单的水平实线从左到右像素边连接。

]1

Xiaolin Wu 圆算法渲染圆里面有洞

Xiaolin Wu circle algorithm renders circle with holes inside

c++

rendering

antialiasing

cocos2d-x