Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Line clipping: Cohen–Sutherland algorithm

Cohen–Sutherland is a fast line-clipping algorithm that uses 4-bit region codes (outcodes) to trivially accept or reject line segments against an axis-aligned rectangular window and iteratively computes intersections when necessary.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Line clipping decides which part of a line segment lies inside a rectangular viewing window before rasterising or further processing. Engineers use Cohen–Sutherland in graphics pipelines, simple CAD viewers, and early-stage clipping before more advanced algorithms (for example, Liang–Barsky or Cyrus–Beck) are used for efficiency or non-axis-aligned windows.

Key ideas

Start from basic terms and assumptions.

  • Clipping window (clip rectangle): an axis-aligned rectangle defined by minimum and maximum coordinates (xmin, ymin) and (xmax, ymax). We assume xmin < xmax and ymin < ymax. Points on the rectangle edges are considered inside (inclusive boundaries). Note: "viewport" usually refers to the device-space rectangle used in window-to-viewport mapping; do not confuse it with the clipping window.

  • Line segment: defined by two endpoints P1(x1, y1) and P2(x2, y2).

  • Region/outcode: a 4-bit code assigned to each endpoint that describes which side(s) of the window the point lies outside of. The bits represent (from MSB to LSB): TOP (y > ymax), BOTTOM (y < ymin), RIGHT (x > xmax), LEFT (x < xmin). Conventionally assign numerical bit values: TOP = 8, BOTTOM = 4, RIGHT = 2, LEFT = 1. (Exam note: always state the bit-order you are using.)

Exact definition (how to compute outcode for a point P(x, y)):

  • Start with code = 0.
  • If x < xmin set code = code | LEFT.
  • If x > xmax set code = code | RIGHT.
  • If y < ymin set code = code | BOTTOM.
  • If y > ymax set code = code | TOP.

Key logical facts used by the algorithm:

  1. Trivial accept: If both endpoints have outcode 0 (both inside), the entire segment is inside. Formally, if outcode(P1) == 0 and outcode(P2) == 0 then accept.
  2. Trivial reject: If the bitwise logical AND of the two outcodes is non-zero, the segment lies entirely outside on the same region side and cannot cross the window. Formally, if (outcode(P1) & outcode(P2)) != 0 then reject.
  3. Otherwise, the segment may cross the window. Compute intersection with one of the window edges chosen by a set bit in an endpoint's outcode, replace that endpoint by the intersection point, recompute its outcode, and repeat. This is an iterative process guaranteed to terminate because each intersection moves an outside endpoint either into the window or to an edge (reducing the number of set bits or making it zero).

Derivation for computing intersection coordinates (what to draw in a diagram):

  • Draw XY axes, mark an axis-aligned rectangle with corners (xmin, ymin) and (xmax, ymax). Draw a line segment with endpoints P1 and P2 outside/partly inside. Label P1(x1,y1), P2(x2,y2). Mark region codes near each point, e.g., TOP|LEFT, RIGHT etc.

To compute intersection with an edge, use the parametric form of the line: draw the line and mark the intersection point I between the line and the rectangle edge you choose (top, bottom, left, or right). Use slope m where defined, or parameter t:

  • Parametric: x(t) = x1 + t*(x2 - x1), y(t) = y1 + t*(y2 - y1), 0 <= t <= 1.
  • For a vertical edge x = xedge solve for t and compute y; for a horizontal edge y = yedge solve for t and compute x.

Algorithm sketch (step-by-step, the way exam answers expect):

  1. Compute outcode1 = outcode(P1), outcode2 = outcode(P2).
  2. While true: a. If outcode1 == 0 and outcode2 == 0: accept — whole line inside; break. b. Else if (outcode1 & outcode2) != 0: reject — line trivially outside; break. c. Else: choose one endpoint with non-zero outcode (say outcode_out). Determine which boundary to intersect using the highest set bit (TOP/BOTTOM/RIGHT/LEFT). Compute intersection point I with that boundary. Replace that endpoint with I and recompute its outcode. Continue loop.

Termination and correctness notes: Each iteration replaces an outside point by its intersection with the window boundary; the number of bits set in its outcode cannot increase indefinitely, and coordinates move monotonically toward the window, so the algorithm will terminate with accept or reject. The algorithm assumes rectangular, axis-aligned window and straight line segments.

Formulas

x(t) = x1 + t * (x2 - x1) — x-coordinate along the line; unit: same as x (no SI unit). Applies for 0 <= t <= 1. y(t) = y1 + t * (y2 - y1) — y-coordinate along the line. If x = xedge then t = (xedge - x1) / (x2 - x1), y = y1 + t * (y2 - y1) — intersection with vertical edge x = xedge (requires x2 != x1). If y = yedge then t = (yedge - y1) / (y2 - y1), x = x1 + t * (x2 - x1) — intersection with horizontal edge y = yedge (requires y2 != y1). outcode(P) = (P.x < xmin ? LEFT : 0) | (P.x > xmax ? RIGHT : 0) | (P.y < ymin ? BOTTOM : 0) | (P.y > ymax ? TOP : 0) — algorithm for computing the 4-bit code. Bits: TOP=8, BOTTOM=4, RIGHT=2, LEFT=1.

Notes on special cases: If x2 == x1 (vertical line) avoid division by zero; compute intersection with horizontal boundaries by using x = x1 and check if x is within [xmin,xmax]. Similarly handle horizontal lines where y2 == y1.

Worked examples

Example 1 — numerical, step-by-step (typical exam question) Given clipping window xmin = 1, ymin = 1, xmax = 8, ymax = 6. Line endpoints P1(0, 5) and P2(10, 3).

  1. Compute outcodes:
    • P1(0,5): x < xmin so LEFT bit = 1; y between ymin and ymax so no TOP/BOTTOM. outcode1 = 0001 (1).
    • P2(10,3): x > xmax so RIGHT bit = 2; y between so outcode2 = 0010 (2).
  2. outcode1 == 0? No. outcode2 == 0? No. outcode1 & outcode2 = 1 & 2 = 0, so cannot trivially reject.
  3. Choose an endpoint with non-zero outcode (P1). outcode1 has LEFT set. Intersect line with x = xmin = 1.
    • Use formula: t = (xedge - x1) / (x2 - x1) = (1 - 0) / (10 - 0) = 1/10 = 0.1.
    • y = y1 + t*(y2 - y1) = 5 + 0.1*(3 - 5) = 5 + 0.1*(-2) = 5 - 0.2 = 4.8.
    • New P1' = (1, 4.8). Compute its outcode: inside => 0.
  4. Now outcode1' = 0, outcode2 = 2. outcode1' & outcode2 = 0 => not trivial reject. outcode2 != 0, choose P2 and intersect using RIGHT (x = xmax = 8).
    • t = (8 - x1') / (x2 - x1') = (8 - 1) / (10 - 1) = 7 / 9 ≈ 0.77777778.
    • y = y1' + t*(y2 - y1') = 4.8 + 0.77777778*(3 - 4.8) = 4.8 + 0.77777778*(-1.8) ≈ 4.8 - 1.4 = 3.4 (exactly 4.8 - (7/9)*1.8 = 4.8 - 1.4 = 3.4).
    • New P2' = (8, 3.4). Its outcode = 0.
  5. Both outcodes 0 => trivial accept. The clipped line is from (1.0, 4.8) to (8.0, 3.4). Final answer: (1.0, 4.8) to (8.0, 3.4).

Example 2 — numerical reject case Window same: xmin=1, ymin=1, xmax=8, ymax=6. Line endpoints P1(0, 7) and P2(2, 9).

  1. outcode P1: x< xmin => LEFT=1; y>ymax => TOP=8 => outcode1 = 1001 (9). outcode P2: x between, y>ymax so TOP => outcode2 = 1000 (8).
  2. outcode1 & outcode2 = 1001 & 1000 = 1000 (8) != 0 => trivial reject. The line is entirely above the window (it lies outside on the TOP side). Final answer: Rejected (no intersection).

Example 3 — C++ program (single-file) implementing Cohen–Sutherland and sample runs // File: cohen_sutherland.cpp #include <bits/stdc++.h> using namespace std;

const int INSIDE = 0; // 0000 const int LEFT = 1; // 0001 const int RIGHT = 2; // 0010 const int BOTTOM = 4; // 0100 const int TOP = 8; // 1000

int computeOutCode(double x, double y, double xmin, double ymin, double xmax, double ymax) { int code = INSIDE; if (x < xmin) code |= LEFT; else if (x > xmax) code |= RIGHT; if (y < ymin) code |= BOTTOM; else if (y > ymax) code |= TOP; return code; }

int main() { double xmin, ymin, xmax, ymax; double x1, y1, x2, y2; // Input format: xmin ymin xmax ymax x1 y1 x2 y2 if (!(cin >> xmin >> ymin >> xmax >> ymax >> x1 >> y1 >> x2 >> y2)) return 0;

double x1c = x1, y1c = y1, x2c = x2, y2c = y2;
int outcode1 = computeOutCode(x1c, y1c, xmin, ymin, xmax, ymax);
int outcode2 = computeOutCode(x2c, y2c, xmin, ymin, xmax, ymax);
bool accept = false;

while (true) {
    if ((outcode1 | outcode2) == 0) { // both inside
        accept = true;
        break;
    } else if (outcode1 & outcode2) { // logical AND != 0 => trivially outside
        break;
    } else {
        // At least one point is outside; pick it.
        int outcodeOut = outcode1 ? outcode1 : outcode2;
        double x, y;
        double dx = x2c - x1c, dy = y2c - y1c;

        if (outcodeOut & TOP) {
            // intersect with y = ymax
            double t = (ymax - y1c) / dy; // dy != 0 since TOP was set
            x = x1c + t * dx;
            y = ymax;
        } else if (outcodeOut & BOTTOM) {
            double t = (ymin - y1c) / dy;
            x = x1c + t * dx;
            y = ymin;
        } else if (outcodeOut & RIGHT) {
            double t = (xmax - x1c) / dx;
            y = y1c + t * dy;
            x = xmax;
        } else { // LEFT
            double t = (xmin - x1c) / dx;
            y = y1c + t * dy;
            x = xmin;
        }

        // Replace the outside point with intersection point
        if (outcodeOut == outcode1) {
            x1c = x; y1c = y;
            outcode1 = computeOutCode(x1c, y1c, xmin, ymin, xmax, ymax);
        } else {
            x2c = x; y2c = y;
            outcode2 = computeOutCode(x2c, y2c, xmin, ymin, xmax, ymax);
        }
    }
}

if (accept) {
    cout.setf(std::ios::fixed); cout<<setprecision(6);
    cout << "Accepted: clipped line from (" << x1c << ", " << y1c << ") to (" << x2c << ", " << y2c << ")\n";
} else {
    cout << "Rejected: line lies outside the window\n";
}
return 0;

}

Sample input 1 (matches Example 1): 1 1 8 6 0 5 10 3

Exact output 1: Accepted: clipped line from (1.000000, 4.800000) to (8.000000, 3.400000)

Sample input 2 (matches Example 2): 1 1 8 6 0 7 2 9

Exact output 2: Rejected: line lies outside the window

(Ensure you compile with a standard C++ compiler: g++ -std=c++11 cohen_sutherland.cpp -o clip)

Common mistakes

  • Forgetting to handle vertical (dx = 0) or horizontal (dy = 0) lines to avoid division by zero — program must branch instead of dividing by zero.
  • Applying trivial reject check before computing updated outcodes — do the checks on current outcodes each iteration.
  • Using equality comparisons with floating-point numbers incorrectly; allow for comparisons only when needed or print with a fixed precision.

For your exam

Types of questions produced:

  • Definitions: define clipping window, outcode, trivial accept/reject.
  • Short notes: explain Cohen–Sutherland algorithm with a diagram and complexity argument.
  • Derivations: derive formulas for intersection coordinates using parametric equations; show steps for a numeric example.
  • Numericals: given window and endpoints, compute outcodes and clipped segment (step-by-step arithmetic).
  • Programs: implement Cohen–Sutherland in C/C++ and show sample input/output.
  • Diagrams: draw the window, the line, and indicate region codes for endpoints and the intersection points.

What full-marks answers must include:

  • Clear statement of assumptions (axis-aligned rectangular window, endpoints coordinates).
  • Correct bit assignment for outcodes and the trivial accept/reject logical checks.
  • A correct step-by-step iteration showing intersections computed with right formulas and final clipped coordinates.
  • Handling of edge cases (vertical/horizontal lines) mentioned or shown in code.

Quick check

  1. What outcode bits are set for a point (9, -2) with window xmin=0, ymin=0, xmax=8, ymax=6?
  2. State the trivial reject condition using outcodes A and B.
  3. For the line with endpoints (0,5) and (10,3) and window [1,1]-[8,6], what is the clipped x-coordinate of the left intersection?

Answers: 1: RIGHT and BOTTOM => bits 2 | 4 = 6. 2: (A & B) != 0 implies trivial reject. 3: x = 1.0 (intersection at x = xmin), with y = 4.8.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?