{"id":150,"date":"2018-07-20T10:01:56","date_gmt":"2018-07-20T10:01:56","guid":{"rendered":"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=150"},"modified":"2018-12-26T12:32:43","modified_gmt":"2018-12-26T12:32:43","slug":"lineclipping","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/chapter\/lineclipping\/","title":{"rendered":"Line Clipping"},"content":{"raw":"\r\n<div>\r\n\r\n<strong>Objectives:<\/strong>\r\n<ul>\r\n \t<li>Understand Cohen-Sutherland Line Clipping<\/li>\r\n \t<li>Solve an example problem.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Discussion:<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>2D Clipping:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let\u2019s try to understand the theory behind the Cohen-Sutherland Line clipping algorithm. Recall discussion from the previous module that, clipping is performed before conversion of data to device coordinates. Line clipping is an extension of point clipping, where we check the position of a given line with respect to a standard rectangular clip window region. We need to perform tests to determine whether a line is completely inside or completely outside or partially inside. The portion of the line that is inside is only selected for display. Clipping algorithms identify the intersections of the lines with the clip window region and decide which portion of the line is inside and so can be selected for display. Two popular algorithms for line clipping are \u201cCohen-Sutherland line clipper\u201d and \u201cLiang-Barsky line clipper.\u201d An algorithm is considered efficient when with few checks if it decides that<\/p>\r\n&nbsp;\r\n<ul>\r\n \t<li>the line is completely inside and so can be selected (Trivial Accept) or<\/li>\r\n \t<li>the line is completely outside and so can be discarded (Trivial Reject) or<\/li>\r\n \t<li>line is partially inside so intersection checks need to be done.<\/li>\r\n<\/ul>\r\n<img class=\"size-full wp-image-154 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97.png\" alt=\"\" width=\"433\" height=\"177\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A line has two end points. If both the end points are inside the clip window, it is trivial that the line is completely inside and so can be selected for display. From the figure above it is evident that line<\/p>\r\n\r\n<\/div>\r\n<div>\r\n<ul>\r\n \t<li style=\"text-align: justify\">P3P4 is completely inside since both the end points P3 and P4 are inside (Trivial Accept case).<\/li>\r\n \t<li style=\"text-align: justify\">P1P2, P9P10 are completely outside, and so can be discarded. In both these cases both the end points are\u00a0 \u00a0 outside and the line is also completely outside.<\/li>\r\n \t<li style=\"text-align: justify\">P5P6 \u2013 A portion of the line is inside and so find intersection point P5\u2019 and select and display the portion\u00a0 \u00a0 of the line that is inside (P4P5\u2019).<\/li>\r\n \t<li style=\"text-align: justify\">P7P8 \u2013 Both end points are outside but a portion of the line is inside. For such types we need to calculate\u00a0 \u00a0 two intersection points P7\u2019 and P8\u2019 and display the line P7\u2019P8\u2019.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Both the algorithms for line clipping, Cohen-Sutherland and Liang-Barsky, are efficient algorithms and both can be extended for 3D clipping as well. But it is Liang-Barsky that suits well for implementation in a program.<\/p>\r\n&nbsp;\r\n\r\n<strong>Cohen-Sutherland Line Clipping Procedure:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This is a rudimentary level line clipping procedure and is efficient. Two scientists Cohen and Sutherland devised this procedure. The method speeds up the processing of line segments by performing <strong>initial tests<\/strong> that reduce the number of intersections that must be calculated particularly in the cases of Trivial Accept and Trivial Reject cases. Imagine that we are dividing the whole space into 9 zones or regions using 4 infinitely extending lines, such that the central region is identified as the <strong>clip window<\/strong> region, and remaining 8 regions around the central region are identified relative to the central region as shown in the figure below.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-155 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98.png\" alt=\"\" width=\"384\" height=\"202\" \/>\r\n<p style=\"text-align: justify\">Every region is assigned a four digit binary code, called <strong><em>region code<\/em><\/strong> that identifies a region. The central region, called the clip window region, is identified with the region code (0000). The region to the left is given a region code 0001. The regions to the right, bottom and top have the region codes, 0010, 0100, and 1000 respectively. The other 4 regions in the corners, top left, top right, bottom left, bottom right have the region codes 1001, 1010, 0101, 0110 respectively.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let\u2019s see how this region code was arrived at? Each bit position in the region code is used to indicate one of the four surrounding regions relative to the central clip window region. The order of the bits from right to left is as follows<\/p>\r\n&nbsp;\r\n<p style=\"padding-left: 90px\">Bit 1 : Left region<\/p>\r\n<p style=\"padding-left: 90px\">Bit 2 : Right region<\/p>\r\n<p style=\"padding-left: 90px\">Bit 3 : Bottom region<\/p>\r\n<p style=\"padding-left: 90px\">Bit 4 : Top region<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">For Ex: If a region code is given as 1010, this means, The <strong><em>top<\/em><\/strong> and <strong><em>right<\/em><\/strong> bits are set (indicated by a binary bit 1) while the <strong><em>left<\/em><\/strong> and <strong><em>bottom<\/em><\/strong> bits are not set (indicated by a binary bit 0). The answer is that the region with the region code 1010 is the top right of the central region. The central region has the region code 0000.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">Let\u2019 s try to understand how this region code is useful in determining the relative position of a line against the clip window. The idea is that for the two end points of a given line we shall compute region code and with simple checks we should be able to decide whether to go for intersection calculations or simply end up with a trivial reject or trivial accept case.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Each bit position in the region code is used to indicate one of the four relative coordinate positions of the point with respect to the clip window. The next step is how do we compute region codes for an end point? It is as simple as checking for four conditions (recall the equations from the point clipping discussion in the previous module - 8).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Assume 4 infinitely extending lines defined by xwmin, xwmax, ywmin, ywmax make up the clip window region. For an end point (x,y), check the first condition, if x&lt;xwmin set the left bit of the region code otherwise keep it 0. Than to check the relation for magnitude, it is convenient to check for the sign bit of the relation, x-xwmin , i.e., if the sign bit of the relation is set then set the left bit. We can perform similar checks for other three bit positions.<\/p>\r\n&nbsp;\r\n<p style=\"padding-left: 60px\">Set Bit 1(left): Sign(<strong><em>x<\/em><\/strong> <strong><em>\u2013<\/em><\/strong> <strong><em>xw<\/em><\/strong><strong><em>min<\/em><\/strong><strong><em>)<\/em><\/strong><\/p>\r\n<p style=\"padding-left: 60px\">Set Bit 2(right): sign(xwmax <strong><em>\u2013<\/em><\/strong> x )<\/p>\r\n<p style=\"padding-left: 60px\">Set Bit 3 (bottom): sign(y \u2013 ywmin )<\/p>\r\n<p style=\"padding-left: 60px\">Set Bit 4 (top): sign(ywmax \u2013 y)<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Compute the region codes for both the end points of a given line. If both the end points have a region code of 0000, then it is a <strong><em>Trivial Accept<\/em><\/strong> case, i.e., the line is completely inside and so can be considered for display. In general, a line that is parallel and outside the clip window region, will have, one bit position commonly set in both the region codes of the two end points. For Ex: consider a line that is parallel to the top boundary and is outside will have its region codes, 1001, 1010. From the region codes we can simply conclude that the line has one bit position commonly set, i.e. the top bit, so the line is parallel to the top boundary and is outside and so can be discarded.<\/p>\r\n&nbsp;\r\n\r\n*************************************************************************************************Steps in the algorithm are as follows\r\n<ul>\r\n \t<li style=\"text-align: justify\">For each end point of a line, compute region code<\/li>\r\n \t<li style=\"text-align: justify\">If both the end points have a region code of 0000, then it is a <strong><em>Trivial Accept<\/em><\/strong> case, i.e., the line is completely inside and so can be considered for display<\/li>\r\n \t<li style=\"text-align: justify\">Otherwise perform a bit wise AND operation for the two region codes of the two end points of a line, and if the operation results in a non-zero value, then it can be concluded that the line is outside and is parallel to that boundary represented by that bit position that is is set in the result, and so is a <strong><em>Trivial<\/em><\/strong> <strong><em>Reject <\/em><\/strong>case. (Ex: consider two region codes 1010, 0110. Performing bit-wise AND operation we get, 0010, which is a non-zero value and the bit position commonly set in both the region codes is the right bit position. The result says that the line is an outside line and is parallel to the right boundary.)<\/li>\r\n \t<li style=\"text-align: justify\">Otherwise, if the bit-wise AND operation results in a zero value, the line intersects the clip window and we need to go for intersection calculations. (Ex: Consider a line with region codes for its end points as 0100 and 0010. The line is an inclined line, no bit position is commonly set and bit-wise AND operation results in a zero value. So it\u2019s obvious to go for intersection calculations.)<\/li>\r\n \t<li style=\"text-align: justify\">If the above cases fail we need to go for intersection calculations.<\/li>\r\n<\/ul>\r\n***********************************************************************************************\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">It is known that, there will be a maximum of two intersection points for a given line, when it intersects clip window, but assuming infinitely extending clip window boundaries, and the line to be clipped being longer, there will be <strong>four<\/strong> intersection points, as shown below. The four dots represent the four intersection points, the maximum possible for a line.<\/p>\r\n<img class=\"size-full wp-image-156 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-99.png\" alt=\"\" width=\"234\" height=\"185\" \/>\r\n<p style=\"text-align: justify\">We need to check for a maximum of 4 intersection points, for the maximum possible line as shown in the figure above. Intersection points with a clipping boundary can be calculated using the slope-intercept form of the line equation.<\/p>\r\n<strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 =<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0<span style=\"text-decoration: underline\"><strong>\u2212\u00a0 \u00a0 \u00a0 \u00a0<\/strong><\/span>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The y coordinate of the intersection point at vertical line can be computed using the formula<\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>\u2212\u00a0\u00a0 =\u00a0\u00a0 ( \u00a0\u2212\u00a0 )\u00a0 <\/strong>where x is either xw<sub>min<\/sub> or xw<sub>max<\/sub><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The x coordinate of the intersection point at horizontal line can be computed using the equation<\/p>\r\n\r\n<\/div>\r\n<p style=\"text-align: center\">=\u00a0 +\u00a0 <u>\u00a0 \u00a0-\u00a0 \u00a0 \u00a0\u00a0<\/u><\/p>\r\n\r\n<div>\r\n\r\n\u00a0 where y is either ywmin or ywmax.\r\n\r\n&nbsp;\r\n\r\n<strong>*********************************************************************************************<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Example:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Compute the clipped portion of the line at [(0,0), (8,5)], when clipped against the clip window between [(1,2), (7, 6)].<\/p>\r\n&nbsp;\r\n\r\n<strong>Solution: <\/strong>From the problem, we can note the following data\r\n<p style=\"padding-left: 60px\">xwmin = 1<\/p>\r\n<p style=\"padding-left: 60px\">xwmax = 7<\/p>\r\n<p style=\"padding-left: 60px\">ywmin = 2<\/p>\r\n<p style=\"padding-left: 60px\">ywmax = 6<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Starting with left boundary we can calculate intersection points, and continue with the right, bottom, top boundaries.<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-157 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100.png\" alt=\"\" width=\"557\" height=\"376\" \/>\r\n\r\n&nbsp;\r\n\r\n**********************************************************************************************\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the solution shown above, after the line is clipped against the <strong><em>left<\/em><\/strong> boundary, we get an intersection point, P1\u2019, discard the portion from P1 to P1\u2019 and the line to be sent to the next clipper (right) is P1\u2019P2. With respect to the <strong><em>right<\/em><\/strong> clipper, when we clip the line we get another intersection point, P2\u2019, and discard the portion from P2 to P2\u2019. Now the line between P1\u2019P2\u2019 is sent to the bottom clipper. When we clip the portion of the line with respect to the bottom clipper, we compute another intersection point, P1\u2019\u2019, and discard the line from P1\u2019 to P1\u2019\u2019. When the line is finally sent to the <strong><em>top<\/em><\/strong> clipper, no intersection point needs to be computed as the line is completely inside with respect to top boundary. The computation ends and finally the line to be displayed is the line between P1\u2019 to P2\u2019\u2019.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary:<\/strong>\r\n<ul>\r\n \t<li>We have learnt how Cohen-Sutherland line clipping works<\/li>\r\n \t<li>This algorithm also works for clipping in 3D as well.<\/li>\r\n \t<li>An example problem has been solved<\/li>\r\n<\/ul>\r\n<img class=\"size-full wp-image-158 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101.png\" alt=\"\" width=\"632\" height=\"319\" \/>","rendered":"<div>\n<p><strong>Objectives:<\/strong><\/p>\n<ul>\n<li>Understand Cohen-Sutherland Line Clipping<\/li>\n<li>Solve an example problem.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Discussion:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>2D Clipping:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let\u2019s try to understand the theory behind the Cohen-Sutherland Line clipping algorithm. Recall discussion from the previous module that, clipping is performed before conversion of data to device coordinates. Line clipping is an extension of point clipping, where we check the position of a given line with respect to a standard rectangular clip window region. We need to perform tests to determine whether a line is completely inside or completely outside or partially inside. The portion of the line that is inside is only selected for display. Clipping algorithms identify the intersections of the lines with the clip window region and decide which portion of the line is inside and so can be selected for display. Two popular algorithms for line clipping are \u201cCohen-Sutherland line clipper\u201d and \u201cLiang-Barsky line clipper.\u201d An algorithm is considered efficient when with few checks if it decides that<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>the line is completely inside and so can be selected (Trivial Accept) or<\/li>\n<li>the line is completely outside and so can be discarded (Trivial Reject) or<\/li>\n<li>line is partially inside so intersection checks need to be done.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-154 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97.png\" alt=\"\" width=\"433\" height=\"177\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97.png 433w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97-300x123.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97-65x27.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97-225x92.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-97-350x143.png 350w\" sizes=\"auto, (max-width: 433px) 100vw, 433px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A line has two end points. If both the end points are inside the clip window, it is trivial that the line is completely inside and so can be selected for display. From the figure above it is evident that line<\/p>\n<\/div>\n<div>\n<ul>\n<li style=\"text-align: justify\">P3P4 is completely inside since both the end points P3 and P4 are inside (Trivial Accept case).<\/li>\n<li style=\"text-align: justify\">P1P2, P9P10 are completely outside, and so can be discarded. In both these cases both the end points are\u00a0 \u00a0 outside and the line is also completely outside.<\/li>\n<li style=\"text-align: justify\">P5P6 \u2013 A portion of the line is inside and so find intersection point P5\u2019 and select and display the portion\u00a0 \u00a0 of the line that is inside (P4P5\u2019).<\/li>\n<li style=\"text-align: justify\">P7P8 \u2013 Both end points are outside but a portion of the line is inside. For such types we need to calculate\u00a0 \u00a0 two intersection points P7\u2019 and P8\u2019 and display the line P7\u2019P8\u2019.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Both the algorithms for line clipping, Cohen-Sutherland and Liang-Barsky, are efficient algorithms and both can be extended for 3D clipping as well. But it is Liang-Barsky that suits well for implementation in a program.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Cohen-Sutherland Line Clipping Procedure:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This is a rudimentary level line clipping procedure and is efficient. Two scientists Cohen and Sutherland devised this procedure. The method speeds up the processing of line segments by performing <strong>initial tests<\/strong> that reduce the number of intersections that must be calculated particularly in the cases of Trivial Accept and Trivial Reject cases. Imagine that we are dividing the whole space into 9 zones or regions using 4 infinitely extending lines, such that the central region is identified as the <strong>clip window<\/strong> region, and remaining 8 regions around the central region are identified relative to the central region as shown in the figure below.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-155 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98.png\" alt=\"\" width=\"384\" height=\"202\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98.png 384w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98-300x158.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98-65x34.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98-225x118.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-98-350x184.png 350w\" sizes=\"auto, (max-width: 384px) 100vw, 384px\" \/><\/p>\n<p style=\"text-align: justify\">Every region is assigned a four digit binary code, called <strong><em>region code<\/em><\/strong> that identifies a region. The central region, called the clip window region, is identified with the region code (0000). The region to the left is given a region code 0001. The regions to the right, bottom and top have the region codes, 0010, 0100, and 1000 respectively. The other 4 regions in the corners, top left, top right, bottom left, bottom right have the region codes 1001, 1010, 0101, 0110 respectively.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let\u2019s see how this region code was arrived at? Each bit position in the region code is used to indicate one of the four surrounding regions relative to the central clip window region. The order of the bits from right to left is as follows<\/p>\n<p>&nbsp;<\/p>\n<p style=\"padding-left: 90px\">Bit 1 : Left region<\/p>\n<p style=\"padding-left: 90px\">Bit 2 : Right region<\/p>\n<p style=\"padding-left: 90px\">Bit 3 : Bottom region<\/p>\n<p style=\"padding-left: 90px\">Bit 4 : Top region<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For Ex: If a region code is given as 1010, this means, The <strong><em>top<\/em><\/strong> and <strong><em>right<\/em><\/strong> bits are set (indicated by a binary bit 1) while the <strong><em>left<\/em><\/strong> and <strong><em>bottom<\/em><\/strong> bits are not set (indicated by a binary bit 0). The answer is that the region with the region code 1010 is the top right of the central region. The central region has the region code 0000.<\/p>\n<\/div>\n<div>\n<p style=\"text-align: justify\">Let\u2019 s try to understand how this region code is useful in determining the relative position of a line against the clip window. The idea is that for the two end points of a given line we shall compute region code and with simple checks we should be able to decide whether to go for intersection calculations or simply end up with a trivial reject or trivial accept case.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Each bit position in the region code is used to indicate one of the four relative coordinate positions of the point with respect to the clip window. The next step is how do we compute region codes for an end point? It is as simple as checking for four conditions (recall the equations from the point clipping discussion in the previous module &#8211; 8).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Assume 4 infinitely extending lines defined by xwmin, xwmax, ywmin, ywmax make up the clip window region. For an end point (x,y), check the first condition, if x&lt;xwmin set the left bit of the region code otherwise keep it 0. Than to check the relation for magnitude, it is convenient to check for the sign bit of the relation, x-xwmin , i.e., if the sign bit of the relation is set then set the left bit. We can perform similar checks for other three bit positions.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"padding-left: 60px\">Set Bit 1(left): Sign(<strong><em>x<\/em><\/strong> <strong><em>\u2013<\/em><\/strong> <strong><em>xw<\/em><\/strong><strong><em>min<\/em><\/strong><strong><em>)<\/em><\/strong><\/p>\n<p style=\"padding-left: 60px\">Set Bit 2(right): sign(xwmax <strong><em>\u2013<\/em><\/strong> x )<\/p>\n<p style=\"padding-left: 60px\">Set Bit 3 (bottom): sign(y \u2013 ywmin )<\/p>\n<p style=\"padding-left: 60px\">Set Bit 4 (top): sign(ywmax \u2013 y)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Compute the region codes for both the end points of a given line. If both the end points have a region code of 0000, then it is a <strong><em>Trivial Accept<\/em><\/strong> case, i.e., the line is completely inside and so can be considered for display. In general, a line that is parallel and outside the clip window region, will have, one bit position commonly set in both the region codes of the two end points. For Ex: consider a line that is parallel to the top boundary and is outside will have its region codes, 1001, 1010. From the region codes we can simply conclude that the line has one bit position commonly set, i.e. the top bit, so the line is parallel to the top boundary and is outside and so can be discarded.<\/p>\n<p>&nbsp;<\/p>\n<p>*************************************************************************************************Steps in the algorithm are as follows<\/p>\n<ul>\n<li style=\"text-align: justify\">For each end point of a line, compute region code<\/li>\n<li style=\"text-align: justify\">If both the end points have a region code of 0000, then it is a <strong><em>Trivial Accept<\/em><\/strong> case, i.e., the line is completely inside and so can be considered for display<\/li>\n<li style=\"text-align: justify\">Otherwise perform a bit wise AND operation for the two region codes of the two end points of a line, and if the operation results in a non-zero value, then it can be concluded that the line is outside and is parallel to that boundary represented by that bit position that is is set in the result, and so is a <strong><em>Trivial<\/em><\/strong> <strong><em>Reject <\/em><\/strong>case. (Ex: consider two region codes 1010, 0110. Performing bit-wise AND operation we get, 0010, which is a non-zero value and the bit position commonly set in both the region codes is the right bit position. The result says that the line is an outside line and is parallel to the right boundary.)<\/li>\n<li style=\"text-align: justify\">Otherwise, if the bit-wise AND operation results in a zero value, the line intersects the clip window and we need to go for intersection calculations. (Ex: Consider a line with region codes for its end points as 0100 and 0010. The line is an inclined line, no bit position is commonly set and bit-wise AND operation results in a zero value. So it\u2019s obvious to go for intersection calculations.)<\/li>\n<li style=\"text-align: justify\">If the above cases fail we need to go for intersection calculations.<\/li>\n<\/ul>\n<p>***********************************************************************************************<\/p>\n<\/div>\n<div>\n<p style=\"text-align: justify\">It is known that, there will be a maximum of two intersection points for a given line, when it intersects clip window, but assuming infinitely extending clip window boundaries, and the line to be clipped being longer, there will be <strong>four<\/strong> intersection points, as shown below. The four dots represent the four intersection points, the maximum possible for a line.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-156 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-99.png\" alt=\"\" width=\"234\" height=\"185\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-99.png 234w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-99-65x51.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-99-225x178.png 225w\" sizes=\"auto, (max-width: 234px) 100vw, 234px\" \/><\/p>\n<p style=\"text-align: justify\">We need to check for a maximum of 4 intersection points, for the maximum possible line as shown in the figure above. Intersection points with a clipping boundary can be calculated using the slope-intercept form of the line equation.<\/p>\n<p><strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 =<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0<span style=\"text-decoration: underline\"><strong>\u2212\u00a0 \u00a0 \u00a0 \u00a0<\/strong><\/span><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The y coordinate of the intersection point at vertical line can be computed using the formula<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>\u2212\u00a0\u00a0 =\u00a0\u00a0 ( \u00a0\u2212\u00a0 )\u00a0 <\/strong>where x is either xw<sub>min<\/sub> or xw<sub>max<\/sub><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The x coordinate of the intersection point at horizontal line can be computed using the equation<\/p>\n<\/div>\n<p style=\"text-align: center\">=\u00a0 +\u00a0 <u>\u00a0 \u00a0&#8211;\u00a0 \u00a0 \u00a0\u00a0<\/u><\/p>\n<div>\n<p>\u00a0 where y is either ywmin or ywmax.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>*********************************************************************************************<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Compute the clipped portion of the line at [(0,0), (8,5)], when clipped against the clip window between [(1,2), (7, 6)].<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Solution: <\/strong>From the problem, we can note the following data<\/p>\n<p style=\"padding-left: 60px\">xwmin = 1<\/p>\n<p style=\"padding-left: 60px\">xwmax = 7<\/p>\n<p style=\"padding-left: 60px\">ywmin = 2<\/p>\n<p style=\"padding-left: 60px\">ywmax = 6<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Starting with left boundary we can calculate intersection points, and continue with the right, bottom, top boundaries.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-157 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100.png\" alt=\"\" width=\"557\" height=\"376\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100.png 557w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100-300x203.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100-225x152.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-100-350x236.png 350w\" sizes=\"auto, (max-width: 557px) 100vw, 557px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>**********************************************************************************************<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the solution shown above, after the line is clipped against the <strong><em>left<\/em><\/strong> boundary, we get an intersection point, P1\u2019, discard the portion from P1 to P1\u2019 and the line to be sent to the next clipper (right) is P1\u2019P2. With respect to the <strong><em>right<\/em><\/strong> clipper, when we clip the line we get another intersection point, P2\u2019, and discard the portion from P2 to P2\u2019. Now the line between P1\u2019P2\u2019 is sent to the bottom clipper. When we clip the portion of the line with respect to the bottom clipper, we compute another intersection point, P1\u2019\u2019, and discard the line from P1\u2019 to P1\u2019\u2019. When the line is finally sent to the <strong><em>top<\/em><\/strong> clipper, no intersection point needs to be computed as the line is completely inside with respect to top boundary. The computation ends and finally the line to be displayed is the line between P1\u2019 to P2\u2019\u2019.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary:<\/strong><\/p>\n<ul>\n<li>We have learnt how Cohen-Sutherland line clipping works<\/li>\n<li>This algorithm also works for clipping in 3D as well.<\/li>\n<li>An example problem has been solved<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-158 aligncenter\" src=\"http:\/\/csp06.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101.png\" alt=\"\" width=\"632\" height=\"319\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101.png 632w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101-300x151.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101-225x114.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-content\/uploads\/sites\/52\/2018\/07\/1-101-350x177.png 350w\" sizes=\"auto, (max-width: 632px) 100vw, 632px\" \/><\/p>\n","protected":false},"author":3,"menu_order":9,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-raghuveera"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-150","chapter","type-chapter","status-publish","hentry","contributor-dr-t-raghuveera"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":8,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/150\/revisions"}],"predecessor-version":[{"id":547,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/150\/revisions\/547"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapters\/150\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/media?parent=150"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/pressbooks\/v2\/chapter-type?post=150"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/contributor?post=150"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp06\/wp-json\/wp\/v2\/license?post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}