Bresenham's Line Algorithm versus Naive Vector Addition

Question

Given xlen is delta-x, ylen is delta-y, len is the length of the line, why is this code:

//Bresenham implementation
float x = x0, y = y0;

if (slope < 1) {
    while (x < xlen) {
        paintpt(x, y));
         x += step;
        if (left.y > right.y) 
            y += slope * step;
        else 
            y -= slope * step;
   }
}

any more efficient than this code?

//Naive vector addition
int x = x0, y = y0;
float xinc = xlen / len, yinc = ylen / len;

for (float i = 0; i < len; i++) {
   paintpt(x, y);
   x += i * xinc;
   y += i * yinc;
}

(I mean, aside from initialization, obviously. Assume that you're only given the line-length and direction and have to back out the slope and whatnot, or something.)

Answer 1

1) x += i * xinc; this is a float multiplication rounded to an integer. It doesn't guarantee you to go through all integers from you starting x to your final x. This means your line may have holes in it...

2) Your Bresenham implementation is wrong. You do not add steps to x. You increment xon every iteration and add delta_y to an error counter. When the error counter is larger than delta_x you increment y and substract delta_x from the error counter.

This is the explanation for a line whose delta_y is greater than 0 and inferior to delta_x. Do the rotation for all other cases.

3) For efficiency: this is a bit tricky. Oldest computers could not do floating point computation easily. Up until the Pentium it was common to not have any x87 coprocessor and all floating point computation was done in software. This was 1000s times slower than doing simple integer arithmetic. Nowadays all computers can do SIMD operations (i.e. they use floating-point vector extensions); it may not be the case any more.

Answer 2

The Bresenham algorithm hails from the 60's, when computers fit into big closets. Its hallmarks were/are:

• no floating point math,
• no multiplications/divisions.

Since in those days, even integer divisions and multiplications were "expensive". A "true" Bresenham implementation will not divide/multiply and will not use floating point math. Your implementation is "false". Check here for a "true" one.