Cohen-Sutherland Line Clipping Algorithm

When rendering a scene, only the portion of it that falls inside the viewing window actually needs to be drawn anything outside should be discarded or trimmed before rendering. This process is called clipping. 

The Cohen-Sutherland algorithm is one of the earliest and most widely taught line-clipping algorithms, prized for its efficiency: it uses simple bitwise operations to quickly identify and discard lines that obviously don't need detailed processing, only doing the more expensive calculations for lines that genuinely need to be clipped.

What is Clipping?

Clipping is the process of determining which portions of a graphical primitive (a line, polygon, or other shape) lie inside a specified clipping window, and removing (or "cutting off") the portions that lie outside it. 

For line segments, clipping can result in one of three outcomes:

• The entire line lies inside the window → keep it as-is.
• The entire line lies outside the window → discard it entirely.
• The line partially crosses the window boundary → keep only the portion inside, recalculating new endpoint(s) at the boundary.

The Need for an Efficient Clipping Algorithm

A naive approach to clipping would compute the intersection of every line with every one of the four window edges, regardless of whether the line is anywhere near the window. 

This is computationally wasteful, especially in scenes with thousands of lines, most of which are either entirely inside or entirely outside the window. 

Cohen-Sutherland solves this by introducing a fast, cheap test that can immediately classify most lines without needing any intersection calculations at all.

The Clipping Window and Region Codes

The clipping window is defined by four boundaries: left (x_min), right (x_max), bottom (y_min), and top (y_max). These four boundaries divide the entire 2D plane into nine regions: the window itself (the center region) and eight surrounding regions.

Each region is assigned a unique 4-bit region code (also called an outcode), where each bit represents whether the point violates one of the four boundary conditions. 

The bits are typically ordered as: Top, Bottom, Right, Left (TBRL), read left to right as bit 4 to bit 1.

A bit is set to 1 if the corresponding condition is true, and 0 otherwise. A point with region code 0000 lies entirely inside the window.

The Nine Regions Visualized

1001 | 1000 | 1010
-----+------+-----
0001 | 0000 | 0010
-----+------+-----
0101 | 0100 | 0110

(Top-Left, Top, Top-Right / Left, Inside, Right / Bottom-Left, Bottom, Bottom-Right)

Computing the Region Code

For any point (x, y), the four bits of its region code are computed using simple comparisons:

Bit 1 (Left)   = 1 if x < xmin else 0
Bit 2 (Right)  = 1 if x > xmax else 0
Bit 3 (Bottom) = 1 if y < ymin else 0
Bit 4 (Top)    = 1 if y > ymax else 0

The Core Clipping Logic

For each line segment, the region codes of both endpoints are computed: code1 for point P1, and code2 for point P2. Three cases arise:

Case 1: Trivial Accept

If both region codes are 0000 (both endpoints inside the window):

code1 OR code2 = 0000

The entire line lies inside the window. Accept the line as-is no clipping needed.

Case 2: Trivial Reject

If the bitwise AND of the two region codes is non-zero:

code1 AND code2 ≠ 0000

This means both endpoints share at least one violated boundary in common (e.g., both points are to the left of the window, or both are above it). 

Since both points are on the same outside side of some boundary, the entire line must lie entirely on the outside of that boundary. Reject the line entirely discard it without further processing.

Case 3: Partial Clipping Required

If neither trivial accept nor trivial reject applies (i.e., code1 OR code2 ≠ 0 but code1 AND code2 = 0), the line may cross the window boundary, but isn't guaranteed to lie entirely outside it. In this case:

1. Pick one endpoint that lies outside the window (i.e., has a non-zero region code).
2. Determine which boundary to clip against, by checking the set bits of that endpoint's region code (commonly checked in order: top, bottom, right, left).
3. Compute the intersection point of the line with that boundary.
4. Replace the outside endpoint with this intersection point.
5. Recompute the region code for the new point, and repeat the entire process (this may require multiple iterations, since a line might need clipping against more than one boundary).

This loop continues until the line is either trivially accepted or trivially rejected.

Computing the Intersection Point

Given a line segment from P1(x₁, y₁) to P2(x₂, y₂), the intersection points with each of the four window boundaries are calculated using the line's slope. Let,

m = (y2 - y1) / (x2 - x1)

Intersection with the Left boundary (x = x_min):

x = xmin
y = y1 + m × (xmin - x1)

Intersection with the Right boundary (x = x_max):

x = xmax
y = y1 + m × (xmax - x1)

Intersection with the Bottom boundary (y = y_min):

y = ymin
x = x1 + (ymin - y1) / m

Intersection with the Top boundary (y = y_max):

y = ymax
x = x1 + (ymax - y1) / m

(Special care is taken for vertical lines, where m is undefined in this case, only the top/bottom intersections need to be computed, since x never changes.)

Step-by-Step Algorithm Summary

1. Compute region codes for both endpoints of the line.
2. If both codes are 0000 → trivial accept, done.
3. If the AND of both codes is non-zero → trivial reject, done.
4. Otherwise: 
   1. Choose the endpoint with a non-zero region code. 
   2. Identify the violated boundary (check bits in a fixed order). 
   3. Calculate the intersection point with that boundary. 
   4. Replace the outside endpoint with the intersection point. 
   5. Recompute its region code. 
   6. Repeat from step 2.

Properties and Advantages of Cohen-Sutherland

1. Efficiency through trivial cases: Many lines in a typical scene are either fully inside or fully outside the window, and these are resolved instantly using cheap bitwise operations, without any division or intersection math.
2. Simplicity: The region code system is easy to compute and easy to reason about, making the algorithm popular for teaching clipping concepts.
3. Limitation rectangular windows only: Cohen-Sutherland is designed specifically for rectangular clipping windows. It cannot directly handle clipping against arbitrary convex or concave polygon windows (other algorithms, like Sutherland-Hodgman, are used for polygon clipping).
4. Limitation repeated computation for complex cases: In the worst case (e.g., a line that crosses multiple boundaries before being fully clipped or rejected), the algorithm may need to loop through several iterations, recalculating intersections each time.
5. Numerically stable for axis-aligned boundaries: Since clipping boundaries are always horizontal or vertical lines, the intersection formulas are simple and avoid more complex geometric computations.

Solved Numerical Problems

Setup for All Problems

Assume the clipping window is defined by:

xmin = 10, xmax = 50, ymin = 10, ymax = 50

Problem 1

Find the region code for the point P(60, 30).

Solution:

x=60 > xmax=50 → Right bit = 1
x=60 < xmin=10? No → Left bit = 0
y=30 < ymin=10? No → Bottom bit = 0
y=30 > ymax=50? No → Top bit = 0

Region code (TBRL) = 0010

Problem 2

Find the region codes for the endpoints of the line segment from A(5, 5) to B(20, 20), and determine whether the line should be trivially accepted, trivially rejected, or requires clipping.

Solution:

For A(5, 5):

x=5 < xmin=10 → Left = 1
y=5 < ymin=10 → Bottom = 1

Code A = 0101

For B(20, 20): both x and y lie within bounds (10 ≤ 20 ≤ 50) Code B = 0000

Code A AND Code B = 0101 AND 0000 = 0000 (no trivial reject)
Code A OR Code B = 0101 OR 0000 = 0101 (not 0000, so not trivial accept)

The line requires clipping point A is outside (to the left and below), point B is inside.

Problem 3

Continuing Problem 2, clip the line from A(5, 5) to B(20, 20) against the window boundaries.

Solution:

Slope: m = (20-5)/(20-5) = 15/15 = 1

Point A's region code is 0101, meaning both the Left and Bottom boundaries are violated. By convention, check bits in order (Top, Bottom, Right, Left) Bottom is checked before Left here.

Clip against the Bottom boundary (y = y_min = 10):

y = 10
x = x1 + (ymin - y1)/m = 5 + (10-5)/1 = 5 + 5 = 10

New point A1 = (10, 10)

Recompute region code for A1(10, 10): x=10 is within [10,50], y=10 is within [10,50] → Code = 0000

Now Code(A1) AND Code(B) = 0000, Code(A1) OR Code(B) = 0000 → Trivial accept.

Clipped line: from (10, 10) to (20, 20) note that since A1 already became 0000 after a single clip, no further iteration was needed in this case.

Problem 4

Determine whether the line from C(60, 60) to D(70, 80) should be trivially rejected.

Solution:

For C(60, 60):

x=60 > xmax=50 → Right = 1
y=60 > ymax=50 → Top = 1

Code C = 1010

For D(70, 80):

x=70 > xmax=50 → Right = 1
y=80 > ymax=50 → Top = 1

Code D = 1010

Code C AND Code D = 1010 AND 1010 = 1010 (non-zero)

Trivial reject both points lie above and to the right of the window, so the entire segment lies outside. The line is discarded without further processing.

Problem 5

Clip the line from E(0, 30) to F(60, 30) against the window.

Solution:

For E(0, 30): x=0 < x_min=10 → Left=1; rest are 0 → Code E = 0001 For F(60, 30): x=60 > x_max=50 → Right=1; rest are 0 → Code F = 0010

Code E AND Code F = 0001 AND 0010 = 0000 (no trivial reject)
Code E OR Code F = 0011 (not trivial accept)

Requires clipping.

Slope: since y1 = y2 = 30, the line is horizontal, m = 0. (Use direct substitution rather than slope formula for x, since y stays constant at 30 throughout.)

Clip E against the Left boundary (x = x_min = 10):

x = 10, y = 30 (unchanged, since the line is horizontal)

New E1 = (10, 30) → Code = 0000

Clip F against the Right boundary (x = x_max = 50):

x = 50, y = 30 (unchanged)

New F1 = (50, 30) → Code = 0000

Clipped line: from (10, 30) to (50, 30) both endpoints now lie exactly on the window boundary, correctly trimming the line to fit within the window.

Problem 6 (Practice try it yourself)

Using the same window (x_min=10, x_max=50, y_min=10, y_max=50), determine the region codes for the line from G(5, 55) to H(45, 5). State whether it should be trivially accepted, trivially rejected, or requires clipping, and if clipping is required, find the first intersection point using the slope formula.

(Hint: compute the region code for each point separately first using the four boundary checks, then apply the AND/OR rules before computing any intersection.)

Conclusion

The Cohen-Sutherland algorithm remains a foundational technique in computer graphics for its elegant combination of simplicity and speed most lines are resolved instantly via bitwise region code comparisons, with the more expensive intersection math reserved only for lines that genuinely straddle the clipping window's boundary. 

Understanding its region code system and trivial accept/reject logic provides a strong foundation for studying more advanced clipping algorithms, such as Sutherland-Hodgman for polygon clipping and Liang-Barsky for parametric line clipping.