简化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在完全显示的方式来维护使用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) = 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;旨在最小化偏移误差; 如果你炸掉你的绘图比例,你会发现你的计算线可能不会在具有不同初始化的所需线上居中.