Sutherland-Hodgeman Polygon Clipping Algorithm:-

A polygon can be clipped by processing its boundary as a whole against each window edge. This is achieved by processing all polygon vertices against each clip rectangle boundary in turn. beginning with the original set of polygon vertices, we could first clip the polygon against the left rectangle boundary to produce a new sequence of vertices. The new set of vertices could then be successively passed to a right boundary clipper, a top boundary clipper and a bottom boundary clipper, as shown in figure (l). At each step a new set of polygon vertices is generated and passed to the next window boundary clipper. This is the fundamental idea used in the Sutherland - Hodgeman algorithm.

The output of the algorithm is a list of polygon vertices all of which are on the visible side of a clipping plane. Such each edge of the polygon is individually compared with the clipping plane. This is achieved by processing two vertices of each edge of the polygon around the clipping boundary or plane. This results in four possible relationships between the edge and the clipping boundary or Plane. (See Fig. m).

1. If the first vertex of the edge is outside the window boundary and the second vertex of the edge is inside then the intersection point of the polygon edge with the window boundary and the second vertex are added to the output vertex list (See Fig. m (a)).
2. If both vertices of the edge are inside the window boundary, only the second vertex is added to the output vertex list. (See Fig. m (b)).
3. If the first vertex of the edge is inside the window boundary and the second vertex of the edge is outside, only the edge intersection with the window boundary is added to the output vertex list. (See Fig. m (c)).
4. If both vertices of the edge are outside the window boundary, nothing is added to the output list. (See Fig. m (d)).

Once all vertices are processed for one clip window boundary, the output list of vertices is clipped against the next window boundary. Going through above four cases we can realize that there are two key processes in this algorithm.

1. Determining the visibility of a point or vertex (lnside - Outside test) and
2. Determining the intersection of the polygon edge and the clipping plane.

One way of determining the visibility of a point or vertex is described here. Consider that two points A and B define the window boundary and point under consideration is V, then these three points define a plane. Two vectors which lie in that plane are AB and AV. If this plane is considered in the xy plane, then the vector cross product AV x AB has only a component given by

The sign of the z component decides the position of Point V with respect to window boundary.

If z is:

Positive - Point is on the right side of the window boundary.

Zero - Point is on the window boundary.

Negative - Point is on the left side of the window boundary.

Sutherland-Hodgeman Polygon Clipping Algorithm:-

1. Read coordinates of all vertices of the Polygon.
2. Read coordinates of the dipping 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.
6. Repeat the steps 4 and 5 for remaining edges or the clipping window. Each time the resultant list of vertices is successively passed to process the next edge of the clipping window.
7. Stop.

Example :- For a polygon and clipping window shown in figure below give the list of vertices after each boundary clipping.

Solution:- Original polygon vertices are V1, V2, V3, V4, and V5. After clipping each boundary the new vertices are as shown in figure above.

1. We can correctly clip a polygon by processing the polygon boundary as a whole against each window edge. This could be accomplished by processing all polygon vertices against each clip rectangle boundary in turn. Beginning with the initial set of polygon vertices, we could first clip the polygon against the left rectangle boundary to produce a new sequence of vertices. The new set of vertices could then be successively passed to a right boundary clipper, a bottom boundary clipper, and a top boundary clipper, as in Fig. At each step, a new sequence of output vertices is generated and passed to the next window boundary clipper.

2. There are four possible cases when processing vertices in sequence around the perimeter of a polygon. As each pair of adjacent polygon vertices is passed to a window boundary clipper, we make the following tests:

   • If the first vertex is outside the window boundary and the second vertex is inside, both the intersection point of the polygon edge with the window boundary and the second vertex are added to the output vertex list.

   • If both input vertices are inside the window boundary, only the second vertex is added to the output vertex list.

   • If the first vertex is inside the window boundary and the second vertex is outside, only the edge intersection with the window boundary is added to the output vertex list.

   • If both input vertices are outside the window boundary, nothing is added to the output list. These four cases are illustrated in Fig for successive pairs of polygon vertices.

3. Once all vertices have been processed for one clip window boundary, the output list of vertices is clipped against the next window boundary

1. We illustrate this method by processing the area in Fig. against the left window boundary. Vertices 1 and 2 are found to be on the outside of the boundary. Moving along to vertex 3, which is inside, we calculate the intersection and save both the intersection point and vertex 3. Vertices 4 and 5 are determined to be inside, and they also are saved. The sixth and final vertex is outside, so we find and save the intersection point. Using the five saved points, we would re-peat the process for the next window boundary. Implementing the algorithm as we have just described requires setting up storage for an output list of vertices as a polygon is clipped against each window boundary. We can eliminate the intermediate output vertex lists by simply clip-ping individual vertices at each step and passing the clipped vertices on to the next boundary clipper. This can be done with parallel processors or a single processor and a pipeline of clipping routines. A point (either an input vertex or a calculated intersection point) is added to the output vertex list only after it has been determined to be inside or on a window boundary by all four boundary dippers. Otherwise, the point does not continue in the pipeline. Figure shows a polygon and its intersection points with a dip window. In Fig, we illustrate the progression of the polygon vertices in Fig. through a pipeline of boundary clippers.

1. The following procedure demonstrates the pipeline clipping approach. An array, records the most recent point that was clipped for each clip-window boundary. The main routine passes each vertex p to the clipPoint routine for clipping against the first window boundary. If the line defined by endpoints p and s [boundary) crosses this window boundary, the intersection is calculated and passed to the next clipping stage. If p is inside the window, it is passed to the next clipping stage. Any point that survives clipping against all window boundaries is then entered into the output array of points. The array first Point stores for each window boundary the first point clipped against that boundary. After all polygon vertices have been processed, a closing routine clips lines defined by the first and last points clipped against each boundary.

Excellent Explaining