Liang – Barsky line clipping algorithm is faster line clipper algorithm based on analysis of the parametric equation of a line segment.
Parametric equation of line segment:
X = X1 + U ΔX
Y = Y1 + U ΔY
Where, ΔX = X2 – X1 and ΔY = Y2 – Y1
Using these equations Cyrus and Beck developed an algorithm that is generated more efficient than the Cohen Sutherland algorithm.
Later Liang and Barsky independently devised an even faster parametric line clipping algorithm.
In the Liang-Barsky approach we first the point clipping condition in parametric form:
$$Xmin ≤ X1 + U ΔX ≤ Xmax$$
$$Ymin ≤ Y1 + U ΔY ≤ Ymax$$
Each of these four inequalities can be expressed as:
μpk ≤ qk for k=1,2,3,4
The parameters p & q are defined as:
p1 = -ΔX and q1 = X1 – Xmin (Left Boundary)
p2 = ΔX and q2 = Xmax - x1 (Right Boundary)
P3 = -ΔY and q3 = Y1- Ymin (Bottom Boundary)
P4 = ΔY and q4 = Ymax - y1 (Top Boundary)
If a line is parallel to a view window boundary, the p value for that boundary is zero.
If the line is parallel to the X axis, for example then p1 and p2 must be zero.
Given pk = 0, if qk < 0 then line is trivially invisible because it is outside view window.
Given pk = 0, if qk > 0 then the line is inside the corresponding window boundary.
When pk < 0, as U increase line goes from the outside to inside i.e. entering.
When pk > 0, line goes from inside to outside i.e. exiting.
If there is a segment of line inside the clip region, a sequence of infinite line intersections must go entering, entering, exiting, and exiting as shown in figure 24.
Algorithm:
Set $U_{min} = 0$ and $U_{max} = 1$
Calculate the value of t:
- If $ U \lt U_{min} or $U > U_{max}$ ignore it.
- Otherwise classify the U values as entering or exiting.
**If Umin\ltUmax then draw a line from:**
$$(X_1 + ΔX. Umin, Y1 + ΔY. Umin) \ \ to \ \ (X_1 + ΔX. Umax, Y_1 + ΔY. Umax)$$
Example:
Given:
$(X_{min}, Y_{min}) = (10, 10)$ and $(X_{max}, Y_{max}) = (50, 50)$
P1 (30, 60) and P2 = (60, 25)
Solution:
Set Umin = 0 and Umax = 1
$U_{Left}$ = q1 / p1
= X1 – Xmin / - Δ X
= 30 – 10 / - (60 - 30)
= 20 / - 30
= -0.67
$U_{Right}$ = q2 / p2
= Xmax – X1/ ΔX
= 50 – 30 / (60 - 30)
= 20 / 30
= 0.67
$U_{Bottom}$ = q3 / p3
= Y1 – Ymin / - ΔY
= 60 – 10 / - (25 – 60)
= 50 / 35
= 1.43
$U_{Top}$ = q4 / p4
= Ymax – Y1 / ΔY
= 50 – 60 / (25 - 60)
= -10 / - 35
= 0.29
Since $U_{Left} = -0.57$ which is less than Umin. Therefore we ignore it.
Similarly $U_{Bottom} = 1.43$ which is greater than Umax. So we ignore it.
$U_{Right} = U_{min}$ = 0.67 (Entering)
$U_{Top} = U_{max}$ = 0.29 (Exiting)
We have $U_{Top}$ = 0.29 and $U_{Right}$ = 0.67
Q – P = (ΔX, ΔY) = (30, -35)
Since Umin>Umax, there is no line segment to draw.
and 2 others joined a min ago.
teamques10
★ 68k