Unit 2

Scan Conversion Algorithm

By: Suvash Chandra Gautam
(PhD Scholar)
June 01, 2024
Scan Conversion
- A procedure used to digitize or rasterize pixel data available on frame buffer.
- The process of representing continuous graphics object as a collection of
discrete pixels is called scan conversion. For e.g. a line is defined by its two
end points and the line equation.
- Scan conversion of a point requires the two data that are pixel position
and color for display.
 Scan Conversion of line
•Let 𝑦 = 𝑚𝑥 + 𝑏 be the equation of line with end point (𝑥1, 𝑦1) and
(𝑥2, 𝑦2) then,∴ 𝑚 = ∆𝑦 ……………………. (i)
𝑥2−𝑥1 ∆𝑥
𝑦2 −𝑦1
𝑚=

•Here, 𝑚 represents the slope of line path where by ∆𝑥 & ∆𝑦 gives the
deflection needed towards horizontal and vertical direction to get new pixel
from current pixel position.
- Slope of line also describes the nature and characteristics of line that is going
to display.
Line Drawing algorithm

a)Digital Differential Analyzer (DDA) algorithm (Incremental algorithm)

• Advantages
- It is simple to understand.
- It requires no special skills for implementation.
- It is faster method than direct use of the line equation y=mx+c.
•Disadvantages of DDA:
- m is stored in floating point number.
- Accumulation of round-off error in successive additions can cause
calculated pixel positions to drift away from the actual line path for long
line segments.
- Rounding operations and floating-point-arithmetic are time consuming.
Q. Digitize the line with end points (0, 0) and (4, 5) using DDA.

X Y x-plot y-plot (x, y)

0 0 0 0 (0, 0)
0.8 1 1 1 (1, 1)
1.6 2 2 2 (2, 2)
2.4 3 2 3 (2, 3)
3.2 4 3 4 (3, 4)
4 5 4 5 (4, 5)
Q. Digitize the line with end points (3, 7) and (8, 3) using DDA.
 Bresenham's Line Algorithm

• This algorithm is used for scan converting a line. It was developed by Bresenham. It is an
efficient method because it involves only integer addition, subtractions operations. These
operations can be performed very rapidly so lines can be generated quickly.
• In this method, next pixel selected is that one who has the least distance from true line.
‘

Then at sampling point (𝑥𝑘 + 1)

Q. Digitize the line with endpoints (20, 10), (30, 18) using Bresenham’s line algorithm.

Solution:
Here,
(𝑥1, 𝑦1) = (20, 10)
(𝑥2, 𝑦2) = (30, 18)

𝑦 −𝑦 18−10
𝑚 = 2 1= = 0.8 < 1
𝑥2−𝑥1 30−20
Here, ∆𝑥 = 10, ∆𝑦 = 8, 2∆𝑦 = 16, 2∆𝑦 − 2∆𝑥 = −4
Since, for the Bresenham’s line drawing algorithm of slope 𝑚 < 1,
The initial decision parameter ( 𝑃0) = 2∆𝑦 − ∆𝑥 = 16 − 10 = 6 > 0
we have If 𝑃𝑘 ≥ 0,
𝑦𝑘+1 = 𝑦𝑘 + 1 & 𝑥𝑘+1 = 𝑥𝑘 + 1 and 𝑃𝑘+1 = 𝑃𝑘 + 2∆𝑦 − 2∆𝑥
If 𝑃𝑘 < 0,
𝑦𝑘+1 = 𝑦𝑘 & 𝑥𝑘+1 = 𝑥𝑘 + 1 and 𝑃𝑘+1 = 𝑃𝑘 + 2∆𝑦
Q. Digitize the line with endpoints (20, 15) & (30, 30) using Bresenham’s line algorithm

Solution:
Here,
(𝑥1, 𝑦1) = (20, 15)
(𝑥2
, 𝑦2) = (30, 30)
𝑦2 −𝑦1 30−15
𝑚= = = 1.
5>1
𝑥2−𝑥1 30−20

Here, ∆𝑥 = 10, ∆𝑦 = 15, 2∆𝑥 = 20, 2∆𝑥 − 2∆𝑦 = −10

The initial decision parameter ( 𝑃0) = 2∆𝑥 − ∆𝑦 =20-15=5>0
Since, for the Bresenham’s line drawing algorithm of slope 𝑚 > 1, we have If 𝑃𝑘 ≥ 0,
𝑥𝑘+1 = 𝑥𝑘 + 1 & 𝑦𝑘+1 = 𝑦𝑘 + 1 and 𝑃𝑘+1 = 𝑃𝑘 + 2∆𝑥 − 2∆𝑦
If 𝑃𝑘 < 0,
𝑥𝑘+1 = 𝑥𝑘 & 𝑦𝑘+1 = 𝑦𝑘 + 1 and 𝑃𝑘+1 = 𝑃𝑘 + 2∆𝑥
11 15 (28, 27)
12 5 (29, 28)
13 -5 (29, 29)
14 15 (30, 30)
Q. How would you digitize a line with end points A(6, 12) and B(10, 5) using
Bresenham’s line drawing algorithm?
Advantages of Bresenham’s line algorithm (BLA) over DDA:
- In DDA algorithm each successive point is computed in floating point, so it
required more time and memory space. While in BLA each successive point
is calculated in integer value or whole number. So it requires less time and
less memory
- In DDA, since the calculated point value is floating point number, it should be
rounded at the end of calculation but in BLA it does not need to round, so
there is no accumulation of rounding error.
- Due to rounding error, the line drawn by DDA algorithm is not accurate,
while in BLA line is accurate.
- DDA algorithm cannot be used in other application except line drawing but
BLA can be implemented in other application such as circle, ellipse and other
curves.
 Differentiate between DDA Algorithm and Bresenham's Line Algorithm:

DDA Algorithm Bresenham's Line Algorithm

1. DDA Algorithm use floating point, i.e. Real Arithmetic. 1. Bresenham's Line Algorithm use fixed point, i.e.
Integer Arithmetic

2. DDA Algorithms uses multiplication & division on its 2.Bresenham's Line Algorithm uses subtraction and
operation addition on its operation

3. DDA Algorithm is slower than Bresenham's Line 3. Bresenham's Algorithm is faster than DDA Algorithm
Algorithm in line drawing because it uses real arithmetic in line because it involves addition & subtraction in its
(Floating Point operation) calculation and uses only integer arithmetic.

4. DDA Algorithm is not accurate and efficient as 4. Bresenham's Line Algorithm is more accurate and
Bresenham's Line Algorithm. efficient than DDA Algorithm.

5.DDA Algorithm can draw circle and curves but are not 5. Bresenham's Line Algorithm can draw circle and
accurate as Bresenham's Line Algorithm curves with more accurate than DDA Algorithm.
 Circle
• Circle is defined as a set of points that are all at a given distance ‘r’ from the
center position (𝑥𝑐, 𝑦𝑐).
• Equation of circle centered at (𝑥𝑐, 𝑦𝑐) with radius ‘r’ is
(𝑥 − 𝑥𝑐)2 + (𝑦 − 𝑦𝑐)2 = 𝑟2
Symmetry of Circle
Calculation of circle point (𝑥, 𝑦) in one
octant yields the circle points shown for the
other seven octants.
 Midpoint Circle Algorithm
•Assume that we have just plotted point xk yk
( , ).

•The next point is a choice between xk 1 yk and xk 1 yk-1

( + , ) ( + , ).

•We would like to choose the point that is nearest to the actual circle.
Let us define a circle function as;

𝑦𝑘

𝑦𝑘 − 1

𝑥𝑘 𝑥𝑘+
Q. Digitize the circle 𝒙𝟐 + 𝒚𝟐 = 𝟏𝟎𝟎 in first octant.
Q. Digitize the circle with radius r =10 centered (3, 4) in first octant.

Solution:
Note: When center is
not origin, we first
calculate the octants
points of the circle in
the same way as the
center at origin then
add the given circle
center on each
calculated pixel.
Q. Digitize the circle with radius r =5 centered (2, 3).

Solution:
Here,
Center = (2, 3)
Radius (r) =5
Initial point = (0, r) = (0, 5)
Initial decision parameter 𝑝0 = 1 − 𝑟 = 1 − 5 = −4
From mid-point circle algorithm we have;
If 𝑝𝑘 < 0;
Plot (𝑥𝑘 + 1, 𝑦𝑘) and 𝑝𝑘+1 = 𝑝𝑘 + 2𝑥𝑘+1 + 1
𝑝𝑘 ≥ 0;
Plot (𝑥𝑘 + 1, 𝑦𝑘 − 1) and 𝑝𝑘+1 = 𝑝𝑘 + 2𝑥𝑘+1 + 1 − 2𝑦𝑘+1
 st
1 Other pixels (in …octant)
K 𝑝𝑘 (𝑥𝑘+1, 2𝑥𝑘+1 2𝑦𝑘+1
𝑦𝑘+1)
0 -4 (1, 5) 2 10 (5,1) (-5,1) (-1, 5) (-1, -5) (-5,-1) (5,- 1) (1, -5)

1 -1 (2, 5) 4 10 (5,2) (-5,2) (-2, 5) (-2, -5) (-5,-2) (5, -2) (2, -5)

2 4 (3, 4) 6 8 (4,3) (-4,3) (-3, 4) (-3, -4) (-4,-3) (4, -3) (3, -4)

3 3 (4, 3) 8 6 (3,4) (-3,4) (-4, 3) (-4, -3) (-3,-4) (3, -4) (4, -3)

Actual pixels
1st octant 2nd octant 3rd octant 4th octant 5th octant 6th octant 7th octant 8th octant
(3, 8) (7, 4) (-3, 4) (1, 8) (1, -2) (-3, 2) (7, 1) (3, -2)
(4, 8) (7, 5) (-3, 5) (0, 8) (0, -2) (-3, 1) (7, 1) (4, -2)
(5, 7) (6, 6) (-2, 6) (-1,7) (-1, -1) (-2, 0) (6, 0) (5, -1)
(6, 6) (5, 7) (-1, 7) (-2, 6) (-2, 0) (-1, -1) (5, -1) (6, 0)
 Ellipse
• Ellipse is defined as the geometric figure which is the set of all points on a plane
whose distance from two fixed points known as the foci remains a constant.
• It consists of two axes: major and minor axes where the major axis is the longest
diameter and minor axis is the shortest diameter.
• Unlike circle, the ellipse has four-way symmetry property which means that only
the quadrants are symmetric while the octants are not.
• Here, we will calculate the points for one quadrant while the points for the
remaining three can be calculated using the former points.
• What is an ellipse?
• Ellipse is defined as the geometric figure which is the set of all points on a
plane whose distance from two fixed points known as the foci remains a
constant.
• It consists of two axes: major and minor axes where the major axis is the
longest diameter and minor axis is the shortest diameter.
• Unlike circle, the ellipse has four-way symmetry property which means that
only the quadrants are symmetric while the octants are not.
• Here, we will calculate the points for one quadrant while the points for the
remaining three can be calculated using the former points.
Now, for understanding the proper working of the algorithm, let us consider the elliptical
curve in the first quadrant.
Also, consider the equation of ellipse:
ry2 x2 + rx2 y2 - rx2 ry2 = 0 ...(1)
where, ry : semi-minor axis rx : semi-major axis
In the ellipse each quadrant is divided into two regions: R1 and R2 respectively.
We know that the slope of an ellipse is given by:
m = dy / dx = - (2 ry2 x /2 rx2 y ) = -1
The region R1 has the value of slope as m<-1 while R2 has the value of slope as m > -1.
The starting point for R1 will be (0, ry) and for R2, the initial points will become the ending
points of R1, where the slope becomes greater than -1.
Thats why we need to keep in check the value of slope while plotting the points for R1 to
know whether we have reached R2 or not.
We will do the derivation for each region:
Derivation for Region 1:
Let us consider two pixels: one which is outside(A) and the other which is inside(B)
respectively.
Let their coordinates be:
For A; ( xk+1, yk )
For B; ( xk+1, yk-1 )
Value for their mid-point will be:
Mp= [ ( (xk+1 + xk+1) / 2 ) ,( (yk + yk-1) / 2) ]
= ( xk+1 , yk-1 / 2 )
Putting Mp in eqn (1):
ry2 (xk+1)2 + rx2 ( yk-1 / 2 )2 - rx2 ry2
Let us define this statement as our decision variable:
Pk= ry2 ( xk+1 )2 + rx2 ( yk-1 / 2 )2 - rx2 ry2 -----(2)
Successive parameter can be defined as:
Pk+1­= ry2 ( xk+1+1 )2 + rx2 ( yk+1-1 / 2 )2- rx2 ry2 -----(3)
Now, subtract eqn (2) from eqn (3);
Pk+1 -­ Pk = [ ry2 ( xk+1 + 1 )2 + rx2 ( yk+1-1 / 2 )2- rx2 ry2 ] - [ ry2 (xk+1)2+ rx2( yk-1 / 2 )2 –
rx2 ry2 ]
= ry2 [ (xk+1+1)2 - (xk+1)2 ] + rx2 [ ( yk+1-1 / 2 )2 - ( yk-1 / 2 )2 ]
As the x-coordinate remains same in both the pixels, put xk+1 = xk+1

Pk+1­- Pk = ry2 [ (xk+1+1)2 - (xk+1)2 ] + rx2 [ ( yk+1-1 / 2 )2 - ( yk-1 / 2)2 ]

= ry2 [ 2xk + 3 ] + rx2 [ (yk+1)2 - yk+1 - (yk)2 + yk ]
Pk+1 =­Pk + ry2 [ 2xk + 3 ] + rx2 [ (yk+1)2 - yk+1 - (yk)2 + yk ]
If Pk < 0 : use yk+1 = yk (Choose point A)
Pk+1 =­Pk+ ry2 [ 2xk + 3 ]
If Pk ≥ 0: use yk+1 = yk -1 (Choose point B)
Pk+1 =­Pk + ry2 [ 2xk + 3 ] + 2 [ 1 - yk ]
Initial Decision Parameter
Put initial point(0,ry) in eq.(2)
P0= ry2 (0+1)2 + rx2( ry-1 /2)2 - rx2 ry2

2 2 2
Derivation for Region 2:
Let us consider two pixels: one which is outside(P) and the other which is inside(Q)
respectively.
Let their coordinates be:
For P; (xk+1, yk-1)
For Q; (xk, yk-1)
Value for their mid-point will be:
Mp= [ ( (xk+1+ xk) / 2 ), ( (yk-1 yk-1) / 2 ) ]
= ( xk+1 / 2 , yk-1 )
Putting Mp in eq.(1):
ry2 (xk+1 / 2)2 + rx2 (yk-1)2- rx2 ry2
Let us define this statement as our decision variable:
P2k = ry2 ( xk+1 /2)2 + rx2 (yk-1)2 - rx2 ry2 ----(4)
Successive parameter can be defined as:
P2 = r 2 ( x + 1 / 2 )2 + r 2 ( y -1 )2 - r 2 r 2 ----(5)
Now, subtract eq.(4) from eq.(5);
P2k+1­- P2k = [ ry2 (xk+1+1/2)2 + rx2 (yk+1-1)2- rx2ry2 ] - [ ry2 (xk+1/2)2+ rx2 (yk-1)2 -
rx2 ry2]
= ry2 [ (xk+1+1 / 2 )2 - ( xk+1 / 2 )2 ] + rx2 [ (yk+1-1)2 - (yk-1)2]
As the y-coordinate remains same in both the pixels, put yk+1 = yk-1
P2k+1­- P2k = ry2 [ (xk+1)2 + xk+1 - (xk)2 - xk ]+ rx2 [ 3 - 2yk ]
P2k+1 =­P2k + ry2 [ (xk+1)2 + xk+1 - (xk)2 - xk ]+ rx2 [ 3 - 2yk ]
If P2k > 0: use xk+1= xk (Choose point Q)
P2k+1 =­P2k - 2 yk+1 rx2 + rx2
If P2k ≤ 0: use xk+1 = xk +1 (Choose point P)
P2k+1 =­P2k+ 2ry2 [2 xk+1] - 2 yk+1 rx2 + rx2
Initial Decision Parameter:
Putting the ending point of region R1
Where, m > -1 i.e. (x, y) in eq.(4)
P20 = ry2 ( x+1 / 2 )2 + rx2 (y-1)2 - rx2 ry2
Q. Digitize the ellipse with 𝒓𝒙 = 𝟖, 𝒓𝒚 = 𝟔 and center at (3, 5).
Algorithms for filled area primitives
a)Scan line polygon fill algorithm
b)Boundary fill algorithm
c)Flood fill algorithm
Rule: To identify a point whether it is exterior or interior, draw a line from that point to
outside a polygon, if this line crosses even number of edges the point is exterior
otherwise it is interior.
Thank You