CS-460/560, Week 8-C Spring, 1998 R. Eckert LINE CLIPPING: THE COHEN-SUTHERLAND LINE CLIPPING ALGORITHM Given the endpoint coordinates (x1,y1) and (x2,y2) of a line, determine what part of that line lies inside the rectangular clip area whose lefthand border is x=xmin, righthand border x=xmax, bottom border y=ymin, and top border y=ymax. Could do point test for all points on the line--i.e., for a point x,y: if ((x<=xmax) && (x>=xmin) && (y<=ymax) && (y>=ymin)) the point x,y lies inside the clip area Too much work! We want a simple test involving the line's endpoint coordinates. Observation-- All lines fall into one of three categories 1. Both endpoints inside rectangle (Trivially accept entire line) 2. Both endpoints outside rectangle on the same side of one of its borders (Trivially reject entire line) 3. Neither 1 or 2 ==> chop off the part of the line outside one of borders (which gives a new endpoint) and see if the resulting line has been reduced to Category 1 or Category 2. A tool to use in assigning lines to Category 1 or 2: a 4-bit region code (RC) that can be assigned to an endpoint (x,y) . Any set bit means the endpoint is outside of one of the 4 borders of the clip rectangle-- RC = LRBA, L=left (if x<xmin, L=1, else L=0) R=Right (if x>xmax, R=1, else R=0) B=Bottom (if y<ymin, B=1, else B=0) T=Top (if y>ymax, T=1, else B=0) The entire x-y plane can be divided into 9 regions, depending on the value of the Region Code: | | 1001 | 0001 | 0101 | | ---------------------- | | 1000 | 0000 | 0100 | | ---------------------- | | 1010 | 0010 | 0110 | | Points inside the clip region have a region code of 0000. Assume that the region codes for the two endpoints of a line are RC1 and RC2. A bitwise OR of RC1 with RC2 will give zero only if all bits of both are zero: if (RC1 OR RC2 == 0) both RCs are 0000, and both endpoints are inside ==> Category 1 (trivial accept) If both endpoints are outside the SAME border of the clip region (Category 2 line), then both endpoint region codes will have the SAME bit set in one of the four bit positions. A bitwise AND of RC1 with RC2 will give a nonzero result if that is the case: if (RC1 AND RC2 != 0) Both endpoints are outside of the same border ==> Category 2 (trivial reject) What about category 3 lines? First observe that Category 3 lines may have both endpoints (P1 and P2) outside different borders of the clip region. In that case it is not important which end of the line is chopped off first. But if we have a case where one endpoint is inside and the other is outside, we want to chop off the end that is outside. To simplify things, we'll always assume that it is endpoint P1 which is the one that is the outside point. (If that is not the case, P1 and P2 will be swapped.) How do we do the chopping? (i.e., how do we determine the new endpoint?) Assume we have the slope (m) and intercept (b) of the line (which can be computed from the original endpoint coordinates). Look the region code of point P1 for each of four possible cases: If RC == 1xxx (P1 is to the left of xmin) The new endpoint should be on the left boundary: x1 <---xmin y1 <---m*xmin + b Reset the RC's L bit if RC == x1xx (P1 is to the right of xmax) The new endpoint should be on the right boundary: x1 <---xmax y1 <---m*xmax + b Reset the RC's R bit if RC == xx1x (P1 is to the below of ymin) The new endpoint should be on the bottom boundary: y1 <---ymin x1 <---(ymin-b)/m Reset the RC's B bit if RC == xx1x (P1 is to the below of ymin) The new endpoint should be on the top boundary: y1 <---ymax x1 <---(ymax-b)/m Reset the RC's T bit THE ALGORITHM-- Input: Original endpoints (x1,y1,x2,y2) Clip region boundaries (xmin,ymin,xmax,ymax) Output: Accept Code (AC==TRUE ==> Some part of the line was inside AC==FALSE ==> no part of the line was inside) Clipped Line endpoints (x1,y1,x2,y2) [if AC == TRUE] PSEUDO-CODE: CS_LineClip(xmin,ymin,xmax,ymax,x1,y1,x2,y2,AC) Calculate m and b from x1,y1,x2,y2 done = FALSE While (NOT done) Calculate endpoint codes rc1, rc2 If ((rc1 OR rc2) == 0) // Category 1, Trivial Accept done = TRUE AC = TRUE Else If ((rc1 AND rc2) != 0) // Category 2, Trivial Reject done = TRUE AC = FALSE Else If (P1 is inside) Swap x1,x2, y1,y2, and rc1,rc2 If (L-bit of rc1 is set) // 1xxx x1 = xmin y1 = m*x1 + b Else If (R-bit of rc1 is set) // x1xx x1 = xmax y1 = m*x1 + b Else If (B-bit of rc1 is set) // xx1x y1 = ymin x1 = (y1-b)/m Else // xxx1 y1 = ymax x1 = (y1-b)/m