Knowledge in Computer Graphics on viden.io

Knowledge in Computer Graphics

LINE CLIPPING

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

Computer Graphics

Dushyant Jodha

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 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. 

Computer Graphics

Dushyant Jodha

PROGRAMMING FUNDAMENTAL (First semester notes) Chapter-4 (Part-1) Makhanlal chaturvedi national University,Bhopal

(Part-1) IN This, There is a chapter fourth of COMPUTER FUNDAMENTAL Subject Part-1 named PROGRAMMING FUNDAMENTAL Makhanlal Chaturvedi national journalism and communication University, Bhopal. There is a very important note oF Fundamental computers For BCA first semester Students. Share with your friends and help them to learn Fundamental of Computers. There are Five subjects in BCA first semester .

bca english +23 more

Piyush Gupta

ARITHMATIC AND LOGICAL OPERATOR (First semester notes) Chapter-4 (Part-2) Makhanlal chaturvedi national University,Bhopal

(Part-2) IN This, There is a chapter fourth of COMPUTER FUNDAMENTAL Subject Part-2 named PROGRAMMING FUNDAMENTAL Makhanlal Chaturvedi national journalism and communication University, Bhopal. There is a very important note oF Fundamental computers For BCA first semester Students. Share with your friends and help them to learn Fundamental of Computers. There are Five subjects in BCA first semester .

BCA Question paper +20 more

Piyush Gupta

READING AND WRITING STORAGE (First semester notes) Chapter-4 (Part-4) Makhanlal chaturvedi national University,Bhopal

(Part-4) IN This, There is a chapter fourth of COMPUTER FUNDAMENTAL Subject Part-4 named PROGRAMMING FUNDAMENTAL Makhanlal Chaturvedi national journalism and communication University, Bhopal. There is a very important note oF Fundamental computers For BCA first semester Students. Share with your friends and help them to learn Fundamental of Computers. There are Five subjects in BCA first semester .

bca english +40 more

Piyush Gupta