Digital differential analyzer (graphics algorithm)

In Computer graphics, Digital Differential Analyzer (DDA) is an algorithm used to determine which points need to be plotted in order to draw a straight line between two given points. It employs the equation for line representation (example: y=mx+c), then scan through an axis. Each scan it would determine the value on the other axis using the equation, this way the proper pixel can be located.

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 x between start and end point:^[1]

#include <math.h>            /* for round() */

/* Interpolate values between start (xa, ya) and end (xb, yb) */
void DDA (int xa, int ya, int xb, int yb)
{
        float x = xa;
        float m = (xb - xa) / (yb - ya);
        int y; 
        for (y=ya; y<=ys; y++) {
                output(round(x), y);
                x = x + m;
        }
}

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 <math.h>            /* for round() */

/* 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])
{
        float x = xa;
        float mx = (xb - xa) / (yb - ya);
        float mc [3];
        int y, color [3];
        mc[0] = (colorb[0] - colora[0]) / (colorb[0] - colora[0]);
        mc[1] = (colorb[1] - colora[1]) / (colorb[1] - colora[1]);
        mc[2] = (colorb[2] - colora[2]) / (colorb[2] - colora[2]);
        for (y=ya; y<=ys; y++) {
                output(round(x), y, color);
                x = x + mx;
                color[0] += mc[0];    /* Red component */
                color[1] += mc[2];    /* Green component */
                color[2] += mc[1];    /* Blue component */
        }
}

Integer Implementation with seperated 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 xi = xa;
        int xf = -(yb - ya);
        int mi = (xb - xa) / (yb - ya);
        int mi = 2 * ((xb - xa) % (yb - ya));
        int y;
        for (y=ya; y<=ys; y++) {
                output(x, y);
                xi = xi + mi;
                xf = xf + mf;
                if (xf > 0) {
                        xf -= 2 * (yb - ya);
                        xi++;
                }
        }
}

DDAs for line drawing

The above implementations interpolate only x values and iterate y values. This is a perfect approach when rasterizlng triangles with horizontal lines (two DDAs interpolate x coordinate, colors etc. for the left and right edge, a third DDA interpolates colors etc on the horizontal line inbetween). But when rasterizing lines, then gaps will occur, when abs(mx) < 1. So a line drawing algorithm using DDAs has to check whether abs(mx) < 1, and interpolate y instead of x if required (since my < 1 if mx > 1).

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.

Literature

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

External links

Basic Computer Graphics Programs

^ Code is inspired by Watt 2000, p. 184.

[1] Code is inspired by Watt 2000, p. 184.

[1]