Line is a series of infinite number of points, where no two points have space in between them. So, the above said inequality also holds for every point on the line to be clipped. A variety of line clipping algorithms are available in the world of computer graphics, but we restrict our discussion to the following Line clipping algorithms, name after their respective developers: 1) Cohen Sutherland algorithm, 2) Cyrus-Beck of algorithm 3.4.1 Cohen Sutherland Line Clippings This algorithm is quite interesting. The clipping problem is simplified by dividing the area surrounding the window region into four segments Up, Down, Left, Right (U,D,L,R) and assignment of number 1 and 0 to respective segments helps in positioning the region surrounding the window. How this positioning of regions is performed can be well understood by considering Figure 3. 0000 Window 1010 region 1 1000 region 2 1001 region 3 0010 region 8 0001 region 4 0110 region 8 0100 region 6 0101 region 5 Figure 3: Positioning of regions surrounding the window In Figure 3 you might have noticed, that all coding of regions U,D,L,R is done with respect to window region. As window is neither Up nor Down, neither Left nor Right, so, the respective bits UDLR are 0000; now see region 1 of Figure 3. The positioning code UDLR is 1010, i.e., the region 1 lying on the position which is upper left side of the window. Thus, region 1 has UDLR code 1010 (Up so U=1, not Down so D=0, Left so L=1, not Right so R=0). The meaning of the UDLR code to specify the location of region with respect to window is: st nd rd 1 bit ⇒ Up(U) ; 2 bit ⇒ Down(D) ;3 bit ⇒ Left(L) ; 4th bit ⇒ Right(R), 73 Raster Graphics and Clipping Now, to perform Line clipping for various line segment which may reside inside the window region fully or partially, or may not even lie in the widow region; we use the tool of logical ANDing between the UDLR codes of the points lying on the line. Logical ANDing (^) operation => 1 ^ 1 = 1; 1 ^ 0 = 0; between respective bits implies 0 ^ 1 = 0; 0 ^ 0 = 0 Note: • UDLR code of window is 0000 always and w.r.t. this will create bit codes of other regions. • A line segment is visible if both the UDLR codes of the end points of the line segment equal to 0000 i.e. UDLR code of window region. If the resulting code is not 0000 then, that line segment or section of line segment may or may not be visible. Now, let us study how this clipping algorithm works. For the sake of simplicity we will tackle all the cases with the help of example lines l1 to l5 shown in Figure 4. Each line segment represents a case. 74 Figure 4: Various cases of Cohen Sutherland Line Clippings Note, that in Figure 4, line l1 is completely visible, l2 and l3 are completely invisible; l4and l5 are partially visible. We will discuss these out comings as three separate cases. Case 1: l1 → Completely visible, i.e., Trival acceptance (∴both points lie inside the window) Case 2: l2 and l3 → Invisible , i.e., Trival acceptance rejection Case 3: l4 and l5→ partially visible (∴partially inside the window) Now, let us examine these three cases with the help of this algorithm: Case 1: (Trivial acceptance case) if the UDLR bit codes of the end points P,Q of a given line is 0000 then line is completely visible. Here this is the case as the end points a and b of line l1 are: a (0000), b (0000). If this trival acceptance test is failed then, the line segment PQ is passed onto Case 2. Case 2: (Trivial Rejection Case) if the logical intersection (AND) of the bit codes of the end points P, Q of the line segment is ≠ 0000 then line segment is not visible or is rejected. Note that, in Figure 4, line 2 is completely on the top of the window but line 3 is neither on top nor at the in bottom plus, either on the LHS nor on the RHS of the 1001 0001 0101 l1 b l2 a l5 a 1010 1000 b 1001 0010 0000 a 0001 a a l4 b l3 b 0110 0100 b 2-D Viewing and Clipping window. We use the standard formula of logical ANDing to test the non visibility of the line segment. So, to test the visibility of line 2 and 3 we need to calculate the logical intersection of end points for line 2 and line 3. line l2: bit code of end points are 1010 and 1000 logical intersection of end points = (1010) ^ (1000) = 1000 as logical intersection ≠ 0000. So line 2 will be invisible. line l3: end points have bit codes 0010 and 0101 now logical intersection = 0000, i.e., 0010 ^ 0101 = 0000 from the Figure 4, the line is invisible. Similarly in line 4 one end point is on top and the other on the bottom so, logical intersection is 0000 but then it is partially visible, same is true with line 5. These are special cases and we will discuss them in case 3. P P’’’ P′′ l5 Figure 5: Cohen Sutherland line clipping Case 3: Suppose for the line segment PQ, both the trivial acceptance and rejection tests failed (i.e., Case 1 and Case 2 conditions do not hold, this is the case for l3, l4 and l5 line segments) shown above in Figure 5. For such non-trivial Cases the algorithm is processed, as follows. Since, both the bitcodes for the end points P, Q of the line segment cannot be equal to 0000. Let us assume that the starting point of the line segment is P whose bit code is not equal to 0000. For example, for the line segment l5 we choose P to be the bitcodes 1001. Now, scan the bitcode of P from the first bit to the fourth bit and find the position of the bit at which the bit value 1 appears at the first time. For the line segment l5 it appears at the very first position. If the bit value 1 occurs at the first position then proceed to intersect the line segment with the UP edge of the window and assign the first bit value to its point of intersection as 0. Similarly, if the bit value 1 occurs at the second position while scanning the bit values at the first time then intersect the line segment PQ with the Down edge of the window and so on. This point of intersection may be labeled as P’. Clearly the line segment PP’ is outside the window and therefore rejected and the new line segment considered for dipping will be P’Q. The coordinates of P’ and its remaining new bit values are computed. Now, by taking P as P’, again we have the new line segment PQ which will again be referred to Case 1 for clipping. l3 P′ P′′ P* P 1010 1000 1001 0010 0000 0001 110 0101 0100 P l5 l4 0 P’ xwmin xwmax d f e c Q (xwmin, Y’) (x1, y1) (xwmax,Ywmax) (x2, y2) ywmax (xwmin, Ywminx) (x′,Ywmax) (xwmax, y) ywmin (x,ywmin) 75 Raster Graphics and Clipping Figure 6: Line Clipping - Geometrically Geometrical study of the above type of clipping (it helps to find point of intersection of line PQ with any edge). Let (x 76 1, y1) and (x2, y2) be the coordinates of P and Q respectively. 1) top case/above if y1 > yw then 1st max bit of bit code = 1 (signifying above) else bit code = 0 2) Bottom case/below case if y1 < ywmin then 2nd bit = 1 (i.e. below) else bit = 0 3) Left case: if x1 < xwmin then 3rd bit = 1 (i.e. left) else 0 4) Right case: if x1 > xwmax then 4th bit = 1 (i.e. right) else 0 Similarly, the bit codes of the point Q will also be assigned. 1) Top/above case: equation of top edge is: y = ywmax . The equation of line PQ is y – y1 = m (x – x1) where, m = (y2 – y1)/ (x2 – x1) The coordinates of the point of intersection will be (x, ywmax) ∴equation of line between point P and intersection point is (ywmax – y1) = m ( x – x1) rearrange we get m 1 x = x1 + (ywmax – y1) -------------------- (A) Hence, we get coordinates (x, ywmax) i.e., coordinates of the intersection. 2) Bottom/below edge start with y = ywmin and proceed as for above case. ∴equation of line between intersection point (x’, ywmin) and point Q i.e. (x2, y2) is (ywmin – y2) = m (x′ – x2) rearranging that we get, m 1 -------------------- (B) – y The coordinates of the point of intersection of PQ with the bottom edge will be ( )), 1 ( 2 min 2 min ywyyw m x + − 3) Left edge: the equation of left edge is x = xwmin. Now, the point of intersection is (xwmin, y). Using 2 point from the equation of the line we get (y – y1) = m (xwmin – x1) Rearranging that, we get, y = y1 + m (xwmin – x1). -------------------- (C) x′ = x2 + (ywmin 2) 2-D Viewing and Clipping Hence, we get value of xwmin and y both i.e. coordinates of intersection point is given by ))(,( . 1min 1min −+ xxwmyxw 4) Right edge: proceed as in left edge case but start with x-xwmax. Now point of intersection is (xwmax, y′). Using 2 point form, the equation of the line is (y′ – y2) = m (xwmax – x2) y′ = y -------------------- (D) The coordinates of the intersection of PQ with the right edge will be (,( )) . 2max 2max −+ xxwmyxw Steps of the Cohen Sutherland Line Clipping Algorithm are Figure 7: Steps for Cohen Sutherland Line Clipping STEP 1: Input: ),(),,(,,,, 222111 yxPyxPyyxx BTRL Initialise i = 1 While i <= 2 if < xx Li then bit 1 of code –Pi = 1 else 0 if > xx Ri then bit 2 of code –Pi =1 else 0 : The endpoint codes of the line are set if < yy Bi then bit 3 of code –Pi = 1 else 0 if > yy Ti then bit 4 of code –Pi = 1 else 0 i = i +1 end while i = 1 STEP 2: Initialise j = 1 While j <= 2 if then Lj < xx = 1 left Cj else = 0 left Cj if then Rj > xx = 1 right Cj else = 0 right Cj :Set flags according to the position of the line endpoints w.r.t. window if j B y y < then = 1 j bottom C else = 0 j bottom C edges XLYB XLYT XRYT XRYB P1 P1 P1 P1 P1 P2 P2 P2 P2 P2 (x1y1) (x2y2) LÆLeft ; RÆ Right TÆTop ; BÆBottom 2 + m (xwmax – x2) 77 Raster Graphics and Clipping = 1 top Cj 78 if j T y y > 0 then else Cjtop = end while STEP 3: If codes of P1and P2 are both equal to zero then draw P1P2 (totally visible) STEP 4: If logical intersection or AND operation of code –P1 and code –P2 is not equal to zero then ignore P1P2 (totally invisible) STEP 5: If code –P1= 0 then swap P1 and P2 along with their flags and set i = 1 STEP 6: If code –P1 < > 0 then for i = 1, {if C1 left = 1 then find intersection )',( with left edge vide eqn. (C) LL yx assign code to )',( LL yx P1 = )',( LL yx end if i = i + 1; go to 3 } for i = 2, {if C1 right = 1 then find intersection )',( with right edge vide eqn. (D) RR yx assign code to )',( RR yx P1 = )',( RR yx end if i = i + 1 go to 3 } for i = 3 {if C1 bottom = 1 then ( ', ) B B find intersection x y with bottom edge vide eqn. (B) assign code to ( ' , ) B B x y P1 = ( ' , ) B B x y end if i = i + 1 go to 3 } for i = 4, {if C1 top = 1 then ( ', ) T T find intersection x y vide eqn. (A) with top edge assign code to ( ' , ) T T x y P1 = ( ' , ) T T x y end if i = i + 1 go to 3 } end