Cohen-Sutherland Line Clipping: 4-Bit Outcodes Against a Viewport

The problem: what to draw when a line runs off-screen

A viewport is a finite rectangle, but the geometry you want to draw is not. Vectors from a CAD model, roads in a GIS layer, or edges of a 3D mesh routinely extend far beyond the visible window. If you rasterize a segment that leaves the window, you waste cycles on pixels nobody sees, and worse, you can write outside your framebuffer. Clipping is the operation that replaces each segment with only the part inside the window — possibly the whole thing, possibly a shortened piece, possibly nothing.

The naive approach — intersect every line with all four window edges and sort the results — is correct but wasteful. Most segments in a real scene are entirely inside or entirely outside the window, and for those, no intersection arithmetic is needed at all. Cohen and Sutherland's insight was to spend a few integer bit operations up front to detect those easy cases (trivial accept and trivial reject), and only fall back to intersection math for the genuinely ambiguous segments that cross a boundary.

How it works: outcodes and the nine-region grid

Extend the four edges of the clip window to infinite lines. They divide the plane into nine regions: the window itself in the center, plus eight surrounding it. Each region gets a 4-bit code where each bit is a boolean answer to "is the point outside this boundary?":

• Bit 1 (top): y > y_max
• Bit 2 (bottom): y < y_min
• Bit 3 (right): x > x_max
• Bit 4 (left): x < x_min

The center window is 0000. The four corners get two bits set (e.g. top-left is 1001). Given endpoints P0 and P1 with codes C0 and C1, two tests decide almost everything:

• Trivial accept: C0 == 0 && C1 == 0 — both inside, draw the whole segment.
• Trivial reject: C0 & C1 != 0 — both endpoints share an outside bit, so the whole segment lies beyond that one boundary; discard it.

If neither holds, pick an endpoint that is outside (nonzero code), clip it to the first boundary its code names, recompute that endpoint's code, and loop.

Complexity and a worked step trace

Computing an outcode is O(1): four comparisons. Trivial accept and trivial reject are each a single bitwise operation, so the best case is O(1) with zero multiplies or divides. In the ambiguous case the loop clips against one boundary per iteration; a segment can be clipped against at most all four window edges, so the loop runs at most 4 iterations — still O(1) with a small constant. Space is O(1): two 4-bit codes. The one true cost is the intersection formula, which uses a multiply and a divide per clip.

Clip a segment from P0=(-3, 1) to P1=(4, 5) against the window x in [0,10], y in [0,6]:

window: x_min=0 x_max=10 y_min=0 y_max=6
C0 for (-3,1): x<0 -> left bit  => 0001
C1 for (4,5): inside          => 0000
C0 & C1 = 0000  (not a trivial reject)
C0 | C1 != 0    (not a trivial accept)
pick P0 (nonzero); its LEFT bit is set, clip to x=0:
  t = (0 - (-3)) / (4 - (-3)) = 3/7
  y = 1 + t*(5-1) = 1 + (3/7)*4 = 2.71
  P0' = (0, 2.71), recompute code => 0000
now C0'=0000, C1=0000 -> TRIVIAL ACCEPT
draw (0, 2.71) -> (4, 5)

Where it is used in real systems

Cohen-Sutherland is a staple of the geometry stage of rendering pipelines, where primitives must be trimmed to the view frustum or viewport before rasterization. The 2D form clips lines to the screen rectangle; the 3D generalization uses a 6-bit outcode (adding near/far planes) to reject geometry outside the view volume. Classic fixed-function GPUs and software rasterizers used exactly this logic; modern hardware clips in homogeneous clip space but keeps the same trivial-accept/reject spirit.

• 2D vector and drawing engines (canvas libraries, SVG renderers, game 2D layers) clip strokes to the drawing surface.
• GIS and mapping: trimming millions of road/boundary segments to a map tile's bounding box, where trivial reject cheaply discards off-tile lines.
• CAD and plotter drivers: pen plotters physically cannot draw off-page, so segments were clipped to the paper rectangle — the original 1967 use case was a flight simulator display.
• Windowing systems: clipping graphics to a window's client rectangle.

Because the trivial tests are integer bit operations, it stays fast even on hardware without floating-point units, which is why it long outlived its 1960s origins.

How it compares to the alternatives

The main rival is Liang-Barsky (1984). Where Cohen-Sutherland can compute an intersection, discover the clipped point is still outside another boundary, and clip again — sometimes doing wasted work on lines that are ultimately rejected — Liang-Barsky uses the parametric form P(t) = P0 + t(P1-P0), reduces the problem to four inequalities in t, and finds the entry/exit t values with at most a few divisions and no redundant intersection points. For scenes with many segments straddling the window, Liang-Barsky typically does fewer floating-point operations.

• Cyrus-Beck generalizes the parametric idea to any convex polygon via edge-normal dot products — more general, more expensive, O(n) in edge count.
• Nicholl-Lee-Nicholl (1987) is faster still for 2D rectangles by exhaustive case analysis, but only handles 2D and is trickier to implement.
• Sutherland-Hodgman solves the different problem of clipping filled polygons.

Cohen-Sutherland's tradeoff is simplicity and cheap early-out versus possible redundant intersection work. When most lines are trivially in or out, it wins; when most straddle the border, parametric methods win.

Pitfalls, failure modes, and significance

The subtleties are worth knowing:

• Trivial reject is not exhaustive. A segment can lie entirely outside the window yet cross two different extended boundaries with no shared outside bit (e.g. a corner region), so C0 & C1 == 0. Such lines pass the trivial tests and get rejected only after one or more clip iterations shorten them — a real cost, and the exact case where Liang-Barsky is more efficient.
• Boundary/degenerate handling. Choose consistent strictly-vs-equal comparisons (< vs <=) so points exactly on an edge are classified deterministically. A zero-length segment or one lying along an extended edge needs care to avoid a divide-by-zero in the intersection step.
• Order of clipping. The result is correct regardless of which boundary you clip first, but the number of iterations can differ; loop termination relies on recomputing the outcode after each clip.

Its significance is historical and pedagogical: it introduced the region-code / trivial-accept-reject pattern that recurs across graphics — frustum culling, bounding-box tests, and collision broad-phases all reuse the idea of cheap conservative rejection before exact computation. Nearly 60 years on, it remains the first clipping algorithm every graphics course teaches.

Cohen-Sutherland vs. common alternative line-clipping algorithms

Algorithm	Approach	Cost per rejected line	Best fit
Cohen-Sutherland (1967)	4-bit outcodes, region tests, clip one boundary at a time	O(1) bit AND for trivial reject; up to 4 intersect calcs otherwise	Windows most lines are fully in/out of; simple to code
Liang-Barsky (1984)	Parametric line, solve for t against 4 inequalities	One division per boundary; no wasted intersections	Many lines straddling the window; fewer float ops
Cyrus-Beck (1978)	Parametric, dot products vs. edge normals	O(n) for n convex-polygon edges	Clipping against any convex polygon, not just a rectangle
Nicholl-Lee-Nicholl (1987)	Case analysis by endpoint region, no repeated clipping	At most one clip per line, no redundant intersections	2D rectangle clipping when raw speed matters
Sutherland-Hodgman (1974)	Clips a whole polygon against each window edge	Per-vertex, per-edge; different problem (polygons)	Filling/clipping polygons, not single segments