While drawing a line on computers they need to perform a set of computation, and it is not that simple as humans can do it in a simple way. So, in computer graphics, there are two algorithms used for drawing a line over the screen that is DDA (Digital Differential Analyser) algorithm and Bresenham algorithm. The chief difference between them is that the DDA algorithm uses floating point values while Bresenham employs integer with round off functions.
Furthermore, the implementation of the DDA algorithm involves multiplication and division while in bresenham algorithm, addition and subtraction are the main operations performed over the integers.
Content: DDA Algorithm Vs Bresenham Algorithm
|Basis for comparison||DDA Algorithm||Bresenham Algorithm|
|Operations used||Multiplication and division||Additions and subtraction|
|Arithmetic computation values||Floating point||Integer type|
|Cost||Expensive||Moderate or cheaper relatively.|
Definition of DDA Algorithm
A DDA (Digital Differential Analyzer) algorithms is a scan-conversion method for drawing a line which follows an incremental approach. In this algorithm to draw a line the difference in the pixel points is analysed then according to that the line is drawn. The method is said to be incremental because it performs computations at each step and uses the outcome of the previous step.
Before understanding DDA algorithm, we must understand what is a line and how it is defined? When two points in a plane connected by a line segment and falls under the line equation is known as a line. The line equation mentioned above is y=mx+b where m is the slope (i.e., m = Δy/Δx) and y is the intercept of the line (the value of y at the points of the line).
Now for DDA, let us assume at i we have computed (xi, yi) to be a point on the line as the next point (xi+1, yi+1) should Δy/Δx = m where Δy = (yi+1) – yi and Δx = (xi+1) – xi, which gives,
yi+1 = yi + mΔx or xi+1 = xi + Δy/m
Depending on the slope three types of situations can arise shown in the below-given diagram:It does not use the floating point multiplication. However, it uses the floating point addition which makes it faster than the straight implementation of the line equation. The algorithm is not precise because of the usage of floating point representation could cause computed points to drift away from their actual position when the line is relatively long.
Definition of Bresenham Algorithm
Bresenham algorithm also provides an efficient raster scan method for generating lines where incremental integer calculations are used. The developer of the algorithm was Jack Elton Bresenham, and the algorithm was named after him. It generates mathematically precise results with the help of addition, subtraction and multiplication by 2, which can be achieved by a simple arithmetic shift operation.
The above-given diagram explains the illustration of the straight line drawn over a display screen. Here the vertical axes indicate scan line positions, and the horizontal axes signify pixel columns. In the sampling at unit x intervals (as shown in example), we need to figure out which possible pixel positions lie nearer to the line path at each consequent step. So, this algorithm does it by examining the sign of an integer parameter, where its value is equal to the difference between the separation of the two pixel position from the true line path.
Now let’s understand Bresenham’s approach, considering a scan-conversion technique for lines having a positive slope of less than 1. Then the pixel location over the line path are then calculated by sampling at unit x intervals. It begins from the left endpoint (x0, y0) of a provided line, then each consecutive column (x position) is considered, and pixels are plotted where the scan-line y value is nearest to the line path. Suppose we have deduced that the pixel to be displayed at (xk, yk), then the next decision to ponder about is which pixel to plot in column xk+1. We can select for the pixels at the given positions (xk+1, yk) and (xk+1, yk+1).
For the position xk+1, the vertical line path labelled as d1 and d2 from the mathematical line path. The y coordinate for pixel column position xk+1 is deduced as
y = m (xk+1) + b –Eq 1
d1 = y-yk = m (xk+1) + b – yk
d2 = (yk+1) – y = yk+1 + m(xk+1) – b
The difference between these two separations is
d1-d2 = 2m (xk+1) – 2yk +2b -1 –Eq 2
The decision parameter Pk for the kth iteration in the line algorithm is obtained by reordering 2nd equation and substituting Δy/Δx in place of m. Δy and Δx are the vertical and horizontal separation of the endpoints position.
Pk = Δ x (d1 – d2) = 2 Δy . xk – 2 Δx . yk + c –Eq 3
Here the sign of Pk is equal to the d1-d2 as Δx is greater than 0. The value of the parameter c (constant) is 2Δy + Δx(2b-1) which does not affect the pixel position and can be removed in the recursive calculation of Pk. In some other cases, the pixel at yk position could present near to the line path than a pixel at yk+1 (i.e., d1>d2) and the parameter Pk is negative. In that condition, we plot the lower pixel. Otherwise, the upper pixel is plotted.
Integrated changes along the line occur in unit steps in any of the direction x or y. Therefore, the consequent decision parameters are calculated using an incremental approach. At k+1 iteration, the decision parameter is calculated from equation 3.
Pk+1 = 2Δy . xk+1 – 2 Δx.yk+1 + c
Subtracting equation 3 from the above equation, we get
Pk+1 – Pk = 2 Δy (xk+1-xk) – 2Δx(yk+1 – y)
but xk+1 = xk+1, so that
Pk+1 = Pk + 2 Δy – 2 Δx (yk+1 – yk)
The term yk+1 – yk is either 0 or 1, according to the sign of parameter Pk. This iterative calculation of decision parameters is carried out at every integer x position, beginning from the left coordinate endpoint of the line. The first parameter P0 is calculated from equation 3 at the pixel position (x0,y0) and m substituted as Δy/Δx.
P0 = 2 Δy – Δx
Key Differences Between DDA and Bresenham line drawing algorithm
- Bresenham’s algorithm is more efficient and accurate than DDA algorithm.
- The DDA algorithm involves floating point values while in bresenham algorithm only integer values is included. This is the major reason that made the computations in DDA difficult than the bresenham algorithm.
- DDA uses multiplication and division operations. As against, bresenham involves addition and subtraction causing less consumption of time. Therefore, DDA is slower than bresenham.
- The values in DDA never rounded off. In contrast, bresenham rounds off the value to the closest integer value.
- Bresenham algorithm is optimized. Conversely, DDA is not and less expensive.
The Bresenhem line drawing algorithm is more efficient and better in all aspects than the DDA algorithm which is not that efficient.