Problem

Given a rectangular clip window and a line segment, output the part of the line inside the window (or nothing if it lies entirely outside).

Region Codes (Outcodes)

Divide the plane into 9 regions using the 4 clip edges. Each region gets a 4-bit code: TBRL.

• Bit 0 (L): x < x_min
• Bit 1 (R): x > x_max
• Bit 2 (B): y < y_min
• Bit 3 (T): y > y_max

Inside region = 0000.

Algorithm

1. Compute outcodes c1, c2 for endpoints P1, P2.
2. If (c1 OR c2) == 0: trivially accept.
3. Else if (c1 AND c2) != 0: trivially reject.
4. Else pick a point with non-zero code, clip it against one of the violated edges, recompute outcode, loop to step 2.

Why It Works

• Bitwise AND non-zero means both points lie in the same outside half-plane -> entire line cannot intersect the window.
• Bitwise OR zero means both points are inside -> whole segment is inside.

Worked Example

Window: x in [0, 10], y in [0, 10]. Line from P1(-2, 5) to P2(8, 12).

• c1 = 0001 (left), c2 = 1000 (top). AND = 0, OR != 0 -> need clip.
• Pick P1, violates left (x = 0). Parametric x: from -2 to 8 -> t = (0 - (-2))/10 = 0.2. y = 5 + 0.2*(12-5) = 5 + 1.4 = 6.4. New P1 = (0, 6.4), c1 = 0000.
• Now c1 = 0, c2 = 1000. AND = 0, OR != 0. Pick P2, violates top. y = 10 -> t = (10-6.4)/(12-6.4) = 0.643. x = 0 + 0.643*(8-0) = 5.14. New P2 = (5.14, 10), c2 = 0000.
• Now both inside -> accept segment from (0, 6.4) to (5.14, 10).

Strengths and Limits

• Strength: Lightning-fast trivial accept/reject for the common case (most lines are entirely inside or entirely outside one half-plane).
• Limit: Requires axis-aligned rectangular window. Use Cyrus-Beck for arbitrary convex windows.