javascript - Bresenham 同心圆留下空像素

Question

我正在使用中点圆算法(也称为 Bresenham 算法)来绘制同心圆。每个圆的半径与下一个圆的半径之差始终为 1，因此最终结果应该是一个完整的圆形区域。

但是，如附图所示，一些像素留空。

我正在使用 Javascript 在 HTML5 Canvas 上绘画，操作 canvas.getContext("2d").getImageData(...).data 数组。

圆圈是交替的白色和红色，空像素是黑色的。您可能需要放大才能正确理解我的意思。

我正在尝试向算法中添加一些代码，以便在绘制相应的弧形时填充这些像素。这些像素中的任何一个似乎都没有理由属于一个弧而不是下一个，所以我不在乎它们是用偶数半径的弧还是奇数半径的弧填充的(我希望我说清楚了)。

像素似乎遵循某种模式，但我不知道那是什么。谁能帮我找到它？

function drawCircles(radius, x, y){
    var f = 1 - radius;
    var ddF_x = 1;
    var ddF_y = -2 * radius;
    var x = 0;
    var y = radius;

    //Colors
    var red = 255;       
    var green = radius%2==0?255:0;       
    var blue = radius%2==0?255:0;        

    paintPixel(x, y + radius, red, green, blue);
    paintPixel(x, y - radius, red, green, blue);
    paintPixel(x + radius, y, red, green, blue);
    paintPixel(x - radius, y, red, green, blue);    

    while(x < y){
        // ddF_x == 2 * x + 1;
        // ddF_y == -2 * y;
        // f == x*x + y*y - radius*radius + 2*x - y + 1;
        if(f >= 0) 
        {
            y--;
            ddF_y += 2;
            f += ddF_y;
        }
        x++;
        ddF_x += 2;
        f += ddF_x;    
        paintPixel(x + x, y + y, red, green, blue);
        paintPixel(x - x, y + y, red, green, blue);
        paintPixel(x + x, y - y, red, green, blue);
        paintPixel(x - x, y - y, red, green, blue);
        paintPixel(x + y, y + x, red, green, blue);
        paintPixel(x - y, y + x, red, green, blue);
        paintPixel(x + y, y - x, red, green, blue);
        paintPixel(x - y, y - x, red, green, blue);
    }

}

function paintPixel(x, y, red, green, blue){
    imageData.data[grid[y][x]] = red;
    imageData.data[grid[y][x]+1] = green;
    imageData.data[grid[y][x]+2] = blue;
    imageData.data[grid[y][x]+3] = 255; //Alpha
}

Answer 1

Bresenham 的设计旨在使用一个像素乘 n 个像素区域绘制一条线。在 45 度时，它将绘制一个像素，然后绘制另一个 (+1,+1)。这给出了 1/√2 的两个像素中心之间的平均厚度。一个像素粗线的精确图的粗细为 1。黑点是由于 Bresenham 算法线的粗细与真实粗细之间的差异造成的。

如果您扩展绘制的像素以包括真实线中心交叉的所有像素，它不应该有任何间隙，因为它的厚度永远不会小于 1。一种方法是使用具有内外半径的 Bresenham 两次，并根据两者之间的差异绘制像素。