UNIT-2
Scan Conversion Algorithm
1
Content
Line drawing algorithms:
• DDA (Digital Differential Analyzer)
• Bresenham’s line drawing algorithm
Circle Generating Algorithms:
• Mid-point Circle Generating Algorithm
• Bresenham’s Circle Algorithm
LINE ALGORITHM
• A line drawing algorithm is a graphical
algorithm for approximating a line segment on
discrete graphical media.
The goals of line drawing algorithms
• Straight line should appear straight.
• It should start and end accurately, matching end points with
connecting lines
• Lines should have constant brightness.
• Lines should be drawn as rapidly as possible.
Two line drawing algorithms are
• DDA (Digital Differential Analyzer)
DDA Algorithm
It is used for finding Rasterlize straight line.
(X1,Y1) (X2,Y2)
Algorithm:
1. Read the line end points in form of (x1,y1) and (x2,y2).
2. Calculate the distance between the two end points vertically and horizontally,
i.e dx=|x1-x2| and dy=|y1-y2|.
3. Define new variable name ‘pixel’(length), and compare dx and dy values,
if (dx > dy) then pixel=dx else pixel =dy.
4.Select Raster unit
dx=dx/pixel
and dy=dy/pixel
5. x=x1;y=y1;
Drawback of DDA Line Algo:
. (x1, y1) = (0, 0) and (x2, y2) = (6, 6)
∆x = x2 – x1 = 6-0 = 0 ∆y = y2 – y1 = 6 -0 = 6
Length = 6
S.No. i Plot
1 0 0,0
2 1 1, 1
3 2 2,2
4 3 3, 3
5 4 4, 4
6 5 5, 5
7 6 6, 6
Bresenham's Line Algorithm
This algorithm is very efficient since it use only incremental
integer calculations.
Bresenham’s Line Algorithm:
1. Input the two line endpoints and store the left endpoint in
(xo,yo)
2. Load (xo, yd into the frame buffer; that is, plot the first
point.
3. Calculate constants ∆x, ∆y, 2∆y, and 2∆y – 2∆x, and obtain
the starting value for the decision parameter as po = 2∆y -
∆x
Continue...
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-2∆y
Otherwise, the next point to plot is (xk+1, yk+1) and
pk+1 = pk + 2∆y - 2∆x
5. Repeat step 4 ∆x times.
po = 2∆y - ∆x
pk+1 = pk-2∆y 8
Circle Generating Algorithms
Representation of Circle:
• Polynomial
• Trigonometric
• Polynomial:
x2+y2=r2
• Trigonometric:
x=rcosΘ,y=rsinΘ
Where
x & y are coordinate Eight-way Symmetric rule of
circle
Mid-point Circle Generating Algorithm
• In the mid-point circle algorithm we use eight-way
symmetry so only ever calculate the points for the top right
eighth of a circle, and then use symmetry to get the rest of
the points.
Mid-Point Circle
1)Input radius r and circle center (x, y,), and obtain the first
point on the circumference of a circle centered on the origin
as (x0,y0) = (0, r)
2)Calculate the initial value of the decision parameter as
p0 = 5\4 – r
3)At each xk position, starting at k = 0, perform the following
test: If pk < 0, the next point along the circle centered on
(0,0) is (xk+1, yk) and
pk+1 = pk+2xk+1+1
Continue...
Otherwise, the nest point along the circle is (xk+1, yk+1) and
pk+1 = pk+2xk+1+1-2yk+1
where
2xk+1= 2xk + 2 and
2yk+1= 2yk - 2.
4. Determine symmetry points in the other seven octants.
5. Move each calculated pixel position (x, y) onto the circular
path centered on (xc, yc) and plot the coordinate values:
x = x + xc, y = y + yc
6. Repeat steps 3 through 5 until x >= y.
12
Bresenham’s Circle Algorithm
• Read the radius r of the circle.
• Initialize the decision variable
d=3-2*r
• Then, put x=0,y=r
• If we are using octant symmetry to the pixels then
Until (x<y) we have perform all steps.
If (d<0)
then
d=d+4x+6
x=x+1 , y=y
Continue...
else
d=d+4(x-y)+10
x=x+1 , y=y-1
• Plot(x,y)
• Determine the symmetry points in other octants also.
• Stop.
14
