Graphics / Reference / DDA line rasterisation

DDA line rasterisation

DDA line rasterisation replaces repeated evaluation of y = mx + c with an incremental floating-point update. Each one-column step adds the constant slope m to the current ideal line height.

DDA means digital differential analyser. For a first-octant line with integer endpoints, it uses the fixed difference in y between adjacent columns rather than recomputing the line equation from scratch.

Initialise:

m = (y1 - y0)/(x1 - x0) x = x0 yi = y0 y = y0

Then iterate while x <= x1:

DRAW(x,y) x = x + 1 yi = yi + m y = ROUND(yi)

The key replacement is yi = yi + m instead of yi = m*x + c. yi starts at y0 because the line passes through the first endpoint. In this site's DDA implementation, ROUND uses the same half-up policy as the direct line drawer: y = floor(yi + 0.5).

The update follows from the one-column step: if yi = m*x + c, then at x + 1 the line height is m*(x + 1) + c = yi + m.

The standard diagrams show the line rising by m between adjacent columns. The real-valued heights yi and yi' = yi + m may differ while their rounded pixel rows y and y' remain equal when the step is too small to cross a rounding boundary.

Two adjacent columns show a line rising from y0 equals one to yi equals 1.4, with horizontal run one and vertical change m equals 0.4.
Advancing x by one column raises the ideal line height by the constant difference m.
Two adjacent columns have ideal heights 1.2 and 1.4 but both select row one, demonstrating that DDA state can change without changing the raster pixel row.
The ideal line advances from yi to yi+m even when both heights round to the same pixel row.

Builds on

Read

Playgrounds