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.