布雷森汉姆同心圆留下空像素 [英] Bresenham concentric circles leaving empty pixels

问题描述

我正在使用中点圆算法（也称为布雷森汉姆算法）绘制同心圆。每个圆的半径与下一个圆的半径之差始终为1，因此最终结果应为完整的圆形区域。

I am using the midpoint circle algorithm, also known as Bresenham's, to draw concentric circles. The difference between each circle's radius and that of the next is always 1, so the final result should be a full circular area.

但是，有些像素保留为空，因为

However, some pixels are left empty, as shown in the attached image.

我正在使用Javascript在HTML5画布上进行绘画，操作canvas.getContext（ 2d）。getImageData（...）数据数组。

I'm using Javascript to paint on an HTML5 canvas, manipulating the canvas.getContext("2d").getImageData(...).data array.

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

The circles are alternatively white and red, and the empty pixels are black. You might have to zoom in in order to see what I mean properly.

我正在尝试向算法中添加一些代码，以便在绘制相应的圆弧时填充这些像素。似乎没有理由让这些像素中的任何一个都属于一个弧而不是属于下一个弧，因此我不在乎是否将它们填充为半径为偶数的弧或半径为奇数的弧（I希望我能使自己清楚。）

I'm trying to add some code to the algorithm so that those pixels are filled when drawing the corresponding arc. There seems to be no reason for any of those pixels to belong to one arc rather than the next one, so I don't care if they are filled along with arcs that have an even radius or with arcs that have an odd radius (I hope I'm making myself clear).

像素似乎遵循某种模式，但是我不知道那是什么。有人可以帮我找到它吗？

The pixels seem to be following a pattern, but I'm clueless about what could that be. Could anyone help me find it?

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
}

推荐答案

Bresenham's使用一个像素乘以n个像素的区域绘制一条线。在45度时，它将先绘制一个像素，然后再绘制另一个像素（+ 1，+ 1）。这给出了1 /半径2的两个像素的中心之间的平均厚度。一像素粗线的精确图线的厚度为1。黑点是由于Bresenham算法线的厚度和真实厚度之间的差异所致。

Bresenham's is designed to plot a line using one pixel by n-pixel areas. At 45 degrees, it will plot one pixel then another (+1,+1) to it. This gives an average thickness between the centres of the two pixels of 1/√2. An exact plot of a one pixel thick line has a thickness of 1. The black dots are due to this difference between the thickness of the Bresenham algorithm line and the true thickness.

如果您扩展绘制的像素以包括所有像素，则它们的真实线交叉的中心将不存在任何间隙，因为其粗细永远不会小于1。一种方法是使用布雷森汉姆（Bresenham）的两次内半径和外半径，并根据两者之间的差异绘制像素。

If you extend the pixels plotted to include all pixels the centre of the true line crosses, it should not have any gaps, as its thickness will never be less than one. One way of doing this is to uses Bresenham's twice with inside and outside radii, and plotting pixels based on the difference between the two.

这篇关于布雷森汉姆同心圆留下空像素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！