CST 304 COMPUTER GRAPHICS AND IMAGE PROCESSING

MODULE 1
Basics of Computer Graphics and its applications. Video Display devices- Refresh Cathode
Ray Tubes, Random Scan Displays and systems, Raster scan displays and systems. Line
drawing algorithms- DDA, Bresenham’s algorithm. Circle drawing algorithms- Midpoint
Circle generation algorithm, Bresenham’s algorithm.

Introduction
The term computer graphics includes almost everything on computers that is not text or
sound. Today almost every computer can do some graphics, and people have even come to expect
to control their computer through icons and pictures rather than just by typing. Computer graphics
is art of drawing pictures on computers, also called as rendering. The pictures can be photographs,
drawings, movies, or simulations - pictures of things, which do not yet exist and maybe could never
exist. Or they may be pictures from places we cannot see directly, such as medical images from inside
your body.

Computer Graphics express data in pictorial form. It displays information in the form of
graphics objects such as pictures, charts, graphs etc instead of simply text. Computer graphics is an
art of drawing pictures, lines, charts, etc using computers with the help of programming. It is the use
of computer to define, store, manipulate, interrogate, and present pictorial output.

Applications of computer graphics

• Movie industry
• Games
• Medical Imaging and Scientific Visualization
• Computer Aided Design
• Education & training
• Simulators used for training ship captains, pilots
• Computer Art
• Presentation graphics
• Image processing
• GUI
Basic concepts in Computer Graphics
A display area is represented as a collection of discrete picture elements called pixels. Pixel is
the smallest addressable unit on the screen. Each pixel has got some information like its intensity and
color.

1
Interactive & Passive computer graphics
Basically there are two types of computer graphics namely Interactive Computer Graphics
and Passive computer graphics .
Interactive Computer Graphics
It involves a two way communication between computer and user. The observer is given
some control over the image by providing him with an input device .For example: Observer send his
request to the computer through video game controller. Computer on receiving signals can modify
the displayed picture appropriately.
Non Interactive Computer Graphics
It is also known as passive computer graphics. The user does not have any kind of control
over the [Link] involves only a one way communication. The image is merely the product of static
stored program and will work according to the instructions given in the program linearly. The image
is totally under the control of program instructions, not under the user. Example: images shown on
television.

Video Display Devices: CRT

The primary output device in a graphics system is a video [Link] operation of most
video monitors is based on the standard cathode ray tube (CRT).

Working of Refresh CRT

The beam of electrons are emitted by an electron gun. It passes through focusing and
deflection systems that direct the beam toward specified positions on the phosphor coated screen.
Thus phosphor emits a small spot of light at each position contacted by the electron beam. Because
the light emitted by the phosphor fades very rapidly, some method is needed for maintaining the
screen picture. One way to keep the phosphor glowing is to redraw the picture repeatedly by quickly
directing the electron beam back over the same [Link] type of display is called a refresh CRT
The primary components of an electron gun in a CRT are the heated metal , cathode and a
control grid .

2
 Heat is supplied to the cathode by directing a current through a coil of wire, called the
[Link] causes electrons to be ‘boiled off" the hot cathode surface. Intensity of the electron
beam is controlled by setting voltage levels on the control grid, which is a metal cylinder that fits over
the cathode. Amount of light emitted by the phosphor coating depends on the number of electrons
striking the screen,thus we control the brightness of a display by varying the voltage on the control
grid. A smaller negative voltage on the control grid simply decreases the number of electrons passing
through the small hole at the end of the control grid structure. A high negative voltage applied will
stop electrons from passing through it.
The focusing system force the electron beam to converge into a small spot as it strikes the
phosphor. Otherwise, the electrons would repel each other, and the beam would spread out as it
approaches the [Link] is accomplished with the help of either electric or magnetic fields. It
is commonly constructed with a pair of magnetic deflection coils mounted on CRT [Link]
magnetic field produced by each pair of coils directs the electron beam properly. Horizontal
deflection is accomplished with one pair of coils, and vertical deflection by the other pair.
When electrostatic deflection is used, two pairs of parallel plates are mounted inside the CRT
envelope. One pair of plates is mounted horizontally to control the vertical deflection, and the other
pair is mounted vertically to control horizontal deflection

In the vacuum inside the CRT envelope, the free, negatively charged electrons are then
accelerated toward the phosphor coating by a high positive voltage. The accelerating voltage can be
generated with an accelerating anode or with a positively charged metal coating inside the CRT
envelope near the phosphor screen.
When the electrons in the beam collide with the phosphor coating, they are stopped and their
kinetic energy is absorbed by the phosphor. A part of the beam energy is converted by friction into
heat energy, and the remainder causes electrons in the phosphor atoms to move up to higher

3
quantum energy levels. After a short time, the excited phosphor electrons begin dropping back to their
stable ground state, giving up their extra energy as small quantum of Light energy. What we see on the
screen is the combined effect of all these electron light emissions.

Basic concepts related to graphics display devices

Persistence :
Persistence is defined as the time CRT takes to decay the emitted light from the screen to one
tenth of its original [Link] persistence phosphor require high refresh rate. Graphics monitors
are usually constructed with a persistence in the range from 10 to 60 microseconds.
Resolution :
The maximum number of points that can be displayed without overlap on a CRT. The number
of points per cm that can be plotted horizontally and vertically. Typical resolution on high- quality
systems is 1280 by 1024. Higher resolution systems are often referred to as high-definition systems.
Intensity distribution :

Intensity is greatest at the center of pixel and decreases with Gaussian distribution towards
edges.

Aspect Ratio :

The ratio of vertical points to horizontal points necessary to produce equal length lines in both
direction on the screen. It is the ratio of horizontal to vertical points.

4
Raster scan display and Random scan display.
Raster scan display

It is the most common type of CRT monitor. In this system, the electron beam is swept across
the screen one row at a time from top to bottom. Beam intensity is turned on and off to create a pattern
of illuminated spots as the electron moves across each row .In a raster scan system entire screen is
considered as a matrix of pixels. Each screen point is referred to as a pixel or pel (shortened form of
picture element) .Frame buffer or refresh buffer is a memory where picture definition is stored .i.e set of
all intensity values for all pixels is stored in refresh buffer.

Horizontal Retrace: At the end of each scan line , the electron beam returns to the left side of the screen
to begin displaying the next scan line.

Vertical retrace: At the end of each frame the electron beam returns to the top left corner of the screen
to begin the next frame.

5
Interlacing: In this method, each frame is displayed in two passes using an interlaced refresh
[Link] all the points on the even numbered scanlines are displayed ,and then all the odd
numbered lines are displayed. Entire screen is displayed in half time , providing that adjacent scanlines
contain similar information.

In a simple black and white system, each screen point is either on or off, so only one bit per pixel
is needed to control the intensity of screen positions. Bit value of 1 indicates that the electron beam is to
be turned on that position, and a value of 0 indicates that the beam intensity is to be turned off. Additional
bits are needed when color and intensity variations are to be displayed .On a black-and-white system with
one bit per pixeI, the frame buffer is commonly called a bitmap. For systems with multiple bits per pixel,
the frame buffer is referred to as a pixmap.

Refreshing on raster scan displays is carried out at the rate of 60 to 80 frames per [Link]
television sets and printers are examples of other systems using raster-scan [Link] capability of a
raster-scan system to store intensity information for each screen point makes it well suited for the realistic
display of scenes containing subtle shading and color patterns.

Random scan display.

It is also called as calligraphic displays, vector displays, stroke [Link] electron beam is directed only
to the parts of the screen where a picture is to be [Link] scan monitors draw a picture one line
at a time. The component lines of a picture can be drawn and refreshed in any specified order.A pen
plotter operates in a similar way and is an example of a random-scan, hard-copy device.

Picture definition is stored as a set of line drawing commands in an area of memory referred to
as refresh display file/refresh [Link] display a specified picture ,the system cycles through a set of
commands in the display file , drawing each component line .After all line drawing commands have been
processed, the system cycles back to the first line command in the list.

6
 Random-scan displays are designed to draw all the component lines of a picture 30 to 60 times
each [Link]-scan systems are designed for line drawing applications and cannot display
realistic shaded scenes.

Color CRT
A CRT monitor displays color pictures by using a combination of phosphors that emit different-
colored light. By combining the emitted light from the different phosphors, a range of colors can be
generated. The two basic techniques are beam-penetration method and shadow-mask method.

Beam-penetration Method

In this method, two layers of phosphor, usually red and green, are coated onto the inside of the
CRT screen. The displayed color depends on how far the electron beam penetrates into the phosphor
layers. A beam of slow electrons excites only the outer red layer. A beam of very fast electrons

penetrates through the red layer and excites the inner green layer. At intermediate beam speeds,
combinations of red and green light are emitted to show two additional colors, orange and yellow. The

7
speed of the electrons, and hence the screen color at any point, is controlled by the beam-acceleration
voltage.

Advantage:
• An inexpensive way to produce color in random-scanmonitors
Disadvantage:
• Only four colors are possible
• quality of pictures is not as good as with other methods.

Shadow-mask Method

This method is commonly used in color TV because they produce a much wider range of colors
than the beam penetration method. A shadow-mask CRT has three phosphor color dots at each pixel
position. One phosphor dot emits a red light, another emits a green light, and the third emits a blue
light. This type of CRT has three electron guns, one for each color dot, and a shadow-mask grid just
behind the phosphor-coated screen.

8
 The three electron beams are deflected and focused as a group onto the shadow mask, which
contains a series of holes aligned with the phosphor-dot patterns. When the three beams pass through a
hole in the shadow mask, they activate a dot triangle, which appears as a small color spot on the screen.
The phosphor dots in the triangles are arranged so that each electron beam can activate only its
corresponding color dot when it passes through the shadow mask. Color variations are obtained by
varying the intensity levels of the three electron beams.
By turning off red and green guns, we get only blue phosphor. The color we see depends on the
amount of excitation of the red, green, and blue phosphors.A white area is the result of activating all three
dots with equal intensity.
Yellow -> green and red dots
Magenta -> blue and red dots
Cyan ->blue and green
In some low-cost systems, the electron beam can only be set to on or off, limiting displays to eight
colors. More sophisticated systems can set intermediate intensity levels for the electron beams, allowing
several million different colors to be generated.

Direct-View Storage Tubes

An alternative method for maintaining a screen image is to store the picture information inside
the CRT instead of refreshing the screen. A direct-view storage tube (DVST) stores the picture information
as a charge distribution just behind the phosphor-coated screen. Two electron guns are used in a DVST-
Primary gun & Flood gun. The Primary gun used to store the picture as pattern of positive charges on
storage grid. The Flood gun used to maintains the picture display. Picture pattern is transferred to
phosphor by continuous flood of electron generated from flood [Link] are attracted by positively
charged picture pattern on storage grid and are repelled by [Link] attracted electrons strike on
phosphor making it visible on screen.

Advantages :
Because no refreshing is needed, very complex pictures can be displayed at very high resolutions
without flicker.
Disadvantages :
• they ordinarily do not display color
• selected parts of a picture cannot be erased. To eliminate a picture section, the entire
screen must be erased and the modified picture redrawn.

9
RASTER& RANDOM SCAN SYSTEMS

RASTER-SCAN SYSTEMS
In Interactive raster graphics systems, in addition to the CPU ,a special-purpose processor, called
the video controller or display controller, is used to control the operation of the display device.

10
 A fixed area of the system memory is reserved for the frame buffer, and the video controller is
given direct access to the frame-buffer memory. Frame-buffer locations, and the corresponding screen
positions, are referenced in Cartesian coordinates.

For many graphics monitors, the coordinate origin is defined at the lower left screen corner .The
screen surface is represented as the first quadrant of a two-dimensional system, with positive x values
increasing to the right and positive y values increasing from bottom to [Link] lines are then labeled
from ymax at the top of the screen to 0 at the bottom. Along each scan line, screen pixel positions are
labeled from 0 to xmax.
On some personal computers, the coordinate origin is referenced at the upper left comer of the
screen, so the y values are inverted.

Basic refresh operations of the video controller

Two registers are used to store the coordinates of the screen pixels: x register and y register.
Initially, x register is set to 0 and the y register is set to ymax. The value stored in the frame buffer for this

11
pixel position is then retrieved and used to set the intensity of the CRT beam. Then the x register is
incremented by 1, and the process repeated for the next pixel on the top scan line. This procedure is
repeated for each pixel along the scan line. After the last pixel on the top scan line has been processed,
the x register is reset to 0 and the y register is decremented by 1. Pixels along this scan line are then
processed in turn, and the procedure is repeated for each successive scan line. After cycling through all
pixels along the bottom scan line (y = 0), the video controller resets the registers to the first pixel position
on the top scan line and the refresh process starts over.
To speed up pixel processing, video controllers can retrieve multiple pixel values from the refresh
buffer on each pass. The multiple pixel intensities are then stored in a separate register called pixel
register and used to control the CRT beam intensity for a group of adjacent pixels.
Organization of a raster system containing a separate display processor, sometimes referred to
as a graphics controller or a display coprocessor. The purpose of the display processor is to free the CPU
from the graphics chores.
In addition to the system memory, a separate display processor memory area can also be
provided. Main purpose is digitizing a picture definition given in an application program into a set of pixel-
intensity values for storage in the frame buffer. This digitization process is caIled scan conversion.

RANDOM-SCAN SYSTEMS

An application program is input and stored in the system memory along with a graphics package.
Graphics commands in the application program are translated by the graphics package into a display file
stored in the system memory. This display file is then accessed by the display processor to refresh the
screen. The display processor cycles through each command in the display file program once during every
refresh cycle. Sometimes the display processor in a random-scan system is referred to as a display
processing unit or a graphics controller.
Graphics patterns are drawn on a random-scan system by directing the electron beam along the
component lines of the picture. Lines are defined by the values for their coordinate endpoints, and these
input coordinate values are converted to x and y deflection voltages. A scene is then drawn one line at a
time by positioning the beam to fill in the line between specified endpoints.

12
13
LINE DRAWING ALGORITHM

A line connects two points. It is a basic element in graphics. To draw a line, you need two points
between which you can draw a line. In the following three algorithms, we refer the one point of line
as (X0,Y0) and the second point of line as (X1,Y1).

Digital Differential Algorithm [DDA]

Digital Differential Analyzer DDADDA algorithm is the simple line generation algorithm which is
explained step by step here.
Step 1 − Get the input of two end points (X0,Y0)(X0,Y0) and (X1,Y1)(X1,Y1).
Step 2 − Calculate the difference between two end points.
dx = X1 - X0
dy = Y1 - Y0
Step 3 − Based on the calculated difference in step-2, you need to identify the number of
steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y
coordinate.
if (absolute(dx) > absolute(dy))
Steps = absolute(dx);
else
Steps = absolute(dy);

Step 4 − Calculate the increment in x coordinate and y coordinate.

Xincrement = dx / steps;
Yincrement = dy / steps;

Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and
complete the drawing of the line.
for(int v=0; v < Steps; v++)
{
x = x + Xincrement;
y = y + Yincrement;
putpixel(Round(x), Round(y));
}

Problem 1
Calculate the points between the starting point (5, 6) and ending point (8, 12).

Given-
• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (8, 12)

14
Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 8 – 5 = 3
• ΔY =Yn – Y0 = 12 – 6 = 6
• M = ΔY / ΔX = 6 / 3 = 2

Step-02:

Calculate the number of steps.

As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6
Step-03:

As M > 1, so case-03 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

Problem-02:

Calculate the points between the starting point (5, 6) and ending point (13, 10).

Solution-

15
Given-
• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (13, 10)

Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 13 – 5 = 8
• ΔY =Yn – Y0 = 10 – 6 = 4
• M = ΔY / ΔX = 4 / 8 = 0.50

Step-02:

Calculate the number of steps.

As |ΔX| > |ΔY| = 8 > 4, so number of steps = ΔX = 8

Step-03:

As M < 1, so case-01 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

16
 Bresenham’s Line Generation
The Bresenham’s algorithm is another incremental scan conversion algorithm. The big advantage of
this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at
each step choose between two different y coordinates.

17
As shown in the above figure let, we have initial coordinates of a line = (xk, yk)
The next coordinates of a line = (xk+1, yk+1)
The intersection point between yk and yk+1 = y
Let we assume that the distance between y and yk = d1
The distance between y and yk+1 = d2
Now, we have to decide which point is nearest to the intersection point.
If m < 1
then x = xk+1 { Unit Interval}
y = yk+1 { Unit Interval}
As we know the equation of a line-
y = mx +b
Now we put the value of x into the line equation, then
y = m(xk+1) +b …………. (1)
The value of d1 = y - yk
Now we put the value of d1 in equation (1).
y = m (xk+1) +b - yk
Now, we again put the value of y in the previous equation then we got,
d2 = yk+1 – y
= yk + 1 – m (xk+1) – b
Now, we calculate the difference between d1 – d2
If d1 < d2
Then yk+1 = yk {we will choose the lower pixel as shown in figure}
18
If d1 => d2
Then yk+1 = yk+1 {we will choose the upper pixel as shown in figure}
Now, we calculate the values of d1 - d2
(d1 - d2)= m (xk+1) +b - yk - yk - 1 + m (xk+1) + b
We simplified the above equation and replaced the m with ∆y/∆x.
(d1 - d2) = 2 m (xk+1) -2yk + 2b-1
We multiplied ∆x at both side then we got,
∆x (d1 - d2) = ∆x (2m (xk+1) -2yk + 2b-1)
We consider ∆x (d1 - d2) as a decision parameter (Pk), so
pk = ∆x (d1 - d2)
After calculation we got,
Pk = 2∆yxk + 2∆y - 2∆xyk +∆x (2b-1)
Then, the next coordinate of pk
pk+1 = 2∆yxk+1 + 2∆y - 2∆xyk+1 +∆x (2b-1)
Now, the difference between pk+1 – pk then,
pk+1 – pk = 2∆y (xk+1-xk) – 2∆x (yk+1-yk)
pk+1 = pk + 2∆y (xk+1-xk) – 2∆x (yk+1-yk) {Decision parameter coordinate}
Now, we put the value of xk+1 in above equation then we got,
pk+1 = pk + 2∆y – 2∆x (yk+1 - yk) {New decision parameter when m <1}
Similarly, if m >1, the new decision parameter for next coordinate will be
pk+1 = pk + 2∆y – 2∆x (xk+1 - xk) {New decision parameter when m >1}
If pk >= 0 {For coordinate y}
Then,
yk+1 = yk+1 {We will choose the nearest yk+1 pixel}
The next coordinate will be (xk+1, yk+1)
If pk < 0
Then,
yk+1 = yk {We will choose the nearest yk pixel}
The next coordinate will be (xk+1, yk)
Similarly,
If pk >= 0 {For coordinate x}
Then,
xk+1 = xk+1 {We will choose the nearest xk+1 pixel}
The next coordinate will be (xk+1, yk+1)
If pk < 0
Then,
xk+1 = xk {We will choose the nearest xk pixel}
The next coordinate will be (xk, yk+1)

Procedure-

19
Given-
• Startingcoordinates = (X0, Y0)
• Ending coordinates = (Xn, Yn)

The points generation using Bresenham Line Drawing Algorithm involves the following steps-

Step-01:

Calculate ΔX and ΔY from the given input.

These parameters are calculated as-
• ΔX = Xn – X0
• ΔY =Yn – Y0

Step-02:

Calculate the decision parameter Pk.

It is calculated as-
Pk = 2ΔY – ΔX

Step-03:

Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
Find the next point depending on the value of decision parameter Pk.
Follow the below two cases-

20
 Step-04:

Keep repeating Step-03 until the end point is reached or number of iterations equals to (ΔX-1) times.

Problem-01:
Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).
Solution-
Given-
• Startingcoordinates = (X0, Y0) = (9, 18)
• Ending coordinates = (Xn, Yn) = (14, 22)

Step-01:
Calculate ΔX and ΔY from the given input.
• ΔX = Xn – X0 = 14 – 9 = 5
• ΔY =Yn – Y0 = 22 – 18 = 4

Step-02:
Calculate the decision parameter.
Pk
= 2ΔY – ΔX
=2x4–5
21
=3
So, decision parameter Pk = 3
Step-03:
As Pk >= 0, so case-02 is satisfied.
Thus,
• Pk+1= Pk + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
• Xk+1 = Xk + 1 = 9 + 1 = 10
• Yk+1 = Yk + 1 = 18 + 1 = 19

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 4 times.
(Number of iterations = ΔX – 1 = 5 – 1 = 4)

Problem-02:
Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).
Solution-
Given-
• Startingcoordinates = (X0, Y0) = (20, 10)
• Ending coordinates = (Xn, Yn) = (30, 18)

Step-01:
Calculate ΔX and ΔY from the given input.
• ΔX = Xn – X0 = 30 – 20 = 10

22
 • ΔY =Yn – Y0 = 18 – 10 = 8

Step-02:
Calculate the decision parameter.
Pk= 2ΔY – ΔX
= 2 x 8 – 10
=6
So, decision parameter Pk = 6

Step-03:

As Pk >= 0, so case-02 is satisfied.

Thus,
• Pk+1= Pk + 2ΔY – 2ΔX = 6 + (2 x 8) – (2 x 10) = 2
• Xk+1 = Xk + 1 = 20 + 1 = 21
• Yk+1 = Yk + 1 = 10 + 1 = 11

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 9 times.
(Number of iterations = ΔX – 1 = 10 – 1 = 9 OR x = y)

23
Advantages of Bresenham Line Drawing Algorithm-

The advantages of Bresenham Line Drawing Algorithm are-

• It is easy to implement.
• It is fast and incremental.
• It executes fast but less faster than DDA Algorithm.
• The points generated by this algorithm are more accurate than DDA Algorithm.
• It uses fixed points only.

Disadvantages of Bresenham Line Drawing Algorithm-

• Though it improves the accuracy of generated points but still the resulted line is not smooth.
• This algorithm is for the basic line drawing.
• It can not handle diminishing jaggies.

CIRCLE DRAWING ALGORITHM

24
MIDPOINT ALGORITHM

Important Points

• Circle drawing algorithms take the advantage of 8 symmetry property of circle.

• Every circle has 8 octants and the circle drawing algorithm generates all the points for one octant.
• The points for other 7 octants are generated by changing the sign towards X and Y coordinates.
• To take the advantage of 8 symmetry property, the circle must be formed assuming that the
centre point coordinates is (0, 0).
• If the centre coordinates are other than (0, 0), then we add the X and Y coordinate values with
each point of circle with the coordinate values generated by assuming (0, 0) as centre point.

Procedure-

Given-
• Centre pointof Circle = (X0, Y0)
• Radius of Circle = R

The points generation using Mid Point Circle Drawing Algorithm involves the following steps-

Step-01:

Assign the starting point coordinates (X0, Y0) as-

• X0 =0
• Y0 = R

Step-02:

Calculate the value of initial decision parameter P0 as-

P0 = 1 – R

Step-03:

Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
25
Find the next point of the first octant depending on the value of decision parameter Pk.
Follow the below two cases-

Step-04:

If the given centre point (X0, Y0) is not (0, 0), then do the following and plot the point-
• Xplot = Xc + X0
• Yplot = Yc + Y0

Here, (Xc, Yc) denotes the current value of X and Y coordinates.

Step-05:

Keep repeating Step-03 and Step-04 until Xplot >= Yplot.

Step-06:

Step-05 generates all the points for one octant.

To find the points for other seven octants, follow the eight symmetry property of circle.
This is depicted by the following figure-

26
 Problem-01:

Given the centre point coordinates (0, 0) and radius as 10, generate all the points to form a circle.
Given-
• Centre Coordinates of Circle (X0, Y0) = (0, 0)
• Radius of Circle = 10

Step-01:

Assign the starting point coordinates (X0, Y0) as-

• X0 =0
• Y0 = R = 10

Step-02:

Calculate the value of initial decision parameter P0 as-

P0 = 1 – R
P0 = 1 – 10
P0 = -9

Step-03:

27
As Pinitial < 0, so case-01 is satisfied.

Thus,
• Xk+1 = Xk + 1 = 0 + 1 = 1
• Yk+1 = Yk = 10
• Pk+1 = Pk + 2 x Xk+1 + 1 = -9 + (2 x 1) + 1 = -6

Step-04:

This step is not applicable here as the given centre point coordinates is (0, 0).

Step-05:

Step-03 is executed similarly until Xk+1 >= Yk+1 as follows-

28
 Problem-02:

Given the centre point coordinates (4, -4) and radius as 10, generate all the points to form a circle.
Given-
• Centre Coordinates of Circle (X0, Y0) = (4, -4)
• Radius of Circle = 10

As stated in the algorithm,

• We first calculate the points assuming the centre coordinates is (0, 0).
• At the end, we translate the circle.

Step-01, Step-02 and Step-03 are already completed in Problem-01.

Now, we find the values of Xplot and Yplot using the formula given in Step-04 of the main algorithm.

The following table shows the generation of points for Quadrant-1-

• Xplot = Xc + X0 = 4 + X0
• Yplot = Yc + Y0 = 4 + Y0

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

30
 • This algorithm is time consuming.

Extra Note:
Let us Take Quadrant 1:

Radius = OR = r
Radius = x intercept = y intercept
At point R
coordinate of x = coordinate of y or we can say x=y
let us take Octet 2 of quadrant 1
here first pixel would be (0,y)
here value of y intercept = radius (r)
as circle’s centre is at origin

DERIVATION

31
let us assume we have plotted Pixel P whose coordinates are
Now we need to determine the next pixel.

We have chosen octet 2 where circle is moving forward and downwards so y can never be
increased, either it can be same or decremented. Similarly x will always be increasing as
circle is moving forward too.

So y is needed to be decided.
Now we need to decide whether we should go with point N or S.

For that decision Mid Point circle drawing technique will us decide our next pixel
whether it will be N or S.

As is the next most pixel of therefore we can write,

And similarly in this case.

Let M is the midpoint between and .

And coordinates of point (M) are
32
Equation of Circle with Radius r

(x– h)2 + (y – k)2 = r2

When coordinates of centre are at Origin i.e., (h=0, k=0)

x2 + y2 = r2 (Pythagoras theorem)
Function of Circle Equation

F(C) = x2 + y2 - r2
Function of Midpoint M (xk+1 , yk -1/2) in circle equation

F(M)= xk+12 + (yk -1/2)2 - r2

= (xk+1)2 + (yk -1/2)2 - r2

The above equation is too our decision parameter pk

Pk = (xk+1)2 + (yk -1/2)2 - r2 …….(i)

To find out the next decition parameter we need to get Pk+1

Pk+1 = (xk+1+1)2 + (yk+1 -1/2)2 - r2

Now,
Pk+1- Pk = (xk+1+1)2 + (yk+1 -1/2)2 - r2
-[(xk+1)2 + (yk -1/2)2 - r2]

= ((xk+1)+1)2 + (yk+1 -1/2)2

- (xk+1)2 - (yk -1/2)2

33
 = (xk+1)2 + 1 +2(xk+1) + yk+12 +(1/4) - yk+1
- (xk+1)2 - yk2 – (1/4) + yk+1

= 2(xk+1) + yk+12 - yk2 - yk+1 + yk +1

= 2(xk+1) +( yk+12 - yk2 ) - (yk+1 - yk) +1

Pk+1 = Pk + 2(xk+1)+( yk+12 - yk2 ) - (yk+1 - yk) +1 …..(ii)

Now let us conclude the initial decision parameter

For that we have to choose coordinates of starting point i.e. (0,r)
Put this in (i) i.e. Pk
Pk = (xk+1)2 + (yk -1/2)2 - r2
P0 = (0+1)2 + (r -1/2)2 - r2
= 1 + r2 + ¼ - r – r2
=1+¼-r

…..(initial decision parameter)

Now If Pk ≥ 0 that means midpoint is outside the circle and S is closest pixel so we will
choose S (xk+1,yk-1)
That means yk+1 = yk-1
Putting coordinates of S in (ii) then,

Pk+1 = Pk + 2(xk+1)+( yk-12 - yk2 ) - (yk-1 - yk) +1

= Pk + 2(xk+1)+( yk -1)2 - yk2 ) - ((yk-1) - yk) +1
= Pk + 2(xk+1)+yk 2+1-2yk - yk2 - yk+1 + yk +1
= Pk + 2(xk+1)-2yk +2 + 1
= Pk + 2(xk+1)-2(yk -1) + 1

As we know (xk+1 = xk+1) and (yk-1 = yk-1)

Therefore,
Pk+1 = Pk + 2xk+1 - 2yk-1 + 1

And if Pk < 0 that means midpoint is inside the circle and N is closest pixel so we will
choose N (xk+1 , yk)
i.e. yk+1 = yk
34
 Now put coordinates of N in (ii)
Pk+1 = Pk + 2(xk+1)+( yk2 - yk2 ) - (yk - yk) +1
= Pk + 2(xk+1)+( yk2 - yk2 ) - (yk - yk) +1
= Pk + 2(xk+1) +1

as xk+1 = xk+1 , therefore,

Pk+1 = Pk + 2xk+1 +1

Hence we have derived the mid point circle drawing algorithm.

Bresenham’s Circle Drawing Algorithm-

Given the centre point and radius of circle,

Bresenham Circle Drawing Algorithm attempts to generate the points of one octant.

The points for other octacts are generated using the eight symmetry property.

Derivation of Bresenham’s circle-drawing algorithm

Let’s say if current pixel coordinates are (xk, yk). Then, we need to find out our next pixel (xk+1, yk+1).

35
So, We will start plotting points in octet-2 from (0, y ) and will move downwards in right direction. It
means xk will be incremented by one at each step and yk will either be decremented or will be same
depending on the sign of decision parameter.
Further, Our choices are the pixels at positions (xk+1, yk) and (xk+1, yk-1).
Equation of Circle with Radius r

(x– h)2 + (y – k)2 = r2

If origin is the center of circle put (h=0, k=0)

x2 + y2 = r2 (Pythagoras theorem)

Here it needs to be decided whether to select N or S.

Also, We know that in a circle distance between centre of circle and any point on the circle is same for
all the points on the circle and it is equal to its radius.

And also

x2 + y2 = r2 (Pythagoras theorem)
Further, For pixel N this distance is

D(N)= (xk+1)2 + (yk)2

Further, For pixel S this distance is

D(S)= (xk+1)2 + (yk-1)2

However, The distance between actual circle and the centre is r.

The main concept

Bresenham’s Circle Drawing Algorithm chooses pixel which minimizes the square of the distance
between one of these pixels and the true circle. Further, Actually squaring is done just to avoid square
root calculations.

Lets represent it by E.

36
E(N)= {D(N)}2 – r2
Also, E(S)= {D(S)}2 – r2
We should remember that for this particular case or we can say for this octant the value of E(N) will
always be positive because N is out-side the circle and the value of E(S) will always be negative because
S is inside the circle.

Now, lets calculate decision parameter Dk in a simpler way,

Dk = E(N)+E(S)
If Dk < 0, it implies E(S)>E(N), since E(S) is negative, that again implies that point N is closer to the
circle than point S. So pixel N is our next pixel. (xk+1, yk)
If Dk > 0 means E(N)>E(S) and since E(N) is positive, that again implies that point S is closer to
the circle than point N. So pixel S is our next pixel. (xk+1, yk-1).
Calculating Decision parameter

Now lets derive Dk

Dk = (xk+1)2 + (yk)2 – r2 + (xk+1)2 + (yk-1)2 – r2 which can also be written as,
= 2(xk + 1)2 + (yk)2 + (yk -1)2 – 2r2 —– (i)
Now lets find Dk+1 also,
So, Replacing every k with k+1

Dk+1 = 2(xk+1 + 1)2 +(yk+1)2 + (yk+1 -1)2 – 2r2

(Replacing xk+1 with xk + 1 but now we can’t replace yk+1 because we don’t know the exact value
of yk )
= 2(xk+1+ 1)2 + (yk+1)2 + (yk+1 -1)2 – 2r2 which can also be written as
= 2(xk+2)2 + (yk+1)2 + (yk+1 -1)2 – 2r2 —– (ii)
Calculating Decision parameter for next pixel

Now to find out the decision parameter of next pixel i.e. Dk+1
We need to find

Dk+1 – Dk = (ii) – (i)

= 2(xk+2)2 + (yk+1)2 + (yk+1 -1)2 – 2r2
– [ 2(xk + 1)2 + (yk)2 + (yk -1)2 – 2r2] Simplify further,
= 2(xk) + 8xk + 8 + (yk+1)2 + (yk+1)2 – 2yk+1 + 1 – 2r2
2

– 2(xk )2– 4xk– 2 – (yk)2 – (yk)2 + 2yk– 1 + 2r2 Then we get,

= 4xk + 2(yk+1)2 – 2yk+1 – 2(yk)2 + 2yk + 6
Dk+1 = Dk + 4xk + 2(yk+1)2 – 2yk+1 – 2(yk)2 + 2yk + 6 —– (iii)
If (Dk < 0) then we will choose N point as discussed i.e. (xk+1,yk)
Then, yk+1 = yk, putting yk in (iii) in place of yk+1
So, we get Dk+1 =Dk + 4xk + 2(yk)2 – 2yk – 2(yk)2 + 2yk + 6
= Dk + 4xk + 6
If (Dk > 0) then we will choose S point i.e. (xk+1,yk-1)
yk+1 = yk-1putting yk-1in (iii) in place of yk+1
Hence, Dk+1 = Dk + 4xk + 2(yk -1)2 – 2(yk -1)- 2(yk)2 + 2yk + 6
= Dk + 4xk + 2(yk)2 + 2 – 4yk– 2yk +2- 2(yk)2 + 2yk + 6 So now we get,
= Dk + 4xk – 4yk + 10
37
 =Dk + 4(xk – yk)+ 10
Initial decision Parameter

Take starting point (0,r) ,value of y is r

Putting (0,r) in (i)
Dk = 2(xk + 1)2 + (yk)2 + (yk -1)2 – 2r2
So, D0 = 2(0+ 1)2 + r2 + (r-1)2 – 2r2
= 2 + r2 +r2 + 1 – 2r – 2r2 Simplifying further we get,
= 3-2r
So this is the complete Bresenham’s Circle drawing technique.
Remember we have assumed that centre is at origin. Now its the time to shift circle to its actual position.
We will actually translate the circle by adding centre coordinates to each calculated point.

Procedure-
Given-
• Centre pointof Circle = (X0, Y0)
• Radius of Circle = R

The points generation using Bresenham Circle Drawing Algorithm involves the following steps-

Step-01:
Assign the starting point coordinates (X0, Y0) as-
• X0 =0
• Y0 = R

Step-02:
Calculate the value of initial decision parameter P0 as-
P0 = 3 – 2 x R
Step-03:

Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
Find the next point of the first octant depending on the value of decision parameter Pk.
Follow the below two cases-

38
Step-04:
If the given centre point (X0, Y0) is not (0, 0), then do the following and plot the point-
• Xplot = Xc + X0
• Yplot = Yc + Y0

Here, (Xc, Yc) denotes the current value of X and Y coordinates.

Step-05:
Keep repeating Step-03 and Step-04 until Xplot => Yplot.

Step-06:
Step-05 generates all the points for one octant.
To find the points for other seven octants, follow the eight symmetry property of circle.

Problem-01:

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

Solution-

Given-
39
 • Centre Coordinates of Circle (X0, Y0) = (0, 0)
• Radius of Circle = 8

Step-01:

Assign the starting point coordinates (X0, Y0) as-

• X0 =0
• Y0 = R = 8

Step-02:

Calculate the value of initial decision parameter P0 as-

P0 = 3 – 2 x R
P0 = 3 – 2 x 8
P0 = -13

Step-03:

As Pinitial < 0, so case-01 is satisfied.

Thus,
• Xk+1 = Xk + 1 = 0 + 1 = 1
• Yk+1 = Yk = 8
• Pk+1 = Pk + 4 x Xk+1 + 6 = -13 + (4 x 1) + 6 = -3

Step-04:

This step is not applicable here as the given centre point coordinates is (0, 0).

Step-05:

Step-03 is executed similarly until Xk+1 >= Yk+1 as follows-

40
 Problem-02:

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

Solution-

Given-
• Centre Coordinates of Circle (X0, Y0) = (10, 10)
• Radius of Circle = 10

Step-01:

Assign the starting point coordinates (X0, Y0) as-

• X0 = 0
• Y0 = R = 10

Step-02:

41
Calculate the value of initial decision parameter P0 as-
P0 = 3 – 2 x R
P0 = 3 – 2 x 10
P0 = -17

Step-03:

As Pinitial < 0, so case-01 is satisfied.

Thus,
• Xk+1 = Xk + 1 = 0 + 1 = 1
• Yk+1 = Yk = 10
• Pk+1 = Pk + 4 x Xk+1 + 6 = -17 + (4 x 1) + 6 = -7

Step-04:

This step is applicable here as the given centre point coordinates is (10, 10).

Xplot = Xc + X0 = 1 + 10 = 11
Yplot = Yc + Y0 = 10 + 10 = 20

Step-05:

Step-03 and Step-04 are executed similarly until Xplot => Yplot as follows-

42
43
19