COMPUTER GRAPHICS - Implement Sutherland Hodgeman polygon clipping algorithm.

 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: 

1. IX = xmin 
2. 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: 

1. IX = xmax 
2. 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: 

1. IX = x1 + (ymax - y1) / slope 
2. IY = ymax 

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

1. IX = x1 + (ymin - y1) / slope 
2. 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)

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

Code : 

#include<stdio.h>

#include<graphics.h>

#include<conio.h>

#include<stdlib.h>

int main()

{

int gd,gm,n,*x,i,k=0;

int w[]={220,140,420,140,420,340,220,340,220,140};//array for drawing

window

detectgraph(&gd,&gm);

initgraph(&gd,&gm,"c:\\turboc3\\bgi"); //initializing graphics

printf("Window:-");

setcolor(RED); //red colored window

drawpoly(5,w); //window drawn

printf("Enter the no. of vertices of polygon: ");

scanf("%d",&n);

x = malloc(n*2+1);

printf("Enter the coordinates of points:\n");

k=0;

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

{

printf("(x%d,y%d): ",k,k);

scanf("%d,%d",&x[i],&x[i+1]);

k++;

}

x[n*2]=x[0];

x[n*2+1]=x[1];

setcolor(WHITE);

drawpoly(n+1,x);

printf("\nPress a button to clip a polygon..");

getch();

setcolor(RED);

drawpoly(5,w);

setfillstyle(SOLID_FILL,BLACK);

floodfill(2,2,RED);

gotoxy(1,1);

printf("\nThis is the clipped polygon..");

getch();

cleardevice();

closegraph();

return 0;

}

Output : 

Observations and learning:

In this experiment we Implemented Sutherland Hodgeman polygon clipping algorithm. The user enters the coordinates of polygon to get the clipped polygon. It can also be applied to other graphical objects.

Question of Curiosity

Q1.] What are the advantages and disadvantages of Sutherland Hodgeman Polygon Clipping Algorithm.

Ans-The advantages of Sutherland-Hodgman algorithm are:

1. It is very useful for clipping polygons. It clips a polygon against all edges of

the clipping region.

2. It is easy to implement.

3. It works by extending each line of the convex clip polygon. It steps from

vertex to vertex and adds 0, 1, or 2 vertices at each step to the output list.

4. It selects only those vertices which are on the visible side of the subject

polygon.

Disadvantages of Cohen-Sutherland clipping algorithm are:

1)Clipping window region can be rectangular in shape only and no other

polygonal shaped window is allowed.

2)Edges of rectangular shaped clipping window has to be parallel to the x-axis and y-axis.

3)If end pts of line segment lies in the extreme limits i.e., one at R.H.S other at L.H.S., and on one the at top and other at the bottom (diagonally) then, even 101

Q.2] What are the three categories of line.

1. Visible

2. Not visible

3. Clipping Case