Liang-Barsky Line Clipping

The ideas for clipping line of Liang-Barsky and Cyrus-Beck are the same. The only difference is Liang-Barsky algorithm has been optimized for an upright rectangular clip window. So we will study only the idea of Liang-Barsky.

Liang and Barsky have created an algorithm that uses floating-point arithmetic but finds the appropriate end points with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.

Let be the line which we want to study. The parametric equation of the line segment from gives x-values and y-values for every point in terms of a parameter tthat ranges from 0 to 1. The equations are

We can see that when t = 0, the point computed is P(x1,y1); and when t = 1, the point computed is Q(x2,y2).

Algorithm

1. Set and

2. Calculate the values of tL, tR, tT, and tB (tvalues).
   • if or ignore it and go to the next edge
   • otherwise classify the tvalue as entering or exiting value (using inner product to classify)
   • if t is entering value set ; if t is exiting value set

3. If then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1 + dy*tmax)

4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax, y1 + dy*tmax) are intersection between line and edge.

Examples

Example2 (line not passing through window)

From P. Asokarathinam -- see details 27.11.1996