Graphics / Reference / Bresenham line rasterisation
Bresenham line rasterisation
Bresenham line rasterisation reduces the first-octant pixel choice to an integer binary decision: at each new column, either remain on row y or advance to row y+1.
Bresenham's line method replaces the floating-point slope, accumulated line height and rounding used by DDA with integer arithmetic for the first-octant, integer-endpoint case. Reference: J. E. Bresenham, "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4(1), 1965.
At each new column, the next pixel has two candidate rows: stay at y or move to y + 1. Conceptually, the upper row is selected when the ideal line lies more than 1/2 pixel above the current row centre; otherwise the current row is kept.
Final integer form:
dx = x1 - x0 d2x = dx + dx d2y = 2*(y1 - y0) x = x0 yf = 0 y = y0
while x <= x1: DRAW(x,y) x = x + 1 yf = yf + d2y if yf > dx: y = y + 1 yf = yf - d2x
The comparison is strict: yf > dx. An exact half therefore remains on the lower row under this convention.
The DDA comparison diagram marks its floating-point operations; the Bresenham decision diagram instead shows the two candidate rows and the half-pixel threshold.
Builds on
Read
- Read the chapter: Bresenham line rasterisation