Objectives

 

To understand the Sutherland Hodgman Clipping Algorithm

Algorithm Description

 

Generally, the operation of clipping is described as reducing a polygonal surface by removing portions of the surface which extend beyond some boundary.  The Sutherland Hodgman clipping algorithm describes a method of clipping using two polygons. The first polygon, the clipping polygon, is defined in terms of a series of edges. The second polygon, the subject polygon, is defined as a series of vertices. The subject polygon may be convex or concave whereas the clipping polygon must be convex. A polygon is convex if a line that is drawn between any two vertices defining the polygon will be contained inside the polygon.  This algorithm uses the clipping polygon to bound the subject polygon, in effect the subject polygon will be "clipped" against the clipping polygon.

 


For each edge, an infinite straight line is defined for it. The algorithm proceeds by traversing over consecutive pairs of vertices of the subject polygon, starting with the last vertex and the first vertex defining the subject polygon. The first element in the pair is defined as the starting vertex (s) and the second element is known as the ending vertex (p). Each pair of vertices is compared to the edge under consideration, and are determined to be either inside or outside the given edge. A vertex v is inside an edge if v falls on the same "side" of the edge line as another point on the clipping polygon. Outside is defined to be the opposite of inside. For each comparison with an edge, the algorithm defines certain vertices to be added to the final output. With the following definitions, there are four possibilities for a given starting vertex, ending vertex and edge.

Case 1: Both the starting vertex and ending vertex fall inside the edge.

For this case, the algorithm adds the ending vertex to the final output.



Case 2: The starting vertex is inside and the ending vertex is outside.

For this case, the algorithm computes the intersection point between the line defined by
the starting vertex and ending vertex and the edge. In this case only the computed intersection point
is added to the final output.



Case 3: Both the starting vertex and ending vertex fall outside the edge
For this case, nothing is added to the final output



Case 4: The ending vertex is inside and the starting vertex is outside.

For this case, the algorithm computes the intersection point between the line defined by the
the starting vertex and ending vertex and the edge. In this case the computed intersection point and
the ending vertex is added to the final output.


To complete the clipping operation, traverse over all edges of the clipping polygon and, when the final output is produced for a given edge, this output becomes the input for the next edge to be considered. Once all the edges have been traversed in this fashion, the final output will be the subject polygon fit within the bounds of the clipping polygon.


Pseudo Code

 

For Each Edge in clipping polygon
   create plane for edge

   For Each Vertex pair in subject polygon
      determine case number from starting vertex, ending vertex, and edge
      perform case operation
  End For Each
  update subject polygon with new vertices

End For Each

Java Implementation

public static void sutherland_hodgman_clipping(ArrayList<Point> subjectPolygon,
                                                               ArrayList<Edge> clippingPolygon)
{
    ArrayList<Edge> edges = clippingPolygon;
    ArrayList<Point> input = subjectPolygon;
    ArrayList<Point> output = new ArrayList<Point>();
    int casenum = 0;
    for(int i = 0; i < edges.size(); ++i) {
        Edge e = edges.get(i);
        Point r = edges.get( (i + 2) % edges.size()).getP1();
        Point s = input.get(input.size() - 1);
        for(int j = 0; j < input.size(); ++j) {
            Point p = input.get(j);
            if(Edge.isPointInsideEdge(e,r,p)) {
                if(Edge.isPointInsideEdge(e,r,s)) {
                    casenum = 1;
                }else{
                    casenum = 4;
                }
            } else {
                if(Edge.isPointInsideEdge(e,r,s)) {
                    casenum = 2;
                }else{
                    casenum = 3;
                }
           }
            switch (casenum) {
                case 1:
                    output.add(p);
                    break;
                case 2:
                    Point pi = e.computeIntersection(s, p);
                    output.add(pi);
                    break;
                case 3: //Do nothing
                    break;
                case 4:
                    Point pa = e.computeIntersection(s, p);
                    output.add(pa);
                    output.add(p);
                    break;
            }
            s = p;
        }//End of For
        input = (ArrayList<Point>)output.clone();
        output.clear();
    }//End of For
}


Algorithm within JHAVE

 

For a video of this visualization that will provide an overview of its use, please click the following link.
Use case video

This visualization supports three different modes.  The first of which is known as standard mode.  In this mode, the system will generate polygons to be used in the clipping algorithm.  These polygons will showcase all aspects of the algorithm.  To view the algorithm in standard mode click the following link.

Standard Mode
(Note this might take a few moments to load)
 
You will now be brought to a window with the visualization. To step through the visualization use the right and left arrows in the bottom of the window. If this is your first time viewing this visualization, we suggest disabling questions under the Options Menu. Once you feel comfortable with the algorithm, enable questions and proceed through the visualization. Once you are able to correctly answer a majority of the questions, you should proceed to the second mode of the visualization (Exercises).


Exercises

 

This visualization supports a series of exercises designed to test user understanding of the Sutherland Hodgman Clipping Algorithm.  Once you click any of the following links for a particular exercise, you will need to click in a data set that satisfies the requirements of the selected exercise. Initially the clipping polygon is selected; simply click in points in the Click Area. The window automatically will close your polygon; you can drag a point and see the resulting polygon. Use the Undo button to undo the last click. Similarly select the Subject Polygon and click in points. You can only click in up to 8 points per polygon.

The exercise list is as follows:


 Exercise Helpful Hint
 Link To Start Exercise
Give a data set where case X occurs exactly Y times during the entire operation of the algorithm. For this exercise please refer to the cases described above.

Do not try to trace the entire operation of the algorithm. Consider how a case occurs and then figure out how to multiply the case to occur several times.
Click Here
Give a data set where exactly X vertices will created/deleted. Remember that a vertex that was created for some other edge could be eliminated at some other point. Click Here
Give a data set where each case occurs exactly X times during the entire operation of the algorithm. For this exercise please refer to the cases described above.

Think about how to get each case to occur for a single edge and then create this situation for all the edges needed.
Click Here
Give a data set where for edge X all the cases will occur Y times For this exercise please refer to the cases described above.

Similar to the previous exercise except focus for only one edge
Click Here
Give a data set where for edge X cases Y1,Y2,... will occur in the specified order For this exercise please refer to the cases described above.

Just remember that the first pair of vertices considered by the algorithm for a particular edge are the last and first entered into the input generator.
Click Here
Give a data set where for edge X only cases Y1,Y2,... may occur For this exercise please refer to the cases described above.

Just make sure only these specified cases and no others occur.
Click Here
Give a subject polygon with X vertices that will have Y vertices after the operation of the algorithm Think in advance when a vertex is created and one is eliminated. Click Here

 

NOTES:
In the exercise list where and X or Y is mentioned a random value will be inserted in place of the variable.
The definition of a case in all exercises is based on the definition presented in the Algorithm Description above

Free Mode

The last mode supported by this visualization is called free mode.  In this mode, you provide a data set for the algorithm to be run against.  There are no specific requirements you are attempting to achieve.  There is still only a maximum of eight vertices per polygon.  Clicking the info tab in this mode will reveal total counts for the following: number of times each case occurred, number of vertices created and number of vertices eliminated.  This mode is designed to assist in acommplishing the exercises listed above by providing the same information that will be requested in the various exercises.  To launch the visualization in this mode click the following link.

Free Mode