Cyrus Beck Line Clipping algorithm:
Cyrus Beck Line Clipping algorithm is used to clip 2D/3D lines against convex polygon/polyhedron.
• Cyrus Beck Line clipping algorithm is actually, a parametric line-clipping algorithm.
• The term parametric means that we require finding the value of the parameter t in the parametric representation of the line segment for the point at that the segment intersects the clipping edge.
• Consider line segment P1P2. The parametric equation of line segment P1P2 is,
P(t) = P1 + t(P2 – P1) … (1)
Where, t value defines a point on the line going through P1 and P2.
0 <= t <= 1 defines line segment between P1 and P2.
If t = 0 then P(0) = P1.
If t = 1 then P(1) = P2.
• Consider a convex clipping region R, f is a boundary point of the convex region R and n is an inner normal for one of its boundaries as shown in Fig
• Then we can distinguish in which region a point lie by looking at the value
of the dot product
n.[P(t) – f ], as shown in Fig.
• If dot product is negative i.e.,
n.[P(t) – f ] < 0 … (2)
then the vector P(t) – f ] is pointed away from the interior of R.
• If dot product is zero i.e.,
n.[P(t) – f ] = 0 … (3)
then the vector P(t) – f ] is pointed parallel to the plane containing f and
perpendicular to the normal.
• If dot product is positive i.e.,
n.[P(t) – f ] > 0 … (4)
then the vector P(t) – f ] is pointed towards the interior of R.
Dot products for three points inside, outside and on the boundary of the
clipping region
• As shown in Fig. if the point f lies in the boundary plane or edge for which
n is the inner normal, then that point t on the line P(t) which satisfies,
n.[P(t) – f ] = 0 condition is the intersection of the line with the
boundary edge.
• To get the formal statement of the Cyrus-Beck algorithm we substitute
value of P(t) in equation 3.
n . [P(t) – f ] = n . [P1 + (P2 – P1)t – f ] = 0 … (5)
• The relation should be applied for each boundary plane or edge of the
window to get the intersection points. Thus in general form equation (5) can
be written as,
ni . [P1 + (P2 – P1)t – fi ] = 0 … (6)
where, i is edge number.
• Solving equation (6) we get,
ni . [P1 – fi ] + ni . (P2 –P1)t = 0 … (7)
• Here the vector P2 – P1 defines the direction of the line. The direction of
the line is important to correctly identify the visibility of the line. The vector
P1 - fi is proportional to the distance from the
end point of the line to the boundary point.
• Let us define,
D = P2 – P1 as the direction of a line and
Wi = P1 – fi as weighting factor.
• Substituting newly defined variable D and Wi in Equation (7) we get,
ni.Wi + (ni . D)t = 0 … (8)
t = – (ni.Wi) /(ni.D) … (9)
where, D ≠ 0 and i = 1, 2, 3 .....
• The equation (9) is used to obtain the value of t for the intersection of the
line with each edge of the clipping window. We must select the proper
value for t using following tips :
1. If t is outside the range 0<= t <= 1, then it can be ignored.
2. We know that, the line can intersect the convex window in at most two
points , i.e. at two values
of t. With equation (9) , there can be several values of t in the range of 0<= t
<= 1 . We have to choose the largest lower limit and the smallest upper
limit.
3. If (ni . Di) > 0 then equation (9) gives lower limit value for t and if (ni. Di)
< 0 then equation (9)
gives upper limit value for t.
Algorithm Cyrus Beck Line Clipping Algorithm:
Step 1 : Read end points of line P1 and P2.
Step 2 : Read vertex coordinates of clipping window.
Step 3 : Calculate D = P2 – P1.
Step 4 : Assign boundary point b with particular edge.
Step 5 : Find inner normal vector for corresponding edge.
Step 6 : Calculate D.n and W = P1 – b
Step 7 : If D.n > 0
tL = – (W.n)/(D.n)
else
tU = – (W.n)/(D.n)
end if
Step 8 : Repeat steps 4 through 7 for each edge of clipping window.
Step 9 : Find maximum lower limit and minimum upper limit.
Step 10 : If maximum lower limit and minimum upper limit do not satisfy
condition 0 ≤ t ≤ 1 then
ignore line.
Step 11 : Calculate intersection points by substituting values of maximum
lower limit and minimum upper limit in parametric equation of line P1P2.
Step 12 : Draw line segment P(tL) to P(tU).
Step 13 : Stop.