c ++ Bresenham的线算法绘制弧和旋转

Question

我正在寻找用Bresenham的线算法制作弧线的方法.这个算法绘制了完美的圆形,但如果我需要绘制弧线(从0到Pi)并将其旋转30度(例如),该怎么办？

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{
        int x = 0;
        int y = radius;
        int delta = 2 - 2 * radius;
        int error = 0;

        while(y >= 0) {
                //SetPixel(hdc,x0 + x, y0 + y,pencol);
                SetPixel(hdc,x0 + x, y0 - y,pencol);
                //SetPixel(hdc,x0 - x, y0 + y,pencol);
                SetPixel(hdc,x0 - x, y0 - y,pencol);
                error = 2 * (delta + y) - 1;
                if(delta < 0 && error <= 0) {
                        ++x;
                        delta += 2 * x + 1;
                        continue;
                }
                error = 2 * (delta - x) - 1;
                if(delta > 0 && error > 0) {
                        --y;
                        delta += 1 - 2 * y;
                        continue;
                }
                ++x;
                delta += 2 * (x - y);
                --y;
        }
}

Answer 1

如果你不需要确定的Bresenham，这篇SO文章中介绍了一种快速步骤方法，你可以在其中设置中心点、起点和圆弧角度。它不需要停止标准，因为它已经包含在算法中（通过弧角）。其速度快的原因是切向和径向运动因子的预先计算，并且实际循环没有三角函数调用，只有乘法、加法和减法。

AFAIK 方法分为三种类型：
A）像 Bresenham 那样的增量
方法 B）像这样的
细分 方法 C）步进（或分段）方法

我将举一个逐步方法的缓慢示例（如果速度很重要，请不要使用此方法）：

// I know the question is tagged c++, but the idea comes clear in javascript
var start_angle = 0.5, end_angle = 1.1, r = 30;
for(var i = start_angle; i < end_angle; i = i + 0.05)
{
  drawpixel(x: 50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (x = 50, y = 100)
}

缓慢来自于 cos 和 sin 在循环中（不必要地）重复。这可以通过预先计算 cos 和 sin 来解决，如上述 SO 帖子中所述。这意味着巨大的加速（前 5 名 JavaScript 引擎平均加速 12 倍）。

我对各种圆和圆弧绘制算法进行了非完全可比的速度测试。Bresenham速度很快，但需要添加启动和停止标准逻辑，这会稍微减慢算法速度。如果你真的需要 Bresenham 和 arc，我没有现成的解决方案，而且还没有找到。这当然是可能的。顺便说一句，与 Bresenham 相比，使用预先计算的三角函数的步骤方法的性能并不算差（至少在 javascript 中）。请用 c++ 进行测试并报告。

Answer 2

要获得 1/2 圆（到 pi），只需调用 SetPixel 例程之一。要使弧线旋转 30 度，需要一些三角技术。您可以让上面的循环运行，直到您的 x/y 比率等于 tan（30 度），然后开始实际绘制，直到您的比率达到您想要停止的值。这不是最有效的方法，但它会起作用。为了获得更好的效果，您需要预先计算起始的 4 个 var 值。您可以从上面的运行中获取值并将它们作为起始值插入，这将非常有效。

您是从Michael Abrash 的 Black Book中得到上述算法的吗？如果没有，我会在谷歌上搜索它作为快速圆/弧绘图的第二个参考点。

好吧，唉，撕开章节的省略号没有包含在其中。以下是我在网上找到的声称来自 Abrash 的内容：

/* One of Abrash's ellipse algorithms  */

void draw_ellipse(int x, int y, int a, int b, int color)
{
    int wx, wy;
    int thresh;
    int asq = a * a;
    int bsq = b * b;
    int xa, ya;

    draw_pixel(x, y+b, color);
    draw_pixel(x, y-b, color);

    wx = 0;
    wy = b;
    xa = 0;
    ya = asq * 2 * b;
    thresh = asq / 4 - asq * b;

    for (;;) {
        thresh += xa + bsq;

        if (thresh >= 0) {
            ya -= asq * 2;
            thresh -= ya;
            wy--;
        }

        xa += bsq * 2;
        wx++;

        if (xa >= ya)
          break;


        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }

    draw_pixel(x+a, y, color);
    draw_pixel(x-a, y, color);

    wx = a;
    wy = 0;
    xa = bsq * 2 * a;

    ya = 0;
    thresh = bsq / 4 - bsq * a;

    for (;;) {
        thresh += ya + asq;

        if (thresh >= 0) {
            xa -= bsq * 2;
            thresh = thresh - xa;
            wx--;
        }

        ya += asq * 2;
        wy++;

        if (ya > xa)
          break;

        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }
}

这个想法是你一次画一个圆的八分之四，然后翻转以绘制其他八分之一。但仍然没有直接回答你的问题。正在努力...

同样，上面的代码应该可以工作，您只需要仔细控制开始和结束条件即可。y >= 0 需要成为完成“弧”长度后 y 的值，并且需要计算起始值作为弧的起点。

就目前的情况而言，这并不是一项直接的任务。使用浮点例程可能会更容易。与设计这些整数例程时相比，数学更加直接，处理器现在往往可以更好地处理它们。