What the f*ck is Sutherland Hodgeman Polygon Clipping Algorithm? - A Complete Tutorial

The Sutherland–Hodgman algorithm is an algorithm 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 that are on the visible side.

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.

✨ A simpler version

To simplify our study of the algorithm, we will take only a rectangular window to clip the given polygon.

It is performed by processing the boundary of polygon against each window corner or edge. First of all entire polygon is clipped against one edge, then resulting polygon is considered, then the polygon is considered against the second edge, so on for all four edges.

How to clip against an edge of clipping area? The edge (of clipping area) is extended infinitely to create a boundary and all the vertices are clipped using this boundary. The new list of vertices generated is passed to the next edge of the clip polygon in clockwise fashion until all the edges have been used.

There are four possible cases for any given edge of given polygon against current clipping edge e.

1. Both vertices are inside : Only the second vertex is added to the output list

2. First vertex is outside while second one is inside : Both the point of intersection of the edge with the clip boundary and the second vertex are added to the output list

3. First vertex is inside while second one is outside : Only the point of intersection of the edge with the clip boundary is added to the output list

4. Both vertices are outside : No vertices are added to the output list

Let us consider the four cases individually.

1️⃣ The First Case

If the first vertex of the edge is outside the window and second vertex 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.

Vertex List = {v'1, v2}

2️⃣ The Second Case

If both the vertices of the edge are inside the window, then only the second vertex is added to the output vertex list.

Vertex List = {v2}

3️⃣ The Third Case

If the first vertex of the edge is inside the window and the second vertex is outside then only the intersection point of the polygon edge with the window boundary is added to the output vertex list.

Vertex List = {v'1}

4️⃣ The Fourth Case

If both vertices of the edge are outside the window. Then nothing is added to the output vertex list.

Vertex List = Φ

⛰️ Conclusion

We learnt about Sutherland Hodgeman Algorithm for Polygon Clipping in this blog. This is how it works:

Thankyou.