简化的 Bresenham 线算法：它*到底*做什么？

Question

根据维基百科关于 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 在方式如代码中所示。

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

err到底做了什么以及为什么dx和dy 完全按照所示的方式使用布雷森汉姆直线算法的简化版本来保持水平和垂直步长之间的正确比例？

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)< /code> 是给定线上的一个点。

如果将 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;旨在最小化偏移误差；如果放大绘图比例，您会发现计算的线可能不会以不同的初始化位于所需的线的中心。

Answer 2

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

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