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.

A short DDA loop has callouts on the floating-point slope, stored ideal height, repeated floating-point addition and rounding operation used to choose each row.
DDA avoids repeated multiplication by x, but it still maintains floating-point slope and height state and rounds that height to choose rows.
Two next-column cases compare ideal heights against the halfway boundary between rows two and three, choosing row two for 2.4 and row three for 2.7.
The next pixel stays on y when the ideal height is at or below the halfway threshold and moves to y+1 only when it is above it.

Builds on

Read

Playgrounds