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

Integer Implementation with seperated Fractional Part

/* Draw a straight line between the points (xa, ya) and (xb, yb) */
void line DDA(int xa, int ya, int xb, int yb)
{
            int dx=xb-xa; // horizontal difference
            int dy=yb-ya; // vertical difference
            int steps, k;
            float xIncrement, yIncrement;
            float x=xa, y=ya; // the drawing points x and y are initiated to one endpoint of the line

            // calculate the number of steps used to draw the line (number of pixels)
            if(abs(dx)>abs(dy)) 
                steps=abs(dx);
            else 
                steps=abs(dy);        

            // calculate the increment for x and y in each step
            xIncrement=dx/(float)steps ;
            yIncrement=dy/(float)steps; 

            // point out the starting pixel
            setPixel(ROUND(x), ROUND(y));

            // loop through the line from one end to the other and point out the pixels
            for(k=0; k<steps; k++) {
                    
                    // the points are incremented an equal amount for every step
                    x += xIncrement;
                    y += yIncrement;
                        
                    // since the values for x and y are float they are rounded before they are plotted
                    setPixel(ROUND(x), ROUND(y));
            }
}

Performance

The DDA method can be implemented using floating-point or integer arithmetic. The naïve floating-point implementation requires one addition and one round 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 round 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.

Literature

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

External links

Basic Computer Graphics Programs

^ inspired by Watt 2000, p. 184.

[1] spired by Watt 2000, p. 184.

[1]