Graphics / Reference / Bresenham error accumulator
Bresenham error accumulator
Bresenham's error accumulator stores the line's offset from the currently selected row, then scales that offset so the decision can be maintained using integer additions, comparisons and subtractions.
Step 1 removes explicit rounding by writing the ideal line height as yi = y + yf, where y is the selected integer row and yf is the offset from that row. For an integer starting endpoint, initialise yf = 0.
Unscaled form:
m = (y1 - y0)/(x1 - x0) x = x0 yf = 0 y = y0 while x <= x1: DRAW(x,y) x = x + 1 yf = yf + m if yf > 1/2: y = y + 1 yf = yf - 1
The correction keeps yf within the interval from -1/2 to +1/2 relative to the selected row centre. With the strict > test, an exact +1/2 remains on the current row.
Step 2 multiplies all yf-related quantities by 2(x1 - x0). The slope increment becomes 2(y1 - y0), the threshold becomes x1 - x0, and the correction becomes 2(x1 - x0). In the source's step-2 listing, the name m is reused for this scaled increment; it is no longer the slope m of the unscaled form.
Scaled form:
m = 2*(y1 - y0) x = x0 yf = 0 y = y0 while x <= x1: DRAW(x,y) x = x + 1 yf = yf + m if yf > x1 - x0: y = y + 1 yf = yf - 2*(x1 - x0)
The final form precomputes dx = x1 - x0, d2x = dx + dx and d2y = 2(y1 - y0), then uses yf += d2y, compares yf > dx, and subtracts d2x when y increments.
Builds on
Read
- Read the chapter: Bresenham error accumulator