Cyrus Beck Algorithm in Line Clippinig


Computer Graphics / Friday, June 5th, 2020

Cyrus Beck Algorithm

Cyrus Beck Line clipping algorithm is infact, a parametric line-clipping algorithm. The term parametric implies that we need to find the value of the parameter ‘t’ in the parametric representation of the line segment for the point at which the segment intersects the clipping edge. For better understanding, consider the Figure where PQ is a line segment, which is intersecting at the two edges of the convex window.

Note: The algorithm is applicable to the “convex polygonal window”.

Now, just recall the parametric equation of line segment PQ.

It is simply P + t (Q – P)   0 ≤ t ≤ 1

Where, t → linear parameter continuously changes value.

∴P + t (Q – P) ⇒ (x1, y1) + t (x2 – x1, y2 – y1) = (x, y) be any point on PQ.    —— (1)

For this equation (1) we have following cases:

  1. When t = 0 we obtain the point P.
  2. When t = 1 we get the point Q.
  3. When t varies such that 0 ≤ t ≤ 1 then line between point P and Q is traced. For t = ½ we get the mid-point of PQ.
  4. When t < 0 line on LHS of P is traced.
  5. When t > 1 line on RHS of Q is traced.

So, the variation in parameter ‘t’ is actually generating line in point wise manner .The range of the parameter values will identify the portion to be clipped by any convex polygonal region having n-vertices or lattice points to be specified by the user. One such clipping situation is shown in Figure.

Interaction of line PQ and Window
Interaction of line PQ and Window

Remark:

How to specify the window region: Cyrus-Beck Algorithm

A convex polygonal region having ‘n’ vertices {P0, P1, P2, …, Pn – 1, Pn, P0} or lattice points to be specified by the user encloses the convex window region. To be specific about the window we may say that each edge between two points contributes to the boundary of the window under the situation that (when we traverse each edge in anticlockwise manner), the window region lies on left hand side (LHS) of edge. This orientation is preserved and while giving input, the user takes care of the orientation to specify the window region of any arbitrary convex shape.

Potentially entering and leaving points (PE and  PL ):

The point of intersection of the line and window may be classified either as Potentially entering or leaving. Before going into other details, let us describe the actual meaning of Potentially entering and leaving points (PE and  PL ). PE and PL are dependent on the edge orientation, i.e. direction. Let us understand how to find PE and PL (we know as we move anticlockwise across the window boundary then region of LHS encloses the window).

Potentially Entering PE and Potentially Leaving PL points
Potentially Entering PE and Potentially Leaving PL points

Say, we are moving from point P to point Q, and we know that while traversing the windows edges in anticlockwise manner the region lying on the left hand side is referred to as the window region. So, from the Figure, you may notice that at point PE  we are moving from P to Q we are entering the window region , thus this point of intersection should be referred to as the Potentially entering point(PE). Now, refer to other intersection shown in the Figure, here, also the movement of points on the line are determined by varying value of parameter t is from point P to Q and  w.r.t., the orientation of window boundary, we are exiting the window region. So, this point of intersection is known as potentially leaving point (PL).

Potentially entering point (PE) while moving towards the window, the point of intersection between line PQ and the window edges faced are known as PE.

Potentially leaving point (PL) These are the point of intersection encountered while we move away from window.

Other way round you may detect the point of intersection as Potentially leaving point (PL) or Potentially entering point (PE) by studying the angle between the line to be clipped from the outward normal to the intersecting edge, at the point of intersection. From Figure, it is the angle between PQ and N1 or N2. You may notice that, while moving from P to Q the angle between line PQ and N1 is obtuse whereas the angle between PQ and N2 is acute; so, you may say, if the angle between line PQ and N1 is obtuse the point of intersection is potentially entering (PE) whereas, if the angle between PQ and N2 is acute, then the point of intersection is potentially leaving (PL).

OR

PE =>Ni . PQ <  0       ; (angle  θ greater than 90° or Obtuse )

Ni . (Q-P) <  0

PL =>Ni . PQ >  0       ; (angle  θ less than 90° or Acute )

Ni . (Q-P) >  0

Where Ni is the outward normal to the i-th edge.

Cyrus-Beck Algorithm

Cyrus-Beck Algorithm

We know that the parametric equation of line PQ is  P + t (Q – P)  ;   0 ≤ t ≤ 1

Now, to find the point of intersection of line PQ and ith edge we need to find the appropriate value of parameter t, for that we firstly find normal to the ith edge. Say Ni is the normal to ith edge (Pi-1 to Pi), then to find the appropriate parameter t, we should determine the dot product of the vector from Pi – 1  to the point of intersection and the normal Ni.

 Example 01

How does the Cyrus Beck line clipping algorithm, clip a line segment if the window is non convex?

Cyrus Back Algorithm Example

 

Leave a Reply

Your email address will not be published. Required fields are marked *