World's most popular travel blog for travel bloggers.

What are the advantages and disadvantages of using DDA algorithm for line generation? List the steps of the algorithm. Use this algorithm to draw a line with endpoints (2, 3) and (9, 8). Compare DDA algorithm and Bresenham Line generation Algorithm? Show step by step execution of Bresenham Line Generation algorithm for drawing a line having endpoints (2, 3) and (9, 8).

, , 3 comments

Advantages of DDA Algorithm

  • It is the simplest algorithm and it does not require special skills for implementation.
  • It is a faster method for calculating pixel positions than the direct use of equation y=mx + b. It eliminates the multiplication in the equation by making use of raster characteristics, so that appropriate increments are applied in the x or y direction to find the pixel positions along the line path.

Disadvantages

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


DDA Algorithm Steps

Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm which is explained step by step here.
Step 1 − Get the input of two end points (X0,Y0) and (X1,Y1).
Step 2 − Calculate the difference between two end points.
dx = X1 - X0
dy = Y1 - Y0
Step 3 − Based on the calculated difference in step-2, you need to identify the number of steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate.
if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);
Step 4 − Calculate the increment in x coordinate and y coordinate.
Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;
Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and complete the drawing of the line.
for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Drawing (2,3), (9,8)


y=mx+c where m=(y1-y0)/(x1-x0)
Given (x0,y0)→(2,3); (x1,y1) →(9,8)
 m=(8-3)/(9-2) =5/7
c = y1-mx1 = 8-(5/7)*9=11/7
So by equation of line (y=mx=c) we have…
Y=(5/7)x+(11/7)

Given (x0,y0)=(2,3)
1) X1=x0+1 = 2+1 = 3
Y1=y0+m= 3+(5/7)=26/7
Put pixel (x0, round y, Color ) i.e.., put (3,5)
2) X2=x1+1 = 3+1 = 4
Y2=y1+m= 26/7+5/7=31/7
Put pixel (x0, round y, Color ) i.e.., put (4,5)
Similarly go on till (9,8) reached.

Difference Between DDA Line Drawing Algorithm and Bresenhams Line Drawing Algorithm.
Digital Differential Analyzer
Line Drawing Algorithm
Bresenhams Line Drawing Algorithm
ArithmeticDDA algorithm uses floating points i.e. Real Arithmetic.Bresenhams algorithm uses fixed points i.e. Integer Arithmetic.
OperationsDDA algorithm uses multiplication and division in its operations.Bresenhams algorithm uses only subtraction and addition in its operations.
SpeedDDA algorithm is rather slowly than Bresenhams algorithm in line drawing because it uses real arithmetic (floating-point operations).Bresenhams algorithm is faster than DDA algorithm in line drawing because it performs only addition and subtraction in its calculation and uses only integer arithmetic so it runs significantly faster.
Accuracy & EfficiencyDDA algorithm is not as accurate and efficient as Bresenham algorithm.Bresenhams algorithm is more efficient and much accurate than DDA algorithm.
DrawingDDA algorithm can draw circles and curves but that are not as accurate as Bresenhams algorithm.Bresenhams algorithm can draw circles and curves with much more accuracy than DDA algorithm.
Round OffDDA algorithm round off the coordinates to integer that is nearest to the line.Bresenhams algorithm does not round off but takes the incremental value in its operation.
ExpensiveDDA algorithm uses an enormous number of floating-point multiplications so it is expensive.Bresenhams algorithm is less expensive than DDA algorithm as it uses only addition and subtraction.
00:00:00

3 comments:

Let us know your responses and feedback