More info

Saturday, 15 February 2014

Computer Graphics Notes- Lab 11 - Line Drawing Cont

DDA (Digital Differential Analyzer) Algorithm


The digital differential analyzer (DDA) is a scan - conversion line alogrithm based on calculating either ∆y or ∆x. We sample the line at unit intervals in one coordinate and determine corresponding integer values nearest the line path for the other coordinate.

If the slope is less than or equal to 1, we sample at unit x intervals (∆x =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 final end point is reached. Since m can take any real number between 0 tot , the calculated y values must be rounded to the nearest integer.





If the slope is greater than 1, we reverse the roles of x and y. that is, we sample at unit y intervals (∆y = 1) and calculate each succeeding x values as




If the slope is between -1 and 0, that is if the line is processed from the left endpoint to the right endpoint then this processing is reversed. Then we have ∆x = -1 and yk+1 = yk- m.
If the slope is less than -1, we have ∆y = -1 and xk+i = xk- 1/m

DDA LINE ALGORITHM

1.     Read the line end points (x1, y1) and (x2, y2) such that they are not equal. If they equal then plot that point and exit.
2.     ∆x = I x2 – x1 1 and ∆y = 1 y2 – y1 1
3.     If (∆x ≥ ∆y) then length = ∆x else length = ∆y endif
4.     ∆x= (x2- x1) /length
∆y= (y2- y1) /length
5.     x = x1 + 0.5 x sign (∆x)
y = y1 + 0.5 x sign (∆y)
6.     i = 0
while (i ≤ length)
{
plot (integer(x), integer(y))
x = x + ∆x
y = y + ∆y
I = i + 1
}
7.     Stop.

Example
Consider the line from (0, 0) to (4, 6). Use the DDA algorithm to rasterize this line.

X1 = 0, y1 = 0, x2 = 4, y2 = 6
∆x = 4, ∆y = 6
∆y ≥ ∆x
Therefore, length = 6
∆x = 4/6
∆y = 1
Initial value for x = 0 + 0.5 x 1 = 0.5
Initial value for y = 0 + 0.5 x 1 = 0.5

i
Plot
X
y


0.5
0.5
0
(0,0)




1.167
1.5
1
(1,1)




1.833
2.5
2
(1,2)




2.5
3.5
3
(2,3)




3.167
4.5
4
(3,4)




3.833
5.5
5
(3,5)




4.5
6.5
6
(4,6)



Example
Consider the line from (0, 0) to (-6, -6). Use the DDA algorithm to rasterize this line.
x1 = 0, y1 = 0, x2 = -6, y2 = -6
x = 6, y = 6
y = x
Therefore, length = -6
∆x = ∆y = -1
Initial value for x = 0 - 0.5 x 1 = -0.5
Initial value for y = 0 - 0.5 x 1 = -0.5

i
Plot
X
y


-0.5
-0.5
0
(0,0)




-1.5
-1.5
1
(-1,-1)




-2.5
-2.5
2
(-2,-2)




-3.5
-3.5
3
(-3,-3)




-4.5
-4.5
4
(-4,-4)




-5.5
-5.5
5
(-5,-5)




-6.5
-6.5
6
(-6,-6)




-7.5
-7.5


Advantages of DDA Algorithm

1.     It is the simplest algorithm and it does not require special skills for implementation.
2.     It is faster method for calculating pixel positions than the direct use of equation.

Disadvantages of DDA Algorithm

1.     Floating point arithmetic in DDA algorithm is still time-consuming.
2.     The algorithm is orientation dependent. Hence end point accuracy is poor.

No comments:

Post a Comment