Prepared by: Ashish Tripathi St Andrews Institute of Technology & Management, Gurugram
SYLLABUS
2|Page Ashish Tripathi
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. In other words,
we can say that computer graphics is a rendering tool for the generation and manipulation of
images.
The act of drawing pictures on the computer is called rendering. The pictures can be
photographs, drawings, movies, or simulations.
Interactive Graphics
In interactive computer graphics, user have some control over the picture i.e. user can make
any change in the produced image. One example of it is the ping pong game. The interactive
software has three components:
The Application Model: It represents the graphics primitive which is shown on the
screen.
The Application Program: It creates, stores into, and retrieves from the application
model. It also handles user input.
The graphics system: It sends a series of graphics output commands that contain both
a detailed geometric description of what is to be viewed and the attributes describing how the
objects should appear. Thus the graphics system is a layer in between the application
program and the display hardware that effects an output transformation from objects in the
application model to a view of the model.
Passive Graphics
A computer graphics operation that transfers automatically and without operator
intervention. Non-interactive computer graphics involves one way communication between
the computer and the user. Picture is produced on the monitor and the user does not have
any control over the produced picture.
3|Page Ashish Tripathi
Applications of Computer Graphics
Cartography: Computer graphics is used to produce both accurate and schematic
representations of geographical and other natural phenomena from measurement data.
Examples include geographic maps, relief maps, exploration maps for drilling and mining,
oceanographic charts, weather maps, contour maps, and population-density maps.
User interfaces: Most applications that run on personal computers and workstations, have
user interfaces that rely on desktop window systems to manage multiple simultaneous
activities, and on point and click facilities to allow users to select menu items, icons, and
objects on the screen; typing is necessary only to input text to be stored and manipulated.
(Interactive) plotting in business, science and technology: The most common use of
graphics today is probably to create 2D and 3D graphs of mathematical, physical, and
economic functions; histograms, bar and pie charts; task-scheduling charts; inventory and
production charts, and the like .
Office automation and electronic publishing: Office automation and electronic
publishing can produce both traditional printed (hardcopy) documents and electronic
(softcopy) documents that allow browsing of networks of interlinked multimedia documents
are proliferating
Computer-aided drafting and design: In computer-aided design (CAD), interactive
graphics is used to design components and systems of mechanical, electrical,
electromechanical, and electronic devices, including structure such as buildings, automobile
bodies, airplane and ship hulls, very large scale-integrated (VLSI) chips, optical systems, and
telephone and computer networks.
Simulation and animation for scientific visualization and entertainment:
Computer produced animated movies and displays or the time-varying behavior of real and
simulated objects are becoming increasingly popular for scientific and engineering
visualization. Another advanced-technology area is interactive cartooning. The simpler kinds
of systems for producing ‘Flat” cartons are becoming cost-effective in creating routine ‘in-
between” frames that interpolate between two explicitly specified ‘key frames”.
Process control: Whereas flight simulators or arcade games let users interact with a
simulation of a real or artificial world, many other applications enable people or interact with
some aspect of the real world itself. Status displays in refineries, power plants, and computer
networks show data values from sensors attached to critical system components, so that
operators can respond to problematic conditions.
Computer-Aided Design for engineering and architectural systems etc.
Objects maybe displayed in a wireframe outline form. Multi-window environment is
also favored for producing various zooming scales and views. Animations are useful for
testing performance.
4|Page Ashish Tripathi
Presentation Graphics
To produce illustrations which summarize various kinds of data. Except 2D, 3D
graphics are good tools for reporting more complex data.
Visualization
For analyzing scientific, engineering, medical and business data or behavior.
Converting data to visual form can help to understand mass volume of data very efficiently.
Image Processing
Image processing is to apply techniques to modify or interpret existing pictures. It is
widely used in medical applications.
Graphical User Interface
Multiple window, icons, menus allow a computer setup to be utilized more efficiently.
Cathode Ray Tube
The primary output device in a graphical system is the video monitor. The main element of a
video monitor is the Cathode Ray Tube (CRT). The operation of CRT is very simple:
1. The electron gun emits a beam of electrons (cathode rays).
2. The electron beam passes through focusing and deflection systems that direct it towards
specified positions on the phosphor-coated screen.
3. When the beam hits the screen, the phosphor emits a small spot of light at each position
contacted by the electron beam.
4. It redraws the picture by directing the electron beam back over the same screen points
quickly.
5|Page Ashish Tripathi
There are two ways (Random scan and Raster scan) by which we can display an object on the
screen.
Raster Scan
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.
Picture definition is stored in memory area called the Refresh Buffer or Frame Buffer.
This memory area holds the set of intensity values for all the screen points. 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 (picture element) or pel. 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.
On black and white systems, the frame buffer storing the values of the pixels is called a
Bitmap. Each entry in the bitmap is a 1-bit data which determine the on (1) and off (0) of the
intensity of the pixel.
On color systems, the frame buffer storing the values of the pixels is called a Pixmap. Each
entry in the Pixmap occupies a number of bits to represent the color of the pixel. For a true
color display, the number of bits for each entry is 24 (8 bits per red/green/blue channel, each
channel 28 =256 levels of intensity value.
6|Page Ashish Tripathi
Random-Scan (Vector Display)
The CRT's electron beam is directed only to the parts of the screen where a picture is to be
drawn. The picture definition is stored as a set of line-drawing commands in a refresh display
file or a refresh buffer in memory. It is also called vector display, stroke-writing display, or
Calligraphic display.
Random-scan displays are designed to draw all the component lines of a picture 30 to
60 times each second.
Random-scan generally have higher resolution than raster systems and can produce smooth
line drawings, however it cannot display realistic shaded scenes.
Resolution
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. This depends on the type of phosphor used and
the focusing and deflection system.
Aspect Ratio
Another property of video monitors is aspect ratio. This number gives the ratio of vertical
points to horizontal points necessary to produce equal-length lines in both directions on the
screen. (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.
7|Page Ashish Tripathi
OUTPUT PRIMITIVES
The process in which the object is represented as the collection of discrete pixels is called
scan conversion. The video output circuitry of a computer is capable of converting binary
values stored in its display memory into pixel-on, pixel-off information that can be used by a
raster output device to display a point.
8|Page Ashish Tripathi
LINE GENERATION ALGORITHM
A line connects two points. It is a basic element in graphics. To draw a line, we need two
points between which you can draw a line. Here points X0 and Y0 are referred as starting
points and X1 and Y1 are ending points of a line.
DDA Algorithm
Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm which is
explained step by step here.
Step 1: Get the input of two end points (X0, Y0) and (X1, Y1).
Step 2: Calculate the difference between two end points.
dx = X1 - X0
dy = Y1 - Y0
Step 3: Based on the calculated difference in step-2, you need to identify the number of steps
to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate.
if (dx > dy)
Steps = absolute(dx);
else
Steps = absolute(dy);
Step 4: Calculate the increment in x coordinate and y coordinate.
Xincrement = dx / steps;
Yincrement = dy / steps;
Step 5: Put the pixel by successfully incrementing x and y coordinates accordingly and
complete the drawing of the line.
for (int v=0; v < Steps; v++)
{
x = x + Xincrement;
y = y + Yincrement;
putpixel(x,y);
}
9|Page Ashish Tripathi
Bresenham’s Line Generation
The Bresenham algorithm is another incremental scan conversion algorithm. The big
advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis
in unit intervals and at each step choose between two different y coordinates.
For example, as shown in the following illustration, from position (2, 3) you need to choose
between (3, 3) and (3, 4). You would like the point that is closer to the original line.
At sample position xk+1, the vertical separations from the mathematical line are labelled as
dupper and dlower.
10 | P a g e Ashish Tripathi
11 | P a g e Ashish Tripathi
12 | P a g e Ashish Tripathi
13 | P a g e Ashish Tripathi
CIRCLE GENERATING ALGORITHMS
14 | P a g e Ashish Tripathi
MID POINT CIRCLE DRAWING ALGORITHM
15 | P a g e Ashish Tripathi
Example
ELLIPSE GENERATING ALGORITHM
Midpoint Ellipse Algorithm
1. Input rx, ry, and ellipse center (xc, yc), and obtain the first point on an ellipse centered
on the origin as
(x0, y0) = (0, ry)
2. Calculate the initial value of the decision parameter in region 1 as
1
P10 = 𝑟𝑦2 − 𝑟𝑥2 𝑟𝑦 + 𝑟𝑥2
4
3. At each Xk position in region 1, starting at k = 0, perform the following test:
If p1k < 0, the next point along the ellipse centered on (0,0) is (Xk+1, Yk) and
P1k+1 = p1k + 2𝑟𝑦2 𝑥𝑘+1 + 𝑟𝑦2
Otherwise, the next point along the circle is (Xk+1, Yk-1) and
P1k+1 = p1k + 2𝑟𝑦2 𝑥𝑘+1 − 2𝑟𝑥2 𝑦𝑘+1 + 𝑟𝑦2
Where,
2𝑟𝑦2 𝑥𝑘+1 = 2𝑟𝑦2 𝑥𝑘 + 2𝑟𝑦2 and 2𝑟𝑥2 𝑦𝑘+1 = 2𝑟𝑥2 𝑦𝑘 − 2𝑟𝑥2
And continue until 2𝑟𝑦2 𝑥 ≥ 2𝑟𝑥2 𝑦
4. Calculate the initial value of decision parameter in region 2 using the last point (x0, y0)
calculated in region 1 as
1
P20 = 𝑟𝑦2 (𝑥0 + ) 2
+ 𝑟𝑥2 (𝑦0 − 1) 2 − 𝑟𝑥2 𝑟𝑦2
2
5. At each yk position in region 2, starting at k = 0, perform the following test:
16 | P a g e Ashish Tripathi
If p2k > 0, the next point along the ellipse centered on (0,0) is (Xk, Yk-1) and
P2k+1 = p2k - 2𝑟𝑥2 𝑦𝑘+1 + 𝑟𝑥2
Otherwise, the next point along the circle is (Xk+1, Yk-1) and
P2k+1 = p2k + 2𝑟𝑦2 𝑥𝑘+1 − 2𝑟𝑥2 𝑦𝑘+1 + 𝑟𝑥2
Using the same incremental calculations for x and y as in region 1
6. Determine symmetry points in the other 3 quadrants.
7. Move each calculated pixel position (x,y) onto the elliptical path centered on (X c, Yc)
and plot the coordinate values:
𝑥 = 𝑥 + 𝑥𝑐 , 𝑦 = 𝑦 + 𝑦𝑐
8. Repeat the steps for region 1 until 2𝑟𝑦2 𝑥 ≥ 2𝑟𝑥2 𝑦
Example:
17 | P a g e Ashish Tripathi
18 | P a g e Ashish Tripathi
Filled Area Primitives
Polygon filling:
Polygon is an ordered list of vertices. For filling polygons with particular colors, you need to
determine the pixels falling on the border of the polygon and those which fall inside the
polygon.
SCAN LINE ALGORITHM
This algorithm works by intersecting scan line with polygon edges and fills the polygon
between pairs of intersections. For each scan line crossing a polygon, the area-fill algorithm
locates the intersection points of the scan line with the polygon edges. These intersection
points are then sorted from left to right, and the corresponding frame-buffer positions
between each intersection pair are set to the specified fill color.
For example two scan lines at positions y and y' that intersect edge endpoints are shown. Scan
line y intersects five polygon edges. Scan line y', however, intersects an even number of edges
although it also passes through a vertex. Intersection points along scan line y' correctly
identify the interior pixel spans. But not the scan line y. For scan line y, the two intersecting
edges sharing a vertex are on opposite sides of the scan line. But for scan line y', the two
intersecting edges are both above the scan line.
19 | P a g e Ashish Tripathi
One way to resolve the problem is to count a vertex as one intersection or two is to shorten
some polygon edges to split those vertices that should be counted as one intersection.
When the endpoint y coordinates of the two edges are increasing, the y value of the upper
endpoint for the current edge 1s decreased by 1.
When the endpoint y values are monotonically decreasing, we decrease the coordinate of the
upper endpoint of the edge following the current edge.
ALGORITHM
20 | P a g e Ashish Tripathi
BOUNDARY FILL ALGORITHM
The boundary fill algorithm picks a point inside an object and starts to fill until it hits the
boundary of the object. The color of the boundary and the color that we fill should be different
for this algorithm to work. A boundary-fill procedure accepts as input the coordinates of an
interior point (x, y), a fill color, and a boundary color. Starting from (x, y), the procedure tests
neighboring positions to determine whether they are of the boundary color. If not, they are
painted with the fill color, and their neighbors are tested. This process continues until all
pixels up to the boundary color for the area have been tested.
In this algorithm, we assume that color of the boundary is same for the entire object. The
boundary fill algorithm can be implemented by 4-connetected pixels or 8-connected pixels.
21 | P a g e Ashish Tripathi
22 | P a g e Ashish Tripathi
8-Connected Polygon
In this technique, we are putting pixels above, below, right and left side of the current pixels
as we were doing in 4-connected technique. In addition to this, we are also putting pixels in
diagonals so that entire area of the current pixel is covered. This process will continue until
we find a boundary with different color.
23 | P a g e Ashish Tripathi
Flood Fill Algorithm
Sometimes we come across an object where we want to fill the area and its boundary with
different colors. We can paint such objects with a specified interior color instead of searching
for particular boundary color as in boundary filling algorithm. Instead of relying on the
boundary of the object, it relies on the fill color. In other words, it replaces the interior color
of the object with the fill color. When no more pixels of the original interior color exist, the
algorithm is completed. Once again, this algorithm relies on the Four-connect or Eight-
connect method of filling in the pixels. But instead of looking for the boundary color, it is
looking for all adjacent pixels that are a part of the interior.
24 | P a g e Ashish Tripathi
