Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 50 ยท Clipping

Liang-Barsky Line Clipping

Learn the Liang-Barsky algorithm: parametric lines, the p and q values, entering and leaving edges, and how it compares to Cohen-Sutherland, with a live clipper.

The Cohen-Sutherland algorithm clips a line by repeatedly cutting it and re-testing the new endpoint. It works, but it may compute several intersections that are thrown away again. The Liang-Barsky algorithm takes a different route. It describes the line with a single parameter u, works out for each window edge where along the line the edge is crossed, and then keeps the one stretch of u values that survives all four edges. Every edge is handled once, and only the final two intersections are turned into coordinates.

This lesson derives the four "p and q" values, shows how they decide whether a line is entering, leaving, parallel or hopelessly outside, walks through a full example by hand, and then lets you drag a line around a live clipping window.

The parametric form of a line

A line segment from P0 = (x0, y0) to P1 = (x1, y1) can be written as a function of one number u:

TEXT
x(u) = x0 + u * dx
y(u) = y0 + u * dy        where dx = x1 - x0 and dy = y1 - y0

At u = 0 you are at P0, at u = 1 you are at P1, and values in between are points on the segment. Values below 0 or above 1 lie on the infinite line beyond the segment, which we do not want.

The clipping window is the rectangle xmin <= x <= xmax, ymin <= y <= ymax. A point of the line is inside when all four inequalities hold. Substitute the parametric form into each of them:

TEXT
xmin <= x0 + u*dx        ->   -dx * u  <=  x0 - xmin
x0 + u*dx <= xmax        ->    dx * u  <=  xmax - x0
ymin <= y0 + u*dy        ->   -dy * u  <=  y0 - ymin
y0 + u*dy <= ymax        ->    dy * u  <=  ymax - y0

All four have the same shape, p * u <= q, so Liang and Barsky give them names:

k Edge p q
1 left -dx x0 - xmin
2 right dx xmax - x0
3 bottom (ymin) -dy y0 - ymin
4 top (ymax) dy ymax - y0

On a canvas, where y grows downward, ymin is simply the smaller y value, which appears at the top of the window. The algebra does not care which one you draw on top.

What p and q tell you

For each edge you have one inequality p * u <= q. Its meaning depends on the sign of p:

  • p = 0: the line is parallel to this edge. The inequality becomes 0 <= q. If q < 0 the whole line is on the wrong side of the edge, so it is rejected immediately. If q >= 0 this edge cannot clip anything.
  • p < 0: the line goes from the outside to the inside across this edge (it is entering). Dividing by a negative number flips the inequality, so u >= q / p. The ratio r = q / p is a lower bound for u.
  • p > 0: the line goes from the inside to the outside (it is leaving). Here u <= q / p, so r = q / p is an upper bound for u.

Start with the full segment, u1 = 0 and u2 = 1. Every entering edge may raise u1; every leaving edge may lower u2:

TEXT
if p < 0:  u1 = max(u1, q / p)
if p > 0:  u2 = min(u2, q / p)

After all four edges, if u1 > u2 there is no value of u that satisfies everything: the segment misses the window and is rejected. Otherwise the visible part runs from u = u1 to u = u2, and only now do you compute the two endpoints with the parametric formulas.

flowchart TD
  S["u1 = 0, u2 = 1"] --> E["for each edge k: p, q"]
  E --> P0{"p = 0?"}
  P0 -->|"yes"| Q{"q < 0?"}
  Q -->|"yes"| REJ["reject"]
  Q -->|"no"| NEXT["next edge"]
  P0 -->|"no"| SIGN{"sign of p"}
  SIGN -->|"p < 0 (entering)"| U1["u1 = max(u1, q/p)"]
  SIGN -->|"p > 0 (leaving)"| U2["u2 = min(u2, q/p)"]
  U1 --> NEXT
  U2 --> NEXT
  NEXT --> DONE{"u1 > u2?"}
  DONE -->|"yes"| REJ
  DONE -->|"no"| ACC["accept: draw u1 to u2"]

The whole algorithm: tighten the interval [u1, u2] edge by edge, then test it once.

A worked example

Take the window xmin = 20, xmax = 80, ymin = 20, ymax = 60 and the segment from (0, 30) to (100, 50). So dx = 100 and dy = 20.

Edge p q r = q / p Effect
left -100 0 - 20 = -20 0.2 entering: u1 = max(0, 0.2) = 0.2
right 100 80 - 0 = 80 0.8 leaving: u2 = min(1, 0.8) = 0.8
bottom -20 30 - 20 = 10 -0.5 entering: u1 = max(0.2, -0.5) = 0.2
top 20 60 - 30 = 30 1.5 leaving: u2 = min(0.8, 1.5) = 0.8

We end with u1 = 0.2 and u2 = 0.8, so the visible segment goes from (0 + 0.2*100, 30 + 0.2*20) = (20, 34) to (0 + 0.8*100, 30 + 0.8*20) = (80, 46). The line crosses the left and right edges and never touches the top or bottom, which the ratios (-0.5 and 1.5, both outside [0, 1]) reveal at once.

The algorithm in code

The function below returns null for a rejected line, or the clipped endpoints. It also fills a steps array so you can see every p, q and r afterwards.

JavaScript
function liangBarsky(x0, y0, x1, y1, win, steps = []) {
  const dx = x1 - x0;
  const dy = y1 - y0;
  const p = [-dx, dx, -dy, dy];
  const q = [x0 - win.xmin, win.xmax - x0, y0 - win.ymin, win.ymax - y0];
  let u1 = 0;
  let u2 = 1;

  for (let k = 0; k < 4; k++) {
    if (p[k] === 0) {
      if (q[k] < 0) return null;       // parallel and outside
      continue;                         // parallel and inside this edge
    }
    const r = q[k] / p[k];
    if (p[k] < 0) u1 = Math.max(u1, r);
    else u2 = Math.min(u2, r);
    if (u1 > u2) return null;
  }
  return { x0: x0 + u1 * dx, y0: y0 + u1 * dy,
           x1: x0 + u2 * dx, y1: y0 + u2 * dy, u1, u2 };
}

Exiting early with u1 > u2 inside the loop is allowed and saves work, because u1 only grows and u2 only shrinks.

Try it: drag the endpoints

In the clipper below, drag either end of the line (the two small circles). The part inside the window is drawn thick and blue; the part that was clipped away is drawn thin and grey. The text underneath lists p, q and r for each of the four edges, so you can check the table from the worked example against your own lines.

Liang-Barsky clipper

Drag one end into the window and the other far outside: you will see only one of u1 and u2 change from its default. Drag the line so that it runs along the left of the window, and u1 > u2 appears with no intersection computed at all.

Liang-Barsky versus Cohen-Sutherland

Both algorithms give identical pictures. They differ in how they get there.

Cohen-Sutherland Liang-Barsky
Idea Region codes decide accept or reject; cut at one edge, then repeat Intersect the parameter interval with one constraint per edge
Intersections computed Up to 4 per line, each with new x and y Only 2 at the very end
Trivial accept/reject Very fast with bit codes Needs the p/q loop (a few divisions)
Best case Most lines wholly inside or outside Lines that are often partly inside
Generalises to 3D (6-bit codes), but gets awkward Arbitrary convex windows (Cyrus-Beck) and 3D clip volumes

If most of your lines are trivially inside or outside, the cheap bit tests of Cohen-Sutherland win. If many lines cross the window, Liang-Barsky does fewer divisions and never recomputes endpoints. Its idea of tightening a parameter interval generalises to the Cyrus-Beck algorithm, which clips against any convex polygon, and is the basis of clipping in many 3D pipelines.

Check the numbers yourself

The second example runs the function on several segments, including a rejected one, a horizontal one (p = 0) and a segment that lies completely inside. Edit the lines array to try your own.

JS Clipping a batch of lines

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The first line reproduces the table above: u = [0.2, 0.8] and the endpoints (20, 34) and (80, 46).

Practical notes

  • Division by zero is avoided by the p = 0 test. Do it before dividing, never after.
  • Floating point is fine. Unlike Bresenham-style code, clipping happens before rasterization, so it is normal to work in floats and round only when you draw.
  • Partial results are free. Because you keep u1 and u2, you can also interpolate colors or texture coordinates along the clipped line with the same two numbers.
  • Rays and lines. For an infinite line or a ray, start with u1 = -infinity or 0 and u2 = +infinity. The same loop works.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the Liang-Barsky algorithm, what does p < 0 for an edge mean?

    A negative p means the line moves from the outside of that edge to the inside, so q/p raises the lower bound u1.
  2. 2. For a line with p = 0 and q < 0 on some edge, what happens?

    p = 0 means the line is parallel to the edge, and q < 0 means it is on the outside of it, so no part of the line can be inside.
  3. 3. When is a line rejected after the loop over all four edges?

    If the largest entering value exceeds the smallest leaving value, the line is inside all edges at no common parameter, so no part is visible.
  4. 4. What is the main advantage of Liang-Barsky over Cohen-Sutherland?

    Liang-Barsky only narrows a parameter interval and turns it into coordinates once; Cohen-Sutherland may compute and discard several intermediate intersections.

Summary

  • A segment is written as P(u) = P0 + u * (P1 - P0) with 0 <= u <= 1, and each window edge gives one inequality p * u <= q.
  • p < 0 means entering (raises u1 = max(u1, q/p)), p > 0 means leaving (lowers u2 = min(u2, q/p)), and p = 0 means parallel (reject when q < 0).
  • If u1 > u2 the line is rejected; otherwise the visible part is P(u1) to P(u2).
  • Only two intersection points are ever computed, and the idea extends to Cyrus-Beck clipping and 3D clip volumes.

Next, we clip whole shapes instead of single lines: Polygon Clipping: Sutherland-Hodgman.