Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 50 ยท Clipping

Cohen-Sutherland Line Clipping

Learn the Cohen-Sutherland line clipping algorithm: region outcodes, trivial accept and reject, iterative clipping, with a live step-by-step clipper.

A scene is usually bigger than the part you can see. A map of the world has far more roads than fit on a phone screen; a game level extends in every direction around the player. Drawing everything and letting the screen throw away the invisible parts wastes time, and in some systems it is not even safe, because coordinates outside the drawing surface can wrap around or corrupt memory. Clipping is the process of cutting a shape down to the part inside a clip region, so only visible geometry is drawn.

In this chapter the clip region is a rectangle, called the clip window, and the first primitive is the line segment. The Cohen-Sutherland algorithm, from the 1960s, is the classic solution. Its trick is to settle most lines with a few cheap bit operations and only do arithmetic for the lines that really cross the boundary.

The problem

Given a segment from P0 = (x0, y0) to P1 = (x1, y1) and a rectangle with xmin, xmax, ymin, ymax, find the part of the segment that lies inside the rectangle, or report that there is none. There are three possible situations:

  1. Fully inside: both endpoints are inside. Draw the line unchanged.
  2. Fully outside: the whole segment is outside. Draw nothing.
  3. Partly inside: the segment crosses the border. Compute the intersection points and draw only the inside portion.

A brute-force approach would intersect every segment with all four rectangle sides, which is slow when most lines are clearly inside or clearly outside. Cohen and Sutherland found a fast way to tell the easy cases apart.

Region codes

The four infinite lines x = xmin, x = xmax, y = ymin and y = ymax cut the plane into nine regions: the clip window in the middle and eight regions around it. Give every region a 4-bit outcode, with one bit for each side that the point is beyond:

Bit Name Set when
1 (0001) LEFT x < xmin
2 (0010) RIGHT x > xmax
4 (0100) BOTTOM y > ymax (screen coordinates, y grows downward)
8 (1000) TOP y < ymin (screen coordinates)

We use screen coordinates here, so "top" means a smaller y. If you work with y pointing up, the TOP and BOTTOM tests swap. The code is the same; only the comparisons flip. Inside the window the code is 0000. The corner regions combine two bits, for example top-left is 1001.

TEXT
 1001 | 1000 | 1010        TOP row    (y < ymin)
------+------+------
 0001 | 0000 | 0010        middle row (window in the center)
------+------+------
 0101 | 0100 | 0110        BOTTOM row (y > ymax)
 LEFT   inside  RIGHT

An outcode takes four comparisons and no multiplications:

JavaScript
const LEFT = 1, RIGHT = 2, BOTTOM = 4, TOP = 8;

function outcode(x, y, r) {
  let code = 0;
  if (x < r.xmin) code |= LEFT;
  else if (x > r.xmax) code |= RIGHT;
  if (y < r.ymin) code |= TOP;
  else if (y > r.ymax) code |= BOTTOM;
  return code;
}

Trivial accept and reject

Compute the outcodes c0 and c1 of the two endpoints. Two bitwise tests then decide many cases right away:

  • Trivial accept: (c0 | c1) == 0. If the bitwise OR is zero, neither endpoint has any bit set, so both are inside, and so is the whole segment (a rectangle is convex).
  • Trivial reject: (c0 & c1) != 0. If the bitwise AND is non-zero, both endpoints are beyond the same side, for example both are to the left of xmin. The segment cannot reach the window.

If neither test succeeds the segment is undecided: it might cross the window, or it might pass around a corner and miss it. Both end up being treated the same way: cut off the part that is clearly outside and test again.

flowchart TD
  S["Compute outcodes c0 and c1"] --> A{"c0 OR c1 = 0 ?"}
  A -->|"yes"| ACC["Accept: draw the segment"]
  A -->|"no"| R{"c0 AND c1 != 0 ?"}
  R -->|"yes"| REJ["Reject: draw nothing"]
  R -->|"no"| C["Pick an endpoint that is outside,<br/>move it to a border line"]
  C --> S

The loop of the algorithm. Each pass either decides the line or shortens it.

Clipping an undecided segment

When a segment is undecided, at least one endpoint is outside. Choose such an endpoint (take the first one with a non-zero code). Its outcode tells you which border to clip against: test the bits in a fixed order, for instance TOP, BOTTOM, RIGHT, LEFT. For the chosen border compute where the segment's line meets it, using the line equation. With dx = x1 - x0 and dy = y1 - y0:

TEXT
Crossing y = ymin or y = ymax:   x = x0 + dx * (y_border - y0) / dy
Crossing x = xmin or x = xmax:   y = y0 + dy * (x_border - x0) / dx

Replace the outside endpoint by the intersection point and recompute its outcode. Then go back to the top of the loop. Each iteration clears at least one bit of the moved endpoint's code, so after at most four iterations the loop ends with an accept or a reject.

There is no division by zero. To use the formula for a horizontal border (TOP or BOTTOM), the endpoint lies beyond that border, and if the segment were horizontal (dy = 0) the other endpoint would be beyond the same border, so the trivial reject would have fired before. The same holds for vertical borders.

A worked example

Window: xmin = 10, xmax = 90, ymin = 10, ymax = 70. Segment from P0 = (0, 40) to P1 = (100, 60).

  • Outcodes: P0 is left of the window (0001), P1 is right of the window (0010). The OR is 0011, not zero. The AND is 0000. The segment is undecided.
  • Take P0, whose code says LEFT. Border x = 10: y = 40 + 20 * (10 - 0) / 100 = 42. New P0 = (10, 42), code 0000.
  • Next pass: codes 0000 and 0010. Still undecided. Take P1, LEFT is not set, but RIGHT is. Border x = 90: y = 40 + 20 * (90 - 0) / 100 = 58. New P1 = (90, 58), code 0000.
  • Next pass: both codes zero, so accept: the visible part runs from (10, 42) to (90, 58).

The algorithm in code

The function below returns the clipped segment, or null if nothing is visible. It also records every step, which is useful for teaching and debugging. The loop is the algorithm described above, nothing more.

JavaScript
function clipLine(x0, y0, x1, y1, r, steps) {
  let c0 = outcode(x0, y0, r), c1 = outcode(x1, y1, r);
  while (true) {
    if ((c0 | c1) === 0) return [x0, y0, x1, y1];     // trivial accept
    if (c0 & c1) return null;                          // trivial reject
    const out = c0 || c1;                              // an endpoint that is outside
    let x, y;
    if (out & TOP)         { x = x0 + (x1 - x0) * (r.ymin - y0) / (y1 - y0); y = r.ymin; }
    else if (out & BOTTOM) { x = x0 + (x1 - x0) * (r.ymax - y0) / (y1 - y0); y = r.ymax; }
    else if (out & RIGHT)  { y = y0 + (y1 - y0) * (r.xmax - x0) / (x1 - x0); x = r.xmax; }
    else                   { y = y0 + (y1 - y0) * (r.xmin - x0) / (x1 - x0); x = r.xmin; }
    if (out === c0) { x0 = x; y0 = y; c0 = outcode(x0, y0, r); }
    else            { x1 = x; y1 = y; c1 = outcode(x1, y1, r); }
  }
}

The next demo clips a set of lines against a rectangle. Grey dashed lines are the originals, solid red lines are the clipped results, and the table shows the endpoint outcodes and the verdict. Click anywhere on the canvas to set the start and then the end of an extra line (the blue one) and watch it classified live.

A live Cohen-Sutherland clipper

Look at line E: it starts below-left of the window and ends inside. Its first code is 0101 (bottom and left), and the algorithm clips against the bottom border first, then against the left border, ending with an accept. Lines B and F are rejected immediately, and line A is accepted without a single multiplication.

Seeing the iterations

The second demo shows the loop step by step. Press Next step to run one iteration of the algorithm on a line that needs several cuts. The log shows the outcodes before every decision and which border the algorithm clips against.

Step through the algorithm

The line starts below and to the left of the window and ends above and to the right. It takes two cuts for each end: the first cut often lands on an extended border line outside the actual window edge, so the new endpoint still has a non-zero code. That is the price of the cheap approach, and why the algorithm loops.

Strengths and weaknesses

  • Fast for the common cases. When most lines are clearly inside or clearly outside, as in a zoomed-in view of a large drawing, nearly every line is settled with two bitwise operations.
  • Easy to extend. The same outcode idea works for 3D clip volumes with six bits, and it is the basis of the clip tests in many pipelines. See the rasterization pipeline.
  • Can do redundant work. An undecided line may be cut several times, and intermediate intersection points that land outside the window are wasted. A line that passes by a corner needs up to four cuts before the reject appears.
  • Rectangles only. The algorithm assumes an axis-aligned rectangular window. A different method, Liang-Barsky, uses the parametric form of the line to avoid recomputing intersections and is usually faster.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A segment has endpoint outcodes 0001 and 0101. What does Cohen-Sutherland do?

    Both endpoints have the LEFT bit set, so the AND is non-zero. Both are left of the window and the line cannot enter it.
  2. 2. When is a segment trivially accepted?

    An OR of zero means neither endpoint has any outside bit, so both lie inside the (convex) window and so does the segment.
  3. 3. What is the outcode of a point that is above and to the right of the window (in screen coordinates, y down)?

    TOP (1000) plus RIGHT (0010) gives 1010.
  4. 4. Why does the algorithm repeat its loop?

    The intersection with an extended border line may still lie outside the window edge on another side. Recomputing the outcode and testing again resolves this, in at most four passes.
  5. 5. Why is there no division by zero when computing x = x0 + dx * (ymin - y0) / dy?

    If dy were 0 and an endpoint were beyond the top or bottom border, the other endpoint would be beyond it too, so the AND test rejects the segment before the division is reached.

Summary

  • Clipping removes the invisible part of a primitive; the clip window is an axis-aligned rectangle.
  • Each endpoint gets a 4-bit outcode (LEFT, RIGHT, BOTTOM, TOP). OR equal to zero means trivial accept; AND not zero means trivial reject.
  • Otherwise move an outside endpoint to a border using the line equation, recompute its code and repeat, for at most four passes.
  • The algorithm is quick when most lines are decided by the bit tests, but may compute redundant intersections.

Next, we look at a parametric alternative: Liang-Barsky Line Clipping.