CST 304- COMPUTER GRAPHICS &

IMAGE PROCESSING
SLOT B, CREDIT 4
Prepared by : Asha Baby
AP in CSE VJEC

CST 304-CGIP AB 1
COURSE OUTCOMES

TRACE KTU

CST 304-CGIP AB 2
 Syllabus

TRACE KTU

CST 304-CGIP AB 3

3
 TRACE KTU

CST 304-CGIP AB 4

4
 TRACE KTU

CST 304-CGIP AB 5
 MODULE I

Module – 1(Basics of Computer graphics and Algorithms)

• Basics of Computer Graphics and its applications.

TRACE KTU
• 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.
CST 304-CGIP AB 6

6
 Basic concepts in Computer Graphics

• Computer graphics is an art of drawing pictures on computer screens with the

help of programming.

• It involves computations, creation and manipulation of data.

TRACE KTU
Basically there are two types of computer graphics

• Interactive computer graphics

• Non interactive computer graphics

CST 304-CGIP AB 7

7
Interactive Computer Graphics:

• Interactive computer graphics work using the concept of two-

way communication between computer and users.

•
TRACE KTU
The computer will receive signals from the input device, and the picture is
modified accordingly.

• Picture will be changed quickly when we apply command.

• In interactive Computer Graphics user have some controls over the

picture, i.e., the user can make any change in the produced image.
CST 304-CGIP AB 8
 • One example of it is the ping-pong game.

Advantages:

• Higher Quality
•
•
•
TRACE KTU
More precise results or products
Greater Productivity
Significantly enhances our ability to understand data and to perceive trends.

CST 304-CGIP AB 9

9
 Non-Interactive or Passive Computer Graphics:

• In non-interactive computer graphics, the picture is produced

on the monitor, and the user does not have any controlled over
the image, i.e., the user cannot make any change in the rendered
image.
TRACE KTU
• One example of its Titles shown on T.V.

• Non-interactive Graphics involves only one-way communication

between the computer and the user, User can see the produced
image, and he cannot make any change in the image.
CST 304-CGIP AB 10
 Application of Computer Graphics
Education and Training
• Computer-generated model of the physical, financial and economic system is often
used as educational aids.

• Model of physical systems, physiological system, population trends or equipment can

TRACE KTU
help trainees to understand the operation of the system.

• For some training applications, particular systems are designed. For example Flight
Simulator.

CST 304-CGIP AB 11

1
1
• Flight Simulator:

• It helps in giving training to the pilots of airplanes.

• These pilots spend much of their training not in a real aircraft

but on the ground at the controls of a Flight Simulator.

• Use in Biology:
TRACE KTU
• Molecular biologist can display a picture of molecules and gain
insight into their structure with the help of computer graphics.

CST 304-CGIP AB 12
 Computer-Generated Maps:
• Town planners and transportation engineers can use computer-generated maps
which display data useful to them in their planning work.

Architect:

TRACE KTU
• Architect can explore an alternative solution to design problems at an
interactive graphics terminal.

• In this way, they can test many more solutions that would not be possible
without the computer.

CST 304-CGIP AB 13

30-08-2020 )
CS401- COMPUTER GRAPHICS(Asha Baby,VJEC 10
Presentation Graphics:

• Example of presentation Graphics are bar charts, line graphs, pie charts and other
displays showing relationships between multiple parameters.

TRACE KTU
• Presentation Graphics is commonly used to summarize, financial reports,
statistical reports, mathematical reports, scientific reports, economic Data for
research reports, managerial reports, consumer information bulletins, and other
types of reports.

CST 304-CGIP AB 14
 Computer Art:
• Computer Graphics are also used in the field of commercial arts.
• It is used to generate television and advertising commercial.

Entertainment

TRACE KTU
• Computer graphics are now commonly used in making motion pictures,
music videos and television shows.

CST 304-CGIP AB 15
 Visualization:

• It is used for visualization of scientists, engineers, medical personnel,

business analysts for the study of a large amount of information.

Educational Software:

TRACE KTU
• Computer Graphics is used in the development of
software for making computer-aided instruction.
educational

CST 304-CGIP AB 16
Printing Technology:
 Computer Graphics is used for printing technology and textile design.

Example of Computer Graphics Packages:

• LOGO
• COREL DRAW
• AUTO CAD
• 3D STUDIO
• CORE
TRACE KTU
• GKS (Graphics Kernel System)
• PHIGS
• CAM (Computer Graphics Metafile)
• CGI (Computer Graphics Interface)

CST 304-CGIP AB 17
 Pixel
• Pixel is the smallest element of an image.

• Each pixel correspond to any one value.

• In an 8-bit gray scale image, the value of the pixel between 0 and 255.

•
TRACE KTU
The value of a pixel at any point correspond to the intensity of the light
photons striking at that point.

• Each pixel store a value proportional to the light intensity at that

particular location.
CST 304-CGIP AB 18
 In the first picture, there may be thousands of pixels, that together make up this image.
TRACE KTU
We will zoom that image to the extent that we are able to see some pixels division.

It is shown in the image below.

CST 304-CGIP AB 19
 Calculation of total number of pixels

• We have define an image as a two dimensional signal or matrix.

• Then in that case the number of PEL would be equal to the number of rows
multiply with number of columns.
TRACE KTU
• This can be mathematically represented as below:
Total number of pixels = number of rows ( X ) number of columns

CST 304-CGIP AB 20
 Gray level

• The value of the pixel at any point denotes the intensity of image
at that location, and that is also known as gray level.

TRACE KTU

CST 304-CGIP AB 21
 Pixel value
• Each pixel can have only one value and each value denotes the intensity of light
at that point of the image.
• The value 0 means absence of light. It means that 0 denotes dark, and it further
means that when ever a pixel has a value of 0, it means at that point, black color
would be formed.
• Have a look at this image matrix

TRACE KTU
0
0
0
0
0
0
0 0 0

• Total no of pixels = total no. of rows X total no. of columns

= 3×3 = 9 pixels.
CST 304-CGIP AB 22
 • An image would be formed with 9 pixels, and that image would have a dimension
of 3 rows and 3 column and most importantly that image would be black.

• The resulting image that would be made would be something like this
TRACE KTU

CST 304-CGIP AB 23
 • Aspect ratio is the ratio of the width of an image to the height of the image.

• This ratio is expressed as x:y, and differs in case of different images used in
photography, television, computer applications and so on.

TRACE KTU
• The resolution of an image is the total number of pixels displayed on your
computer or television screen.

• Generally, the higher the resolution, the higher is the quality of the image.

CST 304-CGIP AB 24
 Aspect ratio Resolution

Ratio of the width of an image to the Total number of pixels displayed on

height of the image (x:y). your computer or television screen
without overlap.

4:3,16:9
TRACE KTU
The common aspect ratios used are The common monitor resolutions
are 640x480, 800x600 and
1024x768.

CST 304-CGIP AB 25
Input devices
• The input devices are the hardware that is used to transfer input to the
computer.

• The data can be in the form of text, graphics, sound, and text.

TRACE KTU
• Output device display data from the memory of the computer.

• Output can be text, numeric data, line, polygon, and other objects.

CST 304-CGIP AB 26
 Output devices

Following are some of the important output devices used in a computer.

Display devices
Graphic Plotter
Printer TRACE KTU

CST 304-CGIP AB 27
 Display devices
• The display device is an output device used to represent the information in the
form of images (visual form).

• Display systems are mostly called a video monitor or Video display unit (VDU).

TRACE KTU
• The purpose of display technology is to simplify information sharing.

• Today, the demand for high-quality displays is increasing.

CST 304-CGIP AB 28
 Display devices

• Cathode-Ray Tube(CRT)
• Color CRT Monitor
• Liquid crystal display(LCD)
•
•
•
TRACE KTU
Light Emitting Diode(LED)
Direct View Storage Tubes(DVST)
Plasma Display
• 3D Display

CST 304-CGIP AB 29
 Cathode-Ray Tube(CRT)

• The primary output device in a graphics system is a video monitor.

• The operations of the video monitors is based on the standard cathode ray tubes
design.
• A CRT is an electronic tube designed to display electrical data.
TRACE KTU
The basic CRT consists of 4 major components
• Electron gun
• Focusing and accelerating anode
• Horizontal and vertical deflection plates
• Evacuated glass envelop

CST 304-CGIP AB 30
 TRACE KTU

CST 304-CGIP AB 31
 • A beam of electrons (cathode rays), emitted by an electron gun, passes through
focusing and deflection systems that direct the beam toward specified positions on
the phosphor coated screen.

• The phosphor then 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.
TRACE KTU
• One way to keep the phosphor glowing is to redraw the picture repeatedly by
quickly directing the electron beam back over the same points.

• This type of display is called a refresh CRT

CST 304-CGIP AB 32
 TRACE KTU

CST 304-CGIP AB 33
 • The primary components of an electron gun in a CRT are the heated metal
cathode and a control grid.

• Heat is supplied to the cathode by directing a current through a coil of wire,

called the filament, inside the cylindrical cathode structure.

TRACE KTU
• This causes electrons to be ‘boiled off" the hot cathode surface.

• In the vacuum inside the CRT envelope, the free, negatively charged electrons are
then accelerated toward the phosphor coating by a high positive voltage.

CST 304-CGIP AB 34
 • The accelerating voltage can be generated with a positively
charged metal coating on the inside of the CRT envelope near
the phosphor screen, or an accelerating anode can be used.

• Sometimes the electron gun is built to contain the accelerating

TRACE KTU
anode and focusing system within the same unit.

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

CST 304-CGIP AB 35
 • Since the amount of light emitted by the phosphor coating depends on the number
of electrons striking the screen, we control the brightness of a display by varying
the voltage on the control grid.

• The focusing system in a CRT is needed to force the electron beam to converge
into a small spot as it strikes the phosphor.

TRACE KTU
• Otherwise, the electrons would repel each other, and the beam would spread out as
it approaches the screen.

• Focusing is accomplished with either electric or magnetic fields. Electrostatic

focusing is commonly used in television and computer graphics monitors.

CST 304-CGIP AB 36
 • As with focusing, deflection of the electron beam can be controlled either with
electric fields or with magnetic fields.

• Different kinds of phosphors are available for use in a CRT. Besides color, a major
difference between phosphors is their persistence, how long they continue to

TRACE KTU
emit light after the CRT beam is removed.

• Persistence is defined as the time it takes the emitted light from the screen to
decay to one-tenth of its original intensity.

CST 304-CGIP AB 37
 • Lower persistence phosphors require higher refresh rates to
maintain a picture on the screen without flicker.

• A phosphor with low persistence is useful for animation, a

high-persistence phosphor is useful for displaying highly
complex, static pictures.

TRACE KTU
• Although some phosphors have a persistence greater than 1
second, graphics monitors are usually constructed with a
persistence in the range from 10 to 60 microseconds.

CST 304-CGIP AB 38
 • The maximum number of points that can be displayed without overlap on a CRT
is referred to as the resolution.

• A more precise definition of resolution is the number of points per centimeter

that can be plotted horizontally and vertically, although it is often simply stated as
the total number of points in each direction.

TRACE KTU
• Resolution of a CRT is dependent on the type of phosphor, the intensity to be
displayed, and the focusing and deflection systems.

CST 304-CGIP AB 39
 • Typical resolution on high-quality systems is 1280 by 1024, with
higher resolutions available on many systems.
• High- resolution systems are often referred to as high-definition
systems.

• Another property of video monitors is aspect ratio.

TRACE KTU
• It is the ratio of the width of an image to the height of the image

CST 304-CGIP AB 40
 • (Sometimes aspect ratio is stated in terms of the ratio of
horizontal to vertical points.)

• An aspect ratio of 3/4 means that a vertical line plotted

with three points has the same length as a horizontal line
plotted with four points

TRACE KTU

CST 304-CGIP AB 41
 There are two ways by which we can display an object on the screen.
Raster scan display and random scan display

Raster scan display

• The most common type of graphics monitor employing a CRT is the raster-scan display,

TRACE KTU
based on television technology.

• In a raster-scan system, the electron beam is swept across the screen, one row at a time
from top to bottom.

• As the electron beam moves across each row, the beam intensity is turned on and off to
create a pattern of illuminated spots.
CST 304-CGIP AB 42
 • Picture definition is stored in a memory area called the refresh
buffer or frame buffer.

• This memory area holds the set of intensity values for all the
screen points.

TRACE KTU
• Stored intensity values are then retrieved from the refresh buffer
and "painted" on the screen one row (scan line) at a time .

• Each screen point is referred to as a pixel or pel (shortened forms

of picture element).

CST 304-CGIP AB 43
 TRACE KTU

CST 304-CGIP AB 44
 • Raster scan display used in home television sets and printers.

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

TRACE KTU
• For a bilevel system, a bit value of 1 indicates that the electron beam is to be
turn on at that position, and a value of 0 indicates that the beam intensity is to be
off.

CST 304-CGIP AB 45
 • Additional bits are needed when color and intensity variations
can be displayed.

• Up to 24 bits per pixel are included in high-quality systems,

which can require several megabytes of storage for the frame
buffer, depending on the resolution of the system.

TRACE KTU
• A system with 24 bits per pixel and a screen resolution 1024 by
1024 requires 3 megabytes of storage for the frame buffer.

CST 304-CGIP AB 46
 • On a black-and-white system with one bit per pixel, the frame buffer is commonly
called a bitmap.

• For systems with multiple bits per pixel, the frame buffer is referred to as a
pixmap.
TRACE KTU
• Refreshingon raster-scan displays is carried out at the rate of 60 to 80 frames
per second, although some systems are designed for higher refresh rates.

CST 304-CGIP AB 47
 • Sometimes, refresh rates are described in units of cycles per
second, or Hertz (Hz), where a cycle corresponds to one frame.

• Using these units, we would describe a refresh rate of 60 frames

per second as simply 60 Hz.
TRACE KTU
• 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.

CST 304-CGIP AB 48
 • The return to the left of the screen, after refreshing each scan
line, is called the horizontal retrace of the electron beam.

• And at the end of each frame (displayed in 1/80th to 1/60th of a

TRACE KTU
second), the electron beam returns (vertical retrace) to the top
left comer of the screen to begin the next frame.

CST 304-CGIP AB 49
 Random scan display

• When operated as random scan display unit, a CRT has the electron beam directed
only to the parts of the screen where a picture is to be drawn.

• Random scan monitors draw a picture one line at a time and for this reason are

TRACE KTU
also referred to as vector displays.

• A pen plotter operates in a similar way and is an example of a random-scan, hard-

copy device.

CST 304-CGIP AB 50
• Refresh rate on a random scan system depends on the number of
lines to be displayed.

• Picture definition is now stored as a set of line drawing commands

TRACE KTU
in an area of memory referred to as the refresh display file.

• Sometimes the refresh display file is called the display list,

display program, or simply the refresh buffer

CST 304-CGIP AB 51
 TRACE KTU

CST 304-CGIP AB 52
 • To display a specified picture, the system cycles through the set of commandsin the
display file, drawing each component line in turn.

• After all line drawing commands have been processed, the system cycles back to
the first line command in the list.

TRACE KTU
• Random scan displays are designed to draw all the component lines of a picture 30
to 60 times each second.

• Random scan systems are designed for line drawing applications and can not
display realistic shaded scenes.

CST 304-CGIP AB 53
 • Since picture definition is stored as a set of line drawing
instructions and not as a set of intensity values for all screen
points, vector displays generally have higher resolution than raster
systems.

TRACE KTU
• Also vector displays produce smooth line drawings because the
CRT beam directly follows the line path.

CST 304-CGIP AB 54
 TRACE KTU

CST 304-CGIP AB 55
 RASTER SCAN SYSTEMS

TRACE KTU

CST 304-CGIP AB 56
 • Interactive raster graphics systems typically employ several processing units.

• In addition to the central processing unit, or CPU, a special-purpose processor,

called the video controller or display controller, is used to control the operation
TRACE KTU
of the display device.

• The frame buffer can be anywhere in the system memory, and the video
controller accesses the frame buffer to refresh the screen.

CST 304-CGIP AB 57
 Video Controller

TRACE KTU

CST 304-CGIP AB 58
 • 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

TRACE KTU
Cartesian coordinates.

• For many graphics monitors, the coordinate origin is defined at the lower left
screen corner .

CST 304-CGIP AB 59
 • The screen surface is then 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 top.

• Scan lines are then labeled from ymax at the top of the screen to 0
at the bottom.

TRACE KTU
• Along each scan line, screen pixel positions are labeled from 0 to
xmax

CST 304-CGIP AB 60
 Basic refresh operations
• Two registers are used to store the coordinates of the screen pixels.

• Initially, the x register is set to 0 and the y register is set to ymax .

•
TRACE KTU
The value stored in the frame buffer for this 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.
CST 304-CGIP AB 61
 • 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.
TRACE KTU
• 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.

CST 304-CGIP AB 62
 • Since the screen must be refreshed at the rate of 60 frames per second, the simple
procedure cannot be accommodated by typical RAM chips.

• The cycle time is too slow. To speed up pixel processing, video controllers can
retrieve multiple pixel values from the refresh buffer on each pass.

TRACE KTU
• The multiple pixel intensities are then stored in a separate register and used to
control the CRT beam intensity for a group of adjacent pixels.

• When that group of pixels has been processed, the next block of pixel values is
retrieved from the frame buffer.

CST 304-CGIP AB 63
 TRACE KTU

CST 304-CGIP AB 64
 • In addition to the CPU ,the raster graphics system is also contains a separate
display processor, referred to as graphics controller and 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.

CST 304-CGIP AB 65
 RANDOM SCAN SYSTEMS

CST 304-CGIP AB 66
 • It is also known as vector system.

• 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.
CST 304-CGIP AB 67
 • 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.

CST 304-CGIP AB 68
 Suppose you have a raster system designed using an 8 inches × 10 inches screen
with a resolution of 100 pixels per inch in each direction. What frame buffer size is
required if 6 bits are stored per pixel in the buffer? (4)

CST 304-CGIP AB 69
Answer

 Here, resolution = 8 inch X 10 inch

 First, we convert it in pixel then Now resolution = 8 X 100 by 10 X
100 pixel = 800
 X 1000 pixel
 1 pixel can store 6 bits
 So, frame buffer size required = 800 X 1000 X6 bits = 600,000 bytes
= 𝟔× 𝟏𝟎5bytes.
 8

CST 304-CGIP AB 70
 Color CRT Monitors

• 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 for producing color displays with a CRT are the beam-
penetration method and the shadow-mask method.

CST 304-CGIP AB 71
 The beam penetration method

• It is used with random scan monitors.

• Two layers of phosphor, usually red and green, are coated onto the inside of the
CRT screen, and 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.
CST 304-CGIP AB 72
 • At intermediate beam speeds, combinations of red and green light are emitted to
show two additional colors, orange and yellow.

• The screen color at any point, is controlled by the beam acceleration voltage.

• Beam penetration has been an inexpensive way to produce color in random scan
monitors.

• But only four colors are possible, and the quality of pictures is not as good as
with other methods.

CST 304-CGIP AB 73
 Shadow-mask methods

• It is commonly used in raster scan systems (including 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.
CST 304-CGIP AB 74
 Delta-delta shadow mask method

CST 304-CGIP AB 75
 • Commonly used in color CRT systems.

• 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.
CST 304-CGIP AB 76
 • We obtain color variations in a shadow mask CRT by varying the intensity levels of the
three electron beams.

• By turning off the red and green guns, we get only the color coming from the blue
phosphor.

• Other combinations of beam intensities produce a small light spot for each pixel position,
since our eyes tend to merge the three colors into one composite.

CST 304-CGIP AB 77
• 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 is produced with the green and red dots only, magenta is
produced with the blue and red dots, and cyan shows up when
blue and green are activated equally.

CST 304-CGIP AB 78
 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.

• One, the primary gun, is used to store the picture pattern;

• Second, the flood gun, maintains the picture display.

CST 304-CGIP AB 79
Advantages over refresh CRT
• Very complex pictures can be displayed at very high resolutions
without flicker.

Disadvantages of DVST systems

• They do not display color.

• The erasing and redrawing process can take several seconds for a
complex picture.

CST 304-CGIP AB 80
POINTS AND LINES

• Line drawing is accomplished by calculating intermediate positions along the line

path between two specified endpoint positions.

• The Cartesian slope-intercept equation for a straight line is

y=m.x+b → equation 1

m→ slope of the line

b→ y intercept
• Given that , the two endpoints of a line segment are specified at positions (x1, y1)
and (x2, y2)
m = y2 - y1 / x2 - x1 → equation 2, m=Δy/Δx → equation 3
b =y1- m.x1 → equation 4
81

CST 304-CGIP 8
AB 1
 82

CST 304-CGIP 8
AB 2
Digital Differential Analyzer(DDA)
• Algorithms for displaying straight lines are based on the line equation 1,2 and 3.
• The digital differential analyzer (DDA) is a scan conversion line algorithm based on calculating
either Δy or Δx.
• We sample the line at unit intervals in one coordinate and determine corresponding integer
values nearest the line path for the other coordinate.
Consider first a line with positive slope (the lines are processed from left to right)
• If the slope is less than or equal to 1(m<=1),
we sample at unit x intervals (Δx = 1) and compute each successive y value as
yk+1 = yk +m
xk+1 = xk +1
y values must be rounded to the nearest integer.
• Subscript k takes integer values starting from 1, for the first point, and increases by 1 until the final
endpoint is reached. Since m can be any real number between 0 and 1, the calculated
83
y values must
be rounded to the nearest integer CST 304-CGIP 8
AB 3
• (The lines are processed from right to left)
Δx = -1 and
yk+1 = yk – m

For lines with a positive slope greater than 1(m>1)

we reverse the roles of x and y. That is, we sample at unit y intervals (Δ y = 1) and calculate
each succeeding x value as
xk+1 = xk + 1/m
yk+1 = yk +1
• If this processing is reversed, so that the starting endpoint is at the right, then either we have
Δy= -1 and
xk+1 = xk -1/m
84

CST 304-CGIP 8
AB 4
Step1 : Start
Step 2: Enter starting and ending points of a line (x1 , y1 ) and (x2 ,y2 ) respectively.
Step 3: Calculate dx = (x2-x1) , dy =( y2-y1 ) declare the variables step, k , xinc , yinc
and initialize x= x1, y= y1 , plot( x, y)
Step 4:Check abs (dx) > abs (dy) , if it is true,
calculate step = abs (dx)
else step = abs (dy)
Step 5: xinc=dx/step
yinc =dy/step
assign x = x1
assign y = y1
Step 6:SetPixel (x, y)
Step 7:for(k=0;k<step;k++)
x=x+xinc
y=y+yinc
plot the points (x, y) until k=step, plot the nearest integer value.
Step 8: stop
85

CST 304-CGIP 8
AB 5
Sample questions

• Using DDA algorithm plot the line with end points (20,10) and (30,18)
• Scan convert the line segment with end points (30,20) and (15,10) using DDAline
drawing algorithm . (University qstn 3 M)

86

CST 304-CGIP 8
AB 6
• Scan convert the line segment with end points (20,10) and (30,18) using DDA.

• X1=20 y1=10 x2=30 y2=18 k (x,y)

0 (21,10.8)
• dx= 10 dy= 8
1 (22,11.6)
• X= 20 y=10
2 (23,12.4)
• Abs(dx)>abs(dy) step = 10 3 (24,13.2)
• Xinc= 10/10 =1 4 (25,14)
• Yinc= 8/10=.8 5 (26,14.8)
6 (27,15.6)
• For k=0 k<10 k++
7 (28,16.4)
8 (29,17.2)
87
9 (30,18)
CST 304-CGIP 8
AB 7
• Scan convert the line segment with end points (30,20) and (15,10) using DDA line
drawing algorithm . (University question 4 M) k (x,y)
x1= 30 , y1= 20 x2= 15, y2=10 0 (29,19.34)
1 (28,18.68)
dx=-15 dy=-10
2 (27,18,02)
abs(dx) > abs(dy) 3 (26,17.36)
abs(-15) > abs(-10) 4 (25,16.7)

Step=15 5 (24,16.04)
6 (23,15.38)
xinc= -15/15 = -1
7 (22,14.72)
yinc= -10/15 = -0.66 8 (21,14.06)
9 (20,13.4)
10 (19,12.74)
11 (18,12.08)
12 (17,11.42)
CST 304-CGIP AB 88
13 (16,10.76)
22-09-2020 CS 401CG-Asha Baby 10
14 (15,10.1)
Advantage:
• It is a faster method than method of using direct use of line equation y=m.x+b.
• It eliminates the multiplication by making use of raster characteristics , so that
appropriate increments are applied in the x or y direction to step to pixel positions
along the line path.
• It is an easy method because each step involves just two additions.
Disadvantage:
• It involves floating point additions rounding off is done. Accumulations of round off
error cause accumulation of error.
• Rounding off operations and floating point operations consumes a lot of time.
• It is more suitable for generating line using the software. But it is less suited for
hardware implementation.
89

CST 304-CGIP
AB
Bresenham's Line Algorithm

• This algorithm is used for scan converting a line.

• It was developed by Bresenham.
• It is an efficient method because it involves only integer addition, subtractions,
and multiplication operations.
• These operations can be performed very rapidly so lines can be generated quickly.

90

CST 304-CGIP
AB
 91

CST 304-CGIP
AB
• Consider the scan conversion process for lines with positive slopes less than 1
• Starting from the left end- point (x0 , y0) of a given line, we step to each successive column (x
position) and plot the pixel whose scan line y value is closest to the linepath.
• Assuming we have determined that the pixel at (xk , yk) is to be displayed, we next need to decide
which pixel to plot in column xk+1. Two choices are the pixels at positions (xk+1, yk) and (xk+1, yk +1).
• We know that , y=m.x+b
y=m(xk+1)+b
then d1 = y-yk
= m(xk+1)+b – yk
d2 = ( yk +1)-y
= ( yk +1)-(m(xk+1)+b)

The difference between these two separations is ,

d1 - d2 = m(xk+1)+b – yk - ( yk +1)-(m(xk+1)+b)
= 2m(xk+1)-2 yk +2b-1 →equation1 92

CST 304-CGIP
AB
 93

CST 304-CGIP
AB
 94

CST 304-CGIP
AB
 95

CST 304-CGIP
AB
• If the pixel at yk is closer to the line path than the pixel at yk +1(that is,
d1 <d2 ,), then decision parameter pk is negative.
• In that case, we plot the lower pixel otherwise, we plot the upper
pixel.

96

CST 304-CGIP
AB
 97

CST 304-CGIP
AB
• Consider the scan conversion process for lines with positive slopes
greater than 1
• For a line with positive slope greater than 1, we interchange the roles of the x and y
directions.
• That is, we step along the y direction in unit steps and calculate successive x values
nearest the line path.

98

CST 304-CGIP
AB
• Using bresenham’s line drawing algorithm plot the line with the endpoints (20,10)
and (30,18).
• Calculate the points between the starting coordinates (9, 18) and ending
coordinates (14, 22) using bresenham’s line drawing algorithm .
• Consider the line from (5, 5) to (13, 9). Use the Bresenham's algorithm to rasterize
the line.

99

CST 304-CGIP
AB
• Calculate the points between the starting coordinates (9, 18) and ending
coordinates (14, 22) using bresenham’s line drawing algorithm.
• m=dy/dx dy=4 dx= 5
• m=4/5 = 0.8
• 2dy = 8 , 2dx=10 k pk (xk+[Link]+1)
• P0=2dy-dx 8-5= 3 0 3 (10,19)
1 1 (11,20)
• p1=p0+2dy-2dx = 3+8-10=1
2 -1 (12,20)
• P2=p1+2dy-2dx = 1+-2=-1
3 7 (13,21)
• P3= p2+2dy = -1+8=7 4 5 (14,22)
• P4= p3+8-10 = 7+-2=5

100

CST 304-CGIP
AB
• Using bresenham’s line drawing algorithm plot the line with the endpoints (20,10)
and (30,18).
• calculate m= dy/dx
dy=8 dx=10
k pk (xk+1,yk+1)
m=8/10
0 6 (21,11)
=.8 1 2 (22,12)
2dy= 16 , 2dx=20 2 -2 (23,12)
3 14 (24,13)
4 10 (25,14)
5 6 (26,15)
6 2 (27,16)
7 -2 (28,16)
8 14 (29,17)
9 10 (30,18)
101

CST 304-CGIP
AB
Advantages of Bresenham Line Drawing
Algorithm
•It is easy to implement.
•It is fast and incremental.
•It executes fast but less faster than DDAAlgorithm.
•The points generated by this algorithm are more accurate than DDAAlgorithm.
•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.
CST 304-CGIP AB 102

22-09-2020 CS 401CG-Asha Baby 24

Circle generating algorithm

Properties of Circles
• A circle is defined as the set of points that are all at a given distance r from a
center position (xc,yc).
• This distance relationship is expressed by the Pythagorean theorem in Cartesian
coordinates as,
(𝒙 − 𝐱c)2 +(𝒚 − 𝐲c)2=r2
We can use this equation to calculate the positions of points on a circle by stepping
along the x axis in unit steps and calculating the corresponding y values at each po
sition as ,
y=yc+-√ r2 -(𝒙 − 𝐱c)2
But this is not the best method for getting a circle.
103

CST 304-CGIP
AB
y

𝐲c
(𝐱c, 𝐲c)

0,0 𝐱c x

104

CST 304-CGIP
AB
• One problem with this approach is that it involves considerable computation at each
step.
• Another method is to calculate the points along the circular boundary using polar
coordinates r and θ.
• Expressing the circle equation in parametric polar form yields the pair of equation.
x=xc+r cos θ
y=yc+r sin θ
• This equation require more computing time, because it involves multiplication and
square root calculation while the parametric equation contains multiplication and
trigonometric calculation.
• So we have 2 circle generating algorithm Midpoint circle algorithm, Bresenham’s
algorithm.
105

CST 304-CGIP
AB
Midpoint circle drawing algorithm

Principle of the midpoint

• Computation can be reduced by considering the symmetry of circles.
• The shape of the circle is similar in each quadrant.
• Circle sections in adjacent octants within one quadrant are symmetric with respect
to the 45 degree line dividing the two octants.

106

CST 304-CGIP
AB
• Taking advantage of the circle symmetry we can generate all pixel positions
around a circle by calculating only the points within the sector from x=0 to x=y.

107

CST 304-CGIP
AB
• To apply the midpoint method, we define a circle function:
fcircle(x,y)= x2+y2-r2
• The relative position of any point (x,y) can be determined by checking the sign of the
circle function.
• fcircle(x,y)= { <0 , if(x,y) is inside the circle boundary
=0, if(x,y) is on the circle boundary
>0, if(x,y) is outside the circle boundary
• 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.
• 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.
• Our decision parameter is the circle function evaluated at the midpoint between these two
pixels.

108

CST 304-CGIP
AB
• Find the values from one octant of a circle centered at (0,0), then find the
remaining octants by symmetry, then translate to (xc,yc).
• The circle function is the decision parameter.
• Calculate the circle function for the midpoint between two pixels.
• If pk<0, midpoint is inside the circle and yk is closer , we select yk
• If pk>=0, midpoint is outside or on the circle and yk-1 is closer, we select yk-1

109

CST 304-CGIP
AB
 110

CST 304-CGIP
AB
 111

CST 304-CGIP
AB
 112

CST 304-CGIP
AB
Algorithm
[Link] radius r and circle center (xc,yc), then set the coordinates for the first point on the
circumference of a circle centered on the origin as
(x0, y0) = (0, r)
[Link] the initial value of the decision parameter as p0 = 5/4 – r (take this value
as 1-r)
[Link] each xk, from k=0, perform the following test:
if pk<0, next point to plot along the circle centered on (0,0) is (xk +1, yk) and
p +1 = p + 2 x + 1
k k k+1
otherwise, next point to plot is (xk + 1, yk - 1) and pk +1= pk + 2 xk+1 + 1-2 yk+1 2 xk+1
where = 2 xk + 2, and 2 yk+1 = 2 yk– 2
4. Determine symmetry points in the other seven octants.
5. Move each calculated pixel position (x, y) onto the circular path centered at (xc , yc) and
plot the coordinate values: x = x + xc , y = y + yc
[Link] steps 3 through 5 until x >= y.

113

CST 304-CGIP
AB
Sample questions

• The center coordinates are (0, 0), and the radius of the circle is 10. Find all points
of the circle by using the midpoint circle drawing algorithm?
• Given the center point coordinates (4, 4) and radius as 10, generate all the points
to form a circle.
• Use mid-point circle drawing algorithm to plot a circle whose radius =20 units and
center at (50,30) (5M).

114

CST 304-CGIP
AB
The center coordinates are (0, 0), and the radius of the circle is 10. Find all points
of the circle by using the midpoint circle drawing algorithm?

• Initial point =(0,10)

• p0=(1-r) (1-10) = -9 next point(1,10) p1= -9+2+1=-6
• Next point(2,10) p2=-6+4+1=-1
• Next point(3,10) p3=-1+6+1= 6
• Next point (4,9) p4=6+8+1-18=-3
• Next point (5,9) p5= -3+10+1=8
• Next point(6,8) p6=8+12+1-16=5

115

CST 304-CGIP
AB
k Pk (xk+1, yk+1) 2xk+1 2yk+1
0 -9 (1,10) 2 20

1 -6 (2,10) 4 20

2 -1 (3,10) 6 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

116

CST 304-CGIP
AB
Q1(x,y) Q2(-x,y) Q3(-x,-y) Q4(x,-y)
(1,10) (-1,10) (-1,-10) (1,-10)
(2,10) (-2,10) (-2,-10) (2,-10)
(3,10) (-3,10) (-3,-10) (3,-10)
(4,9) (-4,9) (-4,-9) (4,-9)
(5,9) (-5,9) (-5,-9) (5,-9)
(6,8) (-6,8) (-6,-8) (6,-8)
(7,7) (-7,7) (-7,-7) (7,-7)
(8,6) (-8,6) (-8,-6) (8,-6)
(9,5) (-9,5) (-9,-5) (9,-5)
(9,4) (-9,4) (-9,-4) (9,-4)
(10,3) (-10,3) (-10,-3) (10,-3)
(10,2) (-10,2) (-10,-2) (10,-2)
(10,1) (-10,1) (-10,-1) (10,-1)

117

CST 304-CGIP
AB
Q1(x,y) Q2(-x,y) Q3(-x,-y) Q4(x,-y)

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

118

CST 304-CGIP
AB
Given the center point coordinates (4, 4) and radius as 10, generate all the points to
form a circle.

• We first calculate the points assuming the center coordinates is (0, 0).
• At the end, we translate the circle.
• Problem same as previous
• Already calculated (x,y) values for all quadrant. Now, we find the values of
Xplot andYplot
• Xplot = Xc +X
• Yplot = Yc + Y

119

CST 304-CGIP
AB
Circle center (4,4)

k Pk (xk+1, yk+1) 2xk+1 2yk+1

0 -9 (5,14) 2 20

1 -6 (6,14) 4 20

2 -1 (7,14) 6 20

3 6 (8,13) 8 18

4 -3 (9,13) 10 18

5 8 (10,12) 12 16

6 5 (11,11) 14 14

120

CST 304-CGIP
AB
Advantages
• 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
• The 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

121

CST 304-CGIP
AB
Bresenhams circle drawing algorithm

[Link] radius r and circle center (xc,yc), then set the coordinates for the first point
on the circumference of a circle centered on the origin as
(x0, y0) = (0, r)
2. Calculate the initial value of the decision parameter as p0 = 3-2r
3. At each xk, from k=0, perform the following test:
if pk<0, next point to plot along the circle centered on (0,0) is (xk +1, yk) and
p +1 = p + 4 x + 6
k k k
otherwise, next point to plot is (xk + 1, yk - 1) and pk +1= pk + 4( xk – yk )+10
4. Determine symmetry points in the other seven octants.
[Link] each calculated pixel position (x, y) onto the circular path centered at (xc ,
yc) and plot the coordinate values: x = x + xc , y = y + yc
6. Repeat steps 3 through 5 until x >= y.
122

CST 304-CGIP
AB
The center coordinates are (0, 0), and the radius of the circle is 10. Find all points
of the circle by using the midpoint circle drawing algorithm?

k pk (xk+1,
yk+1 )
0 -17 (1,10)
1 -11 (2,10)
2 -1 (3,10)
3 13 (4,9)
4 -5 (5,9)
5 17 (6,8)
6 11 (7,7)

123

CST 304-CGIP
AB
University questions…

 Distinguish between raster scan display and random scan display.

 What do you understand about the aspect ratio and resolution of a

display screen in a raster scan display?

 Explain the working of a random scan display system with a

suitable diagram.

 Explain the working of a beam penetration CRT.

 Explain the working of direct view storage tubes(DVST).

CST 304-CGIP AB 124
 Consider a raster system with a resolution of 2560*2048.
Determine the frame buffer size (in bytes) needed for the system
to store 12-bits per pixel. How much storage is required if 24-bits
per pixel are to be stored?

 Explain the working of a delta-delta shadow mask CRT.

 What is the use of computer graphics? List out and explain any 5
applications of computer graphics.

 Draw and explain the architecture of simple raster graphics

systems.

CST 304-CGIP AB 125

 Define the following terms.
Persistence.
Resolution.
Aspect ratio.
Frame buffer.

 Describe in detail the basic video controller refresh operation

used in interactive raster graphics systems.

 Explain the working of the cathode ray tube in detail.

 What is the role of a display controller in a raster scan display

system? Explain.
CST 304-CGIP AB 126
 Explain the functioning of a random scan display system.

 With a neat diagram describe the working of a cathode ray

display device.

 Write the methods used to plot a dashed line segment.

 Using the midpoint circle drawing algorithm find out the first
quadrant point of a circle from x=0 to x=y where r=10. Also draw
the complete circle using the same.

 Using both DDA and Bresenhams’s line drawing algorithm, plot

the line with endpoints (20,15) and (34,20).

CST 304-CGIP AB 127

 How 8-way symmetric points if (x,y) is a point on the circle with
centre at origin.

 Write the DDA line drawing algorithm.

 Rasterize the line segment from pixel coordinate (1,1) to (8,5)

using Bresenham’s line drawing algorithm.

 Write the midpoint circle drawing algorithm.

 Use midpoint circle drawing algorithm to plot a circle whose

radius =20 units and center is (50,30)

 What are the advantages and disadvantages of the DDA

algorithm?

CST 304-CGIP AB 128

 Describe the DDA line drawing algorithm. Use the algorithm to
find the coordinate along the line joining the pixel positions
(5,12) and (15,20).

 Explain DDA line drawing algorithm with examples.

 Explain the midpoint circle drawing algorithm. Find the pixel

locations approximately the first octant of a circle having centre
(10,13) and radius of 5 units using this algorithm.

 Describe simple random scan display system and draw its

architecture.
CST 304-CGIP AB 129
 With a suitable figure, describe the shadow masking techniques in
CRT.

 Compare the working principle of raster scan systems and

random scan systems.

 How much time is spent scanning across each row of pixels

during screen refresh on a raster system with resolution of
1280*1024 and a refresh rate of 60 frames per second?

 Rasterize the line with end points(2,3) and (5,8) using

Bresenham’s line drawing algorithm.
CST 304-CGIP AB 130