Module 2:Output Primitives
Que: Explain DDA line drawing algorithm with example.
DDA line drawing algorithm:
DDA (
Digital Differential Analyzer ) Algorithm is scan conversion of line. It
accepts end points of line A(x1,y1) and B(x2,y2) , finds intermediate pixel
location and display on display device.
we know
line equation y=mx+c where m is slope and c is y-intercept as constant.
slope
m=(y2-y1)/(x2-x1)
= dy/dx where
dx=(x2-x1)
and dy=(y2-y1)
we can
calculate dy if we know dx as dy=m.dx and
we can calculate dx if we know dy as dx=dy/m.
from above
equation we can say if dx=1 then dy=m and if dy=1 then dx=1/m.
DDA
algorithm increments by unit value in one coordinate and second coordinate can
be calculated.Unit increment is based on slope. if abs(slope) <1 then
increment by one in x coordinate and y
coordinate increment can be calculated by
xinc=1,yinc=m
if abs(slope)>1 then increment by one in y
coordinate and calculate x coordinate increment as
yinc=1,xinc=1/m
using
increment factor all intermediate values can be calculated as
xnext=xcurrent+xinc
ynext=ycurrent+yinc
this process
is recursive till we reach last
coordinate of line (x2,y2).
Steps:
1.Accept
input (x1,y1) and (x2,y2) as
end points of Line.
2.Calculate
dx=(x2-x1)
and dy=(y2-y1).
3.If
abs(dx)>=abs(dy)
length=dx
else
length=dy
4.Calculate xinc=dx/length and yinc=dy/length.
5. Plot first pixel (x1,y1) .
6. Calculate xk+1=xk+xinc and yk+1=yk+yinc
and plot(xk+1, yk+1).
7. Repeat step 6 ,length times.
8. Stop
Que: What are limitations of DDA line drawing algorithm.
1. In DDA algorithm we are rounding pixel value to nearest integer this may lead to drifting of line from actual path.
2. floating point calculation and rounding is time consuming process.
2. floating point calculation and rounding is time consuming process.
Que: Explain Bresenham's line drawing algorithm with example.
Bresenhams line
drawing algorithm removes disadvantages of DDA algorithm. this algorithm uses
integer calculation instead of floating-point calculation to reduce complexity
and time consumption. In bresenhams algorithm pixel which is nearer to line
will be displayed as a part of line based on distance from center of pixel and
actual line
From above diagram, equation of line at point (y, xa+1) is
y=m.(xa+1)+c. we will calculate distance D1 and distance D2 to check
which pixel is nearer to line .
D1=y-ya
D1= m.(xa+1)+c-ya
-------------------------------------------------(1)
D2=ya+1 -y
D2= ya+1 - m.(xa+1)+c -------------------------------------------------(2)
We will decide nearer pixel based on D1-D2 and multiplied by dx for
integer calculation as a decision parameter.
Pa= dx*(D1-D2)
Pa= 2.dy.xa -2.dx.
ya +b where b=2.dy+dx.(2c-1) , dx=x2-x1 and
dy=y2-y2..……(3)
At next step decision parameter will be
Pa+1 = 2.dy.xa+1
-2.dx. ya+1 +b --------------------------(4)
We will find relation between current decision parameter and next decision
parameter by subtracting Pa from Pa+1.
Pa+1- Pa = (2.dy.xa+1 -2.dx. ya+1 +b) – (2.dy.xa -2.dx. ya +b)
Pa+1 = Pa+ 2.dy -2.dx(ya+1
- ya) -----------------------------(5)
Initial decision parameter calculated at (x0,y0)
is
P0=2.dy-dx.
1.Accept
line endpoints A(x1,y1) and B(x2,y2) as input.
2.Calculate dx=x2-x1,dy=y2-y1,2.dx,2.dy
3.Calculate
initial decision parameter p0=2.dy-dx
4.If
pk<0:
x1=x1+1,
y1=y1 and
pk+1=pk+2.dy
else:
x1=x1+1,
y1=y1+1 and
pk+1=pk+2.dy-2.dx
5 . Repeat step 4 dx times
6. Plot all pixels and Stop
Que: Explain Midpoint Circle drawing algorithm with example.
Circle: it is locus of points equidistant from center . It means all points on circle are of distance r from center point (xc,yc) in all sides.
Equation of circle with center (xc,yc) and radius r
(x-xc)2+(y-yc)2=r2
Center is at (0,0)
x2+y2=r2 Where x and y is any point on circle
(x-xc)2+(y-yc)2=r2
Center is at (0,0)
x2+y2=r2 Where x and y is any point on circle
Symmetry of circle:
Circle is symmetric if we divide circle along the diameter. If circle is divided into eight parts as shown below then all parts are symmetric.It is possible to draw complete circle if we know coordinates in one part.
Steps:
Step 1: Accept Center point (xc,yc) of Circle and radius r of Circle.
Step 2: calculate initial decision parameter p=1-r
Step 3: if p<0:
x=x+1, y=y, P=P+2x+1
else:
x=x+1,y=y-1,
p=p+2x+1-2y
Step
4: repeat step 3 until x>=y
Step
5: plot all points with respect to center point in all octants.
Step
6: stop.
Que: What are different character generation method? Explain all methods.
Character generation methods:
• Bitmap Method:Use of Pixel Array to display character.Font of Character can be increased by increasing pixel array size.
 |
• Stroke Method:Character can be drawn using graphics Primitives like Line, Curve etc.Font size can be increasing length /width of graphics primitives.
• Starburst Method:
Fixed pattern of 24 lines is used.Each character is stored in 24 bits representation.
Bit for The line highlighted to be set as 1 and non highlighting set as 0.
24
bit code for A is:100001110011110000001100
Que: Define Aliasing. Enlist and Explain methods of Anti aliasing.
Aliasing:
Jagged or staircase effect occur during display of graphics primitives is called as aliasing.
Antialiasing Techniques
• Super
sampling
• Area
Sampling
• Pixel
Phasing
• Masking
Que: Define Polygon. Explain need of Filling polygon.
⦁ Polygon:
E.g. Triangle, Rectangle, Hexagon ….
⦁ Need of Polygon filling:
⦁ After filling polygon, it can look solid and it can give feel like real world objects.
⦁ Human likes colorful objects instead of only outline or black and white objects.
Que: Explain Inside-Outside test methods for finding inside region.
⦁ Inside-Outside Test:
There are two methods – 1) Even Odd Method 2) Winding Number Method
⦁ Even- Odd Method:
In this method line is drawn from point of question and outside point having x coordinate value less than any of vertices x-coordinate value in horizontal direction.
Calculate number of intersections with the polygon boundary.
Select point B and point D from polygon and draw line from those points as AB and CD. Count number of intersections of line with polygon boundary.
- if number of intersections with polygon boundary are odd then Point is inside.
- if number of intersections with polygon boundary are even then Point is outside.
if one point is inside then the area from where point is selected is also inside. As point B is inside means whole area is inside as highlighted by blue color.As point D is outside whole area is outside as shown.
There is problem when line is passing through vertices. There are two possibilities where line passing through vertices. This problem is solved by considering count 1 when line passing through vertices where edges are in opposite direction and consider count 2 when line passing through vertices where edges are of same side.
⦁ Winding Number Method:
If winding number is zero, then Point is Outside
If winding number is non-zero, then Point is Inside
Que: Explain Boundary fill and Flood fill polygon filling algorithms.
In Boundary fill algorithm start filling from a inside point towards outward till the boundary.
It accepts coordinates of inside point (seed point), fill color and boundary color.
It fills seed pixel with fill color and test neighbors of seed pixel. If neighbor pixel is not having fill color, then paint with fill color this process continues till boundary. Neighbors are tested using 4-connected or 8- connected approach.
void bound_fill (int x, int y, int fill_color, int bound_color)
{
int a=getpixel(x,y);
if (a!=fill_color && a!=bound_color)
{
putpixel(x,y,fill_color);
}
bound_fill(int x+1, int y, int fill_color, int bound_color);
bound_fill(int x, int y+1, int fill_color, int bound_color);
bound_fill(int x-1, int y, int fill_color, int bound_color);
bound_fill(int x, int y-1, int fill_color, int bound_color);
}
⦁ Flood Fill Algorithm:
Flood Fill Algorithm fills area bordered with multiple color.
Flood fill algorithm replaces interior color with fill color instead of checking boundary color.
It uses 4-connected or 8- connected approach.
