1. DDA Line Algorithm
Line Equation
The Cartesian slop-intercept equation for a straight line is
y=mx+b ------ (1)
with
m->slope
b->y intercept
The 2 end points of a line segment are specified at a position(x1,y1)
Determine the values for the slope m and y intercept b with the following calculation.
here, slope m:
m = ( y2 - y1) / ( x2 - x1 )
m=Dy / Dx ------( 2 )
y intercept b
b=y1-mx1 ------( 3 )
Algorithms for displaying straight line based on this equation
y interval Dy from the equation
Similarly x interval Dx from the equation
m = Dy / Dx
Dx =Dy /m------- ( 5 )
Line DDA Algorithm:
The digital differential analyzer(DDA) is a scan conversion line algorithm based on calculation eitherDyor Dx.The line at unit intervals is one coordinate and determine corresponding integer values nearest line for the other coordinate.
Consider first a line with positive slope.
Step : 1
If the slope is less than or equal to 1 ,the unit x intervals Dx=1 and compute each successive y values.
Dx=1
m =Dy / Dx
m = ( y2-y1 ) / 1
m = ( yk+1 - yk ) /1
yk+1= yk + m -------- ( 6 )
- subscript k takes integer values starting from 1,for the first point and increment by 1 until the final end point is reached.
- m->any real numbers between 0 and 1
- Calculate y values must be rounded to the nearest integer
Step : 2
If the slope is greater than1 ,the roles of x any y at the unit y intervals Dy=1and compute each successive y values.
Dy=1
m= Dy / Dx
m= 1/ (x2-x1 )
m = 1 / ( xk+1 - xk)
xk+1 =xk +( 1 / m ) ------- ( 7 )
- Equation 6 and Equation 7 that the lines are to be processed from left end point to the right end point.
Step : 3
If the processing is reversed, the starting point at the right
Dx=-1
m= Dy / Dx
m = ( y2 - y1 ) / -1
yk+1= yk - m --------( 8 )
- Iintervals Dy=1and compute each successive y values.
Step : 4
Here,Dy=-1
m= Dy / Dx
m = -1 / ( x2 - x1 )
m = -1 / ( xk+1 - xk)
xk+1 =xk +( 1 / m )-------- ( 9 )
- Equation 6 andEquation9 used to calculate pixel position along a line with ???ve slope.
Advantage:
- faster method for calculating pixel position then the equation of apixel position.
- Y=mx+b
Disadvantage:
- The accumulation of round of error is the successive addition of the floating point increments is used to find the pixel position but it takes a lot of time to compute the pixel position.
Algorithm : A native line-drawing algorithm
dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
y = y1 + (dy) * (x - x1)/(dx)
pixel(x, y)
}
C Programming
void linedda(int xa,int ya,int xb,int yb){
int dx=xb-xa,dy=yb-ya,steps,k;
float xincrement,yincrement,x=xa,y=ya;
if(abs(dx)>abs(dy)) steps=abs(dx);
else steps=abs(dy);
xincrement=dx/(float)steps;
yincrement=dy/(float)steps;
putpixel(round(x),round(y),2)
for(k=0;k<steps;k++) {
x+=xincrement;
y+=yincrement;
putpixel(round(x),round(y),2);
}
}
DDA Line Drawing Algorithm Using C Programming
Example:
xa,ya=>(2,2)
xb,yb=>(8,10)
dx=6
dy=8
xincrement=6/8=0.75
yincrement=8/8=1
1) for(k=0;k<8;k++)
xincrement=0.75+0.75=1.50
yincrement=1+1=2
1=>(2,2)
2) for(k=1;k<8;k++)
xincrement=1.50+0.75=2.25
yincrement=2+1=3
2=>(3,3)
it will be incremented upto the final end point is reached.
Download DDA Line PDF Document
DDA Line Algorithm Tutorial Download