1
41kviews
Write DDA Line Algorithm. Compare DDA with Bresenham line drawing Algorithm.
1 Answer
0
1.2kviews

A line connects two points. It is a basic element in graphics. To draw a line, you need two points between which you can draw a line. In the following three algorithms, we refer the one point of line as X0,Y0X0,Y0 and the second point of line as X1,Y1X1,Y1

DDA Algorithm

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)(X0,Y0) and (X1,Y1)(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));
}

Bresenham Algorithm

  • Bresenham Algorithm was developed by J.E.Bresenham in 1962 and it is much accurate and much more efficient than DDA.
  • It scans the coordinates but instead of rounding them off it takes the incremental value in account by adding or subtracting and therefore can be used for drawing circle and curves.
  • Therefore if a line is to be drawn between two points x and y then next coordinates will be( xa+1, ya) and (xa+1, ya+1) where a is the incremental value of the next coordinates and difference between these two will be calculated by subtracting or adding the equations formed by them.

Comparision

  • DDA uses floating points where as Bresenham algorithm use fixed points.
  • DDA round off the coordinates to nearest integer but Bresenham algorithm does not.
  • Bresenham algorithm is much accurate and efficient than DDA.
  • Bresenham algorithm can draw circles and curves with much more accuracy than DDA.
  • DDA uses multiplication and division of equation but Bresenham algorithm uses subtraction and addition only
- Digital Differential Analyzer,Line Drawing Algorithm Bresenhams Line Drawing Algorithm
Arithmetic DDA algorithm uses floating points i.e. Real Arithmetic Bresenhams algorithm uses fixed points i.e. integer Arithmetic.
Operations DDA algorithms uses multiplication and division in its operations. Bresenhams algorithm uses only subtraction and addition in its
Speed DDA 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 calculations and uses only integer arithmetic so it runs significantly faster.
Accuracy & Efficiency DDA algorithm is not as accurate and efficient as Bresenhm algorithm. Bresenhm algorithm is more accurate and efficient as than DDA algorithm.
Drawing DDA algorithm can draw circles and curves but that are not as accurate as Bresenhm algorithm. Bresenhm algorithm can draw circles and curves with much more accuracy than DDA algorithm.
Round off DDA algorithm round off the coordinates to integer that is nearest to the line. Bresenhm algorithm does not round off but takes the incremental value in its operation.
- - Bresenhm algorithm is less expensive than DDA algorithm as it uses only addition and subtraction.
Please log in to add an answer.