Difference Between Bresenham’s And DDA Line Drawing Algorithm

In computer graphics, we need to represent continuous graphics objects using discrete pixels. This process is known as scan conversion. Every graphics system must transform the primitives like lines, circles, and ellipses into a collection of pixels.

Line drawing algorithms are used to draw a line in discrete graphical media. There are three line drawing algorithms in computer graphics.

1. DDA algorithm (Digital Differential Analyzer)
2. Midpoint algorithm
3. Bresenham’s line algorithm

Bresenham’s Line Drawing Algorithm

Bresenham’s Line Algorithm is a optimistic & incremental scan conversion Line Drawing Algorithm which calculates all intermediate points over the interval between start and end points, implemented entirely with integer numbers and the integer arithmetic. It only uses addition and subtraction and avoids heavy operations like multiplication and division.

Bresenham Line Drawing Algorithm determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. 

It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in commonly used computer instruction sets such as x86_64. It is an incremental error algorithm. It is one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm may be used for drawing circles.

Bresenham’s Algorithm

Step1: Start Algorithm

Step2: Declare variable x₁,x₂,y₁,y₂,d,i₁,i₂,dx,dy

Step3: Enter value of x₁,y₁,x₂,y₂
                Where x₁,y₁are coordinates of starting point
                And x₂,y₂ are coordinates of Ending point

Step4: Calculate dx = x₂-x₁
                Calculate dy = y₂-y₁
                Calculate i₁=2*dy
                Calculate i₂=2*(dy-dx)
                Calculate d=i₁-dx

Step5: Consider (x, y) as starting point and x_endas maximum possible value of x.
                If dx < 0
                        Then x = x₂
                        y = y₂
                          x_end=x₁
                If dx > 0
                    Then x = x₁
                y = y₁
                        x_end=x₂

Step6: Generate point at (x,y)coordinates.

Step7: Check if whole line is generated.
                If x > = x_end
                Stop.

Step8: Calculate co-ordinates of the next pixel
                If d < 0
                    Then d = d + i₁
                If d ≥ 0
          Then d = d + i₂
                Increment y = y + 1

Step9: Increment x = x + 1

Step10: Draw a point of latest (x, y) coordinates

Step11: Go to step 7

Step12: End of Algorithm

DDA Line Drawing Algorithm

DDA stands for Digital Differential Analyzer. This is an incremental line algorithm, the calculation of each step is based on the results of the previous steps. DDA algorithm takes unit steps along one coordinate and compute the corresponding values along the other coordinate.

DDAs are used for rasterization of lines, triangles and polygons. They can be extended to non linear functions, such as perspective correct texture mapping, quadratic curves, and traversing voxels.

A linear DDA starts by calculating the smaller of dy or dx for a unit increment of the other. A line is then sampled at unit intervals in one coordinate and corresponding integer values nearest the line path are determined for the other coordinate.

DDA Algorithm

Step1: Start Algorithm

Step2: Declare x₁,y₁,x₂,y₂,dx,dy,x,y as integer variables.

Step3: Enter value of x₁,y₁,x₂,y₂.

Step4: Calculate dx = x₂-x₁

Step5: Calculate dy = y₂-y₁

Step6: If ABS (dx) > ABS (dy)
            Then step = abs (dx)
            Else

Step7: x_inc=dx/step
            y_inc=dy/step
            assign x = x₁
            assign y = y₁

Step8: Set pixel (x, y)

Step9: x = x + x_inc
            y = y + y_inc
            Set pixels (Round (x), Round (y))

Step10: Repeat step 9 until x = x₂

Step11: End Algorithm

Also Read: Difference Between Deterministic And Non-deterministic Algorithms

DDA vs Bresenham’s Algorithm

Also Read: Difference Between Prim’s And Kruskal’s Algorithm

What you need to know about DDA and Bresenhams

• 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.
• DDA algorithm is rather slowly than Bresenhams algorithm in line drawing because it uses real arithmetic (floating point operations).
• 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.
• 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.
• Bresenhm algorithm does not round off but takes the incremental value in its operation.

Also Read: Difference Between RSA And DSA Algorithm