Polygon Clipping & Filling: Algorithms, Cohen-Sutherland, Scanline

Core Concepts

1. Clipping Fundamentals

Clipping is the process of removing parts of objects that lie outside a specified window (a rectangular region defined by coordinates). It is essential for:

• Displaying only visible portions of objects within a viewport.
• Optimizing rendering by discarding invisible geometry.
• Supporting interactive graphics where objects move in/out of view.

Key Definitions:

• Window: The clipping region in world coordinates (e.g., (x_min, y_min) to (x_max, y_max)).
• Viewport: The target region on the screen where clipped objects are drawn.
• Viewing Transformation: Maps window coordinates to viewport coordinates.

2. Line Clipping: Cohen-Sutherland Algorithm

How It Works

The Cohen-Sutherland algorithm clips a line segment against a rectangular window using region codes and trivial acceptance/rejection rules. It works in two phases:

1. Region Coding: Assign a 4-bit code to each endpoint based on its position relative to the window.
   • Bits represent: Left (L), Right (R), Bottom (B), Top (T).
   • Example: (0001) = inside the window; (1000) = left of the window.
2. Trivial Acceptance/Rejection:
   • If both endpoints have code 0000, the line is fully inside → accept.
   • If bitwise AND of codes is non-zero, the line is fully outside → reject.
3. Iterative Clipping: For partially visible lines, compute intersection points with window edges and update the endpoint codes.

Region Code Table

Worked Example: Clip Line from (10,10) to (60,30) in Window (15,15)-(25,25)

1. Window: (x_min=15, y_min=15) to (x_max=25, y_max=25).
2. Region Codes:
   • P1(10,10): Left (1000) + Bottom (0001) = 1001 (9).
   • P2(60,30): Right (0100) + Top (0010) = 0110 (6).
3. Bitwise AND: 1001 & 0110 = 0000 → Not trivially reject.
4. Iteration 1: Clip against left edge (x=15).
   • Intersection: (15, y) where y = 10 + (30-10)*(15-10)/(60-10) = 12.5.
   • New P1: (15, 12.5) → Code: 0001 (1).
   • P2 remains (60,30) → Code: 0110 (6).
5. Bitwise AND: 0001 & 0010 = 0000 → Continue.
6. Iteration 2: Clip against bottom edge (y=15).
   • Intersection: (x, 15) where x = 10 + (60-10)*(15-12.5)/(30-12.5) = 17.5.
   • New P1: (17.5, 15) → Code: 0000 (0).
   • P2 remains (60,30) → Code: 0110 (6).
7. Bitwise AND: 0000 & 0110 = 0000 → Continue.
8. Iteration 3: Clip against right edge (x=25).
   • Intersection: (25, y) where y = 15 + (30-15)*(25-17.5)/(60-17.5) = 18.75.
   • New P2: (25, 18.75) → Code: 0010 (2).
   • P1 remains (17.5, 15) → Code: 0000 (0).
9. Bitwise AND: 0000 & 0010 = 0000 → Accept.
10. Final Clipped Line: (17.5, 15) to (25, 18.75).

Mermaid Diagram: Cohen-Sutherland Algorithm Flow

flowchart TD
    A[Start] --> B[Compute Region Codes for P1, P2]
    B --> C{Bitwise AND of Codes == 0?}
    C -->|Yes| D{Both Codes == 0000?}
    D -->|Yes| E[Accept Line]
    D -->|No| F[Reject Line]
    C -->|No| G[Find Intersection with Window Edge]
    G --> H[Update Endpoint]
    H --> B

Advantages/Disadvantages

3. Polygon Clipping: Sutherland-Hodgman Algorithm

How It Works

The Sutherland-Hodgman algorithm extends line clipping to polygons by:

1. Clipping the polygon against each edge of the window sequentially.
2. For each edge, compute intersections between the polygon edges and the clipping edge.
3. Retain only the visible portions of the polygon.

Steps:

1. Start with the input polygon P = [P1, P2, ..., Pn].
2. For each clipping edge (e.g., left, right, bottom, top):
   • Initialize an output polygon Q as empty.
   • For each edge (Pi, Pi+1) of P:
     • If Pi is inside the current clipping edge, add it to Q.
     • Compute intersection of (Pi, Pi+1) with the clipping edge. If it exists and Pi+1 is outside, add the intersection to Q.
3. After processing all edges, Q is the clipped polygon.

Worked Example: Clip Polygon with Vertices (10,10), (30,10), (30,30), (10,30) Against Window (15,15)-(25,25)

1. Initial Polygon: [(10,10), (30,10), (30,30), (10,30)].
2. Clip Against Left Edge (x=15):
   • Edge (10,10)-(30,10): Intersection at (15,10) → Add (15,10).
   • Edge (30,10)-(30,30): Inside → Add (30,10).
   • Edge (30,30)-(10,30): Intersection at (15,30) → Add (15,30).
   • Edge (10,30)-(10,10): Outside → Ignore.
   • Output: [(15,10), (30,10), (30,30), (15,30)].
3. Clip Against Right Edge (x=25):
   • Edge (15,10)-(30,10): Intersection at (25,10) → Add (25,10).
   • Edge (30,10)-(30,30): Outside → Ignore.
   • Edge (30,30)-(15,30): Intersection at (25,30) → Add (25,30).
   • Edge (15,30)-(15,10): Inside → Add (15,30).
   • Output: [(25,10), (25,30), (15,30)].
4. Final Clipped Polygon: Triangle with vertices (25,10), (25,30), (15,30).

Mermaid Diagram: Sutherland-Hodgman Steps

flowchart TD
    A[Input Polygon] --> B[Clip Against Left Edge]
    B --> C[Clip Against Right Edge]
    C --> D[Clip Against Bottom Edge]
    D --> E[Clip Against Top Edge]
    E --> F[Output Clipped Polygon]

Comparison: Cohen-Sutherland vs. Sutherland-Hodgman

4. Polygon Filling Algorithms

Filling polygons is essential for rendering solid shapes. Two key methods:

A. Scanline Polygon Filling

1. Process:
   • Sort polygon edges by y-coordinate.
   • For each scanline (horizontal line), compute intersections with polygon edges.
   • Fill pixels between intersection points.
2. Steps:
   • Active Edge Table (AET): Stores edges sorted by y-coordinate.
   • Intersection Calculation: For each scanline, find where edges cross it.
   • Pixel Plotting: Fill pixels between left and right intersections.
3. Worked Example: Fill Triangle with Vertices (10,10), (20,20), (30,10)
   • Scanline y=10: Intersections at x=10 and x=30 → Fill pixels from x=10 to x=30.
   • Scanline y=15: Intersections at x=12.5 and x=27.5 → Fill pixels from x=12.5 to x=27.5.
   • Repeat for all scanlines within the triangle’s y-range.

Mermaid Diagram: Scanline Filling Process

flowchart TD
    A[Sort Edges by Y] --> B[Initialize AET]
    B --> C{For Each Scanline}
    C -->|Yes| D[Compute Intersections]
    D --> E[Fill Pixels Between Intersections]
    E --> C

B. Seed-Fill Algorithm (Flood Fill)

1. Process:
   • Start with a seed pixel inside the polygon.
   • Use boundary checks to fill connected pixels.
2. Variants:
   • 4-connected: Fill adjacent pixels in 4 directions (up, down, left, right).
   • 8-connected: Fill adjacent pixels in 8 directions (including diagonals).
3. Worked Example: Fill Circle with Seed at (10,10)
   • Check pixel (10,10) is inside the circle.
   • Fill all connected pixels within the circle’s boundary.

Comparison: Scanline vs. Seed-Fill

5. Window-to-Viewport Transformation

Mathematical Formulation

To map a window (x_w, y_w) to a viewport (x_vp, y_vp), use: $$x_{vp}=x_{min}+\frac{(x_w-x_{wmin})\cdot (x_{vpmax}-x_{vpmin})}{x_{wmax}-x_{wmin}}$$ $$y_{vp}=y_{min}+\frac{(y_w-y_{wmin})\cdot (y_{vpmax}-y_{vpmin})}{y_{wmax}-y_{wmin}}$$ Example: Map window (20,20)-(90,70) to viewport (50,50)-(200,200).

• For (x_w, y_w) = (50, 50): $$x_{vp}=50+\frac{(50-20)\cdot (200-50)}{90-20}=100$$ $$y_{vp}=50+\frac{(50-20)\cdot (200-50)}{70-20}=100$$

Region Codes for Cohen-Sutherland

For the window (20,20)-(90,70), the region codes for a point (x,y) are:

• Left (L): 1 if x < 20, else 0.
• Right (R): 1 if x > 90, else 0.
• Bottom (B): 1 if y < 20, else 0.
• Top (T): 1 if y > 70, else 0.

Example: Point (10,10) → L=1, R=0, B=1, T=0 → Code 1001 (9).

Exam Tip

What Examiners Look For

1. Algorithm Steps: Show clear, numbered steps for Cohen-Sutherland or Sutherland-Hodgman. Include region codes and intersection calculations.
2. Mathematical Derivations: For window-viewport transformations, write the full formula and substitute values correctly.
3. Diagrams: Draw clipped lines/polygons with window/viewport boundaries. Label intersection points and region codes.
4. Edge Cases: Handle cases where:
   • Lines are horizontal/vertical (e.g., (10,10)-(10,30)).
   • Polygons are concave or self-intersecting.
   • Points lie exactly on window edges.
5. Comparisons: For questions like "Compare scanline and seed-fill," use a table and mention time complexity and use cases.
6. OpenGL/Practicals: If asked about OpenGL, mention:
   • glBegin(GL_POLYGON) and glVertex() for polygon filling.
   • glClipPlane() for clipping in OpenGL.

Common Pitfalls

• Incorrect Region Codes: Forgetting to set bits for all four edges (L, R, B, T).
• Floating-Point Errors: Rounding intersections incorrectly (e.g., (17.5, 15) vs. (17, 15)).
• Polygon Order: Sutherland-Hodgman assumes counter-clockwise vertex order. Reverse if needed.
• Scanline Gaps: Missing scanlines or miscomputing intersections (e.g., ignoring edges outside the y-range).

Model Answer Structure

For a 10-mark question like "Clip the line (10,10)-(60,30) using Cohen-Sutherland":

1. Define Window: State coordinates clearly (e.g., (15,15)-(25,25)).
2. Region Codes: Show binary and decimal codes for both points.
3. Trivial Check: State whether the line is accepted/rejected/trivially clipped.
4. Iterations: For each clipping edge, show:
   • Which edge is clipped (e.g., "left edge").
   • Intersection calculation (with formula).
   • Updated endpoint and new region code.
5. Final Output: Draw the clipped line and state its endpoints.

### Summary Table: Key Algorithms
| Algorithm               | Input          | Output               | Time Complexity | Key Idea                          |
|-------------------------|----------------|----------------------|-----------------|-----------------------------------|
| Cohen-Sutherland        | Line segment   | Clipped line         | O(1) per iter   | Region codes + iterative clipping |
| Sutherland-Hodgman      | Polygon        | Clipped polygon      | O(n) per edge   | Edge-by-edge clipping             |
| Scanline Filling        | Polygon edges  | Filled pixels        | O(n log n)      | Interpolate edges per scanline    |
| Seed-Fill               | Seed pixel     | Filled region        | O(n)            | Boundary flood from seed          |