The Bresenham algorithm is another incremental scan
conversion algorithm
The big advantage of this algorithm is that it uses only
integer calculations.
The Bresenham algorithm is another incremental scan
conversion algorithm. The big advantage of this algorithm is that, it uses only
integer calculations. Moving across the x axis in unit intervals and at each
step choose between two different y coordinates.
Bresenham Example:
Plot the line from (20,10) to (30,18) using
Bresenham/Midpoint line drawing
algorithm.
First, Calculate all of the constants:-
Δx: 10
Δy: 8
2Δy: 16
2Δy - 2Δx: -4
Calculate the initial decision parameter p0:-
p0 = 2Δy – Δx = 6
|
k
|
pk
|
(xk+1,yk+1)
|
|
0
1
2
3
4
5
6
7
8
9
|
6
2
-2
14
10
6
2
-2
14
10
|
(21,11)
(22,12)
(23,12)
(24,13)
(25,14)
(26,15)
(27,16)
(28,16)
(29,17)
(30,18)
|
Advantages of Bresenham Line Algorithm:
–
An fast incremental algorithm
–
Uses only integer calculations
Comparing this to the DDA Algorithm, DDA has the
following problems:
–
Accumulation of round-off errors can make the pixelated
line
drift
away from what was intended
–
The rounding operations and floating point
arithmetic
involved are time consuming
Difference Between
DDA & Bresenham’s Line Drawing Algorithms
DDA & Bresenham’s Line Drawing Algorithms
• DDA uses floating points where as Bresenham’s algorithm
use fixed points.
• DDA round
off the coordinates to nearest integer but Bresenham’s algorithm does not.
• Bresenham’s
algorithm is much accurate and efficient than DDA.
• Bresenham’s
algorithm can draw circles and curves with much more accuracy than DDA
The Bresenham’s Line drawing Algorithm
For |m| < 1.0
Now, keeping in mind all the
above points and calculations, here is the Bresenham algorithm for slope m <
1
Step 1 − Input the two end-points of line, storing the
left end-point in (x0,y0)
Step 2 − Plot the point (x0,y0)
Step 3 − Calculate the constants dx, dy, 2dy, and (2dy –
2dx) and get the first value for the decision parameter as −
p0=2dy−dx
Step 4 − At each Xk
along the line, starting at k
= 0, perform the following test −
If pk
< 0, the next point to plot
is (xk+1,yk)
and
pk+1=pk+2dy
Otherwise,
(xk,yk+1)
pk+1=pk+2dy−2dx
Step 5 − Repeat step 4 (dx – 1) times.
For m > 1, find out whether
you need to increment x while incrementing y each time.
After solving, the equation
for decision parameter Pk
will be very similar, just the
x and y in the equation gets interchanged.
Below is a C program of Bresenham’s line drawing
algorithm with output:-
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<math.h>
void main()
{
int x1,x2,y1,y2,x,y,xend;
int dx,dy,twody,twodydx,p;
int gd=DETECT,gm;
clrscr();
initgraph(&gd,&gm,"");
printf("\n Enter the value of x1 and y1:");
scanf("%d %d",&x1,&y1);
outtextxy(x1,y1,"(x1,y1)");
printf("\n Enter the value of x2 and y2:");
scanf("%d %d",&x2,&y2);
outtextxy(x2,y2,"(x2,y2)");
setbkcolor(0);
dx=(x2-x1);
dy=(y2-y1);
twody=2*dy;
twodydx=2*(dy-dx);
p=2*dy-dx;
if(x1>x2)
{
x=x2;
y=y2;
xend=x1;
}
else
{
x=x1;
y=y1;
xend=x2;
}
printf("\np=%d,\t x=%d,\t y=%d",p,x,y);
putpixel(x,y,5);
while(x < xend)
{
x++;
if(p<0)
p+=twody;
else
{
y++;
p+=twodydx;
}
printf("\np=%d,\t x=%d,\t y=%d",p,x,y);
putpixel(x,y,5);
}
getch();
closegraph();
}
output:
THANK YOU!!!!
No comments:
Post a Comment