Cohen-Sutherland Clipping

How Cohen-Sutherland Clipping works

Cohen-Sutherland clips a line against an axis-aligned rectangle by first trying to decide the whole thing with four bits. The plane is divided into nine regions and each endpoint gets a 4-bit outcode recording which boundaries it is outside of — top, bottom, right, left. Two tests then handle most lines immediately. If both outcodes are 0000 the segment is entirely inside and is accepted whole. If the bitwise AND of the two outcodes is non-zero, both endpoints lie outside the same boundary, so the segment cannot cross the window at all and is rejected whole. Only when neither shortcut fires does the algorithm do real work: pick an endpoint with a non-zero outcode, find the first boundary it violates, compute the intersection of the line with that boundary using the slope, replace the endpoint with the intersection, recompute its outcode, and loop. Each iteration removes at least one outside bit, so the loop terminates quickly and ends in either acceptance or rejection.

Pseudocode

// Outcode bits: 1000 top, 0100 bottom, 0010 right, 0001 left
outcode(x, y):
    code = 0
    if y > yMax: code |= TOP
    if y < yMin: code |= BOTTOM
    if x > xMax: code |= RIGHT
    if x < xMin: code |= LEFT
    return code

cohenSutherland(x1, y1, x2, y2):
    c1 = outcode(x1, y1)
    c2 = outcode(x2, y2)

    loop:
        if (c1 | c2) == 0:  return ACCEPT (x1, y1, x2, y2)   // both inside
        if (c1 & c2) != 0:  return REJECT                    // same outside region

        // at least one endpoint is outside: clip it
        out = (c1 != 0) ? c1 : c2

        if out & TOP:
            x = x1 + (x2 - x1) * (yMax - y1) / (y2 - y1);  y = yMax
        else if out & BOTTOM:
            x = x1 + (x2 - x1) * (yMin - y1) / (y2 - y1);  y = yMin
        else if out & RIGHT:
            y = y1 + (y2 - y1) * (xMax - x1) / (x2 - x1);  x = xMax
        else:  // LEFT
            y = y1 + (y2 - y1) * (xMin - x1) / (x2 - x1);  x = xMin

        if out == c1:  x1 = x; y1 = y; c1 = outcode(x1, y1)
        else:          x2 = x; y2 = y; c2 = outcode(x2, y2)

Time and space complexity

Time

O(1) per line — at most four clip iterations

Space

O(1)

Every iteration clears at least one of the four outcode bits for the endpoint being clipped, so the loop cannot run more than four times regardless of how far outside the line starts.

Worked example

Window xMin = 0, xMax = 10, yMin = 0, yMax = 10. Line from A(−4, 5) to B(14, 8).

1. OutcodesA(−4,5): left of xMin → 0001. B(14,8): right of xMax → 0010.
2. Trivial testsc1 | c2 = 0011 ≠ 0, so not trivially accepted. c1 & c2 = 0000, so not trivially rejected. Must clip.
3. Clip A on LEFTx = xMin = 0. y = y1 + (y2−y1)(xMin−x1)/(x2−x1) = 5 + 3·(0−(−4))/18 = 5 + 12/18 ≈ 5.67. A becomes (0, 5.67), outcode 0000.
4. Clip B on RIGHTx = xMax = 10. Using the updated A: y = 5.67 + (8 − 5.67)(10 − 0)/(14 − 0) ≈ 5.67 + 2.33·0.714 ≈ 7.33. B becomes (10, 7.33), outcode 0000.
5. Retestc1 | c2 = 0000 → trivial accept.

The visible segment runs from (0, 5.67) to (10, 7.33). Both original endpoints were discarded; two clip iterations were enough.

Common exam mistakes

• Using OR where AND belongs. `c1 | c2 == 0` is the accept test; `c1 & c2 != 0` is the reject test. Swapping them rejects lines that clearly cross the window.
• Concluding that a non-zero OR means rejection. A line with one endpoint left and one right has OR ≠ 0 but still crosses the window — that is precisely the case needing clipping.
• Forgetting to recompute the outcode after moving an endpoint. Without it the loop either never terminates or exits with the wrong verdict.
• Clipping against all four boundaries in a fixed order regardless of the outcode. Only the violated boundaries need handling, and clipping against a boundary the point does not violate produces a point outside the segment.
• Dividing without guarding vertical or horizontal lines. x2 − x1 = 0 on a vertical line makes the RIGHT/LEFT formulas divide by zero — those boundaries can never be the violated ones for it, so order the tests accordingly.

Frequently asked questions

Related simulators