DDA (Digital Differntial Analyzer) ALGORITHM:-
A line segment is completely defined in terms of its two endpoints.
A line segment is thus defined as:
Line_Seg = { (x1, y1), (x2, y2) }
All line drawing algorithms make use of the fundamental equations:
Line Equation → y = mx + b (Eqn-1)
Slope → m = y2 − y1 / x2 − x1 = Δy / Δx (Eqn-2)
x-interval → Δx = Δy / m (Eqn-3)
y-interval → Δy = m Δx (Eqn-4)
y-intercept → b = y1 − m.x1 (Eqn-5)
For any given x, interval Δx along a line,
we can compute the corresponding y interval Δy from (Eqn-4)
Similarly, we can obtain the x interval Δx from (Eqn-3) corresponding to a specified Δy.
For lines with slope magnitudes
I m I < 1,
Δx can be set proportional to small horizontal deflection voltage
and corresponding
vertical deflection is then set proportional to Δy.
For lines with slope magnitudes
I m I > 1,
Δy can be set proportional to small vertical deflection voltage
and corresponding
horizontal deflection voltage set proportional to Δx.
DDA Line Algorithm based on calculating either Δy or Δx using the equations: (Eqn-3) & (Eqn-4)
x-interval → Δx = Δy / m (Eqn-3)
y-interval → Δy = m Δx (Eqn-4)
There are two cases based on value of slope :-
I m < 1 I & I m > 1 I
CASE :1
If ImI ≤ 1 means Δy ≤ Δx
then Δx set to unit interval , Δx = 1,
From equation of slope,
m= Δy /Δx = Δy/1
Δy = m
So coordinate for next pixel is given by,
xk+1 = xk + Δx = xk + 1
yk+1 = yk + Δy = yk + m
Since 0.0 < m ≤ 1.0, the calculated y values must be rounded to nearest integer pixel position.
CASE :2
If ImI > 1 means Δy > Δx
then Δy set to unit interval , Δy = 1,
From equation of slope,
m= Δy /Δx = 1/ Δx
Δx = 1/m
So coordinate for next pixel is given by,
xk+1 = xk + Δx = xk + 1/m
yk+1 = yk + Δy = yk + m
In this case, the calculated x values must be rounded to nearest integer pixel position.
CASE :1
If ImI ≤ 1 means Δy ≤ Δx
then Δx set to unit interval , Δx = 1,
From equation of slope,
m= Δy /Δx = Δy/1
Δy = m
So coordinate for next pixel is given by,
xk+1 = xk + Δx = xk - 1
yk+1 = yk + Δy = yk - m
Since 0.0 < m ≤ 1.0, the calculated y values must be rounded to nearest integer pixel position.
CASE :2
If ImI > 1 means Δy > Δx
then Δy set to unit interval , Δy = 1,
From equation of slope,
m= Δy /Δx = 1/ Δx
Δx = 1/m
So coordinate for next pixel is given by,
xk+1 = xk + Δx = xk - 1/m
yk+1 = yk + Δy = yk - 1
DDA ALGORITHM:
1. START
2. Get the values of the starting and ending co-ordinates i.e. (xa,ya) and (xb,yb).
3. Find the value of slope m
m = dy/dx
= ( (yb-ya) / (xb-xa) )
4. If ImI ≤ 1 then
∆x = 1, ∆y = m∆x , ∆y = m
xk+1 = xk + 1, Yk+1 = Yk + m
5. If ImI >1 then
∆y = 1, ∆x = ∆y/m , ∆x = 1/m
xk+1 = xk + 1/m, Yk+1 =Yk + 1
6. STOP
Pseudo Code Of DDA Algorithm
Procedure lineDDA(xa,ya,xb,yb:integer);
var
dx,dy,steps,k:integer
xIncrement, yIncrement, x, y:real;
begin
dx:=xb-xa;
dy:=yb-ya;
if abs(dx)>abs(dy) then steps:=abs(dx)
else steps:=abs(dy);
xIncrement:=dx/steps;
yIncrement:=dy/steps;
x:=xa;
y:=ya;
setPixel(round(x),round(y),1);
for k:=1 to steps do
begin
x:=x+xIncrement;
y:=y+yIncrement;
setPixel(round(x),round(y),1)
end
end
Example:
Consider the line from (0,0) to (4,6). Use the simple DDA algorithm to rasterize
this line.
Consider the line from (0,0) to (4,6). Use the simple DDA algorithm to rasterize
this line.
Sol. Rasterizing the line from (0,0) to (4,6) using DDA algorithm ,
Xl = 0 Y1 = 0 X2 = 4 Y2 = 6
m = ∆Y / ∆X = 6 – 0 / 4 – 0 = 6 / 4 = 1.5 > 1 So, ∆Y > ∆X
For slope ImI > 1 , We know
∆X = 1/m = 1/1.5 = 0.67
&
∆Y = 1 (unit increment)
step = max(dx,dy) = 6
∆X = |X2- X1| / step = 4 / 6 = 0.67
&
∆Y = |Y2- Y1 | / step = 6/6 = 1 (unit increment)
Tabulating the results of each iteration using DDA for |m|>1 for line(0,0) to (4,6)
k
|
Xk,
|
Yk
|
Xk+1 = Xk + 1/m
(1/m = 0.67)
|
Yk+1 = Yk + 1
|
putpixel (Xk+1, Yk+1)
|
0
|
0
|
0
|
0.67
|
1
|
(1,1)
|
1
|
1
|
1
|
1.34
|
2
|
(1,2)
|
2
|
1
|
2
|
2.01
|
3
|
(2,3)
|
3
|
2
|
3
|
2.68
|
4
|
(3,4)
|
4
|
3
|
4
|
(3.35)
|
5
|
(3,5)
|
5
|
3
|
5
|
(4.02)
|
6
|
(4,6)
|
SOLVED using DDA Line from (0,0) to (4,6)
Below is a C program of DDA line drawing algorithm with output:-
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
void main()
{
int i,gd,gm;
float x,y,x1,y1,x2,y2,x_incr,y_incr,length,dx,dy,m;
printf("enter the value of x1:");
scanf("%f",&x1);
printf("\n enter the value of y1:");
scanf("%f",&y1);
printf("\n enter the value of x2:");
scanf("%f",&x2);
printf("\n enter the value of y2:");
scanf("%f",&y2);
detectgraph(&gd,&gm);
initgraph(&gd,&gm," ");
setbkcolor(7);
dx=abs(x2-x1);
dy=abs(y2-y1);
m=dy/dx;
printf("Slope=%f",m);
if(dx>=dy)
{
length=dx;
}
else
{
length=dy;
}
x_incr=abs(x2-x1)/length;
y_incr=abs(y2-y1)/length;
x=x1;
y=y1;
putpixel(x,y,12);
i=1;
while(i<=length)
{
x=x+x_incr;
y=y+y_incr;
putpixel(x,y,12);
printf("\n %f %f",x,y);
i=i+1;
delay(50);
}
getch();
closegraph();
}
Output:
THANK YOU!!!
No comments:
Post a Comment