Sem 4‎ > ‎CG LAB‎ > ‎0 Algorithms‎ > ‎

1 DDA Line Algo

posted Jan 7, 2012, 9:48 PM by Neil Mathew   [ updated Jan 8, 2012, 3:01 AM ]




( DDA uses repeated addition )
( Use of floating point operations makes it slightly slower than Bresenham's Algo )


Explanation:

The program should make use of basic concept of DDA’s line generation algorithm.

The DDA is a scan conversion line algorithm based on calculating Dy and Dx. 

We sample the line at unit intervals in one co-ordinate and determine corresponding integer values nearest the line path for the other co-ordinate.1. 

We will consider a line with positive slope. 

>>If the slope is less than or equal to 1,we sample it at unit x intervals (Dx = 1) and compute each successive y value as 

yk+1 = yk + m

(Subscript k takes integer values starting from 1 for the first point and increases by 1 until the final end point is reached.
The value of m can be any real number between 0 and 1.2)

>>For lines with positive slope greater than 1, we reverse the roles of x and y. We sample at unit y intervals and calculate each succeeding x value as 

xk+1= xk + 1/m

>> For the above equation we are processing the line equation from the left end point to right end point.
 
If this processing is reversed , (negative Slope) so either we have

Dx = -1 and  yk+1 = yk - m  
Or
 Dy = -1 and xk+1= xk - 1/m



Program:

#define ROUND(a) ((int)(a+0.5))

Void lineDDA (int xa , int ya , int xb , int yb)
{

int dx = xb – xa;                       //Calculate Dy Dx (neg value possible)
int dy = yb – ya;

int steps , k ;
float xincr, yincr;


int x = xa, y = ya;                     //Print First pixel as initial pixel
Setpixel(ROUND(x),ROUND(y));


If(abs(dx) > abs(dy))                 //Steps = greater of Dx and Dy (abs values)
steps = abs(dx);

xincr = dx / (float) steps;           //Increment = (-)1 or [ (-) m (for y) or (-)1/m (for x) ]
yincr = dy / (float) steps;           // Implemented how: dx / dx = 1 or dy/dx = m


For(k=0; k<steps; k++)
{
x += xincrement;
y += yincrement;
Setpixel(ROUND(x),ROUND(y));
}

}


Comments