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 9(a), where P Q 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”. (x Figure 9(a): Interaction of line PQ and Window Now, just recall the parametric equation of line segment PQ, which we have studied in the course CS-60. 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. (x1, y1) 2, y P Q A B 2) 83 Raster Graphics and Clipping 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 9(a). Remark: • How to specify the window region: a convex polygonal region having nvertices {P , P 84 0 1, 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). Q Figure 10(a): 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 10 (a), 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 10 (a), 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. OR P Q A B PL PE WINDOW P P e3 e4 P P Q e1 PE1 PE2 PL PE PL Q P (xB 1B, yB 1B) PB 3B PB i – 1B N1 N2 θ θ 2-D Viewing and Clipping Figure 10 (b): Potentially Entering PE and Potentially Leaving PL points 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 10 (b), 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 => (angle θ greater than 90° or Obtuse ) Ni . PQ < 0 ; Ni . (Q-P) < 0 (angle θ is less than 90° or Acute) PL => Ni . PQ > 0 ; Ni . (Q-P) > 0 • Where N is the outward normal to the ith edge. i Note: − N.)PQ( i when = 0 then it implies that: − PQ Ni 1) = 0 2) = 0 3) θ = 90° ↓ ↓ ↓ not possible ∵ if not possible possible i.e. − PQ PQ ⊥− N)PQ( i = 0 then is a point and not a line Ø line segment PQ is || to i th edge then only Ni will be ⊥ to both PQ and i th edge. Pi (xi, yi) Pi – 1 (xi – 1, yi – 1) Ni edge normal • How to find the normal : Figure 11 : Normal Determination − PP i1i = (x1 – xi – 1, yi – yi – 1) = (s1, s2) Ni if = (n1i, n2i), then . − PP i1i = 0 ⇒ (s Ni 1, s2). (n1i, n2i) = 0 85 Raster Graphics and Clipping ⇒ s 86 1n1i + s2n2i = 0 ⇒ s1n1i = – s2n2i = 0 1 2 s − s ⇒ n1i = n2i 1 2 s s If n2i = 1 then, n1i = )1, s s 1 − 2 Therefore, Ni = (n1i, n2i) = ( NORMAL ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ,-1 s s 1 2 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − ,1 s s 1 2 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − ,1 s s 1 2 if is outward normal then – i.e. is inward normal. Now, we have learned some basic things which will be required in the working of the algorithm, so, we can start using the concepts learned so far to clip the line segment passing through the window. 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. Let us do this exercise. The vector joining edge point Pi – 1 and point of intersection of the line PQ with the i th edge for some t will be given by: { [ −−+ −1i }P)]PQ(tP Ni is normal to the ith As edge , so, the dot product of the vector joining edge point Pi – 1 and point of intersection of the line PQ with the ith edge for some t and Ni will be given by: {[ i −−+ −1i N}.P])PQ(tP = 0 ---------------(1) Rearranging (1) we get, i i 1i N).PQ( N).PP( − −− − t = ---------------(2) Using this value of t from (2) in parametric form of line we will get the point of intersection of line PQ and ith edge. Note: By the above discussion of PE and PL we came to know that if Ni . (Q-P) < 0 => PE point and Ni . (Q-P) > 0 => PL point. If the value of t calculated using (2) lies in the interval 0 to 1 (in magnitude) then, the point of intersection will be considered otherwise it will not be considered.