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
Y_{k + 1 }= Y_{k }+
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 y_{k+1} = y_{k}
m.
If the slope is less than 1, we have ∆y = 1
and x_{k+}i = x_{k} 1/m
DDA LINE ALGORITHM
1. Read the line end points (x_{1}, y_{1})
and (x_{2}, y_{2}) such that they are not equal. If they equal
then plot that point and exit.
2. ∆x = I x_{2} – x_{1
}1 and ∆y = 1 y_{2} – y_{1} 1
3. If (∆x ≥ ∆y) then length = ∆x
else length = ∆y endif
4. ∆x= (x_{2} x_{1})
/length
∆y= (y_{2} y_{1}) /length
5. x = x_{1} + 0.5 x
sign (∆x)
y = y_{1}
+ 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.
X_{1 }= 0, y_{1} = 0, x_{2} = 4, y_{2} =
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.
x_{1} = 0, y_{1} = 0, x_{2} = 6, y_{2}
= 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 timeconsuming.
2. The algorithm is orientation
dependent. Hence end point accuracy is poor.
No comments:
Post a Comment