Sutherland and cohen subdivision line clipping algorithm | clipping algorithm

Sutherland and cohen subdivision line clipping algorithm

• this is one of the most oldest and popular method for line clipping algorithm developed by "Dan cohen" and "Ivan sutherland".
• This algo uses a 4 digit code to indicate which of the nine region contain the n point of the line, the 4 digit codes are called Region codes or out codes. these codes identifies the location of the point relative to the boundaries of the clipping window.
• 
• Each bit position in the region code is used to indicate one of the 4 releative co-ordinate position of the point w.r.t the clipping window.(left, right, top and bottom).
• set bit 1: if the end point is to left of the window.
• set bit 2: if the end point is to right of the window.
• set bit 3: if the end point lie below the window.
• set bit 4: if the end point lie above the window.
• Once we have establish region codes for all the lines end points we can determine which lines are completely outside the clipping window and any lines that are completely inside the window boundaries have a region code of (0000) for both the ends point and we accept these lines.
• A method used to test lines for total clipping is equivalent to the logical AND operation with two end points is not equal to (0000).   

• The line that can't be identified as completely inside or completely outside the clipping window by these test they are checked for intersection with the window boundaries. 

Algorithm:

1. read two end points of the line p1(x1,y1), p2(x2,y2).
2. Read two corner(left -top, left-bottom) of the window (Wx1,Wy1) and (Wx2,Wy2).
3. Assign the region codes for the two end points (p1,p2) using the following steps:

• 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 the end point are zero then the line is completly visible hence draw    the line and go to step 9

         b. if region code for the end point are not zero and the logical AND operation of them is also  non -zero then the line is comletely unvisible .so, reject the line and go to step 9.

         c. if above points not satisfy the line is partially visible.

     5.Determine the intersection edge of the clipping window by respecting the region code of the two end points.

a. if the region code for both the end points are non-zero .find the respective points (p1'&p2') with the boundary edge of the clipping window w.r.t it .

    6. Divide the line segment considering the (x) point.

    7. Reject the line segment if any one end point of it appeared outside the clipping window.

    8. Draw the remaning line segment.

     9. STOP.

Posted in clipping, clipping algorithm, cohen, subdivision, sutherland, Sutherland and cohen subdivision line clipping algorithm