[Intermediate] — Removing everything outside the viewing window before it is drawn: point clipping, the three classes of line, Cohen–Sutherland, midpoint subdivision, Cyrus–Beck and Liang–Barsky, and extending them to a 3D frustum and to Bézier curves.

Part 1 of the course. The 3D, clip-space version of this lives in note 09 (“Clip space and NDC”) — this note is where the algorithms behind it are worked by hand.

Before you start

You can find where two lines cross, use a slope , and take a dot product.

After this note you will be able to:

  1. Compute 4-bit region codes and apply Cohen–Sutherland’s accept/reject/clip loop by hand.
  2. Clip the same line with Liang–Barsky and get the same answer.
  3. Explain Cyrus–Beck and why Liang–Barsky is its rectangular special case.
  4. Describe how to clip against a 3D frustum and how to clip a Bézier curve.

The kid version

You’re looking at a big drawing through a small window cut in a piece of card. Only what shows through the hole matters, so before you bother tracing anything, you throw away the parts outside the hole. Some lines are completely inside (keep them), some are completely off to one side (bin them without a thought), and only the ones that poke through the edge of the hole need scissors.

Where the analogy stops working. A line can pass near a corner of the window without going through it. By eye you’d spot that instantly; the algorithm may have to cut it once or twice before it can prove nothing is left.

Terms used in clipping

  1. Clipping: This is the removal of objects, lines or parts of lines that lie outside the viewing window, before the view is drawn. It saves work and guarantees only the visible part is drawn.
  2. Clipping window: This is also known as the window. This is the rectangle with edges , , , that the picture is clipped to.
  3. Region code: This is also known as an outcode. This is the 4-bit code that says which side(s) of the window a point is beyond.
  4. Trivial accept: This is keeping a whole line without calculation, because both its end points are inside.
  5. Trivial reject: This is discarding a whole line without calculation, because both end points are beyond the same edge.
  6. Parametric line: This is a line written as , so is the start, is the end, and values between are points on the segment.
  7. Outward normal: This is a vector perpendicular to a window edge, pointing out of the window.
  8. Entering / leaving: These describe whether a line, travelling from to , is crossing a window edge from outside to inside (entering) or inside to outside (leaving).

1. Point clipping

A point is kept only if it is inside the window in both directions. If either condition fails, it is removed.

Other kinds of clipping exist too: line, polygon, curve and text clipping.

2. The three classes of line

  1. Visible — both end points inside the window. Drawn as is.
  2. Non-visible — the whole line is outside. Rejected. Sufficient condition: both end points are beyond the same side (; or both ; or both ; or both ).
  3. Partially visible (the clipping case) — neither of the above. This is where an algorithm is needed.

The algorithms covered: Cohen–Sutherland, midpoint subdivision, Cyrus–Beck and Liang–Barsky.

3. Cohen–Sutherland

Step 1: region codes

The window and the lines extending its edges split the plane into 9 regions. Each gets a 4-bit code, in the order Top, Bottom, Right, Left (TBRL). A bit is 1 when the point is beyond that edge:

  1. Top is 1 if .
  2. Bottom is 1 if .
  3. Right is 1 if .
  4. Left is 1 if .
 1001 | 1000 | 1010
------+------+------
 0001 | 0000 | 0010     ← 0000 is the window itself
------+------+------
 0101 | 0100 | 0110

Step 2: the loop

  1. Compute codes , for the end points.
  2. If — both inside — accept the whole line. Stop.
  3. Else if — both beyond the same edge — reject the whole line. Stop.
  4. Otherwise (AND is 0000 but the line was not accepted) part of the line may be inside, so clip:
    1. Pick an end point that is outside (code not 0000).
    2. Find where the line crosses the edge named by a 1 bit in that code.
    3. Replace that end point with the intersection and recompute its code.
    4. Go back to step 2.

“AND = 0000” means the line may be inside, not that it is. A line can pass near a corner without entering; it gets clipped once or twice and then rejected when the new end point’s code still shows it outside.

Intersection formulas

With slope , taking an outside end point:

EdgeFixedThe other coordinate
Top
Bottom
Right
Left

Worked — window ,

LineStart codeEnd codeTestResult
(3,3) to (6,5)00000000Both 0000Accept as is
(0,0) to (1,5)01010001AND = 0001Reject
(0,4) to (6,8)00011000AND = 0000Clip

Clipping to , :

StepWhat happensResult
1Start (0,4) is Left. Cut at : New start (2, 5.33), code 0000
2End (6,8) is Top. Cut at : New end (3, 6), code 0000
3Both codes 0000Accept: (2, 5.33) to (3, 6)

Worked — window to

LineEnd pointsCodesORANDResult
1(5,5), (7,7)0000, 000000000000Visible
2(7,9), (11,4)1000, 001010100000Clipping case
3(1,5), (4,1)0001, 010001010000Clipping case → rejected

Line 2: . Top: , giving . Right: , giving . Clipped line: to . Starting from the other end point gives the same .

Line 3 is the subtle one. The conclusion “invisible” is right, but the AND test does not reject it at once (AND = 0000). The algorithm clips against Left: , , giving with code 0100. Now both end points have the Bottom bit set, so AND ≠ 0000 and it is rejected. In an exam, show that step.

Worked — several clips, window ,

LineCodesStepsResult
(−1,5) to (15,11)0001, 1010Clip Left at → (2, 6.125), 0000. Other end still 1010: clip Top at → (7, 8), 0000(2, 6.125) to (7, 8)
(0,10) to (14,−2)1001, 0110Clip Top → (2.33, 8). Clip Bottom for the other end → (9.33, 2)(2.33, 8) to (9.33, 2)
(−3,9) to (1,12)1001, 1001AND = 1001Rejected immediately

The first line shows why it is a loop: after the Left clip the line is still not accepted, because the other end point is beyond both Top and Right and needs its own clip. Recompute the code after every clip, and keep going until accept or reject. Testing bits in a different order gives the same final line.

4. Midpoint subdivision

Do Cohen–Sutherland’s accept/reject tests, but find the intersection by repeated halving instead of the slope formula. It needs only additions and division by 2 (a shift), which is why it suits hardware.

  1. Compute codes. OR = 0000 → accept. AND ≠ 0000 → reject.
  2. Otherwise find the midpoint and treat and as separate lines. Repeat on each.
  3. Stop splitting a piece when it is shorter than about a pixel — it is then a point, accepted or rejected by its own code.
  4. The visible pieces join into the clipped line; the outermost accepted end points are the clipped end points.

On Line 2 above it converges to about and — matching the slope method.

5. Cyrus–Beck

A parametric method that works for any convex window, not just rectangles. (Spelled Cyrus–Beck, not “Cyrus Back”.)

Write the line as , with and . For each window edge , take an outward normal and any point on that edge — any point on the edge, not an intersection with your line. The sign of tells you where is: outside, inside, on the edge.

The crossing is where that dot product is zero. Solving for :

Then classify each edge:

  • : entering. Keep the largest such as (start at 0).
  • : leaving. Keep the smallest such as (start at 1).
  • : parallel to that edge. Reject if the line lies outside it.
  • If , reject. Otherwise the visible part runs from to .

Stopping after finding is the usual incomplete answer. The classification into entering/leaving and the test are the algorithm.

6. Liang–Barsky

Liang–Barsky is a parametric method for rectangular windows: turn each window edge into a limit on , and the visible part is the range of that satisfies all four.

Let , , so . A point is inside when

Each of the four inequalities rearranges into . For the left edge, becomes :

kEdge
1Left
2Right
3Bottom
4Top

What tells you:

  • : parallel to that edge. If it is outside — reject. Otherwise no limit.
  • : entering. The limit is (the inequality flips when dividing by a negative).
  • : leaving. The limit is .

Steps:

  1. Compute , for the four edges.
  2. Any with → reject.
  3. .
  4. .
  5. → reject. Otherwise the clipped line is to . (Equal means it only touches the window at one point, such as a corner.)

Worked — window , , line to

, .

kEdgeType / after
1Left−6−21/3Entering
2Right684/3Leaving
3Bottom−42−1/2Entering
4Top421/2Leaving

: accept. , — the Cohen–Sutherland answer.

Two rejections (same window):

  • to : Left gives , , , so . Right gives . → reject.
  • to : , so Bottom has , . Parallel and outside → reject.

Worked — the several-clips line again: to , window , , . Ratios: Left (entering), Right (leaving), Bottom (entering), Top (leaving). , → to . Same as Cohen–Sutherland, with no repeated recomputation.

Why it is faster, and how it relates to Cyrus–Beck

Cohen–Sutherland may intersect, recompute a code and repeat several times for one line. Liang–Barsky does four divisions, keeps two numbers, and computes the end points once.

Liang–Barsky is Cyrus–Beck for an axis-aligned rectangle. The outward normals are , , , , so the dot products collapse into and : for the left edge, .

Cohen–SutherlandLiang–BarskyCyrus–Beck
WindowRectangleRectangleAny convex shape
Main tool4-bit region codes, , then , Dot products with edge normals, then ,
IntersectionsPossibly several per lineTwo, once, at the endTwo, once, at the end
Best whenMost lines are clearly in or outMany lines need clippingThe window isn’t a rectangle

Exam tip: use the method the question names (SSG 511 Q5 names Cohen–Sutherland). Liang–Barsky is the ideal way to check your answer, because it is an independent calculation of the same clipped line.

7. Clipping against a 3D view frustum

The view frustum is a truncated pyramid with six planes: left, right, bottom, top, near, far. Extend Cohen–Sutherland to 3D:

  1. Use a 6-bit region code, one bit per plane, set when the point is outside that plane.
  2. Accept if both codes are 000000; reject if their AND is not 000000.
  3. Otherwise pick an outside end point and a plane named by one of its 1 bits, and intersect. With and a plane such as : , then and follow from the same .
  4. Replace the end point, recompute its code, repeat.

It is much simpler after the perspective transformation. In the canonical view volume the planes become , , ; in homogeneous clip coordinates the test is — exactly what GPUs do → note 09. Cyrus–Beck with six planes also works, because the frustum is convex.

8. Clipping a Bézier curve against a rectangle

Use the convex-hull property (the curve always lies inside the hull of its control points) and de Casteljau splitting → note 06:

  1. If the control points’ bounding box is entirely inside the window, draw the whole curve.
  2. If it is entirely outside, discard the curve.
  3. Otherwise split at and repeat on each half.
  4. When a piece is flat enough (or about a pixel long), treat it as a straight line and clip it with Cohen–Sutherland.

Runnable check

# liang_barsky.py — run: python3 liang_barsky.py
def liang_barsky(x0, y0, x1, y1, xmin, ymin, xmax, ymax):
    dx, dy = x1 - x0, y1 - y0
    tE, tL = 0.0, 1.0
    for p, q in [(-dx, x0 - xmin), (dx, xmax - x0), (-dy, y0 - ymin), (dy, ymax - y0)]:
        if p == 0:
            if q < 0:
                return None          # parallel and outside
        elif p < 0:
            tE = max(tE, q / p)      # entering
        else:
            tL = min(tL, q / p)      # leaving
    if tE > tL:
        return None
    return (x0 + tE * dx, y0 + tE * dy), (x0 + tL * dx, y0 + tL * dy)
 
print(liang_barsky(0, 4, 6, 8, 2, 2, 8, 6))     # ((2.0, 5.33...), (3.0, 6.0))
print(liang_barsky(7, 9, 11, 4, 4, 4, 10, 8))   # ((7.8, 8.0), (10.0, 5.25))
print(liang_barsky(1, 5, 4, 1, 4, 4, 10, 8))    # None

Common pitfalls

  1. Treating AND = 0000 as “visible”. It is “maybe”.
  2. Forgetting to recompute the code after each clip.
  3. Taking as the intersection point in Cyrus–Beck. It is any point on the edge.
  4. A stray in the Cyrus–Beck denominator. It is , nothing else.
  5. Flipping the inequality the wrong way in Liang–Barsky: dividing by negative flips to , which is why entering edges give lower bounds.
  6. Garbled point-clipping conditions. Both and must hold.

Check your understanding

  1. Give the region codes for and against the window . Can the line be trivially rejected?
  2. Why does Liang–Barsky start at 0 and at 1?
  3. Why can Cyrus–Beck not clip against an L-shaped window?
Answers (after your attempt)
  1. is Top and Left: 1001. is Bottom and Right: 0110. AND = 0000, so no — it needs clipping (and here it does cross the window).
  2. The segment itself only exists for ; the edges can only shrink that range.
  3. The method relies on each edge’s inside being a half-plane and the window being their intersection — true only for convex shapes. An L-shape can make a line enter, leave and enter again.

Practice — independent tasks

  1. Exam Q5b — window from to ; five lines. Codes first, accept/reject tests, intersections only for lines that pass neither. Then check every one with the Liang–Barsky code above. → question bank
  2. Assignment B-7.5 — – and – against window –.
  3. Write cohen_sutherland(...) and show it agrees with liang_barsky on 1,000 random lines. Done when every line matches to within .

Before moving on

Next: 2D and 3D Transformations.

↑ Back to Computer Graphics