Computer Science III B.

Sc CS Sem : VI Year 2019 - 2020

Subject: Graphics and Multimedia

Google Classroom : oefqdki Subject code: 63A

Output Primitives
Unit 1: Circle Generating Algorithm
Dr.M.Manimaran,
Associate Professor,
Department Computer Science,
oefqdki - Graphics & Multimedia
SKACAS
Unit I Output Primitives 1
 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

SNAP TALK / ATTENDANCE

oefqdki - Graphics & Multimedia Unit I Output Primitives 2

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Lecture Agenda
• Circle Generating Algorithms
– Properties of Circles
– Mid-Point Algorithm

oefqdki - Graphics & Multimedia Unit I Output Primitives 3

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

EXPECTED OUTCOME
After studying this class, you should be able
to:
• To understand the concepts of Circle
Generating Algorithms
• To understand the concepts of Properties of
Circles
• To understand the concepts of Mid-Point
Algorithm

oefqdki - Graphics & Multimedia Unit I Output Primitives 4

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Circle Generating Algorithms

• A circle is defined as the set of points that are all at a given
distance r from a center point (xc, yc).

• For any circle point (x, y), this distance is expressed by the
Equation
(x − xc)2 + (y − yc)2 = r 2
• We calculate the points by stepping along the x-axis in unit
steps from xc-r to xc+r and calculate y values as

oefqdki - Graphics & Multimedia Unit I Output Primitives 5

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Circle Generating Algorithms

• There are some problems with this approach:
1. Considerable computation at each step.
2. Non-uniform spacing between plotted pixels as in this
Figure.

oefqdki - Graphics & Multimedia Unit I Output Primitives 6

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Circle Generating Algorithms

• Problem 2 can be removed using the polar form:
x = xc + r cos θ
y = yc + r sin θ

• using a fixed angular step size, a circle is plotted with

equally spaced points along the circumference.

oefqdki - Graphics & Multimedia Unit I Output Primitives 7

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Circle Generating Algorithms

• Problem 1 can be overcome by considering the symmetry of
circles as in Figure 3.
• But it still requires a good deal of computation time.

• Efficient Solutions
– Midpoint Circle Algorithm

oefqdki - Graphics & Multimedia Unit I Output Primitives 8

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• To apply the midpoint method, we define a circle
function:

• Any point (x,y) on the boundary of the circle with

radius r satisfies the equation fcircle(x, y)= 0.

oefqdki - Graphics & Multimedia Unit I Output Primitives 9

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• If the points is in the interior of the circle, the circle
function is negative.
• If the point is outside the circle, the circle function is
positive.
• To summarize, the relative position of any point (x,y)
can be determined by checking the sign of the circle
function:

oefqdki - Graphics & Multimedia Unit I Output Primitives 10

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• The circle function tests in (3) are performed for the mid
positions between pixels near the circle path at each
sampling step.
• Thus, the circle function is the decision parameter in the
midpoint algorithm, and we can set up incremental
calculations for this function as we did in the line
algorithm.

oefqdki - Graphics & Multimedia Unit I Output Primitives 11

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• Figure 4 shows the midpoint between the two candidate
pixels at sampling position xk +1.
• Assuming we have just plotted the pixel at (xk , yk), we
next need to determine whether the pixel at position (xk
+1, yk) or the one at position (xk +1, yk −1) is closer to the
circle.

oefqdki - Graphics & Multimedia Unit I Output Primitives 12

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• Our decision parameter is the circle function (2)
evaluated at the midpoint between these two pixels:

oefqdki - Graphics & Multimedia Unit I Output Primitives 13

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• If pk < 0, this midpoint is inside the circle and the
pixel on scan line yk is closer to the circle boundary.
• Otherwise, the midpoint is outside or on the circle
boundary, and we select the pixel on scan line yk −1.
• Successive decision parameters are obtained using
incremental calculations.

oefqdki - Graphics & Multimedia Unit I Output Primitives 14

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• We obtain a recursive expression for the next decision parameter by
evaluating the circle function at sampling position xk+1 +1 = xk +
2

• where yk+1 is either yk or yk-1,depending on the sign of pk.

oefqdki - Graphics & Multimedia Unit I Output Primitives 15
 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• Increments for obtaining pk+1 are either
– 2xk+1 +1 (if pk is negative) or
– 2xk+1 +1− 2yk+1 (if pk is positive)
• Evaluation of the terms 2xk+1 and 2yk+1 can also be
done incrementally as:

oefqdki - Graphics & Multimedia Unit I Output Primitives 16

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• At the start position (0, r), these two terms (2x, 2y)
have the values 0 and 2r, respectively.
• Each successive value is obtained by adding 2 to the
previous value of 2x and subtracting 2 from the
previous value of 2y.

oefqdki - Graphics & Multimedia Unit I Output Primitives 17

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• The initial decision parameter is obtained by
evaluating the circle function at the start position (x0 ,
y0)=(0, r):

oefqdki - Graphics & Multimedia Unit I Output Primitives 18

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Mid point Circle Algorithm

• If the radius r is specified as an integer, we can
simply round p0 to

• since all increments are integers.

oefqdki - Graphics & Multimedia Unit I Output Primitives 19

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Summary of the Algorithm

• As in Bresenham’s line algorithm, the midpoint
method calculates pixel positions along the
circumference of a circle using integer additions and
subtractions, assuming that the circle parameters are
specified in screen coordinates.
• We can summarize the steps in the midpoint circle
algorithm as follows.

oefqdki - Graphics & Multimedia Unit I Output Primitives 20

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Algorithm

oefqdki - Graphics & Multimedia Unit I Output Primitives 21

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Example
• Given a circle radius r = 10, we demonstrate the
midpoint circle algorithm by determining positions
along the circle octant in the first quadrant from x = 0
to x = y .
• The initial value of the decision parameter is

oefqdki - Graphics & Multimedia Unit I Output Primitives 22

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Example
• For the circle centered on the coordinate origin, the
initial point is (x0 , y0) =(0,10), and initial increment
terms for calculating the decision parameters are

• Successive decision parameter values and positions

along the circle path are calculated using the midpoint
method as shown in the table.

oefqdki - Graphics & Multimedia Unit I Output Primitives 23

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Example

oefqdki - Graphics & Multimedia Unit I Output Primitives 24

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Example
• A plot of the generated pixel positions in the first
quadrant is shown in Figure 5.

oefqdki - Graphics & Multimedia Unit I Output Primitives 25

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Key Points
• Properties of Circles
• Symmetry of a circle
• Midpoint Circle Algorithm

Next Lecture
• Ellipse-Generating Algorithms

oefqdki - Graphics & Multimedia Unit I Output Primitives 26

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

One marks
1)A circle is defined as the set of points that are all at a
given distance r from a center point________

oefqdki - Graphics & Multimedia Unit I Output Primitives 27

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

One marks
2) As in Bresenham’s line algorithm, the midpoint
method calculates pixel positions along the _______

oefqdki - Graphics & Multimedia Unit I Output Primitives 28

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

One marks
3) Successive decision parameters are obtained
using________

oefqdki - Graphics & Multimedia Unit I Output Primitives 29

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

One mark ANSWERS

1) (xc, yc).
2) circumference of a circle
3) incremental calculations.

oefqdki - Graphics & Multimedia Unit I Output Primitives 30

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

VIDEO URL

https://www.youtube.com/watch?v=yfLm9nXsCv
w

oefqdki - Graphics & Multimedia Unit I Output Primitives 31

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

One mark URL

https://www.sanfoundry.com/computer-graphics-
mcqs-line-filling-algorithms/

oefqdki - Graphics & Multimedia Unit I Output Primitives 32

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

Next Lecture
Attributes of Output Primitives

oefqdki - Graphics & Multimedia Unit I Output Primitives 33

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

DISCUSSIONS

oefqdki - Graphics & Multimedia Unit I Output Primitives 34

 Computer Science III B.Sc CS Sem : VI Year 2019 - 2020

oefqdki - Graphics & Multimedia Unit I Output Primitives 35