The Liang-Barsky algorithm is a line clipping algorithm. This algorithm is more efficient than Cohen–Sutherland line clipping algorithm and can be extended to 3-Dimensional clipping. This algorithm is considered to be the faster parametric line-clipping algorithm. The following concepts are used in this clipping:
- The parametric equation of the line.
- The inequalities describing the range of the clipping window which is used to determine the intersections between the line and the clip window.
The parametric equation of a line can be given by,
X = x1 + t(x2-x1)
Y = y1 + t(y2-y1)
Where, t is between 0 and 1.
Then, writing the point-clipping conditions in the parametric form:
xwmin<= x1 + t(x2-x1) <= xwmax
ywmin<= y1 + t(y2-y1) <= ywmax
The above 4 inequalities can be expressed as,
tpk<= qk
Where k = 1, 2, 3, 4 (correspond to the left, right, bottom, and top boundaries, respectively).
The p and q are defined as,
p1 = -(x2-x1), q1 = x1 - xwmin (Left Boundary)
p2 = (x2-x1), q2 = xwmax - x1 (Right Boundary)
p3 = -(y2-y1), q3 = y1 - ywmin (Bottom Boundary)
p4 = (y2-y1), q4 = ywmax - y1 (Top Boundary)
When the line is parallel to a view window boundary, the p value for that boundary is zero.
When pk < 0, as t increase line goes from the outside to inside (entering).
When pk > 0, line goes from inside to outside (exiting).
When pk = 0 and qk < 0 then line is trivially invisible because it is outside view window.
When pk = 0 and qk > 0 then the line is inside the corresponding window boundary.
Using the following conditions, the position of line can be determined:
CONDITION | POSITION OF LINE |
pk = 0 | parallel to the clipping boundaries |
pk = 0 and qk < 0 | completely outside the boundary |
pk = 0 and qk >= 0 | inside the parallel clipping boundary |
pk < 0 | line proceeds from outside to inside |
pk > 0 | line proceeds from inside to outside |
Parameters t1 and t2 can be calculated that define the part of line that lies within the clip rectangle.
When,
- pk < 0, maximum(0, qk/pk) is taken.
- pk > 0, minimum(1, qk/pk) is taken.
If t1 > t2, the line is completely outside the clip window and it can be rejected. Otherwise, the endpoints of the clipped line are calculated from the two values of parameter t.
Algorithm –
- Set tmin=0, tmax=1.
- Calculate the values of t (t(left), t(right), t(top), t(bottom)),
(i) If t <tmin ignore that and move to the next edge.
(ii) else separate the t values as entering or exiting values using the inner product.
(iii) If t is entering value, set tmin = t; if t is existing value, set tmax = t. - If tmin <tmax, draw a line from (x1 + tmin(x2-x1), y1 + tmin(y2-y1)) to (x1 + tmax(x2-x1), y1 + tmax(y2-y1))
- If the line crosses over the window, (x1 + tmin(x2-x1), y1 + tmin(y2-y1)) and (x1 + tmax(x2-x1), y1 + tmax(y2-y1)) are the intersection point of line and edge.
This algorithm is presented in the following code. Line intersection parameters are initialised to the values t1 = 0 and t2 = 1.
Numerical :-
Given :🡪
P1 = (2,7)
P2 = (8 , 12)
(xwmin , ywmin) = (5,5)
(xwmin , ywmax) = (5,10)
xwmax,ywmin) = (10,5)
(xwmax , Ywmin) = (10, 10)
Δx = 8 – 2=6
Δy = 12 - 7 = 5
P1 =- Δx=-6 q1= x -xwmin = 2-5 = -3
P2 = Δx = 6q2 = Xwmax– x1 = 10 - 2 = 8
P3 = - Δy = -5 q3 = y1 -Ywmin= 7-5 = 2
P4 = Δy = 5 q4 =ywmax - Y1 = 10 - 7=3
r1 = q1 / p1 = -3 / -6 = ½
r2 = q2 / p2 = 8/6 = 4/3
r3 = q3/p3 = 2/-5 = -2/5
r4 = q4/p4 = 3/5 = 3/5
or(pi, < 0) u1 = Max (1/2 , -2/5,07) = ½
or (pi> 0) u2 = Min(4/3 , 3/5 ,1) = 3/5
u1 < u2
x1` = x1 + u1Δx = 2 + ½ *6 = 5
x2` = x1 + u2Δx = 2 + 3/5 *6 = 5.6
y1` = y1 + u1Δy = 7 + ½ *6 = 9.5
y2` = y1 + u2Δy = 7 + 3/5 *5 = 10
Coordinate of clipped lines will be (5,9.5) and (5.6 , 10).
Q: Apply the Liang-Barsky to clip the line segment from A(3,7) to B(8,10) against the regular rectangular window P(1,2) , Q(9,2) ,
R(9,8) and S(1,8).
Ans:- [AKTU 2014-15 7M]
(x1,y1) = (3,7)
(x2 , y2) = (8,10)
Δx = x2 – x1 = 8-3 = 5
Δy = y2 – y1 = 10-7 = 3
P1 = -Δx = -5 q1 = x1 - xmin = 3-1 = 2
P2 = Δx = 5 q2 = xmax - x1 = 9 -3 = 6
P3 = -Δy = -3 q3 = y1 - ymin = 7 - 2 = 5
P4 = Δy = -3 q4 = ymax– y1 = 8 - 7 = 1
r1 = q1/p1 = 2/-5 = -0.4
r2 = q2/p2 = 6/5 = 1.2
r3 = q3/p3 = 5/-3 = -1.66
r4 = q4/p4 = 1/3 = 0.33
u1 = max(-0.4 , -1.66 , 0) = 0
u2 = min(1,1.2,0.33) = 0.33
u1<u2 endpoints are visible
x1` = x1 + (Δx * u1) = 3 +(5*0) = 3
y1` = y1 + (Δy * u1) = 7 +(3*0) = 7
x2` = x1 + (Δx * u2) = 3 +(5*0.33) = 4.65
y2` = y1 + (Δy * u2) = 7 +(3*0.33) = 7.99
Visible line will be P1(3,7) and P2(4.65 , 7.99).
0 Comments