Liang-Barsky Line Clipping

Theory

Express line segment in parametric form:

x = x1 + (x2 - x1) * m = x1 + dx * m 0.0 < m < 1.0

y = y1 + (y2 - y1) * m = y1 + dy * m

when m = 0.0 => x1, y1

when m = 1.0 => x2, y2

Any point P(x, y) on line segment which is inside window satisfies:

Xwmin <= x <=xwmax and Ywmin <= y <= ywmax

(Note that if Xwmin = x implies an intersection of the line with left boundary)

or in Parametric form

(1) Xwmin <= x1 + dx*m <= xwmax

(2) Ywmin <= y1 + dy*m <= ywmax

Now (1) can be rewritten as

-dx * m <= x1 xwmin left boundary

dx * m < xwmax x1 right boundary

similarly (2) can be written as

-dy * m < y1 ywmin bottom boundary

dy * m < ywmax y1 top boundary

Above are all of the form:

Pi * m <qi i="1," 2, 3, 4

where:

P1 = -dx q1 = x1 - Xwmin -- Left

P2 = dx q2 = Xwmax - x1 -- Right

P3 = -dy q3 = y1 - Ywmin -- Bottom

P4 = dy q4 = Ywmax - y1 -- Top

ASIDE

Now note that if a line is parallel to Left / Right boundary then

dx = 0 -> P1 = P2 = 0

Similarly if a line is parallel to Top / Bottom then

dy = 0 -> P3 = P4 = 0

Now if P1 = 0

if (q1 = x1 - Xwmin) <0 then x1 < xwmin and line is outside of window

then reject

Similarly:

if P2 = 0 and (q2 = Xwmax - x1) < 0 then x1> Xwmax -> reject.

if P3 = 0 and (q3 = y1 - Ywmin) < 0 then y1 <& ywmin> reject.

if P4 = 0 and (q4 = Ywmax - y1 ) < 0 then y1> Ywmax -> reject.

So as a general rule: if Pi = 0 and qi < 0 reject the lines, else retain lines for further consideration.

Look at case

P1 = -dx < 0

-dx = - (x2 - x1) < 0

x1 - x2 < 0 x1 < x2

so if extend line segment it goes from Left to Right or from outside of Left boundary to inside (see figure)

Now if P1 < 0 then p2> 0, so extended line segment goes from inside of Right boundary to outside. Similarly if P3 = -dy = -(y2 - y1) = (y1 - y2) <0 then y1 < y2 and line goes from outside of bottom boundary to inside and if P4 > 0, line goes from inside of top boundary to outside.

Another way of looking at above.

General inequality :

Pi * m < qi> mi < qi / pi

if Pi < 0 (outside> inside) -> mi > qi / |Pi|

so point of intersection ( mi = qi / Pi ) is the minimum value for which the line is on the visible side of the boundary. Since m increases along line, the direction of the line is from the OUTSIDE (invisible) to the INSIDE (visible).

Similarly if Pi > 0 -> mi <* qi / pi or point of intersection is maximum value of mi. then the direction of line is from inside to outside.

Now remember that for our line segment: 0.0 < m < 1.0

Now look at lines proceeding from outside to inside

Compute intersection at XL, YT

The visible part of line starts at largest such value of m.

same is true, visible portion starts at largest value of m

Remember: m > 0.0 so can express as (for cases of Pi < 0 i.e. outside>inside)

m1 = MAX ( {qi / Pi | Pi < 0, i="1," 2, 3, 4} U {0} )

Reverse above endpoints for Pi > 0 and get

m2 = MIN ( {qi / Pi | Pi > 0, i = 1, 2, 3, 4} U {1} )

Now if there is a visible segment it corresponds to the parametric interval

m1 <= m <= m2 and m1 <= m2

So if m1 > m2 reject line else compute visible endpoints from m1, m2.


Go back to previous screen
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org