**Cohen Sutherland Line Clippings**

This **Cohen Sutherland Line Clipping algorithm** is quite interesting. The clipping problem is simplified by dividing the area surrounding the window region into four segments Up, Down, Left, Right (U, D, L, R) and assignment of number 1 and 0 to respective segments helps in positioning the region surrounding the window. How this positioning of regions is performed can be well understood by considering *Figure 1*.

In *Figure 1* you might have noticed, that all coding of regions U, D, L, R is done with respect to window region. As window is neither Up nor Down, neither Left nor Right, so, the respective bits UDLR are 0000; now see region 1 of *Figure 1*. The positioning code UDLR is 1010, i.e., the region 1 lying on the position which is upper left side of the window. Thus, region 1 has UDLR code 1010 (Up so U=1, not Down so D=0, Left so L=1, not Right so R=0).

The meaning of the UDLR code to specify the location of region with respect to window is:

1^{st} bit ⇒ Up (U); 2^{nd} bit ⇒ Down (D); 3^{rd} bit ⇒ Left (L); 4^{th} bit ⇒ Right (R)

Now, to perform Line clipping for various line segment which may reside inside the window region fully or partially, or may not even lie in the widow region; we use the tool of logical ANDing between the UDLR codes of the points lying on the line.

Logical ANDing (^) operation between respective bits implies

1 ^ 1 = 1; 1 ^ 0 = 0; 0 ^ 1 = 0; 0 ^ 0 = 0

**Note:**

UDLR code of window is 0000 always and w.r.t. this will create bit codes of other regions.

A line segment is visible if both the UDLR codes of the end points of the line segment equal to 0000 i.e. UDLR code of window region. If the resulting code is not 0000 then, that line segment or section of line segment may or may not be visible.

Now, let us study how this clipping algorithm works. For the sake of simplicity we will tackle all the cases with the help of example lines l_{1} to l_{5} shown in *Figure 2*.

Each line segment represents a case.

Note, that in *Figure 2*, line l_{1}is completely visible, l2 and l3 are completely invisible; l4 and l_{5} are partially visible. We will discuss these out comings as three separate cases.

**Case 1:** l_{1} → completely visible, i.e., Trivial acceptance (both points lie inside the window)

**Case 2:** l2 and l3 → Invisible, i.e., Trivial acceptance rejection

**Case 3:** l4 and l5 → partially visible (partially inside the window)

Now, let us examine these three cases with the help of this algorithm:

**Case 1: **(Trivial acceptance case) *if the UDLR bit codes of the end points P, Q of a given line is 0000 then line is completely visible.* Here this is the case as the end points a and b of line l_{1} are: a (0000), b (0000). If this trivial acceptance test is failed then, the line segment PQ is passed onto Case 2.

**Case 2: **(Trivial Rejection Case) *if the logical intersection (AND) of the bit codes of the end points P, Q of the line segment is ≠ 0000 then line segment is not visible or is rejected.*

Note that, in *Figure 2*, line 2 is completely on the top of the window but line 3 is neither on top nor at the in bottom plus, either on the LHS nor on the RHS of the window. We use the standard formula of logical ANDing to test the non visibility of the line segment.

So, to test the visibility of line 2 and 3 we need to calculate the logical intersection of end points for line 2 and line 3.

**line l2: ** bit code of end points are 1010 and 1000 logical intersection of end points = (1010) ^ (1000) = 1000 as logical intersection ” 0000. So line 2 will be invisible.

**line l3:** end points have bit codes 0010 and 0101 now logical intersection = 0000, i.e., 0010 ^ 0101 = 0000 from the *Figure 2*, the line is invisible. Similarly in line 4 one end point is on top and the other on the bottom so, logical intersection is 0000 but then it is partially visible, same is true with line 5. These are special cases and we will discuss them in case 3.

**Case 3:** Suppose for the line segment PQ, both the trivial acceptance and rejection tests failed (i.e., Case 1 and Case 2 conditions do not hold, this is the case for l3, l4 and l5 line segments) shown above in *Figure 3*. For such non-trivial

Cases the algorithm is processed, as follows.

Since, both the bitcodes for the end points P, Q of the line segment cannot be equal to 0000. Let us assume that the starting point of the line segment is P whose bit code is not equal to 0000. For example, for the line segment l we choose P to be the bitcodes 1001. Now, scan the bitcode of P from the first bit to the fourth bit and find the position of the bit at which the bit value 1 appears at the first time. For the line segment l5 it appears at the very first position. If the bit value 1 occurs at the first position then proceed to intersect the line segment with the UP edge of the window and assign the first bit value to its point of intersection as 0. Similarly, if the bit value 1 occurs at the second position while scanning the bit values at the first time then intersect the line segment PQ with the Down edge of the window and so on. This point of intersection may be labeled as P’. Clearly the line segment PP’ is outside the window and therefore rejected and the new line segment considered for dipping will be P’Q. The coordinates of P’ and its remaining new bit values are computed. Now, by taking P as P’, again we have the new line segment PQ which will again be to Case 1 for clipping.

Geometrical study of the above type of clipping (it helps to find point of intersection of line PQ with any edge).

Let (x_{1}, y_{1} ) and (x_{2} , y_{2}) be the coordinates of P and Q respectively.

**Top case /above case:**

If y_{1} > yw_{max} then 1^{st} bit of bit code = 1 (signifying above) else bit code = 0

**Bottom case / below case:**

If y_{1} < yw_{min} then 2^{nd} bit = 1 (i.e. below) else bit = 0

**Left case:**

If x_{1} < xw_{min} then 3^{rd} bit = 1 (i.e. left) else bit = 0

**Right case:**

If x_{1} > xw_{max} then 4^{th} bit = 1 (i.e. right) else bit = 0

## Algorithm

1 2 3 4 5 6 7 8 9 10 |
Step 1 − Assign a region code for each endpoints. Step 2 − If both endpoints have a region code 0000 then accept this line. Step 3 − Else, perform the logical ANDoperation for both region codes. Step 3.1 − If the result is not 0000, then reject the line. Step 3.2 − Else you need clipping. Step 3.2.1 − Choose an endpoint of the line that is outside the window. Step 3.2.2 − Find the intersection point at the window boundary (base on region code). Step 3.2.3 − Replace endpoint with the intersection point and update the region code. Step 3.2.4 − Repeat step 2 until we find a clipped line either trivially accepted or trivially rejected. Step 4 − Repeat step 1 for other lines. |

## Pseudo-code of Cohen-Sutherland Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
procedure CohenSutherlandLineClipAndDraw( x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer); { Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to P1=(x1,y1) and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).} type edge = (LEFT,RIGHT,BOTTOM,TOP); outcode = set of edge; var accept,done : boolean; outcode0,outcode1,outcodeOut : outcode; {Outcodes for P0,P1, and whichever point lies outside the clip rectangle} x,y : real; procedure CompOutCode(x,y: real; var code:outcode); {Compute outcode for the point (x,y) } begin code := []; if y > ymax then code := [TOP] else if y < ymin then code := [BOTTOM]; if x > xmax then code := code +[RIGHT] else if x < xmin then code := code +[LEFT] end; begin accept := false; done := false; CompOutCode (x0,y0,outcode0); CompOutCode (x1,y1,outcode1); repeat if(outcode0=[]) and (outcode1=[]) then {Trivial accept and exit} begin accept := true; done:=true end else if (outcode0*outcode1) <> [] then done := true {Logical intersection is true, so trivial reject and exi t.} else {Failed both tests, so calculate the line segment to clip; from an outside point to an intersection with clip edge.} begin {At least one endpoint is outside the clip rectangle; pick it.} if outcode0 <> [] then outcodeOut := outcode0 else outcodeOut := outcode1; {Now find intersection point; use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).} if TOP in outcodeOut then begin {Divide line at top of clip rectangle} x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y := ymax end if BOTTOM in outcodeOut then begin {Divide line at bottom of clip rectangle} x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y := ymax end else if RIGHT in outcodeOut then begin {Divide line at right edge of clip rectangle} y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x := xmax end else if LEFT in outcodeOut then begin {Divide line at left edge of clip rectangle} y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x := xmin end; {Now we move outside point to intersection point to clip, and get ready for next pass.} if (outcodeOut = outcode0) then begin x0 := x; y0 := y; CompOutCode(x0,y0,outcode0) end else begin x1 := x; y1 := y; CompOutCode(x1,y1,outcode1); end end {subdivide} until done; if accept then MidpointLineReal(x0,y0,x1,y1,value) {Version for real coordin ates} end; {CohenSutherlandLineClipAndDraw} |

## Limitations of Cohen-Sutherland clipping algorithm

1) Clipping window region can be rectangular in shape only and no other polygonal shaped window is allowed.

2) Edges of rectangular shaped clipping window has to be parallel to the x-axis and y-axis.

3) If end points of line segment lies in the extreme limits i.e., one at R.H.S other at L.H.S., and on one the at top and other at the bottom (diagonally) then, even if the line doesn’t pass through the clipping region it will have logical intersection of 0000 implying that line segment will be clipped but infect it is not so.

Example 01 |

**Clip the line shown in Figure below using Cohen Sutherland Line clipping algorithm.**

**Answer:**

Using Cohen Sutherland Line clipping algorithm when we clip the line we get the line shown in *Figure* below as output.