Sutherland-Hodgman Clipping

Every time a 3D game renders a frame, millions of triangles compete to appear on screen. Most of them lie partially or entirely outside the visible window. Sending those stray fragments all the way to the pixel-painting stage wastes work — and can produce corrupted pixels at the viewport boundary. The solution is clipping: trim each polygon to the viewable region before rasterizing it.

The classic tool for this job is the Sutherland-Hodgman algorithm, published by Ivan Sutherland and Gary Hodgman in 1974. Its insight is elegantly simple: instead of trying to clip a polygon against the entire window at once, clip it against one edge at a time. After four passes (left, right, top, bottom), only the intersection of the polygon and the window remains.

What makes it beautiful is the reentrant structure: the output of each clipping pass feeds directly into the next. This pipeline style maps perfectly onto hardware and onto the GPU pipelines that descended from it.

Drag the polygon (blue) across the clipping window (red dashed rectangle) and watch the algorithm trim it in real time. Use Step to advance one clipping edge at a time, or Run All to see the final result. The green shape is what survives after all four edges have clipped it.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="480" height="340"></canvas>
<div class="controls">
  <button id="step" type="button">{{btn_step}}  <span id="edgeNum">1</span>/4)</button>
  <button id="runAll" type="button">{{btn_run_all}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="info" id="info">{{info_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px;
         background: #f6f8fa; cursor: grab; width: 100%; max-width: 480px; touch-action: none; }
canvas.dragging { cursor: grabbing; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.info { font-size: .88rem; font-weight: 600; margin-top: .5rem; min-height: 1.3em; color: #1d3557; }

// Code not found

Notice how each edge processes the polygon independently: vertices inside the boundary are kept, vertices outside are discarded, and a new intersection point is inserted wherever an edge crosses the boundary. The algorithm runs in $O(n \cdot k)$ time where n is the number of polygon vertices and k is the number of clipping edges — linear in the size of the input for any fixed window shape.

Sutherland-Hodgman is a solved, efficient algorithm — not an open problem. Here is precisely what is known:

• Running time: $O(n \cdot k)$. For a polygon with n vertices and a convex clip region with k edges, each of the k passes touches every current vertex once. In practice k = 4 (the view frustum has four sides in 2-D, six planes in 3-D), so the cost is simply linear in the polygon size.
• Output size: $O(n + k)$. The clipped polygon can have at most n + k vertices (one extra intersection per clip edge), so no memory blowup occurs.
• Optimality for convex windows. Because the output can be Θ(n + k) vertices, the algorithm is asymptotically optimal — you cannot clip faster than you must write the output.
• The convex constraint matters. Sutherland-Hodgman requires the clip region to be convex. For concave (non-convex) windows it produces incorrect extra edges. The Weiler-Atherton algorithm (1977) removes this restriction at the cost of more complex bookkeeping.
• 3-D extension. Clipping against six frustum planes instead of four is a direct generalization: the same loop runs six times. Modern GPUs perform this in clip space after the perspective divide, exactly as Sutherland and Hodgman envisioned.

Unlike P vs NP or the halting problem, polygon clipping has no unsolved mystery. Its difficulty is entirely practical: doing it fast enough for millions of triangles per frame.

Polygon clipping is one of the most exercised operations in all of computing:

• Real-time 3D rendering: every GPU processes billions of triangles per second through a clipping stage that is a direct descendant of this algorithm. The OpenGL and Vulkan specifications describe clip-space polygon clipping in terms of Sutherland-Hodgman.
• 2D windowing systems: operating-system GUIs clip every window's contents to the window boundary before compositing the desktop.
• Geographic information systems (GIS): map tiles are generated by clipping feature polygons (countries, roads, lakes) to a grid of tile boundaries — a massive spatial-clipping workload.
• Surgical simulation and medical imaging: virtual scalpels clip mesh geometry in real time; clipped cross-sections reveal interior structures.
• Computational geometry libraries: Sutherland-Hodgman is the standard convex-clip primitive in CGAL, Clipper, and every game-physics engine.

The same edge-by-edge idea also underlies shadow-volume clipping, soft-body physics boundary tests, and radar/sonar zone intersections. Fifty years after its publication, the reentrant pipeline is still the fastest convex clipper we have.

Sutherland-Hodgman's core idea — pass the polygon through one clip edge at a time, in a reentrant pipeline — is one of the most durable algorithms in computer science. Published in 1974, it predates the GPU, the internet as we know it, and the personal computer. Yet every frame rendered on your screen today passes through a direct descendant of its logic.

The algorithm is solved: $O(n \cdot k)$ time, $O(n + k)$ output, optimal for convex regions. Its lesson is not about unsolved difficulty but about the power of decomposition — hard-looking geometry problems often dissolve when you break them into a sequence of simple, independent passes.

Next time a game renders a dragon that reaches past the edge of the screen, remember: an elegant 50-year-old idea quietly trims its wing before you ever see a pixel.