Introduction

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.

Try 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">Drag the blue polygon across the red clipping window. Use <b>Step</b> to clip one edge at a time, or <b>Run All</b> to see the final result. The green shape is what survives.</p>
<canvas id="canvas" width="480" height="340"></canvas>
<div class="controls">
  <button id="step" type="button">Step (edge  <span id="edgeNum">1</span>/4)</button>
  <button id="runAll" type="button">Run All</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="info" id="info">Drag the polygon, then step through the algorithm.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€ Sutherland-Hodgman polygon clipping demo โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Clips a subject polygon against a convex rectangular window, one edge at a
// time. The algorithm runs in O(n * k) where n = polygon vertices, k = clip edges.
//
// Clipping window (clip space coords on the 480ร—340 canvas):
const WIN = { x: 130, y: 70, w: 220, h: 200 };
const CLIP_EDGES = [
  // Each edge = {nx,ny,d}: inside half-plane is nx*x + ny*y <= d
  { nx: -1, ny:  0, d: -WIN.x },              // left   x >= WIN.x
  { nx:  1, ny:  0, d:  WIN.x + WIN.w },       // right  x <= WIN.x+WIN.w
  { nx:  0, ny: -1, d: -WIN.y },               // top    y >= WIN.y
  { nx:  0, ny:  1, d:  WIN.y + WIN.h },       // bottom y <= WIN.y+WIN.h
];
const EDGE_NAMES = ['left', 'right', 'top', 'bottom'];
const COLORS = ['#e07b39','#e0c039','#9b59b6','#27ae60'];

// โ”€โ”€ initial subject polygon (pentagon, centered on canvas) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const INIT_POLY = [
  { x: 240, y:  60 },
  { x: 320, y: 130 },
  { x: 290, y: 230 },
  { x: 190, y: 230 },
  { x: 160, y: 130 },
];
let poly = INIT_POLY.map(p => ({ ...p }));  // current clipped polygon per step
let basePoly = INIT_POLY.map(p => ({ ...p })); // drag-offset base
let currentStep = 0; // how many edges have been applied (0โ€“4)
let stages = [null, null, null, null]; // result after each edge

// โ”€โ”€ drag state โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let dragging = false, dragStart = null, polyAtDrag = null;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

function canvasPoint(e) {
  const r = canvas.getBoundingClientRect();
  const scaleX = canvas.width / r.width;
  const scaleY = canvas.height / r.height;
  const src = e.touches ? e.touches[0] : e;
  return { x: (src.clientX - r.left) * scaleX, y: (src.clientY - r.top) * scaleY };
}
function onPointerDown(e) {
  dragging = true; dragStart = canvasPoint(e);
  polyAtDrag = basePoly.map(p => ({ ...p }));
  canvas.classList.add('dragging'); e.preventDefault();
}
function onPointerMove(e) {
  if (!dragging) return;
  const pt = canvasPoint(e);
  const dx = pt.x - dragStart.x, dy = pt.y - dragStart.y;
  basePoly = polyAtDrag.map(p => ({ x: p.x + dx, y: p.y + dy }));
  resetClip(); e.preventDefault();
}
function onPointerUp() { dragging = false; canvas.classList.remove('dragging'); }
canvas.addEventListener('mousedown', onPointerDown);
canvas.addEventListener('mousemove', onPointerMove);
canvas.addEventListener('mouseup', onPointerUp);
canvas.addEventListener('touchstart', onPointerDown, { passive: false });
canvas.addEventListener('touchmove', onPointerMove, { passive: false });
canvas.addEventListener('touchend', onPointerUp);

// โ”€โ”€ Sutherland-Hodgman core โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function inside(p, e) { return e.nx * p.x + e.ny * p.y <= e.d; }
function intersect(a, b, e) {
  const dx = b.x - a.x, dy = b.y - a.y;
  const denom = e.nx * dx + e.ny * dy;
  if (Math.abs(denom) < 1e-9) return a; // parallel
  const t = (e.d - e.nx * a.x - e.ny * a.y) / denom;
  return { x: a.x + t * dx, y: a.y + t * dy };
}
function clipAgainstEdge(polygon, edge) {
  if (polygon.length === 0) return [];
  const out = [];
  for (let i = 0; i < polygon.length; i++) {
    const curr = polygon[i];
    const prev = polygon[(i + polygon.length - 1) % polygon.length];
    const currIn = inside(curr, edge);
    const prevIn = inside(prev, edge);
    if (currIn) {
      if (!prevIn) out.push(intersect(prev, curr, edge));
      out.push(curr);
    } else if (prevIn) {
      out.push(intersect(prev, curr, edge));
    }
  }
  return out;
}

function resetClip() {
  poly = basePoly.map(p => ({ ...p }));
  currentStep = 0;
  stages = [null, null, null, null];
  document.getElementById('edgeNum').textContent = '1';
  setInfo('Drag the polygon, then step through the algorithm.');
  draw();
}

function stepClip() {
  if (currentStep >= 4) { setInfo('All 4 edges applied โ€” clipping complete.'); draw(); return; }
  const result = clipAgainstEdge(poly, CLIP_EDGES[currentStep]);
  stages[currentStep] = result;
  poly = result;
  currentStep++;
  document.getElementById('edgeNum').textContent = Math.min(currentStep + 1, 4);
  if (poly.length === 0) {
    setInfo('Polygon is entirely outside the window โ€” nothing remains.');
  } else {
    setInfo(fmt('Clipped against %v% edge (%currentStep%/4). %v2%', { v: EDGE_NAMES[currentStep - 1], currentStep: currentStep, v2: currentStep < 4 ? 'Press Step for next edge.' : 'Done!' }));
  }
  draw();
}

function runAll() {
  poly = basePoly.map(p => ({ ...p }));
  currentStep = 0; stages = [null, null, null, null];
  for (let i = 0; i < 4; i++) {
    stages[i] = clipAgainstEdge(poly, CLIP_EDGES[i]);
    poly = stages[i];
    currentStep++;
  }
  document.getElementById('edgeNum').textContent = '4';
  if (poly.length === 0) setInfo('Polygon is entirely outside โ€” nothing survives.');
  else setInfo(fmt('All 4 edges applied. %length% vertices in the clipped polygon.', { length: poly.length }));
  draw();
}

function setInfo(t) { document.getElementById('info').textContent = t; }

// โ”€โ”€ drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function drawPoly(pts, fillStyle, strokeStyle, alpha) {
  if (pts.length < 2) return;
  ctx.globalAlpha = alpha;
  ctx.beginPath();
  ctx.moveTo(pts[0].x, pts[0].y);
  pts.slice(1).forEach(p => ctx.lineTo(p.x, p.y));
  ctx.closePath();
  ctx.fillStyle = fillStyle; ctx.fill();
  ctx.strokeStyle = strokeStyle; ctx.lineWidth = 2; ctx.stroke();
  ctx.globalAlpha = 1;
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // โ”€โ”€ clipping window โ”€โ”€
  ctx.setLineDash([6, 4]);
  ctx.strokeStyle = '#c0392b'; ctx.lineWidth = 2;
  ctx.strokeRect(WIN.x, WIN.y, WIN.w, WIN.h);
  ctx.setLineDash([]);
  ctx.fillStyle = 'rgba(192,57,43,0.04)';
  ctx.fillRect(WIN.x, WIN.y, WIN.w, WIN.h);
  ctx.fillStyle = '#c0392b'; ctx.font = '11px system-ui'; ctx.fillText('Clip window', WIN.x + 4, WIN.y - 6);

  // โ”€โ”€ intermediate stage outlines โ”€โ”€
  for (let i = 0; i < currentStep - 1; i++) {
    if (stages[i] && stages[i].length > 1) {
      ctx.globalAlpha = 0.22;
      ctx.beginPath();
      ctx.moveTo(stages[i][0].x, stages[i][0].y);
      stages[i].slice(1).forEach(p => ctx.lineTo(p.x, p.y));
      ctx.closePath();
      ctx.strokeStyle = COLORS[i]; ctx.lineWidth = 1.5; ctx.stroke();
      ctx.globalAlpha = 1;
    }
  }

  // โ”€โ”€ original polygon โ”€โ”€
  drawPoly(basePoly, 'rgba(52,100,173,0.18)', '#3464ad', 1);
  // dots on original vertices
  basePoly.forEach(p => {
    ctx.beginPath(); ctx.arc(p.x, p.y, 3.5, 0, 2 * Math.PI);
    ctx.fillStyle = '#3464ad'; ctx.fill();
  });

  // โ”€โ”€ clipped result โ”€โ”€
  if (currentStep > 0 && poly.length > 1) {
    drawPoly(poly, 'rgba(39,174,96,0.32)', '#1a8a52', 1);
    poly.forEach(p => {
      ctx.beginPath(); ctx.arc(p.x, p.y, 3.5, 0, 2 * Math.PI);
      ctx.fillStyle = '#1a8a52'; ctx.fill();
    });
  }

  // โ”€โ”€ edge being clipped (current step indicator) โ”€โ”€
  if (currentStep < 4) {
    const e = CLIP_EDGES[currentStep];
    ctx.save();
    ctx.strokeStyle = COLORS[currentStep]; ctx.lineWidth = 2.5; ctx.setLineDash([4, 3]);
    ctx.beginPath();
    if (e.nx !== 0) { const x = -e.d / e.nx; ctx.moveTo(x, 0); ctx.lineTo(x, canvas.height); }
    else            { const y = -e.d / e.ny; ctx.moveTo(0, y); ctx.lineTo(canvas.width, y); }
    ctx.stroke(); ctx.setLineDash([]); ctx.restore();
    ctx.fillStyle = COLORS[currentStep]; ctx.font = 'bold 11px system-ui';
    if (e.nx !== 0) ctx.fillText(fmt('next: %v%', { v: EDGE_NAMES[currentStep] }), -e.d / e.nx + 4, 20);
    else            ctx.fillText(fmt('next: %v%', { v: EDGE_NAMES[currentStep] }), 4, -e.d / e.ny - 6);
  }
}

document.getElementById('step').addEventListener('click', stepClip);
document.getElementById('runAll').addEventListener('click', runAll);
document.getElementById('reset').addEventListener('click', resetClip);
draw();
// โ”€โ”€ verification (runs silently, outputs to console) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
(function verify() {
  // Clip the test pentagon fully and check vertex count & containment
  let p = INIT_POLY.map(v => ({ ...v }));
  for (const e of CLIP_EDGES) p = clipAgainstEdge(p, e);
  const allInside = p.every(v =>
    v.x >= WIN.x - 0.5 && v.x <= WIN.x + WIN.w + 0.5 &&
    v.y >= WIN.y - 0.5 && v.y <= WIN.y + WIN.h + 0.5
  );
  console.assert(p.length === 5, fmt('expected 5 clipped verts, got %length%', { length: p.length }));
  console.assert(allInside, 'some clipped vertex is outside the window');
  console.log(fmt('SH verify: %length% verts, allInside=%allInside%', { length: p.length, allInside: allInside }));
})();
Result
Console

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โ‹…k)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.

The Real Complexity

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

  • Running time: O(nโ‹…k)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)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.

Where It Matters

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.

Conclusion

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โ‹…k)O(n \cdot k) time, O(n+k)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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sutherland-hodgman/Content licensed under CC BY-NC 4.0.