Digital Differential Analyzer (graphics algorithm)
Encyclopedia
In computer graphics
, a hardware 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/m, yi = yi−1 + m, where Δx = xend − xstart and Δy = yend − ystart and m = Δy/Δx
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 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 be pipelined for maximized throughput.
where m represents the slope the line and c is the y intercept . this slope can be expressed in DDA
as
yend-ystart
m= -----------
xend-xstart
in fact any two consecutive point(x,y) laying on this line segment should satisfy the equation.
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, a hardware or software implementation of a digital differential analyzer
Digital differential analyzer
A digital differential analyzer , also sometimes called a digital integrating computer, is a digital implementation of a 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/m, yi = yi−1 + m, where Δx = xend − xstart and Δy = yend − ystart and m = Δy/Δx
Performance
The DDA method can be implemented using floating-point or integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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 FPU with fast add and rounding operation is available.
The fixed-point
Fixed-point arithmetic
In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after the radix 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 be pipelined for maximized throughput.
where m represents the slope the line and c is the y intercept . this slope can be expressed in DDA
as
yend-ystart
m= -----------
xend-xstart
in fact any two consecutive point(x,y) laying on this line segment should satisfy the equation.
See also
- Bresenham's line algorithmBresenham's line algorithmThe Bresenham line algorithm is an algorithm which 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...
is an algorithm for line rendering. - Xiaolin Wu's line algorithmXiaolin Wu's line algorithmXiaolin Wu's line algorithm is an algorithm for line antialiasing, which was presented in the article An Efficient Antialiasing Technique in the July 1991 issue of Computer Graphics, as well as in the article Fast Antialiasing in the June 1992 issue of Dr. Dobb's Journal.Bresenham's algorithm draws...
is an algorithm for line anti-aliasing
Literature
- Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9