Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 08:46, 8 July 2008

Latest revision as of 00:30, 24 July 2024

(243 intermediate revisions by more than 100 users not shown)

Line 1:

{{short description|Hardware or software used for interpolation of variables over an interval}}

{{Refimprove|date=August 2007}}

{{otheruses4About|a graphics algorithm|other uses of DDA|DDA|the digital implementation of a Differentialdifferential Analyzeranalyzer|Digital Differentialdifferential Analyzeranalyzer}}

In [[computer graphics]], a '''digital differential analyzer''' ('''DDA''') is hardware or software used for [[interpolation]] of [[Variable (computer science)|variables]] over an [[Interval (mathematics)|interval]] between start and end point. DDAs are used for [[rasterization]] of lines, triangles and polygons. They can be extended to non linear functions, such as [[texture mapping#Perspective correctness|perspective correct texture mapping]], [[quadratic curves]], and traversing [[voxels]].

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.

In its simplest implementation for linear cases such as [[Line (geometry)|line]]s, the DDA algorithm interpolates values in interval by computing for each x_i the equations x_i = x_i−1 + 1, y_i = y_i−1 + m, where m is the [[slope]] of the line. This slope can be expressed in DDA as follows:

==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 <code>x</code> between start and end point:<ref>Code is inspired by Watt 2000, p. 184.</ref>

:<math>m = \frac{y_{\rm end} -y_{\rm start}}{x_{\rm end}-x_{\rm start}}</math>

<code>

#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;

}

}

</code>

In fact any two consecutive points lying on this line segment should satisfy the equation.

==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:

== Performance ==

<code>

The DDA method can be implemented using [[floating-point]] or [[integer]] arithmetic. The native 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 an [[Floating-point unit|FPU]] with fast add and rounding operation will be available.

#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 */

}

}

</code>

The [[Fixed-point arithmetic|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.

==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:

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

<code>

/* 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++;

}

}

}

</code>

== Algorithm ==

==DDAs for line drawing==

A linear DDA starts by calculating the smaller of dy or dx for a unit increment of the other. A line is then sampled at unit intervals in one coordinate and corresponding integer values nearest the line path are determined for the other coordinate.

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).

Considering a line with positive slope, if the slope is less than or equal to 1, we sample at unit x intervals (dx=1) and compute successive y values as

==Performance==

: <math>y_{k+1} = y_k + m</math>

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.

: <math>x_{k+1} = x_k + 1</math>

Subscript k takes integer values starting from 0, for the 1st point and increases by 1 until endpoint is reached.

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.

y value is rounded off to nearest integer to correspond to a screen pixel.

For lines with slope greater than 1, we reverse the role of x and y i.e. we sample at dy=1 and calculate consecutive x values as

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

: <math>x_{k+1} = x_k + \frac{1}{m}</math>

: <math>y_{k+1} = y_k + 1</math>

Similar calculations are carried out to determine pixel positions along a line with negative slope. Thus, if the absolute value of the slope is less than 1, we set dx=1 if <math> x_{\rm start}<x_{\rm end}</math> i.e. the starting extreme point is at the left.

==See also==

* [[Xiaolin Wu's line algorithm]] is an algorithm for line antialiasing

==Literature Program ==

DDA algorithm program in [[C++]]:

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

<syntaxhighlight lang="cpp" line="1">

==External links==

#include <graphics.h>

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

#include <iostream.h>

#include <math.h>

#include <dos.h>

#include <conio.h>

void main()

{

float x,

float y,

float x1, y1,

float x2, y2, dx, dy, step;

int i, gd = DETECT, gm;

initgraph(&gd, &gm, "C:\\TURBOC3\\BGI");

cout << "Enter the value of x1 and y1: ";

cin >> x1 >> y1;

cout << "Enter the value of x2 and y2: ";

cin >> x2 >> y2;

dx = (x2 - x1);

dy = (y2 - y1);

if (abs(dx) >= abs(dy))

step = abs(dx);

else

step = abs(dy);

dx = dx / step;

dy = dy / step;

x = x1;

y = y1;

i = 0;

while (i <= step) {

putpixel(round(x), round(y), 5);

x = x + dx;

y = y + dy;

i = i + 1;

delay(100);

}

getch();

closegraph();

}

</syntaxhighlight>

== See also ==

* [[Bresenham's line algorithm]] is an algorithm for line rendering.

* [[Incremental error algorithm]]

* [[Xiaolin Wu's line algorithm]] is an algorithm for line anti-aliasing

== References ==

http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf

{{no footnotes|date=June 2011}}

<references/>

* Alan Watt: ''3D Computer Graphics'', 3rd edition 2000, p.&nbsp;184 (Rasterizing edges). {{ISBN|0-201-39855-9}}

[[Category:Computer graphics algorithms]]

[[Category:Digital geometry]]

[[Category:Articles with example C++ code]]