DDA algorithm is an incremental scan conversion method. Here we perform calculations at each step using the results from the preceding step. The characteristic of the DDA algorithm is to take unit steps along one coordinate and compute the corresponding values along the other coordinate. The unit steps are always along the coordinate of greatest change, e.g. if dx = 10 and dy = 5, then we would take unit steps along x and compute the steps along y.
Suppose at step i we have calculated (xi, yi) to be a point on the line. Since the next point (x i+1,y i+1) should satisfy ?y/? x =m where ?y= y i+1–yi and ? x= x i+1–xi , we have y i+1= yi + m? x or x i+1=xi+ ? y/m
These formulas are used in DDA algorithm as follows. When |m| ? 1, we start with x = x1’? (assuming that x1’
When |m| >1, we start with x= x1’ and y= y1’ (assuming that y1’ < y2’), set ? y =1 ( i.e., unit increment in the y direction). The x coordinate of each successive point on the line is calculated using x i+1=xi+ 1/m. This process continues until x reaches x2’(for m| ? 1 case )or y reaches y2’ (for m| > 1 case ) and all points are scan converted to pixel points.
The explanation is as follows: In DDA algorithm we have to find the new point xi+1 and yi+1 from the existing points xi and yi. As a first step here we identify the major axis and the minor axis of the line to be drawn. Once the major axis is found we sample the major axis at unit intervals and find the value in the other axis by using the slope equation of the line.
For example if the end points of the line is given as (x1,y1)= (2,2) and (x2, y2)= (9,5). Here we will calculate y2-y1 and x2-x1 to find which one is greater. Here y2-y1 =3 and x2-x1 =7; therefore here the major axis is the x axis. So here we need to sample the x axis at unit intervals i.e.? x = 1 and we will find out the y values for each ? x in the x axis using the slope equation.
In DDA we need to consider two cases; one is slope of the line less than or equal to one (|m| ? 1)and slope of the line greater than one (m| > 1). When |m| ? 1 means y2-y1 = x2-x1 or y2-y1
We have the slope equation as
? y = m ? x
y2-y1 = m (x2-x1)
In general terms we can say that y i+1 - yi = m(x i+1 - xi ). But here ? x = 1; therefore the equation reduces to y i+1= yi + m = yi + dy/dx.
When m| > 1 means y2-y1> x2-x1 and therefore we assume y to be the major axis. Here
we sample y axis at unit intervals and find the x values corresponding to each y value. We have the slope equation as
? y = m ? x
y2-y1 = m (x2-x1)
In general terms we can say that y i+1 - yi = m(x i+1 - xi ). But here ? y = 1; therefore the equation reduces to 1 = m(x i+1 - xi). Therefore
x i+1=xi+ 1/m
x i+1=xi+ dx/dy
DDA Algorithm is given below:
procedure DDA( x1, y1, x2, y2: integer);
var
dx, dy, steps: integer;
x_inc, y_inc, x, y: real;
begin
dx := x2 - x1; dy := y2 - y1;
if abs(dx) > abs(dy) then
steps := abs(dx); {steps is larger of dx, dy}
else
steps := abs(dy);
x_inc := dx/steps; y_inc := dy/steps;
{either x_inc or y_inc = 1.0, the other is the slope}
x:=x1; y:=y1;
set_pixel(round(x), round(y));
for i := 1 to steps do
begin
x := x + x_inc;
y := y + y_inc;
set_pixel(round(x), round(y));
end;
end; {DDA}
The DDA algorithm is faster than the direct use of the line equation since it calculates points on the line without any floating point multiplication.
