Digital differential analyzer (graphics algorithm)
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
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 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 of the line and c is the y intercept . this slope can be expressed in DDA as
in fact any two consecutive point(x,y) laying on this line segment should satisfy the equation.
The 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.
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
Subscript k takes integer values starting from 0, for the 1st point and increases by 1 until endpoint is reached. 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
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 i.e. the starting extreme point is at the left.
- Bresenham's line algorithm is an algorithm for line rendering.
- Xiaolin Wu's line algorithm is an algorithm for line anti-aliasing
||This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (June 2011)|
- Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9