Cohen Sutherland Subdivision line clipping algorithm:-

This is one of the oldest and most popular line clipping algorithm developed by Dan Cohen and Ivan Sutherland. To speed up the processing this algorithm Performs initial tests that reduce the number of intersections that must be calculated. This algorithm uses a four digit (bit) code to indicate which of nine regions contain the end point of line. The four bit codes are called region codes or outcodes. These codes identify the Location of the point relative to the boundaries of the clipping rectangle as shown in the figure (f).

Each bit position in the region code is used to indicate one of the four relative co-ordinate positions of the point with respect to the clipping window: to the left, right, top or bottom. The rightmost bit is the first bit and the bits are set to 1 based on the following scheme:

Set Bit 1 - if the end point is to the left of the window.

Set Bit 2 - if the end point is to the right of the window.

Set Bit 3 - if the end point is below the window

Set Bit 4 - if the end Point is above the window

Otherwise, the bit is set to zero

Once we have established region codes for all the line endpoints, we can determine which lines are completely inside the clipping window and which are clearly outside. Any lines that are completely inside the window boundaries have a region code of 0000 for both endpoints and we trivially accept these lines. Any lines that have a 1 in the same bit position in the region codes for each endpoint are completely outside the clipping rectangle, and we trivially reject these lines. A method used to test lines for total clipping is equivalent to the logical AND operator. If the result of the logical AND operation with two end Point codes is not 0000, the line is completely outside the clipping region The lines that cannot be identified u as completely inside or completely outside a clipping window by these tests are checked for intersection with the window boundaries.

Consider the clipping window and the lines shown in figure (g) above. Find the region codes for each end point and identify whether the line is completely visible, partially visible or completely invisible.

The figure (h) shows the clipping window and lines with region codes.These codes are tabulated and end point codes are logically ANDed to identify the visibility of the line in Table 1.

The Cohen Sutherland algorithm begins the clipping process for a partially visible line by comparing an outside endpoint to a clipping boundary to determine how much of the line can be discarded. Then the remaining part of the line is checked against the other boundaries, and the process is continued until either the line is totally discarded or a section is found inside the window. This is illustrated in figure (i)

As shown in the figure (i), line P1 P2 is a partially visible and point P1 is outside the window. starting with point P1, the intersection Point P’1 is found and we get two line segments P1 - P’1 and P’1 - P2 .We know that, for P1 - P’1 one end point i.e. P1 is outside the window and thus the line segment P1 – P’1 is discarded. The line is now reduced to the section from P’1 to P2. Since P2 is outside the clip window, it is checked against the boundaries and intersection point P’2 is found. Again the line segment is divided into two segments P’1 – P’2 and P’2 – P2 one end point i.e. P2 is outside the window and thus the line segment P’2 - P2 is discarded. The remaining line segment P’1 – P’2 is completely inside the clipping window and hence made visible.

The intersection points with a clipping boundary can be calculated using the slope-intercept form of the line equation. The equation for line Passing through Points P1 (x1, y1) and P2 (x2, y2) is

Cohen Sutherland Subdivision line clipping algorithm:-

Algorithm:-

1. Read two end Points of the line say P1 (x1, y1) and P2 (x2, y2).

2. Read two corners (left-top and right-bottom) of the window, say (Wx1, Wy1 and Wx2, Wy2).

3. Assign the region codes for two end points P1 and P2 using following steps:

   Initialize code with bits 0000

   Set Bit 1 - If (x < Wx1)

   Set Bit 2 - If (x > Wx2)

   Set Bit 3 - If (y < Wy2)

   Set Bit 4 - If (y > Wy1)

4. Check for visibility of line P1 P2

   a) If region codes for both endpoints P1 and P2 are zero then the line is completely visible. Hence draw the line and go to step 9.

   b) If region codes for endpoints are not zero and the logical ANDing of them is also nonzero then the line is completely invisible, so reject the line and go to step 9.

   c) If region codes for two endpoints do not satisfy the conditions in 4a. and 4b. the line is partially visible.

5. Determine the intersecting edge of the clipping window by inspecting the region codes of two endpoints.

   a) If region codes for both the end points are non-zero, find intersection points P’1 and P’2 with boundary edges of clipping window with respect to point P1 and point P2,respectively

   b) If region code for any one end Point is non-zero then find intersection Point P’1 or P’2 with the boundary edge of the clipping window with respect to it.

6. Divide the line segments considering intersection points.

7. Reject the Line segment if any one end Point of it appears outsides the clipping window.

8. Draw the remaining line segments.

9. Stop.