Cohen Sutherland Line Clipping

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 AND-ing 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₁ to l₅ shown in Figure 2.

Each line segment represents a case.

Note, that in Figure 2, line l₁is completely visible, l2 and l3 are completely invisible; l4 and l₅ are partially visible. We will discuss these out comings as three separate cases.

Case 1: l₁ → 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₁ 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 Cohen Sutherland line clipping 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₁, y₁ ) and (x₂ , y₂) be the coordinates of P and Q respectively.

Top case /above case:
If y₁ > yw_max then 1^st bit of bit code = 1 (signifying above) else bit code = 0

Bottom case / below case:
If y₁ < yw_min then 2^nd bit = 1 (i.e. below) else bit = 0

Left case:
If x₁ < xw_min then 3^rd bit = 1 (i.e. left) else bit = 0

Right case:
If x₁ > xw_max then 4^th bit = 1 (i.e. right) else bit = 0

To learn about another line clipping algorithm: Cyrus-Back Algorithm Visit the link

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.

Cohen-Sutherland line clipping algorithm implementation in C

#include<stdio.h>
#include<graphics.h>
#include<conio.h>

typedef unsigned int outcode;
enum { TOP=0x1, BOTTOM=0x2, RIGHT=0x4, LEFT=0x8 };

void lineclip(x0,y0,x1,y1,xwmin,ywmin,xwmax,ywmax )
float x0,y0,x1,y1,xwmin,ywmin,xwmax,ywmax;
{

	int gd,gm;
	outcode code0,code1,codeout;
	int accept = 0, done=0;

	code0 = calcode(x0,y0,xwmin,ywmin,xwmax,ywmax);
	code1 = calcode(x1,y1,xwmin,ywmin,xwmax,ywmax);

	do{
		if(!(code0 | code1))
		{ accept =1 ; done =1; }
		else
			if(code0 & code1) done = 1;
			else
			{
				float x,y;
				codeout = code0 ? code0 : code1;
				if(codeout & TOP)
				{
					x = x0 + (x1-x0)*(ywmax-y0)/(y1-y0);
				y = ywmax;
				}
				else
					if( codeout & BOTTOM)
					{
						x = x0 + (x1-x0)*(ywmin-y0)/(y1-y0);
						y = ywmin;
					}
					else
						if ( codeout & RIGHT)
						{
							y = y0+(y1-y0)*(xwmax-x0)/(x1-x0);
							x = xwmax;
						}
						else
						{
							y = y0 + (y1-y0)*(xwmin-x0)/(x1-x0);
							x = xwmin;
						}
				if( codeout == code0)
				{
					x0 = x; y0 = y;
					code0=calcode(x0,y0,xwmin,ywmin,xwmax,ywmax);
				}
				else
				{
					x1 = x; y1 = y;
					code1 = calcode(x1,y1,xwmin,ywmin,xwmax,ywmax);
				}
			}
		} while( done == 0);

	if(accept) line(x0,y0,x1,y1);

	rectangle(xwmin,ywmin,xwmax,ywmax);

	getch();

}


int calcode (x,y,xwmin,ywmin,xwmax,ywmax)
float x,y,xwmin,ywmin,xwmax,ywmax;
{
	int code =0;

	if(y> ywmax)
		code |=TOP;
	else if( y<ywmin)
		code |= BOTTOM;
	else if(x > xwmax)
		code |= RIGHT;
	else if ( x< xwmin)
		code |= LEFT;

	return(code);
}


main()
{

	float x2,y2,x1,y1,xwmin,ywmin,xwmax,ywmax;
	int gd=DETECT,gm;

	clrscr();
	initgraph(&gd,&gm,"e:\\tc\\bgi");

	printf("\n\n\tEnter the co-ordinates of Line :");

	printf("\n\n\tX1 Y1 : ");
	scanf("%f %f",&x1,&y1);

	printf("\n\n\tX2 Y2 : ");
	scanf("%f %f",&x2,&y2);


	printf("\n\tEnter the co_ordinates of window :\n ");
	printf("\n\txwmin , ywmin : ");
	scanf("%f %f",&xwmin,&ywmin);
	printf("\n\txwmax , ywmax : ");
	scanf("%f %f",&xwmax,&ywmax);
	clrscr();
	line(x1,y1,x2,y2);
	rectangle(xwmin,ywmin,xwmax,ywmax);
	getch();
	clrscr();


	lineclip(x1,y1,x2,y2,xwmin,ywmin,xwmax,ywmax );
	getch();
	closegraph();

}

<< Previous   Next>>

;