Explain Cohen Sutherland Line Clipping Algorithm
person
brightness_auto
1 Answer
Sutherland and Cohen 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 no of intersections that must be calculated .The algorithm uses four digit (bit) codes to indicate which of the nine regions contains the endpoint of line. These four bit codes are called as region code or out codes. These codes identify the location of point relative to the boundaries of the clipping rectangle as shown below.
REGION CODE
Each bit position in the region code is used to produce one of the four relative coordinate positions of the point with respect to clipping window to left, right, top or bottom. The right hand bit is the first bit and bits are set to
Bit 1 is set to X <Xwmin
Bit 2 is set to X >Xwmin
Bit 3 is set to Y <Ywmin
Bit 4 is set to Y >Ywmin
of the line with window boundary.
Point outside window is compared to boundary of window to determine how much line is to discarded and remaining part of line is checked against other boundary.
calculated using slope intersection formula for line equation as
1.Y co-ordinate of intersection with vertical boundaries
Y=Y1+m(X-X1)
X is neither Xwmin nor Xwmax depending on boundary of window.
2. X co-ordinate of intersection point inserted with horizontal boundaries
X=X1+ (Y-Y1) /m
Y is neither Ywmin nor Ywmax depending on boundary of window.
ALGORITHM:-
1) Read line end points (X1, Y1) and (X2, Y2).
2) Read clipping window co-ordinate.
3) Read m= Y2-Y1/ X2-X1
4) Assign region code.
5) If code = 0000 accept entire line and go to step 12.
6) If intercept = Left XLY= m (XL-X1) +Y1.
7) If intercept = Right XRY= m (XR-X1) +Y1.
8) If intercept = Bottom Y2X= X1+1 (YB-Y1) / m
9) If intercept = Top Y1X= X1+1 (YT-Y1) / m and go to step 11.
10) Else discard entire line.
11) Discard portion of line which is outside of clip window.
12) Stop.