Sutherland-Hodgeman Polygon Clipping Algorithm

By | March 12, 2022

Sutherland-Hodgeman Polygon Clipping Algorithm

Sutherland-Hodgeman Polygon Clipping Algorithm: This algorithm was purposed by Sutherland and Hodgeman in 1974 to determine which portions of the polygon were visible within a window and clipping out the portions that are outside the window.

This algorithm accepts as input a series of polygon vertices, V1, V2, …. Vn. These vertices define polygon edges from Vi, to Vi+1 and from Vn to V1.

The algorithm clips a polygon by processing the polygon boundary as a whole against each window edge. It means all the vertices are processed for clipping against each individual clip boundary of clipping window one by one.

It means starting with the initial set of vertices, the polygon is first clipped against left window boundary and a new set of vertices is produced.

This set is given as input to next clipping boundary and the polygon is clipped against right clipping boundary to produce a new set of vertices and is then clipped against bottom and top clipping boundary to produce final set of vertices . [Left-Right-Bottom-Top]

Sutherland-Hodgeman Polygon Clipping Algorithm

Thus, at each step a new set of output vertices is generated and is passed to the next window boundary clipper.

Clipping Polygon against all four clip boundaries

When all the vertices of a given polygon are processed against any clipping side, there could be any one of the following four possibilities for a successive pair of two vertices of polygon:

Case 1: out → in :

If the starting vertex is outside the window boundary and ending vertex is inside then we preserve or save both point of intersection of polygon edge with window boundary and ending vertex in the output vertex list.

Case 2 : in → in :

If both the starting and ending vertices are inside the window boundary then only the ending vertex is preserved or saved in output vertex list.

Four cases of polygon clipping

Case 3: in → out :

If the starting vertex is inside the window and ending vertex is outside then only the point of intersection of polygon edge with window boundary is saved in output list.

Case 4: out → out :

If both the starting and ending vertices are outside the window boundary then nothing is added or saved in the output vertex list.

Case Output
Out → In A’ B [2 Vertices, Point of intersect with window and ending edge]
In → In C [1 ending vertex ]
In → Out D’ [Point of intersect with window]
Out → Out N/A [Nothing is included]

Example of Sutherland-Hodgeman Polygon Clipping Algorithm

Let us consider a polygon with vertices P1, P2, P3, P4, P5. Inside in a viewing window. Applying Sutherland-Hodgeman Polygon Clipping Algorithm on this polygon, we get:

Example of polygon clipping

Clipping polygon engaged left window boundary:

Here the input vertex list is P1, P2, P3, P4 P5 and the edges are P1P2, P2P3, P3P4, P4P5 and P5P1. Now, consider all the edge with respect to (w.r.t.) left window boundary.

using left clipper
Edge Type Output
P1P2 Out → In P1’P2
P2P3 In → In P3
P3P4 In → In P4
P4P5 In → In P5
P5P1 In → Out P5′

Clipping polygon engaged right window boundary:

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be no changes because all edges lies inside the right clipping window.

using right clipper
Edge Type Output
P1’P2 In → In ‘P2
P2P3 In → In P3
P3P4 In → In P4
P4P5 In → In P5
P5P5′ In → In P5′
P5’P1′ In → In P1′

Clipping polygon engaged bottom window boundary:

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5 and P5P5′. Now, consider all the edge with respect to (w.r.t.) bottom window boundary.

using bottom clipper
Edge Type Output
P1’P2 In → In P2
P2P3 In → In P3
P3P4 In → In P4
P4P5 In → Out P4′
P5P5′ Out → Out N/A
P5’P1′ Out → In P5”

Clipping polygon engaged top window boundary:

Here the input vertex list is P1′, P2, P3, P4, P4′, P5” and the edges are P1’P2, P2P3, P3P4, P4P4′, P4’P5” and P5”P1. Now, consider all the edge with respect to (w.r.t.) top window boundary. Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be no changes because all edges lies inside the top clipping window.

using top clipper
Edge Type Output
P1’P2 In → In P2
P2P3 In → In P3
P3P4 In → In P4
P4P4′ In → In P4′
P4’P5” In → In P5”
P5”P1′ In → In P1′

Final output using Sutherland-Hodgeman Polygon Clipping Algorithm will be:

Final output using Sutherland-Hodgeman Polygon Clipping Algorithm

Vertex list produced by various clippers - Sutherland Hodgeman Clipping Algorithm

Limitations of Sutherland-Hodgeman Polygon Clipping Algorithm

  1. In some concave polygons, the theorem creates extra edges while clipping.

Concave polygon not clipped corrects

Related posts:-