Derivation of Bresenham's algorithm

Floating point line drawing algorithm. We will assume that x1 < x2, y1 < y2, and that (x2 - x1) >= (y2 - y1) for simplicity:

void
draw_line(int x1, int y1, int x2, int y2)
{
    float y = y1 + 0.5f;
    float dy = (float)(y2 - y1) / (x2 - x1); // NOTE: dy <= 1.0f
    for (int x = x1; x <= x2; ++x) {
        plot(x, (int)y);
        y += dy;
    }
}

Now separate the integer and floating-point parts of y:

void
draw_line(int x1, int y1, int x2, int y2)
{
    int yi = y1;
    float yf = 0.5f;
    float dy = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x) {
        plot(x, yi);
        yf += dy;
        if (yf >= 1.0f) {
            yf -= 1.0f;
            ++yi;
        }
    }
}

Now multiply dy and yf by 2*(x2 - x1) everywhere to make them integers:


void
draw_line(int x1, int y1, int x2, int y2)
{
    int yi = y1;
    int yf = x2 - x1;
    int dy = 2 * (y2 - y1);
    for (int x = x1; x <= x2; ++x) {
        plot(x, yi);
        yf += dy;
        if (yf >= 2 * (x2 - x1)) {
            yf -= 2 * (x2 - x1);
            ++yi;
        }
    }
}

We now have integer line drawing!