Terna Engineering College

Computer Engineering Department

Program: Sem III

Course: Computer Graphics

Faculty: Prof. Ramesh Shahabade

LAB Manual
PART A
(PART A : TO BE REFFERED BY STUDENTS)

Experiment No.07
A.1 Aim:
Implement Sutherland Hodgeman polygon clipping algorithm.

A.2 Prerequisite:
1.C Language.
2.Geometric Concepts.
3.Concept of 2D basic Transformations.
4.Clipping Concepts.

A.3 Outcome:
After successful completion of this experiment students will be able
to,

Apply the transformations and clipping algorithms on graphical

objects. A.4 Theory:

The Sutherland-Hodgman algorithm clips a polygon against all edges of the

clipping region in turn.

The Sutherland - Hodgman algorithm performs a clipping of a polygon

against each window edge in turn. It accepts an ordered sequence of verices
v1, v2, v3, ..., vn and puts out a set of vertices defining the clipped polygon.
This figure represents a polygon (the large, solid,
upward
pointing arrow) before clipping has occurred.

The following figures show how this algorithm works at each edge, clipping
the polygon.

Clipping against the left side of the clip window.

Clipping against the top side of the clip window.

Clipping against the right side of the clip window.

Clipping against the bottom side of the clip window.

Four Types of Edges

As the algorithm goes around the edges of the window, clipping the
polygon, it encounters four types of edges. All four edge types are
illustrated by the polygon in the following figure. For each edge type, zero,
one, or two vertices are added to the output list of vertices that define the
clipped polygon.
The four types of edges are:

Edges that are totally inside the clip window. - add the second inside vertex
point

Edges that are leaving the clip window. - add the intersection point as a
vertex

Edges that are entirely outside the clip window. - add nothing to the vertex
output list

Edges that are entering the clip window. - save the intersection and inside
points as vertices

How To Calculate Intersections

Assume that we're clipping a polgon's edge with vertices at (x1,y1) and
(x2,y2) against a clip window with vertices at (xmin, ymin) and
(xmax,ymax).

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)

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)
The intersection of the polygon's edge with the top side of the window is:

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

ii) IY = ymax

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

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

ii) IY = ymin

Example:

The algorithm steps from vertex to vertex, adding 0, 1, or 2 vertices to the

output list at each step.

Assuming vertex A has already been processed,

Case 1 — vertex B is added to the output list

Case 2 — vertex B’ is added to the output (edge AB is clipped to AB’)

Case 3 — no vertex added (segment AB clipped out)

Case 4 — vertices A’ and B are added to the output (edge AB is clipped to

A’B)

A.5 Procedure:
Sutherland Hodgeman Algorithm

1. Input Coordinates of all vertices of the polygon

2. Input coordinates of the clipping window

3. Consider the left edge of the window

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

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 discussed earlier

6. Repeat the steps 4 and 5 for remaining edges of the clipping window.
Each time the resultant list of vertices is successively passed to
process the next edge of the clipping window

7. Stop

PART B
(PART B : TO BE COMPLETED BY STUDENTS)

Roll No.: A07 Name: Harshali Shinde

Class : S.E. A [ Comps ] Batch : A1
Date of Experiment: Date of Submission:
Grade :

B.1 Document created by the student:

#include <stdio.h>

#include <graphics.h>

#include <conio.h>

#include <math.h>

#include <process.h>

#define TRUE 1 #define FALSE 0

typedef unsigned int outcode;

outcode CompOutCode(float

x,float y); enum { TOP = 0x1,

BOTTOM = 0x2,

RIGHT = 0x4,
LEFT = 0x8

};

float xmin,xmax,ymin,ymax; void

clip(float x0,float y0,float x1,float

y1)

outcode

outcode0,outcode1,outcodeOut; int

accept = FALSE,done = FALSE;

outcode0 = CompOutCode(x0,y0);

outcode1 = CompOutCode(x1,y1);

do

if(!(outcode0|outcode1))

accept = TRUE;

done = TRUE;

else

if(outcode0 & outcode1)

done = TRUE;

else

float x,y;
outcodeOut = outcode0?outcode0:outcode1;

if(outcodeOut & TOP)

x = x0+(x1-x0)*(ymax-y0)/(y1-y0);
y = ymax;

else if(outcodeOut & BOTTOM)

x = x0+(x1-x0)*(ymin-

y0)/(y1-y0); y = ymin;

else if(outcodeOut & RIGHT)

y = y0+(y1-y0)*(xmax-

x0)/(x1-x0); x = xmax;

else

y = y0+(y1-y0)*(xmin-x0)/(x1-

x0); x = xmin;

if(outcodeOut==outcode0)

x0 = x;

y0 = y;
outcode0 = CompOutCode(x0,y0);

else

x1 = x;

y1 = y;

outcode1 = CompOutCode(x1,y1);

}while(done==FALSE);

if(accept)

line(x0,y0,x1,y1);

outtextxy(150,20,"POLYGON AFTER CLIPPING");

rectangle(xmin,ymin,xmax,ymax);

outcode CompOutCode(float x,float y)

outcode code =

0; if(y>ymax)

code|=TOP;

else if(y<ymin)

code|=BOTTOM;

if(x>xmax) code|

=RIGHT;
else if(x<xmin)

code|=LEFT;

return code;

void main( )

float x1,y1,x2,y2; /* request auto

detection */ int gdriver = DETECT,

gmode, n,poly[14],i;

clrscr( );

printf("Enter the no of sides of

polygon:"); scanf("%d",&n); printf("\

nEnter the coordinates of polygon\n");

for(i=0;i<2*n;i++)

scanf("%d",&poly[i]);

poly[2*n]=poly[0]; poly[2*n+1]=poly[1]; printf("Enter

the rectangular coordinates of clipping window\n");

scanf("%f%f%f%f",&xmin,&ymin,&xmax,&ymax);

/* initialize graphics and local variables */

initgraph(&gdriver, &gmode, "c:\\tc\\bgi");

outtextxy(150,20,"POLYGON BEFORE

CLIPPING"); drawpoly(n+1,poly);

rectangle(xmin,ymin,xmax,ymax);

getch( ); cleardevice( ); for(i=0;i<n;i++)

clip(poly[2*i],poly[(2*i)+1],poly[(2*i)

+2],poly[(2*i)+3]); getch( );

restorecrtmode( );

Output:
B.3 Observations and learning:
The Sutherland-Hodgman clipping algorithm finds the polygon that is the
intersection between an arbitrary polygon (the "subject polygon") and a
convex polygon (the "clip polygon"). It is used in computer graphics
(especially 2D graphics) to reduce the complexity of a scene being displayed
by eliminating parts of a polygon that do not need to be displayed.

B.4 Conclusion:
It is performed by processing the boundary of polygon against each window
corner or edge. First of all entire polygon is clipped against one edge, then
resulting polygon is considered, then the polygon is considered against the
second edge, so on for all four edges.
B.5 Question of Curiosity
Q.1] Implement Sutherland Hodgeman Polygon Clipping Algorithm.
ANS:

Sutherland Hodgeman Algorithm

1. Input Coordinates of all vertices of the polygon

2. Input coordinates of the clipping window
3. Consider the left edge of the window
4. Compare the vertices of each edge of the polygon , individually with
the clipping plane
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 discussed earlier
6. Repeat the steps 4 and 5 for remaining edges of the clipping window.
Each time the resultant list of vertices is successively passed to
process the next edge of the clipping window
7. Stop

Q2.] What are the advantages and disadvantages of Sutherland

Hodgeman Polygon Clipping Algorithm.
ANS:

Advantages:

1. Simplicity to implement.

2. Clips both concave & convex polygons.

3. Efficient handling of arbitrary clip regions.

Disadvantages:

1. Inefficient for a large number of vertices.

2. Requires a convex clip region.

3. May produce self-intersecting polygons.

************************