The idea: clip against one edge at a time

Only the part of a shape inside the window (the visible rectangle) should be drawn. Clipping cuts away the rest before the shape is filled. The page uses the window 4 ≤ x ≤ 16, 3 ≤ y ≤ 10 on a whole-number grid with y going up.

A window has four edges, and each edge is a straight line that splits the plane into a kept side and a thrown-away side. Clipping against one line is easy. So both methods on this page clip against one window edge at a time, and the result of one edge goes on to the next.

Four small panels, each with a vertical clip line, the kept side on the left in blue and an edge from S to P. In to in: emit P. In to out: emit the crossing point I. Out to out: emit nothing. Out to in: emit I, then P.
The four cases of Sutherland–Hodgman: each polygon edge S → P adds 1, 1, 0 or 2 vertices to the output.

Outcodes: Cohen–Sutherland for a line

The Cohen–Sutherland method gives every endpoint a 4-bit outcode, one bit per window edge, in the order top, bottom, right, left (TBRL). A bit is 1 when the point is outside that edge: top 1000 (y > 10), bottom 0100 (y < 3), right 0010 (x > 16), left 0001 (x < 4). The window itself is 0000, and the eight regions around it get the codes in the figure.

A 3 by 3 grid of regions around the window with their 4-bit outcodes: top row 1001, 1000, 1010; middle row 0001, 0000 (the window), 0010; bottom row 0101, 0100, 0110. The line P0 (1, 4) to P1 (18, 12) crosses it with codes 0001 and 1010.
Nine regions, nine outcodes. The line of the first demo starts in 0001 and ends in 1010.

Two outcodes give quick answers with plain bit operations:

  • OR = 0000: both ends are inside, so the whole line is inside. Draw it (trivial accept).
  • AND ≠ 0000: both ends are outside the same edge, so the whole line is outside. Drop it (trivial reject).
  • Otherwise: take an endpoint that is outside, take its first set bit, cut the line at that edge, move the endpoint to the cut and test again.

The line from P0 (1, 4) to P1 (18, 12) has codes 0001 and 1010. Pass 1 cuts P0 at x = 4: y = 4 + 8 · 3/17 = 5.41. Pass 2 takes P1. Its code 1010 has two bits; top comes first, so it is cut at y = 10, at (13.75, 10), which is already inside. Pass 3 sees OR = 0000 and accepts (Demo: Cohen–Sutherland, a line through the window). The cut points use y = y0 + (y1 − y0)·(x − x0)/(x1 − x0) for a vertical edge and the same with x and y swapped for a horizontal one.

AND = 0000 does not mean the line meets the window. The line from (1, 9) to (7, 13) has codes 0001 and 1000. Its cut at x = 4 lands at (4, 11), code 1000, above the window. Now AND = 1000 and the line is rejected (Demo: a line past a corner). A line wholly above the window is rejected in pass 1 with no cut, and a line wholly inside is accepted in pass 1 (Demo: trivial reject, then trivial accept).

Sutherland–Hodgman: the four cases

A polygon can't be clipped one line at a time: the cut pieces must still join into a closed shape. Sutherland–Hodgman walks round the polygon for one window edge. For each edge from S (the vertex before) to P, it writes 0, 1 or 2 points to an output list. A point on the clip line counts as inside.

SPEmitWhy
ininPthe edge stays inside
inoutIthe edge leaves: keep only where it crosses
outoutnothingthe edge is thrown away
outinI, then Pthe edge comes back in

The output list, read in order, is the clipped polygon. It goes in as the input for the next window edge. The page clips left, right, bottom, then top.

Four clippers in a row

The triangle A (1, 2), B (19, 6), C (7, 14) sticks out of all four edges. Each edge cuts off a corner and adds a vertex (Demo: clip a triangle against 4 edges):

Window edgeKeepNew pointsVerticesArea
(start)396
leftx ≥ 4I1 (4, 8), I2 (4, 2.67)488
rightx ≤ 16I3 (16, 5.33), I4 (16, 8)584
bottomy ≥ 3I5 (4, 3), I6 (5.5, 3)683.75
topy ≤ 10I7 (5, 10), I8 (13, 10)767.75

The triangle ends as the 7-gon I7 I1 I5 I6 I3 I4 I8. In general each window edge can add one vertex, so a convex n-gon can come out with up to n + 4 vertices. The points are not lost along the way: I2 (4, 2.67) is a new vertex after the left edge, and the bottom edge then throws it away.

A shape that covers the whole window ends as the window itself. The square (2, 1) to (18, 12) keeps 4 vertices through every edge, and its area goes 176 → 154 → 132 → 108 → 84 = 12 × 7. None of its own corners survive: the output is the four window corners (Demo: a polygon around the whole window).

Concave shapes: the degenerate edge

The concave ∩ shape has two legs that join above the window. The left edge cuts off its left side (74 → 58). The top edge then cuts off the bar that joins the legs, and here all four cases happen in one pass. The visible part is two separate rectangles, but Sutherland–Hodgman always outputs one list: I3 I1 B I4 I5 E F I6, 8 vertices (Demo: a concave shape leaves a degenerate edge along the top).

Left: the concave shape A to H with its bar above the window top y = 10. Right: the clipped result, two legs joined by the edge I4 to I5 along y = 10 and the edge I6 to I3 back along y = 10, drawn in red; they overlap between x = 7 and x = 12.
After the top edge the two legs are one polygon joined by edges that run along the border and back.

The edges I4 (7, 10) → I5 (12, 10) and I6 (15, 10) → I3 (4, 10) both lie on the window border and overlap from x = 7 to x = 12. They enclose no area: they are degenerate edges. The area is still right, 30 = 15 + 15. A filled polygon looks right too, because a zero-width sliver fills no pixel centre. But a program that draws the outline shows a line along the top of the window that is not in the shape. Weiler–Atherton or Vatti clipping split such a shape into its real pieces.

Back faces: winding order

Before clipping, the page computes the signed area with the shoelace formula:

a = ½ · Σ (x_i · y_(i+1) − x_(i+1) · y_i)
a > 0: vertices go counter-clockwise      a < 0: clockwise

For the triangle the three terms are −32, +224 and 0, so a = +96: counter-clockwise. In OpenGL, glFrontFace(GL_CCW) (the default) makes counter-clockwise polygons front faces. With glEnable(GL_CULL_FACE) and glCullFace(GL_BACK) the GPU drops every back face: on a closed solid those are the sides turned away from the camera, hidden anyway. The triangle (6, 4), (9, 9), (14, 5) lies wholly inside the window, but its terms 18, −81 and 26 give a = −18.5. It is clockwise, so it is culled and never clipped or filled (Demo: a clockwise triangle is a back face).

Clipping keeps the winding. Each output list visits the kept points in the same order round the shape, so the sign never flips: the triangle is +96 before and +67.75 after, the ∩ shape +74 and +30. That is why a GPU can test the winding after clipping, on the final screen positions, as the OpenGL spec does.

Where it sits in the pipeline

A GPU clips triangles in 4D clip space before the divide by w, against planes like −w ≤ x ≤ w; the near plane is shown in The Graphics Pipeline. The idea is the same as here, one plane at a time with the same four cases. A convex clipped polygon is cut back into a fan of triangles, and an n-gon gives n − 2 of them, as in Ear Clipping. Each triangle is then filled pixel by pixel, see Rasterization: Edge Functions and the Z-Buffer. A clipped line is drawn with Bresenham's Line Algorithm.

What the page leaves out

The page leaves out clipping in homogeneous coordinates and the near and far planes, guard-band clipping (GPUs mostly let the rasterizer skip pixels outside the screen), the Liang–Barsky and Cyrus–Beck line clippers that work with the parameter t, clipping against a window that is any convex polygon, Weiler–Atherton and Vatti clipping for concave windows and for splitting the result into pieces, polygons with holes, rounding errors from floating-point cut points, and front-face culling or culling turned off.

On the mind map

Open the Geometric Algorithms mind mapGeometricAlgorithmsTransform matrices: multiply each vertex by a matrixTransform matricesCoordinate frames: same point, different framesCoordinate framesHulls and curves: cross products and lerpsHulls and curvesRendering: which pixel shows whatRenderingFourier and DCT: a signal as a sum of wavesFourier and DCTTriangulations: mesh a point setTriangulationsSegments and polygons: lines, crossings, regionsSegments and polygonsRasterizationRasterizationthree edge tests per pixel, z-bufferGraphics PipelineGraphics PipelineClip before ÷w; opaque first, glass lastPolygon Clippingone window edge at a time: 0, 1 or 2 pointsTexture Mapping & MipmapsTexture Mapping & Mipmapsλ = log2 ρ picks the mipmap levelShadow MappingShadow MappingCompare depth with the light's mapRay tracingRay tracingone ray per pixel, nearest hit winsBresenham lineBresenham lineinteger error term picks the next pixelPhong shadingPhong shadingambient + diffuse N·L + specular (R·V)ⁿOpen the Geometric Algorithms mind mapGeometric Algorithmswhich pixel shows whatRenderingRasterizationRasterizationthree edge tests per pixel, z-bufferGraphics PipelineGraphics PipelineClip before ÷w; opaque first, glass lastPolygon Clippingone window edge at a time: 0, 1 or 2 pointsTexture Mapping & MipmapsTexture Mapping & Mipmapsλ = log2 ρ picks the mipmap levelShadow MappingShadow MappingCompare depth with the light's mapRay tracingRay tracingone ray per pixel, nearest hit winsBresenham lineBresenham lineinteger error term picks the next pixelPhong shadingPhong shadingambient + diffuse N·L + specular (R·V)ⁿ
This page on the Geometric Algorithms mind map · 25 pages in 7 branches · open it to see the whole map and test yourself in recall mode.