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.
Builds on
Read
- Read the chapter: DDA line rasterisation