Unit: 02

Syllabus
Unit – II (12 hours)
Two Dimensional Viewing: Window-to- View Port Coordinate Transformation.
Line Clipping (Cohen-Sutherland Algorithm) and Polygon Clipping (Sutherland-
Hodgeman Algorithm) Aliasing and Antialiasing, Half Toning, Thresholding,
Dithering. Polygon Filling: Seed Fill Algorithm, Scan line Algorithm. Two
Dimensional Object Representations: Spline Representation, Bezier Curves, B-
Spline Curves. Fractal Geometry: Fractal Classification and Fractal Dimension..
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

VIEWING AND CLIPPING:

Introduction:
By using transformation like scaling, rotation and reflection etc., we can generate
variety of views of a single object. But when we need to display only a portion of the drawing that
are immediate interest, it gives an effect of looking at a large image through a window. The process
of selecting and viewing the part of a picture is called windowing.
A view is what can be seen (visible) in a range of vision. The area of a display that is
visible. The area of a display that is visible through a bezel or cut-out is called as viewing area,
active area.
Viewing Transformation in Two Dimension:
Much like what we see in real life through a small window on the wall or the
viewfinder of a camera, a computer generated image often depicts a partial view of a large screen.
Objects are placed into the scene by modeling transformation to a master coordinate
system, commonly referred as World Coordinate System (WCS).
When we model an image in world device coordinate, we are not interested in the
entire world but only a part of it. The portion of interest in the polygonal area / rectangle specified
in world coordinates called Window. A viewport is normalized device coordinates. The viewport is
going to be used to display the windowed area of the real world and controls the placement of
clipping window within the display widow.
The steps in two dimensional viewing pipelines:
 Construct a world coordinate scene using Model-Coordinate Transformation.
 Convert world coordinate to viewing coordinates. (Clipping).
 Transform viewing coordinates to normalized coordinates.
 Map normalized coordinates to device coordinates.
A widow is defined by a set of 4 world coordinates:

A viewport has four normalized device coordinates:

The following relation maintains the same relative placement of any point in the viewpoint and the
window:

[II.1]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

Therefore

Defining window and viewport, happens to be constant.

(

CLIPPING
Introduction:
Any procedure that identifies portions of the picture that are either inside or outside
of a specified region of space is referred to as a Clipping algorithm or Clipping.
Point Clipping:
A point clipping algorithm finds all the point that
are interior to a clipping window. Any point is said
to be interior to the clipping window, if it satisfies that
point visibility test

Line Clipping:
A line clipping is the process of
removing lines or portions of lines
outside of an area of interest.
Categorizing the lines:
i. The total line is visible.
ii. The total line is invisible.
iii. Segment of the line is visible.
COHEN-SUTHERLAND LINE CLIPPING ALGORITHM
The Cohen-Sutherland line clipping quickly detects & dispenses with two common and
trivial cases to clip a line. We need to consider only its end points.

[II.2]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

CASE I: if both the endpoints of a line lie inside

the windows, the entire lie lies inside the
windows.
CASE II: if both the endpoints of a line lie
entirely one side of the window, it lie
entirety outside the window.
The Cohen-Sutherland algorithm uses half space
code for each end point. Algorithm divides plane in nine regions by four straight lines: top-left, top-
center, top-right, center-left, center, center-right, bottom-left, bottom-center & bottom-right.
Each endpoint of a line is coded based on the region. Each bit in the code is set to either 1 or
0.
The code’s bits are set according to the following conditions:

Algorithm:
Step 1: Compute 4 bit outcodes for each endpoint.
Step 2: If both outcodes are 0000. [Bitwise ‘OR’ yields 0000]. The line is completely visible.
Step 3: If both outcodes have 1’s in the same bit position. [Bitwise ‘AND’ yields non 0000. Clip
the entire line. The line is completely invisible.
Step 4: The line may be partially visible or not visible. Calculate the intersection of the line with
appropriate windows edge.
Cohen-Sutherland Line Clipping Code
Cohen-Sutherland ( )
{
OutCode
Boolean accept=False, done=False;

do {

[II.3]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

if (
{accept =True; done=Ture;} //Completely Visible
else if ) // bitwise AND
{ done=Ture;} // Completely Invisible
else { //Partially visible :Clipping
if (

else

if ( //TOP= 1000
{ Y=

else if ( //BOTTOM= 0100

{ Y=

else if ( //RIGHT= 0010

{ X=

else if ( //LEFT= 0001

{ X=
Y
if(

else

}while (done=False);
if (accept =True)
{ line ( );}
}
Problem 01: Clip the line AB?
Solution: Code(A)=0101, Code(B)=0000;
Case I: Both Code(A), Code(B)= 0000 Completely Visible
But Code(A) 0000.
Case II: Find the same position 1’s in Code A and Code B.
So AB is completely invisible. But at same position
1’s are not available.
Case III: Partially visible.
The Point ‘A’ which intercept
X=
[II.4]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

A’ = (10,8) Code(A’)=0100
B = (20,15) Code(B =0000;
Case I: A’B fully visible: Not accepted.
Case II: A’B fully invisible: Not Accepted.
Case III: the point A’ which intercept

B
Case I :
The line AB (5, 5, 20, 15) is clipped into (13,10,20,15).
POLYGON CLIPPING
A polygon is a closed figure bounded by straight lines with one bounded component and
one unbounded component. Computer graphics deals with both convex and concave polygons.
A convex polygon is such that no side extension cut any other side or vertex. It can be cut by
a straight line into two parts.

A polygon is
represented as a set
of vertices as
Convex Polygon with the
assumptions that
Concave Polygon is also an
edge.
A polygon is stored as a collection of vertices, any clipping algorithm takes one collection
and output new collection. A clipped polygon is also a polygon.
SUTHERLAND-HODGEMAN POLYGON CLIPPING
It is a simple and oldest polygon clipping algorithm. It is very efficient in two cases: one
being when the polygon is completely inside the boundaries and other when it is completely
outside. It uses a divide and conquer strategy to attack the problem. It first clip the polygon against
right clipping boundary. The result polygon is then clipped against the top, left and bottom clipping
boundary respectively.

[II.5]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

Possible cases for the vertices to be clipped are as follows:

Case I: if the previous vertex is outside the windows boundary and the current vertex is inside the
window boundary, then intersection point with the window edge and the current vertex are
added to the new vertex list.
Case II: if both the vertex are inside the window, the only the current vertex will be added to the
new vertex list.
Case III: if the previous vertex is inside the window boundary ad the current vertex is outside the
window boundary then only the intersection point with the window edge added to the new
vertex list.
Case IV: if both the vertices are outside the window boundary then the intersection points are tested
for visibility and then added to the vertex list else none.
To reconcile, Suherland-Hodegeman comprises of two key process the algorithm:
o Perform the inside-outside test to determine the visibility of a point or vertex:

o Determine the intersection of the polygon edge and the clipping plane.
ALIASING
Aliasing is a effect of displaying a high resolution image in a low resolution display.
The aliasing effect are also called artifact or distortion. The following effect may occur due
to aliasing:
a) Jagged Profile: it is especially noticed where there is a
high contrast between the interior and exterior of the
object.
b) Picket Fence Problem: it occurs when a user attempts
to scan convert an object that will not fit exactly in the
raster.

c) Staircase Artifact: In a low resolution display

the slant lines may have unequal brightness
because two corner pixel the distance is 1.4

[II.6]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

whereas between two horizontal or vertical neighbor the distance is 1.

ANTIALIASING
The aliasing effect can be reduced by adjusting intensities of the pixel along the line. The
process of adjusting intensities of the pixels along the line to minimize the effect of aliasing the called
antialiasing.
Methods of antialiasing:
I. Increasing Resolution
II. Unweighted Area Sampling
III. Weighted Area Sampling.
I. INCREASING RESOLUTION:
The aliasing can be minimized by increasing
resolution of the raster display. By increasing
resolution and making it twice the original one,
the line passes through twice as many as column
of the pixel and therefore has twice as many jags
but each jag is half as large as in X & Y
direction.
II. UNWEIGHTED AREA SAMPLING:
In unweighted area sampling, the intensity of pixel is
proportional to the amount of line area occupied by
the pixel. The technique produce noticeably better
results than full/zero intensity pixel.
III. WEIGHTED AREA SAMPLING
Equal area contribute unequally i.e. a small area closer
to the pixel center has greater intensity than does one at
a greater distance. Here intensity depends on area
occupied as well as distance from pixels center.
HALFTONING:
It is a technique for obtaining increasing visual
resolution with a minimum number of intensity. It
decrease the overall resolution of the image and it is more
suitable where the resolution of the original image is less
than the outpour device but having more intensity than
the output device.
THRESHOLDING:
Halftoning is resulting loss of spatial resolution
which is visible in case of displaying a low resolution
image. To improve it thresholding is used. In thresholding
the output image is having the same size as original
image. But having only two intensity levels:

DITHERING:
[II.7]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

Dithering is the process by which we create illusion of a color that are not present actually.
It is done by random arrangement of pixel. It is digital Halftoning process to approximate a color
that can’t be display with a uniform dots of the display device.

The classical dithering algorithm are:

SOLID AREA SCAN CONVERSION

Scan conversion is used to draw line, Circle and ellipse as a
common object. When we want to design a solid area, it is little
difficult b using scan conversion. By using edges and joint, we can
design a polygon which is closed in nature but when multiple solid
object comes, then complex increases to find overlap.
Inside Outside Test:
To find out a pixel inside the polygon or outside the
polygon inside outside test or even odd test is performed.
 A pixel value is extended towards horizontal or vertical direction if he line intersect the
boundary.
o Odd number of times then pixel is inside.
o Even number of times then pixel is outside.
Coherence:
It is a property by which we can improve the efficiency of a program. It can be defined as
edges and pixel are likely to have the same characteristics in the polygon means if one pixel is
inside the polygon, its adjacent pixel are also treated as inside the polygon.

POLYGON FILLING: The polygon filling are of two types:

 Seed Filling
 Scan Conversion
Seed Filling: In this technique, we consider a point inside the polygon and treat it as seed. By
using a recursion process and coherence property, we reach up to boundary in all possible direction
i.e. 4 and 8 ways.
Scan Conversion: These technique are used to determine whether or not a point is inside the
polygon using a scan line order or inside outside test. It doesn’t require any seed point and fill
polygon from top to bottom.
Seed Fill Algorithm:
[II.8]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

Seed fill algorithm are future classified into two broad categories:
 Boundary Fill : fill boundary defined regions.
 Flood Fill : fill the interior defined regions.
Boundary Fill:
Boundary fill is an algorithm used to fill an area with a specified color until the
specified boundary color is encountered.
The algorithm works by starting in a specified i.e. seed, filling the point
with a specified fill color, if it is not a boundary and recursively continuing with the four or
eight closest neighbors.

}
FLOOD FILLING ALGORITHM:
It is similar to boundary fill where we change the color of neighbor from seed point
but not up to boundary. It is basically used to change the color from old color to new color
in a connected region. Normally 8-Way filling algorithm is used.

}}
SCAN LINE ALGORITHM:

[II.9]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

This algorithm works by intersecting scanline 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. As per the
figure shown above, 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.

TWO DIMENSION OBJECT REPRESENATION

INTRODUCTION:
Design of object involves designing of lines, Curves and Surfaces. Curves design are
complex. They are classified into two broad classes:
i. Namable: Nameable curves are from classified geometry those that can be
analyzed mathematically by equations. i.e. Planes, Spheres, parabolas etc.
ii. Unnamable: Industrial shapes demand aesthetic looks and variety of
properties, conventional not described by the namable curves. Such curves
and shapes are known as Unnamable.
Curve Continuity
A complete curve is often made up of segments. So it is important to understand how
individual segment ca be connected. To guarantee a smooth transition from one section of the
piecewise curve to next, we can enforce continuity conditions at the link point.
There are two types of curve continuities:
 Geometric
 Parametric
Geometric Continuity:
If two curve sections meet each other at a point.
If two curve sections meet each other at a point and their tangent vectors are
same at meeting point.
If every pair of the first n derivatives of the two segments has the same direction

[II.10]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

at the point.

SPLINE CURVES:
A spline curve is a mathematical representation for which it is easy to build an
interface that will allow a user to design and control the space of complex curves and

surface. The general approach is that the user enters a sequence of points and curve is
constructed
whose space closely follows the sequence. The points are called Control Points. A curve
that actually passes through each control point is called an interpolating curve, a curve that
passes near to the control points but not necessarily through them, called as an
approximating curve.
Bezier Curves:
Bezier curve is discovered by the French engineer Pierre Bezier. These curves can be
generated under the control of other points. Approximate tangents by using control point are used to
generate curve. The Bezier curve can be represented mathematically as

Where is set of control points.

represent Bernstein polynomials.

If degree of curve =n, then n+1 is the number of control points.

If n=3, 4 no of control points.
+
So

PROBLEM:
Construct the Bezier curve for following control points P0(4,2) ,P1(8,8) and P2(16,4).
ANSWER:
No of control point = 3 (n+1)
Where n is order = 3-1= 2
+
Expand in X, Y

[II.11]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

U X(U) Y(U)
0 4 2
0.2 5.76 4
0.4 7.84 5.20
0.6 10.24 5.60
0.8 12.96 5.20
1.0 16 4

P
rope
rties
of
Bezi
er
Cur
ve

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

[II.12]
COMPUTER GRAPHICS | Unit: 02
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, GIET (AUTONOMOUS), GUNUPUR
COMPUTER GRAPHICS - BCSPC7010 - 3-0-1 4

 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 Curve
The Bezier curve produced by Bernstein basic function has limited flexibility.
 The resulting polynomial is fixed by no of control point.
 The Bezier curve is a global control.
The B-Spline basic contains the Bernstein basic as a special case. The B-Spline basic is
non-global.
A B-Spline curve is defined as a linear combination of control point and B-Spline basic
function given by

Where

 is the order of polynomial segments means the curve is made up of piecewise
polynomial segments of degree K-1.
 Normalized B-Spline blending function.

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

[II.13]
COMPUTER GRAPHICS | Unit: 02