COMPUTER GRAPHICS

Module 2B (Complete)
DR. PAYAL BOSE
Assistant Professor
Department of CSE
MODULE 2: GRAPHICS PRIMITIVES

2024 COMPUTER GRAPHICS 2

 Circle Drawing
Drawing a circle on the screen is a little complex than drawing a line.

• Basic Concept:
– In Cartesian Coordinate:
(𝒙 − 𝒂)𝟐 +(𝒚 − 𝒃)𝟐 = 𝒓𝟐 ,
where, r = radius of circle, a and
b is the coordinates of center.

Center of the
circle,
𝑎 = 0&𝑏 = 0

2024 COMPUTER GRAPHICS 3

• Symmetry Property of
y
Quadrant 1
Circle: Quadrant 2
(-x,y) octant1 (x,y)
octant8
– The shape of a circle -x, y x, y
y, x
is similar in each -y, x
octant7 octant2
quadrant -x x
octant3
octant6
– Sections in adjacent -y,-x
y,-x
x,-y
-x,-y
octants within one octant4
octant5
(x,-y)
quadrant are also (-x,-y)
Quadrant 4
Quadrant 3
-y
symmetric

2024 COMPUTER GRAPHICS 4

Circle Drawing Algorithms:

1. Midpoint Circle Drawing Algorithm

2. Bresenham Circle Drawing Algorithm

2024 COMPUTER GRAPHICS 5

❖Midpoint Circle Drawing Algorithm
Consider,
•Centre point of Circle = (𝑥0 , 𝑦0 )
•Radius of Circle = 𝑟

Step-1: Assign the starting point coordinates 𝒙𝟎 , 𝒚𝟎 𝒂𝒔: 𝒙𝟎 = 𝟎, 𝒚𝟎 = 𝒓

Step-2: Calculate the value of initial decision parameter 𝑷𝟎 as: 𝑷𝟎 = 𝟏 – 𝒓

Step-3: Suppose the current point is (𝒙𝒌 , 𝒚𝒌 ) and the next point is (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 )
Find the next point of the first octant depending on the value of decision parameter 𝑃𝑘 .
Follow the below two cases-

When 𝑷𝒌 < 𝟎 , 𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟐𝒙𝒌+𝟏 + 𝟏 When 𝑷𝒌 ≥ 𝟎

𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 𝑷𝒌+𝟏 = 𝑷𝒌 − 𝟐𝒙𝒌+𝟏 + 𝟐𝒚𝒌+𝟏 + 𝟏
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 − 𝟏
Step-4: Keep repeating Step-3 and Step-4 until 𝒙𝒌+𝟏 ≥ 𝒚𝒌+𝟏.
Step-5: If the given center point (𝒙𝟎 , 𝒚𝟎 ) is not (𝟎, 𝟎), then do the following and plot the
point-:- 𝒙𝒑𝒍𝒐𝒕 = 𝒙𝒄 + 𝒙𝟎 and 𝒚𝒑𝒍𝒐𝒕 = 𝒚𝒄 + 𝒚𝟎

2024 COMPUTER GRAPHICS 6

Given the center point coordinates (0, 0) and radius as 5, generate
all the points to form a circle.
𝒙𝟎 = 𝟎, 𝒚𝟎 = 𝟓
1. 𝒙𝟎 = 𝟎, 𝒚𝟎 = 𝒓 𝑃0 = 1 − 5 = −4 < 0 case 1 satisfied
2. decision
parameter 𝑷𝟎 as 𝑷𝒌 (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 ) 𝑷𝒌+𝟏
: 𝑷𝟎 = 𝟏 – 𝒓 (0,5) -4
3. current point is -4 (c-1) (1,5) -4+2.1+1 = -1
(𝒙𝒌 , 𝒚𝒌 ) and the next point
is (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 ) -1 (c-1) (2,5) -1+2.2+1 = 4
4 (c-2) (3,4) 4-2(3-4)+1 = 7
c-1, 𝑷𝒌 < 𝟎 , 𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟐𝒙𝒌+𝟏 + 𝟏 7 (c-2) (4,3) Algorithm
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌
terminates
c-2 𝑷𝒌 ≥ 𝟎
𝑷𝒌+𝟏 = 𝑷𝒌 − 𝟐𝒙𝒌+𝟏 + 𝟐𝒚𝒌+𝟏 + 𝟏
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 − 𝟏

4. Plot, 𝒙𝒌+𝟏 ≥ 𝒚𝒌+𝟏 (Terminate

condition) [Using Symmetric Property]

2024 COMPUTER GRAPHICS 7

 1st Octant 2nd Octant
Points Points

(0,5) (5,0)
(1,5) (5,1)
(2,5) (5,2)
(3,4) (4,3)

1st quadrant 2nd quadrant 3rd quadrant 4th quadrant

Points (x,y) Points (-x,y) points(-x,-y) Points

(0,5) (0,5) (0,-5) (0,-5)

(1,5) (-1,5) (-1,-5) (1,-5)
(2,5) (-2,5) (-2,-5) (2,-5)
(3,4) (-3,4) (-3,-4) (3,-4)
(5,0) (-5,0) (-5,0) (5,0)
(5,1) (-5,1) (-5,-1) (5,-1)
(5,2) (-5,2) (-5,-2) (5,-2)
(4,3) (-4,3) (-4,-3) (4,-3)
2024 COMPUTER GRAPHICS 8
Advantages of Mid Point Circle Drawing Algorithm-
The advantages of Mid Point Circle Drawing Algorithm are-
•It is a powerful and efficient algorithm.
•The entire algorithm is based on the simple equation of circle X2 + Y2 = R2.
•It is easy to implement from the programmer’s perspective.
•This algorithm is used to generate curves on raster displays.

Disadvantages of Mid Point Circle Drawing Algorithm-

The disadvantages of Mid Point Circle Drawing Algorithm are-
•Accuracy of the generating points is an issue in this algorithm.
•The circle generated by this algorithm is not smooth.
•This algorithm is time consuming.

2024 COMPUTER GRAPHICS 9

 ❖Bresenham Circle Drawing Algorithm
Consider,
•Centre point of Circle = (𝑥0 , 𝑦0 )
•Radius of Circle = 𝑟

Step-1: Assign the starting point coordinates 𝒙𝟎 , 𝒚𝟎 𝒂𝒔: 𝒙𝟎 = 𝟎, 𝒚𝟎 = 𝒓

Step-2: Calculate the value of initial decision parameter 𝑷𝟎 as: 𝑷𝟎 = 𝟑 – 𝟐𝒓

Step-3: Suppose the current point is (𝒙𝒌 , 𝒚𝒌 ) and the next point is (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 )
Find the next point of the first octant depending on the value of decision parameter 𝑃𝑘 .
Follow the below two cases-

When 𝑷𝒌 < 𝟎 , 𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟒𝒙𝒌+𝟏 + 𝟔 When 𝑷𝒌 ≥ 𝟎

𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟒(𝒙𝒌+𝟏 − 𝒚𝒌+𝟏 ) + 𝟏𝟎
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 − 𝟏
Step-4: Keep repeating Step-3 and Step-4 until 𝒙𝒌+𝟏 ≥ 𝒚𝒌+𝟏.
Step-5: If the given center point (𝒙𝟎 , 𝒚𝟎 ) is not (𝟎, 𝟎), then do the following and plot the
point-:- 𝒙𝒑𝒍𝒐𝒕 = 𝒙𝒄 + 𝒙𝟎 and 𝒚𝒑𝒍𝒐𝒕 = 𝒚𝒄 + 𝒚𝟎

2024 COMPUTER GRAPHICS 10

Given the centre point coordinates (0, 0) and radius as 8, generate all the
points to form a circle.

1. 𝒙𝟎 = 𝟎, 𝒚𝟎 = 𝒓 𝒙𝟎 = 𝟎, 𝒚𝟎 =
2. decision 𝑃0 = 3 − 2.8 = −13 < 0 case 1 satisfied
parameter 𝑷𝟎 as
: 𝑷𝟎 = 𝟑 – 𝟐𝒓 𝑷𝒌 (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 ) 𝑷𝒌+𝟏
3. current point is (0,8) -13
(𝒙𝒌 , 𝒚𝒌 ) and the next point -13 (c-1) (1,8) -13+4.1+6 = -3
is (𝒙𝒌+𝟏 , 𝒚𝒌+𝟏 )
-3 (c-1) (2,8) -3+4.2+6 = 11
C-1 𝑷𝒌 < 𝟎 , 𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟒𝒙𝒌+𝟏 + 𝟔 11 (c-2) (3,7) 11+4(3-7)+10 = 5
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌
5 (c-2) (4,6) 5+4(4-6)+10 = 7
C-2 𝑷𝒌 ≥ 𝟎 7 (c-2) (5,5) Algorithm terminate
𝑷𝒌+𝟏 = 𝑷𝒌 + 𝟒(𝒙𝒌+𝟏 − 𝒚𝒌+𝟏 ) + 𝟏𝟎
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝟏, 𝒚𝒌+𝟏 = 𝒚𝒌 − 𝟏

4. Plot, 𝒙𝒌+𝟏 ≥ 𝒚𝒌+𝟏 . [Using Symmetric

Property]

2024 COMPUTER GRAPHICS 11

 Quadrant- Quadrant- Quadrant- Quadrant-
1 (X,Y) 2 (-X,Y) 3 (-X,-Y) 4 (X,-Y)

(0, 8) (0, 8) (0, -8) (0, -8)

Octant- Octant-2
1 Points Points (1, 8) (-1, 8) (-1, -8) (1, -8)
(0, 8) (5, 5) (2, 8) (-2, 8) (-2, -8) (2, -8)
(1, 8) (6, 4) (3, 7) (-3, 7) (-3, -7) (3, -7)
(2, 8) (7, 3) (4, 6) (-4, 6) (-4, -6) (4, -6)
(3, 7) (8, 2) (5, 5) (-5, 5) (-5, -5) (5, -5)
(4, 6) (8, 1) (6, 4) (-6, 4) (-6, -4) (6, -4)
(5, 5) (8, 0) (7, 3) (-7, 3) (-7, -3) (7, -3)
(8, 2) (-8, 2) (-8, -2) (8, -2)
(8, 1) (-8, 1) (-8, -1) (8, -1)
(8, 0) (-8, 0) (-8, 0) (8, 0)

2024 COMPUTER GRAPHICS 12

Advantages
•It is a simple algorithm.
•It can be implemented easily
•It is totally based on the equation of circle i.e. x2 +y2 =r2
Disadvantages
•There is a problem of accuracy while generating points.
•This algorithm is not suitable for complex and high graphic
images.

2024 COMPUTER GRAPHICS 13

 Fill Area Primitives
- Filled Area primitives are used to filling solid colors to an AREA OR POLYGON.
- Filling the polygon means highlighting its pixel with different solid colors.

Polygon Filling
Fill Area Primitives Area Filling

Seed Fill Algorithm Scan Fill Algorithm

(when a point is selected inside the polygon) Used to fill the polygon
– Flood Fill using colors by scanning
(when an area has multiple boundaries) horizontal lines

– Boundary Fill
(used to trace the boundary region)

2024 COMPUTER GRAPHICS 14

 Polygon Filling
Polygon is an ordered list of vertices as shown in
the following figure.
Polygon
Polygon filling algorithms:-

• Scan line polygon filling algorithm

• Boundary filling algorithm

• Flood filling algorithm

➢ Two basic concepts are adopted to determine connected points in a

polygon while coloring (used in last 2 fill methods)

• 4-connectivity method

• 8-connectivity method
2024 COMPUTER GRAPHICS 15
 Scanline Algorithm for Polygon Area Filling

1. Find 𝑦𝑚𝑖𝑛 and 𝑦𝑚𝑎𝑥 for the polygon Y

𝒚𝒎𝒂𝒙 p4 p5
2. Consider all the scan-lines from: 𝑦𝑚𝑎𝑥 to 𝑦𝑚𝑖𝑛
p0 p1 p2 p3
(SL1 and SL2 two arbitrary scan-line) SL1
SL2
3. For each scan-line 𝒚𝒎𝒊𝒏
• Store all the intersection points of the polygon
with the scan-line 𝑥𝑚𝑎𝑥 𝑥𝑚𝑖𝑛 X

• Sort the points in ascending order of X Polygon to be colored

coordinate values
• Color all the pixels along a pair of contiguous
intersecting points if the pixels lie within the
polygon (Ex. – Color all points between p0 & p1
; do not color from p1 to p2)
2024 COMPUTER GRAPHICS 16
How to identify the pair of intersecting points is INSIDE or OUTSIDE of the
polygon (which pair to be colored through) ?

INSIDE or OUTSIDE Rules:

• Odd-even rule
• Non-zero winding number rule

Odd-even rule
– Color only the odd pairs and do not
color the even pairs From the above figure, we can see
that from the point (𝑥, 𝑦) the number
– All pixels along odd pair are interior
of interactions point on the left side is
pixels 5 and on the right side is 3. From both
ends, the number of interaction points
– All pixels along even pair are is odd, so the point is considered
within the object.
exterior pixels
2024 COMPUTER GRAPHICS 17
Non-zero winding number rule
• Give directions to all the edges of a polygon (in cyclic order)
• Assign 1 to all edges going upwards and downward edges as (-1)
• Inside/outside test for a point can be performed by summing up the
values of all the intersecting edges by a scan-line drawn from the Y-axis to
the candidate point
− Sum non-zero sum signifies interior point
− Sum zero means exterior point

SL = Scan Line; P = Point

𝐏 = 𝟏 + −𝟏 + 𝟏 = 𝟏 P
SL
𝑃 = 𝑁𝑜𝑛 𝑍𝑒𝑟𝑜
⇒ 𝑃 𝑖𝑠 𝐼𝑛𝑡𝑒𝑟𝑖𝑜𝑟 𝑃𝑜𝑖𝑛𝑡

2024 COMPUTER GRAPHICS 18

 Boundary Fill and Flood Fill
Boundary Fill
• This algorithm picks a point inside an object and starts to fill until it hits the
boundary of the object. The color of the boundary and the color that we fill should
be different for this algorithm to work.
• In this algorithm, that color of the boundary is same for the entire object.

Flood Fill
• This algorithm is needed to fill the area of an object and its boundary with
different colors.
• can paint such objects with a specified interior color instead of searching for
particular boundary color as in boundary filling algorithm.

• 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.

2024 COMPUTER GRAPHICS 19

 Pixel Connectivity

4-connectivity (of a pixel) 8-connectivity (of a pixel)

2024 COMPUTER GRAPHICS 20

Practice Problems

2024 COMPUTER GRAPHICS 21

 Numerical Practice Problems
1. Given the center point coordinates (0, 0) and radius as 8, generate all the
points to form a circle using Midpoint Circle Drawing Algorithm. Draw the
circle.
2. Given the center point coordinates (4, -4) and radius as 10, generate all
the points to draw a circle using Midpoint Circle Drawing Algorithm.

3. Draw a circle using Bresenham Circle Drawing algorithm with center point
(0,0) and radius is 15.
4. Draw a circle using Bresenham Circle Drawing algorithm with center point
(10, 10) and radius is 10.

2024 COMPUTER GRAPHICS 22

 Probable Theoretical Problems

1. What do you mean by Fill area primitives? Types of Fill area primitives.
2. Write down the name of Polygon Filling algorithm.
3. What type of connectivity used in filling algorithms. Describe them briefly.
4. What is Scanline algorithm for polygon filling.
5. How to identify if a pair of points are inside or outside the polygon or not.
6. Briefly describe Inside and Outside Rules with example.
7. Briefly describe Boundary Fill and Flood Fill algorithm.

2024 COMPUTER GRAPHICS 23

2024 COMPUTER GRAPHICS 24