Unit 1: Introduction

BCA 5th Semester

Compiled by: Parash Mani Bhandari 1

 1. Introduction to Computer
Graphics
• Computer Graphics is a field related to the generation
of graphics using computers.
• Computer graphics are graphics created using
computers and the representation of image data by a
computer specifically with help from specialized
graphic hardware and software.
• It includes the creation, storage, and manipulation of
images of objects .
• These objects come from diverse fields such as
physical, mathematical, engineering, architectural,
abstract structures and natural phenomenon.

Compiled by: Parash Mani Bhandari 2

 1. Introduction to Computer
Graphics
• Graphics refers to any sketch, drawing, special art
work to pictorially depict (represent) an object or
process instead of written descriptions.
• The sketch may be a cartoon or landscape
building, electrical network or human anatomy.
• It may be just a few regular lines, 2D or 3D
drawing. In computer graphics pictures or graphic
object is taken as a collection of discrete picture
elements called pixels.
Compiled by: Parash Mani Bhandari 3
 1. Introduction to Computer
Graphics
• Computer Graphics
– Generative Graphics (used to create line, circle,
ellipse)
– Image Analysis (used to generation of pictures,
images)
– Lognitive (used for photographic images)

Compiled by: Parash Mani Bhandari 4

 Main Tasks
• Imaging:
– Formation of an image.
– Representation of 2D images.
• Modeling:
– Representing 3D images.
• Rendering:
– Constructing 2D images from 3D models.
• Animation:
– Stimulating changes over time.
– Describing how objects change in time.

Compiled by: Parash Mani Bhandari 5

 2. Application Areas of Computer
Graphics
• Computer Aided Design (CAD)
• Presentation Graphics
• Computer Art
• Entertainment
• Education and Training
• Visualization
• Image Processing
• Graphical User Interfaces (GUI)
• Simulation
• Cartography

Compiled by: Parash Mani Bhandari 6

2.1. Computer Aided Design (CAD)

• In CAD, graphics is used to design components and

systems of mechanical, electrical, electro-mechanical and
electronic devices including structures such as buildings,
automobile bodies, airplane, VLSI chips, optical systems
and telephone and computer networks.

Compiled by: Parash Mani Bhandari 7

2.1. Computer Aided Design (CAD)…..

• Objects are displayed in wireframe outline that shows

the overall shape and internal features of objects.

Compiled by: Parash Mani Bhandari 8

2.1. Computer Aided Design (CAD)…..
• Architects use computer graphics to layout floor plans that
shows positioning of rooms, doors, windows, stairs, shelves
and other building features. Electrical designers then try out
arrangements for wiring, electrical outlets and other system to
determine space utilization on a building.

Compiled by: Parash Mani Bhandari 9

 2.2. Presentation Graphics
• Presentation Graphics is commonly used to summarize
financial, statistical, mathematical, scientific and economic
data for research reports, managerial reports and other types
of reports.

Compiled by: Parash Mani Bhandari 10

 2.2. Presentation Graphics…..

• Typical examples are bar charts, line graphs, surface

graphs, pie charts and other displays showing
relationship between multiple variables.

Compiled by: Parash Mani Bhandari 11

 2.2. Presentation Graphics…..

• The 3D graphics are usually used simply for effects; they

can provide a more diagrammatic or more attractive
presentation of data relationship.

Compiled by: Parash Mani Bhandari 12

 2.3. Computer Art
• Computer graphics is used to generate arts.

Compiled by: Parash Mani Bhandari 13

 2.3. Computer Art
• They are widely used in both fine art and commercial art
applications. Fine art is drawn by artist hand and this kind of
art is perfect to the artist skill. Artist use a variety of computer
methods including special purpose hardware, artist's paints
brush program, other paint packages, specially developed
software.

Compiled by: Parash Mani Bhandari 14

 2.3. Computer Art
• Mathematics packages, CAD packages, desktop publishing
software and animation packages providing facilities.

Compiled by: Parash Mani Bhandari 15

 2.4. Entertainment and Gaming
• Computer graphics methods are new commonly used in
making motion pictures, music videos and TV shows.

Compiled by: Parash Mani Bhandari 16

 2.4. Entertainment and Gaming
• Images are drawn in wire-frame form and will be shaded with
rendering methods to produce solid surfaces. Music videos
use graphics in several ways.

Compiled by: Parash Mani Bhandari 17

 2.4. Entertainment and Gaming
• Computer graphics are also used to introduce virtual
characters to movies like character in “Lord of the Rings”.

Compiled by: Parash Mani Bhandari 18

 2.5. Education and Training….
• Computer graphics is used in education and training for
making it more effective and more illustrative.

Compiled by: Parash Mani Bhandari 19

 2.5. Education and Training…..
• Computer generated models of physical, financial, and
economic systems are often used as educational aids. A
student can learn surgery using data gloves and realistic
computer graphics.

Compiled by: Parash Mani Bhandari 20

 2.6. Visualization
• Visualization is the process of visually representing the data.
To visualize large amount of information graphical computer
systems are used.
• Some methods generate very large amount of
data/information, analysis the property of the whole amount
of data is very difficult. Visualization simplifies the analysis of
data by using graphical representation.

Compiled by: Parash Mani Bhandari 21

2.6. Visualization…..

Compiled by: Parash Mani Bhandari 22

2.6. Visualization…..

Compiled by: Parash Mani Bhandari 23

 2.7. Image Processing
• Image can be created using simple point program or can be
fed into computer by scanning the image. These picture/
images need to be changed to improve the quality.
• Form image/pattern recognition systems, images need to be
changed in specified format so that the system can recognize
the meaning of the picture.
• Currently computer graphics is widely used for image
processing.

Compiled by: Parash Mani Bhandari 24

2.7. Image Processing….

Compiled by: Parash Mani Bhandari 25

2.7. Image Processing….

Compiled by: Parash Mani Bhandari 26

2.7. Image Processing….

Compiled by: Parash Mani Bhandari 27

2.7. Image Processing….

Compiled by: Parash Mani Bhandari 28

 2.8. Graphical User Interfaces
(GUI)
• GUIs have become key factors for the success of the software
or operating system.
• GUI provides point-and-click facilities to allow users to select
menu items, icons, and objects on the screen.
• Word processing, spreadsheet, and desktop-publishing
programs are typical applications that take advantage of user-
interface technique.

Compiled by: Parash Mani Bhandari 29

2.8. Graphical User Interfaces
(GUI)…..

Compiled by: Parash Mani Bhandari 30

2.8. Graphical User Interfaces
(GUI)…..

31

Compiled by: Parash Mani Bhandari 31

 2.9. Simulation
• A representation of a problem, situation, etc. in mathematical
terms, using a computer is called simulation.
• Computer Simulation is the process of mapping the real-world
scenarios into mathematical model using computer graphics.
• Recently computer graphics is widely used to create simulated
environment.
• E.g.; Robot Operation Simulation, Pilot Training, Military
Training etc.

Compiled by: Parash Mani Bhandari 32

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 33

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 34

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 35

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 36

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 37

2.9. Simulation…..

Compiled by: Parash Mani Bhandari 38

 2.10. Cartography
• Cartography is the study and practice of designing maps using
computer graphics.
• Computer graphics is used to produce both accurate and
schematic representations of geographical and other natural
phenomena from measurement data.
• Examples include geographic maps, exploration maps, for
drilling and mining, oceanographic charts, weather maps etc.

Compiled by: Parash Mani Bhandari 39

2.10. Cartography…..

Compiled by: Parash Mani Bhandari 40

3. Advantage of Computer Graphics
1. A high quality graphics displays of personal computer provide one
of the most natural means of communicating with a computer.
2. It has an ability to show moving pictures, and thus it is possible to
produce animations with computer graphics.
3. With computer graphics use can also control the animation by
adjusting the speed, the portion of the total scene in view, the
geometric relationship of the objects in the scene to one another,
the amount of detail shown and so on.
4. The computer graphics also provides facility called update
dynamics. With update dynamics it is possible to change the
shape, color or other properties of the objects being viewed.
5. With the recent development of digital signal processing (DSP)
and audio synthesis chip the interactive graphics can now provide
audio feedback along with the graphical feedbacks to make the
simulated environment even more realistic.

Compiled by: Parash Mani Bhandari 41

Basic Concept
• RASTER : A rectangular array of points or dots.
• PIXEL (picture element) :One dot or picture element of the
raster
• SCAN LINE : A row of pixels
• BITMAP :ones and zeros representation of the rectangular
array points on screen
• Black and white :- bitmap
• Pixmap :- color (colored raster image)

Compiled by: Parash Mani Bhandari 42

• A rectangular array of points or dots.

Compiled by: Parash Mani Bhandari 43

• One dot or picture element of the raster
• The pixel (a word invented from "picture element") is the basic
unit of programmable color on a computer display or in a
computer image

Compiled by: Parash Mani Bhandari 44

Compiled by: Parash Mani Bhandari 45
Compiled by: Parash Mani Bhandari 46
Compiled by: Parash Mani Bhandari 47
• ones and zeros representation of the rectangular array points
on screen
• Black and white :- bitmap
• Pixmap :- color (colored raster image)

Compiled by: Parash Mani Bhandari 48

• Vector graphics is the creation of digital images through a
sequence of commands or mathematical statements that
place lines and shapes in a given two-dimensional or three-
dimensional space. In physics, a vector is a representation of
both a quantity and a direction at the same time.

Compiled by: Parash Mani Bhandari 49

• Vector graphics are based on vectors, which lead through
locations called control points or nodes. Each of these points
has a definite position on the x- and y-axes of the work plane
and determines the direction of the path; further, each path
may be assigned various attributes, including such values as
stroke color, shape, curve, thickness, and fill

Compiled by: Parash Mani Bhandari 50

• The maximum number of points (pixel) that can be displayed
without overlap on a CRT is referred to as the resolution.
• It is also defined as the number of points per unit of measure
(per centimeter or per inch) that can be plotted horizontally
and vertically.
• Resolution is defined as the maximum member of points that can be
displayed horizontally and vertically without overlap on a display
device.

Compiled by: Parash Mani Bhandari 51

Compiled by: Parash Mani Bhandari 52
Compiled by: Parash Mani Bhandari 53
Compiled by: Parash Mani Bhandari 54
• The aspect ratio of an image describes the proportional relationship
between its width and its height.
• It is commonly expressed as two numbers separated by a colon, as
in 16:9. For an x:y aspect ratio, no matter how big or small the image
is, if the width is divided into x units of equal length and the height is
measured using this same length unit, the height will be measured
to be y units.
• In, for example, a group of images that all have an aspect ratio of
16:9, one image might be 16 inches wide and 9 inches high, another
16 centimeters wide and 9 centimeters high, and a third might be 8
yards wide and 4.5 yards high.

Compiled by: Parash Mani Bhandari 55

Compiled by: Parash Mani Bhandari 56
• It means how long they continue to emit light after the
electron 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.
• Lower persistence phosphors require higher refresh rates to
maintain a picture on the screen.
• A phosphor with lower persistence is useful for animation and
a higher–persistence phosphor is useful for displaying highly
complex static picture.
• Graphics monitor are usually constructed with the persistence
10 to 60 microseconds.

Compiled by: Parash Mani Bhandari 57

• The number of times the screen is redrawn each second.
• Higher refresh rates mean less flicker on the screen, which
translates into less eyestrain.

Compiled by: Parash Mani Bhandari 58

Compiled by: Parash Mani Bhandari 59
Compiled by: Parash Mani Bhandari 60
Compiled by: Parash Mani Bhandari 61
• Mouse, Touch Screen, Light Pen, Data Glove, Tablet (Digitizer),
Bar Code Reader

Compiled by: Parash Mani Bhandari 62

• A mouse is a small hand-held device used to position the
cursor on the screen.
• Mouse are relative devices, that is, they can be picked up,
moved in space, and then put down gain without any change
in the reported position.
• Types
• Mechanical mouse
• Optical mouse

Compiled by: Parash Mani Bhandari 63

• Touch panels are a sensitive surface that is used to point
directly. The panel can be touched by finger or any other
object like stylus. Transparent touch panels are integrated with
computer monitor for the manipulation of information display.
A basic touch panel senses voltage drop when a user touches
the panel. It knows where the voltage has dropped and
accordingly calculates the touch position.

Compiled by: Parash Mani Bhandari 64

• a computer input device in the form of a light sensitive wand
used in conjunction with a computer's CRT TV set or monitor
• works by sensing the sudden small change in brightness of a
point on the screen when the electron gun refreshes that spot
• Light pens have the advantage of 'drawing' directly onto the
screen, but this can become uncomfortable, and they are not
as accurate as digitizing tablets

Compiled by: Parash Mani Bhandari 65

Compiled by: Parash Mani Bhandari 66
Compiled by: Parash Mani Bhandari 67
• Constructed with a series of sensors that can detect hand and
finger motions.
• The transmitting and receiving antennas can be structured as
a set of three mutually perpendicular cols, forming a three
dimensional Cartesian coordinates system.
• Electromagnetic coupling between the three pairs of coil is
used to provide information about the position and
orientation of hand.

Compiled by: Parash Mani Bhandari 68

Compiled by: Parash Mani Bhandari 69
Compiled by: Parash Mani Bhandari 70
Compiled by: Parash Mani Bhandari 71
• A tablet is digitizer.
• In general a digitizer is a device which is used to scan over an
object, and to input a set of discrete coordinate positions.
• No keyboard, no mouse. Instead, you have an LCD screen and
a stylus
• You don't need to convert handwriting to text
• Tablets are gaining popularity as a replacement for the
computer mouse as a pointing device

Compiled by: Parash Mani Bhandari 72

Compiled by: Parash Mani Bhandari 73
Compiled by: Parash Mani Bhandari 74
Compiled by: Parash Mani Bhandari 75
• A bar code is a machine-readable code in the form of a pattern
of parallel vertical lines.
• They are commonly used for labeling gods that are available in
supermarkets, numbering books in libraries etc.
• These codes are sensed and read by a photoelectric device
called bar code reader that reads the code by means of
reflected light.
• The information recorded in a bar code reader is fed into the
computer, which recognizes the information from the
thickness and spacing of bars.

Compiled by: Parash Mani Bhandari 76

• The most common graphics output device is the video
monitor which is based on the standard cathode ray tube
(CRT) design, but several other technologies exist such as
LCDs, LEDs, the direct view storage tube(DVST) etc.

Compiled by: Parash Mani Bhandari 77

• CRT are the most common display devices on computer today.
• A CRT is an evacuated glass tube, with a heating element on
one end and a phosphor-coated screen on the other end.
• When a current flows through this heating element (filament)
the conductivity of metal is reduced due to high temperature.
These cause electrons to pile up on the filament.
• These electrons are attracted to a strong positive charge from
the outer surface of the focusing anode cylinder.
• The forwarding fast electron beam is called Cathode Ray. A
cathode ray tube is shown in figure below.

Compiled by: Parash Mani Bhandari 78

Compiled by: Parash Mani Bhandari 79
• The cathode ray tube (CRT) is a tube containing one or more
electron guns (a source of electron) and a fluorescent screen
used to view images.
• 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.
• When the electrons hit the screen, the phosphor emits visible
light.
• Because the light emitted by the phosphor decays very rapidly
with time, so the entire picture must be refreshed (redrawn)
many times per second by quickly directing the electron beam
back over the same points.
• Therefore, also called a refresh CRT.
Compiled by: Parash Mani Bhandari 80
Compiled by: Parash Mani Bhandari 81
Compiled by: Parash Mani Bhandari 82
• There are two sets of weakly charged deflection plates with
oppositely charged, one positive and another negative. The first
set displaces the beam up and down and the second displaces
the beam left and right.
• The electrons are sent flying out of the neck of bottle (tube) until
the smash into the phosphor coating on the other end.
• When electrons strike on phosphor coating, the phosphor then
emits a small spot of light at each position contacted by electron
beam. The glowing positions are used to represent the picture in
the screen.
• The amount of light emitted by the phosphor coating depends on
the no of electrons striking the screen. The brightness of the
display is controlled by varying the voltage on the control grid.

Compiled by: Parash Mani Bhandari 83

2.1.1Main Components of CRT
• An electron gun
• The primary components of an electron gun in a CRT are the heated metal
cathode and a control grid.
• Heated metal cathode: Heat is supplied to the cathode by directing the beam through a
coil of wire called the filament inside the cylindrical cathode structure.
• Control grid: Intensity of the electron beam is controlled by setting the voltage levels on

Mohan Bhandari (BCA-CG)

the control grid, which is a metal cylinder that fits to the cathode.

• Focusing System & Accelerating Anode

• The focusing system in a CRT is needed to force the electron beam to converge
into a small spot as it strikes the phosphor.
• And the accelerating anode is used to accelerate electron beam towards the
phosphor coated screen. Otherwise, the electron beam would not reach to the
screen.
• Deflection System
• It is used to control the vertical and horizontal scanning of the electron beam.
84

Compiled by: Parash Mani Bhandari 84

2.1.1 Properties of CRT
• Persistence
• Resolution
• Aspect Ratio

Compiled by: Parash Mani Bhandari 85

2.1.1. Types of Refresh CRT’s
1. Raster-Scan Displays
2. Random-Scan Displays

Compiled by: Parash Mani Bhandari 86

2.1.1.1. Raster-Scan Displays
• The most common type of graphics monitor employing a CRT
is the raster-scan display. In raster scan approach, the viewing
screen is divided into a large number of discrete phosphor
picture elements, called pixels. Row of pixels is called the scan
line. The matrix of pixels or collection of scan lines constitutes
the raster (shown in figure below).

Compiled by: Parash Mani Bhandari 87

2.1.1.1. Raster-Scan Displays
• Two types of Raster-scan systems:
Non-interlaced Raster-Scan System:
In non-interlaced refresh procedure, electron beam sweeps
over entire scan lines in a frame from top to bottom in one
pass.
Interlaced Raster-Scan System:
In interlaced scan, each frame is displayed in two passes. First
pass for odd scan lines and another for even ones.

Compiled by: Parash Mani Bhandari 88

Architecture of Raster Scan System

• The raster graphics systems typically consists of several processing

units. CPU is the main processing unit of computer systems. Besides
CPU, graphics system consists of a special purpose processor called
video controller or display processor. The display processor controls
the operation of the display device.
• A fixed area of system memory is reserved for the frame buffer. The
video controller has the direct access to the frame buffer for
refreshing the screen.

Compiled by: Parash Mani Bhandari 89

Architecture of Raster-Scan Display Processor
• The display processor has its own separate memory called display
processor memory.
• System memory holds data and those programs that execute on
the CPU, and the application program, graphics packages and
OS.
• The display processor memory holds data plus the program that
perform scan conversion and raster operations.
• The frame buffer stores displayable image created by scan
conversion and raster operations.

Compiled by: Parash Mani Bhandari 90

2.1.1.1. Random-Scan Displays
• In a random scan display unit, electron beam directed
towards 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 also referred to as vector displays
(or stroke-writing or calligraphic displays).
• Random scan system uses an electron beam which
operates like a pencil to create a line image on the CRT.
• The component line can be drawn or refreshed by a
random scan display system in any specified order

Compiled by: Parash Mani Bhandari 91

 2.1.1.1. Random-Scan Displays

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

hard-copy device Compiled by: Parash Mani Bhandari 92
Architecture of Random Scan Display

Compiled by: Parash Mani Bhandari 93

Architecture of Random Scan Display…..

• Vector display system consists of several units along with

peripheral devices. The display processor is also called as
graphics controller.
• Graphics package creates a display list and stores in systems
memory (consists of points and line drawing commands)
called display list or display file.
• Refresh time around so cycle per second.
• Vector display technology is used in monochromatic or beam
penetration color CRT.
• Graphics are drawn on a vector display system by directing the
electron beam along component line.

Compiled by: Parash Mani Bhandari 94

 Raster VS Random
Raster Random
1.Refresh Rates : 1.Refresh Rates :

Refreshing on raster scan display is Generally, refreshing on random-scan

carried out at the rate of 60 to 80 display is carried out at the rate of 60
frames per second. Sometimes, refresh frames per second. Refresh rate on a
rates are described in units of cycles per random-scan system depends on the
second, or Hertz (Hz), where a cycle number of lines to be displayed.
corresponds to one frame. Picture definition is now stored as a set
of line-drawing commands in an area of
memory, referred to as the refresh
display file.
2.Applications: 2.Applications:
i. For the realistic display of scenes i. Random-scan systems are used in
containing subtle shading and color line-drawing applications.
patterns. ii. Vector displays generally used to
ii. Home television sets and printers produce graphics with higher
are examples of raster-scan resolution.
systems. Compiled by: Parash Mani Bhandari 95
 Raster VS Random

Raster Random

Compiled by: Parash Mani Bhandari 96

Raster VS Random

Compiled by: Parash Mani Bhandari 97

• A color 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;
1. Beam Penetration Method
2. Shadow Mask Method

Compiled by: Parash Mani Bhandari 98

2.2.1. Beam Penetration Method
• It is a cheaper method and is used in Vector scan displays.

• In this method the inside section of CRT is coated with red

(outer layer) and green (inner layer) phosphors.
• If the electrons are slow they penetrate only the outer layer
thus emitting red light, and if the electrons are moving fast
they penetrate the outer layer and the inner layer. The
electrons speed is also adjusted in such a way that by
combination of red and green, orange and yellow
color are also produced. The limitation of this method is that
only four colors can be displayed in the screen. Since we have
only four colors the quality of image is diminished.
Compiled by: Parash Mani Bhandari 99
Compiled by: Parash Mani Bhandari 100
2.2.1. Beam Penetration Method……..
• Used with random-scan monitors
• Two layers of phosphor: red and green
• The displayed color depends on how far the electron beam
penetrates into the phosphor layers.
• Only four colors are possible: red, green, orange, and yellow.

ADVANTAGE:
• Economical way to produce colors

LIMITATIONS:
• Generation of only four colors is possible
• Poor picture quality

Compiled by: Parash Mani Bhandari 101

Compiled by: Parash Mani Bhandari 102
Compiled by: Parash Mani Bhandari 103
Compiled by: Parash Mani Bhandari 104
Compiled by: Parash Mani Bhandari 105
Compiled by: Parash Mani Bhandari 106
Compiled by: Parash Mani Bhandari 107
Compiled by: Parash Mani Bhandari 108
Compiled by: Parash Mani Bhandari 109
2.2.2. Shadow Mask Method
• Shadow-mask methods are commonly used in raster-scan systems
(including color TV) because they produce a much wider range of colors
than the beam-penetration method.
• It gives much wider range of colors than a beam penetration method.
• A shadow Mask CRT has three phosphor color dots at each pixel
location. One phosphor dot emits a red light, another emits green light
and the last one emits a blue light.
• This type of CRT also has three electron guns one for each color dot. A
shadow mask grid is installed just behind the phosphor coated screen.
• The three electron beams are deflected and focused as a group onto
the shadow mask, which contains a series of very fine 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 color of pixel is controlled by light of intensity. Different
colors can be obtained by varying the intensity levels.

Compiled by: Parash Mani Bhandari 110

2.2.2. Shadow Mask Method …..

Compiled by: Parash Mani Bhandari 111

2.2.2. Shadow Mask Method …..

Compiled by: Parash Mani Bhandari 112

2.2.2. Shadow Mask Method …..

Compiled by: Parash Mani Bhandari 113

2.2.2. Shadow Mask Method …..

Compiled by: Parash Mani Bhandari 114

2.2.2. Shadow Mask Method …..

Compiled by: Parash Mani Bhandari 115

• The information in the buffer typically consists of color values
for every pixel .
• A frame buffer may be thought of as computer memory
organized as a two dimensional array . with each (x , y)
addressable location corresponding to one pixel.
• Bit planes or bit depth is the number of bit corresponding to
each pixel.

Compiled by: Parash Mani Bhandari 116

Compiled by: Parash Mani Bhandari 117
Compiled by: Parash Mani Bhandari 118
• They are far lighter and thinner than traditional cathode ray
tube (CRT) television sets and video displays and are usually
less than 10 centimeters (3.9 in) thick.
• Sometimes abbreviated as FPD, a flat-panel display is a thin
screen display found on all portable computers and is the new
standard for desktop computers. Unlike (CRT) monitors, flat-
panel displays use liquid-crystal display (LCD) or light-emitting
diode (LED) technology to make them much lighter and
thinner compared to a traditional monitor.
• Types
1. LCD (liquid-crystal display)
2. LED (light-emitting diode)

Compiled by: Parash Mani Bhandari 119

2.3.1. LCD(Liquid-crystal display)
• A liquid-crystal display (LCD) is a flat-panel display or
other electronic visual display that uses the light-modulating
properties of liquid crystals .
• Liquid crystals do not emit light directly.
• LCDs are used in a wide range of applications including computer
monitors, televisions, instrument panels, aircraft cockpit displays,
and indoor and outdoor signage.
• Small LCD screens are common in portable consumer devices such
as digital cameras, watches , calculators ,and mobile telephones ,
including smartphones.

Compiled by: Parash Mani Bhandari 120

How LCD work
• The pixels are controlled in completely different ways in
plasma and LCD screens. In a plasma screen, each pixel is a
tiny fluorescent lamp switched on or off electronically. In
an LCD television, the pixels are switched on or off
electronically using liquid crystals to rotate polarized light

Compiled by: Parash Mani Bhandari 121

How pixels are switched off

1. Light travels from the back of the TV toward the front from a large bright
light.
2. A horizontal polarizing filter in front of the light blocks out all light waves
except those vibrating horizontally.
3. Only light waves vibrating horizontally can get through.
4. A transistor switches off this pixel by switching on the electricity flowing
through its liquid crystal. That makes the crystal straighten out (so it's
completely untwisted), and the light travels straight through it unchanged.
5. Light waves emerge from the liquid crystal still vibrating horizontally.
6. A vertical polarizing filter in front of the liquid crystal blocks out all light
waves except those vibrating vertically. The horizontally vibrating light that
travelled through the liquid crystal cannot get through the vertical filter.
7. No light reaches the screen at this point. In other words, this pixel is dark.

Compiled by: Parash Mani Bhandari 122

How pixels are switched off

Compiled by: Parash Mani Bhandari 123

How pixels are switched on

1. The bright light at the back of the screen shines as before.

2. The horizontal polarizing filter in front of the light blocks out all light
waves except those vibrating horizontally.
3. Only light waves vibrating horizontally can get through.
4. A transistor switches on this pixel by switching off the electricity
flowing through its liquid crystal. That makes the crystal twist. The
twisted crystal rotates light waves by 90° as they travel through it.
5. Light waves that entered the liquid crystal vibrating horizontally
emerge from it vibrating vertically.
6. The vertical polarizing filter in front of the liquid crystal blocks out all
light waves except those vibrating vertically. The vertically vibrating
light that emerged from the liquid crystal can now get through the
vertical filter.
7. The pixel is lit up. A red, blue, or green filter gives the pixel its color.

Compiled by: Parash Mani Bhandari 124

How pixels are switched on

Compiled by: Parash Mani Bhandari 125

Compiled by: Parash Mani Bhandari 126
2.3.1. LED(Light Emitting Diode)

Compiled by: Parash Mani Bhandari 127

Numerical
Q.N.1.: If the pixel values are accessed from the frame buffer
with an average access time (for one single pixel) of 20 ns and
the total resolution of the screen is 1024 X 800 , will there be a
flickering effect seen on the screen ?
 To glow one single pixel takes = 20 ns
To glow all pixel on screen it takes = 1024 X 800 X 20ns
= 16,384,000ns
= 0.01638 second
Now

frequency(F) = 1/T
= 1/0.01638
= 61.05 HZ

since it is above 50times/sec there will be no flickering effect seen on

screen

Compiled by: Parash Mani Bhandari 128

Numerical
Q.N.2:. In case of raster system with resolution 1024 X 1280,
how many pixel could be accessed per second in the system by
a display controller at a rate of 60 frames per second?
what is accessed time per pixel in this system ?
Ans :
1. Pixel accessed :

= 1024 X 1280 X 60 pixel can be

accessed in this system

2. Access time per pixel:

60 times
= 1/(1024 X 1280 X 60 )
= 12.71ns

Compiled by: Parash Mani Bhandari 129

 Numerical
Q.N.3.: How long would it takes to load a 640 X 480 frame
buffer with 12 bit per pixels if 105 bits can be transferred per
second.

Ans :
total size of frame buffer :
= 640 X 480 X 12

it takes = (640 X 480 X 12)/105

*Formula:
Required size of frame= Resolution or total no. of pixel X no. of bit per pixel on screen

Compiled by: Parash Mani Bhandari 130

 Numerical
Q.N.4.: if the total number of intensities achievable out of a
single pixel on the screen is 1024 and the total resolution of
the screen is 1024 X 800 , what will be the required size of
frame buffer in this case for the display purpose ?
Ans :
(Note : 2n = pixel on the screen ) where n= no. of bit on screen

So, 2n = 1024
n = 10 bit

Required size of frame buffer = 10 X 1024 X 800

= 8,192,000 bit

*Formula:
Required size of frame= Resolution or total no. of pixel X no. of bit per pixel on screen
where , single pixel on screen = 2n and n= total no. of intensities out of a single pixel
Compiled by: Parash Mani Bhandari 131
Numerical
Q.N.5.: Consider three different raster system with resolution 640
by 400, 1280 by 1024 and 2560 by 2048. what size frame buffer
(in byte) is needed for each of the system to store 12 bits per pixel
? How much storage is required for each system if 24 bit per pixel
are to be stored.
Ans :
1) for 12 bit per pixel system
the frame buffer(in byte) size needed
a. for 640 by 400 resolution = (640 X 400 X 12)
8
=384000 byte
b. for 1280 by 1024 resolution = (1280 X 1024 X 12)
8
=1966080 byte
c. for 2560 by 2048 resolution = (2560 X 2048 X 12)
8
=7864320 byte

Compiled by: Parash Mani Bhandari 132

 Cont…..

2) for 24 bit per pixel system

the frame buffer(in byte) size needed
a. for 640 by 400 resolution = (640 X 400 X 24)
8
=768000 byte
b. for 1280 by 1024 resolution = (1280 X 1024 X 24)
8
=3932160 byte
c. for 2560 by 2048 resolution = (2560 X 2048 X 24)
8
=15728600byte

Compiled by: Parash Mani Bhandari 133

Numerical
Q.N.6.: Suppose an RGB raster system is to be designed using 8-
inch by 10-inch screen with a resolution of 100 pixels per inch in
each direction . If we wont to store 9 bit per pixel in the frame
buffer . How much storage (in byte) do we need for the frame
buffer ?
Ans :
Size of screen = 8 inch × 10 inch.
Pixel per inch(Resolution) = 100.

Then, Total no of pixels = 8 x100 by 10x100 pixels

= (8*100 X 10*100) pixels
= 8,00,000

Bit per pixel storage = 9

Therefor , total storage required in frame buffer = 8,00,000 X 9 bytes

8
= 9,00,000 bytes

Compiled by: Parash Mani Bhandari 134

Numerical
Q.N.7.: How long would it take to load a 640 by 480 frame buffer
with 12 bits per pixel , if 105 bit can be transferred per second?
How long would it take to lead a 24-bit per pixel frame buffer with
a resolution of 1280 by 1024 using this same transfer rate?

Ans :
 for 640 X 480 frame buffer with 12 bits for pixels
total pixel= 640 X 480 X12
time required = (640 X 480 X12)
105
= 36.864 second
 for 1280 X 1024 frame buffer with 24 bits for pixels
total pixel= 1280 X 1024 X 24
time required = (1280 X 1024 X 24)
105
= 314.57 second

Compiled by: Parash Mani Bhandari 135

Numerical
Q.N.8.: Consider two raster system with resolution of 640 by 480
and 1280 by 1024. how many pixel could be accessed per second
in each of these system by a display controller that refreshes the
screen at the rate of 60 frames per second ? What is the access
time per pixel in each system ?
Ans :
for a raster system with resolution of 640 by 480,
i) No.of pixel accessed per second = 640 X 480 X 60
ii) Total access time = 1/60 = 0.0167
access time per pixel = (0.0167)/(640 X 480 )
= 54.36 ns

for a raster system with resolution of 1280 by 1024,

i) No.of pixel accessed per second = 1280 X 1024 X 60
ii) Total access time = 1/60 = 0.0167
access time per pixel = (0.0167)/(1280 X 1024 )
= 12.7 ns

Compiled by: Parash Mani Bhandari 136

Numerical
Q.N.9.: A raster system can produce a total number of 1024
different level of intensities from a single pixel composed of red,
green and blue phosphor dots. If the resolution of the screen is
1280 X 1024, what will be the required size of frame buffer for the
display purpose?
Ans :
(Note : 2n = pixel on the screen ) where n= no. of pixel

So, 2n = 1024
n = 10 bit

Required size of frame buffer = 10 X 1280 X 1024

= 13107200 bit
= 1638400 byte

Compiled by: Parash Mani Bhandari 137

Numerical
Q.N.10. : A system with 24 bits per pixel and resolution of 1024
by 1024. Calculate the size of frame buffer (in Megabytes).

Ans :

Frame size in bits= 24*1024*1024 bits

Frame size in bytes= 24*1024*1024 / 8 bytes

(since, 8 Bits = 1 Byte)
Frame size in kilobytes= 24*1024*1024 / (8 * 1024 kb)
(since, 1024 Bytes = 1 KB)
So, Frame size in megabytes= 24*1024*1024 / (8*1024*1024) MB
(since, 1024 KB = 1 MB)
= 3 MB.

Compiled by: Parash Mani Bhandari 138

Numerical
Q.N.11. : How Many k bytes does a frame buffer needs in a 600
x 400 pixel ?

Ans :

Resolution is 600 x 400.

Suppose 1 pixel can store n bits
Then, the size of frame buffer = Resolution * bits per pixel
= (600 * 400) * n bits
= 240000 n bits
= 240000 n kb (as 1kb = 1024 bites)
1024 * 8

= 29.30 n k bytes.

Compiled by: Parash Mani Bhandari 139

Numerical
Q.N.12. : Find out the aspect ratio of the raster system using 8 x
10 inches screen and 100 pixel/inch.

Ans :
We know that, Aspect ratio = Width / Height
= 8 x 100 = 4 / 5
10 x 100

So, aspect ratio = 4 : 5.

Compiled by: Parash Mani Bhandari 140

2.4. Concept of Three Dimension
viewing devices

Compiled by: Parash Mani Bhandari 141

• In computer graphics, graphics software refers to a program or
collection of programs that enable a person to manipulate images or
models visually on a computer. Computer graphics can be classified
into distinct categories: raster graphics and vector graphics, with
further 2D and 3d variants.
• Many graphics programs focus exclusively on either vector or raster
graphics, but there are a few that combine them in interesting ways.
It is simple to convert from vector graphics to raster graphics, but
going the other way is harder. Some software attempts to do this.

Compiled by: Parash Mani Bhandari 142

• In addition to static graphics, there are animation and video
editing software. Different types of software are often designed to
edit different types of graphics such as video, photos, and drawings.
The exact sources of graphics may vary for different tasks, but most
can read and write files.
• Most graphics programs have the ability to import and export one or
more graphics file formats, including those formats written for a
particular computer graphics program. Examples of such programs
include Vectr, GIMP, Adobe Photoshop, Pizap, Microsoft
Publisher, Picasa, etc.

Compiled by: Parash Mani Bhandari 143

Compiled by: Parash Mani Bhandari 144
Compiled by: Parash Mani Bhandari 145
Compiled by: Parash Mani Bhandari 146
Compiled by: Parash Mani Bhandari 147
• Interactive graphics allow users to make change over the
displayed objects. Several graphics software packages are now
available. There are two general classifications for graphics
software:
I. General programming packages
II. Special-purpose application packages

Compiled by: Parash Mani Bhandari 148

2.5.1. General programming packages

• contain graphics functions that can be used with high level

programming languages such as C, FORTRAN, Java etc.
Example, Open GL (Graphics library). A general-purpose
graphics package provides users with a variety of functions for
creating and manipulating pictures. These graphic functions
include tools for generating picture components, setting color,
selecting views, and applying transformations.

Compiled by: Parash Mani Bhandari 149

2.5.2. Special-purpose application packages

• Specifically designed for particular applications. Maya,

CINEMA 4D are particularly used for animations, different
types of CAD applications are designed for medical and
business purposes. These are primarily oriented to non-
programmers.

Compiled by: Parash Mani Bhandari 150

Software standards
• Many problems have been encountered due to the plate-form dependency
of the graphic software's. So primary goal of standardized graphics software
is portability. When graphics packages are designed with standard graphics
functions (set of specifications that is independent of any programming
languages), software can be easily moved from one H/W system to another.
And it can be used in different implementations and applications.

Mohan Bhandari (BCA-CG)

• I. Graphical Kernel System (GKS): GKS was the first graphics software
standard adopted by the international standards organization (ISO). It was
originally designed as a 2-dimensional graphics package. GKS supports the
grouping of logically related primitives such as; lines, polygons, character
strings.
• II. Programmer’s Hierarchical Interactive Graphics System (PHIGS): It is an
extension of GKS. Increased capabilities in object modeling, color
specifications, surface rendering, and picture manipulations are provided in
PHIGS. PHIGS include all primitives supported by GKS, in addition it also
151
includes geometric transformations (Scaling, Translation, and Rotation).
• III. PHIGS+: Extension of earlier PHIGS. 3-d surface shading capabilities are
Compiled by: Parash Mani Bhandari 151
added to the PHIGS.
Unit 2: Scan Conversion
Algorithm
B.Sc. CSIT 3rd Semester

Compiled by: Parash Mani Bhandari 152

Compiled by: Parash Mani Bhandari 153
• Points
• Plotted by converting co-ordinate position to appropriate
operations for the output device (e.g.: in CRT monitor, the electron
beam is turned on to illuminate the screen phosphor at the
selected location.)
• Line
• Plotted by calculating intermediate positions along the line
path between two specified endpoint positions.
• Screen locations are referenced with integer values, so plotted
positions may only approximate actual line positions between
two specified endpoints  “the jaggies”. E.g.: position
(10.48,20.51)  (10,21).

Compiled by: Parash Mani Bhandari 154

• Pixel position: referenced by scan line number and column
number

Compiled by: Parash Mani Bhandari 155

 • DDA Algorithm- (Digital Differential Analyzer)
• Bresenham’s Line Algorithm
Note:
• Pixel- picture element smallest piece of information in an
image represented using dots, squares and rectangle
• Components-
• RGB
• or
• 4 components Y Scan Line

(cyan ,magenta,
yellow & black)
Pixel
0
0
Column number X

Compiled by: Parash Mani Bhandari 156

 DDA Algorithm
 Digital Differential Analyzer
Scan-conversion line – algorithm based on calculating either

Sample the line at unit intervals in one coordinate

Determine the corresponding integer values nearest the line
path in another co-ordinate

Compiled by: Parash Mani Bhandari 157

Positive Slope
(Y always increase when X increases and
Y always Decreases when X decrease)

Negative Slope
(Y always increase when X decrease and
Y always Decreases when X increases)

Compiled by: Parash Mani Bhandari 158

Positive Slope
1. Slope less than 1 ( |M| < 1 ) and
moving Left to Right
M=1
Delta x = 1

Xk+1 = Xk + 1 Y2

YK+1 = Yk
Y1

X1 X2

Compiled by: Parash Mani Bhandari 159

Positive Slope
2. Slope less than 1 ( |M| < 1 ) and
moving Right to Left
M=1
Delta x = -1

Xk+1 = Xk - 1
Y2
YK+1 = Yk
Y1

X1 X2

Compiled by: Parash Mani Bhandari 160

Positive Slope
3. Slope greater than 1 ( |M| > 1 ) and
moving Left to Right
M=1

Y2
Xk+1 = Xk + 1/M
YK+1 = Yk Y1

X1 X2

Compiled by: Parash Mani Bhandari 161

Positive Slope
4. Slope Greater than 1 ( |M| > 1 ) and
moving Right to Left
M=1

Y2
Xk+1 = Xk – 1/M
YK+1 = Yk Y1

X1 X2

Compiled by: Parash Mani Bhandari 162

Negative Slope
1. Slope less than 1 ( |M| < 1 ) and
moving Left to Right

M=-1

Xk+1 = Xk + 1
YK+1 = Yk Y1

Y2

X2
X1

Compiled by: Parash Mani Bhandari 163

Negative Slope
2. Slope less than 1 ( |M| < 1 ) and
moving Right to Left

M=-1

Xk+1 = Xk - 1
YK+1 = Yk Y1

Y2

X2
X1

Compiled by: Parash Mani Bhandari 164

Negative Slope
3. Slope greater than 1 ( |M| > 1 ) and
moving Left to Right

M=-1

Y1
Xk+1 = Xk – 1/M
YK+1 = Yk Y2

X1 X2

Compiled by: Parash Mani Bhandari 165

Negative Slope
4. Slope Greater than 1 ( |M| > 1 ) and
moving Right to Left

M=-1
Y1
Xk+1 = Xk +1/M
Y2
YK+1 = Yk

X1 X2

Compiled by: Parash Mani Bhandari 166

DDA

Compiled by: Parash Mani Bhandari 167

DDA Examples
Q.> Digitize a Line with end point A(2,3) and B(6,8) , using DDA.
A.> Here , Slope (M) = (8-3)/(6-2) = 1.25
here Slope is positive and greater than 1
And moving left to right and 1/m = 0.8
Xk+1 = Xk + 1/M
YK+1 = Yk + 1

K Xk+1 = Xk + 1/M YK+1 = Yk + 1 (X,Y)

1 =2 + 0.8 = 2.8 ~ 3 4 (3,4)

2 =2.8 + 0.8= 3.6 ~ 4 5 (4,5)

3 =3.6 + 0.8 = 4.4 ~ 4 6 (4,6)

4 = 4.4 + 0.8 = 5.2 ~ 5 7 (5,7)

5 = 5.2 + 0.8 = 6 Compiled by:8Parash Mani Bhandari

(6,8) 168
DDA Examples
Q.> Digitize a Line with end point A(2,3) and B(6,8) , using DDA
Right to left.

Q.> Digitize a Line with end point A(3,2) and B(8,4) , using DDA

Q.>Digitize a Line with end point A(2,6) and B(4,2) , using DDA

Compiled by: Parash Mani Bhandari 169

1. Digitize the line from A(1,1) to B(10,8) using scan conversion line
algorithm.
2. Draw a line with two end point P(5,3) and Q(1,2) using DDA
3. Digitize the line with endpoints A(1,7) and B(6,3) using digital
differential analyzer line drawing algorithm. Show all necessary
steps. (TU 2013, 3 marks) .
4. Digitize the line with end points (1,2) and (5,6) using digital
differential analyzer method.(TU 2012, 3 marks).
5. Digitize the given line endpoints (1,1) and (5, 5) using DDA.
6. Draw a line using DDA with two end points A(0,0) and B(-10,8).
7. Digitize line with start at (5,3) and end at (1,5) using DDA.
8. Digitize DDA with all necessary steps with two end points (0,0)
and (10,0).

Compiled by: Parash Mani Bhandari 170

Bresenham’s Line Algorithm
The BLA is a more efficient method used to plot pixel
position along a straight-line path.
Advantage of BLA over DDA
• In DDA algorithm each successive point is computed in floating
point, so it requires more time and more memory space. While
in BLA each successive point is calculated in integer value or
whole number. So it requires less time and less memory space.
• In DDA, since the calculated point value is floating point number,
it should be rounded at the end of calculation but in BLA it does
not need to round, so there is no accumulation of rounding error.
• Due to rounding error, the line drawn by DDA algorithm is not
accurate, while in BLA line is accurate.
• DDA algorithm cannot be used in other application except line
drawing, but BLA can be implemented in other application such
as circle, ellipse and other curves.
Compiled by: Parash Mani Bhandari 171
BLA for slope +ve and |m| ≤ 1

+1 +1

+1 +1

+1 +1

Compiled by: Parash Mani Bhandari 172

 Let us assume that pixel (xk, yk) is already
plotted assuming that the sampling direction is
along X-axis i.e. (xk+1, yk) or (xk+1, yk+1). Thus, the
common equation of the line is
y = m(xk+1) + c
Now,

d1 = y - yk = m (xk +1) + c - yk
and
d2 = (yk +1)- y = yk+1– {m (xk +1) + c

Compiled by: Parash Mani Bhandari 173

The difference betn these two separation is,
d1 - d2 = [m (xk +1) + c - yk ] - [yk+1– {m (xk +1) + c }]
Or,
d1- d2 = 2m (xk+1)+ 2c - 2yk -1
Since, slope of line (m) = Δy / Δx,
We have,
Δx (d1- d2) = 2 Δy (xk+1)+ 2 Δx C - 2 Δx Yk – Δx
Define Decision parameter at Kth step,
Pk = Δx (d1- d2)
= 2 Δy (xk+1)+ 2 Δx C - 2 Δx yk – Δx
=2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx

Compiled by: Parash Mani Bhandari 174

Pk=2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx
Now , K+1th term
Pk+1 = 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx

Here,
Pk+1- Pk = 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx – {2 Δy Xk+2
Δy + 2 Δx c - 2 Δx yk – Δx }

= 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx – 2 Δy Xk- 2

Δy - 2 Δx c + 2 Δx yk + Δx
Pk+1 = Pk +2 Δy Xk+1 - 2 Δx yk+1– 2 Δy Xk+ 2 Δx yk

Pk+1 = Pk +2 Δy(Xk+1 – Xk)- 2 Δx(Yk+1– Yk)

Compiled by: Parash Mani Bhandari 175

Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk+1
Yk+1 = Yk

Pk = Pk + 2 Δy

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk+1
Yk+1 = Yk+1

Pk = Pk + 2 Δy -2Δx
Compiled by: Parash Mani Bhandari 176
Initial Decision Parameter (P0)

y = m(xk+1) + c

Let, X0 = 0 , Y0 = 0 then C = 0

Δx (d1- d2) = 2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx

P0 = 0 + 2 Δy + 0 + 0 – Δx

P0 = 2 Δy - Δx

Compiled by: Parash Mani Bhandari 177

Example-1: Digitize the line with end points (20, 10) and (30, 18)
using BLA.
Solution :
Here, Starting point of line = (x1, y1) = (20, 10) and
Ending point of line = (x2, y2) = (30, 18)
Thus, slope of line, m = Δy / Δx = y2-y1 / x2-x1
= (18-10) / (30-20)
= 8/10
As the given points, it is clear that the line is moving left to right
with the positive slop
|m| =

Compiled by: Parash Mani Bhandari 178

Thus,
The initial decision parameter (P0) = 2Δy - Δx = 2*8 – 10 = 6
Since, for the Bresenham’s Line drawing Algorithm of slope, |m| ≤ 1, we have

If Pk < 0 (i.e. d1-d2 is Negative ) If Pk ≥ 0

then, then,
Xk+1 = Xk+1 Xk+1 = Xk+1
Yk+1 = Yk Yk+1 = Yk+1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx
(20, 10)

Compiled by: Parash Mani Bhandari 179

Example-2: Digitize the line with end points (15, 5) and (30, 10)
using BLA.

180

Compiled by: Parash Mani Bhandari 180

Example-3: Digitize the line with end points (20, 5) and (25, 10)
using BLA.

181

Compiled by: Parash Mani Bhandari 181

 BLA for slope +ve and |m| > 1
(Xk, ) (Xk, )

( ,Yk) ( ,Yk)

+1 +1

+1 +1

+1 +1

Compiled by: Parash Mani Bhandari 182

 Let us assume that pixel (xk, yk) is already
plotted assuming that the sampling direction is
along X-axis i.e. (xk, yk+1) or (xk+1, yk+1). Thus, the
common equation of the line is
Y=MX+C
yK+1 = mx + c
X= {yk+1 – c}/m
Now,

d1 = X - Xk = {yk +1 – c}/m - xk
and
d2 = (Xk +1)- X = xk+1– [(yk+1 – c)/m]
Compiled by: Parash Mani Bhandari 183
So,
d1 - d2 = [{(yk +1 – c)/m} - xk] -[xk+1–
{(yk+1 – c)/m }]
Or,
d1 - d2 = 2/m* (yk+1) - 2c/m – 2xk -1
Since, slope of line (m) = Δy / Δx,
we have
Pk = Δy (d1 - d2)
= 2Δx (yk+1) - 2c Δx - 2Δy xk - Δ
Compiled by: Parash Mani Bhandari 184
Pk = 2Δx (yk+1) - 2c Δx - 2Δy xk - Δy
Now , K+1th term
Pk+1 = 2Δx (yk+1+1) - 2c Δx - 2Δy xk+1 – Δy
Here,
Pk+1-Pk = {2Δx (yk+1+1) - 2c Δx - 2Δy xk+1 – Δy} -
{2Δx (yk+1) - 2c Δx - 2Δy xk - Δy}
= 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk)

Pk+1 = Pk + 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk)

Compiled by: Parash Mani Bhandari 185
Pk+1 = Pk + 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk)
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk
Yk+1 = Yk+1

Pk = Pk + 2 Δx

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk+1
Yk+1 = Yk+1

Pk = Pk + 2 Δx -2Δy
Compiled by: Parash Mani Bhandari 186
Initial Decision Parameter (P0)
We Know,
Pk = 2Δx (yk+1) - 2c Δx - 2Δy xk - Δy
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = 2Δx (y0 +1) - 2c Δx - 2Δy x0 - Δ

P0 = 2 Δx - Δy
Compiled by: Parash Mani Bhandari 187
Example-4: Digitize the line with end points (1, 0) and (3,
3) using BLA.
Solution :
Here,
Starting point of line = (x1, y1) = (1, 0) and
Ending point of line = (x2, y2) = (3, 3)
Thus,
slope of line, m = Δy / Δx = y2-y1 / x2-x1
= (3-0) / (3-1)
= 3/2
As the given points, it is clear that the line is moving
left to right with the positive slope,
|m| =
Compiled by: Parash Mani Bhandari 188
Thus, the initial decision parameter
Δx = x2-x1 = 3-1 = 2
(P0) = 2Δx - Δy = 2*2 – 3 = 1 Δy = y2-y1 = 3-0 = 3
we have
If Pk < 0 If Pk ≥ 0
then, then,
Xk+1 = Xk Xk+1 = Xk+1
Yk+1 = Yk+1 Yk+1 = Yk+1
Pk = Pk + 2 Δx Pk = Pk + 2 Δx -2Δy

Compiled by: Parash Mani Bhandari 189

Example-5: Digitize A(5,2) and B(7,8) using BLA.

Compiled by: Parash Mani Bhandari 190

Example
1. Digitize the line A(1,1) and B(5,6) using BLA.
2. Digitize the line A(1,1) and B(5,6) using DDA.
3. Digitize the line A(5,2) and B(7,8) using BLA.
4. Digitize the line A(0,0) and B(10,10) using
BLA.
5. Digitize the line A(1,3) and B(10,10) using
BLA and DDA.

Compiled by: Parash Mani Bhandari 191

 Slope –Ve and |M| ≤ 1
(Xk-1,Yk+1) (Xk-1,Yk+1)
(Xk,Yk+1)

d2
d2
Y
Y

d1
d1

(Xk-1,Yk) (Xk,Yk) (Xk-1,Yk) (Xk,Yk)

d1-d2 > 0 (Positive) d1-d2 < 0 (Negative)

Xk+1 = Xk - 1 Xk+1 = Xk - 1
Yk+1 = Yk +1 Yk+1 = Yk

Compiled by: Parash Mani Bhandari 192

Let us assume that pixel (xk, yk) is already plotted assuming
that the sampling direction is along X-axis i.e. (xk-1, yk+1) or
(xk-1, yk). Thus, the common equation of the line is
Y=Mx + C
Here,
Y= m(Xk-1)+c
Now,
d1=Y-Yk
And
d2= (Yk+1)-Y
Or,
d1-d2= Y-Yk – {(Yk+1)-Y}
= Y-Yk –Yk-1+Y
=2y-2yk -1
=2m(Xk-1)+ 2c - 2yk - 1
Here slope of line (m) = - (Δy / Δx), {for –ve slope)

Compiled by: Parash Mani Bhandari 193

d1- d2 = 2m(Xk-1)+ 2c - 2yk - 1
Now , (m) = - (Δy / Δx),
d1- d2 = -2 {(Δy / Δx)} (Xk-1)+ 2c - 2yk - 1
Δx(d1-d2) = -2 Δy (Xk-1)+ 2 c Δx – 2 Δx Yk - Δx
Here Pk = Δx(d1-d2)
= -2 Δy (Xk-1)+ 2 c Δx – 2 Δx Yk - Δx
Pk = -2 Δy Xk + 2 Δy + 2 c Δx – 2 Δx Yk - Δx
Now k+1 th term
Pk+1 = -2 Δy Xk+1 + 2 Δy + 2 c Δx – 2 Δx Yk+1 - Δx
Or,
Pk+1 – Pk = -2 Δy Xk+1 - 2 Δy + 2 c Δx – 2 Δx Yk+1 - Δx
+2 Δy Xk + 2 Δy - 2 c Δx + 2 Δx Yk + Δx
= -2Δy(Xk+1 - Xk) +2Δx (-Yk+1 + Yk)

Pk+1 = Pk - 2Δy(Xk+1 - Xk) + 2Δx (-Yk+1 + Yk)

Compiled by: Parash Mani Bhandari 194

 Pk+1 = Pk - 2Δy(Xk+1 - Xk) - 2Δx (Yk+1 – Yk)
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk - 1
Yk+1 = Yk

Pk = Pk + 2 Δy

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk - 1
Yk+1 = Yk +1

Pk = Pk + 2 Δy -2 Compiled by: Parash Mani Bhandari 195

Initial Decision Parameter (P0)
We Know,
Pk = -2 Δy Xk + 2 Δy + 2 c Δx – 2 Δx Yk - Δx
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = -2 Δy X0 + 2 Δy + 2 c Δx – 2 Δx Y0

P0 = 2 Δy - Δx
Compiled by: Parash Mani Bhandari 196
 Slope –Ve and |M| > 1
(Xk-1,Yk+1) (Xk,Yk+1)
(Xk,Yk+1) (Xk-1,Yk+1)

d1 d2 d1
d2

(Xk,Yk) (Xk-1,Yk)
(Xk-1,Yk) X X
(Xk,Yk)

d1-d2 > 0 (Positive) d1-d2 < 0 (Negative)

Xk+1 = Xk - 1 Xk+1 = Xk
Yk+1 = Yk +1 Yk+1 = Yk +1

Compiled by: Parash Mani Bhandari 197

Let us assume that pixel (xk, yk) is already plotted assuming that the
sampling direction is along X-axis i.e. (xk-1, yk+1) or (xk, yk +1). Thus, the
common equation of the line is
Y=Mx + C
Here,
Yk +1 = mX+c
X= {Yk +1-C}/M
Now,
d1=Xk-X
Slope –Ve and |M|> 1
And
d2= X-{Xk-1}
Or,
d1-d2 = Xk-X – { X-{Xk-1} }
= Xk-X – X+Xk-1
= 2Xk – 2X -1
= 2Xk -2 {Yk +1-C}/M -1
Here slope of line (m) = - (Δy / Δx), {for –ve slope)

Compiled by: Parash Mani Bhandari 198

d1 – d2 = 2Xk -2 {Yk +1-C}/M -1
= 2Xk -2 {Yk +1-C}/{- (Δy / Δx)} -1
= 2Xk + 2 {Yk +1-C}/{ (Δy / Δx)} -1
Δy (d1 – d2 ) = 2 Δy Xk + 2 Δx {Yk +1-C} - Δy
= 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy
Pk = Δy (d1 – d2 ) for decision parameter
Pk = 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy
Now K+1 th term
Pk+1 = 2 Δy Xk+1 + 2 Δx Yk+1 + 2 Δx - 2 Δx C - Δy
Or,
Pk+1- Pk = 2 Δy Xk+1 + 2 Δx Yk+1 + 2 Δx - 2 Δx C - Δy
- 2 Δy Xk - 2 Δx Yk - 2 Δx + 2 Δx C + Δy
= 2 Δy (Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
199
Pk+1 = Pk +2 Δy (Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
Compiled by: Parash Mani Bhandari 199
 Pk+1 = Pk +2 Δy (Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk
Yk+1 = Yk +1

Pk = Pk + 2 Δx

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk - 1
Yk+1 = Yk +1

Pk = Pk + 2 Δy -2Δx Compiled by: Parash Mani Bhandari 200

Initial Decision Parameter (P0)
We Know,
Pk = 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = 2 Δy X0 + 2 Δx Y0 + 2 Δx - 2 Δx C -

P0 = 2 Δx - Δy
Compiled by: Parash Mani Bhandari 201
Example: Digitize the given line endpoints (5, 10) and (10, 7) using Bresenham’s line
drawing algorithm.(TU 2014)
Solution:
Δx = |5-10| = 5
Here, (X1,Y1)= (10,7) & Δy = |10-7| = 3
(X2,Y2)=(5,10)
here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x3-5
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx
(10, 7)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)

0 1 9 8 (9,8)
1 = 1 + 2x3 - 2x5 =-3 8 8 (8,8)
2 = -3 + 2x3 = 3 7 9 (7,9)
3 = 3 + 2x3 – 2x5 = -1 6 9 (6,9)

4 = -1 + 2x3 = 5 5 10 (5,10)
Compiled by: Parash Mani Bhandari 202
Example: Digitize line with endpoints (3, 10) and (6,2) using Bresenham's Line
DrawingAlgorithm.( TU 2016)
Solution:
Δx = |3-6| = 3
Here, (X1,Y1)= (6,2) & Δy = |10-2| = 8
(X2,Y2)=(3,10)
here,
If Pk < 0 If Pk ≥ 0 Initial (P0) = 2 Δx – Δy
Xk+1 = Xk Xk+1 = Xk - 1 = 2x3-8
Yk+1 = Yk +1 Yk+1 = Yk +1 = -2
Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy

(6, 2)
K PK Xk+1 Yk+1 (Xk+1 ,Yk+1)

0 -2 6 3 (6,3)
1 =-2+2x3 = 4 5 4 (5,4)
2 =4+6-16=-6 5 5 (5,5)
3 =-6+6=0 4 7 (4,7)
4 =0+6-16=-10 4 8 (4,8)
5 =-10+6= -4 4
Compiled by: Parash9Mani Bhandari
(4,9) 203

6 =-4 +6 =2 3 10 (3,10)
Example: Digitize the given line endpoints (15, 15) and (10, 18) using Bresenham’s
line drawingalgorithm.
Solution:
Δx = |10-15| = 5
Here, (X1,Y1)= (15,15) & Δy = |18-15| = 3
(X2,Y2)= (10,18)
here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x3-5
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx
(15, 15)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)

0 1 14 16 (14,16)
1 = 1 + 2x3 - 2x5 =-3 13 16 (13,16)
2 = -3 + 2x3 = 3 12 17 (12,17)
3 = 3 + 2x3 – 2x5 = -1 11 17 (11,17)

4 = -1 + 2x3 = 5 10 18 (10,18)
Compiled by: Parash Mani Bhandari 204
Example: Digitize the given line endpoints (10, 10) and (20, 5) using Bresenham’s
line drawingalgorithm.
Solution:
Δx = |10-20| = 10
Here, (X1,Y1)= (20,5) & Δy = |10-5| = 5
(X2,Y2)= (10,10)
here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x5-10
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =0
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx
(20, 5)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)
0 0 19 6 (19,6)
1 = 0 + 2x5 - 2x10 =-10 18 6 (18,6)
2 = -10 + 2x5 = 0 17 7 (17,7)
3 = 0 + 2x5 - 2x10 =-10 16 7 (16,7)
4 = -10 + 2x5 = 0 15 8 (15,8)
5 = 0 + 2x5 - 2x10 =-10 14 8 (14,8)
6 = -10 + 2x5 = 0 13 9 (13,9)
7 = 0 + 2x5 - 2x10 =-10 12 9 (12,9)
8 = -10 + 2x5 = 0 11 10 (11,10)
9 = 0 + 2x5 - 2x10 =-10 10 by: Parash Mani
Compiled 10 Bhandari (10,10) 205
Example: Digitize line with endpoints (5, 6) and (6,3) using Bresenham's Line
DrawingAlgorithm.
Solution:
Δx = |5-6| = 1
Here, (X1,Y1)= (6,3) & Δy = |6-3| = 3
(X2,Y2)=(5,6)
here,
If Pk < 0 If Pk ≥ 0 Initial (P0) = 2 Δx – Δy
Xk+1 = Xk Xk+1 = Xk - 1 = 2x1-3
Yk+1 = Yk +1 Yk+1 = Yk +1 = -1
Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy

(6, 3)
K PK Xk+1 Yk+1 (Xk+1 ,Yk+1)

0 -1 6 4 (6,4)
1 =-1+2x1 = 1 5 5 (5,5)
2 =1+2x1-2x3=-3 5 6
(5,6)

Compiled by: Parash Mani Bhandari 206

 BLA for slope +ve
|M| ≤ 1 |M| >1

if Pk < 0 If Pk ≥ 0 If Pk < 0 If Pk ≥ 0
Xk+1 = Xk+1 Xk+1 = Xk+1 Xk+1 = Xk Xk+1 = Xk+1
Yk+1 = Yk Yk+1 = Yk+1 Yk+1 = Yk+1 Yk+1 = Yk+1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx Pk = Pk + 2 Δx Pk = Pk + 2 Δx -2Δy

P0 = 2 Δy - Δx P0 = 2 Δx - Δy

Bresenham’s Line Algorithm

BLA for slope -ve
|M| ≤ 1 |M| >1

If Pk < 0 If Pk ≥ 0 If Pk < 0 If Pk ≥ 0
Xk+1 = Xk - 1 Xk+1 = Xk - 1 Xk+1 = Xk Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 Yk+1 = Yk +1 Yk+1 = Yk +1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy

P0 = 2 Δy - Δx P0 = 2 Δx - Δy
Compiled by: Parash Mani Bhandari 207
Circle Algorithm
What is Circle ?
• Similarly to the case with lines, there 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 ever calculate the points for the top right eighth of a
circle, and then use symmetry to get the rest of the points

Compiled by: Parash Mani Bhandari 208

 Clockwise direction

Mid Point Circle Algorithm

(Xk,Yk) (Xk+1,Yk)

Pk<0

Pk≥0 (Xk+1,Yk-1/2)

(Xk+1,Yk-1)

Pk< 0 Pk ≥ 0
XK+1 = Xk+1 XK+1 = Xk+1
YK+1 = Yk YK+1 = Yk-1
Compiled by: Parash Mani Bhandari 209
Compiled by: Parash Mani Bhandari 210
Compiled by: Parash Mani Bhandari 211
Compiled by: Parash Mani Bhandari 212
 (Xk+1,Yk)
(Xk,Yk)
Pk<0
Case 1 : Pk < 0
Xk+1 = Xk +1
Yk+1 = Yk
Pk≥0 (Xk+1,Yk-1/2)
Pk+1 = Pk + 2(Xk+1) + 1
Pk+1 = Pk + 2Xk+1 + 1

Case 2: Pk ≥ 0 (Xk+1,Yk-1)
Xk+1 = Xk +1
Yk+1 = Yk - 1
Pk+1 = Pk + 2(xk+1) + [(yk – 1)2 - yk2)] - (yk - 1 - yk) +1
= Pk+2(xk+1) + [(yk 2 - 2yk +1 – yk 2)] - (yk-1- yk) + 1
= Pk+2(xk+1) - 2yk +1 +1 + 1
= Pk+2(xk+1) – 2(yk +1) +1
Pk+1 = Pk+2Xk+1 – 2YCompiled
k+1 +1 by: Parash Mani Bhandari 213
 Initial decision parameter
(1,r)
(0,r)
i.e.,
(x0,y0) = (0,r)
(1,r-1/2)
Here ,
Fcircle (1,r-) = P0

Now, (1,r-1)
P0 = 12+(r-1/2 )2 – r2
= 1 + r2- r + ¼ - r2
= 5/4 – r
P0 ≈ 1-r
P0 ≈ 1-r
Compiled by: Parash Mani Bhandari 214
Example : Digitize a circle with radius 10 at center (0,0)
Solution
Here, the initial decision parameter (P0) =1 – r = 1-10 = - 9
Since, for the Midpoint Circle Algorithm of initial point(0, r) &
center at origin (0, 0) rotating at clockwise direction, we have
Initial point (x0,y0) = (0,10)
P0

Compiled by: Parash Mani Bhandari 215

 Case 1 : Pk < 0 Case 2: Pk ≥ 0
Xk+1 = Xk +1 Xk+1 = Xk +1
Yk+1 = Yk Yk+1 = Yk - 1
Pk+1 = Pk + 2Xk+1 + 1 Pk+1 = Pk+2Xk+1 – 2Yk+1 +1
Thus, (0 , 10)
K PK X k+1 Y k+1 ( X k+1, Y k+1)

0 -9 0+1 = 1 10 (1,10)
1 = -9 + 2*1 +1= -6 1+2 =2 10 (2, 10)
2 =-6 + 2*2 +1= -1 2+1=3 10 (3, 10)
3 =-1 + 2*3 +1= 6 3+1 = 4 10-1=9 (4, 9)
4 =6 + 2*4 - 2*9 +1= -3 4+1 = 5 9 (5, 9)

5 =-3 + 2*5 +1= 8 5+1 = 6 9-1=8 (6, 8)

6 =8 + 2*6 - 2*8 +1= 5 6+1 = 7 8-1=7 (7, 7)

7 =5 +2*7 – 2*7 +1 =6 7+1 = 8by: Parash Mani7-1=6

Compiled Bhandari (8,6) 216
Compiled by: Parash Mani Bhandari 217
Example : Digitize a circle with radius 8

Compiled by: Parash Mani Bhandari 218

Example: Digitize a circle with radius 9 and
center at (6, 7).
Here, the initial decision parameter (P0)
P0 =1 – r = 1-9 = - 8
Since, for the Midpoint Circle Algorithm of starting point (0, r) &
centre at origin (0, 0) rotating at clockwise direction, we have
If P < 0

Mohan Bhandari (BCA-CG)

Plot (xk +1, yk )
Pk+1 = Pk + 2xk+1 + 1
Else (P ≥ 0)
Plot (xk +1, yk - 1)
Pk+1 = Pk+2xk+1 – 2yk+1 +1

219

Compiled by: Parash Mani Bhandari 219

k Pk Xk+1 Y (Xk+1, Yk+1) (Xk+1, Yk+1)
k+ At (0, 0) At (6, 7)
1

0. -8 0+1 = 1 9 (1, 9) (1+6, 9+7) = (7, 16)

1. = -8 + 2*1 +1= -5 1+1 = 2 9 (2, 9) (2+6, 9+7) = (8, 16)

Mohan Bhandari (BCA-CG)

2. = -5 + 2*2 +1= 0 2+1 = 3 8 (3, 8) (3+6, 8+7) = (9, 15)

3. = 0 + 2*3 - 2*8 +1=-9 3+1 = 4 8 (4, 8) (4+6, 8+7) = (10,15)

4. = -9 + 2*4 +1= 0 4+1 = 5 7 (5, 7) (5+6, 8+7) = (11,15)

5. = 0 + 2*5 - 2*7 +1=-3 5+1 = 6 7 (6, 7) (6+6, 7+7) = (12,14)

6. = -3 + 2*6 +1= 10 6+1 = 7 6 (7, 6) (7+6, 6+7) = (13,13)

220

Compiled by: Parash Mani Bhandari 220

 Mohan Bhandari (BCA-CG)
221

Compiled by: Parash Mani Bhandari 221

 Anti-Clockwise direction

Mid Point Circle Algorithm

(Xk-1,Yk) (Xk,Yk)

Pk<0

(Xk-1,Yk-1/2) Pk ≥ 0

(Xk-1,Yk-1)

Pk< 0 Pk ≥ 0
XK+1 = Xk-1 XK+1 = Xk-1
YK+1 = Yk YK+1 = Yk-1
Compiled by: Parash Mani Bhandari 222
 Here,
Decision parameter(Pk) = Fcircle (Xk -1,Yk-1/2)
= (Xk -1)2 + (Yk-1/2)2 - r2
Then, K+1th term is,
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}
= -2(xk-1)+(Y2k+1-Y2k) – (Yk+1 – Yk) + 1
[ ‫ ؞‬Xk+1 =Xk-1 in both condition ]

Pk+1= Pk-2xk+1+(Y2k+1-Y2k) – (Yk+1 – Yk) + 1

Case 1 : Pk< 0 Case 2: Pk ≥ 0
XK+1 = Xk-1 XK+1 = Xk-1
YK+1 = Yk YK+1 = Yk-1
Pk+1= Pk-2Xk+1 +1 Pk+1= Pk-2Xk+1 – 2Yk+1 +1
Compiled by: Parash Mani Bhandari 223
 Initial decision parameter
(-1,r) (0,r)

i.e.,
(x0,y0) = (0,r)
(-1,r-1/2)
Here ,
Fcircle (-1,r-) = P0

Now, (-1,r-1)
P0 = (-1)2+(r-1/2 )2 – r2
= 1 + r2- r + ¼ - r2
= 5/4 – r
P0 ≈ 1-r
P0 ≈ 1-r
Compiled by: Parash Mani Bhandari 224
Midpoint Ellipse Algorithm
Our approach here is similar to that used in displaying a
raster circle but the ellipse has 4-way symmetry. The midpoint
ellipse method is applied throughout the first quadrant in two
parts or region as shown in figure. The region-1 just behaves as
the circular property and the region-2 is slightly straight curve.
The equation of ellipse, whose centre at (0, 0)
is
x2/a2 + y2/b2 = 1

Compiled by: Parash Mani Bhandari 225

Midpoint Ellipse Algorithm (cont..)

Starting at (0, b), we take unit steps in the x direction until we

reach the boundary between region 1 and region 2. Then we
switch to unit steps in the y direction over the remainder of the
curve in the first quadrant. At each step, we need to test the
value of the slope of the curve. The ellipse slope is calculated by
differentiating the ellipse function as:

2xb2 + 2ya2 * dy/dx= 0 Or dy/dx = - 2xb2 / 2ya2

At the boundary between region 1 and region 2, dy/dx = - 1 and

2xb2 = 2ya2. Therefore, we move out of region 1 whenever
2xb2>=2ya2.

Compiled by: Parash Mani Bhandari 226

For Region – 1: Condition (2xb2 >= 2ya2)

Compiled by: Parash Mani Bhandari 227

Midpoint Ellipse Algorithm (cont..)

Assuming that the position (xk, yk) has been plotted, we

determine next position (xk+1, yk+1) as either (xk+1, yk) or (xk+1, yk-1)
by evaluating the decision parameter P1k
as:
P1k = Fellipse (xk+1, yk-1/2)
= b2 (x k+1)2 + a2 (yk-1/2 )2 –a2 b2 --- ------------- I
At next sampling position, the decision parameter will be
P1k+1 = Fellipse (xk+1+1, yk+1-1/2)
= b2 (xk+1+1)2 + a2 (yk+1-1/2)2 –a2 b2
= b2 {(xk+1) +1}2 + a2 (yk +1-1/2) 2 – a2 b

Compiled by: Parash Mani Bhandari 228

Compiled by: Parash Mani Bhandari 229
Initial decision parameter (P10) for region-1 of ellipse

The initial decision parameter is obtained by evaluating the

ellipse function at the start position (x0, y0) = (0, b). Here, the
next pixel will either be (1, b) or (1, b-1) where the midpoint is
(1, b -1/2). Thus, the initial decision parameter is given by:

P10 = Fellipse (1, b-1/2) = b2 + a2 (b -1/2)2 – a2 b2

= b2 – a2 b + a 2 *1/4

Thus, P10 = b2 – a2 b + a 2 *1/4

Compiled by: Parash Mani Bhandari 230

For Region – 2: Condition (2xb2 < 2ya2)

Compiled by: Parash Mani Bhandari 231

Compiled by: Parash Mani Bhandari 232
Compiled by: Parash Mani Bhandari 233
Compiled by: Parash Mani Bhandari 234
Compiled by: Parash Mani Bhandari 235
Compiled by: Parash Mani Bhandari 236
Compiled by: Parash Mani Bhandari 237
Polygon Fill Algorithm
• Different types of Polygons
• Simple Convex
• Simple Concave
• Non-simple : self-intersecting
• With holes

Convex Concave Self-intersecting

Compiled by: Parash Mani Bhandari 238

Area Fill Algorithm
• An alternative approach for filling an area is to
start at a point inside the area and “paint” the
interior, point by point, out to the boundary.
• This is a particularly useful technique for filling
areas with irregular borders, such as a design
created with a paint program.
• The algorithm makes the following assumptions
• one interior pixel is known, and
• pixels in boundary are known.

Compiled by: Parash Mani Bhandari 239

Area Fill Algorithm
• If the boundary of some region is specified in a single color, we
can fill the interior of this region, pixel by pixel, until the
boundary color is encountered.
• This method, called the boundary-fill algorithm, is employed
in interactive painting packages, where interior points are
easily selected.

Compiled by: Parash Mani Bhandari 240

Example
• One can sketch a figure outline, and pick an interior point.
• The figure interior is then painted in the fill color as shown in
these Figures

Compiled by: Parash Mani Bhandari 241

Area Fill Algorithm
• Basically, a boundary-fill algorithm starts from an interior point
(x, y) and sets the neighboring points to the desired color.

• This procedure continues until all pixels are processed up to

the designated boundary for the area.

Compiled by: Parash Mani Bhandari 242

Area Fill Algorithm
• There are two methods for processing neighboring pixels
from a current point.
1. Four neighboring points.
• These are the pixel positions that are right, left, above, and
below the current pixel.
• Areas filled by this method are called 4-connected.

Compiled by: Parash Mani Bhandari 243

Area Fill Algorithm
2. Eight neighboring points.
• This method is used to fill more complex figures.
• Here the set of neighboring points to be set includes the four
diagonal pixels, in addition to the four points in the first method.
• Fill methods using this approach are called 8-connected.

Compiled by: Parash Mani Bhandari 244

Area Fill Algorithm

Compiled by: Parash Mani Bhandari 245

Area Fill Algorithm
• Consider the Figure in the next slide.
• An 8-connected boundary-fill algorithm would correctly fill the
interior of the area defined in the Figure.

• But a 4-connected boundary-fill algorithm would only fill part

of that region.

Compiled by: Parash Mani Bhandari 246

Area Fill Algorithm

Compiled by: Parash Mani Bhandari 247

Area Fill Algorithm
• The following procedure illustrates a recursive
method for painting a 4-connected area with a
solid color, specified in parameter fillColor, up to
a boundary color specified with parameter
borderColor.
• We can extend this procedure to fill an 8-
connected region by including four additional
statements to test the diagonal positions (x ± 1, y
± 1).

Compiled by: Parash Mani Bhandari 248

Area Fill Algorithm

Compiled by: Parash Mani Bhandari 249

Area Fill Algorithm
• Some times we want to fill in (or recolor) an area that is not
defined within a single color boundary.
• Consider the following Figure.

Compiled by: Parash Mani Bhandari 250

Area Fill Algorithm
• We can paint such areas by replacing a specified interior color
instead of searching for a particular boundary color.

• This fill procedure is called a flood-fill algorithm.

Compiled by: Parash Mani Bhandari 251

Area Fill Algorithm
• We start from a specified interior point (x, y) and reassign all
pixel values that are currently set to a given interior color with
the desired fill color.
• If the area we want to paint has more than one interior color,
we can first reassign pixel values so that all interior points
have the same color.

Compiled by: Parash Mani Bhandari 252

Area Fill Algorithm
• Using either a 4-connected or 8-connected approach, we then
step through pixel positions until all interior points have been
repainted.

• The following procedure flood fills a 4-connected region

recursively, starting from the input position.

Compiled by: Parash Mani Bhandari 253

Area Fill Algorithm

Compiled by: Parash Mani Bhandari 254

Problems with Fill Algorithm (1)
• Recursive boundary-fill algorithms may not fill regions
correctly if some interior pixels are already displayed in the fill
color.

• This occurs because the algorithm checks next pixels both for
boundary color and for fill color.

Compiled by: Parash Mani Bhandari 255

Problems with Fill Algorithm
• To avoid this, we can first change the color of any interior
pixels that are initially set to the fill color before applying the
boundary-fill procedure.

• Encountering a pixel with the fill color can cause a recursive

branch to terminate, leaving other interior pixels unfilled.

Compiled by: Parash Mani Bhandari 256

Problems with Fill Algorithm (2)
• This procedure requires considerable stacking of neighboring
points, more efficient methods are generally employed.
• These methods fill horizontal pixel spans across scan lines,
instead of proceeding to 4-connected or 8-connected
neighboring points.

Compiled by: Parash Mani Bhandari 257

Problems with Fill Algorithm (2)
• Then we need only stack a beginning position for each
horizontal pixel span, instead of stacking all unprocessed
neighboring positions around the current position.
• Starting from the initial interior point with this method, we
first fill in the contiguous span of pixels on this starting scan
line.

Compiled by: Parash Mani Bhandari 258

Problems with Fill Algorithm (2)
• Then we locate and stack starting positions for spans on the
adjacent scan lines, where spans are defined as the
contiguous horizontal string of positions bounded by pixels
displayed in the border color.
• At each subsequent step, we retrieve the next start position
from the top of the stack and repeat the process.

Compiled by: Parash Mani Bhandari 259

Area Fill Algorithm
The algorithm can be summarized as follows:
1. define seed point,
2. fill scan line containing seed point,
3. for scan lines above and below, define new seed
points as:
i) first point inside left boundary,
ii) subsequent points within boundary whose left neighbor is
outside,
1. d) repeat algorithm with the new set of seed points.

Compiled by: Parash Mani Bhandari 260

Example
• In this example, we first process scan lines
successively from the start line to the top
boundary.
• After all upper scan lines are processed, we fill in
the pixel spans on the remaining scan lines in
order down to the bottom boundary.
• The leftmost pixel position for each horizontal
span is located and stacked, in left to right order
across successive scan lines.

Compiled by: Parash Mani Bhandari 261

Example
• In (a) of this figure, the initial span has been filled, and starting
positions 1 and 2 for spans on the next scan lines (below and
above) are stacked.

Compiled by: Parash Mani Bhandari 262

Example
• In Fig.(b), position 2 has been unstacked and processed to
produce the filled span shown, and the starting pixel (position
3) for the single span on the next scan line has been stacked.

Compiled by: Parash Mani Bhandari 263

Example
• After position 3 is processed, the filled spans and stacked
positions are as shown in Fig. (c).

Compiled by: Parash Mani Bhandari 264

Example
• And Fig.(d) shows the filled pixels after processing all spans in
the upper right of the specified area.

Compiled by: Parash Mani Bhandari 265

Example
• Position 5 is next processed, and spans are filled in the upper
left of the region; then position 4 is picked up to continue the
processing for the lower scan lines.

Compiled by: Parash Mani Bhandari 266

Example
• Finish up the upper scan lines.

Compiled by: Parash Mani Bhandari 267

Example
• Start the bottom scan lines.

Compiled by: Parash Mani Bhandari 268

Example
• Finish up the bottom scan lines.

Compiled by: Parash Mani Bhandari 269

Example
• Finish up the bottom scan lines.

Compiled by: Parash Mani Bhandari 270

Any Queries?

Compiled by: Parash Mani Bhandari 271