Liang–Barsky algorithm

The idea of the Liang-Barsky clipping algorithm is to do as much testing as possible before computing line intersections. Consider first the usual parametric form of a straight line:

${\displaystyle x=x_{0}+u(x_{1}-x_{0})=x_{0}+u\Delta x\,\!}$

${\displaystyle y=y_{0}+u(y_{1}-y_{0})=y_{0}+u\Delta y\,\!}$

A point is in the clip window, if

${\displaystyle x_{\text{min}}\leq x_{0}+u\Delta x\leq x_{\text{max}}\,\!}$

and

${\displaystyle y_{\text{min}}\leq y_{0}+u\Delta y\leq y_{\text{max}}\,\!}$,

which can be expressed as the 4 inequalities

${\displaystyle up_{k}\leq q_{k},\quad k=1,2,3,4\,\!}$,

where

${\displaystyle p_{1}=-\Delta x,q_{1}=x_{0}-x_{\text{min}}\,\!}$ (left)

${\displaystyle p_{2}=\Delta x,q_{2}=x_{\text{max}}-x_{0}\,\!}$ (right)

${\displaystyle p_{3}=-\Delta y,q_{3}=y_{0}-y_{\text{min}}\,\!}$ (bottom)

${\displaystyle p_{4}=\Delta y,q_{4}=y_{\text{max}}-y_{0}\,\!}$ (top)

To compute the final line segment:

1. A line parallel to a clipping window edge has ${\displaystyle p_{k}=0}$ for that boundary.
2. If for that ${\displaystyle k}$, ${\displaystyle q_{k}<0}$, the line is completely outside and can be eliminated.
3. When ${\displaystyle p_{k}<0}$ the line proceeds outside to inside the clip window and when ${\displaystyle p_{k}>0}$, the line proceeds inside to outside.
4. For nonzero ${\displaystyle p_{k}}$, ${\displaystyle u={\frac {q_{k}}{p_{k}}}}$ gives the intersection point.
5. For each line, calculate ${\displaystyle u_{1}}$ and ${\displaystyle u_{2}}$. For ${\displaystyle u_{1}}$, look at boundaries for which ${\displaystyle p_{k}<0}$ (outside -> in). Take ${\displaystyle u_{1}}$ to be the largest among ${\displaystyle \left(0,{\frac {q_{k}}{p_{k}}}\right)}$. For ${\displaystyle u_{2}}$, look at boundaries for which ${\displaystyle p_{k}>0}$ (inside -> out). Take ${\displaystyle u_{2}}$ to be the minimum of ${\displaystyle \left(1,{\frac {q_{k}}{p_{k}}}\right)}$. If ${\displaystyle u_{1}>u_{2}}$, the line is outside and therefore rejected.

See also

Algorithms used for the same purpose:

• Cyrus–Beck
• Nicholl–Lee–Nicholl
• Fast-clipping

References

• Liang, Y.D., and Barsky, B., "A New Concept and Method for Line Clipping", ACM Transactions on Graphics, 3(1):1-22, January 1984.
• Liang, Y.D., B.A., Barsky, and M. Slater, Some Improvements to a Parametric Line Clipping Algorithm, CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.
• James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 117.

External links

• http://hinjang.com/articles/04.html