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 [(xstart, ystart) ... (xend, yend)] by computing for each xi the equations xi = xi−1+1, yi = yi−1 + Δy/Δx, where Δx = xend − xstart and Δy = yend − ystart.

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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Digital differential analyzer (graphics algorithm) — This article is about a graphics algorithm. For the digital implementation of a Differential Analyzer, see Digital Differential Analyzer. In computer graphics, a hardware or software implementation of a digital differential analyzer (DDA) is used …   Wikipedia

  • Digital differential analyzer — This article is about the digital implementation of a Differential Analyzer. For other uses of DDA, see DDA. For the graphics algorithm, see Digital Differential Analyzer (graphics algorithm). A digital differential analyzer (DDA), also sometimes …   Wikipedia

  • Bresenham's line algorithm — The Bresenham line algorithm is an algorithm that determines which points in an n dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a… …   Wikipedia

  • List of acronyms and initialisms: D — This list contains acronyms, initialisms, and pseudo blends that begin with the letter D. For the purposes of this list: acronym = an abbreviation pronounced as a series of constituent letters, e.g., SARS = severe acute respiratory syndrome… …   Wikipedia

  • Rasterung von Linien — Die Rasterung von Linien ist eine elementare Aufgabe der Computergrafik, bei der eine Linie auf das Punktraster einer Rastergrafik oder eines Raster Grafikgeräts gezeichnet (gerastert) wird. Dazu werden diejenigen Punkte oder Pixel eingefärbt,… …   Deutsch Wikipedia

  • computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… …   Universalium

  • List of file formats — This is an incomplete list, which may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries. See also: List of file formats (alphabetical) This is a list of file formats… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.