Clipping Algorithms in Computer Graphics: Cohen-Sutherland, Liang-Barsky and Polygon Worked Examples

A clipping problem asks which part of a point, line or polygon survives a rectangular window. Cohen-Sutherland assigns outcodes, Liang-Barsky tightens a parameter interval, and Sutherland-Hodgman updates a polygon's vertex list. Their results can be checked against the same coordinate window.

Clipping algorithms: window, viewport and the decision

Clipping removes the portion of a geometric primitive outside a world-coordinate clip window. A viewport is the display area to which the survivor may be mapped later, so clipping and viewport mapping are separate operations.

Point clipping is an inside test: (2, 6) lies on the boundary and survives, while (1, 6) lies outside and is removed. Line clipping may replace endpoints, and polygon clipping may create vertices. These geometric methods are distinct from the broader methods in DSA & Algorithms.

The rectangular window is 2 <= x <= 8 and 2 <= y <= 6.

Boundary points count as inside. Fix TOP = 1000, BOTTOM = 0100, RIGHT = 0010, and LEFT = 0001; the central region is 0000.

Cohen-Sutherland line clipping: outcodes and a complete example

Cohen-Sutherland first applies two bitwise tests:

1. If code(P) OR code(Q) = 0000, both endpoints are inside, so accept the whole line.

2. If code(P) AND code(Q) != 0000, both endpoints share an outside half-plane, so reject the line.

3. Otherwise, intersect an outside endpoint with a boundary, replace it, and classify again.

Clip P = (-2, 5) to Q = (10, 1). Here code(P) = 0001 because P is left of the window. For Q, both y < 2 and x > 8, so code(Q) = 0110. Their OR is non-zero, while 0001 AND 0110 = 0000. The line is neither trivially accepted nor rejected.

Parameterise it as:

x = -2 + 12t, y = 5 - 4t, for 0 <= t <= 1.

Clip P against the left boundary. Set x = 2:

2 = -2 + 12t, so t = 1/3.

Then y = 5 - 4(1/3) = 15/3 - 4/3 = 11/3. Replace P by A = (2, 11/3), whose code is 0000.

For Q, choose its BOTTOM bit and set y = 2:

2 = 5 - 4t, so t = 3/4.

Then x = -2 + 12(3/4) = -2 + 9 = 7. Replace Q by B = (7, 2), also coded 0000. The accepted segment is exactly (2, 11/3) to (7, 2). Choosing Q's RIGHT bit first adds an intermediate intersection, but repeated classification reaches the same segment.

Liang-Barsky line clipping: the same answer from parameter bounds

Liang-Barsky keeps the same parameterised line, with dx = 12 and dy = -4, but converts the four window inequalities into entering and leaving bounds. For p < 0, raise the entering bound. For p > 0, lower the leaving bound. If p = 0, reject only when q < 0; otherwise that parallel boundary adds no restriction.

Therefore:

u_enter = max(0, 1/3, -1/4) = 1/3

u_leave = min(1, 5/6, 3/4) = 3/4

Since u_enter <= u_leave, part of the line survives. Substitution gives (2, 11/3) at t = 1/3 and (7, 2) at t = 3/4, exactly matching Cohen-Sutherland. The distinction is procedural: Cohen-Sutherland repeatedly classifies endpoints, while Liang-Barsky tightens one parameter interval from four inequalities.

Sutherland-Hodgman polygon clipping: a worked triangle

Sutherland-Hodgman sends the polygon's cyclic vertex list through each clip boundary. For every directed polygon edge, apply four rules: inside to inside outputs the endpoint; inside to outside outputs the intersection; outside to inside outputs the intersection and endpoint; outside to outside outputs nothing. The output from one boundary becomes the input to the next.

Clip triangle A = (1, 3), B = (5, 7), C = (9, 3) in the order left, right, bottom, top.

• After left: [(2, 3), (2, 4), (5, 7), (9, 3)]

• After right: [(8, 3), (2, 3), (2, 4), (5, 7), (8, 4)]

• After bottom: unchanged, because every y-coordinate is at least 3

• After top: [(8, 3), (2, 3), (2, 4), (4, 6), (6, 6), (8, 4)]

The non-obvious intersections are easy to verify parametrically. On A -> B, x = 1 + 4t; setting x = 2 gives t = 1/4 and y = 3 + 4(1/4) = 4, so the point is (2, 4). On B -> C, setting 5 + 4t = 8 gives t = 3/4 and y = 7 - 4(3/4) = 4, giving (8, 4).

For the top pass, (2, 4) -> (5, 7) reaches y = 6 at t = 2/3, so x = 2 + 3(2/3) = 4. The edge (5, 7) -> (8, 4) reaches y = 6 at t = 1/3, so x = 5 + 3(1/3) = 6. The visible result is a six-vertex polygon.

Cohen-Sutherland, Liang-Barsky and Sutherland-Hodgman compared

Liang-Barsky checks four inequalities for a rectangle. Sutherland-Hodgman processes the current vertex list once per clip edge, commonly expressed as O(nm) for n subject vertices and m clip edges. No line method is universally fastest because rejection rate, branching and window shape affect implementation cost.

Weiler-Atherton is the alternative for concave clip regions, holes or multiple disjoint output components that one Sutherland-Hodgman vertex stream cannot represent cleanly.

Clipping algorithm question angles

Most clipping questions reduce to four operations: calculate endpoint outcodes, apply OR and AND correctly, solve an intersection or parameter interval, and trace polygon vertices after successive boundaries. Use UGC NET Computer Science Syllabus Areas: Paper 2 for syllabus-level orientation and UGC NET Computer Science High-Yield Topics for a broader revision map.

For a fast rejection example, take R = (-1, 7) and S = (9, 8). Their outcodes are 1001 and 1010. Since 1001 AND 1010 = 1000, both points are above the window and the line is trivially rejected. By contrast, the running line had AND equal to zero and still needed clipping.

Place clipping among the broader Computer Science subjects with the UGC NET CS Exam Preparation category.

Clipping algorithm traps that change the answer

• Wrong outcode logic: OR being non-zero does not prove rejection. Declare the bit order, then use non-zero AND for a trivial reject.

• Mixed endpoint formulas: Reusing one coordinate from an updated endpoint and another from the original line changes the geometry. Keep one form, P + t(Q - P), and handle parallel lines explicitly.

• Broken polygon trace: Treating boundary points as outside, losing cyclic order or omitting the intersection on an outside-to-inside transition changes the final list. Write the four transition rules before tracing.

Clipping algorithms: the short version and next step

Use a five-step recall sequence: define the window and inclusive boundary rule; classify endpoints or vertices; take a trivial line decision when possible; compute only the required intersections; verify every final point satisfies 2 <= x <= 8 and 2 <= y <= 6. The stable answers above are the line (2, 11/3) to (7, 2) and the six-vertex polygon [(8, 3), (2, 3), (2, 4), (4, 6), (6, 6), (8, 4)].

As a final check, clip P = (0, 0) to Q = (10, 8). With x = 10t and y = 8t, the entering bound is max(2/10, 2/8) = 1/4, and the leaving bound is min(8/10, 6/8) = 3/4. The accepted segment is (2.5, 2) to (7.5, 6).

If you want Computer Science Paper 2 concepts, notes, practice and tests in one structured path, continue with NTA-UGC-NET Paper - 2. If clipping is your only gap, first redraw the window and reproduce both worked outputs without looking back.