Downloaded fro m [Link].

co m

Course Introduction

In this course, you will learn about the concepts of using computers for drawing
and manipulation of pictures. Though initially computers were being used only f or
calculations (number crunching - as it is called), with the advent of high resolution
monitors, the concept of using them to display drawings come into vogue. This was
found very useful in a number of domains - like in design and drawing, animation of
pictures, and virtual reality shows etc. The basic advantage was that computers can
calculate at a very rapid speed and also display them. They can also store information for
any length of time. Thus, an engineers concept of design - calculate the details, draw the
picture, modify if needed, calculate the changes etc. Until satisfied and finally store the
information for future use - were all possible in the graphics using computers. Others
areas like simulation, animation (display of moving pictures), computer games etc. Were
also highly dependent on the concept of computer graphics.

This course is divided into two units. In the first unit, we see the basics of
computer graphics - The different hardware available for graphics use like different kinds
of monitors, input devices like mouse, light pens etc. Are introduced. Also the concepts
of drawing simple pictures like lines, circles etc. Using mathematical equations are
introduces. You will also learn the concepts of modifying the drawn picture - not by
erasing parts of it, but by moving it so some other portions of the screen, enlarging or
reeducating their size and also rotating them through a given angle. The concept of
fitting a larger picture into the available screen size by clipping and windowing are also
dealt with. The computer also provides certain facilities where by small errors of the user
are covered up. These are also introduced in this unit.

The second unit covers the more advanced topics. Most of the objects that we see
and deal with in daily life are there dimensional, but the screen is a two d imensional one,
on which theses objects are to be represented. However, we cannot afford to lost
information about the depth of the object, since it is critical in certain applications like in
simulation, design of 3-D objects etc. Hence, concepts like perspective projections are

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
introduced in this unit. To ensure to continuity and also make many of the methods
developed for 2-D also become applicable in 3-D, we make use of similar notations. You
are also introduced to two important concepts - those of scan conversion and hidden
surface removal. Scan conversion deals with displaying closed areas opposed to the
surrounding back ground. Even though this concept covers 2-D objects, some of the
concepts like coherence and scan conversion mechanisms become applicable in several
3-D operations. Hence, this block is included in this unit.

Subsequent blocks introduce to concepts of transformation, clipping, windowing

etc., in the 3-D environment. You will recognize that most of the 2-D principles become
applicable there also. WE close the discussion with a study of various methods of hidden
surface removal.

In real life, when one object stands behind another, the first object coves
the second object wholly or partly based on the location of two objects. To induce a
concept of depth, it is essential that the obscured parts need to be identified and removed
(only from display and not from the original data files). Several interesting algorithms
for the same are introduced in this section.

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
UNIT - 1

Unit Introduction

In this unit, you are introduced to the basin of computer graphics. To begin with
we should know why one should study computer graphics. It's areas of application
include design of objects, animation, simulation etc. Though computer graphics gained
importance after the introduction of monitors, these are several other input and out
devices that are important for the concept of computer graph lines. They include high
resolution color monitors, light pens, joy sticks, mouse etc. You will be introduced to the
working principles of them.

The concept of computer graphics simply means identifying there areas of the
screen that are to be illuminated and those that should not be. Most of the regular figures
like straight lines, circles etc, are represented by mathematical equations. Given such
equations, the first aspect of computer graphics is to convert them to a sequence of points
- picture cells or pixels that are to be illuminated (in case of raster graphic display) or
simply covert it to a curve that should be traced on the screen. Since many times these
jobs have to be very fast and efficient. You will be introduced to a number of such
algorithms and also their limitations.

We also look into the concept of transformations. Whenever as existing is to be

moved to a new place or say to be zoomed, the drawing is not done again on the other
hand, we only try to transform them. Simple transformation matrices for various
operations are also introduced. Further, often we may end up drawing pictures larger
than these that can be represented on the screen. In such cases, we have a mechanism of
"clipping" it to the required dimensions. We also have schemes that fit a given picture
into a "window" of suitable size and location.

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Further, since the computer is an "exact" device, in the sense it cannot
approximate operations, sometimes it becomes difficult for the human beings to input
exact values, like making the lines join exactly or the ends of a circle meeting perfectly
etc. To take care of such cases, certain "constraints" are introduced so that the computer
can know what the input is about - or looking at the other way, one cannot "approximate"
things he is "constrained" to make them perfect. Similarly there are several other
graphical input techniques that allow the user to interactively input the data, mostly
drawings, without giving rise to ambiguities. These are also dealt with in this unit.

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK – I

What is computer Graphics?

Introduction : In this block, you get introduced the scope of computer graphics and it's
origin from display of simple drawings to the present state of animated pictures. You are
introduced to the various areas of application, and the two basic methods of represent ing
pictures namely (i) line drawing methods in which, as the word suggests, the figures are
drawn using lines and (ii) raster graphics, where in the picture is presented as a sequence
of illuminated dots (pixels). You will also be introduced to some of the inherent
difficulties in the above methods.

Contents :

1. Area of Computer Graphics

2. How are pictures actually stored and displayed
3. Difficulties for displaying pictures
4. Block Summary
5. Review Question and Answers.

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Areas of Computer Graphics : After number crunching, the most important area
of application of computer, perhaps, is computer graphics. With the advent of CRT
monitors, the concept of data input and output of computers underwent a revolutionary
change. In fact, the ease of seeing what one is inputting to the computer, and ease of
modifying the same, if necessary, and the ease of getting outputs on the screen was one of
the major factors that helped in popularizing computers amongst non-computer
professionals.

The other use of the monitor technology was the advent of graphics. Apart from
characters, lines, circles and all shapes of figures can be drawn and manipulated on the
screen. They can be stored in files and storage devices, modified and transported. This
led to the use of computers in all applications, where such properties become useful. We
will briefly see some of the areas.

i) Design and Drawing : In almost all areas of engineering, be it civil, mechanical,

electronic etc., drawings are of prime importance. In fact, drawing is said to be
the language of engineers. The ability of computers to store complex drawings
and display them on demand was one of the major attractions for using computers
in graphic mode. However, these were further advantages. Most of these
drawings were the result of engineering calculations. In fact, programs can be
written to make these calculations and the results can be used to draw diagrams on
the screen. If changes are to be made, one can get back to the design formulae
and so on. Thus, the are of design and drawing was one of the earliest and most
useful applications of graphics.
ii) Animation: But what brought the computers pretty close to the average
individuals is the concept of animation moving pictures. It is the well known
principle of moving pictures that a succession of related pictures, when flashed
with sufficient speed will make the succession of pictures appear to be moving.
In movies, a sequence of such pictures is shot and are displayed with sufficient
speed to make them appear moving. Computers can do it in another way. The

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
properties of the picture can be modified at a fairly fast rate to make it appear
moving. For example, if a hand is to be moved, say, the successive positions of
the hand at different periods of time can be computed and pictures showing the
position of the hand at these positions can be flashed on the screen. This led to
the concept of “animation” or moving pictures. In the initial stages, animation
was mainly used in computer games.

However, this led to a host of other possibilities. As we see later on in this

course, computers not only allow you to display the figures but also offer you
facilities to manipulate them in various ways – you can enlarge, reduce, rotate,
twist, morph (make one picture gradually change to another – like an
advertisement showing a cheetah change into a motor bike) and do a whole lot of
other things. Thus, a whole lot of films made use of computers to generate tricks.
In fact, several advertisement films and cartons strips are built with no actors at
all – only the computer generated pictures.
iii) Multime dia applications : The use of sound cards to make computers produce
sound effect led to other uses of graphics. The concept of virtual reality, where
in one can be taken through an unreal experience, like going through an unbuilt
house ( to see how it feels inside, once it is built ) are possible by the use of
computer graphics technology . In fact the ability of computers to convert
electronic signals (0 & 1) to data and then on to figures and pictures has made it
possible for us to get photographs of distant planets like mars being reproduced
here on the earth in almost real time.
iv) Simulation : The other revolutionary change that graphics made was in the area
of simulation. Basically simulation is a mockup of an environment elsewhere to
study or experience it. The availability of easily interactive devices (mouse is one
of them, we are going to see a few other later in the course) made it possible to
build simulators. One example is of flight simulators, wherein the trainee, sitting
in front of a computer, can operate on the interactive devices as if he were
operating on the flight controls and the changes he is expected to see outside his

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
window are made to appear on the screen, so that he can master the skills of flight
operations before actually trying his hand on the actual flights.

The graphic capabilities of computers are used in a very large variety of areas like
criminology (to recreate faces of victims, assailants etz.,) medical fields (recreating
pictures of internal cavities, using signals sent by miniature cameras), recreation of
satellite pictures etc.,.

How are pictures actually stored and dis played ?:

All operations on computers are in terms of Os and 1s and hence figures are also
to be stored in terms of Os and 1s. Thus a picture file, when viewed inside the memory,
can be no different from other files – a string of Os and 1s. However, their treatment
when they are to be displayed makes the difference.

Figures can be stored and drawn in two ways – either by line drawing or by Raster
graphic methods. In the line drawing scheme, the figures are represented by equations –
for example a straight line can be represented by the equation y=mx+c, a circle by
x2 +y2 =r2 etc. If (x,y) are representative points, then all these (x,y) value pairs which
satisfy the equations form a part of the figure while those that do not, lie outside the
figure. Thus, to generate any figure, obviously the equation of the figure is to be known.
Then all points that satisfy the equation are evaluated. These are the points to be
illuminated on the screen.

o x

a
x
x
x Points to be illuminated
x
y x
x
x
b

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

The screen, or the monitor, as we know is illuminated by a moving electronic

beam. Whenever the beam is switched on, the electrons illuminate the phosphorescent
screen and display a point. In the line drawing schemes, this beam is made to traverse the
path of the figure to be traced and we get the figure we need. For example, in the above
cited example if the electron beam is made to move from a to be along the points, we
get the line.

The raster scan mechanism uses a different technique and is often found more
convenient to manipulate and operate with. In this case, a "frame buffer", (a chunk of
memory) is made to store the pixel values. (Remember, the screen can be thought of as
having beam made up of a number of horizontal rows of pixels (picture cells), each pixel
representing a point on the picture. In fact the number of a such horizontal and vertical
points indicate higher resolutions and therefore better pictures. Typical resolutions are
like

o x

1024 x 1024 etc., where the figures indicate the no. of rows and the number of pixels
along each row respectively on a computer screen (unlike in standard mathematics) the

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
top left hand point indicates the origin or the point (0,0) and the distances are measured
horizontally and vertically as shown).

Now, assuming a 1024 x 1024 point screen, any figure that is to be displayed
within this space. The "frame buffer" stores "status" of each of these pixels - say 0
indicates the pixel is off and hence is not a part of the picture and 1 indicates it is a part of
the picture, and is to be displayed. This data is used to display the pictures. (The exact
details of manipulation of raster points will be taken up in the next unit).

What are the difficulties for displaying pictures ?: Unfortunately, the concept of
graphics of displaying pictures is lot more complicated than what has been described so
far - evaluate the points using the equations, store them in a file and use raster graphics
methods or use simple line drawing algorithms. We will list a few of them before we
close this chapter.
i) stair case effects: Note that the pixel values are always integers (0,0) (0,1)
(0,2) - - - - - -- - -, but an algorithm to draw/manipulate pictures need not
always return integer values. Suppose the point at which two line meet, say is
at (1.4, 2.7). What do we do? Common sense suggests that we round off the
values, by using any of the standard algorithms. Excellent. 1.4 gets rounded
of to 1 and 2.7 to 3. But another value of 1.6 say gets rounded off to 2 and a
value of 3.1 also gets rounded of to 3. So, what do we have? The pointer 1.4
and 1.6, which should be very close to each other, appear to be separated by a
distance of 1 and not 0.2 in our figure, i.e. the smoothness of a figure joining
these points is lost. Alternately, the points 2.7 and 3.1, instead of appearing to
be different, appear to be the same in our picture. A no. of such adjustments
makes the figure looks like a jagged one instead of a smooth figure.

10

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
(Why this is called a stair case effect and how we can reduce it, we will see in due
course)
ii) Response time: Especially when talking of animation, the speed at which new
calculations are made and the speed at which the screen can interact are
extremely important. Imagine a running bus, shown on the screen. Each new
position of the bus (and it's surroundings, if needed) are to be calculated and
sent to the screen and the screen should delete the earlier position of the bus
and display its new position. All this should happen at a speed that convinces
the viewer that the vehicle is actually moving at the prescribed speed,
otherwise a running vehicle would appear like a "walking" bus or worse a
"piecewise movement" bus. For this, most the speed of the algorithm and the
speed of the display devices are extremely important. Further, the entire
operation should appear smooth and not jerky otherwise, especially in
simulation applications, the effects can be danger's.
iii) What happens when the size of the picture exceeds the size of the screen?:
Obviously, some areas of the picture are to be cut off. But this involves
certain considerations and needs to be addressed by a software.
iv) Can the user create pictures directly on the screen?: Definitely all pictures can
not be thought of in terms of regular geometric figures and hence in terms of
equations? Now, seeing a particular picture on the screen, the viewer wants to
change it slightly, say bend it slightly here, stretch it there etc. This may not
suit any regular equation? How should the system handle it ?

The subsequent blocks answer these and may other questions.

Block Summary : You were introduced to the areas of application of computer graphics
like computer aided design, simulation, animation etc. We also discussed the basic
difference between line drawing and raster graphics methods and some of the difficulties
encountered while implementing the two methods.

11

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Review Questions

1. The art of representing moving pictures is called ________________________-

2. The concept of changing one picture gradually into another is called _____________

3. The combination of calculations, sound and pictures in computer is called __________

4. Building a mock up of an environment with the aim of studying the same is called
__________________

5. The equation of a straight line is given by _______________________

6. A block of memory to store pixel values is called ________________________

7. The number of pixels available for display of pictures is indicated by

________________
8. The concept of creating pictures directly on the screen is called ________________

Ans wers

1. Animation
2. Morphing
3. Multimedia
4. Simulation
5. y= mx+c
6. Frame buffer
7. Resolution
8. Interactive graphics.

12

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK - II

Graphic Devices

Block Introduction : In this block, we will look into some of the commonly used
hardware devices in conjunction with graphics. While the normal concept of a CPU,
Memory and I/O devices of a computer still holds good, we will be concentrating more
on the I/O devices. The special purpose output devices that allow us to see pictures in
color, for example, with different sizes, features etc. Also, once the picture is presented,
the user may like to modify it interactively. So one should be able to point to specific
portions of the display and change them. Special input devices which allow such
operations are also introduced. While ever changing technologies keep producing newer
and newer products, what you are being introduced to here are trends of technology.

Contents

1. Cathode Ray Tube

2. Quality of Phosphors
3. Direct View Storage Tube
4. Tablets
[Link] Dimensional Devices
6. Block Summary
7. Review Question and Answers

13

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
The Cathode Ray Tube (CRT/Monitor)

We would revisit the basic concepts of CRT. It helps in two ways - to brush up
the fundamentals with which we are already familiar an one hand and also serve as a bash
for the description of further concept.

A cathode ray tube is based on the simple concept that an electronic beam, when
hits a phosphorescent surface, produces a beam of light (momentarily - though we later
an describe surfaces that produce light intensities lashing over a period of time). Further,
the beam of light itself can be focused to any point on the screen by using suitable
electronic / magnetic fields. The direction and intensity of the fields will allow one to
determine the extent of the defection of the beam. Further these electronic / magnetic
fields can be easily manipulated by using suitable electric fields with this background, we
revisit the concept of the computer monitor.

The electronic gun produces a stream of electrons (Electron beam). The beam itself can
be switched on/off easily by switching on/off the heating system. The beam is focussed

14

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
towards the phosphor coated screen. The point where the beam hits the screen becomes
phosphorescent and produces a speck of light.

The actual focusing of the electronic beam on to the screen is done by a pair of
focusing grids - one horizontal and another vertical. These grids are operated by
electronic or magnetic fields. Depending on the direction (positive or negative) and the
intensity of the fields applied to them, the beam is deflected horizontally (or vertically)
and thus, by using a suitable combination of these focusing grids, the beam can be
focused to any point on the screen. So, we now have a mechanism wherein any point on
the screen can be illuminated (or made dark by simply switching off the beam).

Hence, from a graphics point of view, any picture can be traced on the screen by
the electron beam by suitably and continuously manipulating the focusing grids and we
get to see the picture on the screen "A basic graphic picture" of course, since the picture
produced vanishes once the beam is removed, to give the effect to continuity, we have to
keep the beam retracing the picture continuously - (Refreshing).

We leave out the minor details of the monitor - but move on to special purpose
CRT to suite graphic applications.

Quality of Phosphors : The quality of graphic display depends on the quality of

phosphors used. The phosphors are usually chosen for their color characteristics and
persistence. Persistence is how long the picture will be visible on the screen, after it is
first displayed. Most of the standards prescribe that the intensity of the picture should fall
to 1/10 of it's original intensity is less than 100 milliseconds.

The color of the phosphor is normally chosen as white, Also it should be of

small grains, so that the resolution of the screen can be high.

15

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
However, special types of monitors, to suit special applications have been
devised, which may not confirm to the above standards. We will see a few of them in the
next sections.

CRTs for Color Display : This was one the earlier CRTs to produce color displays.
Different colored pictures can be produced by coating phosphors of different compounds.
But the basic problem of graphics is not to produce a picture of a predetermined color,
but to produce color pictures, with the color characteristics chosen at run time.

The basic principle behind colored displays is that every color can be produced by
combining the 3 basic colors – Red, Blue and Green. By choosing different ratios of
these three colors we can produce different colors - millions of them infact. For punately
we also have basic phosphors which can produce these basic colors. So, one should have
a technology to combine them in different combinations.

Beam Penetration CRT: This CRT has uses a multiplayer phosphor and achieves the
control by modulating a parameter - normally the beam accelerating potential.

The organization is something like this - The red, green and blue sulphurs are
coated in layers - one behind the other. If a low speed beam strikes the CRT, only the red
colored sulphur is activated, a slightly accelerated beam would activate both red and
green (because it can penetrate deeper) and a much more activated one would add the
blue component also.

But the basic problem is a reliable technology to accelerate the electronic beam to
precise levels to get the exact colors - it is easier said than done. However, a limited
range of colors can be conveniently produced using the concept.

The Shadow - Mask CRT : This works, again, on the principle of combining the basic
colors - Red, green and blue - is suitable proportions to get a combination of colors, but
it's principle is much more sophisticated and stable.

16

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

The shadow mask CRT, instead of using one electron gun, uses 3 different guns
placed one by the side of the other to form a triangle or a "Delta" as shown. Each pixel
point on the screen is also made up of 3 types of phosphors to produce red, blue and
green colors. Just before the phosphor screen is a metal screen, called a "s hadow mask".
This plate has holes placed strategically, so that when the beams from the three electron
guns are focused on a particular pixel, they get focused on particular color producing
pixel only. i.e. If for convenience sake we can call the electronic beams as red, blue and
green beams (though in practice the colors are produced by the phosphors, and until the
beams hit the phosphor dots, they produce no colors), the metal holes focus the red beam
onto the red color producing phosphor, blue beam on the blue producing one etc. When
focused on to a different pixel, the red beam again focuses on to the red phosphor and so
on.

17

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Now, unlike the beam penetration CRTs where the acceleration of the electron
beam was being monitored, we now manipulate the intensity of the 3 beams
simultaneously. If the red beam is made more intense, we get more of red color in the
final combination etc. Since fine tuning of the beam intensities is comparatively simple,
we can get much more combination of colors than the beam penetration case. In fact, one
can have a matrix of combinations to produce a wide variety of colors.

The shadow mask CRT, though better than the beam penetration CRT in
performance, is not without it's disadvantages. Since three beams are to be focused, the
role of the "Shadow mask" becomes critical. If the focusing is not achieved properly, the
results tend to be poor. Also, since instead of one pixel point in a monochrome CRT
now each pixel is made up of 3 points (for 3 colors), the resolution of the CRT (no. of
pixels) for a given screen size reduces. Another problem is that since the shadow mask
blocks a portion of the beams (while focusing them through the holes) their intensities get
reduced, thus reducing the overall brightness of the picture. To overcome this effect, the
beams will have to be produced at very high intensities to begin with. Also, since the 3
color points, though close to each other, are still not at the same point, the pictures tend to
look like 3 colored pictures placed close by, rather than a single picture. Of course, this
effect can be reduced by placing the dots as close to one another as possible.

The above displays are called refresh line drawing displays, because the picture
vanishes (typically in about 100 Milli seconds ) and the pictures have to be continuously
refreshed so that the human persistence of vision makes them see as static pictures.
They are costly on one hand and also tend to flicker when complex pictures are displayed
(Because refreshing because complex). These problems are partly overcome by devices
with inherent storage devices - i.e. they continue to display the pictures, till they are
changed or atleast for several minutes without the need of being refreshed. We see one
such device called the Direct View Storage Tube (DVST) below.

18

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Direct Vie w Storage Tube: Conceptually the Direct View Storage Tube
(DVST) behaves like a CRT with highly persistent phosphor. Pictures drawn on there
will be seen for several minutes (40-50 minutes) before fading. It is similar to CRT as far
as the electronic gun and phosphor coated mechanisms are concerned. But instead of the
electron beam directly writing the pictures on the phosphor coated CRT screen, the
writing is done with the help of a fine- mesh wire grid. The grid, made of very thin, high
quality wire, is located with a dielectric and is mounted just before the screen on the path
of the electron beam from the gun. A pattern of positive charges is deposited on the grid
and this pattern is transferred to the phosphor coated CRT by a continuous flood of
electrons. This flood of electrons is produced by a "flood gun" (This is separate frame
the electron gun that produces the main electron beam).

Just behind the storage mesh is a second grid called the collector. The function of
the collector is to smooth out the flow of flood electrons. Since a large number of
electrons are produced at high velocity by the flood gun, the collector grid, which is also

19

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
negatively charged reduces, the acceleration on these electrons and the resulting low
velocity flood pass through the collector and get attracted by the positively charged
portions of the storage mesh (Since the electrons are negatively charged), but are
repelled by the other portions of the mesh which are negatively charged (Note that the
pattern of positive charges residing on the storage mesh actually defines the picture to be
displayed). Thus, the electrons attracted by the positive charges pass through the mesh,
travel on to the phosphor coated screen and display the picture. Since the electrons have
been slowed down by the collector, they may not be able to produce sharp and bright
images. To over come this problem, the screen itself is maintained at a high positive
potential by means of a voltage applied to a thin aluminum coating between the tube face
and the phosphor.

Flood of
electrons

mesh of thin gauge CRT Screen

The dotted circle on the mesh is created by positive charges the flood of electrons
hit the mesh at all points. But only those electrons that hit the dotted circle pass through
and hit the CRT screen. Others are repelled by the negatively charged mesh.

Since the phosphor is of a very high persistence quality, the picture created on the
CRT screen will be visible for several minutes without the need for being refreshed.

Now the problem arises as to how do we remove the picture, when the time for it's
erasure or modification comes up. The simple method is to apply a positive charge to
the negatively charged mesh so that it gets neutralized. This removes all charges and

20

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
clears the screen. But this technique also produces a momentary flash, which may be
unpleasant to the viewer. This is mainly so when only portions of the picture are to be
modified in an interactive manner. Also, since the electrons hit the CRT screen at very
low speeds (though they are slightly accelerated in the last part of their journey to the
CRT by a positively charged aluminum coating), the contrasts are not sharp. Also, even
though the pictures stay for almost an hour, there will be a gradual degradation because
of the accumulation of the back ground glow. The other popular display device is the
plasma panel device, which is partly similar to the DVST in principle, but over comes
some of the undesirable features of the DVST.

We shall now see some of the popularly used input devices for interactive
graphics.

The most important of these devices is the mouse. It is a metallic base provided
with a spherical ball at the bottom, which can rotate in all directions. The concept is that
a driver software keeps track of the present curser position and when the mouse is pushed
to any new position, the movement of the ball at the bottom is converted to the position
of the curser on the screen. Thus, instead of specifying the coordinator and then moving
the curser to that position, simply moving the mouse to that position suffices. The basic
advantage is the inherent visual appeal of the concept. Instead of calculating the distance
from say a point P(x1, y1) to another point say ( x2, y2) and then issuing commands, the
mouse can be simply moved so that the curser goes to the new position. (The concept of
mouse, though was developed for the graphic applications, became popular with the
advent of windows operating system and the mouse became an essential input device
along with the key board)

21

Downloaded fro m [Link] m

 Downloaded fro m [Link] m


Since it is a very popular and well known device, we will not deal with it in very
great detail.

In fact, the forerunner of the mouse is a joystick. Here, as the name suggests, we
have a stick (or a handle, to be more exact) can be moved in all possible directions and

22

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

A joy Stick

The direction and amount of movement in that direction controls the amount of curser
movement. Once the curser arrives at the desired position, the picture can be chosen by
clicking the buttons and any modification can be made.

In fact, the joysticks were originally used for video games (hence the name "joy"
stick), but later on modified for the more accurate graphics requirements.

However, both the mouse and joysticks may appear a bit cumbersome for the new
users. They find some difficulty in aligning the curser to the precisely desired postions.

TABLETS

In addition to the need for practice before the mouse can be used effectively, it
has a serious advantage. It cannot be used to trace handwritten characters / pictures.
Quite often, we may not have regular equations of the pictures we want to manipulate
(refer the next block), but we may have the actual pictures themselves drawn on paper.
Suppose we are able to trace these drawings and if the software could produce the same

23

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
on the screen, it would be convenient atleast in some cases. This is true not only in terms
of drawings, but also handwritten characters or letters. But the mouse, with it's fairly
limited resolution, can not be made to trace such pictures accurately. Tablets are
developed to do the job. They can also be used to draw pictures on a paper which can be
transferred to the screen.

Several techniques for developing such tablets are available. A simple method is
by using a flat area which rests as a table top. The rectangular area is divided by several
horizontal and vertical lines into grids. (Usually 1024 horizontal and 1024 vertical lines)

Stylus

Grids of a tablet

A stylus or a pen like apparatus, which is connected by a coaxial cable to the

computer is used to point to the grid.. Each horizontal and vertical line carries a uniquely
coded digital signal. When the stylus touches the junction o f one horizontal and another
vertical junctions, the stylus picks up their corresponding signals. For example the 100 th
vertical signal and 125th horizontal signal identifies the position as the junction of the
100th vertical and 125th horizontal line or say the point (125, 100) which is unique. Thus,
later if the stylus is later moved to the positions (124, 101), (123,102) etc, the system can
very easily keep tract of these movements.

The digital signal concept is not the only method of identifying the position. An
acoustic tablet can make use of sound signals to identify the location. In the figure, two

24

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

strip microphones which are at 90 0 to each other and are attracted to the edger of the
tablet are independently connected to the system. The stylus has a small piece of ceramic
mounted close to it's tip and at regular intervals a small spark is generated a cross the
surface of the ceramic between two electrodes. This spark produces a sound and the two
microphones pickup the sound of the pulse and transmit to the computer. The delay
between the time of creation of the spark and the time at which it is picked up by a
microphone gives the position of the spark (and hence the stylus) with respect to the
microphone. Thus each microphone gives the distance of the stylus from itself and when
the positions provided by the two microphones are superimposed, we get the actual
position of the stylus.

The light Pen: The devices discussed so far, the mouse, the tablet, the joystick are called
"positioning devices". They are able to position the curser at any point on the screen.
(Which in turn means, we can operate at that point or the chain of points)

Often, we also need devices that can "point" to a given position on the screen.
This becomes essential when a diagram is already there on the screen, but some changes
are to be made. So, instead of trying to know it's coordinates, it is advisable to simply
"point" to that portion of the picture and ask for changes.

The simplest of such devices is the "light pen". It's principle is extremely simple.

25

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

We know that every pixel on the screen that is a part of the picture emits light. In
fact they are much brighter than their surrounding pixels. All that the light pen does is to
make use of this light signal to indicate the position. A small aperture is held against the
portion of the picture to be modified and the light from the pixels, after passing through
the operator falls on a photocell. This photocell converts the light signal received from
the screen to an electrical pulse - a signal sent to the computer. Since the electrical
signal is rather weak, it is amplified by an amplifier before being sent to the computer.
Since a "tracking software" keeps track of the position of the light pen always (in a
manner much similar to the position of the mouse being kept track of by the software), a
signal received by the light pen at any point indicates that portion of the picture that
needs to be modified (most often that portion gets erased, pa ving way for any other
modifications to be made).

However, when the pen is being moved to it's position - where the modification is
required - it will encounter so many other light sources on the way and these should not
trigger the computer. So the operator of the light pen is normally kept closed and when
the final position is reached, then it can be opened by a switch - in a manner similar to the

26

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
one used in a photographic camera, though, of course, the period of opening the operator
is for much longer periods than in a camera.

Three Dimensional Devices

Though the display on the CRT monitor always presents a 2 dimensional picture,
it is not necessary that the data stored in the computer about the picture also should be
two dimensional. In particular, when one is taking data from 3-dimensional models it
becomes necessary to map input data which is 3-dimensional in nature into the 2-
dimensional pictures. This aspect will be dealt with in a later chapter. However, the
input devices should be able to read and transfer data from a 3-dimensional world, in the
first place. The devices that we have seen so far, namely the mouse or light pen or
joysticks or even tablets work only on two dimensional data only.

In this section, we see the simplest of input devices, which work only on the
extended principle of the 2-dimensional tablet that we have encountered earlier.

The concept is that when two perpendicularly placed microphones can pick up
signals and identify them in a 2 dimensional space, 3-perpendiculorly placed
microphones can pickup and identify signals in a 3-dimensional space. The result is the
above figure.

27

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
But when a 2 -dimensional tablet is made 3-dimensional by adding a third,
perpendicular microphone, the tablet becomes more difficult to manage because of the
bulk. Hence one more mechanism, wherein a 2-dimensional tablet can be used to effect
a 3 dimensional recognition was developed. In this case, all the four sides of the tablet
are provided with a microphone each and it can be mathe matically shown that any sound
made by the stylus tip at a height above the tablet is picket up by the four microphones,
the time delays will be proportional not only to the x and y distances of the stylus form
the microphones, but also to it's height above the stylus - the z distance. By using very
simple mathematics - it is possible to separate the x,y and z values, i.e. the actual
position of the stylus.
reel of tense wire

Stylus

One more simple method of tracking in 3 dimensions is by the use of wires in 3

dimensions. The trick is to connect the stylus to 3-wires, positioned in x,y and z
direction, connected to several length of wires and which are spring loaded. The distance
of the stylus from each of these springs is proportional to the force applied on the springs,
which can be used to indicate the position. However, this method is less accurate and is
seldom used.

Block Summary: In this block, your were introduced to several output and input devices
which have special significance to the graphic applications. You were first introduced to
the concept of producing colored displays by using the three primary colors - red, blue
and green and how by suitably combining their proportions, it is possible to get
different colors. The 3 color producing phosphors were either placed one behind the

28

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
other, in which ease the intensities of the electronic beam were adjusted to control their
penetration into these phosphors and hence produce the color (as in the case of beam
penetration CRT) or the three types of phosphors are placed in roughly triangular place
and three independent electronic beams were used (shadow mast CRTs). You also saw
the Direct View Storage Tube (DVST) where the images did not need refreshing but used
to be persistent for long periods of time.

You were also introduced to several of the input device the mouse, the tablets,
joysticks and light pens. They allowed one to either position or point parts of the images.
A brief introduction to 3-dimensional inputs was also given.

Review Questions

1. In a CRT, a stream of electrons falling on a ___________ screen produces images.

2. The path of the electron beam is focussed on to the screen using _____________ or
_________________.

3. The term ____________________ indicates how long the picture created on the
phosphorescent screen remains on it.

4. The three basic colors are ___________, ____________ and ________________

5. Different electron beams are accelerated to different levels in a ______________

6. When the picture has to remain on the screen for a long time _______________ type
of CRT is sued.

7. The first device to allow the user to move the cursor to any point, without actually
knowing the coordinates was ____________________

8. The input device that allows user to write pictures on it an input them directly to the
computer is called _______________________

9. Light pen is a ________________ device.

10. Name one device that allows a 3 dimensional input to be given to the computer.

Ans wers

29

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
1. Phosphorescent

2. Magnetic, electrical

3. Persistence

4. Red, Blue, Green

5. Beam Penetration CRT

6. Direct view storage Tube (DVST)

7. Joy stick

8. Tablet

9. Pointing

10. acoustic Tablet.

BLOCK - III

Simple Line Drawing Methods

Block Introduction : In this block, you will be introduced the concept of writing pictures
on the screen as a set of points. Any picture can be thought of as a combination of points.
The idea is to identify the points which form the part of the picture one is trying to draw
and by a suitable technique display these points. To do this, the screen is supposed to be

30

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
made up of a number of pixels (picture cells), each pixel corresponding to a point. Those
pixels which form a part of the picture being drawn are made to light up so that the
picture is visible on the screen. The trick is to switch on the laser beam (of the CRT)
when it is passing over the pixel and switch it off when it is passing over a pixel that does
not form a part of the picture.

This block tells us about the techniques of identifying those pixels that should
from the part of the picture and the various difficulties that one will have to encounter in
the process. Once the pixels are identified , that hardware takes over the question of
actually drawing the pictures.

Contents :

1. Point Plotting Techniques

2. Qualities of good line drawing algorithms
3. The Digital Differential Analyzer (DDA)
4. Bresenham Algorithm
5. Generation of Circles
6. Block Summary
7. Review Question and Answers

Point Plotting Techniques

The coordinate systems of the monitor: Point plotting techniques are based on the use
of Cartesian coordinate system. Each point is addressed by two points (x,y) which
indicate the distance of the point with respect to the origin
o x

P (x,y)
x xx
x

31

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
y

p (x,y) is pixel at a horizontal distance x and vertical distance y from the origin

Now any picture to be displayed is to be represented as a combination of points

Examples of point plotted pictures:

Though no continuous lines are drawn but only a sense of points are being made bright,
because of the properties of the human eye, we see continuous lines, when the points that
are being lighted are fourly close to each other.

In fact, the closer the points to one another, we see better pictures (see the
example below)

32

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
In the above figure both pictures indicate A, but in the second picture, the points
are closer and hence it appears more like A than the first. How many points are there per
unit area of the screen indicate what is known as the "resolution" of the monitor. Higher
the resolution, we get more number of points and hence better quality pictures can be
displayed (As a corollary, such high resolution monitors are costlier)

Having surveyed the essentials of hardware of CRT once again we are now in a
position to look at the actual process of drawing pictures.

Incre mental methods

The concept of incremental methods, as the name suggests, is to d raw the picture
in stages - incrementally. I.e. from the first point of the picture, we have a method of
drawing the second point, from there to the third point etc. They are also sometimes
called "iterative methods" because they draw picture in stages - in iterations.

Qualities of good line drawing algorithms : Before we start looking at a few basic line
drawing algorithms, we see what are the conditions that they should satisfy. While the
same picture can be drawn using several algorithms, some are more desirable than others,
because they provide as features that enable us to draw better "quality" pictures. A few
of the commonly expected qualities are as follows:

i. Lines should appear straight: Often straight lines drawn by the point plotting
algorithms do not appear all that straight.

Examples of not so straight lines.

33

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

The reason is not far to be searched for. Any point plotting algorithm will give a series of
points (x,y) for various values of x and y. In a general case, the values of x and y need
not be integers, they can be any real numbers. But on the screen, pixel values are only
integers. So, what do we do?. The easy solution is to round off. If two points (successive
points) are given say as (6.6, 15.4) and (7.4, 16) when rounded off 6.6 becomes 7 and
15.4 becomes 15.

So, the point becomes (7, 15) Similarly the second point will become (7,16).
Note that while the difference between 6.6 and 7.4 was 0.8 (almost 1 pixel value) the
display shows then as the some point, whereas the points 15 and 16 are different points.
So the segment, instead of appearing as in fig (a) appears as in fig (b)
 (6.6, 15.4) (7,15)
 (7.4, 16) (7,16)

Note that the slope of the line has changed - A series of such changes between successive
points make the lines look as shown in the fig above (Jagged lines)

ii. Lines should terminate accurately: The cause is still the same as in (1). Because of
inaccuracies and approximations, the lines do not terminate accurately. Either they stop
short of the point at which they should end or extend beyond the points result?
Intersections and joints do not form correctly. Look at the examples below

Required triangle Lines stop short Lines extend beyond

iii. Maintain constant intensity: The pictures are drawn with illumination i.e. a number
of point along the line are illuminated. As long as the intensity of these points is uniform,
we have a pleasing picture to look at. This can be do ne if the points to be illuminated are

34

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
equidistance from one another. However, because of the inaccuracies in the algorithm,
we often end up with either dots which are too close or a bit further from each other.
Obviously two points, close to each other, when illuminated, make the points look
brighter. The result is a line which is brighter in save parts and not so bright in others.
The result will be a line that looks jagged and non uniform.

iv. Lines should be drawn rapidly : This is especially the case in interactive graphics,
wherein lines are drawn in real time. While there may not be much problems with straight
lines, complex figures may need longer computations before the next pants are identified.
Hence the picture is drawn in bits and pieces which may appear unpleasant or even
irritating at times.
Having seen some of the requirements of algorithms, we now see a few practical
algorithms to draw simple figures like straight lines or circles.

The Digital Differential Analyzer (DDA)

These include a class of algorithms which draw lines from their corresponding
differential equations. Before we see the actual algorithms, let us see the concept by the
example of a simple straight line.

The differential equation of a straight line is given by dy = y / x

dx

Looked another way, given a point on the straight line, we get the next point by adding
x to the x coordinate and y to the y coordinate i.e. given a point p(x,y), we can get the
R
x
Q
y x

P x

35

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
next point as a Q(x+ x, y + y) , the next point R as R(x+2* x, y+2* y)etc. So this
is a truly incremental method, where given a starting point we can go on generating
points, one after the other each spaced from it's previous points by an additional x and y,
until we reach the final point.
Different values of x and y give us different straight lines.
But because of inaccuracies due to rounding off, we seldom get a smooth line, but end up
getting lines that are not really perfect.

We now present a simple DDA algorithm in a C like Language.

Procedure DDA (x1, y1, x2, y2)
/* the line extends from (x1, y1) to (x2, y2)*/
{
length = abs (x2 - x1);
if length < abs (y2-y1), then length = abs(y2- y1)
x increment = (x2- x1)/length;
y increment = y2-y1)/length;
x=x1+0.5; y=y1+0.5;
for (I=1;I<=length; i++)
{ plot (trun (x), trun (y))
x = x + x increment;
y = y + y increment;
}
}
we start from the point (x1,y1) and go up to the point (x2,y2)
The difference (x2-x1) gives the x spread of the line (along the x-axies) and (y2-y1)
gives the y spread ( along y axis)
(x2 ,y2 )

y spread

36

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
(x1 ,y1 )
x spread

The larger of these is taken as the variable length (not exactly the length of the line)

The variable x increment and y increment give the amount of shifts that we should
make at a time in each direction. (Note that by dividing by length, we have made one of
them equal to unity. If y2-y1 is larger, then y increment will be unity, otherwise x
increment will be unity. What this means is that in one of the directions, we move by
one pixel at a time, while in the other direction, we have to calculate as to whether we
have to go to the next valve or should stay in the previous value)

Plot is a function that takes the new values of x and y, truncates then and plots
those points. Then we move on to the next valve of x, next value of y, plot it, and so on.

A typical DDA drawn line appears as follows :

Obviously a mean line through these points is the actual line needed.
Note that the line looks like a series of steps. This effect is sometimes called a "Stair
case" effect.

Bresenham algorithm: This algorithm is designed on a very interesting feature of the

DDA. At each stage, one of the coordinates changes by a value 1 (That is because we
have made either (y2- y1) or x2-x1) equal to length, so that either (x2- x1/length or (y2-
y1)/length will be equal to 1). The other coordinate will e ither change by 1 or will remain
constant. This is because, even though the value should change by a small value, because

37

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
of the rounding off, the value may or may not be sufficient to take the point to the next
level.

Look at the above figure. The left most point should have been at the point indicated by
x, but because of rounding off, falls back to the pre vious pixel. Whereas in the second
case, the point still falls below the next level, but because of the rounding off, goes to the
next level. In each case, e is the error involved in the process.

So what the Bresentiam algorithm does is as follows. In each case adds y or x

as the case may be, to the previous value and finds the difference between the value and
the (next) desirable point. This difference is the error e. If the error is +ve, then the point
is incremented to the next level and 1 is subtracted from the value. If e is -ve, we have
not yet reached the point, where we should go to the next point, hence keep the display
pants uncharged.
We present the algorithm below
e=(deeltay/deltax)-0.5;
for(i=1;i=deltax; i++)
{
plot (x,y);
if e>o then
{
y=y+1;
e=e-1;

38

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
}
x=x+1;
e=e+(deltay/deltax);
}
The steps of the algorithm are self explanatory. After plotting each point, find the
error involved, if it is greater than Zero, then in the next step, the next incremental point
is to be plotted and error by error-1; else error remains the same and the point will not be
incremented. In either case, the other coordinate will be incremented (In this case, it is
presented that x - coordinate is uniformly incremented at each stage, while y coordinate is
either incremented or retained as such depending on the value of error)

Generation of Circles

The above algorithms can always be extended to other curves - the only required
condition is that we should know the equations of the curve concerned in a differential
form. We see a few cases.

i) A circle generating DDA :

The differential equation of a circle is dy = -x/y
dx
Hence by using the above principle, we can implement the circle plotting DDA by
using the following set of equations x n+1 = xn + yn and yn+1 = yn - xn

Where the subscript n refers to the present value and n+1 to the next value to be
computed. y and x are the increments along the x and y values.

Unfortunately, this method ends up drawing a spiral instead of a circle, because

the two ends of a circle do not meet. This is because, at each stage, we move slightly
in a direction perpendicular to the radius, instead of strictly along the radius i.e. we
keep moving slightly away from the center. So, in the e nd, we get the closing point a
little higher up than where it is required and hence the circle does not close up

39

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Ideal Circle Drawn by a DDA

However the error can be reduced to a large extent by using the term - x n+1 instead of xn
in the second equation.
i.e. x n+1 = xn + yn
yn+1 = yn - x n+1

Another way of drawing circles is by using polar coordinators

x n+1 = xn cos + yn sin

yn+1 = yn cos - x n sin

Of course, each of them have a few minor disadvantages which are rectified by special
algorithms, discussion of which is beyond the scope of the present course.

Block Summary : In this block, you were introduced to the concept of point plotting. I.e.
drawing the curser point by point. The concept of pixels in the monitor helps you to
calculate the points that form the line (or curve) and these points can be illuminated
giving the picture.

However, because of rounding off errors, certain inaccuracies are introduced in

the pictures so drawn, like non uniform slopes, non uniform illumination and in accurate
terminations.

40

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

The concept of differential analyzer algorithms was introduced - The algorithms

which draw the lines based on the Bresenham algorithms were disc ussed in detail, while
the circle generation algorithms were also introduced.

Review Questions:

1. Higher the resolution, better will be the quality of pictures because the __________
will be closer.

2. An algorithm that draws the next point based on the previous paut's location is called
____________________.

3. The appearance of stair case effect in drawing straight lines is be cause of __________
of mathematical calculations.

4. DDA stands for __________________________

5. The algorithm that ensures a movement of 1 unit at a time in either x or y direction is

the ________________________ algorithm.

6. The common difficulty in drawing circles using DDA method with it's differential
equation is that ______________________.

7. One method to overcome the above problem is to use ______________ equation.

Ans wers

1. Pixels

41

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
2. Incremental method

3. approximation

4. Digital Differential Analyzer

5. Bresenham's

6. the ends do not meet

7. parametric equations.

42

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK - IV

2 Dimensional Transformation

Block Introduction : In this block, you are introduced to the basics of pictures
transformations. Graphics is as much about the concept of creating pictures as also about
making modifications in them. Most often, it is not changing the pictures altogether, but
about making "transformation" in them. Like shifting the same picture to some other
place on the screen, or increasing or decreasing it's size (this can be in one or two
directions) or rotating the picture at various angles - The rotation also can be either w.r.t.
the original x, y coordinates or with any other axis. All these are essentially
mathematical operations. We view points (and hence pictures, which are nothing but the
collections of points) as matrices and try to transform them by doing mathematical
operations on them. These operations yield the new pixel values, which, when displayed
on the CRT give the transformed picture.

[A pre requisite for the block is a very preliminary knowledge of matrices. If the
student is not very confident about the same, he is advised to refresh himself about the
basic definitions and concepts like matrix addition, multiplication, transpose etc., before
attempting to go through the block.]

Contents:
1. What is transformation
2. Matrix representation of points
3. Basic transformation
4. Translation
5. Rotation
6. Scaling
7. Block Summary
8. Review Question and Answers

43

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
What is transformation? In the previous block, we have seen the concept of producing
pictures, given their equations. Though we talked of generating only straight lines and
circles, needless to say similar procedures can be adopted for the other more complex
figures - in many cases a complex picture can always be treated as a combination of
straight line, circles, ellipse etc., and if we are able to generate these basic figures, we can
also generate combinations of them. Once we have drawn these pictures, the need arises
to transform these pictures. We are not essentially modifying the pictures, but a picture
in the center of the screen needs to be shifted to the top left hand corner, say, or a picture
needs to be increased to twice it's size or a picture is to be turned through 90 0 . In all these
cases, it is possible to view the new picture as really a new one and use algorithms to
draw them, but a better method is, given their present form, try to get their new counter
parts by operating on the existing data. This concept is called transformation.

Matrix representation of points : Before we start discussing about the actual

transformations, we would go through the concept of representation of points. Once we
know how to unambiguously represent a pant, we will be able to represent all other
possible pictures.

Normally, we represent a point by two values in a rectangular coordinate systems

as (x,y). x represents the distance of the point from the origin in the horizontal direction
and y in the vertical directions. Negative values are intended to represent movement in
the reverse direction (on a CRT screen, however, negative valued pixels can not be
represented).

However, in the context of graphics we tend to represent a point as a 3 valued

entity [ x y 1] where x and y are the coordinates and 1 is just added to the representation.
But use of this additional value becomes significant shortly.

The basic Transformation : Now we are ready to probe into the basics of
transformations. As indicated earlier, we talk about transforming points, through out the

44

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
discussions, but any complex picture can be transferred using similar techniques in
succession.

The three basic transformations are (i) Translation (ii) rotation and (iii) scaling.
Translation refers to the shifting of a point to some other place, whose distance with
regard to the present point is known. Rotation as the name suggests is to rotate a point
about an axis. The axis can be any of the coordinates or simply any other specified line
also. Scaling is the concept of increasing (or decreasing) the size of a picture. (in one or
in either directions. When it is done in both direc tions, the increase or decrease in both
directions need not be same) To change the size of the picture, we increase or decrease
the distance between the end points of the picture and also change the intermediate points
are per requirements;
Translation:

x Q(x2 ,y2 )

y Ty
(x,y)
x Tx

Consider a point P(x1 , y1 ) to be translated to another point Q(x2 , y2 ). If we know

the point value (x2 , y2 ) we can directly shift to Q by displaying the pixel (x2 , y2 ). On the
other hand, suppose we only know that we want to shift by a distance of Tx along x axis
and Ty along Y axis. Then obviously the coordinates can be derived by x2 =x1 +Tx and
Y2 = y1 + Ty .

Suppose we want to shift a triangle with coordinates at A(20,10), B(30,100 and

C(40,70). The shifting to be done by 20 units along x axis and 10 units along y axis.

45

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Then the new triangle will be at A (20+20, 10+10) B1 (30+20, 10+10) C 1 (40+20, 70+10)
1

In the matrix form [x2 y2 1] = [x1 y1 1] 1 0 0

* 0 1 0
Tx Ty 1

Rotation : Suppose we want to rotate a point (x1 y1 ) clockwise through an angle about
the origin of the coordinate system. Then mathematically we can show that
x2 = x1 cos + y1 sin and
y2 = x1 sin - y1 cos
These equation become applicable only if the rotation is about the origin.

In the matrix for [ x2 y 2 1] = [x1 y 1 1] cos - sin 0

sin cos 0
0 0 1

Scaling : Suppose we want the point (x1 y1 ) to be scaled by a factor sx and by a factor sy
along y direction.
Then the new coordinates become : x2 = x1 * sx and y2 = y1 * sy

(Note that scaling a point physically means shifting a point away. It does not magnify
the point. But when a picture is scaled, each of the points are scaled differently and
hence the dimensions of the picture changes.)
35
30
25 B
20
15
10 B A C
5
A C
5 10 15 20 25 30 35

46

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
For example consider a Triangle formed by the points A (5,5), B(10,10) and C
(10,5). Suppose we scale it by a factor of 3 along x axis and 2 along y axis.

Then the new points will A(5 * 3, 5 * 2)

B(10*3, 10*2) and
C(10*3,5*2)

In the matrix form we get

[x2 y 1 1 ] = [x1 y1 1 ] sx 0 0
0 sy 0
0 0 1
Concentration of the ope rations

Normally, one will not be satisfied with a single scaling or rotation or translation
operation, but we will be doing a sequence of such operations. We may translate by a
factor, scale by some other factor, translate a second time by other factor, rotate . . . . . .
etc. In such cases, we can simply represent the situation by a sequence of matrix
operations. The only constraint is that we should not change the order of operations.
Suppose O1 is the first operation, O 2 is the second operation, O 3 the third etc. Then the
final point will be simply
[P2] = [P1] [O1] [O2] [O3] . . . . .
where [p1] is the original point in matrix form
[P2] is the new point (got after the transformations)
[O1] [O2] … are the respective operations in matrix forms.

In fact, we can also undo some of the operations, if need be, by simply taking up the
converse operations like inversing. In effect, we will be bringing the computations into
the realm of matrix operations, where all the rules of matrix arithmetic become
applicable.

47

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Rotation about an arbitrary point : Note that our rotation formula described previously
is about rotating the point w.r.t. the origin. But most often we do want to rotate our
pictures about points other than the origin, like say the center of the picture we are talking
of, or one of it's vertices or may be a point on a neighboring picture. In this concluding
section on transformations, we perform the operation of rotating a point (x1, y1) about
another arbitrary point (Rx, Ry).

This is also supposed to provide you an insight about the ease with which matrix
representation of operations allow us to Performa a sequence of operations.

First, how do we sequence the operations in the case?

Since we know how

i) to translate any point to any other point
ii) to rotate it by any angle w.r.t. the origin and
iii) to scale a point, we should be able to combine these operations to do the
required transformation.

R (Rx, Ry)
y x
xP (x,y)

o x

Now if we look at the figure, we know how to rotate the point w.r.t. O, the origin,
whose coordinates are (0,0). But we should rotate it about the point R(Rs, Ry).
Looking other way, we could have rotated P about R, if the coordinates of R were
(0,0), or if we make the coordinates of R as (0,0). We can make the coordinates of R
as (0,0) if we shift the rigin to R, (as shown by dotted lines). If we do that, then we
can rotate P about R. But we can shift the origin to

48

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
R ( or shift R to the origin, say) and make corresponding adjustments in the
coordinates of P. (In practice, we simply evaluate what would be the value of (x1,
y1), if instead o, R were the origin and we start measuring from R. This could be
easily done by subtracting the difference of x and y values of R and origin (i.e. Rx &
Ry) from the coordinates of (x, y). The new values, x1 1 and y1 1 referee to the
coordinates w.r.t. R. Now since R is the origin, we know the formula for rotation P
w.r.t. R by an angle .

We do the operation and get the picture.

But the only hitch is that the whole sequence is about the point R, but it should
have been w.r.t. origin. So, to get the desired picture from this, shift the origin back
to O. Then we get the desired picture.

Now we can list the sequence of operations as follows.

i) Shift the origin to (Rx, Ry) from (o,o)
Using the matrix 1 0 0
0 1 0
-Rx - Ry 0

ii) Rotate the point P(x1, y1) w.r.t. the (new) origin by

cos - sin 0
sin cos 0
0 0 1

iii) Shift the origin back to (o,o) by

1 0 0

0 1 0
Rx Ry 1

49

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Hence the required point is

[x2 , y2 1] = [ x1 y1 1] 1 0 0 cos - sin 0 1 0 0

0 1 0 sin cos 0 0 1 0

-Rx - Ry 0 0 0 1 Rx Ry 1

Block Summary : You have been introduced to the concept of transformation of

pictures, by transforming (normally) the end points of the picture. The basic
operations are transformation, rotation and scaling. Though each of these can be
done by modifying the values x & y it is desirable to perform them as matrix
operations, since such an operation would allow us to perform a lay sequence of
operations on the picture as a sequence of matrix multiplications, are example to
provide the statement has also been given.

Review Questions :

1. If a point (x,y) is moved to a point which is at a distance of Tx along x axis what is

it's new position?

2. If a point (x,y) is moved to a point which is at a distance Ty along y axis, what is

it's new position.

3. If a point (x,y) is rotated anticlockwise through an angle about the origin, what
are it's new coordinates.

4. Write the equation for scaling transformations.

5. How many values does the matrix representation of a point (x,y) has ? What are
they?

50

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
6. Give the matrix formulations for transforming a point (x,y) to (x1, y1) by
translation

7. A point (x,y) is to be moved through an angle clockwise about a point (px, py).
What is the sequence of operations.

Ans wers

1. (x+Tx, y)

2. (x, y+Ty)

3. (xcos(- ) + y sin (- ), - xsin ( - ) + ycos ( )

= (xcos - ysin , xsin + ycos ( )

4. x1=xsx, y1=ysy

5. 3 values (x y 1)

6. [ x1 y1 1] = [x y 1] 1 0 0
0 1 0
Tx Ty 1

7. Translate (px, py) to origin, effect the rotation Translate the point back to it's
original position.

51

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

BLOCK – V

CLIPPING AND WINDOWING

Block Introduction : In this block, you are introduced to the concepts of handling
pictures that are larger than the available display screen size, since any part of the
picture that lies beyond the confines of the screen can not be displayed. We compare
the screen to a window, which allows us to view only that portion of the scene outside
as the limits of the window would permit. Any portion beyond that gets simply
blocked out. But in graphics, this “blocking out “ is to be done by algorithms that
decide point beyond which the picture should not be shown. This concept is called
clipping. Thus, we are “clipping” a picture so that it becomes viewable on a
“window”.

The other related concept is the windowing transformation. It is not always

necessary that you clip off the larger parts of the picture. You may resolve to zoom it
to lower sizes and still present the whole picture. This concept is called windowing.
Here you are not cutting off the parts beyond the screen size, but are trying to prepare
them to a size where they become displayable on the screen. Again, such a
“prepared” picture need not occupy the complete window. In fact, it may be possible
for you to divide the screen into 2 or more windows, each showing a different picture.
Then, the pictures will be “prepared” to be “fitted” not to the entire screen, but to
their respective windows.

Since all these operations are done at run time, it is necessary that the algorithms
will have to be very fast and efficient. We introduce you to a few clipping and
windowing algorithms, in this block.

52

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Contents :
1. Need for Clipping and Windowing
2. Line Clipping Algorithms
3. The midpoint subdivision Method
4. Other Clipping Methods
5. Suther land - Hodgeman Algorithm
6. Viewing Transformations
7. Block Summary
8. Review Question and Answers

53

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Need for Clipping and Windowing

The size of a CRT terminal on which the pictures are displayed is limited – both
the physical dimensions and it‟s resolution. The physical dimensions limit the
maximum size of the picture that can be displayed on the screen and the resolution
(no. of pixels/inch) limits the amount of district details that can be shown.

Suppose the size of the picture to be shown is bigger than the size of the screen,
then obviously only a portion of the picture can be displayed. The context is similar
to that of viewing a scene outside the window. While the scene outside is quite large,
a window will allow you to see only that portion of the scene as can be visible from
the window – the latter is limited by the size of the window.

Similarly if we presume that the screen, which allows us to see the pictures as a
window, then any picture whose parts lie outside the limits of the window cannot be
shown and for algorithmic purposes, they have to be “clipped”. Note that clipping
does not become necessary only when we have a picture larger than the window size.
Even if we have a smaller picture, because it is lying in one corner of the window,
parts of it may tend to lie outside or a picture within the limits of the screen may go
(partly or fully) outside the window limits, because of transformation done on them.
And what is normally not appreciated is that as result of transformation, parts which
were previously outside the window limits may come within limits as well. Hence, in
most cases, after each operation an the pictures, it becomes necessary to check
whether the picture lies within the limits of the screen and if not, too decide as to
where exactly does it reach the limits of the window and clip it at that point. Further,
since it is a regular operation in interactive graphics, the algorithms to do this will
have to be pretty fast and efficient.

The other related concept is windowing. It is not always that we cut down the
invisible parts of the picture to fit it into the window. The alternate option is to scale
down the entire picture to fit it into the window size i.e. instead of showing only a

54

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
part of the picture, it‟s dimensions can be zoomed down. In fact, the window can be
conceptually divided into more than one window and a different picture can be
displayed in each window, each of them “prepared” to fit into the window.

In a most general case, one may partly clip a picture and partly transform it by
windowing operation. Also, since the clipped out parts cannot be discarded by the
algorithm, the system should be able to keep track of every window and the status of
every picture in each of them and keep making changes as required all in real time.

Having seen what clipping and windowing is all about, we straightaway introduce
you to a few clipping and windowing algorithms.

A Line Clipping Algorithm

Look at the following set of lines.

The rectangle indicates the screen in which they are to be displayed.

How to decide which of the lines, or more precisely which part of every
line is to be displayed. The concept is simple. Since we know the coordinates of the
screen,
55

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

i) any line whose end points lie within the screen coordinate limits will have
to displayed fully (because we cannot have a straight line whose end
points are within the screen and any other middle point in outside).
ii) Any line whose end points lie totally outside the screen coordinates will
have to examined to see if any intermediate point is inside the screen
boundary.
iii) Any line whose one end point lies inside the boundary will have to be
identified.

In case of (ii) and (iii), we should decide upto what point, the line segment can be
displayed. This can be done by simply finding the intersection of the line with the
screen boundary.

Though on paper the concept appears simple, the actual implementation

poses sufficient problems. We now see how to find out whether the respective
end points lie inside the screen or not. The subsequent sections will inform us
about how to go about getting the intersection points.

The Four bit code

1001 1000 1010

screen
0001 0000 0010
0101 0100 0110

Look at the above division of region. Each region is given a code of 4

bits. They are assigned to their values based on the following criterion.

56

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
First bit : will be 1 if the point is to the left of the left edge of the screen.
(LSB)
Second bit : 1 if the point is to the right of the right edge.
Third bit : is 1 if the point is below the bottom edge and
Fourth bit: is 1 if the point is to the top of the top edge.
(MSB)
The conditions can be checked by simply comparing the screen coordinate values
with the coordinates of the endpoints of the line.

If for a line, both end points have the bit pattern of 0000, the line can be
displayed as it is (trivially).

Otherwise, the pattern of 1 s will indicate as to with respect to which particular

edge the intersection of the line is to be verified.

For example if one of the points of a straight line shows 1000, then it‟s inter
section w.r.t. to the top edge needs to be computed (since the point is above the top
edge). If for the same line, the other point returns 0010, then since a segment of the line a
beyond the right edge, the intersection with the right edge is to be computed.

(The students are encouraged to write a simple algorithm which accepts the end
points of a straight line, find out whether it needs any clipping and if so w.r.t. which
edges).

Having decided that we need clipping to be done, we look at algorithms that

compute the intersections of the line w.r.t. the edges efficiently.

57

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
The Midpoint subdivision method

While mathematical formulae exist to compute the intersection of two straight

lines (in this case, the edge under consideration and the straight line to be clipped) it
ecomes computationally intensive and hence another efficient method has been
developed. As you know, multiplication and division are most time consuming and
hence an algorithm that minimizes on multiplications and divisions is always considered
superior. The algorithm in question can be seen to be very efficient in minimizing the
divisions that occur, when the intersection of two straightline are computed directly.

P2
P2 1
P1 1

P1

Consider a straight line P1 P2. We have decided, (based on the earlier suggested
algorithm) that the point P11 is visible while the point P2 is not. The point is that we
should find a point P1 which is the point farthest from P1 and still visible. Any point
beyond P1 1 becomes invisible. The question is to find P 1 1.

The algorithm processes by dividing the line P1 P2 at the middle. Hence the
name mid point division. Let us say the point is P1 1 . This point, in this ease is visible.
That means the farthest visible point away from P 1 1 . So divide the segment P1 1 p2 at the
middle. In this case, the new mid point P 2 1 is invisible. So the farthest visible point is
between P1 1 P21 So divide the segment into two and so on, until you end up at a point
that cannot be further divided. The segment P1 to this point is to be visible on the screen.

58

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Now we formally suggest the mid point division algorithm.

Algorithm mid point s ubdivision :

1. Check whether the line P1 P2 can be trivially included. i.e. when both P1 and P2 are
visible. If so exit. else
2. check the point P1 which is visible and the other point P2 which is invisible.
3. Divide the segment P1 P2 at P 11 check if P1 1 is visible if so, the farthest point is
beyond P1 1 , so proceed by dividing P1 1 P2 else divide the segment P1 P1 1
4. Repeat step (3) until the segment to be divided reduces to a single point. The segment
to be displayed is bound by P1 and this point.

and
(Note: if in step2, both P1 P2 are invisible, we have to first divide the line, take a
visible point and then repeat the algorithm twice for both the segments)

Other clipping methods

In general, the graphic pictures involve much mere than more s traight lines.
Curves, if any can be considered as a series of straight lines and each of them can be
clipped based on requirements. However, dividing the curve into a series of straight lines
may not be very efficient in many cases. One other method is to consider the curves as
polygons and use the polygon clipping algorithm, which will be introduced in the next
section.

The other difficulty is about characters. It is normal practice not to clip

characters. Either they are shown in full if only a small portion of it is to be clipped,
otherwise the entire character is clipped. The normal practice is to divide the character at
the middle. If the portion to be clipped lies on the farther side of this middle line, the
entire character is deleted otherwise the entire character is seen.

59

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Polygon clipping

A polygon is a closed figure bounded by line segments. While common sense

tells us that the figure can be broken into individual lines, each being clipped
individually, in certain applications, this method does not work. Look at the following
example.

A
A

B
B

Original Figure Clipped Figure

A solid arrow is being displayed. Suppose the screen edge is as shown by dotted
lines. After clipping, the polygon becomes opened out at the points A and B. But to
ensure that the look of solidly is retained, we should close the polygon along the line A-

B. This is possible only if we consider the arrow as a polygen – not as several individual
lines.

Hence we make use of special polygon clipping algorithms – the most celebrated
of them is proposed by Suther land and Hodgeman.

60

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Suther land - Hodge man algorithm

The basis of the Suther land Hodgeman algorithms is that it is relatively easy to
clip a polygon against one single edge of the screen at a time i.e. given a complete
polygon, clip the entire polygon against one edge and take the resultant polygon to clip
against a second edge and so on until all the four edges are covered. At first sight, it
looks like a rather simplistic and too obvious a solution, but when put in practice this has
been found to be extremely efficient.

Now to the algorithm. An algorithm can be represented by a set of vertices v1 , v2 ,

v3 -------------- vn which means there is an edge from v1 to v2, v2 to v3 . . . .. . . . vn to v1
(we consider only closed polygons and even after clipping would like to have closed
polygons, the only difference being that the edges of the screen make for some of the
edges of the newly formed, clipped polygon).

The algorithm tests each vertex vi (i=1,2 . . . . . . . .. . . . .n) in succession against a

clipping edge e. Now e is an edge of the screen and has two sides. Any vertex lying on
one side of the edge will be visible (which we call the visible side) While any other
vertex will not be visible if it is on the other side (the invisible side). (For example for
the top edge of the screen, any vertex above it is on the invisible side whereas any vertex
below it is visible. Similarly for the left edge, any point to it‟s left is invisible but an
edge on it‟s right is visible and so on). Now coming back to the algorithm. It tests each
vertex of the given polygon in turn against a clipping edge e. Vertices that lie on the
visible side of e are included in the output polygon, while those that are on the invisible
side are discarded. The next stage is to check whether the vertex vi (say) lies on the same
side of e as it‟s predecessor vi-1. If it does not, it‟s intersection with the clipping edge e is
to be evaluated and added to the output polygon.

We formally see an algorithm and also the application of the algorithm to a

specific example.

61

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Algorithm sutherland – Hodgeman (v1, v2 v3 . . . .. . . . vn)

For i 1 to n do
if (i>1) then begin check whether the line
v[i] V[i-1] intersects the edge e, ifso, compute the intersection
and output the intersection point as the next out put vertex
end;
check always whether vi is on the visible
side of e
if so output vi
if i<n, go to (1)
else
Check whether the line Vn-V1 intersects e
if so, compute the intersection
and output it as the next edge
of the output polygon,
always return.

Now to illustrate this algorithm consider the 5 edges polygon below.

V2

V1 V3
V4
V4

V5

62

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Now, let us consider ab as the clipping edge e.
Beginning with v1
the vertex v1 is an the visible edge of ab
so retain it in the output polygon

now take the second vertex v2, the vertices v1, v2 are on different side of a.

Compute the intersection of V1, V2 let it be i1, add i1 to the output polygon.

Now consider the vertex v3, v2 and v3 are an different sides of ab. Compute the
intersection of v2 and v3 with ab. Let it be i3. include i3 in the output polygon. Now
consider v3, v4 and v5 are all on the same side (visible side) of the polygon, and hence
when considered are after the other, they are included in the output polygon straightaway.

Now the output polygon of stage (1) looks like in the figure below

i1 i2

V3
V1
V4

V5

Now repeat the same sequence with respect to the edge b c, for this output polygon of
stage (1)

63

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
v1, i1 and iz are on the same side of bc and hence get included in the output polygon of
stage (2) since iz and v3, are the different sides of the line be, the intersection of bc with
the line iz is is v3 computed. Let this point be i3 . Similarly, v3, v4 are an the different
sides of bc, their intersection with be is computed as i4, v\4, v5 are on the same sides of bc
and hence pass the test trivially.

Now the output polygon looks like this:

i1 i2

i3
v1

v4 i4

v5

After going through two more clippings against the edges cd and da, the clipped figure
looks like the one below i1 i2

i8 i3
i7 i4
v4

i6 i5

64

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
It may be noted that the algorithms works correctly for all sorts of polygons.

VIEWING TRANSFORMATIONS

Assuming a screen of some size say 1024 x 1200 pixels, this size given the
maximum size of the picture that we can represent. But the picture on hand need not
always be corresponding to these sizes. Common sense suggests that if the size of the
picture to be displayed is larger than the size of the screen, two options are possible (i)
clip the picture against the screen edges and display the visible portions. This will need
fairly large amount of computations, but in the end, we will be seeing only a portion of
the picture. (ii) Scale down the picture (We have already seen how to enlarge/scale down
a point or a set of points by using matrix transformations). This would enable us to see
the entire picture, though with a smaller dimensions.

The converse can also be true. If we have a very small picture to be displayed on
the screen, we can either display it as it see, thereby seeing only a cramped picture or
scale it up so that the entire screen is used to get a better view of the same picture.

However, a picture need not always be presented on the complete screen. More
recent applications allow us to see different pictures on the different part of the screen.
i.e., the screen is divided into smaller rectangles and each rectangle displays a different
picture. Such a situation is encountered when several pictures are being viewed
simultaneously either because we want to work on them simultaneously or we want to
view several of them for comparison purposes. Now, each of these smaller rectangles
that form the space for one such picture is called a “window” and it should be possible
for us to open several of these windows at one time and view the pictures. In s uch a
scenario, the problem is still the same: of trying to fit the picture into the rectangle meant
for it. i.e., of scaling the picture into it‟s window. The only change is that since the
window sizes are different for different pictures, we should have a general transformation
mechanism that can map a picture of any given size to fit into any window of any given
size. Incidentally we call the coordinates system of the picture as the “world coordinate”

65

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

This concept of mapping the points between the two coordinate systems is called
the “windowing transformation”

Generally, when the rectangle in which we display the picture on the screen is
smaller than the entire screen size, it is called a view port and in such a case the
transformation can be called a “View Port Transformation”.

Now we derive a very simple and straightforward method of transforming the

world coordinates to the full screen coordinates (or for that matter any window size)

Since different authors use different nomenclatures, in this course, we follow the
following conventions. A picture in it‟s normal coordinates system is in the “world
Coordinate” system. We are interested only in a part of this picture. That part of picture
in which we are interested is called the “window”.

Now we want to transform the portion of the picture that lies within this window
to fit into a “viewport”. This view port can be a part of screen or the full screen itself.
The following diagrams illustrate the situation and also the various coordinate values that
we will be using

wyt

wyb

wx1 wxr

66

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
The dotted lines indicate the window while the picture is in full lines. The
window is bounded by the coordinates wx1 and wxr ( the x-coordinates on the left side of
window and the x – coordinates on the right side of the window) and wyt and wyb ( The y-
coordinate on the bottom of the window). It is easy to see that these coordinates enclose
a window between them (The dotted rectangle of the figure),

We can correspondingly think of a view port rectangle.

vyt

vyb

vxc vxr
Screen

The nomenclature is the same as before.

Now consider any point (xc w yws) on the window. To convert this to the view port
coordinates, the following operations are to be done in the sequence.

i) Scale the window coordinates so that the sizes of the window and the view port
match. This will ensure that the entire window fits into the view port without
leaving blank spaces in the view port. This can be done by simply changing the x

67

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
and y coordinates in the ratio of the x-size of view port to the x size of window
and y – size of view port to y – size of the window respectively
i.e. vxr – vx1 and vyt – vyb
wxr – wx1 wyt – wyb

It may be noted that in each of the above ratios, the numerator defines the overall
space available in the view port and the denominator, the overall space available in the
window.

ii) Since the origins of the window and view port need not be coinciding with their
world coordinate systems and the screen coordinate system respectively we have
to shift them correspondingly. This can be achieved by the following sequence.

a) Before scaling, shift the origin of the window to the origin of the world coordinates.
b) Perform the scaling operation.
c) Shift it back to reflect the difference between the screen origin and view port origin.

Now considering any point (xw, yw) to be transformed, we get the following sequence on
applying the above sequence of operations.

a) xw – wx1 and yw – yyb

b) Vxy – Vx1 (xw-wx1) and Vyt – Vyb (yw – wyb )
Wxr – Wxl Wyt - Wyb

c) Vxy – Vx1 (xw-wx1 ) + Vx1 Vyt – Vyb (yw – wyb ) + Vyb

Wxr – Wxl Wyt - Wyb

The equation in the step c indicate the complete window to view port transformation.

Before closing this section a few observations:

68

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
i) It is may not be necessary to transform all the points using the above formula.
Regular figures like straightlines or regular curves can be transformed by
transforming only their end points.
ii) Since more often than not a transformation from window to view port involves
certain portions getting clipped in the process, it is desirable to run a clipping
algorithm on the picture w.r.t. the view port so that unnecessary points are not
computed only to be thrown off latter.

Block Summary

In this block, you were introduced to two basic concepts of graphics namely
clipping and windowing. When the size of the picture to be displayed is larger than the
screen size, the portions that go out of the screen are to be “Clipped off” by computing
their points of intersection w.r.t. the screen edges. The Suther land Hodgeman algorithm,
which does the same elegantly for polygons was introduced. Since most pictures can be
thought of as polygons with sides of varying numbers and sizes, this would be a very
general and useful algorithm.

The other concept introduced was windowing. When a portion of a picture

computed in the world coordinates (or a picture in a window) is to be transformed into a
rectangle in the screen ( a view part) each point on the transformed picture is to be
correspondingly mapped. The exact formula was derived by showing that it comprises
only of shifting and scaling operators.

69

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Review Questions
1. Define Clipping
2. Define Windowing
3. Explain the 4 bit code to define regions used in rejection method.
4. What is the other name of the most popular polygon clipping algorithm?
5. With usual notations, state the equations that transform the window coordinates to
screen coordinates.

Ans wers
1. The process of dividing the picture to it's visible and invisible portions, allowing the
invisible portion to be discarded.
2. Specifying an area (or a window) around a picture in world coordinate, so that the
contents of the window can be displayed or used otherwise.

3.
1001 1000 1010

0001 Screen 0010

0000
0101 0100 0110

4. Sutherland - Hodgeman algorithm

5. Vxy – Vx1 (xw-wx1 ) + vx1 )
Wxr – Wxl

c) Vyt – Vyb (yw-wyb) + Vyb

Wyt – Wyb
(xs, ys) are the screen coordinates vxr and vx1 are the right and left edges of the view port,
vyt and vyb are the top and bottom edges of the view port, wxr, wx1 , wyt and wyb are the
corresponding edges of the window., (xw, yw) are the window coordinates .

70

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK – VI

Graphical Input Techniques

Block Introduction : We have familiarized ourselves with many of the interactive input
devices. But since the computer expects perfect input values, any errors made in the use
of such devices can create problems - like not drawing the lines completely on the tablet
or overdrawing it. Similarly, the end points of lines may not appear exactly on a pixel
value. One can go on listing such in accuracy's, which would make the computer's
understanding of the situation difficult. On the other hand, insisting that one should be
able to draw perfectly, also is not advisable. Hence, several techniques are available that
can cover up for the deficiencies of the input and still make the computer work
satisfactorily.

In this block, you will be introduced to various positing techniques using

positional constants, concept of modular constraints, ability to draw straight lines
interactively using rubber hand techniques selection and the concept of menus. The
implementation details, however, are omitted.

Contents

1. Graphical Input Techniques

2. Positioning Techniques
3. Positional Constraints
4. Rubber band Techniques
5. Block summary
6. Review Question and Answers

71

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Graphical Input Techniques: We have seen several input devices which bear
resemblance to pens and pencils – example light pens, joysticks etc., To some extent they
are intentionally made to resemble the device that the user is familiar with. For example,
writing on a pad with a pen like stylus is more convenient for the user. However, there is
a basic difference between the targets of such inputs i.e. a material written with a pen are
targeted towards the human user, while the graphical input derives are targeted towards
the computer. Herein lies the difference. The human can understand variations of input
to a large extent. For example the letter A may be written in different ways by different
people or for that matter, the same person may write it in different ways at different
times. While a human can understand the variations, a computer normally cannot. In
other words, the input to human can vary over a range, while the inputs to a computer
needs to be precise. Similarly while drawing a circle, if the two ends do not meet
properly, a human being can still consider it as a circle, whereas a computer may not. At
the same time, training a person to say, precisely write the letters in the same manner,
trial after trial, or to make him draw his graphs to the exact precision would be time
consuming. In other words, whereas a common user can be made to be aware of what he
wants and would be willing to get it as fast and accurately as possible, making him
acquire graphic arts skills would be inexcusable. On the other hand, it is desirable to
make the computer understand what he wants to input or alternately, we can make the
input devices cover up for the miner lapses of the user and feed a near perfect input to
the computer – like making it cover the circle, when the user stops just short of closing it
or ends up making the two ends one next to the other. There are several astonishingly
simple ways to make the life of the user more comfortable and at the same time improve
effectiveness of the input device.

In other words, the graphical input device should not only be influenced by the
way it is used, but should also consider other factors like what the user is trying to say or
what is the next logical step in the sequence of events and extrapolate or interpolate the
same. Of course, some guess work is involved in the process, but most often it should
work satisfactorily.

72

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
In fact, the very simple concept of cursor is a good example of input technique. It
can be thought of as a feedback technique. It indicates the present position of editing /
operation. In a more sophisticated case, it can be a “block” of the text / figure selected by
blocking. It helps the user to know what he is doing and in fact, ascertains that the
function that he is working on is actually working.

However, in this chapter, we look at slightly more sophisticated user friendly

techniques. The algorithms are fairly involved and hence we will only be discussing the
details, without going into the implementation details.

Positioning Techniques

This can be considered the most basic of graphical input operations. In it‟s
simplest form, it involves choosing a symbol / character on the screen and moving it to
another location. One way of using it is to choose the symbol or picture involved,
moving the cursor to the position required and pressing a (predetermined) key to place in
that position.

Choose a Symbol Choose a Position End of operation

While in earlier DOS versions, this operation was being done by using a
combination of preselected keys in proper order, the advent of mouse has simplified the
matter. The concept of selection, positioning and fina l movement are all done with the
click of buttons.

73

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Positional Constraints

One of the problems faced by inexperienced users while drawing figures is the concept of
positioning. For example, we may want to put an object exactly at the end of a straight-
line or a cross at the centre of the circle etc. Because of lack of coordination between the
eyes and the hand movements, the object may end up either a little away from the line or
inside the line as below.

Desired position Away from the end Inside the line

Similarly, while locating a centre of the circle the cross may get located very near
to the centre of the circle, but not exactly at the centre. In fact, it is easy to appreciate
that in the case of putting a rectangle at the end of the straight lines one may often end up
operating between the second and third stages several times before (if at all) successfully
reacting the position of (i). One of the methods of helping the user is to put a “construct”
on the position of the box. i.e. when the distance between the box and the end of the line
is very small, the box automatically aligns itself on the edge of the line. i.e. it is enough
if the user brings it to either of the positions (ii) & (iii) and the software automatically
aligns it to position (i).

Though we are not considering the implementation aspects of the same, it is easy
to note that writing an algorithm for this is fairly straight forward. Assuming each line
ends at an integer value of the pixel, if the edge of the base is brought to a value which is
a fraction above / below the value, automatically round it off to the pixel value. For
example, if the (x,y) values of the end of the lines is say (10,50) and a box is brought to

74

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
a position say (10.6, 50.7), the values are automatically changed to (10,50), similar being
the case if the box position is say (9.7, 49.8). It is easier to see that the first example is
the case where the box is slightly above the line and the second where it is inside the line.

This type of putting constraints is often called a “modular constraint”. There can
be other types of constraints as well. In a certain figure, only horizontal and vertical
lines are there, say like in a grid design, any angular lines can be brought into any one of
these positions by putting an angular constraint that no straight line can be at any angle
other than 00 and 900 . The same can be extended to draw lines at any particular angle.

Now let us go back to the problem of attaching a box to the end of a line.
Suppose the end of the line does not terminate always at integer value. Then positional
constraints cannot be used. In such cases, we can think of gravity constraints, wherein
the box gets attached to the line because of the “gravitational force” of the line. i.e. it
gets attached to the nearest free point which forms the end of line. Again this relieves the
user of the difficulty of exactly putting the box to the end of the line.

Rubber band techniques

Rubber banding is a very simple, but useful technique for positioning. The user,
if he wants to draw a line, say, specifies the end points and as he moves from one point
to another, the program displays the line being drawn. The effect is similar to an elast ic
line being stretched from one point to another and hence the name for the technique. By
altering the end points, the position of the line can be modified.

The technique can be extended to draw rectangles, arcs, circles etc., The
technique is very useful when figures, that pass through several intermediate points, are
to be drawn. In such cases, just by looking at the end points, it may not be possible to
judge the course of the line. Hence, the positioning can be done dynamically, However,
rubber band techniques normally demand fairly powerful local processing to ensure that
lines are drawn fast enough.

75

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Dragging : As the name suggests, it involves choosing a symbol or a portion of a figure

and positioning it at any desired point. It is possible to achieve a accurate and visible
results without bothering to know about the actual coordinates involved.

Dimensioning Techniques : It is often desirable to display the coordinate position or the

dimensions along with the object. This would be helpful in ascertaining the location of
the object, when mere visible accuracy of location may not be enough, but they may
have to be positioned w.r.t. the actual coordinate system.

80, 100

80, 60

30, 40

The more difficult problem is that the coordinates need to keep changing as the
figure is being dragged around and this demands rapid calculation on the part of the
system.

Normally the dimensions are displayed only when the object is being manipulated
or moved around and will stay only long enough for the user to take note of the m. This
ensures that they do not obscure the active parts of the picture, once the completed
picture is on display.

Selection of Objects : One of the important points to be addressed is to select parts of the
picture for further operations. Once the selection is made properly, tasks like moving,
deletion, copying are whatever can be done. But the actual selection process poses
several problems.

76

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
The first one is about the choice of coordinates. When a point is randomly chosen
at the starting point of the selection process, the system should be able to properly
identify it‟s coordinates. The second problem is about how much is being selected. This
can be indicated by selecting a number of points around the figure or by enclosing the
portion selected by a rectangle. The other method is to use multiple keys. i.e. position
the cursor at the first point of selection, press certain combination of keys, move the
cursor to the final position and again press certain combination of keys, so that the figure
lying in between them is selected. The mouse facilitates the same operation by the use
of multiple buttons on it. Once the selection is made, normally the system is supposed to
display the portion selected so that user can know he has actually selected what he had
wanted to. This feed back is done either by changing the color of the screen, modifying
the brightness or by blinking.

Menu selection : This is one of the special cases of selection where the user would be
able to choose and operate from a set of available commands / figures displayed on the
screen. This concept is called the “menu” operation, where you select the item from
those available on the menu card. The use of mouse an input technique normally implies
menus being provided by the system. The menu concept helps the user to overcome the
difficulty of having to draw simple and often used objects by providing them as a part of
the system.
Block Summary

In this block, you were introduced to the concept of providing additional facilities
to the user while inputting the data. The basic concept is not to expect the user to have
graphical art skills, but allow him to concentrate on the actual work. Several techniques
to ensure that the object is positioned accurately at the desired position, even if slight
inaccuracies in placement is made. Similarly the concept of “constraints” was used to
facilitate the system understand the intentions of the user and cover- up minor
inaccuracies in inputting of data.
Several other concepts like rubber band techniques, dragging and menu selection
to reduce the effort on the part of the user were discussed.

77

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Review Question :

Name the type of input facility available to the user in each of the following cases

1. Moving a pictures from one place to another.

2. Making a line meet another box accurately.

3. Ending a line exactly an a pixel.

4. Drawing a straight line interactively

5. Showing the x, y coordinates of points as the lines are being drawn.

6.. Choosing one out of a number of options.

Ans wers :

1. Dragging

2.. gravitational constraint

3. Modular constraint

4.. Rubber band technique

5. Dimensioning technique.

6. Menu selection.

78

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

UNIT - 2

Unit Summary
In this unit, we familiarise ourselves with some of the advanced topics in
computer graphics. We intend looking at the 3 rd dimension of the objects. Most objects
that we encounter in day to day life, as well as in design, simulation etc. Are 3
dimensional screen, the problem of displaying them in such a way that the cue of depth
is not lost assumes great significance. Several methods are available, but we see a few of
them in this unit. The most important of them being parallel projection. This is the way
the human eye visualises the objects. Those features of the object that are for away from
the observer appear smaller in contrast to those features of similar dimensions that are
nearer to the eye. There are other methods also, but we may not deal with them in great
detail. Of course, we will also see how to represent the three dimensional objects using
the conventions similar to those used to represent two dimensional ones. This constraint
ensures that the methods developed for the 2-D applications become applicable for 3-D
also of course with minor changes. We see that the concepts of transformation clipping
and windowing apply here also, but additional computations are involved, since the third
dimension involves additional constraints.
We also see the concept of solid area scan conversion. While a figure with a
boundary, like a rectangle, is drawn, most often we don't get the idea of the area inside
the figure. For example a ring and a disk appear alike. To take care of these, we need to
fill the inside, where ever necessary. This concept is called scan conversion. The
concept of identifying not only those pixels that lie on the picture, but also to identify
those that lie inside and distinguish them from the other pixels is of primary importance
in presenting realistic pictures.
The other aspect dealt in detail in the concept of hidden surface removal. The
basic concept in conveying the idea of depth is that areas or object that are far away, if
are covered by any other nearby objects, will not become visible. Identifying those areas
and removing them from display is important. However, in moving pictures like those in
animation, the areas hidden and visible keep changing and to present the viewer with a
realistic feature needs fast computations to be done. Hence several methods to speed up

79

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
the computations using additional information about the geometry etc. Of the display
area are also presented.

80

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK – I

THREE DIMENSIONAL GRAPHICS

BLOCK INTRODUCTION

In this block, we get ourselves introduced to the realm of 3-dimensional graphics.

Through 2-dimensional pictures help us in a number of areas, there are several
applications where it is simply not sufficient to meet the requirements. We look into
those areas where 2-D displays fall short of the demands initially. Then, since we have
only a 2-dimensional display to represent 3-dimensional objects we briefly look into the
various alternatives available for the user in brief. Of course, in the subsequent blocks,
we study same of them with greater depth.

Contents:
1. Need for 3-Dimensional Imaging
2. Techniques for 3-Dimesional displaying
3. Parallel Projections
4. Perspective projection
5. Intensity cues
6. Stereoscope effect
7. Kinetic depth effect
8. Shading
9. Block Summary
10. Review Question and Answers

81

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Need for 3-Dime nsional Imaging
There are several areas of applications where 2-D imaging is not sufficient we
look into some of them in brief.

a. Computer Aided Design (CAD): Computer generated images are of

atmost use in several design applications like those of automobiles,
aircraft‟s, mechanical parts etc. Since the computers can do fast
computations and the displays can draw them for the visual analysis of
the designer, CAD has gained immense popularity in recent years.
Obviously, a mere 2-dimensional picture seldom tells the complete
story. Further, design details like fixtures etc can be studied only in 3-
Dimensions. Hence the use of 3-Dimensional pictures is obviously the
key in CAD.
b. Animation : This is another fast growing area, A sequence of pictures
that educate or explain some concept or simply are of entertainment
value are presented with motion incorporated. In such cases, mere 2-
dimensional animation is of little interest and the viewer is to be
treated to a virtual concept of depth.
c. Simulation : There are certain experiments that are either too costly or
for certain other reasons can not be conducted in full scale reality. In
certain other cases, a preliminary sequence of oeprations are done on
the computer before a full fledged experimentation is taken. The
examples of flight simulation or nuclear testing illustrate the concepts.
In a flight simulation case, the trainee is made to “Experience” real
flight even though he is stationery. In such a case, definitely a 2-
Dimensional simulation is of very little use and for the trainee to
experience fully the various complexities involved, an experience of
depth is to be provided. Similarly in the case of a nuclear testing, a
realistic study can be made only by having a 3-dimensional view on
the screen.

82

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
In fact, the list of applications that need 3-D views can go on endlessly. Instead,
we simply underline the fact that using the 2-dimensional screen to provide a 3-
dimensional effect is of prime importance and move on to the various ways in which this
can be achieved.

Techniques for 3-Dimensional displaying

At the outset itself, it is to be made clear that since we are using a 2-dimensional
screen for a 3-dimensional display, what we can achieve is only an approximation. Even
this approximation is achieved at the cost of computational overheads i.e. additional
computation are to be done before a picture can be fitted into a 2-D screen. Further there
is a limit to the amount of computations that can be done. This limit is not set so much
by the hardware / software capacities of the machine as by the available time. Going
through some of the applications that need 3-dimensional views, it is clear that the effects
are to be achieved within reasonable time. In an animation picture, if time delays prevent
a continuous stream of pictures being presented to the viewer, the n the whole idea behind
animation is lost. In case of simulation, the limitations are more stringent. The views are
to be presented to the viewer as they “happen” in the real world. If a plane is moving (or
it‟s motion is being simulated), then the movement of hills, buildings etc should be
presented at the same speed as it is experienced in a real case. Otherwise, the entire
meaning of simulation is lost.

The aim of this discussion is to highlight the fact that the methods of presentation
depend not only on how good is one scheme than the other, but also on how fast can one
scheme gets executed than the other. With the rapid changes in hardware technologies,
some of the schemes that were unattractive previously have become useful now and the
process will continue in future also.

83

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Now a look at some of the techniques.

1. Parallel projections : Those familiar with the concepts of engineering drawing will
recall that any 3-dimensional object can be represented by it‟s projections on parallel
planes. They constitute the front view, top view ( and some times the side view). This is
the simplest of the available techniques and can be done quite rapidly and also with
reasonable accuracy. But the views will be useful only to trained engineers and arc hitects
whereas a common viewer may not be able to make much out of it. For example if a
motor car is represented by what it looks like from the front, from the side and from the
top, a trained engineer or mechanic can immediately visualize it‟s form, inc luding the
various dimensions. But a common man can not make any thing out of it. Thus, this
method may be useful in applications like CAD, but is useless as far as animation or
simulation is concerned.

2. Perspective projection: This is the „common man‟s‟ technique. When we see a

number of objects or even a large object, parts that are nearer to the eye appear larger
than those that are for away. Thus a match box can obscure a building which is far away.
This is the way all humans see and understand things in real life. Thus, the scheme
provides a very realistic depth information and is best suited for animation and simulation
applications. But the draw back is that even though the method provides a feel of depth,
it seldom provides the actual information about the depth. (The case of a match box
obscuring the building clarifies the situation). It also is fairly computation intensive.

3. Intensity cues: One depth cue that is not computationally intensive is the concept of
intensity cues. As an object moves further from the viewer, it‟s intensity decreases.
Further, if it is made up of wide lines, the width of the lines decrease with increasing
distance.

4. Stereoscope effect : The reason why we see depth is because of the stereoscopic
effect of the eyes. We get two views of the same object by the two eyes and when these
are superimposed, we get the idea about the depth. (In fact a clear idea about the depth

84

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
coordinates cannot be got if only one eye is functional). The same can be used eve n in
the case of computer displays. How exactly can we show two images differs. Either two
different screens showing slightly displayed images of the same object can be shown or
the same screen can be used to alternate the two views at more than 20 times per second.
The method of polarized glasses is of a recent origin.

5. Kinetic depth effect: It is common experience that while in motion, objects that are
far away appear to move much slower than those near by. The same can be used in the
reverse method to give an indication of depth, especially in motion pictures. The objects
that are supposed to be nearer to the viewer can be made to move faster than those that
are to be shown further away. The viewer automatically gets the feeling of difference in
depths of the various objects. This could be a very useful technique especially in
animation and simulation pictures.

6. Shading : Those who have done artistic pictures know that shading is a very powerful
method of shading depth. Depending on the direction of incident light and the depth of
the point under consideration, shades are generated. If they can be represented
graphically, excellent ideas about depth can be created in the viewer. Raster graphics,
which allow each pixel to be set to a large number of brightness values is ideally suited
for such shading operations.
We see some of these concepts in details in later blocks.

Block Summary

In this introductory block, we have seen the need for converting the 3-
dimensional images to a 2-dimensional screen and yet give the viewer an idea of the third
dimension. We have also seen several techniques that are normally used to convey the
concept of depth to the viewer. The actual choice, however, depends on the applicability
as well as the hardware / software constraints on the system.

85

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Review questions

1. Name the method of sharing fast moving sequence of pictures.

2. State two reasons why simulation is resorted to?
3. What is the need for 3-dimentional representation of pictures ?
4. Name the type of projections normally used in engineering drawings.
5. Which projection gives the most realistic view of the object?
6. What is stereoscope technique?
7. How can one produce the stereoscope effect with a computer display?
8. What is kinetic depth effect?

Ans wers :
1. Animation.
2. Certain experiments may be too costly, certain other experiments need lot of changes
to be made, which is easier to incorporate on a computer.
3. Most of the objects we see in real life are 3-dimentional. Also in applications like
animation or simulation, where realism is of prime importance, not able to give a concept
of depth would make the whole concept useless.
4. Parallel Projection.
5. Perspective Projection.
6. The technique of showing two different pictures which are slightly displaced from
each other, so that the user gets the idea of a third dimension is called the stereoscope
technique.
7. Either by using two screen displaced slightly from each other or by using a single
screen to produce both the views, one after the other at speeds greater than 20 times per
second.
8. In moving objects, the following points move slowly compared to the nearby points.
If a similar technique is used in moving pictures, the viewer gets a cue about the depth of
the object.

86

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
BLOCK – II
Solid Area Scan Conversion
Block Introduction
In this block, we learn about the concept of scan conversion of polygons. We talk
about polygons, since any object of any random shape can be though of as a polygon – a
figure bounded by a number of sides. Thus if we are able to do certain operations on the
polygons, they can be extended to all other bodies.
So for, we have seen the line drawing algorithms. But if only a figure bounded by
a number of sides is given, we do not know complex when a large number of polygons
are there in the screen. We do not know whether the objects behind the present object is
visible or not. So, we would like to make a distinction between objects that are inside the
polygon and those that are outside and display them differently. The concept of
identifying such pixels is called the “scan conversion”, since we convert the pixels along
one scan line at a time.
We make use of the property of coherence- i.e. pixels that are in the same
neighborhood share similar properties. Using this, we introduce you to the YX
algorithm, which makes use of the intersections of polygons with the scan lines and the
concept of coherence to suggest an efficient scan conversion methodology.

Contents :

1. Solid Area Scan Conversion

2. Scan Conversion of Polygons
3. Algorithm Singularity
4. Block Summary
5. Review Question and Answers

87

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
SOLID AREA SCAN CONVERSION

The main reason for the rapid increase in popularity of raster scan displays is their
ability to display “solid” images. They are useful in representative, thickness, depth, or
objects line up one behind another. Needless to say, the ability to display the third
dimension is of prime importance in realistic display of objects, especially in video
games and animation.

Generating a display of a solid object means one should be able to

i) find out pixels that lie within the solid area and find out those that lie outside the
solid area. This concept is called the mask of the area. One simple way of
representative such pixels is to use a 1 to indicate pixels that lie inside the area
and use a 0 to indicate pixels outside. The bit is called the “mask”
ii) To determine the shading rule. The shading rule deals with the pixel intensity of
each pixel within the solid area. To give a realistic image for the depth, it is
essential that the “shade” of each pixel be indicated separately, so as to give a
coherent idea of the concept of depth. Such a mechanism would give the effect of
shadows to pictures so that pixels that lie nearer to the observer would caste a
shadow on those that are far away. A variable shading technique is of prime
importance in presenting realistic 3-dimensional pictures.
iii) To determine the priority . When one speaks of 3-dimensions and a number of
objects, the understanding is that some of the objects that are nearer are likely to
cover the objects that are far away. Since each pixel can represent only one
object, the pixel should become a part of the object that is nearest to the observer
i.e. a priority is assigned to each object and if a pixel forms part of more than one
object, then it will represent the object with the highest priority amongst them.

Out of these concepts, the problem of identifying those pixels that form a part of
the object from those that do not is called “scan conversion” In this block, we see
a few algorithms for scan conversion. In the subsequent blocks, we see more
about the other aspects.

88

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Scan conversion of polygons

The simplest algorithm of scan conversion can do something like this

i) Display the boundary of the solid object
ii) For each pixel on the screen, try to findout whether it lies inside the
boundary or on the boundary or outside it. Suitably arrange the mask of
each.

Though this method is simple and reliable, it needs enormous amounts of

computations to achieve the purpose. Obviously more efficient methods for scan
conversion are needed. One may note that the trade off involved is not just the time
involved, but such inordinate delays avoid a proper, real time modifications and display
of the picture. Hence, several algorithms have been devised so that certain inherent
properties of the pictures are utilized to reduce the computations. One such broad
technique is to consider figures as closed polygons and use certain properties of polygons
to find out which pixels should lie inside the picture and which are not one such property
is coherence.

Cohe rence: The performance of a scan conversion algorithm can be substantially

improved by taking advantage of the property of coherence. i.e. Given a pixel that is
inside a polygon, it‟s immediately adjacent pixels are most likely to be also inside the
polygon. Similarity if a pixel is outside a polygon, most of it‟s adjacent ones also will be
most probably outside it. A corollary is that the coherence property changes only at the
boundaries. i.e. we will have to check the status of the pixels only at the boundaries and
immediately adjacent to it, to find out whether the pixel lies inside or outside. The
property of coherence can be applied to all it‟s neighboring pixels and hence their status
need not be checked individually. Consider the following example. Given a polygon, it
is to be scan converted.

89

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

a1 a2
a
b
c

Suppose we want to identify all those pixels that lie inside the polygon and those that lie
outside. This can be done in stages, scan line by scan line. Consider the scan line a.
This is made up of a number of pixels. Beginning with left most point of the scan line,
compute the intersections of the edges of the polygon with the particular scan line. In
this case these are two intersections (91 & a2). Starting at the left most pixels, all pixels
lie outside the polygon upto the first intersection. From then on all pixels lie inside the
polygon until the next intersection. Then afterwards, all pixels lie outside. Now consider
a line b. It has more than two intersections with the polygon. In this case, the first
intersection indicates the beginning of the series of pixels inside the polygon, the next
intersection indicates that the following pixels will be inside the polygon and fourth
intersection concludes the series.

Now we write these observation as an algorithm. This algorithm is called the (yx)
Algorithm (We will see at the end of the algorithm, why this peculiar name).

(yx) Algortithm :

1. For every edge of the polygon, find out it‟s intersection with all the scanlines (This is a
fairly straight forward process, because beginning with one tip of the edge, every
incremental value of y gives the next scan line and hence a DDA type algorithm can be

90

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
written to compute all such intersections very fast and quite efficiency. However, we
leave this portion to the student). Build a list of all those (x,y) intersections.
2. Sort the list so that the intersections of each scan line are at one place. Then sort them
again with respect to the x coordinate values. (Understanding this concept is central to
the algorithm). To simplify the operations, in stage 1, we simply computed the
intersections of every edge with every (intersecting) scan line. This gives a fairly large
number of (unordered) points. Now sort these points w.r.t. their y-values, i.e. the scan
line values. Assuming that the first scan line has a y value of 1, we get the list of it‟s
intersections with every edge. Then of the scan line with value 2 and soon. At this stage,
looking at the previous example, we have the intersections of „a‟ listed first, then
intersection of „b‟ and then of „c‟ Now sort these intersections separately w.r.t. x points.
Then the points a1 and a2 appear in the order, similarly of b and c)

3. Remove the intersection points in pairs. The first of these points indicate the
beginning of the series of pixels that should lie inside the polygon and the second one
ends the series. (a1 and a2 in this case) . (In the case of the scan line b, we get two pairs of
intersections, since we have two sets of pixels inside the polygon for that scanline, while
an intermediate set lies outside). This information can be used to display the pictures.

Incidentally this algorithm is called the yx algorithm, since it sorts the elements
first w.r.t. y and then w.r.t. x. We leave it to the student to try and write a xy algorithm
and ensure that it does the job equally well.

Singularities: Note that we have not commented on the scan line c of the picture. The
peculiarity of that line is that the intersection lie exactly on the vertex of a polygon. In
such a case, it is very easy to see that the algorithm fails. This is because the intersection
of the scan line with the vertex not only defines the beginning of a series of pixels that lie
inside the polygon, but also the end of the series. Now how do we treat such
intersections?

91

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
One earlier solution suggested was never to have such intersections at all. i,.e.
instead of sharp vertices, have only blunt vertices. Then every scan line will have two
intersections instead of one. But obviously this solution is not a welcome one since it
distorts the picture altogether.

The other suggestion is to identify that such a “special” type of intersection has
occurred and treat it as two intersections at the same point. This solves the problem
elegantly, the only problem being that how do we identify? The answer is to keep track
of the direction of the polygon edges. It is easy to note that the polygon changes it‟s
“direction” at it‟s vertex. So, whenever an intersection is recorded, find out whether the
next point on the boundary of polygon lies o n a monotonically increasing / decreasing
sequence or is on a different direction altogether. Once this is done, if the direction is
different, then include two points instead of one into the list of intersections (With the
same coordinate values, of course). Now, we write a simple algorithm that treats such
singularity problems. This algorithm also takes care of the other imminent problem –
that of horizontal edges. A horizontal edge would intersect with every pixel of the scan
line and how to deal with such a situation wherein every pixel can be considered to be
inside the polygon is also dealt with here.

Algorithm Singularity :
1. A variable yprev is used to keep track of the previous intersection of the edge.
Whenever an intersection is found, not only is a new pair of (x,y) stored as in the yx
algorithm, but the y coordinate is stored to indicate the previous intersection by storing it
in yprev . Initially it‟s value is set to 0.

2. Go to the next edge of the polygon. If these are no more edges to be processed, exit.

3. Compute it‟s intersection with the scan lines. If it has no intersections at all (or a very
large no. of intersections, the way you look at it) it can be considered horizontal. Go to
step 2

92

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
4. Compute the difference dy=y2 -y1 , where y2 is the y coordinate of the begining vertex
of the edge and y1 the y coordinate of the ending vertex. If dy>o go to step5, else go to
step6.

5. If dy>0, the first intersection generated must have y= yprev .+1 compute all other
intersections of the edge. The y coordinate of the last intersection is stored in yprev . . Go
to step 2 to findout whether any edges are still there.

6. If dy<o, the first intersection generated will have y= yprev . itself generate all
intersections for the edge. The y coordinate of the last intersection is preserved in yprev .
= ylast -1. Go to step2.

Note that this algorithm does not generate intersection nor does it produce the
scan conversion. The scan conversion algorithm, which does the conversion will only
pass it‟s intersection values to the singularity algorithm to check for the specific cases.

The other aspect to be taken care of while displaying polygons is to decide on the
priority. In 3 dimensional graphics, it is obvious that two or more polygons tend to
overlap one another. In such cases, only the polygon that it is closest to the observer will
visible. This polygon obscures any more polygons behind it. But the problem is that the
front polygon may not cover the polygon behind it completely. That me ans the farther
polygon is visible in those places where it is not covered by the front polygon, but will
not be visible in those regions where the front polygon covers it. One solution to solve
this problem is to find the intersections of the polygons, display the front polygon
completely and display the back polygon(s) in these areas where the front polygon is not
covering it. But, if you consider cases wherein a large no. of polygons are covering one
another at different regions, this method becomes unwieldy.

A very ingenious method to solve this problem of assigning priorities to the

algorithms have been devised. This is called a “painters algorithm”. Imagine a painter
painting these polygons on his canvas. What does he do? He does not bother hims elf

93

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
about intersections or partially obscurities. He begins by painting the furthest polygon,
say in a particular color. This, obviously has the least priority in display i.e. it will be
displayed only when no other polygon is obscuring it. Then he begins painting the next
polygon in front of it. He simply goes about painting this second polygon, without
bothering about the previous polygon. This new polygon, let us say polygon 2, has a
higher priority than the polygon 1. i.e. when the two polygons appear together, polygon 2
will be visible completely and polygon 1 is visible only if polygon 2 is not obscuring it in
that region. Now, once the second polygon is painted, in a different color, it is simple to
analyze that the parts of the polygon 1 that are covered by polygon 2 automatically get
covered and becomes invisible. Similarly if a polygon 3 is painted, it gets the highest
priority in display.

Thus, an extremely simple concept emerges. Do not bother about any

mathematical formulations. Start from the farthest polygon and keep displaying them in
the order of increasing priorities. The priorities are automatically taken care of.

Expressed in technical terms the algorithm can be expressed as follows. Assign a

priority to each polygon, the lowest priority to the polygon that is farthest from the
viewer and the highest priority to the one that vs nearest. Sort them on the order of
priority. Scan covert each of the polygons and start displaying them in the increasing
order of priority. The higher order polygons automatically cover the lower order ones
and the priority concept is case of.

This algorithm can be called p-(yx) algorithm on the lines similar to yx algorithm.
In the yx algorithm we were first ordering on y then on x coordinates. Here, before that,
we order the polygons based on priorities. i.e. 3 stages of p, y and x sorting are involved.
Hence p(yx) algorithm.

This algorithm, however, has a very minor drawback. It is not visually appealing.
Since the algorithms appear in the order of priorities, from the least to the highest, the
most important of them appear only in the end. Also, it will be distracting to the user to

94

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
see the polygons appearing one after the other, one overwriting another. A better scheme
will be to make them appear in their final order, even if it is from one end to the other (or
top to bottom). A simple way to do this is to first sort the pixels in terms of their y
coordinates (scan line by scan line), then on their priorities and finally on their x
coordinates. Then the algorithm changes to a ypx algorithm.

The algorithm, in brief, appears as follows:

1. For each polygon, compute the intersections with every scan line. This yields a list of
(x,y,p) where x & y are the coordinates of the point of intersection and p is the priority of
the polygon.
2. Sort the list first by y, then sort w.r.t. p and finally w.r.t. x
3. Remove pairs of nodes from this sorted list and scan convert as before.

One difficulty of this algorithm is that it takes large amounts of computational

efforts for sorting, since a large number of points are involved. The only solution will be
to resort to efficient sorting algorithms.

Block Summary

In this block, you were introduced to the concept of scan conversion i.e. the
method of identifying those pixels that lie inside an object from those that lie outside
since every picture can be thought of as a polygon, the idea was to scan covert the
polygon w.r.t. the pixels. To do this efficiently and systematically the concept of pixel
coherence was introduced i.e.e every pixel that lies inside will most probably have it‟s
neighbors also inside and viceversa. Using this concept, a simple yx algorithm was
suggested. To take case of singularities, where a vertex of the edge intersection a
schanline, a singularity testing algorithm was suggested.

Finally to take care of multiple polygons standing one behind another, so that
one/more of them are obscured by other polygons, the painters algorithm or ypx
algorithm was introduced.

95

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Review questions

1. What is scan conversion

2. Why are we specific about polygons?
3. What is priority in the concept of a pixel?
4. What is coherence?
5. Why yx algorithm called so?
6. What is singularity? How are they taken care of in yx algorithm?
7. How is a singular point identified?

Ans wers:
1. The idea of identifying and converting pixels along a scan line that lie inside the
polygon so that they can be displayed differently.
2. Because once we are able to do certain operations on polygons, they can be exte nded
to others, since most of the regular and irregular boundaries can be thought of as
polygons.
3. In 3-dimensional views, when more than one object stands one behind another, the
same pixel on the screen represents more than one object. So the priority for the pixel as
to which object it should represent is important.
4. Pixels in the same neighborhood share similar properties – most often. If a pixel is
inside a polygon, most probably, it‟s neighbors also will be inside the same polygon.
Hence, the same set of operations need not be repeated on each of them.
5. Since it first sorts the elements with respect to y and then with respect to x.
6. When a vertex coincides with a scan line, it is a singular because the scan line entres
and leaves the polygon at the same place. They are counted as z intersections for the
algorithm.
7. In a singular point, an edge of the polygon changes it‟s direction.

96

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Block III

Three Dimensional Transformations

Block Introduction

In this block, we look into the basics of 3-D graphics, beginning with
transformations. In fact the ability to transform a 3-dimensional point, i.e. a point
represented by 3 Co-ordinates (x,y,z) is of immense importance not only for the various
operations on the picture, but also for the ability to display the 3-D picture in a 2-D
screen. We briefly see the various transformation operations – they are nearly similar to
the 2-D operations. We also see the concepts of clipping and windowing in 3-D.

Contents:
1. Three Dimensional transformation
2. Translations
3. Scaling
4. Rotation
5. Viewing Transformation
6. The Perspective
7. Algorithms
8. Three Dimensional Clipping
9. Perspective view of Cube
10. Block Summary
11. Review Question and Answers

97

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Three Dimensional Transformation :

Just as in the case of 2D, we represent the transformation operations as a series of

matrix operations. With this, we obtain the flexibility of sequencing a series of
operations one after the other to get the desired results on one hand and also the ability to
undo the operations, by resorting to the reverse sequence. Since in the 2-dimensional
case we were representing a point (x,y) as a tuple [x y 1], in the 3-dimensional case, we
represent a point (x,y,z) as a [x y z 1]. The dimensions of the matrices grow from 3 x 3 to
4 x 4.

Translations:
Without repeating the earlier methods, we simply write

[x1 y1 z1 1] = [x y z 1] 1 0 0 0
0 1 0 0
0 0 1 0
Tx Ty Tz 1

where the point [ x y z 1 ] gets transformed to [ x1 y1 z1 1] after translating by Tx, Ty and

Tz along the x,y,z directions respectively.

Scaling:
A given point [x y z 1] gets transformed to [x1 y1 z1 1] after getting scaled by factors
Sx, Sy and Sz in the three dimensions to

[x1 y1 z1 1] = [x y z 1] Sx 0 0 0
0 Sy 0 0
0 0 Sz 0
0 0 0 1

Rotation:

Rotation in 3-dimensions is a more complex affair. (In fact, even in 2

dimensions, rotation was more involved than scaling or translation because the concept of
point of rotation). This is because, the rotation takes place about an axis. The same

98

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
point, given the same amount of rotation, gets transformed to different points depending
on which axis it was rotated.
The simplest of the cases is to rotate the po int about an axis that passes through
the origin, and coincides with one of the axes x, y or z. The next complication arises
when the axis passes through the origin, but does not coincide with any of the axes. The
most general case would be, of course, when an arbitrary axis that does not pass through
the origin becomes the axis of rotation.
Let us begin with simplest cases: The understanding is that a clockwise rotation,
when viewed at the origin, standing on the axis is taken as positive and the other direction
is negative. If this description looks too complicated, look at the following figures. In
each case, we write down the transformation for the rotation through a positive angle of
+ .
Z

O X
Rotation Direct ion of view of orig in

[x1 y 1 z1 1] = [x y z 1] cos - Sin 0 1

sin cos 0 0
0 0 1 0
0 0 0 1

Transformation Matrix

Z
Direction of view of
Origin
Y

O X
99

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

[x1 y 1 z1 1] = [x y z 1] cos 0 - Sin 0

0 1 0 0
-sin 0 cos 0
0 0 0 1

Transformation Matrix

Direction of view of origin

O X

[x1 y 1 z1 1] = [x y z 1] 1 0 0 0
0 cos - Sin 0
0 sin cos 0
0 0 0 1

Transformation Matrix

Now the other cases of rotation can be taken to be concatenations of the various
operations.
For example to rotate a point about an axis that passes through the origin, but does
not coincide with any of the axes, as in the following figure
Z

O X

100

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Suppose the axis passes through the origin, but does not coincide with any of the
axes, then the axis itself is to be first aligned to one of the axes before doing the
transformations. The sequence of events appear as follows.
(a) Rotate the axis through the desired angle to make it coincide with one of the axes.
(Depending on with respect to which axis, it's angle of deviation is available).
(b) Rotate the point (desired to be rotated )about this axis.
(c) Rotate the axis back to it's original angle of deviation.

In cases where the axis is an arbitrary axis passing through some points, but not the
origin, the sequence lenthans
(a) Shift the point through which the axis points to the origin.
(b) Rotate the axis through an angle necessary to coincide it with one of the primary axes.
(c) Rotate the point to be rotated about this axis.
(d) Rotate the axis back to it's original inclination.
(e) Shift the point from the origin to it's original point.

(Similar operations have been illustrated n the case of 2-dimensional operations in the
earlier block. The student is encouraged to attempt to write transformations for above
cases on similar lines).

(It is also to be noted that reverse operations can be done fairly easily using matrices.
For example if a rotation is made through an angle , to undo the operation, one need not
go to the extent of finding the inverse of the original transformation matrix, but by simply
multiplying the resultant with one more matrix where cos( ) and sin ( ) are replaced by
cos (- ) and sin(- ). In the case of scaling -Sx and -Sy perform the inverse operations for
Sx and Sy).

Vie wing Transformations

Before displaying the 3-D picture one more set of "viewing transformations" is to
be done. This is to ensure that the viewer would get the depth perspective that has been

101

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
displayed on the screen. This is done by transforming the image to another coordinate
system with axes xe, ye and ze, the origin being the position of the eye and ze being the
axis passing from the eye perpendicularly to the screen.

If this transformation is called V, then it is not enough if we simply display the

completed picture as it is, but every point is to be transformed to the eye coordinate
system.

Calling the original picture coordinate systems as the world system, if a point in it
is represented by [ xw yw zw 1] then it should be transformed to the eye coordinate system
[xe ye ze 1] using the following transformation

[xe ye ze 1] = [ xw yw zw 1] V

V is a series of matrix transformations that can be got by including several

translations and rotations that are determined by viewing parameters.

The perspective Transformation

A perspective display can be generated by simply projecting every point of the

object on to the plane of the screen. This section teaches you to get the coordinates (xs -
ys) in the screen coordinates with respect to the eye coordinates (xe, ye, ze).

102

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Consider the above figure which indicates the basics of the perspective projection. O is
the point behind the screen which is called the "Perspective Point", the point. The point P
measured in eye coordinate is available at P(xe,ye,ze). The effort is to find the coordinates
of the same point P(xs,ys) on the screen (also called screen coordinates) so that the
perspective effect is established. D is the distance of the convergence point (where ze =
0) behind screen and S is half width of the screen.

The triangles OQ'P' and OQP are similar.

Hence ys / D = ye / ze
Similarly it can be shown that
xs / D = xe /ze
The numbers xs and ys can be converted to fractions by dividing them by the screen size.
This operation not only allows as to numbers which are fractions, but it also makes the
numbers dimesionless (we are dividing a dimension with another dimension).

Xs / D = Xe /sze and Ys / D = Ye / S ze
Or Xs = D xe / Sze and ys = D ye / Sze
Alternatively they can be converted to the screen coordinates by including a specification
of the location of view port in which the image is displayed.
Xs = (Dxe / Sze ) Vsx + Vcx and ys = (Dye /Sze ) V sy + Vcy

[This can be derived as follows:

The view port is at the centre (Vcx, Vcy) and is 2 Vsx units wide and 2 Vsy unit high

103

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

(Vcx,Vcy)

Vsx Vsy

View Port

Hence a value xs which is given in the window coordinates as (xs = Dxe / Sze) is
scaled by a factor Vsx and is shifted by a value Vcx.
Similarly the coordinate xy given by a value Dye / Sze is scaled by a factor Vsy
and is shifted by a value Vcy. You can remember that we used a similar methodology to
transform from windows to view port in an earlier block. ]

Thus, in order to convert a picture it's perspective equivalent, we should convert

every point (xe,ye) using these formulae.
However, this involves a series difficulty. As we can see, divisions are involved
in both the conversions. I.e. to convert a single point to it's perspective equivalent, we
have a few multiplication's and additions, but more worryingly two divisions as well.
Computers are most efficient for additions and multiplications but are thoroughly
inefficient with division. Fortunately a picture can be converted into a perspective
equivalent by transforming only the corners of the picture.

Three dimension clipping

The direct application of the perspective conversion may end up mapping the
object to size of the window, also points beyond the viewport may a lso get mapped. To
circumvent these problems, the object generated needs to be clipped against a viewing
pyramid. The concept is similar to the 2-dimensional case.

104

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

CLIPPING
Every point needs to be checked as to whether it lies within the visible area of the
pyramid by comparing the values of (D/S) xe and (D/s) ye to the end values of the visible
area
i.e. -Ze (D/S) xe +Ze and -Ze (D/s) ye +Ze.
This will exclude all points beyand the view point (ze 0) and all points that go beyand
the visible pyramid.

Note that this creates on problem. We indicated before that an object can be
transformed to it's perspective by simply mapping it's endpoints. But, if these points go
beyond the visible pyramid, then they cannot be displayed. But this does not mean the
entire object cannot be rejected. The intersection of the visible pyramid with the profile
of the object needs to be computed. This clipping has to work on a 3-dimensional
perspective.
A three dimensional clipping algorithm can be derived by extending the 2-D
scheme.
The algorithm determines whether the end point of the line lies in the visible
pyramid by assigning a 4 bit code to it.

First bit is 1: if the point is to the left the pyramid, else it will be zero, similarly,
Second bit : If the point is to the right of the pyramid
Third bit: If the point is below the pyramid

105

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Fourth bit : If it is above the pyramid.
As earlier, if the codes for both the end points is 0000, then the line is trivially accepted.
If the logical AND of the codes is not zero, both end points lie on the invisible side of one
of the planes and can be trivially rejected. Otherwise the line crosses the side of the
pyramid at one/more points. The point of intersection can be computed in the
parametric form as
( (1- t) [x1 y1 z1] + t [xz yz Zz]) =0

1
Where different values of and have different values for different planes. For
example if =1 , = 0, then it indicates the plane x=z. By substituting the various
values of and one can find the point of intersection with different planes.

These Intersections then replace the ends of the line in the viewing pyramid.

Perspective view of a cube.

We clarify the above discussions with an example, getting the perspective view of a cube.
Consider a cube centered at the origin of the world coordinate system, defined by the
following points and lines:
Lines Points
X Y Z
AB, BC A -1 1 -1
CD, DA B 1 1 -1
EF, FG C 1 -1 -1
GH, HE D -1 -1 -1
AE, BF E -1 1 1
CG, DH F 1 1 1
G 1 -1 1
H -1 -1 1

106

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
We shall observe this cube from a point (6, 8, 7.5) with the viewing axis ze pointed
directly at the origin of the world coordinate system. There is still one degree of freedom
left, namely an arbitrary rotation about the ze axis: we shall assume that the xe axis lies in
the z = 7.5 plane.
The viewing transformation is established by a sequence of changes of coordinate
systems. Recall that a transformation that moves a coordinate system is the inverse of the
corresponding transformation that moves points.
1. The coordinate system is translated to (6,8,7.5), the point in the original coordinate
systems becomes the origin:

T1 = 1 0 0 0
0 1 0 0
0 0 1 0
-6 -8 -7.5 1

2. Rotate the coordinate system about the x' axis by -90o . Because we require the inverse
transformation, we substitute = 90 o.
T2 = 1 0 0 0
0 0 -1 0
0 1 0 0
0 0 0 1

3. Rotate about the y' axis by an angle so that the point (0, 0, 7.5) will lie on the z' axis.
We have cos - = cos = -8/10 and sin - = -sin = 6/10:
T3 = -0.8 0 0.6 0
0 1 0 0
-0.6 0 -0.8 0
0 0 0 1

4. Rotate about the x' axis by an angle so that the origin of the original coordinate
system will lie on the z' axis, we have cos - = cos = 10/12.5 and sin - = -sin =-
7.5/12.5:
T4 = 1 0 0 0
0 0.8 0.6 0
0 -0.6 -0.8 0
0 0 0 1

107

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

5. Finally reverse the sense of the z' axis in order to create a left handed coorinate system
that conforms to the conversions of the eye coordinate system, A scaling matrix is used.
T4 = 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

This completes the five primitive transformations needed to establish the viewing
transformation V = T1 T2 T3 T4 T5

Suppose that we wish to fill a 30 by 30 centimeter display screen, designed to be viewed

from 60 centimeters away, and that the coordinate system of the screen runds from 0 to
1023. Thus D = 60, S = 15, and Vsx = Vcs = Vsy =Vcy = 1023/2
The transformation is therefore
N= 4 0 0 0
0 4 0 0
0 0 1 0
0 0 0 1

xs = 511.5 (xc / zc) + 511.5 ys = 511.5 (yc/zc) + 511.5

All the details of the transformations have now been specified. Each vertex of the cube is
transformed by the matrix VN clipped and converted to screen coordinates using the
above equation

VN = T1 T2 T3 T4 T5 N =
-3.2 -1.44 -0.48 0
2.4 -1.92 -0.64 0
0 3.2 -0.6 0
0 0 12.5 1

108

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
We can now apply this transformation to the eight vertices of the cube:
Xc yc zc
A 5.6 -3.68 12.94
B -0.8 -6.56 11.98
C -5.6 -2.72 13.26
D 0.8 0.16 14.22
E 5.6 2.72 11.74
F -0.8 -0.16 10.78
G -5.6 3.68 12.06
H 0.8 6.56 13.02

Although the clipping routine must be applied to each line in the cube, it is apparent from
the table that all of the vertices lie within the viewing pyramid, and the clipping algorithm
will trivially accept each line.

Block Summary

In this block, you were introduced to the basics of 3-dimensional transformations.

The need for various transformations and also the various formulae for translation,
rotation and scaling were introduced. It may be noted that these are extensions of similar
transformations in the z- dimensional case. However, rotation about an arbitrary point
involved a combination of a few transformations.
You were also introduced to the concept of perspective transformations, the wa y
human eyes see the objects and how to create a similar effect as a computer screen. Once
these transformations are done, often areas of the picture lie outside the “visible”
pyramid. To take care of those cases, the concept of 3-dimensional clipping was also
introduced. Again the concepts involved were extensions of 2-D case.
Since a practical example to illustrate these cases would be of immense use, you
were introduced to the example of a given cube being transformed to it‟s perspective
view.

109

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Questions

1. What is the order of matrices in 3-dimensional representation of pictures ?

2. What are the sequence of steps involved in rotating a given 3-D point about an axis
passing through the origin, but not coinciding with any of the principal axes?
3. What is the name given to the method of projecting drawings in a way similar to that
seen by the eye?
4. Write down the formulae for transforming the eye coordinates to screen coordinates.
5. Explain the concept of 4 bit assignment for clipping algorithm.

Ans wers:
1. 4X4
2.
a) Rotate the axis to make it coincide with x,y or z axis
b) Rotate the point suitably over this axis.
c) Bring the axis back to it‟s original position by the sequence of reverse
transformations.
3. Perspective projection.
4. Xs = (DXe/SZe) Vsx + Vcx
And Ys = (DYe / SZe) Vsy + Vcy
Where Xs and Ys are screen coordinates,
Xe and Ye are the eye coordinates
S is half screen size
Vsx and Vsy are the dimensions of the viewport
Vcx and Vcy are the shift of the viewport with respect to the screen coordinates.

5. First bit is set to 1 if the point is to the left of viewing pyramid

Second bit is set to 1 if the point is to the right of the viewing pyramid
Third bit is set to 1 if the point is below viewing pyramid
Fourth bit is set to 1 if the point is above the viewing pyramid

110

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Block IV

Hidden Surface removal

Block Introduction

In this block, you will be introduced to one of the most interesting and involved
concept of computer graphics – the concept of hidden surface elimination. When two or
more object are represented one behind the other – it is quite clear that some of them
either partially or fully obscure the other object in such cases the hidden parts of the
objects are to be removed.

Several algorithms for the same are introduced. Almost all of them work on the
simple concept of sorting the polygons in the order of their distance, the nearest ones
being represented in full, the farther ones in part since, in raster graphics, a given pixel
can represent more than one object (each with same x,y) it will r epresent that object that
is nearest to the screen amongst these objects. Though this concept is straight forward
and accurate, it suffers from the difficulty that it is computationally intensive. Hence,
several efficient algorithms, which perform the sa me job with more efficiency are
introduced. Most of them make use of some sort of coherence concept – i.e. pixels in the
neighborhood of a pixel share the properties of a pixel. i.e. If a pixel forms a part of an
object, the neighboring pixel also, most probably, form the part of the same object. You
will also be introduced to certain specific instances, wherein these concept may not yield
satisfactory results.
Contents:
1. Need for hidden surface removal
2. The Depth - Buffer Algorithm
3. Properties that help in reducing efforts
4. Scan Line coherence algorithm
5. Span - Coherence algorithm
6. Warnock's Algorithm
7. Priority Algorithms
8. Block Summary
9. Review Question and Answers

111

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
Need for hidden surface re moval

This has been considered as one of the most challenging jobs of computer
graphics. Once we start talking of solid objects in 3 dimensional spaces, it is implied that
some of the objects that are nearer to the viewer tend to partly or wholly cover other
objects. In fact, even if there is only one object, some of it‟s faces are unseen (the back
faces) and some are partially seen (the side faces). The ability to identify the faces and
surfaces that are to be covered and the extent of coverage in the case of partially covered
surfaces in real time is not only computationally intensive, but also analytically daunting.
When only wireframe types of drawings are being displayed, the task gets somewhat
simplified to that of “hidden line removal” – identifying those lines that should not be
shown. However, when solid objects are being considered, the task becomes more
complex because entire surfaces need to be identified for removal.

A large number of algorithms are available for the job –though no single
algorithm can be though to be all encompassing capable of being efficient in all possible
conditions. However almost all of them share some common feature. The first one is
that at some point in the algorithm, they tend to sort the objects in the order of their Z-
distance from the viewer and try to eliminate the farthest ones. But the sorting tends to
be a difficult task at least in some cases, since often an object may not be identified with
a unique distance – Z. when several part of the object have different Z coordinates,
simple, direct sorting methods may become inadequate.

The other common feature with these algorithms in the use of coherence. As we
have seen in other contexts, the coherence (or similarity with respect to a property)
between neighboring pixels is used to reduce the number of computations effectively.

The behaviour of the algorithm also depends on which type of images one is
talking of. In the case of line drawing algorithms, the problem is solved using the various
properties of lines, whereas in the case of raster images, the algorithms t end to look like
extensions of 2-dimensional scan conversion algorithms.

The algorithms can also work either with respect to the object space or the image
space. One should clearly be able to draw the distinguishing line between them. The
object space in the space occupied by the pictures created by the algorithms. However,
112

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
before these pictures can be displayed, they undergo various operations – like clipping,
windowing, perspective transformations etc. This final set of pictures – ready for display
on the screen is called the image space. The object space algorithms tend to calculate the
values with as a precision as feasible since often these calculations form the basis for the
next set of calculations, whereas the image space algorithms calculate with precision that
is in line with the precision available with the display devices. This is because any higher
precision, achieved with great efforts, will become useless since the display devices
cannot anyway handle such precisions. Further, the computational efforts in the case of
objects – since every object tend to rapidly increase with the no. of objects – since every
object will have to be tested with other objects, where as in the image apace
computations, the increase is much slower, since one tends to look at the number of
pixels, irrespective of the no. of objects in the scene. The number of pixels in a given
resolution of display device is a constant.

Having noted some of the expected features of the algorithms, we now look into the
working of some of the algorithms.

The Depth – Buffer algorithm.

The concept of this algorithm is extremely simple and straight forward. Given a given
resolution of the screen, every pixel on the screen can represent a point on one (and only
one) object (or it may be set to the back ground if it does not form a part of any object).
I.e. irrespective of the number of objects in line with the pixel, it should represent the
object nearest to the viewer. The algorithm aims at deciding for every pixel the object
whose features it should represent. The depth-buffer algorithm used two arrays, depth
and intensity value. The size of the arrays equals the number of pixels. As can be
expected, the corresponding elements of the array stere the depth and intensity
represented by each of the pixels.

113

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
The algorithm itself proceeds like this

Algorithm Depth Buffer:

a. For every pixel, set it‟s depth and intensity pixels to the back ground value ie. At the
end of the algorithm, if the pixel does not become a part of any of the objects it
represents the background value.

b. For each polygon on the scene, find out the pixels that lie within this polygon (which
is nothing but the set of pixels that are chosen if this polygon is to be displayed
completely).

For each of the pixels

i) Calculate the depth Z of the polygon at that point (note that a polygon, which
is inclined to the plane of the screen will have different depths at different
points)

ii) If this Z is less than the previously stored value of depth in this pixels, it
means the new polygon is closer than the earlier polygon which the pixel was
representing and hence the new value of Z should be stored in it. (i.e from
now on it represents the new polygon). The corresponding intensity is stored
in intensity vector.

If the new Z is greater than the previously stored vale, the new polygon is at a
farther distance than the earlier one and no changes need be made. The
polygon continues to represents the previous polygon.

One may note that at the end of the processing of all the polygons, every pixel, will have
the intensity value of the object which it should display in its intensity location and this
can be displayed.

This simple algorithm, as can be expected, works on the image space. The scene should
have properly projected and clipped before the algorithm is used.

The basic limitation of the algorithm is it‟s computational intensiveness. On a 1024 X

1024 screen it will have to evaluate the status of each of these pixels in a limiting case.

114

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
In it‟s present form, it does not use any of the coherence or other geometric properties to
reduce the computational efforts.

To reduce the storage, some times the screen is divided into smaller regions like say 50 X
50 or 100 X 100 pixels, computations made for each of this religions, displayed on the
screen and then the next region is undertaken. However this can be both advantageous
and disadvantageous. It is obvious that such a division of screen would need each of the
polygons to be processed for each of the regions – thereby increasing the computational
efforts. This is disadvantage. But when smaller regions are being considered, it is
possible to make use of various coherence tests, thereby reducing the number of pixels to
be handled explicitly.

Properties that help in re ducing the efforts.

Several features can be made use of to identify the polygons that are totally/partially
covered, so that the actual effort of elimination of hidden surfaces can be reduced. A few
popularly used tests are as follows.

i) Use of geometric properties: The depth buffer algorithm reduces the objects to a
series of polygons and tests them for visibility. The polygon, in geometric terms
is a surface, which is represented by the equation ax + by + cz +d =0 for any point
(x,y,z) that lies on the surface (or plane in geometric terminology). A point that
does not satisfy the equation lies outside the plane. A point that gives a negative
value for the equation lies on the backface of the plane (since x,y coordinates
cannot be negative, it implied z becomes negative). Such backfaces like the back
of a cube or a pyramid or some similar shape, can be totally removed from the
calculations then reducing the efforts considerably.

ii) Overlap tests: Common sense gives us one simple idea. An object can obscure
another only if (a) one of them is at a farther distance than another – obviously
two objects standing side by side cannot obscure each other

115

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
iii) Even if they are at unequal distances, they can obscure only if either their x or y
coordinates overlap. For example the two polygons in the given figure cannot
obscure each other irrespective of how far or near is each of them than the other.

P2

P1

The minimax tests guarantee just this. If the minimum x coordinate of one polygon is
larger than the maximum x coordinate of another (P2 and P1 respectively of the figure)
and similarly the max is coordinate of one is less than the minimum is coord inate of
another (P1 and P2 respectively). The two figures cannot overlap no matter what their z
coordinates are. This test allows us to trivially avoid testing a few pairs of polygons for
obscuring each other.

However it should be noted that failure to pass the minimax test does not always imply
that they obscure consider the following case

P1 P2

Here though P1 and P2 coordinates overlap, they still do not obscure each other. Test ing
such instances need more elaborate computations.

116

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Scan Line Coherence Algorithms

Scan line algorithms solve the hidden surface problem, one scanline at a time. i.e.
They traverse the picture the picture space from top to bottom, one line at a time
removing all the hidden surface along that scan line.

The simplest of them can be the depth buffer algorithm itself. Since the algorithm
has to consider every pixel, it can take care of pixels along each scan line at a time and
then go to the next line and so on.

Scan line coherence algorithm:

For each scan line perform the following steps.
a. For every pixel on a scan line, set depth value to 1.0 and intensity to the back ground
value.
b. For each polygon in the view scene, find all pixels of the scan line under
consideration that lie within the polygon. For each of them
i. Find the depth z of the polygon at the point.
ii. If Z < depth [x], set depth[x] to z and the intensity to the intensity of the
polygon.
c. Once all polygons have been taken care of, the pixels co ntain the intensity values that
are to be displayed. This algorithm when used in conjunction with Y-X scan
conversion forms the simplest of scan line coherence algorithms.

Span – Coherence algorithm

Another property of coherence that can be made use of in scan conversion is the
one-dimensional form of area coherence, called span coherence. If a pixel is inside a
polygon, it‟s neighbours also lie inside the polygon. This holds good upto a “Span” once
the Span is detected, all pixels within the span can be set to the intensity value of the

117

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
polygon and the next comparison can take place at the end of the span. This reduces the
computation by a very large amount, especially if the no. of polygons are limited.
The concept of spans can be considered in a simplistic manner by the following
example.
In the 3-dimensional space, each scan line produces a plane. i.e. each scan line is
for a particular value of y. A plane with this value of y as a constant over different values
of x and z form a plane.
Plane defined by the scan line

Scan line

If one travels along this scan line, the plane intersects one/more polygons at
different points. If these points of intersection are noted and are sorted in the increasing
order of x, we get a sort of xz algorithm which gives the list of intersections with
different polygons.
Taking them in pairs, just as in the XY algorithm, one can convert the entire plane
into several spans.
i. Spans that do not lie within any polygon, the pixels can be set to the background
intensity.
ii. Spans that lie within a single polygon. All of them can be set to the intensity of
the polygon.
iii. Spans that are intersected by 2 or more polygons. In such spans, the pixel values
can be set to the intensity of the nearest polygon.

The algorithm implements the details in the following order.

i. A single active edge list, sorted by x, contains the intersection (and the intensity
values) of all polygons that intersect the scan line.
ii. During the actual scan conversion, the process starts from the left to the right.
Initially, the pixels are at the back ground intensity. The first node on the list

118

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
indicates the first polygon being activated i.e. from no on the pixels will be inside
the polygon. The next node can be either an entry into a new polygon or the exit
from a polygon. (The concept of entry or exit into or out of polygons is stored
into the nodes by setting a particular bit to 1 or 0 for entry or exit at the time of
creating the list – while taking not of the intersections.
iii. Whenever an entry into a polygon occurs, all polygons that have been currently
activated are checked to find the one that is nearest to the viewer and the pixels
from then onwards are set to that polygons intensity. While exiting from a
polygon, again that polygon is deactivated and the pixel intensity value is
recalculated.
This basic algorithm can make use of coherence in many other ways for farther
improvisation of efficiency. For example, the intersections need not be calculated
for all the scan lines (or scan planes). If a polygon cuts a scan plane at (x,z) say,
then the intersection of the same polygon in the next immediate scan plane will be
either at (x,z) itself or at one pixel distance from (x, z) in any direction. This can
be used to avoid actual calculation of the intersection and in fact, if the direction
of the polygon edge is known, it‟s intersection with next scan plane can be found
at accurately by looking at the precise pixel indicated b y the direction.

Area – Coherence Algorithms

The idea of coherence can be extended in both directions. I.e. just as a pixel will have,
most probably, the intensity of it‟s left or right neighbor, the coherence can be extended
to the other direction as well. This bidirectional or area coherence was made use of by
Warnock in his algorithm, known by his name.

Warnock’s Algorithm
This is one of the class of “area” algorithms. It tries to solve the hidden surface
problem recursively. The algorithm proceeds on the following lines.

119

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
i. Try to solve the problem by taking the entire screen as one window. If no
polygons overlap either in x or y or even if they do, overlap so that they do not
obscure, then return the screen.
ii. If the problem is not easily solvable in step (i) the algorithm divides the screen
into 4 equal parts and tries to apply step (i) each of them. If it is not solvable,
again divides into smaller windows and so on.
iii. The recursive process continues till each window is trivially solvable or one
endsup with single pixels.

We have still not described how the actual “solution” is done. To do this, in any
window, the algorithm classifies the polygons into three groups
i) Disjoint Polygons: Polygons that do not overlap in the window and hence can be
trivially passed.
ii) A bigger and a smaller polygon overlapping so that the smaller one will be
completely blocked by the bigger one (if the Z of the larger polygon is smaller
than Z of the smaller one).
iii) Intersector polygons: Polygons that partly obscure each other.

Polygons that fall into category (i) and (ii) are removed at each level. If the
remaining polygons can be easily solved, the recursive process stops at that level, else the
process continues (with the polygons of category (i) and (ii) removed).

Since at each recursive level a few polygons are removed, as the windows become
smaller and smaller with the advance of recursion, the list of polygons falling into them
also reduces and hopefully the problem of hidden surfaces gets solved trivially.

One main draw back of algorithm is that the windows get divided into smaller and
smaller rectangles. In many cases it would be efficient if one can divide the window
roughly in the shape of the polygons themselves. Such an algorithm, developed by
Wieler and Atherton, was found more efficient, though more complex in terms of larger
complexities of recursive divisions and clippings.

120

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Priority Algorithms
In contrast to the scan line and area coherence algorithms, priority algorithms try
to discover the depth relations first and then perform the xy calculations only after the
visibility has been established. They are similar to the priority algorithms of scan
conversion.
Remember the painters algorithm? A painter drawing a painting on a canvas
simply keeps painting them beginning from the farthest object. As and when a nearer
object gets painted, the hidden areas of the farther objects automatically get covered by
the new object.
Similarly if one begins scan converting the polygons beginning with the farthest
polygon, the hidden lines and hidden surfaces automatically get eliminated. However, if
the polygons in the priority list overlap in depth, the things become more complex. Look
at the following figure:
Z
ZA
ZB B

Simply sorting them on the basis of Z max would make computations complicated
because for certain scan lines. A is nearer than B but for certain others B is nearer than
A. Hence the priority list, prepared based only on the depths will have to be rearranged as
follows.
Consider the last polygon in the A (Say). If it has no overlaps in depths with it‟s
predecessors, then it has no overlaps with any other polygons and can remain at the end.
Other wise, if it has any depth overlaps with one or more polygons, denoted by the set
{b}, then we have to again check if any specific polygon B from this set is obscured by

121

Downloaded fro m [Link] m

 Downloaded fro m [Link] m
A. If yes, then B has no business to be in that priority since A, which is obscuring B,
should have a higher priority than B. corresponding modifications are to be made to the
list.
Based on the these considerations, in the above figure A should have a higher
priority than B, though the Zmax of B is less than that of A.
The question is how to find out the relation “A obscures B”? Apply the following
steps in the same order to ascertain that A does not obscure B.
(a) Depth minimax test should indicate that A and B do not overlap in depth and B is
closer to the viewpoint than A. This test is implemented by initially sorting by depth
all polygons and by the way A and {b} are selected.
(b) Minimax test in xy should indicate that A and B do not overlap in X or Y.
(c) All vertices of A should be farther from the view point than the plane of B. This can
be implemented by substituting x,y coordinates of a into the plane equation of B and
solving for the depth of B.
(d) All vertices of B should be closer to the viewpoint than the plane of B.
(e) A full overlap test should indicate that A and B do not overlap in x or y.

The order is not very important, except that any one of the tests being true indicates
that A does not obscure B. since the latter tests are more involved, it is desirable that the
order is followed so that one can avoid the latter tests if possible.

Is the “A obscures B” relation sufficient condition to sort polygons? Look at the

following sequence of figure.

122

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

Obviously the algorithm fails to give a clearcut sequence of polygons. In such cases, it is
desirable to subdivide one/more polygons so that the “Chain reactions” are avoided.

Block Summary
You were introduced to the concept of hidden surface removal a necessity to
create the concept of depth.
You were introduced to the basic inefficiency of the simple algorithm based on
the painters concept. The first algorithm you were introduced was the simple depth
buffer algorithm which was just the extension of the painters algorithm.
To make the algorithm more efficient, the concept of using the geometric
properties like xy overlapping and plane equations was introduced. Then the concept of
scanline and span line coherence was introduced. Especially the span line coherence
algorithm was helpful in reducing the computations involved.
The concept of area coherence wherein the concept of coherence was extended to
2-dimensional areas was introduced leading to the concept of the recursive Warnock‟s
algorithm.
The limitations of these methods was discussed with certain examples.

Review questions:
1. State painters algorithm in 2-3 lines.
2. What is the main difficulty of the scan line algorithm?
3. What is the concept of overlap testing ?
4. If tow or more objects fail in overlap testing, does it mean they always obscure at least
in some regions.
123

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

5. Explain the concept of coherence of pixels.

6. Name the algorithm that work on the concept of area coherence
7. State one method of improving the recursive efficiency of the above algorithm.
8. If a portion of polygon A obscure B, a portion of B obscures C and so on so that they
form a cyclic loop, the concept of Zmax fails? How do you apply the scan conversion
algorithm in such a case?

Ans wers :
1. Start painting from the object that is farthest from the viewer. As and when new
objects are painted, the earlier objects that are obscured by the nearer objects
automatically get removed- either in full or in those regions where they are invisible.
2. It is computationally intensitive.
3. Two objects can obscure each only if Zmax of one is greater than the Zmax of the
other. Even then, they overlap only if they overlap in either x or y cordinates. i.e. the
maximum y of one is greater than the minimum y of the other or the maximum x of one
is greater than the minimum x of the other and this holds for both the objects.
4. No, It depends on their actual shapes and placements
5. The general property of coherence is that neighboring pixels share properties i.e. if a
particular pixel belongs to a particular object, most probably it‟s neighboring pixels also
lie in the same object. This applied over certain “Spans”.
6. Warnock‟s Algorithm
7. By dividing the screen recursive not into rectangles but into areas similar to the shape
of the polygons.
8. By dividing on/more of these polygons into similar polygons.

124

Downloaded fro m [Link] m

 Downloaded fro m [Link] m

125

Downloaded fro m [Link] m