Computer Graphics: Clipping Algorithms Infographic

What is Clipping?

In computer graphics, Clipping is the process of determining which parts of a geometric primitive (like a point, line, or polygon) fall within the viewing area (the viewport or window) and discarding the rest. This is crucial for optimization—why calculate pixels for objects the user can't see?

The Viewport: Usually a rectangle defined by $(X_{min}, Y_{min})$ and $(X_{max}, Y_{max})$.

1. Cohen-Sutherland Line Clipping

The most popular algorithm for line clipping. It uses a 4-bit region code to quickly determine if a line is fully inside, fully outside, or needs clipping.

The Logic (Outcodes)

The screen is divided into 9 regions using 4 bits: Top, Bottom, Right, Left.

1001
(Top-Left)

1000
(Top)

1010
(Top-Right)

0001
(Left)

0000
(Window)

0010
(Right)

0101
(Bot-Left)

0100
(Bottom)

0110
(Bot-Right)

Trivial Accept: Both endpoints have code 0000 (OR operation = 0).
Trivial Reject: Both endpoints share a set bit (AND operation != 0).
Else: Clip against the boundary and repeat.

JavaScript Implementation

const INSIDE = 0; // 0000
const LEFT = 1;   // 0001
const RIGHT = 2;  // 0010
const BOTTOM = 4; // 0100
const TOP = 8;    // 1000

function computeCode(x, y) {
  let code = INSIDE;
  if (x < xmin) code |= LEFT;
  else if (x > xmax) code |= RIGHT;
  if (y < ymin) code |= BOTTOM;
  else if (y > ymax) code |= TOP;
  return code;
}

Interactive Demo

Click "Regenerate" to create random lines. Red lines are rejected, Green are accepted/clipped parts, Grey are the parts discarded.

2. Liang-Barsky Line Clipping

A more efficient algorithm based on parametric equations. It avoids the repetitive division operations found in Cohen-Sutherland.

The Math

A line is defined as $P(t) = P_1 + t(P_2 - P_1)$ where $0 \le t \le 1$.

We solve four inequalities of the form $p_k \cdot t \le q_k$.

The values $t_E$ (entering) and $t_L$ (leaving) are calculated. If the interval $[t_E, t_L]$ is valid, the line is drawn.

Code Logic

function clipLineLB(x1, y1, x2, y2) {
  let t0 = 0, t1 = 1;
  let dx = x2 - x1, dy = y2 - y1;
  // Checks 4 boundaries (p, q calculations)
  // Updates t0 (max of entering)
  // Updates t1 (min of leaving)
  
  if(t0 > t1) return null; // Reject
  
  // New coords
  nx1 = x1 + t0 * dx;
  ny1 = y1 + t0 * dy;
  nx2 = x1 + t1 * dx;
  ny2 = y1 + t1 * dy;
}

Interactive Demo

3. Sutherland-Hodgman Polygon Clipping

Clipping polygons is harder because clipping a convex polygon can result in more vertices than you started with. This algorithm clips the entire polygon against one edge of the window at a time.

The Pipeline

The output vertex list of one stage becomes the input of the next.

Input Polygon $\to$ Clipper (Left)
$\to$ Clipper (Right)
$\to$ Clipper (Bottom)
$\to$ Clipper (Top) $\to$ Final Polygon

Intersection Rule: If going from Inside $\to$ Outside: Add Intersection.
If going from Outside $\to$ Inside: Add Intersection & Destination.
If Inside $\to$ Inside: Add Destination.

Algorithm Steps

for each clipEdge in Window:
  outputList = []
  for each vertex in inputList:
    curr = vertex
    prev = previousVertex
    
    if (Inside - Inside) add curr
    if (Inside - Out) add intersect
    if (Out - Inside) add intersect, curr
    if (Out - Out) do nothing
    
  inputList = outputList

Interactive Demo

The Grey shape is the original random polygon. The Pink shape is the result after clipping against the white box.