Digital differential analyzer (graphics algorithm): Difference between revisions

Content deleted Content added
Markzou (talk | contribs)
No edit summary
Program: The DDA algorithm requires rounding the floating point x,y to the nearest integer. The sample code should not depend on the behavior of some specific graphics library's putpixel() (for example if it takes int parameters, float->int uses truncation and will produce the wrong answer)
 
(289 intermediate revisions by more than 100 users not shown)
Line 1:
{{short description|Hardware or software used for interpolation of variables over an interval}}
DDA (digital differential analyzer) is used for generating pixels using a line formed by two points. It employees 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.
{{About|a graphics algorithm|the digital implementation of a differential analyzer|Digital differential analyzer}}
Here is a sample C code of the DDA implementation:
 
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]].
void line DDA(int xa, int ya, int xb, int yb)
 
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<sub>i</sub> the equations x<sub>i</sub> = x<sub>i−1</sub> + 1, y<sub>i</sub> = y<sub>i−1</sub> + m, where m is the [[slope]] of the line. This slope can be expressed in DDA as follows:
 
:<math>m = \frac{y_{\rm end} -y_{\rm start}}{x_{\rm end}-x_{\rm start}}</math>
 
In fact any two consecutive points lying on this line segment should satisfy the equation.
 
== Performance ==
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.
 
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.
 
DDAs are well suited for hardware implementation and can be pipelined for maximized throughput.
 
== Algorithm ==
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.
 
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
: <math>y_{k+1} = y_k + m</math>
: <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.
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
: <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.
 
== Program ==
DDA algorithm program in [[C++]]:
 
<syntaxhighlight lang="cpp" line="1">
#include <graphics.h>
#include <iostream.h>
#include <math.h>
#include <dos.h>
#include <conio.h>
 
void main()
{
float x,
int dx=xb-xa, dy=yb-ya, steps, k;
float y,
float xIncrement, yIncrement, x=xa, y=ya;
float x1, y1,
if(abs(dx)>abs(dy)) steps=abs(dx);
float x2, y2, dx, dy, step;
else steps=abs(dy);
int i, gd = DETECT, gm;
initgraph(&gd, &gm, "C:\\TURBOC3\\BGI");
xIncrement=dx/(float)steps;
yIncrement=dy/(float)steps;
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);
 
setPixel if (ROUNDabs(xdx), ROUND>= abs(ydy));
step = abs(dx);
for(k=0; k<steps; k++)
else
{
step = abs(dy);
x += xIncrement;
 
y += yIncrement;
dx = dx / step;
setPixel(ROUND(x), ROUND(y));
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]]