ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

cohen sutherland implementation using OpenGL

Updated on July 8, 2011

Cohen Sutherland line clipping - snapshot

In computer graphics, the Cohen–Sutherland algorithm is a line clipping algorithm. The algorithm divides a 2D space into 9 regions, of which only the middle part (viewport) is visible.

In 1967, flight simulation work by Danny Cohen (engineer) lead to the development of the Cohen–Sutherland computer graphics two and three dimensional line clipping algorithms, created with Ivan Sutherland. For more, read p. 124 and p. 252 of Principles of Interactive Computer Graphics.

The algorithm

The algorithm includes, excludes or partially includes the line based on where:

  • Both endpoints are in the viewport region (bitwise OR of endpoints == 0): trivial accept.
  • Both endpoints are on the same non-visible region (bitwise AND of endpoints != 0): trivial reject.
  • Both endpoints are in different regions: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport region (there will be at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.

The numbers in the figure below are called outcodes. An outcode is computed for each of the two points in the line. The first bit is set to 1 if the point is above the viewport. The bits in the outcode represent: Top, Bottom, Right, Left. For example the outcode 1010 represents a point that is top-right of the viewport. Note that the outcodes for endpoints must be recalculated on each iteration after the clipping occurs.

Cohen sutherland line clipping using OpenGL source code

/* Refer to the Cohen_Sutherland algorithm in the textbook.  */
#include <GL/glut.h>
#include <stdio.h>
#include <stdlib.h>

#define X_COORDINATE 0
#define Y_COORDINATE 1
#define Z_COORDINATE 2
#define b0 0
#define b1 1
#define b2 2
#define b3 3

float xBoundaryRight, xBoundaryLeft, yBoundaryUpper, yBoundaryLower;
float p1[3], p2[3], p3[3], p4[3];
/* corners of the clipping rectangle, clock-wise from top left */

float givenLineSegmentP1[3], givenLineSegmentP2[3];
float clippedLineP1[3], clippedLineP2[3];

void display ();
void myInit ();

int main (int argc, char **argv) {

    char outP1[4], outP2[4], outTemp[4]; /* b0, b1, b2 and b3 as described in the text book. */
    int i;
    float m, c, tempPoint[3];

    printf ("Enter X-Boundary (right): ");
    scanf ("%f", &xBoundaryRight);
    printf ("Enter X-Boundary (left): ");
    scanf ("%f", &xBoundaryLeft);
    printf ("Enter Y-Boundary (upper): ");
    scanf ("%f", &yBoundaryUpper);
    printf ("Enter Y-Boundary (lower): ");
    scanf ("%f", &yBoundaryLower);

    printf ("Enter the first point of the the line segment to be clipped (x, y): ");
    scanf ("%f %f", &givenLineSegmentP1[X_COORDINATE], &givenLineSegmentP1[Y_COORDINATE]);

    printf ("Enter the second point of the the line segment to be clipped (x, y): ");
    scanf ("%f %f", &givenLineSegmentP2[X_COORDINATE], &givenLineSegmentP2[Y_COORDINATE]);

    givenLineSegmentP2[Z_COORDINATE] = givenLineSegmentP1[Z_COORDINATE] = 0;

    /* Now calcluate the corners of the clipping rectangle */

    p1[X_COORDINATE] = xBoundaryLeft;
    p1[Y_COORDINATE] = yBoundaryUpper;
    p1[Z_COORDINATE] = 0;

    p2[X_COORDINATE] = xBoundaryRight;
    p2[Y_COORDINATE] = yBoundaryUpper;
    p2[Z_COORDINATE] = 0;

    p3[X_COORDINATE] = xBoundaryRight;
    p3[Y_COORDINATE] = yBoundaryLower;
    p3[Z_COORDINATE] = 0;

    p4[X_COORDINATE] = xBoundaryLeft;
    p4[Y_COORDINATE] = yBoundaryLower;
    p4[Z_COORDINATE] = 0;

    /* Do the required calculations. */
    /* b0 is 1 if point is outside of yBoundaryUpper
       b1 is 1 if point is outside of yBoundaryLower 
       b2 is 1 if point is outside of xBoundaryLeft and
       b3 is 1 if point is outside of xBoundaryRight. */

    outP1[b0] = (givenLineSegmentP1[Y_COORDINATE] > yBoundaryUpper) ? 1 : 0;
    outP1[b1] = (givenLineSegmentP1[Y_COORDINATE] < yBoundaryLower) ? 1 : 0;
    outP1[b2] = (givenLineSegmentP1[X_COORDINATE] < xBoundaryLeft) ? 1 : 0;
    outP1[b3] = (givenLineSegmentP1[X_COORDINATE] > xBoundaryRight) ? 1 : 0;

    outP2[b0] = (givenLineSegmentP2[Y_COORDINATE] > yBoundaryUpper) ? 1 : 0;
    outP2[b1] = (givenLineSegmentP2[Y_COORDINATE] < yBoundaryLower) ? 1 : 0;
    outP2[b2] = (givenLineSegmentP2[X_COORDINATE] < xBoundaryLeft) ? 1 : 0;
    outP2[b3] = (givenLineSegmentP2[X_COORDINATE] > xBoundaryRight) ? 1 : 0;

  
    /* We now have four cases to consider according to the Cohen-Sutherland Algorithm. */
    /* The point may be out of more than one side. In which case, we first clip w.r.t
       one side and continue the loop (updating the outP[] and clippedLine[] arrays */

    for (i = 0; i < 3; i++) clippedLineP1[i] = givenLineSegmentP1[i];
    for (i = 0; i < 3; i++) clippedLineP2[i] = givenLineSegmentP2[i];
    /* Henceforth, only clippedLineP[] will be used. */
    while (1) { 	     
	/* case 1 */
	if (outP1[b0] == 0 && outP1[b1] == 0 && outP1[b2] == 0 && outP1[b3] == 0 &&
	    outP2[b0] == 0 && outP2[b1] == 0 && outP2[b2] == 0 && outP2[b3] == 0) {
	    break;
	}
    
	/* case 2. One point inside and the other outside the rect. Split into two cases. */
	/* case 2a: outP1 != 0 && outP2 == 0: First point is outside and second inside. */
	else if ((outP1[b0] != 0 || outP1[b1] != 0 || outP1[b2] != 0 || outP1[b3] != 0) &&
		 (outP2[b0] == 0 && outP2[b1] == 0 && outP2[b2] == 0 && outP2[b3] == 0)) {
	    if (clippedLineP1[X_COORDINATE] == clippedLineP2[X_COORDINATE]) {
		/* then m = (y2-y1)/(x2-x1) would be infinity. */
		if (outP1[b0] == 1) {
		    clippedLineP1[Y_COORDINATE] = yBoundaryUpper;
		    outP1[b0] = 0;
		}
		else {
		    clippedLineP1[Y_COORDINATE] = yBoundaryLower;
		    outP1[b2] = 0;
		}
		continue;
	    }
	    m = clippedLineP1[Y_COORDINATE]-clippedLineP2[Y_COORDINATE];
	    m /= clippedLineP1[X_COORDINATE]-clippedLineP2[X_COORDINATE];

	    if (m == 0) {
		if (outP1[b2] == 1) {
		    clippedLineP1[X_COORDINATE] = xBoundaryLeft;
		    outP1[b2] = 0;
		}
		else {
		    clippedLineP1[X_COORDINATE] = xBoundaryRight;
		    outP1[b3] = 0;
		}
		continue;
	    }
	    /* Line is neither horizontal nor vertical at this point */
	    /* We try to clip whichever bound exceeds that we see first. After clipping
	       at that point, we immediately check if the other (if any) has been clipped
	       too. */

	    c = clippedLineP1[Y_COORDINATE]-(m*clippedLineP1[X_COORDINATE]);
	    if (outP1[b0] == 1) {
		clippedLineP1[Y_COORDINATE] = yBoundaryUpper;
		clippedLineP1[X_COORDINATE] = (yBoundaryUpper-c)/m;
		outP1[b0] = 0;
		if (clippedLineP1[X_COORDINATE] <= xBoundaryRight &&
		    clippedLineP1[X_COORDINATE] >= xBoundaryLeft) {
		    outP1[b2] = outP1[b3] = 0;
		    break;
		}
		continue;
	    }
	    if (outP1[b1] == 1) {
		clippedLineP1[Y_COORDINATE] = yBoundaryLower;
		clippedLineP1[X_COORDINATE] = (yBoundaryLower-c)/m;
		outP1[b1] = 0;
		if (clippedLineP1[X_COORDINATE] <= xBoundaryRight &&
		    clippedLineP1[X_COORDINATE] >= xBoundaryLeft) {
		    outP1[b2] = outP1[b3] = 0;
		    break;
		}
		continue;
	    }
	    if (outP1[b2] == 1) {
		clippedLineP1[X_COORDINATE] = xBoundaryLeft;
		clippedLineP1[Y_COORDINATE] = (m*xBoundaryLeft)+c;
		outP1[b2] = 0;
		if (clippedLineP1[Y_COORDINATE] <= yBoundaryUpper &&
		    clippedLineP1[Y_COORDINATE] >= yBoundaryLower) {
		    outP1[b0] = outP1[b1] = 0;
		    break;
		}
		continue;
	    }
	    if (outP1[b3] == 1) {
		clippedLineP1[X_COORDINATE] = xBoundaryRight;
		clippedLineP1[Y_COORDINATE] = (m*xBoundaryRight)+c;
		outP1[b3] = 0;
		if (clippedLineP1[Y_COORDINATE] <= yBoundaryUpper &&
		    clippedLineP1[Y_COORDINATE] >= yBoundaryLower) {
		    outP1[b0] = outP1[b1] = 0;
		    break;
		}
		continue;
	    }
	}
	/* Case2b: If first point is inside and second point is outside. */
	else if ((outP2[b0] != 0 || outP2[b1] != 0 || outP2[b2] != 0 || outP2[b3] != 0) &&
		 (outP1[b0] == 0 && outP1[b1] == 0 && outP1[b2] == 0 && outP1[b3] == 0)) {
	    /* Exchange first and second points completely including outP[] and continue. */
	    for (i = 0; i < 3; i++) tempPoint[i] = clippedLineP1[i];
	    for (i = 0; i < 3; i++) clippedLineP1[i] = clippedLineP2[i];
	    for (i = 0; i < 3; i++) clippedLineP2[i] = tempPoint[i];

	    for (i = 0; i < 4; i++) outTemp[i] = outP1[i];
	    for (i = 0; i < 4; i++) outP1[i] = outP2[i];
	    for (i = 0; i < 4; i++) outP2[i] = outTemp[i];
	    continue;
	}

	/* Case 3. if (outP1 & outP2 != 0): Both points exceed the same boundary. */
	else if  ((outP1[b0] && outP2[b0] == 1) || (outP1[b1] && outP2[b1] == 1) ||
		  (outP1[b2] && outP2[b2] == 1) || (outP1[b3] && outP2[b3] == 1)) {
	    /* set clippedLineP1 and clippedLineP2 both to 0,0,0 */
	    for (i = 0; i < 3; i++) clippedLineP2[i] = clippedLineP1[i] = 0;
	    break;
	}
	/* case 4. Both endpoints are outside, but of different edges. */
	else {
	    /* Determine the points of intersection of the line with the four boundaries
	       and determine the outcode for each of these intersection points. We can
	       then estimate if the line is entirely out of the boundary or not. */
	    float intersectionP1[3], intersectionP2[3], intersectionP3[3], intersectionP4[3];
	    int validIntersections = 0;
    
	    /* check for special cases where line is horizontal or vertical. */
	    if (clippedLineP1[X_COORDINATE] == clippedLineP2[X_COORDINATE]) {
		/* The line starts from above yBoundaryUpper and ends below yBoundaryLower. */
		clippedLineP1[Y_COORDINATE] = yBoundaryUpper;
		clippedLineP2[Y_COORDINATE] = yBoundaryLower;
		break;
	    }
	    if (clippedLineP1[Y_COORDINATE] == clippedLineP2[Y_COORDINATE]) {
		/* The line starts from left of xBoundaryLeft and ends after xBoundaryRight. */
		clippedLineP1[X_COORDINATE] = xBoundaryLeft;
		clippedLineP2[X_COORDINATE] = xBoundaryRight;
		break;      
	    }
	    /* Line is neither vertical nor horizontal. Do all four intersections. */
	    m = clippedLineP1[Y_COORDINATE] - clippedLineP2[Y_COORDINATE];
	    m /= clippedLineP1[X_COORDINATE] - clippedLineP2[X_COORDINATE];
	    c = clippedLineP1[Y_COORDINATE] - (m*clippedLineP1[X_COORDINATE]);

	    /* Intersection with yBoundaryUpper */
	    intersectionP1[Y_COORDINATE] = yBoundaryUpper;
	    intersectionP1[X_COORDINATE] = (yBoundaryUpper-c)/m;
	    intersectionP1[Z_COORDINATE] = 0;

	    /* Intersection with yBoundaryLower */
	    intersectionP2[Y_COORDINATE] = yBoundaryLower;
	    intersectionP2[X_COORDINATE] = (yBoundaryLower-c)/m;
	    intersectionP2[Z_COORDINATE] = 0;

	    /* Intersection with xBoundaryLeft */
	    intersectionP3[X_COORDINATE] = xBoundaryLeft;
	    intersectionP3[Y_COORDINATE] = (m*xBoundaryLeft)+c;
	    intersectionP3[Z_COORDINATE] = 0;

	    /* Intersection with xBoundaryRight */
	    intersectionP4[X_COORDINATE] = xBoundaryRight;
	    intersectionP4[Y_COORDINATE] = (m*xBoundaryRight)+c;
	    intersectionP4[Z_COORDINATE] = 0;

	    /* If all these intersections are "outside", line is outside.
	       If atleast one intersection is inside, there is one more
	       intersection that is inside. These two intersections form 
	       the clipped line. (unless the line passes through a corner). */
	    /* The line cannot pass through the viewing rectange at more
	       than two points. If there are more than two points (among
	       the above intersection points) that are inside the viewing
	       rectangle, some are identical. We need to set clippedLineP1
	       and clippedLineP2 to these two points (if any). */
	    /* When we find the 2nd valid intersection, we verify that it is
	       not the same as the first and then only use it. At the end, if
	       we have only one valid intersection, we reset both end points to
	       0,0,0 so that the line is not displayed as clipped. */
	    /* WE NEED TO FIND UNIQUE INTERSECTION POINTS THAT ARE INSIDE (if any).  */

	    /* intersectionP1 (intersection with yBoundaryUpper). */
	    if (intersectionP1[X_COORDINATE] <= xBoundaryRight &&
		intersectionP1[X_COORDINATE] >= xBoundaryLeft) {
		for (i = 0; i < 3; i++) clippedLineP1[i] = intersectionP1[i];
		validIntersections++;
	    }
	    /* intersectionP2 (intersection with yBoundaryLower). */
	    if (intersectionP2[X_COORDINATE] <= xBoundaryRight &&
		intersectionP2[X_COORDINATE] >= xBoundaryLeft) {
		if (validIntersections == 1) {
		    /* we need to verify if its the same point as the first one. */
		    if (intersectionP2[X_COORDINATE] == clippedLineP1[X_COORDINATE] &&
			intersectionP2[Y_COORDINATE] == clippedLineP1[Y_COORDINATE] &&
			intersectionP2[Z_COORDINATE] == clippedLineP1[Z_COORDINATE])
			/* do nothing. */ ;
		    else {
			for (i = 0; i < 3; i++) clippedLineP2[i] = intersectionP2[i];
			validIntersections++;
			break;
		    } 
		}
		else {
		    for (i = 0; i < 3; i++) clippedLineP1[i] = intersectionP2[i];
		    validIntersections++;
		}
	    }
	    /* intersectionP3 (intersection with xBoundaryLeft). */
	    if (intersectionP3[Y_COORDINATE] <= yBoundaryUpper &&
		intersectionP3[Y_COORDINATE] >= yBoundaryLower) {
		if (validIntersections == 1) {
		    /* we need to verify if its the same point as the first one. */
		    if (intersectionP3[X_COORDINATE] == clippedLineP1[X_COORDINATE] &&
			intersectionP3[Y_COORDINATE] == clippedLineP1[Y_COORDINATE] &&
			intersectionP3[Z_COORDINATE] == clippedLineP1[Z_COORDINATE])
			/* do nothing. */ ;
		    else {
			for (i = 0; i < 3; i++) clippedLineP2[i] = intersectionP3[i];
			validIntersections++;
			break;
		    } 
		}
		else {
		    for (i = 0; i < 3; i++) clippedLineP1[i] = intersectionP3[i];
		    validIntersections++;
		}
	    }
	    /* intersectionP4 (intersection with xBoundaryRight */
	    if (intersectionP4[Y_COORDINATE] <= yBoundaryUpper &&
		intersectionP4[Y_COORDINATE] >= yBoundaryLower) {
		if (validIntersections == 1) {
		    /* we need to verify if its the same point as the first one. */
		    if (intersectionP4[X_COORDINATE] == clippedLineP1[X_COORDINATE] &&
			intersectionP4[Y_COORDINATE] == clippedLineP1[Y_COORDINATE] &&
			intersectionP4[Z_COORDINATE] == clippedLineP1[Z_COORDINATE])
			/* do nothing. */ ;
		    else {
			for (i = 0; i < 3; i++) clippedLineP2[i] = intersectionP4[i];
			validIntersections++;
			break;
		    } 
		}
		else {
		    for (i = 0; i < 3; i++) clippedLineP1[i] = intersectionP4[i];
		    validIntersections++;
		}
	    }
      
	    /* If validIntersections <= 1 at this point, we set both clippedLineP1
	       and clippedLineP2 to 0,0,0. Only one validIntersection means that
	       the line just passes through a corner of the viewing rectangle. */
	    if (validIntersections <= 1)
		for (i = 0; i < 3; i++) clippedLineP2[i] = clippedLineP1[i] = 0;
	    break;
	}
    }

    glutInit (&argc, argv);
    glutCreateWindow ("Cohen-Sutherland Line Clipping");
    glutInitWindowPosition (400, 400);
    glutInitWindowSize (640, 480);
    glutDisplayFunc (display);
    myInit();
    glutMainLoop();
}

void myInit () {

    glClearColor (1.0, 1.0, 1.0, 1.0);
    glPointSize (1);
    glColor3f (0.0, 0.0, 0.0);

    glMatrixMode (GL_PROJECTION);
    glLoadIdentity();
    glOrtho (-50.0, 50.0, -50.0, 50.0, -50.0, 50.0);
    glMatrixMode (GL_MODELVIEW);
}

void display () {

    /* Clipped line is displayed in red, and unclipped in black. */

    glClear (GL_COLOR_BUFFER_BIT);
    glColor3f (0.0, 0.0, 0.0);
    glBegin (GL_LINE_LOOP);
    glVertex3fv (p1);
    glVertex3fv (p2);
    glVertex3fv (p3);
    glVertex3fv (p4);
    glEnd ();
    glBegin (GL_LINES);
    glVertex3fv (givenLineSegmentP1);
    glVertex3fv (givenLineSegmentP2);
    glColor3f (1.0, 0.0, 0.0);
    glLineWidth (2);
    glVertex3fv (clippedLineP1);
    glVertex3fv (clippedLineP2);
    glEnd();

    glFlush();
}

Comments

    0 of 8192 characters used
    Post Comment

    • profile image

      blee 

      4 years ago

      thankssss

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://hubpages.com/privacy-policy#gdpr

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)