COMPUTER GRAPHICS

CGR-22318
UNIT-II
RASTER SCAN GRAPHICS

Miss. S. A. Salunkhe
23-07-2020
 POINTS TO BE COVERED
• BASIC CONCEPTS IN LINE DRAWING
– DIGITAL DIFFERENTIAL ANALYSER (DDA) ALGORITHM

– BRESENHAMS ALGORITHM

• BASIC CONCEPTS IN CIRCLE GENERATION

ALGORITHM
– SYMMETRY OF CIRCLE

– BRESENHAMS CIRCLE GENERATION ALGORITHM

• POLYGONS

• POLYGON FILLING ALGORITHMS

• CHARACTER GENERATION METHODS

23-07-2020
 LINE DRAWING ALGORITHM
• Line is a straight object with no curves.

• A line does not have end and if it has ends then it is called as
line segment.

• The process of turning on the pixels for a line

segment is called as vector generation or line generation.

• And the algorithms used for drawing these lines are called as
vector generation algorithm or line drawing algorithms.

23-07-2020
 Y-axis

Vertical

X-axis
0
Horizontal
23-07-2020
 LINE DRAWING ALGORITHM
• DIGITAL DIFFERENTIAL ANALYZER (DDA) ALGORITHM

• Computer needs to take care of 2 things

– Pixels
– Computation

• DDAlinedrawing algorithm helps computer to make

this possible

23-07-2020
 LINE DRAWING ALGORITHM
• SLOPE INTERCEPT LINE EQUATION

𝒚 = 𝒎𝒙 + 𝒃

• Where, m = slope and b = y

intercept

• And 𝒎 = 𝒅𝒚 𝒐𝒓 ∆𝒚 = 𝒚𝟐−𝒚𝟏
𝒅𝒙 ∆𝒙 𝒙𝟐−𝒙𝟏

• And 𝒃 = 𝒚𝟏 − 𝒎𝒙𝟏

23-07-2020
 Y-axis

(x1 , y1)

(x0 , y0)

X-axis
0

23-07-2020
 LINE DRAWING ALGORITHM
• Plot initial points 𝒙 = 𝒙𝟎 , 𝒚 = 𝒚𝟎

• Then find,
• 𝑥0, 𝑟𝑜𝑢𝑛𝑑 𝑦 and 𝑦 = 𝑦0 + mx

• CASE I – if m < 1 (x is increasing more than y)

• 𝒙 = 𝒙𝟎 + 𝟏 and 𝒚 = 𝒚𝟎 + 𝒎
• Where value of x=1.
• Repeat the above equations till we get the following condition
• 𝒙𝟎 = 𝒙 𝟏

23-07-2020
 LINE DRAWING ALGORITHM
• CASE II – if m > 1 (y is increasing more than x)
• 𝑟𝑜𝑢𝑛𝑑 𝑥 , 𝑦
• 𝒙 𝒙 𝟏
𝒏𝒆𝒘 𝒗𝒂𝒍𝒖𝒆 𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 𝒗𝒂𝒍𝒖𝒆
( )= ( )+
• 𝒚𝒎 𝒚 𝟏
𝒏𝒆𝒘 𝒗𝒂𝒍𝒖𝒆 𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 𝒗𝒂𝒍𝒖𝒆
( )= ( )+

• Where value of y=1.

• Repeat the above equations till we get the following condition

• 𝒚𝟎 = 𝒚 𝟏

23-07-2020
 EXAMPLE 1
• Input Coordinates A(2,3) & B(12,8)

∆𝑦 y2−y1 8−3 5
• Slope 𝑚 = = = = = 𝟎. 𝟓
∆𝑥 X2−X1
12−2 10

• m < 1 (x increment more than y)

• 𝑥0, 𝑟𝑜𝑢𝑛𝑑 𝑦 and 𝑦 = 𝑦0 + mx

• 𝒙 = 𝒙𝟎 + 𝟏 and 𝒚 = 𝒚𝟎 + 𝒎
• Where value of x=1

• Repeat the above equations till we get the following condition

• 𝒙𝟎 = 𝒙 𝟏
23-07-2020
 EXAMPLE 1
𝒙 = 𝒙𝟎 + 𝟏 x 𝒚 = 𝒚𝟎 + 𝒎 y x-plotted y-plotted
-- 2 -- 3 2 3
2+1 3 3+0.5 3.5 3 4
3+1 4 3.5+0.5 4 4 4
4+1 5 4+0.5 4.5 5 5
5+1 6 4.5+0.5 5 6 5
6+1 7 5+0.5 5.5 7 6
7+1 8 5.5+0.5 6 8 6
8+1 9 6+0.5 6.5 9 7
9+1 10 6.5+0.5 7 10 7
10+1 11 7+0.5 7.5 11 8
11+1 12 7.5+0.5 8 12 8
23-07-2020
 EXAMPLE 2
• Input Coordinates A(0,0) & B(4,6)

• Slope 𝑚 = ∆𝑦 = y2−y1 = 6−0 6 = = 𝟏. 𝟓

∆𝑥 X2−X1 4−0 4

• m > 1 (y increment more than x)

• 𝑟𝑜𝑢𝑛𝑑 𝑥 , 𝑦

𝟏
• 𝒙 𝒙
𝒏𝒆𝒘 𝒗𝒂𝒍𝒖𝒆 𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 𝒗𝒂𝒍𝒖𝒆
( )= ( )+𝒎
• 𝒚 𝒚 𝟏
𝒏𝒆𝒘 𝒗𝒂𝒍𝒖𝒆 𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 𝒗𝒂𝒍𝒖𝒆
( )= ( )+

• Where value of y=1.

• Repeat the above equations till we get the following condition

• 𝒚𝟎 = 𝒚𝟏
23-07-2020
 EXAMPLE 2
𝟏 x 𝒚=𝒚+𝟏 y x-plotted y-plotted
𝒙=𝒙+
𝒎
-- 0 -- 0 0 0

0+0.66 0.66 0+1 1 1 1

0.66+0.66 1.32 1+1 2 1 2

1.32+0.66 1.98 2+1 3 2 3

1.98+0.66 2.64 3+1 4 3 4

2.64+0.66 3.3 4+1 5 3 5

3.3+0.66 3.96 5+1 6 4 6

23-07-2020
 LINE DRAWING ALGORITHM
• ADVANTAGES OF DDA
• Simple and faster.
• Can plot exact points easily.

• DISADVANTAGES OF DDA
• Floating point calculation make this algorithm
slower.
• It is orientation dependent.

23-07-2020
 LINE DRAWING ALGORITHM

BRESENHAM’S LINE DRAWING ALGORITHM

23-07-2020
 Y- axis

Y
k+1

y
yk

0 D X- axis
Dupper
lower
DB DA
 LINE DRAWING ALGORITHM
• ALGORITHM STEPS
1. Input coordinates (x1,y1) and (x2,y2)
2. Plot (x1,y1)
3. Calculate Initial decision parameter 𝒆𝒌 = 𝟐∆𝒚 − ∆𝒙
4. If e > 0 , Choose pixel above the line and plot (+ve) (inc x & y)
𝒆𝒌 + 𝟏 = 𝒆𝒌 + 𝟐∆𝒚 − 𝟐∆𝒙
5. If e < 0, Choose pixel below the line and plot (-ve) (inc x)
𝒆𝒌 + 𝟏 = 𝒆𝒌 + 𝟐∆𝒚
6. Repeat step 5 for (∆𝒙 − 𝟏) times.
7. Stop
 LINE DRAWING ALGORITHM
• EXAMPLE 1
• Consider A(20,10) & B(30,18) and find the points w.r.t x &
y axis.
• ∆𝒙 = 10
• ∆𝒚 = 8
• 𝟐∆𝒙 = 20
• 𝟐∆𝒚 = 16
• 𝟐∆𝒚 − 𝟐∆𝒙 = - 4
• 𝒆𝒌 = 𝟐∆𝒚 − ∆𝒙 = 6
 𝑰𝒏𝒕𝒊𝒂𝒍 𝒅𝒆𝒄𝒊𝒔𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓 𝒆𝟎 = 6

ITR 𝒆𝒏𝒆𝒘 = 𝒆𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 + 𝟐∆𝒚 (e < 0) (-ve) ITR 𝒆𝒏𝒆𝒘 = 𝒆𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 + 𝟐∆𝒚 − 𝟐∆𝒙 (e >
NO. NO. 0) (+ve)
3 - 2 + 16 = 14 1 6 + 16 – 20 = 2
8 - 2 + 16 = 14 2 2 + 16 – 20 = - 2
4 14 + 16 – 20 = 10
5 10 + 16 – 20 = 6
6 6 + 16 – 20 = 2
7 2 + 16 – 20 = - 2
9 14 + 16 – 20 = 10
10 10 + 16 – 20 = 6
ITR No. e x y Plot
0 6 20 10 (20,10)
1 2 21 11 (21,11)
2 -2 22 11 (22,11)
3 14 23 12 (23,12)
4 10 24 13 (24,13)
5 6 25 14 (25,14)
6 2 26 15 (26,15)
7 -2 27 15 (27,15)
8 14 28 16 (28,16)
9 10 29 17 (29,17)
10 6 30 18 (30,18)
BRESENHAM’S LINE DRAWING ALGORITHM

• EXAMPLE 2
• Consider A(5,5) & B(13,9) and find the points w.r.t x & y axis.
• ∆𝒙 = 8
• ∆𝒚 = 4
• 𝟐∆𝒙 = 16
• 𝟐∆𝒚 = 8
• 𝟐∆𝒚 − 𝟐∆𝒙 = - 8
• 𝒆𝒌 = 𝟐∆𝒚 − ∆𝒙 = 0
 𝑰𝒏𝒕𝒊𝒂𝒍 𝒅𝒆𝒄𝒊𝒔𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓 𝒆𝟎 = 0

ITR 𝒆𝒏𝒆𝒘 = 𝒆𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 + 𝟐∆𝒚 (e < 0) (-ve) ITR 𝒆𝒏𝒆𝒘 = 𝒆𝒑𝒓𝒆𝒗𝒊𝒐𝒖𝒔 + 𝟐∆𝒚 − 𝟐∆𝒙 (e >
NO. NO. 0) (+ve)
2 -8+8=0 1 0–8=-8
4 -8+8=0 3 0–8=-8
6 -8+8=0 5 0–8=-8
8 -8+8=0 7 0–8=-8
ITR No. e x y Plot
0 0 5 5 (5,5)
1 -8 6 5 (6,5)
2 0 7 6 (7,6)
3 -8 8 6 (8,6)
4 0 9 7 (9,7)
5 -8 10 7 (10,7)
6 0 11 8 (11,8)
7 -8 12 8 (12,8)
8 0 13 9 (13,9)
 LINE DRAWING ALGORITHM
• ADVANTAGES OF BRESENHAMS ALGORITHM
• Includes only integers than float values.
• Can plot exact points with help of decision
parameter.
• DISADVANTAGES OF BRESENHAMS ALGORITHM
• More computation makes this algorithm slower.
• It is dependenton decision parameter consider
to position of points. the
 CIRCLE GENERATION ALGORITHM
• SYMMETRY OF CIRCLE
• A circle is a symmetrical figure.

• It has 8-way symmetry.

• So for circle generation algorithm takes advantage of

this symmetry and plots the 8 points.
 Y- axis

(x+1, y)
(x,y)

D
upper
dN
(x+1, y+1)

0 X- axis
D
23-07-2020 lower
dS
 CIRCLE GENERATION ALGORITHM
• BRESENHAMS CIRCLE GENERATION ALGORITHM

• ALGORITHM STEPS
1. Read the radius (r) of the circle
2. d = 3 – 2r [ Initial decision parameter]
3. x = 0, y = r [ initial starting point]
4. If (d < 0) , then d = d + 4x + 6, x = x+1, y = y
If (d > 0), then d = d + 4(x-y) + 10, x = x+1, y = y-1.
5. Check x >= y
6. Stop
 CIRCLE GENERATION ALGORITHM
• EXAMPLE 1 : Radius (r) = 10
• x = 0 and y = 10

• Initial decision parameter d = 3 -2r = 3 – 20 = -17

• If (d < 0) , then d = d + 4x + 6, x = x+1, y = y

• If (d > 0), then d = d + 4(x-y) + 10, x = x+1, y = y-1.

 𝑰𝒏𝒕𝒊𝒂𝒍 𝒅𝒆𝒄𝒊𝒔𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓 𝒅 =
-17
ITR (d < 0) , d = d + 4x + 6, x = x+1, y = y ITR (d > 0), d = d + 4(x-y) + 10
NO. NO.
1 -17 + 4(0) + 6 = -11 4 13 + 4 (3 - 9) + 10 = -1
2 -11 + 4(1) + 6 = -1 6 21 + 4(5 – 8) + 10 = 19
3 -1 + 4(2) + 6 = 13
5 -1 + 4(4) + 6 = 21
ITR No. d x y Plot (x,y)
0 -17 0 10 (0,10)
1 -11 1 10 (1,10)
2 -1 2 10 (2,10)
3 13 3 9 (3,9)
4 -1 4 9 (4,9)
5 21 5 8 (5,8)
6 19 6 7 (6,7)
7 35 7 6 (7,6)

x >= y

23-07-2020
 POLYGONS
• POLYGON
• It is a closed figure where the sides are all line segments.

• A polygon is usually named after how many sides it has.

• If a polygon has 5 sides it is called as

PENTAGON.
 POLYGONS
• TYPES OF POLYGONS
• There are 2 types of polygons

• CONVEX
• It is a polygon in which the linesegment joining
any two
points within the polygon lies completely inside the polygon.

• CONCAVE
• It is a polygon in which the linesegment joining
any two points within the polygon may not lie inside the
CONVEX
POLYGON

CONCAVE
POLYGON
 POLYGONS
• INSIDE OUT TEST

• EVEN ODD METHOD

• Construct a line segment between the point in question and a
point know to be outside the polygon.

• Count the number of intersection of the line segment with the

boundary.

• If the count is ODD then the point in question is INSIDE or else

OUTSIDE the polygon.
 POLYGONS
• It the intersection point is vertex of the polygon then look at
the other end points of the two segments which meet at the
vertex.

• If the point lies on the same side then it is calculated as EVEN.

• If the point lies on the opposite side then it is calculated as

ODD.
23-07-2020
 POLYGONS FILLING ALGORITHMS
• POLYGON FILLING
• Many closed figures are simple polygons.

• The simplest method of filling a polygon is to examine every pixel in the

raster to see if it is inside the polygon.

• Since most pixels is not inside the polygon, this technique is wasteful.

• So a bounding box can be used to reduced work.

• The bounding box is smallest rectangle that contains the polygon.

• Only those points inside the bounding box are examined.

 Problem with polygon filling

23-07-2020
 Polygon bounding box

Raster

Bounding Box

Polygon

23-07-2020
 POLYGONS FILLING ALGORITHMS
• Polygon filling algorithms are classified as

• SEED FILL ALGORITHM

• It is further classified as flood fill & boundary fill algorithm

• SCAN LINE ALGORITHM

 POLYGONS FILLING ALGORITHMS
• SEED FILL ALGORITHM – BOUNDARY FILL ALGORITHM
• In this algorithm the edges are drawn.

• Then a starting SEED (pixel) is chosen at any point inside the polygon.

• The neighbouring pixels are examined to check whether the boundary

pixel is reached.

• If the boundary pixels are not reached, pixels are highlighted and the
process is continued until boundary are reached.
 POLYGONS FILLING ALGORITHMS
• 4 connected and 8 connected regions
 POLYGONS FILLING ALGORITHMS
• If a region is 4-connected, the every pixel in the region can be
reached by a combination of moves in only 4 directions

– Left
– Right
– Up
– Down U

L R

D
 POLYGONS FILLING ALGORITHMS
• If a region is 8-connected, the every pixel in the
region is reached by a combination of moves in

– Two horizontal

– Two vertical

– Four diagonal direction

D1 V1 D4

H1 H2

D3 V2 D2
 POLYGONS FILLING ALGORITHMS
• 4 CONNECTED METHOD
 POLYGONS FILLING ALGORITHMS
• 8 CONNECTED METHOD
 POLYGONS FILLING ALGORITHMS
• SEED FILL ALGORITHM – FLOOD FILL ALGORITHM
• Flood fill algorithm focuses on different color for different pixel.

• It is not dependent of boundary color.

• This algorithm also starts with a SEED (pixel) and examines neighbouring
pixels.

• Here pixels are checked for a specified interior color instead of boundary
color and they are replaced with new color.
Sometimes we come across an object where we want to
fill the area and its boundary with different colors. We can
paint such objects with a specified interior color instead of
searching for particular boundary color as in boundary
filling algorithm.

Instead of relying on the boundary of the object, it relies on

the fill color. In other words, it replaces the interior color of
the object with the fill color. When no more pixels of the
original interior color exist, the algorithm is completed.
 POLYGONS FILLING ALGORITHMS
• SCAN LINE ALGORITHM
• This algorithm locates the intersection points on the polygon
for each scan line passing through the polygon.

• These intersection points are sorted from LEFT to RIGHT and

corresponding positions between each intersection pair are
set to specified fill color.
Find largest and smallest y-value and start working with largest y-value

23-07-2020
 EVEN – Same side of the scan line (SCAN LINE 3)

23-07-2020
ODD – Opposite side of the scan line (SCAN LINE 1 & 2)
 CHARACTER GENERATION METHODS
• There are 3 basic character generation methods

• STROKE METHOD
• Use small line segments to generate a character.

• Small series of line segments are drawn like strokes of a pen.

A
 CHARACTER GENERATION METHODS
• STARBURST METHOD
• A fixed pattern of linesegments are used to
generate
characters.
 CHARACTER GENERATION METHODS
• BITMAP METHOD
• It is also called as dot-matrix because in this method
characters are represented by an array of dots in the matrix
form.