PadhaikoAll subjects

Point, Line (Cohen–Sutherland, Liang–Barsky), Polygon & Text Clipping

Computer Graphics and Visualization (ENCT 201)

Open in the Padhaiko app

2.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:

Definition

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:

  1. Completely Inside: Both endpoints satisfy the point-clipping condition. The line is accepted without alteration.
  2. 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.
  3. 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
Definition

Region Code (Outcode) Bit Assignment

For any point :

Trivial Acceptance and Rejection Tests

Let and be the outcodes of endpoints and :

  1. Trivial Acceptance:

Both endpoints have code , meaning both lie inside the clipping window. The line is accepted immediately with zero floating-point operations.

  1. 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.

  1. Iterative Clipping: If and , the line is partially visible or intersects multiple boundary lines without immediate trivial rejection.
Theorem

Cohen–Sutherland Line Clipping Algorithm

For lines requiring iterative clipping:

Proof

  1. Select an endpoint with a non-zero outcode (say ).
  2. Test the bits of in consistent order () to find the first boundary the endpoint crosses.
  3. Compute the intersection point of the line with that boundary line using the line slope :
    • Top ():
    • Bottom ():
    • Right ():
    • Left ():
  4. Replace the outside endpoint with the intersection point .
  5. Recompute the outcode for the new endpoint.
  6. 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:

Definition

Geometric Meaning of and Parameter Updates

The sign of dictates the direction of the directed line segment relative to boundary :

  1. (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.
  2. (Line proceeds from outside to inside — Entering Boundary): The value defines an entering intersection parameter. The line enters the visible region as increases:
  1. (Line proceeds from inside to outside — Exiting Boundary): The value defines an exiting intersection parameter. The line leaves the visible region as increases:
Theorem

Liang–Barsky Line Clipping Algorithm

  1. Initialize the parameter bounds: and .
  2. 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.
  3. If , calculate the clipped endpoints:
AspectCohen–Sutherland Line ClippingLiang–Barsky Line Clipping
Mathematical BasisExplicit Cartesian slope-intercept form ().Parametric line equations ().
Outcode CheckingAssigns 4-bit outcodes; extremely fast for trivial accept/reject.Solves four simple linear inequalities ().
Intersection CalculationsIteratively 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 EfficiencySuperior 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
Definition

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:

Traversal Rules for Extracting Clipped Polygons

Theorem

Weiler–Atherton Clipping Algorithm

To extract all clipped polygon components:

Proof

  1. Find all intersections between edges of subject polygon and window .
  2. Insert each intersection vertex into the circular vertex list of and the circular vertex list of in their respective clockwise traversal positions.
  3. Classify every intersection vertex as Entering or Exiting.
  4. 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.
  5. 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:

Definition

Text Clipping Strategies

  1. 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.
  2. 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.
  3. 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.
Comparison of Text Clipping Methods
FeatureAll-or-None StringAll-or-None CharacterComponent (Stroke) Clipping
GranularityEntire text stringIndividual character glyphsIndividual vector stroke segments
Boundary AppearanceString vanishes entirely if touching boundaryCharacters vanish abruptly at boundaryCharacters are smoothly cut through the middle
Font TypeBitmap or outlineBitmap or outlineOutline / vector fonts only
Computational CostSingle bounding box test ()One test per character ()Many line-clipping operations ()
Typical UseFast GUI labels, radar screensLow-power terminals, bitmap consolesCAD viewports, PDF viewers, high-end vector publishing

Worked Out Examples

Example 1

1

Use the Cohen–Sutherland line clipping algorithm to clip two line segments:

  1. Line 1: to
  2. 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.
Answer:
  1. Line 1: Partially visible. Clipped to segment from to .
  2. Line 2: Trivially rejected (); completely outside bottom boundary.
Example 2

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 :

  1. Left Boundary ():

Since (entering):

  1. Right Boundary ():

Since (exiting):

  1. Bottom Boundary ():

Since (entering):

  1. 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 :
Answer:

The Liang–Barsky algorithm computes parameter limits and . The clipped line segment extends from to .

Example 3

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:

  1. Start at unvisited entering intersection on list .
  2. Follow subject polygon clockwise: advance from to exiting intersection .
  3. Switch to window list at : advance clockwise down the right window boundary to entering intersection .
  4. Switch to subject polygon list at : advance clockwise along to exiting intersection .
  5. Switch to window list at : advance clockwise up the left window boundary to entering intersection .
  6. We have returned to the starting vertex . All entering intersections are now visited.
Answer:

The Weiler–Atherton traversal extracts a single closed polygon with vertices:

This defines the rectangular region .

Exercises

Exercise — Point, Line, Polygon & Text Clipping

Question 1

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 : .

  1. Clip against Bottom boundary ():

New point is . Since , the Left bit is still set: .

  1. Clip against Left boundary ():

New endpoint . Outcode: and .

Clipping Endpoint : .

  1. Clip against Top boundary ():

Since , the Right bit is still set: .

  1. Clip against Right boundary ():

New endpoint . Outcode: and .

Answer:

The clipped line segment connects and .

Question 2

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:

  1. Left Boundary ():

Since (entering):

  1. Right Boundary ():

Since (exiting):

  1. Bottom Boundary ():

Since (exiting):

  1. Top Boundary ():

Since (entering):

Parameter Interval and Endpoint Evaluation: Since , the clipped segment is accepted:

  • Point at :
  • Point at :
Answer:

The parameter interval is . The clipped line segment connects and .

Question 3

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 .

  1. For : (violates ). Condition fails Rejected (lies left of the window).
  2. For : (True) and (True). All conditions satisfied Saved (lies inside the window).
  3. For : (violates ) and (violates ). Condition fails Rejected (lies below and to the right of the window).
  4. For : (violates ). Condition fails Rejected (lies above the window).
Answer:
  • : Rejected ()
  • : Saved (inside window)
  • : Rejected ()
  • : Rejected ()
Question 4

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:

  1. It inserts intersection vertices into both lists and classifies them as entering or exiting.
  2. 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.
  3. Once a closed cycle returns to its starting entering intersection, it forms an independent polygon component.
  4. The algorithm then proceeds to the next unvisited entering intersection, discovering and cleanly separating each disconnected polygon piece without extraneous joining edges.
Answer:

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.

Question 5

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.
  • 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.
Answer:

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.

Question 6

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:

  1. 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.
  2. 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.
  3. 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 ().
Answer:
  • 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).

Past exam questions for Computer Graphics and Visualization

← Scan-Line, Boundary & Flood Fill2D & Composite Transformations; Window-to-Viewport →