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.
- DDA algorithm (Digital Differential Analyzer)
- Midpoint algorithm
- 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 x1,x2,y1,y2,d,i1,i2,dx,dy
Step3: Enter value of x1,y1,x2,y2
Where x1,y1are coordinates of starting point
And x2,y2 are coordinates of Ending point
Step4: Calculate dx = x2-x1
Calculate dy = y2-y1
Calculate i1=2*dy
Calculate i2=2*(dy-dx)
Calculate d=i1-dx
Step5: Consider (x, y) as starting point and xendas maximum possible value of x.
If dx < 0
Then x = x2
y = y2
xend=x1
If dx > 0
Then x = x1
y = y1
xend=x2
Step6: Generate point at (x,y)coordinates.
Step7: Check if whole line is generated.
If x > = xend
Stop.
Step8: Calculate co-ordinates of the next pixel
If d < 0
Then d = d + i1
If d ≥ 0
Then d = d + i2
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 x1,y1,x2,y2,dx,dy,x,y as integer variables.
Step3: Enter value of x1,y1,x2,y2.
Step4: Calculate dx = x2-x1
Step5: Calculate dy = y2-y1
Step6: If ABS (dx) > ABS (dy)
Then step = abs (dx)
Else
Step7: xinc=dx/step
yinc=dy/step
assign x = x1
assign y = y1
Step8: Set pixel (x, y)
Step9: x = x + xinc
y = y + yinc
Set pixels (Round (x), Round (y))
Step10: Repeat step 9 until x = x2
Step11: End Algorithm
Also Read: Difference Between Deterministic And Non-deterministic Algorithms
DDA vs Bresenham’s Algorithm
BASIS OF COMPARISON | DDA ALGORITHM | BRESENHAM’S ALGORITHM |
Description | DDA stands for Digital Differential Analyzer. | ——- |
Operations | DDA algorithms uses multiplication and division in its operations. | Bresenham’s algorithm uses only subtraction and addition in its operations. |
Functionality | DDA algorithm is not as accurate and efficient as Bresenham’s. | Bresenham’s algorithm is more accurate and efficient than DDA algorithm. |
Arithmetic | DDA algorithm uses floating points i.e Real Arithmetic. | Bresenham’s algorithm uses fixed points i.e integer arithmetic. |
Round-off | DDA algorithm round off the coordinates to integer that is nearest to the line. | Bresenham’s algorithm does not round off but takes the incremental value in its operation. |
Drawing | DDA algorithm can draw circles and curves with less accuracy. | Bresenham’s algorithm can draw circles and curves with much more accuracy. |
Speed | DDA algorithm is slower than Bresenham’s algorithm because it uses real arithmetic floating point operations. | Bresenham’s algorithm is faster than DDA algorithm because it uses integer arithmetic. |
Complexity | In DDA algorithm, the complexity of calculation is more complex. | In Bresenham’s algorithm, the complexity of calculation is simple. |
Cost | DDA algorithm is costlier than Bresenham’s algorithm. | Bresenham’s algorithm is cheaper than DDA 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