绘制实心圆的快速算法？

Question

我正在使用Bresenham的圆形算法进行快速圆绘制.但是,我也希望(应用户的要求)画一个圆圈.

有这样快速有效的方法吗？布雷森汉姆沿袭同样的路线？

我使用的语言是C.

Answer 1

阅读了关于Bresenham(也称为"Midpoint")圈算法的维基百科页面,看起来最简单的事情就是修改它的动作,而不是

setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);

和你说的相似

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);

也就是说,对于yBresenham你想要绘制的每一对点(具有相同的),你改为用线连接.

Answer 2

只需使用蛮力.此方法迭代了太多像素,但它只使用整数乘法和加法.你完全避免了Bresenham的复杂性和sqrt的可能瓶颈.

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Answer 3

这是一个C#粗略指南(不应该很难得到C的正确想法) - 这是"原始"形式,而不使用Bresenham来消除重复的平方根.

Bitmap bmp = new Bitmap(200, 200);

int r = 50; // radius
int ox = 100, oy = 100; // origin

for (int x = -r; x < r ; x++)
{
    int height = (int)Math.Sqrt(r * r - x * x);

    for (int y = -height; y < height; y++)
        bmp.SetPixel(x + ox, y + oy, Color.Red);
}

bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");

Answer 4

你可以用这个:

void DrawFilledCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int xChange = 1 - (radius << 1);
    int yChange = 0;
    int radiusError = 0;

    while (x >= y)
    {
        for (int i = x0 - x; i <= x0 + x; i++)
        {
            SetPixel(i, y0 + y);
            SetPixel(i, y0 - y);
        }
        for (int i = x0 - y; i <= x0 + y; i++)
        {
            SetPixel(i, y0 + x);
            SetPixel(i, y0 - x);
        }

        y++;
        radiusError += yChange;
        yChange += 2;
        if (((radiusError << 1) + xChange) > 0)
        {
            x--;
            radiusError += xChange;
            xChange += 2;
        }
    }
}

Answer 5

我喜欢palm3D的答案.对于蛮力,这是一个非常快速的解决方案.没有平方根或三角函数来减慢速度.它的一个弱点是嵌套循环.

将其转换为单个循环使此功能几乎快两倍.

int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;

for (int i = 0; i < area; i++)
{
    int tx = (i % rr) - r;
    int ty = (i / rr) - r;

    if (tx * tx + ty * ty <= r2)
        SetPixel(x + tx, y + ty, c);
}

这种单循环解决方案可以与线条绘制解决方案的效率相媲美.

            int r2 = r * r;
            for (int cy = -r; cy <= r; cy++)
            {
                int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
                int cyy = cy + y;

                lineDDA(x - cx, cyy, x + cx, cyy, c);
            }

Answer 6

我发现 palm3D 的暴力算法是一个很好的起点。此方法使用相同的前提，但它包括几种跳过检查大多数像素的方法。

首先，这是代码：

int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
    for (int x = largestX; x >= 0; --x) {
        if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
            largestX = x;
            break; // go to next y coordinate
        }
    }
}

接下来，进行解释。

首先要注意的是，如果找到给定水平线的圆内的最小 x 坐标，您立即就知道最大 x 坐标。这是由于圆的对称性。如果最小 x 坐标为圆边界框左侧前方 10 个像素，则最大 x 坐标为圆边界框右侧后方 10 个像素。

从高 x 值迭代到低 x 值的原因是，可以通过较少的迭代找到最小 x 值。这是因为对于大多数线来说，最小 x 值比圆的中心 x 坐标更靠近边界框的左侧，因为圆向外弯曲，如此图所示 ，由于圆也是垂直对称的，你找到的每条线都会给你一条免费的第二条线来绘制，每次你在圆的上半部分找到一条线，你就会在半径 y y 坐标的下半部分得到一条线。因此，当找到任何一条线时，可以绘制两条线，并且只需要迭代 y 值的上半部分。

最后要注意的是，如果从圆心的 y 值开始，然后向 y 的顶部移动，则下一行的最小 x 值必须更接近圆心的 x 坐标圆比最后一行。这也是由于当您沿着圆向上移动时，圆会弯曲得更接近中心 x 值。这是关于这种情况的视觉效果。

总之：

1. 如果找到一条线的最小 x 坐标，则可以免费获得最大 x 坐标。
2. 您在圆的上半部分找到的每条线都会免费为您在圆的下半部分绘制一条线。
3. 当从中心 y 坐标迭代到顶部时，每条线的每个最小 x 坐标都必须比前一个 x 坐标更接近圆的中心。

(radius * radius)您还可以存储、 和的值，(y * y)而不是多次计算它们。

Answer 7

这里的好主意！由于我在一个需要绘制数千个圆圈的项目中，我在这里评估了所有建议（并通过预先计算半径的平方改进了一些建议）：

http://quick-bench.com/mwTOodNOI81k1ddaTCGH_Cmn_Ag

Rev 变体只是交换了 x 和 y，因为按照我的网格/画布结构的工作方式，沿 y 轴的连续访问速度更快。

明显的赢家是 Daniel Earwicker 的方法 (DrawCircleBruteforcePrecalc)，它预先计算 Y 值以避免不必要的半径检查。有点令人惊讶的是，这否定了由 sqrt 调用引起的额外计算。

一些评论表明 kmillen 的变体 (DrawCircleSingleLoop) 与单个循环一起工作应该非常快，但它在这里是最慢的。我认为这是因为所有的分歧。但也许我已经将它错误地适应了该代码中的全局变量。如果有人看一下就好了。

编辑：自大学以来第一次寻找汇编代码后，我设法发现圆的起源的最后添加是罪魁祸首。预先计算这些，根据工作台，我将最快的方法提高了 3.7-3.9 倍！ http://quick-bench.com/7ZYitwJIUgF_OkDUgnyMJY4lGlA 太棒了。

这是我的代码：

for (int x = -radius; x < radius ; x++)
{
    int hh = (int)std::sqrt(radius_sqr - x * x);
    int rx = center_x + x;
    int ph = center_y + hh;

    for (int y = center_y-hh; y < ph; y++)
        canvas[rx][y] = 1;
}