written 7.8 years ago by | modified 2.3 years ago by |

**Subject:** Computer Graphics

**Topic:** Output Primitives

**Difficulty:** Medium

**2 Answers**

0

50kviews

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

written 7.8 years ago by | modified 2.3 years ago by |

**Subject:** Computer Graphics

**Topic:** Output Primitives

**Difficulty:** Medium

ADD COMMENT
EDIT

2

920views

written 7.8 years ago by |

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.

ADD COMMENT
EDIT

2

419views

written 6.3 years ago by | • modified 6.3 years ago |

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**.

**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**.

**Disadvantages of DDA algorithm :-**

**1. It uses floating point operation which is expensive: -** The co-ordinates are always integer values but by using this algorithm we get floating point values which the computer screen doesn’t allow.

**Plot (Integer (x), Integer (y)) used for floating point operation.**

**2. It produces Aliasing effect: -** The exact location / exact line is not found we get a **zig-zag** line.

ADD COMMENT
EDIT

Please log in to add an answer.