Bresenham line algorithm - where does the decision parameter come from?

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();
}

Where does the e = 2*dy - dx come from? Why do we increase it by 2*dy or 2*dy - 2*dx?

Answer 1

Bresenham's algorithm uses only integer arithmetic. The key idea is to minimize the calculations for incremental evaluation of the line equation.

The algorithm is really simple. Let's start with the line equation

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

(and assume 0 <= a < 1 for now). When we go one pixel to the right, we get:

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

But both a and y will not be integers for the typical line. So let's just introduce an "error". We always go to the right neighbor. In doing so, we make an error of a by not going up. If our error is above half a pixel (0.5), we go up (and hence decrease the error value by a pixel again)

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;
    }
}

(Note that we already set the error e to a initially and not to zero, because we always make the decision after the pixel is drawn, and we don't need to check the condition before drawing the very first pixel because that one is always exactly on the line.)

Now, we have come close. But there are two things which prevent us from using integers: the 0.5 and a which is dy/dx. But: we can scale the error value (and the condition) by an arbitray factor, without changing anything. Think about it: we've measured the error in pixels so far (because that seems intuitive at first), but this algorithm could use any arbitrary unit for the error value - half pixels, double pixels, pi pixels.

So let's just scale it by 2*dx to get rid of both fractions in the formula above! (In a way, they key trick here is that the "unit" in which we measure the error value is just not constant in the algorithm, but a function of the line).

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;
    }
}

Now, we have what we want: only integers. (One thing to note here, though: by going from float to int, we automatically "snap-in" the line's endpoints to integer coordinates - having integer endpoints is some precondition for (and limitation of) the Bresenham algorithm).

There is one additional trick: the condition contains a variable. It would be even more efficient, if we would test against a constant, and ideally against zero (since branching depending just on the sign or zero flags saves us a compare operation). And we can achive this, by just shifiting our error values. In the same way as before, not only the scale of the error value cane be chosen arbitrarily, but also origin.

Since we test for e > dx currently, shifting the error by -dx will allow us to test against 0 (and 0 now means what dx meant before, namely 0.5 pixels). This shift only affects the initial value of e, and the condition, all the increments stay the same as before:

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;
    }
}

Voila, the 2*dy-dx term has suddenly emerged... ;)