Digital Differential Analyzer (graphics algorithm)

In Computer graphics, an hard- or software implementation of a Digital Differential Analyzer (DDA) is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. In its simplest implementation the DDA algorithm interpolates values in interval [(x_start, y_start) ... (x_end, y_end)] by computing for each x_i the equations x_i = x_i−1+1, y_i = y_i−1 + Δy/Δx, where Δx = x_end − x_start and Δy = y_end − y_start.

Basic algorithm (naïve floating-point implementation)

The straightforward DDA algorithm requires a fast floating-point add and round() operation for good performance. Here an example in the C programming language interpolating a single value y between start point (xa, ya) and end point (xb, yb): [Code is inspired by Watt 2000, p. 184.]

#include /* for round() */ extern void output (int x, int y); /* forward declaration for user-defined output */ /* Interpolate values between start (xa, ya) and end (xb, yb) */ void DDA (int xa, int ya, int xb, int yb) { int x; float dydx = (float) (yb - ya) / (float) (xb - xa); float y = ya; for (x=xa; x<=xb; x++) { output(x, round(y)); y = y + dydx; } }

Interpolating multiple values

Usually not only the coordinate component, but also additional values like depth, color, alpha, texture coordinates etc. are required for every point. For good performance on common architectures all values should get interpolated in the same inner loop:

#include extern void output (int x, int y, int color [3] ); /* Interpolate y-coord and RGB color values between start (xa, ya, colora) and end (xb, yb, colorb) */ void DDA (int xa, int ya, int colora [3] , int xb, int yb, int colorb [3] ) { int x; float dx = xb - xa; float dydx = (yb - ya) / dx; float dc0dx = (colorb [0] - colora [0] ) / dx; float dc1dx = (colorb [1] - colora [1] ) / dx; float dc2dx = (colorb [2] - colora [2] ) / dx; float y = ya, color [3] = { colora [0] , colora [1] , colora [2] }; for (x=xa; x<=xb; x++) { output(x, round(y), round(color [0] ), round(color [1] ), round(color [2] )); y = y + dydx; color [0] += dc0dx; /* Red component */ color [1] += dc1dx; /* Green component */ color [2] += dc2dx; /* Blue component */ } }

Integer implementation with separated fractional part

By splitting the integer and fractional part of all floating-point numbers, the algorithm can get converted to fixed-point arithmetics, so that it achieves good performance on architectures without floating-point support. Now the inner-loop rounding is replaced by a fractional-part overflow handler:

/* Interpolate values between start (xa, ya) and end (xb, yb) */ void DDA (int xa, int ya, int xb, int yb) { int x; int yi = ya; int yf = -(xb - xa); int mi = (yb - ya) / (xb - xa); int mf = 2 * ((yb - ya) % (xb - xa)); int mtwo_xb_minus_xa = -2 * (xb - xa); for (x=xa; x<=xb; x++) { output(x, yi); yi = yi + mi; yf = yf + mf; if (yf > 0) { yf += mtwo_xb_minus_xa; yi++; } } }

DDAs for triangle and line drawing

The above implementations interpolate only y values and iterate x values.

In order to rasterizlng triangles with horizontal spanlines one uses 3 independent DDAs: two DDAs interpolate x coordinate for incremental y, colors etc. for the left and right edge, a third DDA interpolates colors etc. on the span inbetween while iterating over x.

When rasterizing lines, then gaps would occur when abs(dydx) > 1 (thus, when |Δy| > |Δx|). So a line drawing algorithm using DDAs has to check whether abs(dydx) > 1, and interpolate x over y instead of y over x if so.

Performance

The DDA method can be implemented using floating-point or integer arithmetic. The naïve floating-point implementation requires one addition and one rounding operation per interpolated value (e.g. coordinate x, y, depth, color component etc.) and output result. This process is only efficient when a FPU with fast add and rounding operation is available.

The fixed-point integer operation requires two additions per output cycle, and in case of fractional part overflow one additional increment and subtraction. The probability of fractional part overflows is proportional to the ratio m of the interpolated start/end values.

DDAs are well-suited for hardware implementation and can get pipelined for maximized throughput.

See also

* Bresenham's line algorithm is an algorithm for line rendering.
* Xiaolin Wu's line algorithm is an algorithm for line antialiasing

References

Literature

*Alan Watt: "3D Computer Graphics", 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9

External links

* [http://programmers-lounge-basicgraphics.blogspot.com/ Basic Computer Graphics Programs]