一尘不染

简化的布雷森纳姆(Bresenham)线路算法:“确实”是做什么的?

algorithm

根据Wikipedia关于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做,为什么dxdy在完全显示方式使用Bresenham直线算法的这个简化版保持水平和垂直步骤之间的正确比例使用?


阅读 345

收藏
2020-07-28

共1个答案

一尘不染

直线有多种形式的方程式,其中一种最为常见y=m*x+b。现在如果m=dy/dxc = dx*b,那么dx*y = dy*x + c。写作f(x) = dy*x - dx*y + c,我们有f(x,y) = 0当且仅当(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;

表示前进xy一个单位(沿sxsy向),对功能值有影响。如前所述,f(x,y)线上的点为零;直线一侧的点为正,另一侧的点为负。该if测试确定是否前进x会留比前进更接近期望线y,或反之亦然,或者两者兼而有之。

初始化err = dx - dy;旨在最大程度地减少偏移误差。如果放大绘图比例,则会看到您的计算线可能不会通过不同的初始化而位于所需线的中心。

2020-07-28