Skip to content

15. Clipping - 2

Dated: 13-05-2025

Polygon Clipping

Sutherland-hodgman's Polygon-clipping Algorithm

This algorithm uses divide and conquer design.

Notes

  • Polygons are clipped against each edge of the window at a time.
  • Vertices which are clipped, are saved for clipping against other window edges.
  • Number of vertices will often change.
  • Using divide and conquer approach.

Cases of Polygon Clipping against One Edge

  • Both vertices of the edge are fully inside the visible region.
  • Both vertices of the edge are fully outside the visible region.
  • One vertex is inside the visible region and the edge exits.
  • One vertex is outside the visible region and the edge enters.

Pipeline Clipping Approach

Vertices are clipped against each window boundary in sequence.
For each vertex, intersections are calculated and passed along if the edge crosses a boundary; points inside are passed directly.
Surviving points are added to the output.
Arrays s and firstPoint track the last and first clipped points for each boundary, with a final step to close the polygon.

Shortcoming of Sutherlands -hodgeman Algorithm

The Sutherland-Hodgman algorithm clips convex polygons correctly but can produce extraneous lines for concave polygons, as it always connects the last and first vertices.
Solutions include splitting concave polygons into convex parts, checking for multiple intersections along boundaries, or using more advanced algorithms like Weiler-Atherton.

Weiler-atherton Polygon Clipping

The Weiler-Atherton algorithm modifies vertex processing to correctly clip concave polygons by following either polygon edges or window boundaries, based on vertex direction (clockwise/counterclockwise) and whether vertices go from outside to inside or vice versa.
This allows accurate clipping for arbitrary regions and was designed for visible surface detection.