Clipping Algorithms: Line & Polygon Clipping, Z-Buffer vs Painter’s

TAKEAWAYS:

• Clipping algorithms crop objects to a defined window (e.g., a game’s screen or a CAD viewport) by computing intersections with window edges.
• Cohen-Sutherland assigns 4-bit region codes to line endpoints and iteratively clips segments outside the window.
• Sutherland-Hodgeman clips polygons by traversing vertices and computing intersections with window edges, handling concave/self-intersecting polygons.
• Z-buffer (depth buffering) and Painter’s algorithm (painter’s sort) solve hidden surface removal but produce different results for overlapping transparent/translucent surfaces.
• Back-face culling discards polygons facing away from the viewer, improving rendering speed but failing for complex scenes.
• Master region codes, intersection calculations, and edge traversal for exam questions requiring step-by-step traces.

1. Introduction to Clipping

Clipping is the process of removing parts of objects that lie outside a defined viewport (window). This is critical in:

• Computer games (e.g., Pathao driver UI showing only relevant map regions).
• CAD/CAM systems (e.g., AutoCAD hiding parts of a 3D model outside the current view).
• Virtual reality (e.g., Oculus clipping objects beyond the user’s field of view).

Why clip?

• Performance: Avoid rendering invisible pixels.
• Correctness: Ensure only visible parts are displayed.
• Realism: Simulate cameras, windows, or viewports.

2. Line Clipping: Cohen-Sutherland Algorithm

Key Idea

Clip a line segment between two endpoints $(x_1,y_1)$ and $(x_2,y_2)$ against a rectangular window defined by $(x_{\text{min}},y_{\text{min}})$ and $(x_{\text{max}},y_{\text{max}})$.

How It Works

1. Assign region codes to each endpoint (4 bits: left, right, bottom, top).

   • Example: For a window $A(20,20)$, $B(90,20)$, $C(90,70)$, $D(20,70)$:
     • Left: $x<x_{\text{min}}$ → bit 1 set.
     • Right: $x>x_{\text{max}}$ → bit 2 set.
     • Bottom: $y<y_{\text{min}}$ → bit 3 set.
     • Top: $y>y_{\text{max}}$ → bit 4 set.
   • Region code for $(x,y)$: $$\text{code}=\{\begin{array}{ll}0001& \text{if }x<x_{\text{min}}\\ 0010& \text{if }x>x_{\text{max}}\\ 0100& \text{if }y<y_{\text{min}}\\ 1000& \text{if }y>y_{\text{max}}\end{array}$$ (Combine bits if multiple conditions are true.)

2. Trivial acceptance/rejection:

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

3. Iterative clipping:

   • While neither endpoint is trivial:
     • Pick the endpoint with a non-zero code.
     • Compute intersection with the closest window edge.
     • Update the endpoint and its code.
     • Repeat until trivial or rejection.

Worked Example: Clip Line from (10,10) to (80,80) Against Window (30,30)-(70,70)

1. Region codes:
   • $P_1(10,10)$: Left (0001) + Bottom (0100) = 0101.
   • $P_2(80,80)$: Right (0010) + Top (1000) = 1010.
2. Bitwise AND: 0101 & 1010 = 0000 → Not trivial.
3. Clip $P_1$:
   • Closest edge: bottom ($y=30$).
   • Intersection: $y=30$, $x=10+(80-10)\times (30-10)/(80-10)=20$.
   • New $P_1=(20,30)$, code = 0000 (inside).
4. Clip $P_2$:
   • Closest edge: right ($x=70$).
   • Intersection: $x=70$, $y=10+(80-10)\times (70-10)/(80-10)=60$.
   • New $P_2=(70,60)$, code = 0000.
5. Result: Clipped line from $(20,30)$ to $(70,60)$.

Advantages/Disadvantages

3. Polygon Clipping: Sutherland-Hodgeman Algorithm

Key Idea

Clip a polygon against a rectangular window by traversing its edges and computing intersections.

How It Works

1. Initialize: Start with the first vertex of the polygon.
2. Clip against each window edge (left, right, bottom, top):
   • For each edge of the window, traverse the polygon vertices.
   • If a vertex is inside the edge, add it to the output list.
   • If a vertex is outside, compute intersection with the edge and add it.
3. Repeat for all four edges.

Worked Example: Clip Polygon PQRSTU Against Window (15,20)-(60,50)

Vertices: $P(10,30)$, $Q(25,35)$, $R(35,50)$, $S(60,30)$, $T(45,28)$, $U(40,15)$.

Step 1: Clip against left edge ($x=15$)

• Start with $P(10,30)$ (outside).
• Intersection with $PQ$: $x=15$, $y=30+(35-30)\times (15-10)/(25-10)=31$.
• Add $(15,31)$ to output.
• $Q(25,35)$ is inside → add to output.
• Continue for all edges.

Final clipped polygon: $(15,31)$, $(25,35)$, $(35,50)$, $(60,30)$, $(45,28)$, $(15,24)$.

Advantages/Disadvantages

4. Hidden Surface Removal: Z-Buffer vs Painter’s Algorithm

Z-Buffer Algorithm

• Idea: Store depth (Z-coordinate) of each pixel. For each pixel, keep the closest object.
• Steps:
  1. Initialize a Z-buffer with infinity.
  2. For each object, project its pixels to screen space.
  3. If pixel’s Z < stored Z, update framebuffer and Z-buffer.
• Example: Rendering a teapot behind a cube.
  • The cube’s pixels will overwrite the teapot’s where they overlap.

Painter’s Algorithm

• Idea: Sort objects by depth (far to near) and render in order.
• Steps:
  1. Sort polygons by Z-coordinate (farthest first).
  2. Render each polygon, overwriting previous ones.
• Example: Overlapping transparent windows (e.g., WhatsApp chat vs. YouTube video).

Comparison

Scenario Where Results Differ

Scene: A semi-transparent red cube overlaps a blue sphere.

• Z-buffer: Blends colors based on depth.
• Painter’s: Renders the sphere first, then the cube, hiding parts of the sphere entirely.

graph LR
    A["Z-Buffer"] -->|"Blends colors"| B["Red + Blue = Purple"]
    C["Painter's"] -->|"Renders sphere first"| D["Blue hidden under red"]

5. Back-Face Removal

Key Idea

Discard polygons facing away from the viewer (back-faces) to improve rendering speed.

• Test: Compute the normal vector of the polygon. If it points away from the viewer, discard it.
• Example: A 3D cube has 3 visible faces and 3 back-faces.

Advantages/Disadvantages

6. Real-World Applications

1. eSewa App (Nepal)

• Clipping: The app’s UI clips irrelevant parts of the map (e.g., hiding Kathmandu’s outskirts when zoomed into Thamel).
• Hidden Surface: Uses Z-buffer to render 3D buttons without overlap artifacts.

2. Daraz Order Queue

• Line Clipping: The "Your Orders" section clips completed orders outside the visible list.
• Polygon Clipping: Product images are clipped to fit thumbnails.

3. Kathmandu Traffic Simulation

• Painter’s Algorithm: Simulates traffic by rendering far roads first, then closer ones.
• Z-Buffer: Used in 3D traffic models to show vehicles at different elevations.

4. Ncell’s 4G Network Visualization

• Polygon Clipping: Displays only the active tower coverage area on a map.
• Back-Face Removal: Hides the "back" of 3D tower models.

7. Exam Tips

1. For Cohen-Sutherland:

   • Always show region codes and intersection calculations.
   • Label diagrams clearly (e.g., "Clipped segment").
   • Use small numbers (e.g., window (20,20)-(90,70)) for easy computation.

2. For Sutherland-Hodgeman:

   • Trace the algorithm step-by-step for each window edge.
   • Highlight intersection points in diagrams.
   • Mention if the polygon is concave (affects clipping).

3. For Z-Buffer vs Painter’s:

   • Compare output differences for transparent/overlapping objects.
   • Draw a side-by-side diagram of the two results.

4. Common Pitfalls:

   • Forgetting to update the output list during clipping.
   • Miscomputing intersection points (use parametric equations).
   • Confusing 4-connected vs 8-connected in flood fill (not in this unit, but related).

5. Diagrams Are Mandatory:

   • Always include a clipped line/polygon with original and clipped parts.
   • For Z-buffer/Painter’s, show layered rendering.

8. Practice Questions

1. Clip the line from $(5,5)$ to $(100,100)$ against the window $(30,30)-(70,70)$ using Cohen-Sutherland.
2. Use Sutherland-Hodgeman to clip the polygon $(10,10)$, $(50,10)$, $(50,50)$, $(10,50)$ against the window $(20,20)-(40,40)$.
3. Explain why the Z-buffer would render a semi-transparent glass cube differently than Painter’s algorithm.
4. Derive the region code for a point $(x,y)$ outside the window $(x_{\text{min}},y_{\text{min}})-(x_{\text{max}},y_{\text{max}})$.