COMPUTER GRAPHICS - Implement DDA and Bresenham Line Drawing algorithms
Experiment No.01
Aim: Implement DDA and Bresenham Line Drawing algorithms
Prerequisite: C Language
Outcome: After successful completion of this experiment students will be able to Implement various line, circle, ellipse drawing algorithms.
Theory
DDA algorithm:
Input to the function is two endpoints (x1,y1) and (x2,y2)
- length =abs(x2-x1);
- if (abs(y2-y1) > length) then length =abs(y2-y1);
- xincrement (x2-x1) / length;
- yincrement (y2-y1) / length;
- x =x + 0.5; y =Y + 0.5;
- for i 1 to length follow steps 7 to 9
- plot (trunc(x),trunc(y));
- x= x + xincrement ;
- y =y + yincrement ;
- stop.
Bresenham's Line Drawing Algorithm:
1. Input the two line endpoints and store the left endpoint in(x0,y0)
2. Load ( x0,y0 ) into the frame buffer; that is , plot the first point.
3. Calculate constants dx, dy,2 dy and 2 dy -2 dx , and obtain the starting value for the decision parameter as:
p0 = 2 dy - dx
4. At each xk, the next point 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 + 2 dy
Otherwise ,the next point to plot is (xk + 1, yk +1) and
pk+1 = pk + 2 dy - 2 dx
5.Repeat step 4 dx times.
DDA Algorithm:
Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm.
Step 1 − Get the input of two end points (X0,Y0) and (X1,Y1).
Step 2 − Calculate the difference between two end points.
dx = X1 - X0
dy = Y1 - Y0
Step 3 − Based on the calculated difference in step-2, you need to identify the number of steps to put pixel.
If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate.
if (dx > dy) Steps = absolute(dx);
else Steps = absolute(dy);
Step 4 − Calculate the increment in x coordinate and y coordinate.
X increment = dx / (float) steps;
Y increment = dy / (float) steps;
Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and complete the drawing of the line.
for(int v=0; v < Steps; v++)
{
x = x + Xincrement;
y = y + Yincrement;
putpixel(x,y);
}
BRESENHAM’S Line Drawing Algorithm.
Assumption : Y=mX+b
where b is the intercept cut by line at Y axis and m is the slope of line
(0 <= m < 1)
Derivation : Initially we have plotted a point (Xk , Yk) and increase X by 1 we come to Xk+1.
Decision Parameter(Pk) - (Xk+1 , Yk+1)
- (Xk+1 , Yk)
D1 = Y – Yk
D1 = m(Xk+1)+b – Yk
D2 = Yk+1 – Y
D2 = Yk+1 – [m(Xk+1)+b]
D1-D2 = m(Xk+1) – Yk - Yk+1 + m(Xk+1) + 2b
D1-D2 = 2m(Xk+1) + 2b – Yk – Yk+1
D1-D2 = 2mXk + 2m – 2Yk + (2b-1)
Put m = dY/dX
(D1-D2)dX = 2Xk dY – 2Yk dX + 2dY + (2b-1)dX
Pk = 2Xk dY – 2Yk dX + C
Where C = 2dY + (2b-1)dX
Pk+1 = 2Xk+1 dY – 2Yk+1 dX + C
Pk+1-Pk = 2(Xk+1 - Xk)dY – 2(Yk+1 - Yk)dX
Pk+1 = Pk + 2dY – 2(Yk+1 - Yk)dx -------------------------- (A)
If Pk is negative (Pk < 0)
(D1-D2)dX < 0
Xk+1 – Xk = 1
Yk+1 – Yk = 0
Put these value in A
Pk+1 = Pk +2dy
This is the decision parameter for less than zero.
If P is positive (P>=0)
(D1-D2)dx >= 0
Xk+1 – Xk = 1
Yk+1 – Yk = 1
put these value in A
Pk+1 = Pk + 2(dY - dY)
This is the decision parameter for greater than zero.
Initial value of decision parameter (Xo , Yo)
Po = 2Xo dY – 2Yo dX + 2dY + (2b-1)dX -------------------------- (B)
Yo = mXo +b
Yo – mXo = b
Yo – dY/dX Xo = b
2Yo – 2Xo dY/dX = 2b
2Yo dx – 2Xo dY - dX = (2b-1)dX
Put the value of (2b-1)dX in B
Po = 2Xo dY – 2Yo dX + 2dY + 2Yo dx – 2Xo dY – dX
Po = 2dY – dX
This is the initial decision parameter.
Codes :
Code for DDA line drawing algorithm:
#include<graphics.h>
#include<stdio.h>
#include<math.h>
#include<dos.h>
#include<conio.h>
void main( )
{
float x,y,x1,y1,x2,y2,dx,dy,step;
int i,gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\turboc3\\bgi");
printf("Enter the value of x1 and y1 : ");
scanf("%f%f",&x1,&y1);
printf("Enter the value of x2 and y2: ");
scanf("%f%f",&x2,&y2);
dx=abs(x2-x1);
dy=abs(y2-y1);
if(dx>=y2-y)
step=dx;
else
step=dy;
dx=dx/step;
dy=dy/step;
x=x1;
y=y1;
i=1;
while(i<=step)
{
putpixel(x,y,5);
x=x+dx;
y=y+dy;
i=i+1;
delay(100);
}
getch();
closegraph();
}
Code for Bresenham's line drawing algorithm:
#include<stdio.h>
#include<graphics.h>
void drawline(int x0, int y0, int x1, int y1)
{
int dx, dy, p, x, y;
dx=x1-x0;
dy=y1-y0;
x=x0;
y=y0;
p=2*dy-dx;
while(x<x1)
{
if(p>=0)
{
putpixel(x,y,7);
y=y+1;
p=p+2*dy-2*dx;
}
else
{
putpixel(x,y,7);
p=p+2*dy;
}
x=x+1;
}
}
int main()
{
int gdriver=DETECT, gmode, error, x0, y0, x1, y1;
initgraph(&gdriver, &gmode, "c:\\turboc3\\bgi");
printf("Enter the starting co-ordinates: ");
scanf("%d%d", &x0, &y0);
printf("Enter the ending co-ordinates: ");
scanf("%d%d", &x1, &y1);
drawline(x0, y0, x1, y1);
return 0;
Output :
Output for DDA line drawing algorithm:
Output for Bresenham's line drawing algorithm:
Conclusion:
With the help of DDA and Bresenham's line drawing algorithm it becomes possible to draw an accurate line as per the co-ordinates given by the user.
Question of Curiosity
Q.1] Write Disadvantages of DDA line algorithm. How it is overcome by Bresenham Line Drawing algorithm.
Ans] Disadvantages of DDA Algorithm-
1.There is an extra overhead of using round off( ) function.
2. Using round off( ) function increases time complexity of the algorithm.
3. Resulted lines are not smooth because of round off( ) function.
4. The points generated by this algorithm are not accurate.
The advantages of Bresenham Line Drawing Algorithm are :
- It is easy to implement.
- It is fast and incremental.
- It executes fast but less faster than DDA Algorithm.
- The points generated by this algorithm are more accurate than DDA Algorithm.
- It uses fixed points only
Q.2] Plot the Line for co-ordinates 100,100 to 150,150 using DDA and Bresenham Line Drawing algorithm.
Output using DDA line drawing algorithm:
Output using Bresenham line drawing algorithm:
Comments
Post a Comment