Understanding Bresenham's error accumulation part of the algorithm?

Question

I'm having issues understanding how the error accumulation part works in Bresenham's line drawing algorithm.

Say we have x1 and x2. Let's assume that x1 < x2, y1 < y2, and (x2 - x1) >= (y2 - y1) for simplicity:

Let's start with the naive way of drawing a line. It would look something like:

void DrawLine(int x1, int y1, int x2, int y2)
{
    float y = y1 + 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, (int)y);
        y += slope;
    }
}

Let's make it more Bresenham'ish, and separate the integer and floating-point parts of y:

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

At this point we could multiply yf and slope by 2 * (x2 - x1) to make them integers, no more floats. I understand that.

The part I don't fully understand, is this:

    if (yf >= 1.0f)
    {
        yf -= 1.0f;
        ++yi;
    }

How does that actually work? why are we comparing against 1.0 and then decrementing by it?

I know that the basic question of Bresenham is: If we're currently at pixel x, y and we want to draw the next one, should we pick x + 1, y or x + 1, y + 1? - I just don't understand how that check is helping us answer this question.

Some people call it error term, some call it threshold, I just don't get what it represents.

Any explanations is appreciated, thanks.

score 2 · Accepted Answer · answered Feb 16 '16 at 03:45

Bresenham's line rasterization algorithm performs all the calculations in integer arithmetic. In your code you are using float types and you shouldn't.

First consider that you know two pixels that are on the line. The starting pixel and the end pixel. What the algorithm calculates are the pixels that approximate the line such that the rasterized line starts and stops on the two input pixels.

Second, all lines drawn are reflections of lines with slope between 0 and 0.5. There is a special case for vertical lines. If your algorithm is correct for this input, then you need to initialize the starting state of the rasterizer to correctly rasterize a line: start pixel (x, y), ∆x, ∆y, and D the decision variable.

Since you can assume all lines are drawn from left to right, have positive slope equal to or less than 0.5, the problem boils down to: is the next rasterized pixel to the current pixels right or to the right and up one pixel.

You can make this decision by keeping track of how much your rasterized line deviates from the true line. To do so, the line equation is re-written into an implicit function, F(x, y) = ∆yx - ∆xy + ∆xb = 0 and you repeatedly evaluate it F(x + 1 y + 0.5). Since that requires floating point math, you focus on identifying if you are on, above, or below the true line. Therefore, F(x + 1 y + 0.5) = ∆y - 0.5∆x and multiplying by two 2 * F(x + 1 y + 0.5) = 2∆y - ∆x. That's the first decision, if the result is less than zero, add one to x but zero to y.

The second decision and subsequent decisions follow similarly and the error is accumulated. A decision variable D is initialized to 2∆y - ∆x. If D < 0, then D = D + 2∆y; else y = y + 1 and D = D + 2(∆y - ∆x). The x variable is always incremented.

Jim Arvo had a great explanation of Bresenham's algorithm.

Thanks for the answer. Nice article! One thing it doesn't cover is how to adapt the algorithm to work with other octants and cases where m > 1. Any ideas? — vexe, Feb 16 '16 at 05:19

score 1 · Answer 2 · answered Feb 16 '16 at 03:52

In your implementation yf is a 0.5 + distance between real floating-point Y coordinate and drawn (integral) Y coordinate. This distance is the current error of your drawing. You want to keep the error within at most half-of-pixel between real line and drawn line (-0.5..+0.5), so your yf which is 0.5+error should be between 0 and 1. When it exceeds one, you just increase your drawn Y coordinate (yi) by one and you need to decrease an error by one. Let's take an example:

slope = 0.3;
x = 0; yf = 0.5; y = 0; // start drawing: no error
x = 1; yf = 0.8; y = 0; // draw second point at (1, 0); error is +0.3
x = 2; yf = 1.1; y = 0; // error is too big (+0.6): increase y
       yf = 0.1; y = 1; // now error is -0.4; draw point at (2, 1)
x = 3; yf = 0.4; y = 1; // draw at (3, 1); error is -0.1
x = 4; yf = 0.7; y = 1; // draw at (4, 1); error is +0.2
x = 5; yf = 1.0; y = 1; // error is too big (+0.5); increase y
       yf = 0.0; y = 2; // now error is -0.5; draw point at (5, 2)

And so on.

Thanks for the reply. So the 'error term' is just the difference/distance between the rasterized integer and actual floating-point coordinates of the line? — vexe, Feb 16 '16 at 05:23

Understanding Bresenham's error accumulation part of the algorithm?

2 Answers2