Computer Graphics

CS 010 703

Module - II (2D Graphics)

 Output Primitives
 Line Drawing Algorithms
 Circle Drawing Algorithms
Output primitives
Description of pictures
Specified by a set of intensities for the pixel positions.
Describe it as a set of complex objects, such as trees,
furniture and walls, positioned at specific coordinate
locations within the scene.
Output Primitives...
• Output primitives - Basic geometric structures.
•Graphics programming packages provide functions to describe
a scene in terms of basic geometric structures referred to as
output primitives and to group sets of o/p primitives into more
complex structures.
• Each output primitive is specified with the input coordinate data
and other information about the way that object is to be
displayed.
• Points
• Straight lines
• Circles
• Spline curves and surfaces
• Polygon color areas
• Character strings , etc.
Displaying Picture
• The raster grid consists of discrete cells called pixels which are
referenced by integer screen coordinates.
• In order to display a geometric primitive, the intensities of pixels very
close to the desired primitive are loaded into the frame buffer in the
form of bits.
• The bits corresponding to each pixel are converted into analog values,
which illuminate phosphor dots representing the pixels on the raster
grid.
• The coordinates of actual points on any primitive need not be integers
whereas we require the integer coordinates.

• Rasterization - Process of determining which pixels give the best

approximation to a desired line on the screen.
• Scan Conversion - Digitizing a picture definition given in an
application program into a set of pixel intensity values for storage in
the frame buffer.
Displaying Picture...
• Points- Point plotting is accomplished by converting a single
coordinate position in an application program into appropriate
operations for the output device in use.

• Line- Line drawing is accomplished by calculating

intermediate positions along the line path between 2 specified
end point positions. The output device is directed to fill these
positions between the end points.
Implementing Application Programs
Description of objects in terms of primitives and
attributes and converts them to the pixels on the screen.
Primitives – what is to be generated
Attributes – how primitives are to be generated
Points
(0,0)

CRT

(maxx,maxy)

The electron beam is turned on to illuminate the phosphor

at the selected location (x, y) where
0 ≤ x ≤ maxx
0 ≤ y ≤ maxy
 setpixel(x, y, intensity) – loads an intensity value into the
frame-buffer at (x, y).
 getpixel(x, y) – retrieves the current frame-buffer intensity
setting at position (x, y).
Lines
Analog devices, such as a random-scan display or a vector
plotter, display a straight line smoothly from one endpoint to
another. Linearly varying horizontal and vertical deflection
voltages are generated that are proportional to the required
changes in the x and y directions to produce the smooth line.
Digital devices display a straight line by plotting discrete coordinate
points along the line path which are calculated from the equation of
the line.
Screen locations are referenced with integer values, so plotted
positions may only approximate actual line positions between two
specific endpoints.
A computed line position of (10.48, 20.51) will be converted to pixel
position (10, 21). This rounding of coordinate values to integers
causes lines to be displayed with a stairstep appearance ( “jaggies”).
Particularly noticeable on systems with low resolution.
To smooth raster lines, pixel intensities along the line paths must be
adjusted.
Line Drawing Algorithms

Cartesian equation:
y = mx + b
y2
where y1

m – slope x1 x2

b – y-intercept

y 2− y 1 Δy
m= =
x 2 − x 1 Δx
Slope
+ve -ve
if |m| = 1
 = 45° 45°
45°

if |m|  1
-45° <  < 45°
°
°

if |m|  1
45° <  < 90° or
°
-90° <  < -45° outside
°
11
Straight line segment with 5 sampling positions
along the x axis and y axis

y2

y1

x1 x2
The Cartesian slope intercept equation for straight line is
y = m x + b  (1)
(x1,y1) & (x2,y2) be the two endpoints of the line, then
y1 = mx1 + b  (2) y2 = mx2 + b  (3)
Eqn(3) – (2)  ( y2 – y1) = m (x2 – x1)
m = (y2-y1)/(x2-x1)
m = ∆y/ ∆x
For any given x interval (∆x) along a line, compute the
corresponding y interval (∆y) as ∆y = m ∆x
Similarly the x interval (∆x) is obtained as ∆x = ∆y /m
The above equations form the basis for determining deflection
voltages in analog devices.
Digital Differential Analyzer Algorithm(DDA)
Scan conversion algorithm based on calculating either ∆x or ∆y.
Sample the line at unit intervals in one coordinate and determine
the corresponding integer values nearest the line path for the
other coordinate. (Left to right)
Case 1:
Line with positive slope less than or equal to 1 (m <=1),
we sample at unit x intervals (∆x =1) and determine the successive
y value as
∆y = m ∆x
yk+1- yk = m ∆x
yk+1 = yk + m yk+1- yk = m (∆x =1)
k takes integer values starting from 1 and increases by 1 until the
final point is reached.
m can be any number between 0 and 1.
Calculated y values must be rounded off to the nearest integer
Case 2:
For lines with positive slope greater than 1 (m>1) , sample
at unit y intervals (∆y = 1) and calculate each successive x value as

xk+1= xk + 1/m ∆y = m ∆x
∆x = ∆y/m
xk+1- xk = ∆y/m
xk+1- xk = 1/m (∆y =1)
Equations used when lines are processed from (right to left)
1. (m <= 1) ∆x = -1 & yk+1 = yk – m
2. (m > 1) ∆y = -1 & xk+1 = xk – 1/m
|m| = 1
y=x
m=1
c=0 y
x y 8 
0 0 7 
1 1 6 

2 2 5 
4 
3 3
3 
4 4
2 
5 5
1 
6 6
0 
7 7 0 1 2 3 4 5 6 7 8 x
8 8
16
|m |  1
y=½x+1
m=½
y
c=1
8
x y round(y)
7
0 1 1 6
1 1.5 2 5  
2 2 2 4  
3 2.5 3 3  
4 3 3 2  
5 3.5 4 1 
6 4 4 0

7 4.5 5 0 1 2 3 4 5 6 7 8 x
8 5 5 17
The DDA Method
Uses differential equation of the line : m
If slope |m|  1 then increment x in steps of 1 pixel and
find corresponding y-values.
If slope |m|  1 then increment y in steps of 1 pixel and
find corresponding x-values.




  
  
  
  
19
step through in x step through in y
The DDA Approach

Desired line

(xi+1,round(yi+m))

(xi,yi) (xi+1,yi+m)

(xi,round(yi))

20
Steps for DDA Algorithm
1. Accept as input the two end point pixel positions.
P1(xa , ya) P2 (xb , yb)
2. Horizontal and vertical differences between the endpoint
positions are computed & assigned to two parameters
namely dx and dy.
dx= xb – xa, dy = yb – ya,
3. If abs(dx) >abs(dy) ,then steps =abs( dx)
else steps =abs( dy)
4. xincr = dx/steps yincr = dy/steps
(if steps = abs(dx) , xincr = 1, yincr = dy/dx = m)
(if steps = abs(dy) , yincr = 1, xincr = dx/dy = 1/m)
5. Assign x = xa and y = ya
6. Plot (x, y)
7. x= x + xincr & y= y + yincr
8. Loop through 6 and 7 steps times.
DDA Algorithm
Advantages
• It is simple and easy to implement algorithm
• DDA algorithm is a faster method for calculating pixel positions
than the direct use of line equation y= mx+b.
• It eliminates multiplication by making use of raster characteristics,
incremental operations

Disadvantages
• DDA algorithm runs slowly because it requires real arithmetic
(floating point operations) and rounding operations.
• Rounding off errors
• As it is orientation dependent, so it has poor endpoint accuracy.
• Due to the limited precision in the floating point representation it
produces cumulative error.
void LineDDA(int x0, int y0, int x1, int y1)
{
int dx = x1 – x0, dy = y1 – y0, steps;

if (abs(dx)>abs(dy)) steps = abs(dx);

else steps = abs(dy);

// one of these will be 1 or -1

double xIncrement = (double)dx / (double )steps;
double yIncrement = (double)dy / (double )steps;

double x = x0;
double y = y0;
setPixel(round(x), round(y),1);

for (int i=0; i<steps; i++)

{
x += xIncrement;
y += yIncrement;
setPixel(round(x), round(y),1);
} Note: The DDA algorithm is faster than the direct use of y = mx + c. 25
} It eliminates multiplication; only one addition.
Bresenham’s Line Algorithm

The Bresenham line algorithm is an

incremental scan conversion algorithm

Advantages
-uses only integer calculations
- more efficient
Jack Bresenham worked
for 27 years at IBM
before entering
academia. Bresenham
developed his famous
algorithms at IBM in the
early 1960s
Bresenham’s Line Algorithm

Basis of the algorithm:

- From start position decide A or B next

A
B

Start position

27
The Big Idea
Note: Move across the x axis in unit intervals and at each
step choose between two different y coordinates

Eg. From position (2, 3) have

5 to choose between (3, 3) and
(xk+1, yk+1) (3, 4) :- point that is closer to
4 original line
(xk, yk)
3
(xk+1, yk)

2 3 4 5
Deriving Bresenham’s Line Algorithm
At sample position xk+1 the vertical yk+1
separations from the mathematical line dupper
are labelled dupper and dlower y
dlower
The y coordinate on the mathematical yk
line at xk+1 is:
y  m( xk  1)  b
So, dupper and dlower are given as: xk+1
d lower  y  yk
 m( xk  1)  b  yk
and:
d upper  ( yk  1)  y
 yk  1  m( xk  1)  b
Deriving Bresenham’s Line Algorithm
Decision is based on difference between the two pixel positions:
dlower – dupper = [m (xk + 1) + b – yk] – [yk + 1 – m (xk + 1) – b]
= m xk + m + b – y k – y k – 1 + m x k + m + b
= 2m xk + 2m – 2 yk + 2 b– 1
= 2m (xk + 1) – 2 yk + 2 b – 1
(m = ∆y/∆x, where ∆x and ∆y are differences between the end-points )
Decision parameter at step k , pk is:
pk = Δx (dlower – dupper )
= Δx [2m (xk + 1) – 2 yk + 2 b – 1]
= Δx [2(Δy/Δx) (xk + 1) – 2 yk + 2 b – 1]
= 2Δy (xk + 1) – 2Δx yk + 2Δx b – Δx
= 2Δy xk – 2Δx yk + [2Δy + Δx (2 b – 1)]
= 2Δy xk – 2Δx yk + c
(where c is a constant , c = 2Δy + Δx (2 b – 1) )
Deriving Bresenham’s Line Algorithm
(Sign of decision parameter pk is same as that of (dlower – dupper ))
if pk is negative, then choose lower pixel, (xk +1, yk )
if pk is positive ,then choose upper pixel, (xk +1, yk +1)

Decision parameter at step k+1 , pk+1 is evaluated as:

p  2y  x  2 x  y c
k 1 k 1 k 1
p  p  2y ( x  x )  2 x ( y y )
k 1 k k 1 k k 1 k
p  p  2 y  2x ( y y )
k 1 k k 1 k
Take (xk+1 = xk +1) where
(yk+1 – yk ) is either 0 or 1 depending on sign of pk
Deriving Bresenham’s Line Algorithm
if ( p  0), ( y  y )
k k 1 k
p  p  2 y  2 x ( y  y )
k 1 k k 1 k
 p  2 y  2 x ( y  y )
k k k
 p  2 y
k
p  p  2 y , ( p  0)
k 1 k k

Similarly
if ( p  0), ( y  y  1)
k k 1 k
p  p  2 y  2 x ( y  y )
k 1 k k 1 k
 p  2 y  2 x ( y  1  y )
k k k
 p  2 y  2 x
k
p  p  2 y  2 x , ( p  0)
k 1 k k
Deriving Bresenham’s Line Algorithm
The first decision parameter p0 is evaluated at (x0, y0) as:
p k  x ( d lower  d upper )
 x ( 2 m ( x k  1)  2b  2 y k  1)
p0  x ( 2 m ( x 0  1)  2b  2 y 0  1)
 x ( 2 mx 0  2 m  2b  2 y 0  1)
 x ( 2 ( mx 0  b  y 0 )  2 m  1)
( y  mx  b , so ( mx 0  b  y 0 )  0 , m  y / x )
 ( 2 m  1) x  2 mx  x
 2 ( y / x ).x  x
p0  2 y  x
Bresenham’s Line Algorithm - (for |m| < 1)
1. Input the two line end-points (x0, y0) and (x1, y1) , storing the left
end-point in (x0, y0)
2. Plot the point (x0, y0)
3. Calculate the constants
Δx = (x1 – x0 ), Δy =( y1 - y0), 2Δy, and (2Δy - 2Δx)
and get the first value for the decision parameter as:
p0  2y  x

4. At each xk along the line, starting at k = 0, perform following test:

if ( pk < 0), the
p nextpoint
p to 2plot
yis (xk+1, yk ) and
k 1 k

if ( pk > 0), the

p nextpoint
p to2plot
y is 2(xk+1,
x yk+1) and
k 1 k
In General For a line with gradient ≤ 1
p0 = 2Δy – Δx
if pk  0 then yk+1 = yk
pk+1 = pk + 2Δy
if pk ≥ 0 then yk+1 = yk + 1
pk+1 = pk + 2 (Δy – Δx)
xk+1 = xk + 1
For a line with gradient  1
p0 = 2Δx – Δy
if pk  0 then xk+1 = xk
pk+1 = pk + 2Δx
if pk ≥ 0 then xk+1 = xk + 1
pk+1 = pk + 2 (Δx – Δy)
yk+1 = yk + 1
Note: For |m| ≤ 1 the constants 2 Δy and 2(Δy – Δx) can be calculated once,
so the arithmetic will involve only integer addition and subtraction.
Example – Draw a line from (20,10) to (30,18)
Δx = 30 - 20 = 10 (30,18)
Δy = 18 - 10 = 8
Initial decision parameter p0
p0 = 2 Δy – Δx = 6
Also 2 Δy = 16, 2(Δy – Δx) = -4 (20,10)
k pk (xk+1,yk+1)
19

0 6 (21,11) 18
1 2 (22,12) 17
2 -2 (23,12) 16
3 14 (24,13) 15
4 10 (25,14) 14
5 6 (26,15) 13
6 2 (27,16) 12
7 -2 (28,16) 11
8 14 (29,17) 10
9 10 (30,18) 20 21 22 23 24 25 26 27 28 29 30 31 32 36
void LineBres(int x0, int y0, int x1, int y1) // line for |m| < 1
{
int dx = abs(x1 – x0), dy = abs(y1 – y0);
int p = 2 * dy – dx;
int x, y, xend;
if (x0 > x1) { // determines which point to use as start, which as end
x = x1;
y = y1;
xend = x0;
}
else {
x = x0;
y = y0;
xend = x1;
}
setPixel(x,y,1);
while (x < xend) {
x++;
if (p < 0) p = p+ 2* dy;
else {
y++;
p= p + 2 * (dy-dx);
}
setPixel(x, y,1);
} 37
}
Bresenham’s Line - Special Cases
 Bresenhams algorithm is generalised to lines with arbitrary slopes by
considering the symmetry between the various octants and quadrants of
xy plane of the coordinate system.
 For line with +ve slope (m > 1), we interchange the roles of x and y
direction i.e., step along y directions in unit steps and calculate
successive x values nearest the line path.
 For +ve slope to plot from right to left, both x and y decreases in steps
 For line with –ve slopes the procedures are similar except that now,
one coordinate decreases as the other increases.
Special cases can be handled separately
– Horizontal lines (y = 0)
– Vertical lines (x = 0)
– Diagonal lines (|x| = |y|)
Points loaded directly into the frame-buffer without processing them
38
using the line-plotting algorithms.
Bresenham’s Line Algorithm
Advantages
• Only involves integer calculations.
• It outperforms DDA in terms of speed.
• Using a shift register, we may implement multiplication by two in
hardware.
• Involves less expensive operations such as addition and
subtraction.
• More accurate.

Disadvantages
• Though it improves the accuracy of generated points but still the
resulting line is not smooth.
• This algorithm is for the basic line drawing. It cannot handle
diminishing jaggies.
Circle Generating Algorithms
 Polar form
x = rCosy = rSin (r = radius of circle)
 = 0°
while ( < 360°) y
x = rCos
y = rSin
setPixel(x,y) P=(rCos, rSin)
 =  + 1°
end while r rSin

x
rCos
Disadvantages
 To find a complete circle  varies
from 0° to 360°
 The calculation of trigonometric
functions is very slow
40
Cartesian Form
 Use Pythagoras theorem
x 2 + y 2 = r2
y
r y

P  x, r 2  x 2 
x r y

Disadvantages x x
 To find a complete circle 
varies from 0° to 360°
 The calculation of square and
square roots is very slow
41
Circle algorithms
 Step through x-axis to determine y-values

 Disadvantages:
– Not all pixel filled in
42
– Square root function is very slow
Circle Symmetry
 Use 8-fold symmetry and only compute pixel positions
for the 45° sector.

(-x, y) (x, y)

(-y, x) 45° (y, x)

(-y, -x) (y, -x)

(-x, -y) (x, -y)

43
Bresenham’s Circle Algorithm
Consider only
General Principle 45° ≤  ≤ 90°
 The circle function:
2 2 2
f circle ( x, y )  x  y  r
 and

 0 if (x,y) is inside the circle boundary


f circle ( x, y )   0 if (x,y) is on the circle boundary
 0 if (x,y) is outside the circle boundary

44
Bresenham’s Circle Algorithm

p1 p3
yk du

yk - 1 dl
p2

xk xk+ 1

After point p1, we choose p2 or p3?

45
Bresenham’s Circle Algorithm
Define: dupper = d1 = distance of p3 from circle
dlower = d2 = distance of p2 from circle

i.e. d1 = (xk + 1)2 + yk2 – r2 [always +ve] ( p3 outside circle)

d2 = (xk + 1)2 + (yk – 1)2 – r2 [always -ve] ( p2 inside circle)

Decision Parameter at step k, pk

pk = d1 – (- d2 ) = d1 + d2
= [ (xk + 1)2 + yk2 – r2 ] + [ (xk + 1)2 + (yk – 1)2 – r2 ]
= 2 (xk + 1)2 + yk2 + (yk – 1)2 – 2 r2

So, pk = 2 (xk + 1)2 + yk2 + (yk – 1)2 – 2 r2

if pk < 0 then circle closer to p3 (xk + 1, yk ) (upper pixel)
Bresenham’s Circle Algorithm
Decision Parameter at step k+1, pk+1
pk+1 = 2 (xk+1 + 1)2 + yk+12 + (yk+1 – 1)2 – 2 r2
where xk+1 = (xk + 1)
pk+1 – pk = [2 (xk+1 + 1)2 + yk+12 + (yk+1 – 1)2 – 2 r2 ]
– [2 (xk + 1)2 + yk2 + (yk – 1)2 – 2 r2 ]
= [2 (xk + 1+ 1)2 + yk+12 + ( yk+1 – 1)2 – 2 r2 ]
– [2 (xk + 1)2 + yk2 + ( yk – 1)2 – 2 r2 ]
= 2 (xk + 2)2 + yk+12 + ( yk+12 – 2 yk+1 + 1) – 2 r2
– 2 (xk + 1)2 – yk2 – (yk2 – 2 yk + 1) + 2 r2
= 2 (xk2 + 4 xk + 4) + 2 yk+12 – 2 yk+1 + 1
– 2 (xk2 + 2 xk + 1) – 2 yk2 + 2 yk – 1
= 2 xk2 + 8 xk + 8 + 2 yk+12 – 2 yk2 – 2 yk+1 + 2 yk
– 2 xk2 – 4 xk – 2
2 2
Bresenham’s Circle Algorithm
pk+1 = pk + 4 xk + 2 (yk+12 – yk2 ) – 2 (yk+1 – yk ) + 6
if pk < 0 then ( yk+1 = yk ) (upper pixel)
pk+1 = pk + 4 xk + 2 (yk2 – yk2 ) – 2 (yk – yk ) + 6
= pk + 4 xk + 2 (0) – 2 (0) + 6
= pk + 4 xk + 6

if pk ≥ 0 then ( yk+1 = yk – 1) (lower pixel)

pk+1 = pk + 4 xk + 2 ((yk – 1)2 – yk2 ) – 2 ((yk – 1) – yk ) + 6
= pk + 4 xk + 2 (yk2 – 2 yk + 1) – yk2 ) – 2 (– 1) + 6
= pk + 4 xk + 2 (– 2 yk + 1) + 2 + 6
= p k + 4 x k – 4 yk + 2 + 2 + 6
Bresenham’s Circle Algorithm
Initial point (x0, y0) = (0, r)
Initial decision parameter p0 is:
pk = 2 (xk + 1)2 + yk2 + (yk – 1)2 – 2 r2
p0 = 2 (0 + 1)2 + r2 + (r – 1)2 – 2 r2
= 2 (1)2 + r2 + r2 – 2 r + 1 – 2 r2
= 2 + 2 r2 – 2 r + 1 – 2 r2
= 3 – 2r

pk+1 = pk + 4 xk + 6 ( pk < 0 )
pk +1 = pk + 4 xk – 4 yk + 10 ( pk ≥ 0 )
p0 = 3 – 2r
Bresenham’s Circle Algorithm
1. Initial values:- point (0, r) move circle origin at (0,0) by
x = x – xc and y = y – yc
x0 = 0, y0 = r
2. Initial decision parameter, p0 = 3 – 2r
3. At each xk position, starting at k = 0, along circle centered on (0,
0) perform the following test:
if ( pk < 0), the next point is upper pixel (xk + 1, yk ) and
pk+1 = pk + 4xk + 6
else if (pk ≥ 0 ), the next point is lower pixel (xk+1, yk -1) and
pk+1 = pk + 4(xk – yk) + 10
4. Determine symmetry points in the other 7 octants
5. Move pixel positions (x, y) onto the circular path centered on
(xc , yc) and plot the coordinates: x = x + xc , y = y + yc
6. Repeat steps 3 to 5 until (x ≥ y) 50
Example- Bresenham’s Circle
r = 10
p0 = 3 – 2r = -17
Initial point (x0, y0) = (0, 10)
10    
k pk xk+1, yk+1 9  
8 
0 -17 (1, 10) 7 
1 -11 (2, 10) 6 

2 -1 (3, 10) 5 
4 
3 13 (4, 9) 3 
4 -5 (5, 9) 2 

5 17 (6, 8) 1 
0 
6 11 (7,7) 0 1 2 3 4 5 6 7 8 9 10
51
Bresenham’s Circle Algorithm
Advantages:
• Due to its integer arithmetic - addition, subtraction and
multiplication, it is faster
• There is no need for squares, square roots and trigonometric
functions
• This algorithm is more efficient and accurate than any other
circle drawing algorithm as it avoids the round off function
Disadvantages:
• No accuracy of the generating points.
• This algorithm cannot generate complex and highly
graphical
images.
• There is no significant enhancement with respect to 52
Mid-Point Circle Algorithm
Similarly to the case with lines, this is an
incremental algorithm for drawing
circles – the Mid-point circle algorithm
In the mid-point circle algorithm we use
eight-way symmetry
So only calculate the points for the top
right eighth of a circle, and then use
symmetry to plot the rest of the points in The mid-point circle
algorithm was developed
7 other octants. by Jack Bresenham.
Mid-Point Circle Algorithm (cont…)
Assume that we have just
plotted point (xk, yk)
The next point is a
choice between (xk+1, yk) and
(xk+1, yk-1)
Choose the point that is nearest
to the actual circle
Mid-Point Circle Algorithm (cont…)
The equation of circle evaluates as follows:

2 2 2
f circ ( x, y )  x  y  r

By evaluating this function at the midpoint between the

candidate pixels we can make our decision

 0, if ( x, y ) is inside the circle boundary


f circ ( x, y )  0, if ( x, y ) is on the circle boundary
 0, if ( x, y ) is outside the circle boundary

Mid-Point Circle Algorithm (cont…)
After plotting pixel at (xk,yk) , choose between (xk+1, yk) and (xk+1, yk-
1), the decision variable pk can be defined as:

pk  f circ ( xk  1, yk  1 )
2
 ( xk  1) 2  ( yk  1 ) 2  r 2
2
If pk < 0, midpoint is inside the circle , yk is closer to circle
If pk > 0 the midpoint is outside and yk-1 is closer
To do calculations incrementally consider:

p
k 1
 f x
circ k  1
 1, y
k 1
1 
2
 [( x  1)  1]2  ( y  1 )2  r 2
k k 1 2
Mid-Point Circle Algorithm (cont…)
p  p  (( x  1)  1) 2  ( y  1 )2  r 2
k 1 k k k 1 2
 [( x  1) 2  ( y  1 ) 2  r 2 ]
k k 2
 ( x  1) 2  2( x  1)  1  ( y )2  y 1
k k k 1 k 1 4
2
 ( x  1)  y 2  y  1
k k k 4
 2( x  1)  [( y ) 2  y 2 ]  [( y )  y ] 1
k k 1 k k 1 k
now
2 2
pk 1  pk  2( xk 1)  ( yk 1  yk )  ( yk 1  yk ) 1
xk 1  xk 1
when( pk  0), y k 1  yk (upperpixel )
pk 1  pk  2( xk 1)  ( yk2  yk2 )  ( y k  yk ) 1
pk 1  pk  2( xk 1)  0  0 1
 pk  2 xk 1 1
Mid-Point Circle Algorithm (cont…)
when( pk  0), yk 1  yk 1(lowerpixel)
pk 1  pk  2( xk 1) [( yk 1) 2  yk2 ][( yk 1)  yk ]1
[(a 2  b 2 )  (a  b)(a  b)]also[((a  b)(a  b))  (a  b))  (a  b)(a  b 1)]
[a  ( yk 1),b  yk ]
 pk  2( xk 1) [( yk 1)  yk ][( yk 1)  yk ][( yk 1)  yk ]1
 pk  2( xk 1) [( yk 1)  yk 1][( yk 1)  yk ]1
 pk  2( xk 1) [(2 yk  2)(1)]1
 pk  2( xk 1)  2( yk 1) 1
 pk  2 xk 1  2 yk 1 1

where 2 xk 1  2( xk  1)
 2 xk  2
2 y k 1  2( y k  1)
 2 yk  2
Mid-Point Circle Algorithm (cont…)
Initial point (x0, y0) = (0, r)
initial decision parameter p0 is given as:
p0  f circ (1, r  1 )
2
 1  (r  1 )2  r 2
2
 5 r
4
(if r is integer , round p0 = 5/4 – r to integer)
Then if pk < 0 then next decision variable pk+1 is:
pk 1  pk  2 xk 1  1

Else if pk > 0 then next decision variable pk+1 is:

pk 1  pk  2 xk 1  1  2 y k 1
Midpoint Circle Algorithm
1. Initial values:- point (0, r) move circle origin at (0,0) by
x = x – xc and y = y – yc
x0 = 0, y0 = r
2. Initial decision parameter, p0
p0  5  r  1 r
4
3. At each xk position, starting at k = 0, along circle centered on (0, 0)
perform the following test:
if pk < 0, the next point is upper pixel (xk + 1, yk ) and
pk+1 = pk + 2xk+1 + 1
else if pk ≥ 0, the next point is lower pixel (xk + 1, yk – 1) and
pk+1 = pk + 2xk+1 + 1 – 2yk+1
where 2xk+1 = 2xk + 2 and 2yk+1 = 2yk – 2
4. Determine symmetry points in the other 7 octants
5. Move pixel positions (x,y) onto the circular path centered on (xc, yc)
and plot the coordinates: x = x + xc , y = y + yc
6. Repeat steps 3 to 5 until x ≥ y
Example - Midpoint Circle
r = 10
p0 = 1 – r = -9 (if r is integer round p0 = 5/4 – r to integer)
Initial point (x0, y0) = (0, 10)
10    
k pk xk+1, yk+1 2xk+1 2yk+1 9  
8 
0 -9 (1, 10) 2 20 7 

1 -6 (2, 10) 4 20 6 
5 
2 -1 (3, 10) 6 20 4 
3 6 (4, 9) 8 18 3 

4 -3 (5, 9) 10 18 2 
1 
5 8 (6, 8) 12 16 0 
6 5 (7, 7) 0 1 2 3 4 5 6 7 8 9 10
Mid-Point Circle Algorithm
Advantages:
• Due to its integer arithmetic - addition, subtraction and
multiplication, it is faster
• There is no need for squares, square roots and trigonometric
functions
• This algorithm is efficient for scan conversion for drawing
geometric curves on raster display.
Disadvantages:
• It is time consuming
• Distance between the pixels is not equal so a smooth circle will not
be got.
• No accuracy of the generating points.