Bresenham Line Drawing Algorithm
By BYJU'S Exam Prep
Updated on: September 25th, 2023
Bresenham Line Drawing Algorithm is one of the popular computer graphics algorithms used to overcome the drawback of the DDA(Digital Differential Analyzer) algorithm. The Bresenham line drawing algorithm is less fast than the DDA algorithm.
The Bresenham implements the Bresenham line drawing algorithm. This algorithm is efficient because it involves three integer operations: addition, subtraction, and multiplication. These three operations will be performed rapidly, so lines should be formed quickly. Let us discuss the need, advantages and algorithm of the Bresenham line drawing algorithm in this article.
Download Formulas for GATE Computer Science Engineering – Programming & Data Structures
Table of content
What is Bresenham Line Drawing Algorithm?
The Bresenham line drawing algorithm determines the points of the N-dimensional raster selected to generate the close approximation to the straight line between the two coordinates or points. In the Bresenham line drawing algorithm, the integer is only for addition, subtraction, and multiplication.
The operation in the Bresenham line drawing algorithm is performed quickly so the line can be generated quickly. Suppose the line equation is y = mx + c. If the slope(m) value is 1, both the coordinate incremented, but if the slope value is less than 1, then the y coordinate may or may not be incremented. The Bresenham line drawing algorithm is used where the slope value is not equal to one.
Download Formulas for GATE Computer Science Engineering – Discrete Mathematics
Bresenham Line Drawing Algorithm Derivation
The Bresenham line drawing algorithm takes four integer values that are x1, y1, x2, and y2. The Bresenham line drawing algorithm given below is for the slope value less than one that is as follows:
Algorithm_bresenham(x1, y1, x2, y2)
{
x= x1;
y=y1;
dx = x2 – x2;
dy = y2 – y1;
p = 2dx = dy;
while(x <= x2)
{
putpixel(x,y);
x++;
if(p<0)
p=p+2dx;
else
p=p + 2dy – 2dx;
y++;
}
}
Need of Bresenham Line Drawing Algorithm
The Bresenham line drawing algorithm is needed to overcome the problem of floating points in the DDA (Digital Differential Analyzer) that is for the DDA algorithms, the equations are:
- For X-axis Δx = x2 – x1
- For Y-axis Δy = y2 – y1
Step = max(Δx, Δy)
Xinc = Δx/step
Yinc = Δy/step
As in the above equation, the division operation is used, which returns the float value. The float takes more time for addition, subtraction, and multiplication than an integer. Therefore, the Bresenham line drawing algorithm is used to overcome the floating-point problem.
Advantages of the Bresenham Line Drawing Algorithm
The advantage of the Bresenham line drawing Algorithm is that the Bresenham line drawing algorithm is easy to implement. It is very fast to execute but less than the DDA(Digital Differential Analyzer) algorithm and incremental.
The points generated by the Bresenham line drawing algorithm are more correct or accurate than DDA(Digital Differential Analyzer) Algorithm. The Bresenham line drawing algorithm uses fixed points or coordinates only.
Download Formulas for GATE Computer Science Engineering – Algorithms
How is the Decision Parameter Calculated in the Bresenham Line Drawing Algorithm?
The decision parameter calculated in the Bresenham line drawing algorithm for slope |m|>1 is as follows:
1. Input two endpoints or coordinates of the line (x1,y1) and (x2,y2).
2. The first point (x1,y1) is plotted on the graph or screen.
3. Now calculate the difference in X and Y coordinates, that is: dx =|x2 – x1| dy = |y2 – y1 |
4. The initial decision parameter will be calculated as aa: p = 2*dx – dy.
5. For I = 0 to dy in step 1.
If p < 0 then
the Y coordinate incremented as y1 = y1 + 1 and then plot(x1,y1).
Calculate new decision parameter as p = p + 2dx.
Else
the X coordinate incremented as x1 = x1 + 1
the Y coordinate incremented as y1 = y1 + 1
and then plot(x1, y1)
Calculate new decision parameter as p = p + 2dx – 2*dy
6. END
| Important Topics for Gate Exam | |
| Brittle Material | Capacitors in Parallel |
| Capacitors in Series | Carnot Cycle |
| Cement Test | Clamping Circuit |
| Clipping Circuit | CMOS Fabrication |
| CMOS Converter | Column Base |
