0
50kviews
Explain DDA line drawing algorithm. What are the disadvantages of DDA algorithm?

Subject: Computer Graphics

Topic: Output Primitives

Difficulty: Medium

2
920views
• Floating point arithmetic in DDA algorithm is still time consuming.

• The algorithm is orientation dependent. Hence end point accuracy is poor.

• Although DDA is fast, the accumulation of round-off error in successive additions of floating point increment, however can cause the calculation pixel position to drift away from the true line path for long line segment.

• Rounding-off in DDA is time consuming.

2
419views

Before discussing specific line drawing algorithms it is useful to note the general requirements for such algorithms. These requirements specify the desired characteristics of line.

• The line should appear as a straight line and it should start and end accurately.

• The line should be displayed with constant brightness along its length independent of its length and orientation.

• The line should be drawn rapidly.

Let us see the different lines drawn in Fig.

The process of ‘turning on’ the pixels for a line segment is called line generation, and the algorithm for them are known as line generation algorithms or vector generation algorithms.

# Digital Differential Analyzer (DDA) / Vector Generation Algorithm :

Vector Generation / DDA Line Algorithm:-

1. Read the line end points (x1, y1) and (x2, y2) such that they are not equal.
[if equal then plot that point and exit]

2. Δx  = |x2 - x1|    and  Δy  = |y2 - y1|

3. if(Δx ≥ Δy) then
length = Δx
else
length = Δy
end if

4. Δx = (x2 - x1) / length
Δy = (y2 - y1) / length


[This makes either Δx or Δy equal to 1 because length is either |x2 - x1| or |y2 - y1|.Therefore,the incremental Value for either x or y is one.]

5.  x = x1 + 0.5 * Sign(Δx)
y = y1 + 0.5 * Sign(Δy)


[Here, sign function makes the algorithm work in all quadrant. It returns -1, 0, 1 depending on whether its Argument is < 0, = 0, > 0 respectively. The factor 0.5 makes it possible to round the values in the integer Function rather than truncating them.]

     Plot (Integer (x), Integer (y))

6. i.= 1
[Begins the loop, in this loop points are plotted]
while ( i ≤ length)
{
x = x + Δx
y = y + Δy
Plot (Integer (x), Integer (y))
i = i + 1
}

7. Stop


Problem : Consider the line from (0,0) to (4,6). use the simple DDA algorithm to rasterized the line

solution :-

Evaluating steps 1 to 5 in the DDA algorithm

we have,
Given :- x1=0 , y1=0 , x2=4 , y2=6

Length = |y2—y1| = |6 – 0| = 6

There for,

Δx = (x2 - x1) / length = (4-0) / 6 = 4 / 6.

Δy = (y2 - y1) / length = (6-0) / 6 = 1.

Initial value for

x = 0 + 0.5 * Sign(4/6) = 0.5

y = 0 + 0.5 * Sign(1) = 0.5

Tabulating the results of each iteration in the step 6 we get,

The results are plotted as shown in the Fig. above .It shows that the rasterized line lies to both sides of the actual line, i.e. the algorithm is orientation dependent.