Clipping Algorithms: Lines, Polygons & Window-Viewport

TAKEAWAYS

• Clipping algorithms crop objects to fit within a defined window/viewport, improving rendering efficiency and realism.
• Cohen-Sutherland uses region codes (9-bit binary flags) to discard lines entirely outside the window in 4 passes.
• Sutherland-Hodgman clips polygons by iteratively intersecting edges with the window boundary.
• Liang-Barsky is a parametric line-clipping method faster than Cohen-Sutherland for complex scenes.
• Real-world uses: eSewa’s transaction UI (clips overflowing buttons), Google Maps (zooms to visible area), game engines (culls off-screen objects).
• Exam tip: Always draw the region codes and intersection points in traces—partial credit is lost without visuals.

---

Why Clipping?

Computer graphics systems (e.g., games, CAD tools, or even eSewa’s mobile app) render objects in a virtual world but display only what fits on the screen (viewport). Clipping algorithms discard invisible parts to save computation and avoid rendering artifacts.

Real-World Example 1: eSewa’s Mobile UI

When you open eSewa to pay a bill, the app’s interface clips:

• Overflowing buttons (e.g., "Pay Bill" button) to fit within the phone screen.
• Transaction history to show only visible rows (like a scrollable list). How? The app uses viewport clipping to ensure no UI element bleeds outside the display.

Real-World Example 2: Google Maps (Zoom & Pan)

When you zoom into a map, Google Maps clips:

• Roads and landmarks to the visible rectangle on your screen.
• Off-screen tiles (e.g., Kathmandu’s eastern districts when you’re viewing Thamel). How? The backend uses Liang-Barsky or Cohen-Sutherland to discard irrelevant map data.

Real-World Example 3: Game Engines (FPS Culling)

In Call of Duty or PUBG, the game engine clips:

• Buildings and enemies outside your field of view (FOV).
• Bullet trajectories to stop rendering once they leave the screen. How? Frustum clipping (a 3D extension of 2D clipping) removes unseen objects.

---

1. Line Clipping: Cohen-Sutherland Algorithm

Cohen-Sutherland clips a line segment against a rectangular window using region codes and 4 passes.

Key Concepts

• Region Codes (RC): A 4-bit code (extended to 9 bits for all 9 regions) that labels where a point lies relative to the window:

  Bit Positions: 3 2 1 0
  Meaning:       Left Right Bottom Top
  

  • 0000: Inside the window.
  • 1000: Left of the window.
  • 0001: Above the window.
  • 1111: Outside all boundaries (trivial reject).

• Trivial Accept/Reject:

  • If both endpoints have RC = 0000 → accept (fully inside).
  • If bitwise AND of RCs is non-zero → reject (fully outside).

Algorithm Steps

1. Compute region codes for both endpoints.
2. Trivial accept/reject check.
3. 4 passes (each pass eliminates one boundary):
   • Left/Right: Adjust the endpoint outside the left/right boundary.
   • Bottom/Top: Adjust the endpoint outside the bottom/top boundary.
4. Repeat until trivial accept or reject.

Worked Example: Clip Line from (50, 50) to (100, 10)

Assume window: x ∈ [20, 80], y ∈ [20, 60].

Step-by-Step Trace

Final Clipped Line: (50,50) to (80,20).

Advantages/Disadvantages

---

2. Polygon Clipping: Sutherland-Hodgman Algorithm

Clips a polygon against a convex window (e.g., a rectangle or irregular shape) by processing edges one by one.

Key Concepts

• Inside/Outside Test: For each edge of the window, classify polygon vertices as inside (I) or outside (O).
• Intersection Points: When a polygon edge crosses the window boundary, compute the intersection.
• Output Polygon: Built incrementally by adding valid vertices and intersections.

Algorithm Steps

1. For each window edge (e.g., left, right, bottom, top):
   • Traverse the polygon vertices.
   • If a vertex is inside, add it to the output.
   • If an edge crosses the boundary, compute the intersection and add it.
2. Repeat for all 4 edges.

Worked Example: Clip Polygon Against a Rectangle

Polygon Vertices: (50,50), (100,20), (80,80), (30,70) Window: x ∈ [20, 80], y ∈ [20, 60]

Step-by-Step Trace

Final Clipped Polygon: (50,50), (40,60), (30,70), (20,30)

Advantages/Disadvantages

---

3. Liang-Barsky Line Clipping Algorithm

A parametric line-clipping method that computes intersections mathematically without region codes. Faster than Cohen-Sutherland for some cases.

Key Concepts

• Parametric Equations:
  • Line from (x1,y1) to (x2,y2) can be written as: x = x1 + t*(x2-x1), y = y1 + t*(y2-y1), where t ∈ [0,1].
• Clipping Conditions:
  • For each boundary (e.g., x ≥ xmin), solve for t: x1 + t*(x2-x1) ≥ xmin → t ≥ (xmin - x1)/(x2-x1) (if x2 > x1).

Algorithm Steps

1. Initialize t0 = 0, t1 = 1.
2. For each boundary (left, right, bottom, top):
   • Compute t for intersection.
   • Update t0 and t1 to the most restrictive interval.
3. If t0 ≤ t1, the line is visible; clip to [t0, t1].

Worked Example: Clip Line (50,50)-(100,10)

Window: x ∈ [20,80], y ∈ [20,60]

Step-by-Step Trace

Correction: The line is fully outside the top boundary (t ≤ 0.25 conflicts with t ≥ 0.75). But wait! Let’s re-calculate carefully:

• For top boundary (y ≤ 60): y1 + t*(y2-y1) ≤ 60 → 50 + t*(-40) ≤ 60 → -40t ≤ 10 → t ≥ -0.25 (since we divide by negative, inequality flips).
• Bottom boundary (y ≥ 20): 50 + t*(-40) ≥ 20 → -40t ≥ -30 → t ≤ 0.75.
• Final t range: max(-0.6, -0.25, 0) = 0 to min(0.6, 0.75, 1) = 0.6.
• Visible segment: t ∈ [0, 0.6] → Clip to (50,50) to (50 + 0.6*50, 50 + 0.6*(-40)) = (80, 26).

Final Clipped Line: (50,50) to (80,26).

Advantages/Disadvantages

---

Comparison Table: Line Clipping Algorithms

---

Real-World Tie-In: Daraz’s Order Queue System

Imagine Daraz’s order processing pipeline:

1. A user places an order (e.g., a phone from Kathmandu to Pokhara).
2. The logistics system "clips" the delivery route to:
   • Visible delivery zones (e.g., only Pokhara’s Lekhnath area).
   • Avoid off-limits areas (e.g., remote hills without Daraz lockers). How? Daraz uses spatial clipping (like Sutherland-Hodgman) to:

• Filter delivery options to only feasible routes.
• Optimize courier paths by clipping to city boundaries.

---

Exam Tip: How to Score Full Marks

1. Always draw the window and object:
   • For Cohen-Sutherland, show region codes and intersection points.
   • For Sutherland-Hodgman, sketch the original and clipped polygon.
2. Show all steps:
   • Write the RC bits for Cohen-Sutherland.
   • List intersection calculations for Liang-Barsky.
3. Use real numbers:
   • Avoid (0,0)-(10,10); use exam-like values (e.g., (50,50)-(100,10)).
4. Compare algorithms:
   • If asked "which is better?", discuss speed vs. simplicity (e.g., Liang-Barsky is faster but harder to code).
5. Mention applications:
   • Link to eSewa UI clipping, Google Maps zooming, or game culling.

---

Practice Questions (Exam Style)

1. Cohen-Sutherland: Clip the line (30,30)-(90,10) against window [20,80]×[20,60]. Show RCs and final clipped line.
2. Sutherland-Hodgman: Clip the polygon (40,40), (60,20), (80,60), (20,80) against a rectangle [30,70]×[30,70].
3. Short Notes: Compare Cohen-Sutherland and Liang-Barsky in a table (speed, complexity, use case).
4. Application: How does Khalti’s transaction UI use clipping? (Hint: Button scaling to fit screen.)

---

Summary Visual