2D Viewing & Clipping: Windows, Viewports, Cohen-Sutherland, Liang-Barsky

TAKEAWAYS:

• Viewing transformation maps a world coordinate window to a device coordinate viewport using scaling, translation, and clipping.
• Cohen-Sutherland clips lines by region codes (9-bit binary flags) and trivial accept/reject tests before parametric intersection checks.
• Liang-Barsky improves efficiency by computing intersection parameters directly from line equations and clipping boundaries.
• Polygon clipping (Sutherland-Hodgman) processes edges sequentially, adding/subtracting vertices at intersections.
• Real-world use: Clipping ensures only visible content renders (e.g., Daraz’s product thumbnails, Pathao’s ride boundaries).
• Exam focus: Derive region codes, trace clipping steps, and compare algorithms’ time/space complexity.

1. Viewing in 2D: Windows and Viewports

Key Concepts

• World Coordinate System (WCS): The original coordinate system where objects are defined (e.g., a 2D map of Kathmandu with coordinates in meters).
• Window: A rectangular subset of WCS that defines the visible area (e.g., W = [x₁, x₂] × [y₁, y₂]).
• Viewport: The corresponding rectangle in device coordinates (e.g., pixels on your screen, V = [u₁, u₂] × [v₁, v₂]).
• Viewing Transformation: Maps the window to the viewport using:
  1. Scaling: Stretch/shrink the window to fit the viewport.
  2. Translation: Shift the scaled window to align with the viewport.

Mathematical Formulation

For a point (x, y) in WCS:

1. Scale to viewport dimensions: $$x^{\prime }=\frac{(x-x_1)(u_2-u_1)}{x_2-x_1},y^{\prime }=\frac{(y-y_1)(v_2-v_1)}{y_2-y_1}$$
2. Translate to viewport origin: $$u=x^{\prime }+u_1,v=y^{\prime }+v_1$$

Example: Daraz Product Thumbnail

• Scenario: Daraz displays product images in a grid. Each product’s bounding box (window) in its original resolution must be clipped to a fixed viewport (e.g., 150×150 pixels).
• Steps:
  1. Define window: W = [0, 1000] × [0, 800] (original image dimensions).
  2. Define viewport: V = [0, 150] × [0, 150] (thumbnail size).
  3. Apply viewing transformation to clip and scale the image.

Mermaid Diagram: Viewing Pipeline

flowchart LR
    A["World Coordinate System\n(x, y)"] -->|"Window Selection"| B["Window\nW = [x₁,x₂]×[y₁,y₂]"]
    B -->|"Scaling"| C["Scaled Coordinates\n(x', y')"]
    C -->|"Translation"| D["Viewport\nV = [u₁,u₂]×[v₁,v₂]"]
    D -->|"Rasterization"| E["Device Screen\n(u, v)"]

2. Line Clipping: Cohen-Sutherland Algorithm

Why Clipping?

• Problem: Lines or polygons may extend outside the viewport. Only visible portions should be rendered.
• Example: In a game like Angry Birds, birds’ trajectories are clipped to the screen edges.

Region Codes

Each line endpoint is assigned a 9-bit region code (3 bits for left/right, 3 for top/bottom, 3 for inside/outside):

• Bit 1-3: Left (001), Right (010), Inside (000).
• Bit 4-6: Top (100), Bottom (001), Inside (000).
• Bit 7-9: Outside (100), Inside (000).

Formula: For a line from (x₁, y₁) to (x₂, y₂) and window [x₁, x₂] × [y₁, y₂]: $$\text{code}=\{\begin{array}{ll}001& \text{if }x<x_{\text{min}}\\ 010& \text{if }x>x_{\text{max}}\\ 100& \text{if }y>y_{\text{max}}\\ 001& \text{if }y<y_{\text{min}}\\ 000& \text{otherwise}\end{array}$$

Algorithm Steps

1. Compute region codes for both endpoints (P₁ and P₂).
2. Trivial Accept: If both codes are 000, accept the line.
3. Trivial Reject: If P₁ ∧ P₂ ≠ 0, reject the line (both outside same region).
4. Clip: Find intersection of the line with the window boundary and compute the new endpoint’s region code. Repeat until trivial accept/reject.

Worked Example: Clipping a Line

Line: (x₁, y₁) = (50, 50), (x₂, y₂) = (200, 200) Window: [100, 300] × [100, 300]

1. Region Codes:
   • P₁: 001 (left) + 001 (bottom) = 001001001 (binary) → 73 (decimal).
   • P₂: 000 (inside).
2. Trivial Reject? 73 ∧ 0 = 0 → No.
3. Clip to Left Edge (x = 100):
   • Parametric equation: x = x₁ + t(x₂ - x₁), y = y₁ + t(y₂ - y₁).
   • Solve 100 = 50 + t(200 - 50) → t = 0.75.
   • New point: (100, 50 + 0.75(150)) = (100, 162.5).
   • New code: 000 (inside).
4. Accept: Both endpoints now inside → Clip to (100, 162.5) to (200, 200).

Visual: Cohen-Sutherland Clipping

graph TD
    A["Window: [100,300]×[100,300]"] --> B["Line: (50,50)→(200,200)"]
    B --> C["Clip to x=100\nNew point: (100,162.5)"]
    C --> D["Accept clipped line"]

Advantages/Disadvantages

3. Line Clipping: Liang-Barsky Algorithm

Improvement Over Cohen-Sutherland

• Uses parametric equations to compute intersections directly.
• Avoids region codes → faster for complex scenes (e.g., 3D game engines).

Parametric Line Equation

A line from (x₁, y₁) to (x₂, y₂) can be written as: $$x=x_1+t\cdot (x_2-x_1),y=y_1+t\cdot (y_2-y_1),t\in [0,1]$$ where t is the parameter.

Clipping Conditions

For window [x₁, x₂] × [y₁, y₂], compute:

1. Left/Right: $$p=x_2-x_1,q=x_1-x_{\text{min}}$$ If p > 0: t₀ = q / p, else t₀ = q / p (sign matters).
2. Bottom/Top: $$p=y_2-y_1,q=y_1-y_{\text{min}}$$ Similarly compute t₀.

Algorithm Steps

1. Initialize t₀ = 0, t₁ = 1.
2. For each boundary (left, right, bottom, top):
   • Compute t for intersection.
   • Update t₀ = max(t₀, t) and t₁ = min(t₁, t).
   • If t₀ > t₁, reject the line.
3. If t₀ ≤ t₁, accept the clipped line from t₀ to t₁.

Worked Example: Liang-Barsky

Line: (50, 50) to (200, 200) Window: [100, 300] × [100, 300]

1. Left Edge (x = 100):

   • p = 200 - 50 = 150, q = 50 - 100 = -50.
   • t = q / p = -50 / 150 ≈ -0.333 → Reject if t < 0 (but we take max(t₀, t)).
   • Update t₀ = max(0, -0.333) = 0, t₁ = min(1, ∞) = 1 (no change).

2. Right Edge (x = 300):

   • p = 150, q = 50 - 300 = -250.
   • t = -250 / 150 ≈ -1.666 → t₀ remains 0.

3. Bottom Edge (y = 100):

   • p = 150, q = 50 - 100 = -50.
   • t = -50 / 150 ≈ -0.333 → t₀ = 0.

4. Top Edge (y = 300):

   • p = 150, q = 50 - 300 = -250.
   • t = -250 / 150 ≈ -1.666 → t₀ = 0.

Result: t₀ = 0.75 (from left edge), t₁ = 1.

• Clipped line: (100, 162.5) to (200, 200).

Visual: Liang-Barsky Intersection

graph TD
    A["Line: (50,50)→(200,200)"] --> B["Intersection at t=0.75\n(100,162.5)"]
    B --> C["Clipped line: (100,162.5)→(200,200)"]

4. Polygon Clipping: Sutherland-Hodgman Algorithm

Problem

Clipping polygons (e.g., a country’s border on a map) requires handling multiple edges.

Steps

1. Clip the polygon against one edge of the window at a time (left, right, bottom, top).
2. For each edge, process vertices sequentially:
   • If a vertex is inside, add it to the output list.
   • If a vertex is outside, compute its intersection with the edge and add the intersection point.
   • If both vertices are outside, skip.

Worked Example: Clipping a Triangle

Polygon: (50, 50), (200, 50), (100, 200) Window: [100, 300] × [100, 300]

1. Clip against Left Edge (x = 100):

   • Start with (50, 50) (outside).
   • Intersection with (200, 50): t = (100 - 50)/(200 - 50) = 0.5 → (100, 50).
   • (100, 200) is inside → add to output.
   • Result: (100, 50), (100, 200).

2. Clip against Bottom Edge (y = 100):

   • (100, 50) is outside → intersection with (100, 200): t = (100 - 50)/(200 - 50) = 0.5 → (100, 100).
   • (100, 200) is inside → add.
   • Result: (100, 100), (100, 200).

3. Final Clipped Polygon: (100, 100), (100, 200).

Visual: Polygon Clipping

graph TD
    A["Original Triangle"] --> B["Clip Left Edge\n(100,50)-(100,200)"]
    B --> C["Clip Bottom Edge\n(100,100)-(100,200)"]

In the Real World

1. Pathao Ride Boundaries

   • Idea: Viewport Clipping
   • How: Pathao’s app shows ride routes only within the map’s visible area. The driver’s path is clipped to the viewport to avoid rendering off-screen segments, improving performance.

2. Daraz Product Thumbnails

   • Idea: Line and Polygon Clipping
   • How: Product images are clipped to fixed-size thumbnails. The algorithm ensures only the visible portion of each product’s bounding box is rendered, saving memory and rendering time.

3. NTC Traffic Simulation

   • Idea: Sutherland-Hodgman Polygon Clipping
   • How: Simulating vehicle paths on Kathmandu’s roads involves clipping vehicle polygons to road boundaries. This ensures only valid paths (within road limits) are rendered in traffic models.

Exam Tip

1. Derive Region Codes: For Cohen-Sutherland, always show the 9-bit binary code for each endpoint.
2. Trace Steps: In Liang-Barsky, explicitly compute t for each boundary and update t₀/t₁.
3. Polygon Clipping: For Sutherland-Hodgman, process edges in order (left → right → bottom → top) and show intermediate vertex lists.
4. Common Pitfalls:
   • Forgetting to handle t < 0 or t > 1 in Liang-Barsky.
   • Incorrectly computing intersections in polygon clipping (use parametric equations).
5. Compare Algorithms: In short-answer questions, contrast Cohen-Sutherland (region codes) vs. Liang-Barsky (parametric math).

Key Formula Summary: