Using the integer scaled error term. Here we see that the integer scaled error term correctly chooses the correct pixels. Here we are comparing the integer scaled error term to dx to determine pixel position. Is there a yet faster comparison that we could use? What comparison is faster than comparing an integer to some arbitrary value? Could we use that comparison here?

We now have the basis for a line scan-conversion algorithm that uses only integer arithmetic. The following is C code that implements Bresenham's algorithm for lines whose slopes are between 0 and 1. All of the variables are integers. Notice that all of quantities that are added to or subtracted from 'ie' (the integer scaled error term) have been scaled by 2 *dx. The code may easily be modified to work for all slopes.

The code, as written, is still not quite as fast as it could be. What modifications would make the algorithm even faster?

void Bresenham (int xl, int yl, int xr, int yr)

/* xl, yl: coordinates of the left endpoint */
/* xr, yr: coordinates of the right endpoint */
{
int x,y; /* coordinates of pixel being drawn */
int dy, dx; /* rise, run */
int ie; /* integer scaled error term */

x = xl; /* start at left endpoint */
y = yl;
ie = 2 * dy - dx; /* initialize the error term */
/* pixel-drawing loop */
while (x <= xr){
PlotPixel (x,y); /* draw the pixel */
if (ie > 0) {
y = y + 1;
ie = ie - 2 * dx; /* replaces e = e - 1 */
}
x = x + 1;
ie = ie + 2 * dy; /* replaces e = e + m */
}
}

Back

Quit