Circle Drawing

Spiral Drawing
Ellipse Drawing

CS335 Computer Graphics

Circle and Ellipse Drawing Algorithms

Dr. Sambit Bakshi

Computer Science & Engineering, NIT Rourkela

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Spiral Drawing
Ellipse Drawing

Table of contents

1 Circle Drawing
Circle Drawing
Midpoint Circle Drawing Algorithm

2 Spiral Drawing
Spiral Drawing

3 Ellipse Drawing
Ellipse Drawing
Midpoint Ellipse Drawing Algorithm

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Equation of a circle

General circle drawing problem: parameters are center and

radius
(x xc )2 + (y yc )2 = r 2

y = yc r 2 (xc x)2

x = xc r 2 (yc y )2
Creates uneven spacing if plotted!!!

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Drawing a circle

Figure: Plot with Figure: Plot with

y = f (x) = yc r 2 (xc x)2 x = f (y ) = xc r 2 (yc y )2

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Drawing a circle

How to eliminate uneven spacing?

parametric polar form:
x = xc + r cos
y = yc + r sin

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Drawing a circle

How to vary ?
We are aiming to plot
4r 4 points
Step size for varying
is 2/4(r 1)
Computation can be
reduced by exploiting
symmetry

Figure: Parametric circle drawing

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Drawing a circle

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Drawing a circle

y = yc r 2 (xc x)2

x = xc r 2 (yc y )2
Uneven plotting wont be there if we plot 1/8th of a circle!
Each pixel computation would need 3 addition (or
subtraction) and 3 exponentiation (or root) operation

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Midpoint Circle Drawing

fcircle = x 2 + y 2 r 2
Without loss of generalization, we consider center at (0, 0)

< 0; if (x, y ) is inside the boundary
fcircle (x, y ) = = 0; if (x, y ) is on the boundary
> 0; if (x, y ) is outiside the boundary

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter

Assuming (xk , yk ) is plotted, we want to plot (xk+1 , yk+1 )

Without loss of generalization, we consider xk+1 = xk + 1
and we check if yk+1 = yk or yk+1 = yk 1
pk
= fcircle (xk + 1, yk 12 )
= (xk + 1)2 + (yk 12 )2 r 2

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter

pk+1
= fcircle (xk+1 + 1, yk+1 12 )
= [(xk + 1) + 1]2 + (yk+1 12 )2 r 2
2
pk+1 = pk + 2(xk + 1) + (yk+1 yk2 ) (yk+1 yk ) + 1

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter

2
pk+1 = pk + 2(xk + 1) + (yk+1 yk2 ) (yk+1 yk ) + 1
When pk was negetive, i.e. yk+1 = yk , pk+1 = pk + 2xk+1 + 1
When pk was positive, i.e. yk+1 = yk + 1,
pk+1 = pk + 2xk+1 + 1 2yk+1
Evaluation of xk+1 and yk+1 can be done as follows:
2xk+1 = 2xk + 2 and 2yk+1 = 2yk 2 when we start from
(0, r ) and move towards ( r 2 , r 2 )

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Finding p0 and halting the algorithm

p0
= fcircle (1, r 21 )
= 12 + (r 12 )2 r 2
= 54 r
= 1 r (rounding p0 for an integer value of r )
Starting from (0, r ), stop when x > y

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Circle drawn on a quadrant

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Midpoint circle drawing algorithm

1 Input: r
2 (x0 , y0 ) (0, r )
3 Load (x0 , y0 )
4 p0 (1 r )
5 k0
6 if (pk < 0)
xk+1 xk + 1, yk+1 yk , Load (xk + 1, yk )
pk+1 pk + 2xk+1 + 1 OR pk+1 pk + 2xk + 3
7 Otherwise
xk+1 xk + 1, yk+1 yk 1, Load (xk + 1, yk 1)
pk+1 pk + 2xk+1 + 1 2yk+1 OR pk+1 pk + 2xk + 5 2yk
8 k (k + 1)
9 Repeat steps 6,7,8 while xk yk

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

A simple example by MCD

Find the coordinate of raster points on the circle

with r = 10 having center at (3, 4)

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

A simple example by MCD

k pk xk+1 yk+1 2xk+1 2yk+1

- - 0 10 0 20
p0 = 1 10 = 9 0 -9 1 10 2 20
(x0 , y0 ) (0, 10) 1 -6 2 10 4 20
2x0 = 0 2 -1 3 10 6 20
2y0 = 20 3 6 4 9 8 18
4 -3 5 9 10 18
5 8 6 8 12 16
6 5 7 7 14 14

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

A simple example by MCD

x y x + xc y + yc
0 10 3 14
1 10 4 14
Shifting center 2 10 5 14
at (3, 4) 3 10 6 14
4 9 7 13
5 9 8 13
6 8 9 12
7 7 10 11

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Circle Drawing
Spiral Drawing
Midpoint Circle Drawing Algorithm
Ellipse Drawing

Midpoint Circle Drawing

What would happen if we do not stop at xk+1 = yk+1 ?

If we dont consider the computation, would the answer be
correct? NO
WHY? because our decision parameter pk is designed to
check inclusion or exclusion of the midpoint along y axis and
not along x axis, which role is reversed once we cross x = y

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Spiral Drawing Spiral Drawing
Ellipse Drawing

Spiral Drawing

Can a spiral be drawn based on any circle drawing

algorithm?

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Spiral Drawing Spiral Drawing
Ellipse Drawing

Spiral Drawing

x = xc + r cos
y = yc + r sin
(router rinner )
r = 2 keeps on recomputed as intermediate value
of r
How to vary ?
We aim to plot 4r 4 points for a circle with radius r
Step size for varying is 2/4(r 1)

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Equation of an ellipse

General ellipse drawing problem: parameters are center and

radius along x and y axes
y yc 2
( xxc 2
rx ) + ( ry ) = 1
r
y = yc ryx rx2 (xc x)2

x = xc rryx ry2 (yc y )2
Creates uneven spacing if plotted!!!

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Drawing an ellipse

How to eliminate uneven spacing?

parametric polar form:
x = xc + rx cos
y = yc + ry sin

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Drawing an ellipse

How to vary ?
We are aiming to plot p = max(4rx 4, 4rx 4) points
Step size for varying is 2/p
Computation can be reduced by exploiting symmetry

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Rationally choosing the independent axes

Figure: Rationally choosing the independent axes

Dr. Sambit Bakshi CS335 Computer Graphics
 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Midpoint Ellipse Drawing

fellipse = ry2 x 2 + rx2 y 2 rx2 ry2

Without loss of generalization, we consider center at (0, 0)

< 0; if (x, y ) is inside the boundary
fellipse (x, y ) = = 0; if (x, y ) is on the boundary
> 0; if (x, y ) is outiside the boundary

dy 2r 2 x
Slope of ellipse at (x, y ) = dx = 2ry2 y
x

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Midpoint Ellipse Drawing

The algorithm starts from (0, ry )

(slope = 0)
We move towards (rx , 0) (slope =
)
We move from Region 1 to 2 when
dy 2r 2 x
dx
= 2ry2 y 1, i.e. ry2 x rx2 y
x
Midpoint parameters are formed in
dierent way in two regions
Region 1: Change in x > Change in
y
Region 2: Change in y > Change in
x
Figure: Rationally choosing the
independent axes

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter in Region 1

Assuming (xk , yk ) is plotted, we

want to plot (xk+1 , yk+1 )
We consider xk+1 = xk + 1
and we check if yk+1 = yk or
yk+1 = yk 1
p1k
= fellipse (xk + 1, yk 21 )
= ry2 (xk + 1)2 + rx2 (yk 12 )2 rx2 ry2

Figure: Decision parameter in

Region 1

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter in Region 1

p1k
= fellipse (xk + 1, yk 21 )
= ry2 (xk + 1)2 + rx2 (yk 12 )2 rx2 ry2
p1k+1
= fellipse (xk+1 + 1, yk+1 12 )
=
ry2 [(xk +1)+1]2 +rx2 (yk+1 21 )2 rx2 ry2
p1k+1
= p1k + 2ry2 (xk + 1) + ry2 +
rx2 [(yk+1 21 )2 (yk 21 )2 ]
IF p1k < 0
yk+1 = yk
p1k+1 = p1k + 2ry2 xk+1 + ry2
OTHERWISE
yk+1 = yk 1 Figure: Decision parameter in
p1k+1 = p1k +2ry2 xk+1 +ry2 2rx2 yk+1 Region 1

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding p10

p10
= fellipse (1, ry 21 )
= ry2 + rx2 (ry 12 )2 rx2 ry2
rx2
= ry2 rx2 ry + 4

Figure: Decision parameter in

Region 1

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter in Region 2

Assuming (xk , yk ) is plotted, we

want to plot (xk+1 , yk+1 )
We consider yk+1 = yk 1
and we check if xk+1 = xk or
xk+1 = xk + 1
p2k
= fellipse (xk + 21 , yk 1)
= ry2 (xk + 12 )2 + rx2 (yk 1)2 rx2 ry2

Figure: Decision parameter in

Region 2

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding Decision Parameter in Region 2

p2k
= fellipse (xk + 21 , yk 1)
= ry2 (xk + 12 )2 + rx2 (yk 1)2 rx2 ry2
p2k+1
= fellipse (xk+1 + 12 , yk+1 1)
=
ry2 (xk+1 + 12 )2 +rx2 [(yk 1)1]2 rx2 ry2
p2k+1
= p2k 2rx2 (yk 1) + rx2 +
ry2 [(xk+1 + 21 )2 (xk + 21 )2 ]
IF p2k > 0
xk+1 = xk
p2k+1 = p2k 2rx2 yk+1 + rx2
OTHERWISE
xk+1 = xk + 1 Figure: Decision parameter in
p2k+1 = p2k 2rx2 yk+1 +rx2 +2ry2 xk+1
Region 2

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Finding p20

p20
= fellipse (x0 + 21 , y0 1)
= ry2 (x0 + 12 )2 + rx2 (y0 1)2 rx2 ry2
(x0 , y0 ) is the last point of Region 1.

rx4 ry4
(x0 , y0 ) = ( r 2 +r 2
, r 2 +r 2
)
x y x y

Figure: Decision parameter in

Region 2

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

Midpoint ellipse drawing algorithm

1 Input: rx , ry 10 (x0 , y0 ) (xk , yk )

2 (x0 , y0 ) (0, ry ) 11 Load (x0 , y0 )
3 Load (x0 , y0 ) 12 p20
4 p10 ry2 rx2 ry + rx2 /4 ry2 (x0 + 1/2)2 + rx2 (y0 1)2 rx2 ry2
5 k0 13 k0
6 if (p1k < 0) 14 if (p2k > 0)
xk+1 xk + 1, yk+1 yk , xk+1 xk , yk+1 yk 1,
Load (xk + 1, yk ) Load (xk , yk 1)
p1k+1 = p1k + 2ry2 xk+1 + ry2 p2k+1 = p2k 2rx2 yk+1 + rx2
7 Otherwise 15 Otherwise
xk+1 xk + 1, yk+1 yk 1, xk+1 xk + 1, yk+1 yk 1,
Load (xk + 1, yk 1) Load (xk + 1, yk 1)
p1k+1 = p1k +2ry2 xk+1 +ry2 2rx2 yk+1 p2k+1 = p2k 2rx2 yk+1 +rx2 +2ry2 xk+1
8 k (k + 1) 16 k (k + 1)
9 Repeat steps 6,7,8 while ry2 xk rx2 yk 17 Repeat steps 14,15,16 while yk > 0

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

A simple example by MED

Find the coordinate of raster points on the ellipse

with rx = 8 and ry = 6 having center at (0, 0)

Dr. Sambit Bakshi CS335 Computer Graphics

 Circle Drawing
Ellipse Drawing
Spiral Drawing
Midpoint Ellipse Drawing Algorithm
Ellipse Drawing

A simple example by MED

p0 = 62 82 6+ 14 82 = 332 k p1k xk+1 yk+1 2ry2 xk+1 2rx2 yk+1

0 -332 1 6 72 768
1 -224 2 6 144 768
2 -44 3 6 216 768
(x0 , y0 ) (0, 6) for Region 1. 3 208 4 5 288 640
We move out of Region 1 at 4 -108 5 5 360 640
5 288 6 4 432 512
k=6 as 2ry2 xk+1 > 2rx2 yk+1 .
6 244 7 3 504 384
The last point of Region 1 is
(7, 3).
k p2k xk+1 yk+1 2ry2 xk+1 2rx2 yk+1
0 -151 8 2 576 256
(x0 , y0 ) (7, 3) for Region 2. 1 -233 8 1 576 128
p20 = f (7+0.5, 31) = 151 2 745 8 0
We stop when y = 0

Dr. Sambit Bakshi CS335 Computer Graphics