Polygon Clipping Background Theory

1.0 What is Polygon Clipping?

2.0 The Polygon Clipping Algorithm

    2.1 Introduction of the Sutherland-Hodgman's polygon-clipping algorithm

    2.2 The four cases of clipping a polygon to an edge

    2.3 Pseudo-code for polygon clipping using the Sutherland-Hodgman algorithm




1.0 What is Polygon Clipping?

The following diagram illustrates a simple case of the results of clipping a polygon to a clipping window.


Go back to Polygon Clipping Teaching Tool


2.0 The Polygon Clipping Algorithm

An algorithm that clips a polygon is rather complex. Each edge of the polygon must be tested against each edge of the clipping window, usually a rectangle. As a result, new edges may be added, and existing edges may be discarded, retained, or divided. Multiple polygons may result from clipping a single polygon. We need an organized way to deal with all of these cases.

Go back to Polygon Clipping Teaching Tool

2.1 Introduction of the Sutherland-Hodgman's polygon clipping algorithm

The Sutherland and Hodgman's polygon clipping algorithm is used in this tool. This algorithm is based on a divide-and-conquer strategy that 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 clipping edge. This process outputs the series of vertices that define the clipped polygon. Four clipping edges, each defining one boundary of the clipping window, are used to successively to fully clip the polygon.

Go back to Polygon Clipping Teaching Tool

2.2 The four cases of clipping a polygon to an edge

There are four cases that need to be analyzed when clipping a polygon to a single edge of the clipping window. Let us consider the polygon edge from vertex s to vertex p.

2.3 Pseudo-code for polygon clipping using the Sutherland-Hodgman's algorithm

typedef struct Vertex{
        float x,y;
        } Vertex
typedef Vertex edge[2];
typedef Vertex VertexArray[MAX]; /*MAX is a declared constant*/

Vertex *outputVertexArray PolygonClipping (Vertex *inputVertexArray)
{
        int inLength;
        edge[0] = Top_Left_Vertex_of_Clipping_Window;           /*Left edge*/
        edge[1] = Bottom_Left_Vertex_of_Clipping_Window;
        inLength = Size_of(inputVertexArray);
        SutherlandHodgmanPolygoClip (inputVertexArray,outVertexArray, 
                        inLength, outLength, edge);
        OutputToInput(inLength, inVertexArray, outLength,  outVertexArray);
        edge[0] = Bottom_Left_Vertex_of_Clipping_Window;        /*Bottom Edge*/
        edge[1] = Bottom_Right_Vertex_of_Clipping_Window;
        SutherlandHodgmanPolygoClip (inputVertexArray,outVertexArray, 
                        inLength, outLength, edge);
        OutputToInput(inLength, inVertexArray, outLength,  outVertexArray);
        edge[0] = Bottom_Right_Vertex_of_Clipping_Window;       /*Right Edge*/
        edge[1] = Top_Right_Vertex_of_Clipping_Window;
        SutherlandHodgmanPolygoClip (inputVertexArray,outVertexArray, 
                        inLength, outLength, edge);
        OutputToInput(inLength, inVertexArray, outLength,  outVertexArray);
        edge[0] = Top_Right_Vertex_of_Clipping_Window;          /*Top Edge*/
        edge[1] = Top_Left_Vertex_of_Clipping_Window;   
        SutherlandHodgmanPolygoClip (inputVertexArray,outVertexArray, 
                        inLength, outLength, edge);
        OutputToInput(inLength, inVertexArray, outLength,  outVertexArray);
        return(outVertexArray);
 }

The "SutherlandHodgmanPolygoClip" function is a critical function of the polygon clipping. It uses the Sutherland_Hodgman algorithm to implement a step in clipping a polygon to a clipping window. The code for this function is as following:

void SutherlandHodgmanPolygoClip (
    Vertex *inVertexArray ,          /*Input vertex array*/
    Vertex *outVertexArray,     /*Output vertex array*/
    int inLength,                   /*Number of entries in inVertexArray*/
    int *outLength,             /*Number of entries in outVertexArray*/
    Vertex *clipBoundary)                 /*Edge of clip polygon*/
{
    Vertex s,p,i;                     /*Start, end point of current polygon edge*/ 
    Vertex i;                    /*Intersection point with a clip boundary*/
    int j;                       /*Vertex loop counter*/
    {
        *outLength := 0;
        s= inVertexArray[inLength-1];/*Start with the last vertex in inVertexArray*/
        for (j=0; j < inLength; j++)
        {
            p := inVertexArray[j]; /*Now s and p correspond to the vertices*/
            if (Inside(p,clipBoundary))      /*Cases 1 and 4*/
            {
                 if Inside(s, clipBoundary) 
                {
                        Output(p, outLength, outVertexArray)/*Case 1*/
                }
                else                            /*Case 4*/
                {
                        Intersect(s, p, clipBoundary, i);
                        Output(i, outLength, outVertexArray);
                        Output(p, outLength, outVertexArray)
                }
            }
            else                   /*Cases 2 and 3*/
            {
                if Inside(s, clipBoundary)  /*Cases 2*/
                {
                        Intersect(s, p, clipBoundary, i);
                        Output(i, outLength, outVertexArray)
                }
           }                          /*No action for case 3*/
           s = p     /*Advance to next pair of vertices*/
      }
}      /*SutherlandHodgmanPolygonClip*/

The "OutputToInput" function sets the resulting polygon of this step up to be the input polygon for next step of the clipping algorithm. As the Sutherland-Hodgman algorithm is a polygon clipping algorithm, it does not handle line clipping very well. The modification so that lines may be clipped as well as polygons is included in this function. The code for this function is:

void OutputToInput(int inLength, Vertex *inVertexArray, int *outLength, 
                        Vertex *outVertexArray )
{ 
        if ((inLength==2) && (*outLength==3)) //linefix
        {
                inVertexArray[0].x=outVertexArray [0].x;
                inVertexArray[0].y=outVertexArray [0].y;
                if (outVertexArray[0].x==outVertexArray[1].x) /*First two vertices 
                                                                are same*/
                {
                        inVertexArray[1].x=outVertexArray [2].x;
                        inVertexArray[1].y=outVertexArray [2].y;
                }
                else                    /*First vertex is same as third vertex*/
                {
                        inVertexArray[1].x=outVertexArray [1].x;
                        inVertexArray[1].y=outVertexArray [1].y;
                }

                inLength=2;

        } 
        else  /* set the outVertexArray as inVertexArray for next step*/
        {
                inLength=*outLength;

                for (i=0; i < outLength; i++)
                {
                        inVertexArray[i].x=outVertexArray [i].x;
                        inVertexArray[i].y=outVertexArray [i].y;
                }
        }
}

The "Inside" function returns TRUE if the vertex tested is on the inside of the clipping boundary. "Inside" is defined as "to the left of clipping boundary when one looks from the first vertex to the second vertex of the clipping boundary". The code for this function is:

boolean inside (point testVertex, point *clipBoundary)
{
  if (clipBoundary[1].x > clipBoundary[0].x)              /*bottom edge*/
    if (testVertex.y >= clipBoundary[0].y) return TRUE;
  if (clipBoundary[1].x < clipBoundary[1].x)              /*top edge*/
   if (testVertex.y <= clipBoundary[0].y) return TRUE;
  if (clipBoundary[1].y > clipBoundary[0].y)              /*right edge*/
    if (testVertex.x <= clipBoundary[1].x) return TRUE;
  if (clipBoundary[1].y < clipBoundary[0].y)              /*left edge*/
    if (testVertex.x >= clipBoundary[1].x) return TRUE;
  return FALSE;
}

The "Intersect" function calculates the intersection of the polygon edge (vertex s to p) with the clipping boundary. The code for this function is:

void intersect (point first, point  second, point  *clipBoundary,
                point  *intersectPt)
{
  if (clipBoundary[0].y==clipBoundary[1].y)     /*horizontal*/
   {
     intersectPt->y=clipBoundary[0].y;
     intersectPt->x=first.x +(clipBoundary[0].y-first.y)*
                    (second.x-first.x)/(second.y-first.y);   /*Vertical*/
   } else {
           intersectPt->x=clipBoundary[0].x;
           intersectPt->y=first.y +(clipBoundary[0].x-first.x)*
                    (second.y-first.y)/(second.x-first.x);
          }
}

The "Output" function moves "newVertex" to "outVertexArray" and updates "outLength".

The code for this function is:

Void Output(Vertex newVertex, int outLength, Vertex outVertexArray : vertexArray);
{
        (outLength)++;
        outVertexArray[*outLength-1].x=newVertex.x;
        outVertexArray[*outLength-1].y=newVertex.y;
}







Author:

Huiling Yang

e-mail hxy8630@cs.rit.edu