Subject: Computer Graphics

Topic: Output Primitives

Difficulty: Medium

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

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.

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.