Assignment 5 (Sutherland polygon clipping)
Aim:
Implement Cohen Sutherland polygon clipping method to clip the polygon with respect the view-port and window. Use mouse click, keyboard interface
Theory:
Line Clipping – Cohen Sutherland
In computer graphics, 'line clipping' is the process of removing lines or portions of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed.
The Cohen–Sutherland algorithm is a computer graphics algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions (or a three-dimensional space into 27 regions), and then efficiently determines the lines and portions of lines that are visible in the center region of interest (the viewport).
The algorithm was developed in 1967 during flight simulator work by Danny Cohen and Ivan Sutherland
The design stage includes, excludes or partially includes the line based on where:
- Both endpoints are in the viewport region (bitwise OR of endpoints == 0): trivial accept.
- Both endpoints share at least one non-visible region which implies that the line does not cross the visible region. (bitwise AND of endpoints != 0): trivial reject.
- Both endpoints are in different regions: In case of this nontrivial situation the algorithm finds one of the two points that is outside the viewport region (there will be at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.
The numbers in the figure below are called outcodes. The outcode is computed for each of the two points in the line. The outcode will have four bits for two-dimensional clipping, or six bits in the three-dimensional case. The first bit is set to 1 if the point is above the viewport. The bits in the 2D outcode represent: Top, Bottom, Right, Left. For example the outcode 1010 represents a point that is top-right of the viewport. Note that the outcodes for endpoints must be recalculated on each iteration after the clipping occurs.
|
1001 |
1000 |
1010 |
|
0001 |
0000 |
0010 |
|
0101 |
0100 |
0110 |
Sutherland Hodgman Polygon Clipping
It is used for clipping polygons. It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon those are on the visible side.
An algorithm that clips a polygon must deal with many different cases. The case is particularly note worthy in that the concave polygon is clipped into two separate polygons. All in all, the task of clipping seems rather complex. Each edge of the polygon must be tested against each edge of the clip rectangle; new edges must be added, and existing edges must be discarded, retained, or divided. The algorithm begins with an input list of all vertices in the subject polygon. Next, one side of the clip polygon is extended infinitely in both directions, and the path of the subject polygon is traversed. Vertices from the input list are inserted into an output list if they lie on the visible side of the extended clip polygon line, and new vertices are added to the output list where the subject polygon path crosses the extended clip polygon line.
This process is repeated iteratively for each clip polygon side, using the output list from one stage as the input list for the next. Once all sides of the clip polygon have been processed, the final generated list of vertices defines a new single polygon that is entirely visible. Note that if the subject polygon was concave at vertices outside the clipping polygon, the new polygon may have coincident (i.e. overlapping) edges – this is acceptable for rendering, but not for other applications such as computing shadows.
The following example illustrate a simple case of polygon clipping
Sutherland and Hodgman's polygon-clipping algorithm uses a divide-and-conquer strategy: It solves a series of simple and identical problems that, when combined, solve the overall problem. The simple problem is to clip a polygon against a single infinite clip edge. Four clip edges, each defining one boundary of the clip rectangle, successively clip a polygon against a clip rectangle.
Note the difference between this strategy for a polygon and the Cohen-Sutherland algorithm for clipping a line: The polygon clipper clips against four edges in succession, whereas the line clipper tests the outcode to see which edge is crossed, and clips only when necessary.
Steps of Sutherland-Hodgman's polygon-clipping algorithm
- Polygons can be clipped against each edge of the window one at a time. Windows/edge intersections, if any, are easy to find since the X or Y coordinates are already known.
- Vertices which are kept after clipping against one window edge are saved for clipping against the remaining edges.
- Note that the number of vertices usually changes and will often increases.
- We are using the Divide and Conquer approach
· After clipped by the right and bottom clip boundaries.
The original polygon and the clip rectangle.
Clipping polygons would seem to be quite complex. A single polygon can actually be split into multiple polygons .The Sutherland-Hodgman algorithm clips a polygon against all edges of the clipping region in turn. The algorithm steps from vertex to vertex, adding 0, 1, or 2 vertices to the output list at each step.
The Sutherland-Hodgeman Polygon-Clipping Algorithms clips a given polygon successively against the edges of the given clip-rectangle. These clip edges are denoted with e1, e2, e3, and e4, here. The closed polygon is represented by a list of its verteces (v1 to vn; Since we got 15 verteces in the example shown above, vn = v15.).
Clipping is computed successively for each edge. The output list of the previous clipping run is used as the inputlist for the next clipping run. 1st run: Clip edge: e1; inputlist = {v1, v2, ..., v14, v15}, the given polygon
CODE :
#include <math.h>
#include <time.h>
#include <GL/glut.h>
using namespace std;
int wxmin = 200,wxmax=500,wymax=350, wymin=100;
int points[10][2];
int edge;
void init(){
glClearColor(1.0,1.0,1.0,0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0,640,0,480);
glClear(GL_COLOR_BUFFER_BIT);
}
void Draw(){
glClearColor(1.0,1.0,1.0,0.0);
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.2,0.2,1);
glBegin(GL_POLYGON);
for(int i=0; i<edge; i++)
{
glVertex2i(points[i][0],points[i][1]);
}
glEnd();
glFlush();
glColor3f(0,1,0);
glBegin(GL_LINE_LOOP);
glVertex2i(200,100);
glVertex2i(500,100);
glVertex2i(500,350);
glVertex2i(200,350);
glEnd();
glFlush();
}
int BottomCliping(int e){
float m=0;
int x=0,k=0;
int t[10][2];
for(int i=0; i<e; i++){
if(points[i][1] < wymin){
if(points[i+1][1] < wymin){
}
else if(points[i+1][1] > wymin){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
x = ((1/((y2-y1)/(x2-x1))) * (wymin - y1) )+ x1;
t[k][0] = x;
t[k][1] = wymin;
k++;
}
}
else if(points[i][1]>wymin){
if(points[i+1][1] > wymin){
t[k][0] = points[i][0];
t[k][1] = points[i][1];
k++;
}
else if(points[i+1][1] < wymin){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
x = ((1/((y2-y1)/(x2-x1))) * (wymin - y1) )+ x1;
t[k][0] = x1;
t[k][1] = y1;
k++;
t[k][0] = x;
t[k][1] = wymin;
k++;
}
}
}
cout<<"k = "<<k;
for(int i=0; i<10;i++)
{
points[i][0] = 0;
points[i][1] = 0;
}
for(int i=0; i<k;i++)
{
cout<<"\n"<<t[i][0]<<" "<<t[i][1];
points[i][0] = t[i][0];
points[i][1] = t[i][1];
}
points[k][0] = points[0][0];
points[k][1] = points[0][1];
return k;
}
int TopCliping(int e){
float m=0;
int x=0,k=0;
int t[10][2];
for(int i=0; i<e; i++){
if(points[i][1] > wymax){
if(points[i+1][1] > wymax){
}
else if(points[i+1][1] < wymax){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
x = ((1/((y2-y1)/(x2-x1))) * (wymax - y1) )+ x1;
t[k][0] = x;
t[k][1] = wymax;
k++;
}
}
else if(points[i][1]<wymax){
if(points[i+1][1] < wymax){
t[k][0] = points[i][0];
t[k][1] = points[i][1];
k++;
}
else if(points[i+1][1] > wymax){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
x = ((1/((y2-y1)/(x2-x1))) * (wymax - y1) )+ x1;
t[k][0] = x1;
t[k][1] = y1;
k++;
t[k][0] = x;
t[k][1] = wymax;
k++;
}
}
}
cout<<"k = "<<k;
for(int i=0; i<10;i++)
{
points[i][0] = 0;
points[i][1] = 0;
}
for(int i=0; i<k;i++)
{
cout<<"\n"<<t[i][0]<<" "<<t[i][1];
points[i][0] = t[i][0];
points[i][1] = t[i][1];
}
points[k][0] = points[0][0];
points[k][1] = points[0][1];
return k;
}
int leftCliping(int e){
float m=0;
int y=0, k = 0;
int t[10][2];
for(int i=0;i<e;i++)
{
if(points[i][0] < wxmin){
if(points[i+1][0] < wxmin){
cout<<"\n Test 1";
}
else if (points[i+1][0] > wxmin){
cout<<"\n Test 2";
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
y = (((y2-y1)/(x2-x1)) * (wxmin - x1) )+ y1;
t[k][0] = wxmin;
t[k][1] = y;
k++;
}
}
else if(points[i][0] > wxmin){
if(points[i+1][0] > wxmin){
t[k][0] = points[i][0];
t[k][1] = points[i][1];
k++;
}
else if(points[i+1][0] < wxmin){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
y = ((y2-y1)/(x2-x1)*(wxmin - x1)) + y1;
t[k][0] = x1;
t[k][1] = y1;
k++;
t[k][0] = wxmin;
t[k][1] = y;
k++;
}
}
}
cout<<"k = "<<k;
for(int i=0; i<10;i++)
{
points[i][0] = 0;
points[i][1] = 0;
}
for(int i=0; i<k;i++)
{
cout<<"\n"<<t[i][0]<<" "<<t[i][1];
points[i][0] = t[i][0];
points[i][1] = t[i][1];
}
points[k][0] = points[0][0];
points[k][1] = points[0][1];
return k;
}
int RightCliping(int e){
float m=0;
int y=0, k = 0;
int t[10][2];
for(int i=0;i<e;i++)
{
if(points[i][0] > wxmax){
if(points[i+1][0] > wxmax){
}
else if(points[i+1][0] < wxmax){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
y = (((y2-y1)/(x2-x1)) * (wxmax - x1) )+ y1;
t[k][0] = wxmax;
t[k][1] = y;
k++;
}
}
else if(points[i][0] < wxmax){
if(points[i+1][0] < wxmax){
t[k][0] = points[i][0];
t[k][1] = points[i][1];
k++;
}
else if(points[i+1][0] > wxmax){
float x1,x2;
float y1,y2;
x1 = points[i][0];
y1 = points[i][1];
x2 = points[i+1][0];
y2 = points[i+1][1];
y = ((y2-y1)/(x2-x1)*(wxmax - x1)) + y1;
t[k][0] = x1;
t[k][1] = y1;
k++;
t[k][0] = wxmax;
t[k][1] = y;
k++;
}
}
}
cout<<"k = "<<k;
for(int i=0; i<10;i++)
{
points[i][0] = 0;
points[i][1] = 0;
}
for(int i=0; i<k;i++)
{
cout<<"\n"<<t[i][0]<<" "<<t[i][1];
points[i][0] = t[i][0];
points[i][1] = t[i][1];
}
points[k][0] = points[0][0];
points[k][1] = points[0][1];
return k;
}
void P_C(){
Draw();
}
void goMenu(int value){
switch(value){
case 1:
edge = leftCliping(edge);
Draw();
break;
case 2:
edge = RightCliping(edge);
Draw();
break;
case 3:
edge = TopCliping(edge);
Draw();
break;
case 4:
edge = BottomCliping(edge);
Draw();
break;
}
glutPostRedisplay();
}
int main(int argc, char** argv){
cout<<"\n Enter No of edges of polygon ";
cin>>edge;
for(int i=0;i<edge;i++){
cout<<"\n Enter point "<<i<<" x space y ";
cin>>points[i][0]>>points[i][1];
}
points[edge][0] = points[0][0];
points[edge][1] = points[0][1];
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(640,480);
glutInitWindowPosition(200,200);
glutCreateWindow("Polygon Clipping");
init();
glutCreateMenu(goMenu);
glutAddMenuEntry("Left",1);
glutAddMenuEntry("Right",2);
glutAddMenuEntry("Top",3);
glutAddMenuEntry("Bottom",4);
glutAttachMenu(GLUT_RIGHT_BUTTON);
glutDisplayFunc(P_C);
glutMainLoop();
return 0;
}
Output
g++ filename.cpp -lGL -lGLU -lglut
./a.out 
FAQ 1. What is clipping?2. What do you mean by interior and exterior clipping?
3. Explain how exterior clipping is useful in multiple window environments
4. The Sutherland-Hodgman algorithm can be used to clip lines against a non rectangular boundary. What uses might this have? What modifications to the algorithm would be necessary? What restrictions would apply to the shape of clipping region?
5. Explain why Sutherland-Hodgman algorithm works only for convex clipping regions?
Comments
Post a Comment