java - 简化的 Bresenham 线算法 : What does it *exactly* do?

Question

根据维基百科关于 Bresenham 直线算法的文章，我实现了 simplified version在那里描述，我的 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 以代码中所见的方式更改.

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

err 究竟做了什么以及为什么 dx 和 dy 以完全显示的方式使用以保持正确的比率使用此简化版 Bresenham 线算法的水平和垂直步长？

Answer 1

直线方程有多种形式，最熟悉的一种是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) = 0 iff (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; 旨在最小化偏移误差；如果放大绘图比例，您会发现计算出的线可能不会以不同的初始化位于所需线的中心。