Bresenham线算法 - 决策参数来自哪里？

Question

void line()
{
  int x1 = 10, y1 = 10, x2 = 300, y2 = 500  , x, y;
  int dx, dy, //deltas
      e;      // decision parameter

  glClear(GL_COLOR_BUFFER_BIT);
  glColor3f( 1 ,0, 0);
  setPixel(x1, y1); //plot first point

  // difference between starting and ending points
  dx = x2 - x1;
  dy = y2 - y1;
  e = 2 * dy - dx;
  x = x1; y = y1;

  for(int k = 0; k < dx - 1; ++k)
  {
    if(e < 0)
    {
      //next pixel: (x+1, y)
      e = e + 2*dy;
    } 
    else 
    {
      //next pixel: (x+1, y+1)
      e = e + 2*dy - 2*dx;
      ++y;
    }
    ++x;
    setPixel(x, y);
  }

  glFlush();
}

它e = 2*dy - dx来自哪里？为什么我们通过增加它2*dy还是2*dy - 2*dx？

Answer 1

Bresenham的算法仅使用整数运算.关键思想是最小化线方程增量评估的计算.

算法非常简单.让我们从线方程开始

f(x) = y = a*x +b

(现在假设0 <= a <1).当我们向右移动一个像素时,我们得到:

f(x+1) = a * (x+1) + b = f(x) + a

但是a和y都不是典型线的整数.所以我们只是介绍一个"错误".我们总是去找对方的邻居.在这样做的过程中,我们会a因为不上升而犯错误.如果我们的误差超过半个像素(0.5),我们就会上升(因此再次将误差值减少一个像素)

float e=a;
float y=y1;
int x=x1;
while(x<=x2) {
    SetPixel(x,y);
    x++;
    if (e > 0.5) {
        y++;
        e=e+a-1;
    } else {
        e=e+a;
    }
}

(注意,我们已经将误差设置e为a最初而不是零,因为我们总是在绘制像素后做出决定,并且我们不需要在绘制第一个像素之前检查条件,因为那个像素总是在这条线.)

现在,我们已经接近了.但是有两件事阻止我们使用整数:0.5,a哪个是dy/dx.但是:我们可以通过一个任意因子来缩放误差值(和条件),而不会改变任何东西.想一想:到目前为止我们已经测量了像素的误差(因为这看起来很直观),但是这个算法可以使用任意单位来表示误差值 - 半像素,双像素,pi像素.

所以,让我们只是按比例缩小2*dx上面的公式中的两个分数!(在某种程度上,它们的关键技巧是我们测量误差值的"单位"在算法中不是常数,而是线的函数).

int e=2*dy;
int y=y1;
int x=x1;
while(x<=x2) {
    SetPixel(x,y);
    x++;
    if (e > dx) {
        y++;
        e=e+2*dy - 2*dx;
    } else {
        e=e+2*dy;
    }
}

现在,我们有我们想要的东西:只有整数.(但有一点需要注意:通过从中float开始int,我们自动将线的端点"捕捉"到整数坐标 - 具有整数端点是Bresenham算法的一些先决条件(和限制).

还有一个技巧:条件包含一个变量.如果我们测试一个常量,理想情况下是零,那就更有效了(因为仅根据符号或零标志进行分支可以节省我们的比较操作).我们可以通过移动我们的错误值来实现这一目标.以与以前相同的方式,不仅可以任意选择误差值的标度,还可以选择原点.

由于我们测试e > dx当前,因此将错误移位-dx将允许我们进行测试0(0现在dx意味着之前的意思,即0.5像素).此移位仅影响初始值e和条件,所有增量保持与以前相同:

int e=2*dy-dx;
int y=y1;
int x=x1;
while(x<=x2) {
    SetPixel(x,y);
    x++;
    if (e > 0) {
        y++;
        e=e+2*dy - 2*dx;
    } else {
        e=e+2*dy;
    }
}

瞧,这个2*dy-dx词突然出现......;)