Clipping Algorithms in Computer Graphics: The Viewport Gatekeepers
A clipping algorithm determines which geometric primitives (points, lines, polygons, 3D objects) lie inside a defined viewing volume (the "clipping window" or "frustum"). Only the visible portions are passed to the rasterizer; everything outside is discarded. This is fundamental to rendering performance and correctness.
Core Principle
Define region → Test geometry against boundaries → Retain interior / Discard exterior / Generate new vertices at intersections.
Major Algorithm Families
- Point Clipping: Trivial inequality test (xmin ≤ x ≤ xmax, ymin ≤ y ≤ ymax).
- Line Clipping: Compute intersections with clip boundaries.
- Cohen–Sutherland: Outcodes (bitmasks) for trivial accept/reject; iterative clipping. Fast for coarse rejection.
- Liang–Barsky: Parametric line equation; solves for entry/exit parameters (tE, tL). More efficient, fewer intersections calculated.
- Sutherland–Hodgman: Actually a polygon clipper (see below), but often taught in line context.
- Polygon Clipping: Clip polygon edges against each boundary plane sequentially.
- Sutherland–Hodgman: Standard for convex clip windows. Iterates vertices through 4 clip planes (left, right, bottom, top). Output vertex list feeds next plane.
- Weiler–Atherton: Handles concave polygons / arbitrary clip regions. Tracks entering/exiting intersections.
- Greiner–Hormann: Robust for complex polygons, self-intersections.
- 3D Clipping (View Frustum): Clip against 6 planes (left, right, bottom, top, near, far).
- Cyrus–Beck: Parametric line clipping against convex polyhedra (frustum). Generalizes Liang–Barsky to 3D.
- Sutherland–Hodgman (3D): Extended to 6 planes for polygons.
Clipping is the gatekeeper of the pipeline. Without it, the GPU wastes cycles shading pixels that never appear. With it, the scene is surgically trimmed to the window of interest.