12

基于维基百科关于 Bresenham 的线算法的文章，我已经实现了那里描述的简化版本，我的 Java 实现如下所示：

int dx = Math.abs(x2 - x1);
int dy = Math.abs(y2 - y1);

int sx = (x1 < x2) ? 1 : -1;
int sy = (y1 < y2) ? 1 : -1;

int err = dx - dy;

while (true) {
    framebuffer.setPixel(x1, y1, Vec3.one);

    if (x1 == x2 && y1 == y2) {
        break;
    }

    int e2 = 2 * err;

    if (e2 > -dy) {
        err = err - dy;
        x1 = x1 + sx;
    }

    if (e2 < dx) {
        err = err + dx;
        y1 = y1 + sy;
    }
}

现在我明白了，它err控制了 x 轴上的步数与 y 轴上的步数之间的比率——但现在我应该记录代码在做什么，但我无法清楚地表达它的用途，以及为什么if 语句是这样的，它们是如何err变化的，以及为什么会以代码中看到的方式发生变化。

维基百科没有指向任何更详细的解释或来源，所以我想知道：

使用此简化版本的 Bresenham 线算法，究竟做了什么err？dxdy

4

2 回答 2

13

直线有多种形式的方程，其中最熟悉的一种是y=m*x+b。现在如果m=dy/dx和c = dx*b，那么dx*y = dy*x + c。写作f(x) = dy*x - dx*y + c，我们有f(x,y) = 0iff(x,y)是给定线上的一个点。

如果您推进x一个单位，f(x,y)则更改为dy; 如果您推进y一个单位，f(x,y)则更改为dx。在您的代码中，err表示线性函数的当前值f(x,y)，以及语句序列

    err = err - dy;
    x1 = x1 + sx;

和

    err = err + dx;
    y1 = y1 + sy;

表示前进x或y一个单位（在sx或sy方向上），从而对函数值产生影响。如前所述，f(x,y)线上的点为零；线一侧的点为正，另一侧的点为负。测试if确定前进是否x会比前进更接近所需的线y，反之亦然，或两者兼而有之。

初始化err = dx - dy;旨在最小化偏移误差；如果你放大你的绘图比例，你会发现你的计算线可能不在具有不同初始化的所需线的中心。

于 2011-11-13T19:03:08.027 回答
1

只想在 jwpat 的出色答案中添加一点“为什么”信息。

使用f(x) = dy*x - dx*y + c公式的目的是加快计算速度。此公式使用整数运算（更快），而传统y = mx + b公式使用浮点运算（较慢）。

于 2013-11-03T01:10:34.390 回答