Clipping Algorithms: Lines and Polygons | Draftsbook

Geometric Pruning & Clipping

Rendering geometry that lies outside the visible display window wastes precious GPU fillrate and memory bandwidth, and can trigger out-of-bounds memory writes in framebuffers. Clipping is the computer graphics procedure that identifies geometric primitives (points, lines, polygons) intersecting the clipping boundary, preserves visible portions, and discards invisible exterior segments. In this article, we rigorously analyze two classic algorithms that form the bedrock of rendering pipelines: Cohen-Sutherland Line Clipping (utilizing 4-bit region outcodes) and Sutherland-Hodgman Polygon Clipping (utilizing boundary-by-boundary vertex pipelines).

1. Cohen-Sutherland Line Clipping Algorithm

The Cohen-Sutherland algorithm accelerates line clipping by dividing the 2D plane into 9 regions using the 4 boundaries of the rectangular clipping window: $x = xw_{\min}$, $x = xw_{\max}$, $y = yw_{\min}$, and $y = yw_{\max}$.

The 4-Bit Region Outcode (TBRL)

Every endpoint $(x, y)$ is assigned a 4-bit binary code (Outcode) where each bit is set according to spatial position:

Bit Position	Boundary	Condition	Bit Assignment
Bit 1 (MSB)	Top	y > yw_max	1 (else 0)
Bit 2	Bottom	y < yw_min	1 (else 0)
Bit 3	Right	x > xw_max	1 (else 0)
Bit 4 (LSB)	Left	x < xw_min	1 (else 0)

Fast Bitwise Tests: Trivial Accept & Reject

Trivial Accept (Bitwise OR)

Outcode(P1) | Outcode(P2) == 0000

Both endpoints lie entirely inside the clipping window. The line is rendered completely without computing intersection points.

Trivial Reject (Bitwise AND)

Outcode(P1) & Outcode(P2) != 0000

Both endpoints share an outside region (e.g. both are to the left of $xw_{\min}$). The line cannot cross the window and is discarded immediately.

Intersection Calculation

If a line cannot be trivially accepted or rejected, it is clipped against an outside boundary edge. Using the line slope $m = \frac{y_2 - y_1}{x_2 - x_1}$:

Intersection with vertical edge ($x = xw_{\min}$ or $xw_{\max}$):
y = y_1 + m \cdot (x - x_1)
Intersection with horizontal edge ($y = yw_{\min}$ or $yw_{\max}$):
x = x_1 + \frac{1}{m} \cdot (y - y_1)

The exterior endpoint is replaced by the calculated intersection, its Outcode is recomputed, and the loop repeats until trivial accept or reject occurs.

2. Sutherland-Hodgman Polygon Clipping Algorithm

Clipping a polygon is fundamentally different from clipping independent lines: clipping must produce a closed polygon with valid perimeter edges, not a disconnected set of floating segments.

The Sutherland-Hodgman Algorithm clips an arbitrary polygon against each infinite window boundary edge sequentially (Left → Right → Bottom → Top) in a pipeline architecture.

The 4 Edge-Crossing Cases

For each boundary clipper, directed edges connecting vertex $V_1$ to vertex $V_2$ are tested against the boundary line:

Case 1: In to In

Both $V_1$ and $V_2$ lie inside the boundary.

Output: V_2

Case 2: In to Out

$V_1$ is inside, $V_2$ is outside.

Output: Intersection Point (I)

Case 3: Out to Out

Both $V_1$ and $V_2$ lie outside.

Output: None

Case 4: Out to In

$V_1$ is outside, $V_2$ is inside.

Output: Intersection (I) and V_2

Part 9: Clipping Algorithms: Cohen-Sutherland Line & Sutherland-Hodgman Polygon