4 
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*dyor 2*dy - 2*dx？

4

2 回答 2

9

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.5a和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词突然出现了……；）

于 2013-10-04T22:20:32.587 回答
0

术语 2dy-dx 出现在我们在公式 (2dy•xk-2dx•yk+2dy+(2b-1)) 中填充 xk =yk=0 之后，因为对于第一个参数，我们假设线的起点位于原点，即 ( 0,0)。b 是常数，因此被忽略。自己试试吧。

于 2019-11-16T05:20:02.060 回答