Point, Line (Cohen–Sutherland, Liang–Barsky), Polygon & Text Clipping
Open in the Padhaiko app2.8 Point Clipping
In computer graphics, clipping is the computational process of identifying which portions of geometric primitives lie inside a designated region (the clipping window) and discarding everything outside.
A rectangular clipping window in two dimensions is defined by four coordinate boundaries:
Point Clipping Condition
A point lies strictly inside the clipping window and is saved for display if and only if it simultaneously satisfies all four boundary inequalities:
If any of these four conditions evaluates to false, the point lies outside the viewing window and is discarded.
In graphics hardware and pipeline software, point clipping is implemented using four comparison operations. Point clipping is commonly applied to particle systems, point clouds, starfields, and bounding-box rejection tests.
2.9 Line Clipping
Line clipping determines which segment of a line falls inside the clipping window. A line segment belongs to one of three categories:
- Completely Inside: Both endpoints satisfy the point-clipping condition. The line is accepted without alteration.
- Completely Outside: Both endpoints lie entirely on the exterior side of a single window boundary (e.g., both lie to the left of ). The line is discarded without computing intersections.
- Partially Inside / Intersecting: One or both endpoints lie outside the window, and the segment crosses one or more window boundaries. Intersection points must be calculated to truncate the line to the window boundary.
In three dimensions, line clipping generalizes to clipping against the six planar boundaries of the viewing frustum (near, far, left, right, top, bottom planes) prior to the perspective divide. In 2D normalized device coordinates, lines are clipped against the axis-aligned rectangular boundaries of the viewport or world window.
2.9.1 Cohen–Sutherland Line Clipping Algorithm
The Cohen–Sutherland algorithm is a classic line-clipping method that minimizes floating-point intersection calculations by performing rapid bitwise tests on 4-bit region codes assigned to each endpoint.
The 4-Bit Region Code (Outcode)
The 2D plane is partitioned into nine regions relative to the clipping window. Each point is assigned a 4-bit code:
1001 | 1000 | 1010
Top-Left | Top | Top-Right
----------+----------+---------- y_wmax
0001 | 0000 | 0010
Left | Window | Right
----------+----------+---------- y_wmin
0101 | 0100 | 0110
Bot-Left | Bottom | Bot-Right
x_wmin x_wmax
Region Code (Outcode) Bit Assignment
For any point :
- Bit 1 (Top, MSB): Set to if , else .
- Bit 2 (Bottom): Set to if , else .
- Bit 3 (Right): Set to if , else .
- Bit 4 (Left, LSB): Set to if , else .
Trivial Acceptance and Rejection Tests
Let and be the outcodes of endpoints and :
- Trivial Acceptance:
Both endpoints have code , meaning both lie inside the clipping window. The line is accepted immediately with zero floating-point operations.
- Trivial Rejection:
Both endpoints share a common outside half-plane (e.g., both have Bit 1 set, indicating both are above the top boundary). The line cannot intersect the window and is discarded immediately.
- Iterative Clipping: If and , the line is partially visible or intersects multiple boundary lines without immediate trivial rejection.
Cohen–Sutherland Line Clipping Algorithm
For lines requiring iterative clipping:
Proof
- Select an endpoint with a non-zero outcode (say ).
- Test the bits of in consistent order () to find the first boundary the endpoint crosses.
- Compute the intersection point of the line with that boundary line using the line slope :
- Top ():
- Bottom ():
- Right ():
- Left ():
- Replace the outside endpoint with the intersection point .
- Recompute the outcode for the new endpoint.
- Repeat the trivial acceptance and rejection tests until the line is either accepted or rejected.
2.9.2 Liang–Barsky Line Clipping Algorithm
While the Cohen–Sutherland algorithm can calculate extraneous intersections for lines that are ultimately rejected, the Liang–Barsky algorithm uses a parametric line formulation that computes intersections using efficient inequalities.
Parametric Representation and Boundary Inequalities
A straight line segment from to is defined parametrically by:
where and .
For a point to lie inside the window :
These four inequalities are written in the unified form:
where:
- Boundary 1 (Left):
- Boundary 2 (Right):
- Boundary 3 (Bottom):
- Boundary 4 (Top):
Geometric Meaning of and Parameter Updates
The sign of dictates the direction of the directed line segment relative to boundary :
- (Parallel to boundary ):
- If , the line lies completely outside the boundary; reject the line.
- If , the line is parallel to the boundary and lies inside the boundary's half-space.
- (Line proceeds from outside to inside — Entering Boundary): The value defines an entering intersection parameter. The line enters the visible region as increases:
- (Line proceeds from inside to outside — Exiting Boundary): The value defines an exiting intersection parameter. The line leaves the visible region as increases:
Liang–Barsky Line Clipping Algorithm
- Initialize the parameter bounds: and .
- For each boundary :
- If and , reject the line.
- If , update .
- If , update .
- If at any step , the line enters after it has already exited; reject the line immediately.
- If , calculate the clipped endpoints:
| Aspect | Cohen–Sutherland Line Clipping | Liang–Barsky Line Clipping |
|---|---|---|
| Mathematical Basis | Explicit Cartesian slope-intercept form (). | Parametric line equations (). |
| Outcode Checking | Assigns 4-bit outcodes; extremely fast for trivial accept/reject. | Solves four simple linear inequalities (). |
| Intersection Calculations | Iteratively clips against boundaries; may calculate unused intersections for lines that are later rejected. | Computes parameter ratios ; never computes coordinate intersections until final are validated. |
| Computational Efficiency | Superior when most lines are trivially inside or completely outside. | Faster and requires fewer floating-point divisions when lines cross multiple boundaries. |
2.10 Polygon Clipping: Weiler–Atherton Polygon Clipping
Standard polygon clipping algorithms such as Sutherland–Hodgman clip a polygon against each window edge in succession. While Sutherland–Hodgman works well for convex polygons, when applied to concave polygons, it frequently produces extraneous connecting edges across exterior space when the polygon splits into multiple separate components.
The Weiler–Atherton algorithm overcomes this limitation, correctly clipping arbitrary concave polygons (including polygons and windows with internal holes) and decomposing them into distinct, well-formed polygon components.
Data Structures and Representation
Both the subject polygon () and the clipping window () are represented as circular linked lists of vertices traversed in a consistent clockwise (CW) direction.
Subject Polygon (S) Clipping Window (W)
S_1 -------> S_2 W_1 -------> W_2
^ | ^ |
| Clock- | | Clock- |
| wise v | wise v
S_4 <------- S_3 W_4 <------- W_3
Weiler–Atherton Intersection Classification
All edge intersections between the subject polygon and the window boundary are calculated and inserted into both vertex lists. Each intersection is classified as:
- Entering Intersection: Moving clockwise along the subject polygon edge, the edge transitions from the exterior of the window into the interior.
- Exiting (Leaving) Intersection: Moving clockwise along the subject polygon edge, the edge transitions from the interior of the window to the exterior.
Traversal Rules for Extracting Clipped Polygons
Weiler–Atherton Clipping Algorithm
To extract all clipped polygon components:
Proof
- Find all intersections between edges of subject polygon and window .
- Insert each intersection vertex into the circular vertex list of and the circular vertex list of in their respective clockwise traversal positions.
- Classify every intersection vertex as Entering or Exiting.
- Loop through the list of entering intersections:
- Select an unvisited entering intersection and mark it as visited.
- Follow the subject polygon list in the clockwise direction until an exiting intersection is encountered.
- Switch to the clipping window list at .
- Follow the window boundary in the clockwise direction until an entering intersection is encountered.
- Switch back to the subject polygon list at .
- Continue alternating between lists until returning to .
- Output the accumulated vertex chain as one closed clipped polygon component.
- Repeat step 4 until all entering intersections have been processed.
2.11 Text Clipping
Displaying textual annotations and labels within a graphics scene requires clipping characters against the viewing boundaries. Because text consists of combinations of strings, glyphs, and character outlines, graphics systems implement three distinct levels of text clipping depending on performance and precision requirements:
Text Clipping Strategies
- All-or-None String Clipping:
- A single rectangular bounding box is constructed around the entire text string.
- If the bounding box lies entirely within the clipping window, the entire string is displayed.
- If any portion of the bounding box falls outside the window, the entire string is rejected.
- Advantage: Minimal processing overhead; fastest text clipping method.
- Limitation: Discards entire words near window edges even if most characters are visible.
- All-or-None Character Clipping:
- An individual bounding box is calculated for each character in the string.
- Each character is tested independently against the window:
- If the character's bounding box is completely inside, that character is rendered.
- If the character's bounding box overlaps or lies outside the window, that character is discarded.
- Advantage: Characters inside the window remain readable; standard for bitmap fonts.
- Limitation: Characters crossing the boundary are either completely displayed or omitted, producing ragged edges.
- Component (Stroke / Outline) Clipping:
- Text is represented using vector or outline fonts (e.g., TrueType, PostScript) defined by line segments and Bézier curve strokes.
- Individual stroke segments are clipped against the window boundaries using line-clipping algorithms (Cohen–Sutherland or Liang–Barsky).
- Advantage: Precise, pixel-accurate clipping through the bodies of individual characters.
- Limitation: Requires significantly higher computational resources.
| Feature | All-or-None String | All-or-None Character | Component (Stroke) Clipping |
|---|---|---|---|
| Granularity | Entire text string | Individual character glyphs | Individual vector stroke segments |
| Boundary Appearance | String vanishes entirely if touching boundary | Characters vanish abruptly at boundary | Characters are smoothly cut through the middle |
| Font Type | Bitmap or outline | Bitmap or outline | Outline / vector fonts only |
| Computational Cost | Single bounding box test () | One test per character () | Many line-clipping operations () |
| Typical Use | Fast GUI labels, radar screens | Low-power terminals, bitmap consoles | CAD viewports, PDF viewers, high-end vector publishing |
Worked Out Examples
1
Use the Cohen–Sutherland line clipping algorithm to clip two line segments:
- Line 1: to
- Line 2: to
against a clipping window defined by .
Evaluating Outcodes for Line 1 (): Window boundaries: . Outcode definition: .
- For :
- For :
Testing trivial acceptance / rejection:
- Bitwise OR: (not trivially accepted).
- Bitwise AND: (not trivially rejected; line is partially visible and must be clipped).
Clipping Line 1 Against Left Boundary: Endpoint has Bit 4 (Left) set. Line slope:
Compute intersection with left boundary line :
New endpoint is . Checking outcode: and .
Clipping Line 1 Against Top Boundary: Endpoint has Bit 1 (Top) set. Compute intersection with top boundary line :
New endpoint is . Checking outcode: and . Both endpoints now have outcode ; the clipped segment is accepted.
Evaluating Outcodes for Line 2 ():
- For :
- For :
Testing trivial acceptance / rejection:
- Bitwise AND: .
- Because Bit 2 is set in both outcodes, both endpoints lie entirely below the bottom boundary .
- Therefore, Line 2 is trivially rejected and completely discarded.
- Line 1: Partially visible. Clipped to segment from to .
- Line 2: Trivially rejected (); completely outside bottom boundary.
2
Use the Liang–Barsky line clipping algorithm to clip the line segment from to against a window with .
Formulating Parametric Steps and : Line coordinates: and .
Initialize parameter bounds: (entering maximum) and (exiting minimum).
Evaluating Boundaries :
- Left Boundary ():
Since (entering):
- Right Boundary ():
Since (exiting):
- Bottom Boundary ():
Since (entering):
- Top Boundary ():
Since (exiting):
Validation and Calculating Clipped Endpoints: Comparing parameter limits:
Since , the segment is visible and clipped between and :
- Entering Point :
- Exiting Point :
The Liang–Barsky algorithm computes parameter limits and . The clipped line segment extends from to .
3
Demonstrate the Weiler–Atherton polygon clipping algorithm by clipping a subject rectangle against a rectangular window . Trace the clockwise vertex lists, classify the intersections, and extract the resulting clipped polygon.
Identifying Edge Intersections and Classifications: Both polygons are oriented in clockwise order. Testing subject polygon edges against the window boundaries ():
- Edge : Lies entirely outside the left boundary (). No intersections.
- Edge :
- Crosses the left window edge at . Directed from outside to inside Entering Intersection.
- Crosses the right window edge at . Directed from inside to outside Exiting Intersection.
- Edge : Lies entirely outside the right boundary (). No intersections.
- Edge :
- Crosses the right window edge at . Directed from outside to inside Entering Intersection.
- Crosses the left window edge at . Directed from inside to outside Exiting Intersection.
Constructing Circular Vertex Lists: Insert intersections into both lists in clockwise order:
- Subject Polygon List :
- Window List (Clockwise around boundaries):
- Left edge (, increasing from to ):
- Top edge (, increasing from to ):
- Right edge (, decreasing from to ):
- Bottom edge (, decreasing from to ):
Clockwise Traversal and Loop Extraction:
- Start at unvisited entering intersection on list .
- Follow subject polygon clockwise: advance from to exiting intersection .
- Switch to window list at : advance clockwise down the right window boundary to entering intersection .
- Switch to subject polygon list at : advance clockwise along to exiting intersection .
- Switch to window list at : advance clockwise up the left window boundary to entering intersection .
- We have returned to the starting vertex . All entering intersections are now visited.
The Weiler–Atherton traversal extracts a single closed polygon with vertices:
This defines the rectangular region .
Exercises
Exercise — Point, Line, Polygon & Text Clipping
Use the Cohen–Sutherland line clipping algorithm to clip the line segment connecting and against a window with boundaries . Show all outcode evaluations, intersection calculations, and determine the clipped endpoints.
Outcode Evaluation and Initial Rejection Test: Window extents: .
- For :
- For :
Bitwise tests:
- (not trivially accepted).
- (not trivially rejected).
The line is partially visible and requires boundary intersection clipping. Line slope:
Clipping Endpoint : .
- Clip against Bottom boundary ():
New point is . Since , the Left bit is still set: .
- Clip against Left boundary ():
New endpoint . Outcode: and .
Clipping Endpoint : .
- Clip against Top boundary ():
Since , the Right bit is still set: .
- Clip against Right boundary ():
New endpoint . Outcode: and .
The clipped line segment connects and .
Apply the Liang–Barsky line clipping algorithm to clip the line from to against the window .
Computing Parametric Directional Steps: Given endpoints and :
Initialize and .
Evaluating Boundary Conditions:
- Left Boundary ():
Since (entering):
- Right Boundary ():
Since (exiting):
- Bottom Boundary ():
Since (exiting):
- Top Boundary ():
Since (entering):
Parameter Interval and Endpoint Evaluation: Since , the clipped segment is accepted:
- Point at :
- Point at :
The parameter interval is . The clipped line segment connects and .
Given a clipping window , test the following four points using point clipping: . State which points are saved and which are rejected, with reasons.
Applying the Point Clipping Conditions: A point is saved if and only if and .
- For : (violates ). Condition fails Rejected (lies left of the window).
- For : (True) and (True). All conditions satisfied Saved (lies inside the window).
- For : (violates ) and (violates ). Condition fails Rejected (lies below and to the right of the window).
- For : (violates ). Condition fails Rejected (lies above the window).
- : Rejected ()
- : Saved (inside window)
- : Rejected ()
- : Rejected ()
Explain why the Sutherland–Hodgman algorithm fails on concave polygons, and explain how the Weiler–Atherton algorithm resolves this issue.
Failure Mode of Sutherland–Hodgman on Concave Polygons: The Sutherland–Hodgman algorithm clips a polygon against each window boundary line sequentially, outputting a single continuous list of vertices. When a concave polygon (such as a U-shaped or crescent polygon) intersects a clipping boundary, the portion inside the window may be severed into two or more physically separate polygon components. Because Sutherland–Hodgman maintains only a single vertex sequence, it connects the separated components with an extraneous bridge edge along the clipping boundary. When the polygon is later rendered or filled, this artificial edge causes incorrect exterior regions to be shaded.
Resolution by the Weiler–Atherton Algorithm: The Weiler–Atherton algorithm maintains two circularly linked vertex lists (one for the subject polygon and one for the clipping window), both oriented clockwise:
- It inserts intersection vertices into both lists and classifies them as entering or exiting.
- It traces closed cycles individually: walking along the subject polygon from entering to exiting intersections, and walking along the window boundary from exiting to entering intersections.
- Once a closed cycle returns to its starting entering intersection, it forms an independent polygon component.
- The algorithm then proceeds to the next unvisited entering intersection, discovering and cleanly separating each disconnected polygon piece without extraneous joining edges.
Sutherland–Hodgman outputs a single vertex list and introduces extraneous connecting edges across exterior gaps when clipping concave shapes. Weiler–Atherton resolves this by alternating traversal between dual circular lists of the subject polygon and window boundary, successfully producing separate output vertex lists for each disconnected component.
Compare the Cohen–Sutherland and Liang–Barsky line clipping algorithms in terms of computational complexity, number of divisions, and suitability for different scene conditions.
Computational Comparison:
- Cohen–Sutherland:
- Uses 4-bit region outcodes and bitwise Boolean operators (
AND,OR). - For lines completely inside or completely outside, it requires zero floating-point calculations ( bitwise operations).
- For lines requiring clipping, it computes intersections iteratively. If a line is clipped multiple times before ultimately being discarded outside another boundary, all intermediate floating-point divisions are wasted.
- Uses 4-bit region outcodes and bitwise Boolean operators (
- Liang–Barsky:
- Uses a parametric formulation ().
- Evaluates parameter limits using at most four scalar divisions.
- Never computes spatial coordinates until the final parameter range is proven valid ().
- Avoids all extraneous intersection calculations.
Suitability:
- Cohen–Sutherland is optimal for large virtual worlds where the vast majority of scene lines lie completely outside the viewing frustum (trivial reject) or completely inside (trivial accept).
- Liang–Barsky is significantly faster when a large fraction of lines intersect the clipping boundaries, because it replaces multiple line-equation evaluations with at most four single-division parameter tests.
Cohen–Sutherland is fastest for scenes dominated by completely inside or completely outside lines due to instant bitwise testing. Liang–Barsky is superior when lines cross multiple boundaries, because its parametric formulation delays coordinate evaluation until validity is proven, minimizing expensive floating-point divisions.
Describe the three standard text clipping methods: all-or-none string clipping, all-or-none character clipping, and component clipping. Compare their visual quality and computational cost.
Characteristics of the Three Methods:
- All-or-None String Clipping:
- Computes a single bounding box enclosing the entire text string.
- If the bounding box intersects or exceeds the window boundary, the entire string is discarded.
- Fastest method; zero character-level computation.
- All-or-None Character Clipping:
- Computes individual bounding boxes for each character.
- Characters completely inside are rendered; characters overlapping or outside boundaries are dropped.
- Moderate cost; characters near borders appear or vanish as whole units.
- Component (Stroke / Outline) Clipping:
- Decomposes outline or vector characters into constituent line segments and curve strokes.
- Applies standard line/curve clipping against window boundaries.
- High computational cost; characters are smoothly sliced across the window border.
Comparison:
- Visual Quality: Component clipping provides the highest fidelity (smooth cut across character strokes), followed by character clipping (whole characters), with string clipping having the lowest fidelity (entire text strings disappear).
- Computational Cost: String clipping requires only four boundary comparisons per string (). Character clipping requires four comparisons per character (). Component clipping requires line-clipping intersections for every vector stroke ().
- All-or-none string clipping: Lowest cost (), lowest quality (entire string is discarded if any part is outside).
- All-or-none character clipping: Moderate cost (), medium quality (individual characters inside are kept; characters crossing boundaries are omitted).
- Component clipping: Highest cost (), highest visual quality (vector strokes are cleanly clipped through the middle of characters).