COMPUTER GRAPHICS 22318

Pravin Patil Polytechnic

Bhyandar East

Department : Computer Engineering.

Course : Computer Graphics

Semister : III Class : CO3I

Lecturer : Mrs. Harsha Devendra Zope.

COMPUTER GRAPHICS 22318

CHAPTER 1

Basics Of Computer Graphics

COMPUTER GRAPHICS 22318

CHAPTER 1

Basics Of Computer Graphics

1.1

OBJECT AND IMAGES

Image is basically representation of real world object on a computer.

It can be an actual picture displayed , a stored page in a video memory as a source

code generated by a program.

Image = 2D array of data with color value.

To manipulate the image you need to process each pixel individually.

Pixel: A pixel is the smallest piece of information in an image.In computer

graphics objects are represented as collection of pixels, where pixel is smallest

addressable point which can be displayed on screen.

Resolution: In computer graphics, display resolution is the number of pixels

contained on a display monitor .It is expressed in terms of the number of pixels

on the horizontal axis and the number on the vertical axis.

COMPUTER GRAPHICS 22318

Aspect ratio:

It is the ratio of the number of vertical points to the number of horizontal points

necessary to produce equal length lines in both directions on the screen. or In

computer graphics, the relative horizontal and vertical sizes. For example, if a

graphic has an aspect ratio of 2:1, it means that the width is twice as large as the

height. or Aspect ratio is the ratio between width of an image and the height of

an image.

Example: The term is also used to describe the dimensions of a display resolution.

For example, a resolution of 800x600, 1027x768, 1600x1200 has an aspect ratio

of 4:3. Resolution 1280x1024 has an aspect ratio 5:4 Resolution 2160x1440,

2560x1700 has an aspect ratio 3:2

COMPUTER GRAPHICS 22318

VIDEO DISPLAY MODE

1. Text mode

2. Graphics mode

Text mode is a personal computer display setting that divides the display

screen into 25 rows and 80 columns in order to display text without images.

In text mode, each box can contain one character. Text mode contrasts with

graphics mode, which features an array of pixels instead of text boxes.

Text mode is also known as character mode or alphanumeric mode.

Graphics mode A way of displaying images on a computer screen or other

graphics device such that the basic unit is the pixel. Lines and characters on the

screen are drawn pixel by pixel. The resolution and complexity of the image

depends on how many pixels there are in total, and how many bits are assigned

to each pixel. The more bits per pixel, the more different colors or shades of gray.

A single graphics device can operate in a number of different graphics modes

with different resolutions and color selections. A common mode for a desktop PC

would be 1024 by 768 pixels with 256 different colors – chosen from a much

larger number – available for each pixel. See also text mode, computer graphics.
COMPUTER GRAPHICS 22318

1.2

Display Devices

Raster scan display:

• In this electron beam moves all over the screen one row at a time.

• As electron beam moves across each row, beam intensity is turned ON and OFF

to create picture pattern. Here, picture definition is stored in memory called as

Refresh Buffer or frame buffer. This refresh buffer holds set of intensity values

for all screen points .These stored intensity values are retried from buffer and

displayed on screen one row at a time.

• When beam is moved from left to right, it is ON and when moved from right to

left (from end of first row to the start of next row.)it is OFF and is termed as

horizontal retrace. When beam reaches bottom of screen it is made OFF and it

return to top left corner of screen which is referred as vertical retrace.

COMPUTER GRAPHICS 22318

• Raster scan display maintains the steady Image on the screen by repeating

scanning of the same image. This process is known as refreshing of screen.

• Raster scan may use non-interlace or interlace technique to display picture. In

non- interlace , electron beam scans through each line one by one.

• In interlace technique, beam firstly scans through even scan lines and then odd

scan lines thus scanning screen twice, ie . beam scans through alternate line first

and then through remaining alternate lines.

Vector scan display

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

copy device.

When operated as a random-scan display unit, a CRT has the electron beam

directed only to the parts of the screen where a picture is to be drawn.

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

also referred to as vector displays (or stroke-writing or calligraphic displays).

COMPUTER GRAPHICS 22318

Here the electron gun of a CRT illuminate’s points and / or straight lines in any

order. If we want a line connecting point A with point B on vector graphics

display, we simply drive the beam reflection circuitry, which will cause beam to

go directly from point A to point B.

Refresh rate on a random-scan system depends on the number of lines to be

displayed.

Picture definition stored as a set of line drawing commands in an area of

memory called “refresh display file” or also called as display list or display

program or refresh buffer.

To display a given picture, the system cycles through the set of commands in

the display file, drawing each component line by line in turn. After all line

drawing commands have been processed, the system cycles back to the first line

drawing command in the list. And repeats the procedure of scan, display and

retrace.

This displays to draw all the component lines of picture 30 to 60 frames/second

Random scan system is designed for line drawing applications; hence cannot

display realistic shaded scenes.

Vector displays produces smooth line drawings but raster produces jagged lines

that are plotted points

Random scan suitable for applications like engineering and scientific drawings
COMPUTER GRAPHICS 22318

Graphics patterns are displayed by directing the electron beam along the

component lines of the picture

A scene is then drawn one line at a time by positioning the beam to fill in the

line between specified end points.

Flat Panel Display

Flat-Panel Devices are the devices that have less volume, weight, and power

consumption compared to Cathode Ray Tube (CRT). Due to the advantages of

the Flat-Panel Display, use of CRT decreased. As Flat Panel Devices are light in

weights that’s why they can be hang on walls and wear them on our wrist as a

watch. Flat Panel Display (FPD) allow users to view data, graphics, text and

images.
COMPUTER GRAPHICS 22318

Types of Flat Panel Display:

Emissive Display:

The Emissive Display or Emitters are the devices that convert electrical energy

into light energy.

Examples: Plasma Panel, LED (Light Emitting Diode), Flat CRT.

Non-Emissive Display:

Non-Emissive Display or Non-Emitters are the devices that use optical effects to

convert sunlight or some other source into graphic patterns.

Examples: LCD (Liquid Crystal Display)

COMPUTER GRAPHICS 22318

Light Emitting Diode (LED):

LED is a type of LCD that actually accompanies the advancement

of technology. This replaces the fluorescent tube with backlight technology,

which produces a clearer picture than the LCD. LED have wider viewing angle

than the LCD. It have better black level and contrast in comparison to LCD

LCD display. LED delivers better color accuracy in comparison to the LCD.

Advantage:

LED have very long life.

It requires low maintenance.

LED doesn’t produce heat.

LED is highly efficient.

Disadvantage:

It is more costly.

It have restricted viewing angle.

Liquid Crystal Display (LCD):

An LCD is a passive device, which means that it does not deliver any light to

display characters, animations, videos, etc. LCD uses fluorescent tubes to

lighten the picture, but can’t provide the clearer picture as LED delivers. It

delivers good color accuracy, but we can notice the difference if we compare

LED and LCD color accuracy. In LCD, the wide angle decreases with 30
COMPUTER GRAPHICS 22318

degrees from the center in the image then the contrast ratio.

Advantage:

It consumes less power.

It includes millions of color.

It is lighter than LED.

Disadvantage:

It needs extra light sources.

It have also restricted viewing angle.

Its speed is very slow.

1.4

Graphics functions with its syntax:

Using functions of graphics.h in Turbo C compiler you can make graphics

programs, animations, projects, and games. You can draw circles, lines,

rectangles, bars and many other geometrical figures. You can change their colors

using the available functions and fill them. Following is a list of functions of

graphics.h header file.

1) Line: This command draws a line on screen.

Syntax: line(x1,y1,x2,y2 );
COMPUTER GRAPHICS 22318

Where, (x1,y1) are co-ordinates of startingpoint of line and (x2,y2) are co-

ordinates of end point of line.

2)Circle():This command draws a circle on screen.

Syntax:Circle(x,y,r);

Where (x,y) are co-ordinates of centre of circle and r is radius of circle.

1.5

Virtual reality (VR)

Virtual Reality means experiencing things through our computers that don't

really exist.

OR

Virtual Reality (VR) is the use of computer technology to create a simulated

environment. Instead of viewing a screen in front of them, users are immersed

and

able to interact with 3D worlds.

Advantages:

Virtual reality creates a realistic world

COMPUTER GRAPHICS 22318

Through Virtual Reality user can experiment with an artificial

environment.

Virtual Reality make the education more easily and comfort.

It enables user to explore places.

Virtual Reality has made watching more enjoyable than reading.

Virtual reality widely used in video games, engineering, entertainment,

education,

design, films, media, medicine and many more.

Applications of computer graphics :

1.Computer Aided Design /Drafting(CAD/CADD).

2.Geographical Information System(GIS)

3.Desktop publishing(DTP)

4.Graphical User Interface(GUI)

5.Digital Art.
COMPUTER GRAPHICS 22318

CHAPTER 2

Raster Scan Display

COMPUTER GRAPHICS 22318

CHAPTER 2

Raster Scan Display

2.1
DDA LINE DRAWING ALGORITHM

This algorithm generates a line from differential equations of line and hence

the name DDA.

DDA algorithm is an incremental scan conversion method.

A DDA is hardware or software used for linear interpolation of variables over

an interval between start and end point.

DDAs are used for rasterization of lines, triangles and polygons.

DDA method is referred by this name because this method is very similar to

the numerical differential equations. The DDA is a mechanical device that solves

differential equations by numerical methods.

Algorithm:

Steps 1: Read the end points of line (x1,y1) and (x2,y2).

Steps 2: dx = abs (x2 – x1) and

dy = abs (y2 – y1)

Step 3: if dx >= dy then

COMPUTER GRAPHICS 22318

length = dx

else

length = dy

end if

Step 4: dx = (x2 – x1)/length

Step 5: dy = (y2 – y1)/length

Step 6: x= x1 + 0.5 * sign (dx)

y= y1 + 0.5 * sign (dy)

Step 7: i = 1

while (i <= length)

plot (integer (x), integer (y))

x = x + dx

y = y + dy

i=i+1

Step 8: End
COMPUTER GRAPHICS 22318

Merits of DDA algorithms:

It is the simplest algorithm and it does not require special skills for

implementation.

It is a faster method for calculating pixel positions than the direct use of

equation y = mx + b. It eliminates the multiplication in the equation by

making use of raster characteristics, so that appropriate increments are

applied in the x or v direction to find the pixel positions along the line path

Floating point Addition is still needed.

COMPUTER GRAPHICS 22318

BRESENHAMS LINE DRAWING ALGORITHM

COMPUTER GRAPHICS 22318

Merits of Bresenham’s Algorithm:

Bresenhams algorithm is faster than DDA algorithm

Bresenhams algorithm is more efficient and much accurate than DDA

algorithm.

Bresenham's line algorithm is a highly efficient incremental method over

DDA.

Bresenhams algorithm can draw circles and curves with much more
COMPUTER GRAPHICS 22318

accuracy than DDA algorithm.

It produces mathematically accurate results using only integer addition,

subtraction, and multiplication by 2, which can be accomplished by a simple

arithmetic shift operation.

Bresenham’s algorithm to plot 1/8th of the circle and write the

algorithm required to plot the same.

The key feature of circle that it is highly symmetric. So, for whole 360 degree of

circle we will divide it in 8-parts each octant of 45 degree. In order to that we will

use Bresenham’s Circle Algorithm for calculation of the locations of the pixels

in the first octant of 45 degrees. It assumes that the circle is centered on the origin.

So for every pixel (x, y) it calculates, we draw a pixel in each of the 8 octants of

the circle as shown below:

COMPUTER GRAPHICS 22318

Algorithm:

Step 1: Read the radius of circle (r).

Step 2: Set decision parameter d = 3 – 2r.

Step 3: x=0 and y=r.

Step 4: do

Plot (x,y)

If(d<0) then

d = d + 4x + 6

Else

d=d + 4(x-y) + 10

y=y-1

}
COMPUTER GRAPHICS 22318

X=x-1

While(x<y)

Step 5: stop

Plotting 8 points, each point in one octant

Call Putpixel (X + h, Y + k).

Call Putpixel (-X + h, Y + k).

Call Putpixel (X + h, -Y + k).

Call Putpixel (-X + h, -Y + k).

Call Putpixel (Y + h, X + k).

Call Putpixel (-Y + h, X + k).

Call Putpixel (Y + h, -X - k).

Call Putpixel (-Y + h,-X + k).

COMPUTER GRAPHICS 22318

2.4

TYPES OF POLYGAON

Convex Polygon:

It is a polygon in which if you take any two positions of polygon then all the

points on the line segment joining these two points fall within the polygon itself.

Concave Polygon:

It is a polygon in which if you take any two positions of

polygon then all the points on the line segment joining these two points does not

fall entirely within

COMPUTER GRAPHICS 22318

Inside outside test

This method is also known as counting number method. While filling an

object, we often need to identify whether particular point is inside the object or

outside it.

There are two methods by which we can identify whether particular point is inside

an object or outside namely, Odd-Even Rule, and Non-zero winding number rule.

1. Odd-Even Rule: In this technique, we count the edge crossing along the

line from any point (x, y) to infinity. If the number of interactions is odd

then the point (x, y) is an interior point. If the number of interactions is

even then point (x, y) is an exterior point. Here is the example to give you

the clear idea,

COMPUTER GRAPHICS 22318

2. Non-zero Winding Number Rule: This method is also used with the simple

polygons to test the given point is interior or not. It can be simply

understood with the help of a pin and a rubber band. Fix up the pin on one

of the edge of the polygon and tie-up the rubber band in it and then stretch

the rubber band along the edges of the polygon. When all the edges of the

polygon are covered by the rubber band, check out the pin which has been

fixed up at the point to be test. If we find at least one wind at the point

consider it within the polygon, else we can say that the point is not inside

the polygon.

In another alternative method, give directions to all the edges of the

polygon. Draw a scan line from the point to be test towards the left most

of X direction. Given the value 1 to all the edges which are going to upward

direction and all other – 1 as direction values. Check the edge direction
COMPUTER GRAPHICS 22318

values from which the scan line is passing and sum up them. If the total

sum of this direction value is non-zero, then this point to be tested is an

interior point, otherwise it is an exterior point. In the above figure, we

sum up the direction values from which the scan line is passing then the

total is 1 – 1 + 1 = 1; which is non-zero. So the point is said to be an interior

point.

Polygaon filling algorithm

Flood fill

Sometimes it is required to fill in an area that is not defined within a single colour

boundary. In such cases we can fill areas by replacing a specified interior colour

instead of searching for a boundary colour . This approach is called a flood fill

algorithm. Like boundary fill algorithm, here we start with some seed and

examine the neighbouring pixels. However, here pixels are checked for a

specified interior colour instead of boundary colour and they are replaced by new

colour.

Using either 4-connected or 8-connected approach, we can step through pixel

positions until all interior point have been filled. The following procedure

illustrates the recursive method for filling

COMPUTER GRAPHICS 22318

8-connected region using flood-fill algorithm.

Procedure: flood_fill(x,y,old_colour,new_colour)

If(gepixel (x,y)=old_colour)

Putpixel(x,y,new_colour);

flood_fill(x+1,y,old_colour,new_colour);

flood_fill(x-1,y,old_colour,new_colour);

flood_fill(x,y+1,old_colour,new_colour);

flood_fill(x,y-1,old_colour,new_colour);

flood_fill(x+1,y+1,old_colour,new_colour);

flood_fill(x-1,y-1,old_colour,new_colour);

flood_fill(x+1,y-1,old_colour,new_colour);

flood_fill(x-1,y+1,old_colour,new_colour);

}
COMPUTER GRAPHICS 22318

BOUNDRY FILL

Limitations:

There is a problem with this technique. Consider the case following, where we

tried to fill the

entire region. Here, the image is filled only partially. In such cases, 4-connected

pixels technique

cannot be used.
COMPUTER GRAPHICS 22318

SCAN LINE ALGORITHM

For each scan line crossing a polygon, the area-fill algorithm locates the

intersection points of the scan line with the polygon edges.

These intersection points are then sorted from left to right, and the

corresponding frame-buffer positions between each intersection pair are set to

the specified fill color

Scan line algorithm works by intersecting scan line with polygon edges and

fills the polygon between pairs of intersections. The following steps depict how

this algorithm works.

Step 1 : Find out the Ymin and Ymax from the given polygon.

Step 2 : ScanLine intersects with each edge of the polygon from Ymin to Ymax.

Name each intersection point of the polygon.

COMPUTER GRAPHICS 22318

As per the Fig. 2.21 shown, they are named as p0, p1, p2, p3. Step 3 : Sort the

intersection point in the increasing order of X coordinate i.e. (p0, p1), (p1, p2),

and (p2, p3).

Step 4 : Fill all those pair of coordinates that are inside polygons and ignore

the alternate pairs.

2.5

Frame Buffer

The frame buffer is the video memory (RAM) that is used to hold or map the

image displayed on the screen.

OR

A framebuffer (frame buffer, or sometimes framestore) is a portion of RAM

containing a bitmap that drives a video display.

Character generation methods

i) Stroke method:

This method uses small line segments to generate a character.

COMPUTER GRAPHICS 22318

The small series of line segments are drawn like a strokes of a pen to form a

character as shown in Fig.

We can build our own strike method. By calling a line drawing algorithm. Here,

it is necessary to decide which line segments are needed for each character and

then drawing these segments using line drawing algorithm. This method supports

scaling of the character. It does this by changing the length of line segments used

for character drawing.

ii) Starburst method:

In this method a fix pattern of line segments are used to generate

characters. As shown in Fig. there are 24 line segments. Out of 24 line segments,

segments required to display for particular character, are highlighted. This

method is called starbust method because of its characteristic appearance.

The patterns for particular characters are stored in the form of 24 bits

code.

Each bit representing one line segments.

COMPUTER GRAPHICS 22318

The bit is set to one to highlight the line segments otherwise it is set to zero.

For example, code for letter V is, 110011100001001100000000

iii)BITMAP METHOD

Bitmap method is a called dot-matrix method as the name suggests this

method use array of bits for generating a character. These dots are the

points for array whose size is fixed.

In bit matrix method when the dots is stored in the form of array the value 1

in array represent the characters i.e. where the dots appear we represent that

position with numerical value 1 and the value where dots are not present is

represented by 0 in array.

It is also called dot matrix because in this method characters are represented

by an array of dots in the matrix form. It is a two dimensional array having

COMPUTER GRAPHICS 22318

columns and rows.

A 5x7 array is commonly used to represent characters. However 7x9 and 9x13

arrays are also used. Higher resolution devices such as inkjet printer or laser

printer may use character arrays that are over 100x100.

****************************************************************
COMPUTER GRAPHICS 22318

CHAPTER 3

Overview Of Transformation
COMPUTER GRAPHICS 22318

3.1

2D transformations with its basic types.

2D transformations: In animation applications one need to move object along

some specified path.Such changes in orientation,size and shape of an object

alter co-ordinates of object and this is done with geometric transformation.

Basic geometric transformations are:

1.Translation.

2.Scaling.

3.Rotation.

1.Translation:It is the process of repositioning an object along a straight line

path from one coordinate location to new co-ordinate location.

To translate a two dimensional point one need to add translation distance tx and

ty along x and y axis respectively to original co-ordinate position as,

x’=x+tx

y’=y+ty

where,

(x,y)=Original co-ordinates of a point.

(x’,y’)=New co-ordinates of a point.

tx,ty= Translation distance in x,y direction.

Matrix form defined with column vectors form:

COMPUTER GRAPHICS 22318

x’ = x tx

y’ = y + ty

i.e P’=P+T

2.Scaling:

Scaling changes size of object along x or y or both axes. New transformed co-

ordinates of a point (x,y) can be calculated by multiplying it with scaling

factors Sxand Sy in x and y directions respectively.

• Scaling is stretching of points along axes:

Equations :

X = Sx . X

Y = Sy . Y

Where,
COMPUTER GRAPHICS 22318

(x,y) = Original co – ordinates of point.

(X’,Y’) = new co-ordinates of point.

(Sx.Sy) = scaling factors.

• In matrix from :

x' = Sx 0 x

y' = 0 Sy y

P’=S.P

3)Rotation:

• Rotation of an object is repositioning it along a circular path in x y plane.

We need to specify rotation angle Ɵ of position of rotation point about

which object is to be rotated.

• General equations: x'=x.cos Ɵ -y.sin Ɵ

y'=x.sin Ɵ + y. cos Ɵ
COMPUTER GRAPHICS 22318

Matrix form:

x' = cos Ɵ -sinƟ x

y' sin Ɵ cosƟ y

i.e P'=R.P
COMPUTER GRAPHICS 22318

3.2

MATRIX REPRESENTATION AND HOMOGENEOUS COORDINATES

Homogeneous coordinates are another way to represent points to simplify the

way
COMPUTER GRAPHICS 22318

3.3

COMPOSITE TRANSFORMATION

Rotation of an object about any selected arbitrary point P1(x1 ,y1)

To do rotation of an object about any selected arbitrary point P1(x1 ,y1),

following

sequence of operations shall be performed.

1. Translate: Translate an object so that arbitrary point P1 is moved to

coordinate

origin.

2. Rotate: Rotate object about origin.

3. Translate: Translate object so that arbitrary point P1 is moved back to the its

original position.

Note: Here to do one operation we are doing the sequence of three operations.

So

it is called as composite transformation or concatenation.

Rotate about point P1(x1,y1).

1) Translate P1 to origin.

2) Rotate
COMPUTER GRAPHICS 22318

3) Translate back to P1.

Equation for this composite transformation matrix form is as follows:

Here (x1,y1) are coordinates of point P1 and hence are translation factors tx and

ty; we want to move P1 to origin , x1 and y1 are x and y distances to P1and

hence

it is translation factor.
COMPUTER GRAPHICS 22318

2D AND 3D SCALING MATRIX

2D Scaling

Scaling means to change the size of object. This change can either be positive

or negative.

To change the size of an object, scaling transformation is used. In the scaling

process, you either expand or compress the dimensions of the object.

Scaling can be achieved by multiplying the original co-ordinates of the object

with the scaling factor to get the desired result.

COMPUTER GRAPHICS 22318

Let us assume that the original co-ordinates are (X, Y), the scaling factors are

(SX, SY), and the produced co-ordinates are (X', Y'). This can be mathematically

represented as shown below:

The scaling factor SX, SY scales the object in X and Y direction respectively.

The above equations can also be represented in matrix form as below:

COMPUTER GRAPHICS 22318

It specifies three co-ordinates with their own scaling factors. If scale factors,

Sx = Sy = Sz = S > 1 then the scaling is called as magnification.

Sx = Sy = Sz = S < 1 then the scaling is called as reduction.

Therefore, point after scaling with respect to origin can be calculated as,

P=P . S

3.5TYPES OF PROJECTION

Perspective projection:

• In Perspective projection, the distance from the center of projection to

project plane is finite and the size of the object varies inversely with

distance which looks more realistic.

• The distance and angles are not preserved and parallel lines do not remain

parallel. Instead, they all converge at a single point called center of

projection or projection reference point. It is more elaborated in fig:

COMPUTER GRAPHICS 22318

There are 3 types of perspective projections which are shown in the figure:

1. One-point:

One principle axis cut by projection plane.

One axis vanishing point.

2. Two-point:

Two principle axes cut by projection plane.

Two axis vanishing points.

COMPUTER GRAPHICS 22318

3.Three-point:

Three principle axes cut by projection plane.

Three axis vanishing points.

Parallel Projection

Orthographic projection – the projection direction is a normal one to the plane

and it is categorized as

o Top projection

o Front projection

o Side projection
COMPUTER GRAPHICS 22318

Oblique projection – the projection direction is not a normal one to the plane;

it gives a better view and it is categorized as

o Cavalier projection

o Cabinet projection

****************************************************************
COMPUTER GRAPHICS 22318

CHAPTER 4

Windowing and Clipping

COMPUTER GRAPHICS 22318

4.1

WINDOWING AND CLIPPING CONCEPT

Window to Viewport transformation:

1) The picture is stored in the computer memory using any convenient Cartesian

co-ordinate system, referred to as World Co-ordinate System (WCS).

2) When picture is displayed on the display device it is measured in Physical

Device coordinate system(PDCS) corresponding to the display device. Therefore,

displaying an image of a picture involves mapping the co-ordinates of the points

and lines that form the picture into the appropriate physical device co-ordinate

where the image is to be displayed. This mapping of co-ordinate is achieved with

the use of co-ordinate transformation known as viewing transformation.

COMPUTER GRAPHICS 22318

3) Sometimes the two dimensional viewing transformation is simply

referred to as the window to viewport transformation or the windowing

transformation.

4) The viewing transformation which maps picture co-ordinates in the

WCS to display co-ordinates in PDCS is performed by the following

transformation.

a) Converting world co-ordinates to viewing co-ordinates.

b) Normalizing viewing co-ordinates.

c) Converting normalized viewing co-ordinates to device cordinates.

5)World Co-ordinate System (WCS) is infinite in extent and the device

display area is finite.

6)To perform a viewing transformation we select a finite world co-ordinate

area for display called a window.

7)An area on a device to which a window is mapped is called a viewport.

8)The window defines what is to be viewed, the viewport defines where it

is to be displayed, as shown in fig:

COMPUTER GRAPHICS 22318

The steps involved in viewing transformation:

1. Construct the scene in world cordinates using the output primitives and

attributes.

2.Obtain a particular orientation for the window by setting a two-

dimensional viewing co-ordinate system in the world co-ordinate plane and

define a window in the viewing co-ordinate system.

3.Use viewing co-ordinates reference frame to provide a method for setting

up arbitrary orientations for rectangular windows.

4. Once the viewing reference frame is established, transform descriptions

in world co-ordinates to viewing co-ordinates.

5.Define a view port in normalized co-ordinates and map the viewing co-

ordinate description of the scene to normalized co-ordinates.

6.Clip all the parts of the picture which lie outside the viewport.
COMPUTER GRAPHICS 22318

4.2

LINE CLIPPING

Cohen Sutherland line clipping algorithm.

1.Read to end points of the line say P1(x1,y1) and P2 (x2,y2)..

2. Read two corners (left-top and right-bottom) of the window,say (Wx1,Wy1 and

Wx2,Wy2).

3. Assign the region codes for two endpoints P1 and P2 using following steps:

Initialize code with bits 0000

Set Bit 1-if(x<Wx1)

Set Bit 2 -if(x>Wx2)

Set Bit 3 -if(y<Wy2)

Set Bit 4-if(y>Wy1)

4. Check for visibility of line P1 P2

a) If region codes for both endpoints P1 and P2 are zero then the line is

completely

visible. Hence draw the line and go to step 9.

b) If region codes for endpoints are not zero and the logical ANDing of

them is also

nonzero then the line is completely invisible, so reject the line and go to

step 9
COMPUTER GRAPHICS 22318

c) If region codes for two endpoints do not satisfy the conditions in 4a) and

4b)the line is partially visible.

5.Determine the intersecting edge of the clipping window by inspecting the

region codes of two endpoints

a) If region codes for both the end pointe are non-zero, find intersection

points P1'

and P2' with boundary edges of clipping window with respect to point P1

and point P2 respectively.

b) If region code for any one end point is non zero then find intersection

point P1' or

P2' with the boundary edge of the clipping window with respect to it.

6.Divide the line segments considering intersection points.

7.Reject the line segment if any one end point of it appears outsides the clipping

window.

8. Draw the remaining line segments.

9. Stop.
COMPUTER GRAPHICS 22318

Cyrus-Beck line clipping algorithm.

Cyrus Beck Line Clipping algorithm: Cyrus Beck Line Clipping algorithm is used

to clip 2D/3D lines against convex polygon/polyhedron.

• Cyrus Beck Line clipping algorithm is actually, a parametric line-clipping

algorithm.

• The term parametric means that we require finding the value of the parameter t

in the parametric representation of the line segment for the point at that the

segment intersects the clipping edge.

• Consider line segment P1P2. The parametric equation of line segment P1P2 is,

P(t) = P1 + t(P2 – P1) … (1) Where, t value defines a point on the line going

through P1 and P2. 0 <= t <= 1 defines line segment between P1 and P2.

If t = 0 then P(0) = P1. If t = 1 then P(1) = P2.

• Consider a convex clipping region R, f is a boundary point of the convex region

R and n is an inner normal for one of its boundaries as shown in Fig

COMPUTER GRAPHICS 22318

• Then we can distinguish in which region a point lie by looking at the value of

the dot product n.[P(t) – f ], as shown in Fig.

• If dot product is negative i.e., n.[P(t) – f ] < 0 … (2)

then the vector P(t) – f ] is pointed away from the interior of R.

• If dot product is zero i.e., n.[P(t) – f ] = 0 … (3)

then the vector P(t) – f ] is pointed parallel to the plane containing f and

perpendicular to the normal.

• If dot product is positive

i.e., n.[P(t) – f ] > 0 … (4)

then the vector P(t) – f ] is pointed towards the interior of R.

COMPUTER GRAPHICS 22318

Dot products for three points inside, outside and on the boundary of the clipping

region

• As shown in Fig. if the point f lies in the boundary plane or edge for which n is

the inner normal, then that point t on the line P(t) which satisfies, n.[P(t) – f ] = 0

condition is the intersection of the line with the boundary edge.

• To get the formal statement of the Cyrus-Beck algorithm we substitute value

of P(t) in equation 3. n . [P(t) – f ] = n . [P1 + (P2 – P1)t – f ] = 0 … (5)

• The relation should be applied for each boundary plane or edge of the window

to get the intersection points. Thus in general form equation (5) can be written as,

ni . [P1 + (P2 – P1)t – fi ] = 0 … (6) where, i is edge number.

• Solving equation (6) we get, ni . [P1 – fi ] + ni . (P2 –P1)t = 0 … (7)

• Here the vector P2 – P1 defines the direction of the line. The direction of the

line is important to correctly identify the visibility of the line. The vector P1 - fi

is proportional to the distance from the end point of the line to the boundary point.

• Let us define, D = P2 – P1 as the direction of a line and Wi = P1 – fi as weighting

factor. • Substituting newly defined variable D and Wi in Equation (7)

we get, ni.Wi + (ni . D)t = 0 … (8)

t = – (ni.Wi) /(ni.D) … (9) where, D ≠ 0 and i = 1, 2, 3 .....

COMPUTER GRAPHICS 22318

• The equation (9) is used to obtain the value of t for the intersection of the line

with each edge of the clipping window. We must select the proper value for t

using following tips :

1. If t is outside the range 0<= t <= 1, then it can be ignored.

2. We know that, the line can intersect the convex window in at most two points

, i.e. at two values of t. With equation (9) , there can be several values of t in the

range of 0<= t <= 1 . We have to choose the largest lower limit and the smallest

upper limit.

3. If (ni . Di) > 0 then equation (9) gives lower limit value for t and if (ni. Di) < 0

then equation (9) gives upper limit value for t.

Step 1: Read end points of line P1 and P2.

Step 2: Read vertex coordinates of clipping window.

Step 3: Calculate D = P2 – P1.

Step 4: Assign boundary point b with particular edge.

Step 5: Find inner normal vector for corresponding edge.

Step 6:Calculate D.n and W = P1 – b

Step 7:If D.n > 0

tL = – (W.n)/(D.n)

else

tU = – (W.n)/(D.n)
COMPUTER GRAPHICS 22318

end if

Step 8: Repeat steps 4 through 7 for each edge of clipping window.

Step 9: Find maximum lower limit and minimum upper limit.

Step 10: If maximum lower limit and minimum upper limit do not satisfy

condition 0 ≤ t ≤ 1 then ignore line.

Step 11: Calculate intersection points by substituting values of maximum lower

limit and minimum upper limit in parametric equation of line P1P2.

Step 12: Draw line segment P(tL) to P(tU).

Step 13: Stop.

COMPUTER GRAPHICS 22318

Algorithm to clip line using Liang Barsky line clipping algorithm.

Liang Barsky line clipping algorithm:

1. Read two endpoints of the line say p 1 (x 1 , y 1 ) and p 2 (x 2 , y 2 ).

2. Read two corners (left top and right-bottom) of the window, (x wmin ,y wmax

,x wmax ,y wmin )

3. Calculate the values of parameters p i and q i for i=1,2,3, 4 such that

p 1 = -∆x q 1 =x 1 -x wmin

p 2 = ∆x q 2 =x wmax -x 1

q 1 = -∆y q 3 =y 1 - ywmin

q 2 = ∆y q 4 = y wmax -y 1

4.if p i =0, then

The line is parallel to i th boundary

Now if q i &lt;0 then

Line is completely outside the boundary hence discard the line segment and goto

stop

Else

Check whether the line is horizontal or vertical and accordingly check the line
COMPUTER GRAPHICS 22318

endpoint with corresponding boundaries. If line endpoints lie within the bounded

area then use them to draw line otherwise use boundary coordinates to draw line.

Goto

stop.

5. Initialize values for t 1 and t 2 as

t 1 =0 and t 2 =1

6.Calculate values for q i /p i for i=1,2,3,4

7.Select values of q i /p i where p i &lt;0 and assign maximum out of them as t 1

8.Select values of q i /p i where p i &gt;0 and assign maximum out of them as t

2.

9.If (t 1 &lt;t 2 )

Calculate the endpoints of the clipped line as follows:

xx 1 =x 1 + t 1 ∆x

xx 2 =x 1 + t 2 ∆x

yy 1 =y 1 +t 1 ∆y

yy 2 =y 1 +t 2 ∆y

Draw line (xx 1 ,yy 1 ,xx 2 ,yy 2 )

COMPUTER GRAPHICS 22318

10.Stop.

MIDPOINT SUBDIVISION

Step 1: Scan two end points for the line P1(x1, y1) and P2(x2, y2).

Step 2: Scan corners for the window as ( x1, y1) and ( x2, y2).

Step 3:Assign the region codes for endpoints P1 and P2 by initializing code with

0000.

Bit 1 - if (x < x1)

Bit 2 - if (x > x2)

Bit 3 - if (y < y2)

Bit 4 - if (y > y1)

Step 4: Check for visibility of line P1, P2.

If region codes for both end points are zero then the line is visible, draw it

and jump to step 6.

If region codes for end points are not zero and the logical Anding operation

of them is also not zero then the line is invisible, reject it and jump to step

6.

If region codes for end points does not satisfies the condition in 4 (i) and 4
COMPUTER GRAPHICS 22318

(ii) then line is partly visible.

Step5: Find midpoint of line and divide it into two equal line segments and repeat

steps 3 through 5 for both subdivided line segments until you get completely

visible and completely invisible line segments.

Step 6: Exit.

4.3

POLYGAON CLIPPING

Sutherland-Hodgeman

In Sutherland-Hodgeman, a polygon is clipped by processing the polygon

boundary as a whole against each window edge. Clipping window must be

convex.

This could be accomplished by processing all polygon vertices against each

clip rectangle boundary in turn beginning with the original set of polygon

vertices, first clip the polygon against the left rectangle boundary to produce a

new sequence of vertices.

The new set of vertices could then be successively passed to a right boundary

clipper, a top boundary clipper and a bottom boundary clipper.

COMPUTER GRAPHICS 22318

At each step a new set of polygon vertices us generated and passed to the

next window boundary clipper. This is the logic used in Sutherland-Hodgeman

algorithm.

Fig. Clipping polygon against successive window boundaries

The output of algorithm is a list of polygon vertices all of which are on the

visible side of clipping plane. Such each edge of the polygon is individually

compared with the clipping plane.

This is achieved by processing two vertices of each edge of the polygon

around the clipping boundary or plane.

This results in four possible relationships between the edge and clipping plane.

1. If first vertex of polygon edge is outside and second is inside window

boundary, then intersection point of polygon edge with window boundary

COMPUTER GRAPHICS 22318

and second vertex are added to output vertices set as shown in Fig. 6.13.

If both vertices of edge are inside window boundary, then add only second

vertex to output set as shown in Fig. 6.14.

3. If first vertex of edge is inside and second is outside of window boundary

then point of intersection of edge with window boundary is stored in

output set as shown in Fig. 6.15.

COMPUTER GRAPHICS 22318

4. If both vertices of edges are outside of window boundary then those

vertices are rejected as shown in Fig. 6.16.

Going through above four cases we can realize that there are two key

processes in this algorithm:

1. Determine the visibility of point or vertex (Inside – Outside Test)

2. Determine the intersection of the polygon edge and clipping plane.

The second key process in Sutherland-Hodgeman polygon clipping algorithm

is to determine the intersection of the polygon edge and clipping plane.

COMPUTER GRAPHICS 22318

Assume that we're clipping a polygon’s edge with vertices at (x1, y1) and (x2,

y2) against a clip window with vertices at (xmin, ymin) and (xmax, ymax).

1. The location (IX, IY) of the intersection of the edge with the left side of the

window is:

(i) IX = xmin

(ii) IY = slope*(xmin – x1) + y1, where the slope = (y2 – y1)/(x2 – x1).

2. The location of the intersection of the edge with the right side of the

window is:

(i) IX = xmax

(ii) IY = slope*(xmax – x1) + y1, where the slope = (y2 – y1)/(x2 – x1)

3. The intersection of the polygon's edge with the top side of the window is:

(i) IX = x1 + (ymax – y1) / slope

(ii) IY = ymax

4. Finally, the intersection of the edge with the bottom side of the window is:

(i) IX = x1 + (ymin – y1) / slope

(ii) IY = ymin

Algorithm for Sutherland-Hodgeman Polygon Clipping:

COMPUTER GRAPHICS 22318

Step 1: Read co-ordinates of all vertices of the polygon.

Step 2: Read co-ordinates of the clipping window.

Step 3: Consider the left edge of window.

Step 4: Compare vertices of each of polygon, individually with the clipping plane.

Step 5: Save the resulting intersections and vertices in the new list of vertices

according to four possible relationships between the edge and the

clipping boundary.

Step 6: Repeat the steps 4 and 5 for remaining edges of clipping window. Each

time resultant list of vertices is successively passed to process next edge of

clipping window.

Step 7: Stop.
COMPUTER GRAPHICS 22318

4.4

TEXT CLIPPING

Many techniques are used to provide text clipping in a computer graphics. It

depends on the methods used to generate characters and the requirements of a

particular application. There are three methods for text clipping which are listed

below −

1) All or none string clipping

2) All or none character clipping

3) Text clipping

The following figure shows all or none string clipping –

In all or none string clipping method, either we keep the entire string or we reject

entire string based on the clipping window. As shown in the abovefigure, Hello2
COMPUTER GRAPHICS 22318

is entirely inside the clipping window so we keep it and Hello1 being only

partially inside the window, we reject.

The following figure shows all or none character clipping –

This clipping method is based on characters rather than entire string. In this

method if the string is entirely inside the clipping window, then we keep it. If it

is partially outside the window, then −

You reject only the portion of the string being outside

If the character is on the boundary of the clipping window, then we discard that

entire character and keep the rest string.

COMPUTER GRAPHICS 22318

The following figure shows text clipping –

This clipping method is based on characters rather than the entire string. In this

method if the string is entirely inside the clipping window, then we keep it. If it

is partially outside the window, then you reject only the portion of string being

***************************************************************
COMPUTER GRAPHICS 22318

CHAPTER 5

Introduction to Curves
COMPUTER GRAPHICS 22318

5.1

CURVE GENERATION

Arc generation technique using DDA algorithm:

Digital differential analyzer algorithm uses the differential equation of the

Curve. The differential equations for simple curve such as circle is fairly easy to

solve. The equation for an arc in the angle parameters can be given as:

x=R cosƟ +x0……………..(1)

y=R sinƟ + y0………………(2)

COMPUTER GRAPHICS 22318

where (x0,y0) is the center of curvature, and R is the radius of arc. As shown in

the fig above.

Differentiating equation (1) and (2) we get,

dx= -R sin Ɵ dƟ………..(3)

dy= R cos Ɵ dƟ…………(4)

From equation (1) and (2) we can solve for R cos Ɵ and R sin Ɵ as

follows:

x= R cos Ɵ + x0

Therefore,

R cos Ɵ=x-x0and…………..(5)

R sin Ɵ= y- y0......................(6)

Substituting values of R cosƟ and R sin Ɵ from equation(5) and

(6) in (3) and(4) we get,

dx= -(y-y0) dƟ…………..(7)

dy= (x-x0)dƟ…………….(8)

The values of dx and dy indicate the increment in x and y increment

respectively, to

be added in the current point on the arc to get the next point on the arc. Therefore

we can write,

x2=x1+dx=x1 -(y1-y0) dƟ…….(9)

y2=y1 +dy=y1 +(x2-x1) dƟ…..(10)

COMPUTER GRAPHICS 22318

The equation (9) and (10) forms the basis for arc generation algorithm. From

equation (9) and (10) we can see that the next point on the arc is the function of

dƟ. To have a smooth curve, the neighbouring points on the arc should be close

to each other. To achieve this, the value of dƟ should be small enough not to

leave gaps in the arc. Usually, the value of dƟ can be determined from the

following equation:

dƟ= Min (0.01, 1/(3.2 x (|x-x0| +|y-y0|))

INTERPOLATION

Specify a spline curve by giving a set of coordinate positions, called control

points, which indicates the general shape of the curve These, control points are

then fitted with piecewise continuous parametric polynomial functions in one of

two ways. When polynomial sections are fitted so that the curve passes through

each control point, the resulting curve is said to interpolate the set of control

points. On the other hand, when the polynomials are fitted to the general control-

point path without necessarily passing through any control point, the resulting

curve is said to approximate the set of control points interpolation curves are

commonly used to digitize drawings or to specify animation paths.

Approximation curves are primarily used as design tools to structure object

surfaces an approximation spline surface credited for a design application.

COMPUTER GRAPHICS 22318

Straight lines connect the control-point positions above the surface

5.2

TYPES OF CURVES

Koch Curve

Koch Curve: - In Koch curve, begin at a line segment. Divide it into third and

replace the center by the two adjacent sides of an equilateral triangle as shown

below.
COMPUTER GRAPHICS 22318

This will give the curve which starts and ends at same place as the

original segment but is built of 4 equal length segments, with each 1/3rd of the

original length. So the new curve has 4/3 the length of original segments. Repeat

same process for each of the 4 segment which will give curve more wiggles and

its length become 16/9 times the original.

Suppose repeating the replacements indefinitely, since each repetition

increases the length by a factor of 4/3, the length of the curve will be infinite but

it is folded in lots of tiny wiggles.

COMPUTER GRAPHICS 22318

Hibert's curve:

The Hilbert curve is a space filling curve that visits every point in a square

grid with a size of 2x2,4x4,8x8,16x16 or any other power of 2.

• This curve can be built by the following successive

approximation.Thepeano curve or space filling curve follows

Hilberts curve.

• In this,begin with a square.The first approximation will be to divide

the square into 4 quadrants and draw the curve which connects the

centre points of each as shown in fig:

COMPUTER GRAPHICS 22318

• In second approximation, further divide each of the quadrants and

connects the centre of each of these finer divisions before moving

to the next major quadrants.

• In the third approximation, again subdivide it .Ib It again connects

the centre of the finest level before stepping to the next level of

detail.
COMPUTER GRAPHICS 22318

• The constructed curve is topologically equivalent to a line D t=1,but

the curve has been so twisted and folded that it exactly fills up a

square.

• The fractal dimension can be determined at each subdivision the

scale changed by 2,but the length changed by 4.For square, it takes

4 curves of the half scale to build the full sized object so dimension

D can be given as=2D.

• The Hilbert curve has topological dimension 1 but fractal dimension

2.It is a line so folded that it behaves like a two dimensional object.

COMPUTER GRAPHICS 22318

C program for Hilbert’s Curve.

#include<stdio.h>

#include<graphics.h>

#include<conio.h>

#include<math.h>

void move(int j, int h, int x, int y)

if(j==1)y-=h;

else if(j==2)x+=h;

else if(j==3)y+=h;

else if(j==4)x-=h;

lineto(x,y);

voidhilbert(intr,intd,intl,intu,inti,inth,int x, int y)

if(i&gt;0)

i--;

hilbert(d,r,u,l,i,h,x,y);
COMPUTER GRAPHICS 22318

move(r,h,x,y);

hilbert(r,d,l,u,i,h,x,y);

move(d,h,x,y);

hilbert(r,d,l,u,i,h,x,y);

move(l,h,x,y);

hilbert(u,l,d,r,i,h,x,y);

void main()

int n,x1,y1;

int x0=50,y0=150,x,y,h=10,r=2,d=3,l=4,u=1;

intgd,gm;

initgraph(“&gd,&gm,”c:\\tc\\bgi”);

printf(“give the value of n”,n);

x=x0;

y=y0;

moveto(x,y);

hilbert(r,d,l,u,n,h,x,y);

getch();

closegraph();
COMPUTER GRAPHICS 22318

Bezier Curves

Where n is the polynomial degree, i is the index, and t is the variable.

The simplest Bézier curve is the straight line from the point P0 to P1. A quadratic

Bezier curve is determined by three control points. A cubic Bezier curve is

determined by four control points.

COMPUTER GRAPHICS 22318

Properties of Bezier Curves

Bezier curves have the following properties −

• They generally follow the shape of the control polygon, which consists of

the segments joining the control points.

• They always pass through the first and last control points.

• They are contained in the convex hull of their defining control points.

• The degree of the polynomial defining the curve segment is one less that

the number of defining polygon point. Therefore, for 4 control points, the

degree of the polynomial is 3, i.e. cubic polynomial.

• A Bezier curve generally follows the shape of the defining polygon.

• The direction of the tangent vector at the end points is same as that of the

vector determined by first and last segments.

• The convex hull property for a Bezier curve ensures that the polynomial

smoothly follows the control points.

COMPUTER GRAPHICS 22318

• No straight line intersects a Bezier curve more times than it intersects its

control polygon.

• They are invariant under an affine transformation.

• Bezier curves exhibit global control means moving a control point alters

the shape of the whole curve.

• A given Bezier curve can be subdivided at a point t=t0 into two Bezier

segments which join together at the point corresponding to the parameter

value t=t0.

B-Spline Curves
The Bezier-curve produced by the Bernstein basis function has limited

flexibility.

• First, the number of specified polygon vertices fixes the order of the

resulting polynomial which defines the curve.

• The second limiting characteristic is that the value of the blending

function is nonzero for all parameter values over the entire curve.

The B-spline basis contains the Bernstein basis as the special case. The B-

spline basis is non-global.

COMPUTER GRAPHICS 22318

A B-spline curve is defined as a linear combination of control points Pi and B-

spline basis function Ni , k t given by

COMPUTER GRAPHICS 22318

Properties of B-spline Curve

B-spline curves have the following properties −

• The sum of the B-spline basis functions for any parameter value is 1.

• Each basis function is positive or zero for all parameter values.

• Each basis function has precisely one maximum value, except for k=1.

• The maximum order of the curve is equal to the number of vertices of

defining polygon.

• The degree of B-spline polynomial is independent on the number of

vertices of defining polygon.

COMPUTER GRAPHICS 22318

• B-spline allows the local control over the curve surface because each

vertex affects the shape of a curve only over a range of parameter values

where its associated basis function is nonzero.

• The curve exhibits the variation diminishing property.

• The curve generally follows the shape of defining polygon.

• Any affine transformation can be applied to the curve by applying it to

the vertices of defining polygon.

• The curve line within the convex hull of its defining polygon.

THE END