/* Date: Sun, 2 Nov 86 21:23:26 pst From: michael zyda To: info-iris@sumex-aim Subject: Backface Polygon Removal... One of the most frustrating things about the current IRIS product is its lack of support for double buffered hidden surface elimination. The only thing you can do is to order the drawing of your polygon's faces or, if your object is simple enough, use backface polygon removal. Backface polygon removal is a technique where the raster subsystem throws away polygons whose vertices are ordered clockwise and keeps polygons whose vertices are ordered counterclockwise. The effect of this technique is a pseudo-hidden surface effect, i.e. it works as long as you stay on the outside skin of the object you are examining. The only problem with this technique is that you need some sort of a tool to help you order your polygon's vertices. The code that follows in this file is one such tool. The code works on the principle that you know an interior point inside the 3D object whose vertices you want to order. You call a routine (bfinside) with that point. The rest of the routines in the package are shadow routines (i.e bfpolf,...) that mimick standard GL2 polygon calls. The routines in the package take care of the vertex ordering for you with respect to the interior point you provided... Michael Zyda Naval Postgraduate School, Code 52, Dept. of Computer Science Monterey, California 93943-5100 (408) 646-2305 zyda@nps-cs.arpa ucbvax!dual!lll-crg!nps-cs!zyda */ /* sample of the package's usage... */ /* this is file drawcube.c */ /* draw a cube with center (x,y,z), having the designated sidelength*/ /* the cube is drawn so that all outside facing polygons have their vertices ordered in a counterclockwise fashion (for hidden surface elimination). */ drawcube(x,y,z,sidelength) Coord x,y,z; /* center of the cube in 3-space */ float sidelength; /* length of cube's side */ { float halfside; /* length of half the side of the cube */ Coord p[4][3]; /* array to hold coords for the cube faces */ /* save current attributes */ pushattributes(); /* compute the halfside */ halfside=sidelength/2.0; /* set a point on the inside of the cube */ bfinside(x,y,z); /* back face */ p[0][0]=x-halfside; p[0][1]=y+halfside; p[0][2]=z-halfside; p[1][0]=x+halfside; p[1][1]=y+halfside; p[1][2]=z-halfside; p[2][0]=x+halfside; p[2][1]=y-halfside; p[2][2]=z-halfside; p[3][0]=x-halfside; p[3][1]=y-halfside; p[3][2]=z-halfside; color(BLUE); bfpolf(4,p); /* draw a filled blue face */ /* draw the front face */ /* this polygon is deliberately disordered. If you call straight polf without calling bfpolf, the front face will be missing when the program starts up. */ p[0][0]=x-halfside; p[0][1]=y+halfside; p[0][2]=z+halfside; p[1][0]=x+halfside; p[1][1]=y+halfside; p[1][2]=z+halfside; p[2][0]=x+halfside; p[2][1]=y-halfside; p[2][2]=z+halfside; p[3][0]=x-halfside; p[3][1]=y-halfside; p[3][2]=z+halfside; color(RED); bfpolf(4,p); /* draw a red filled face */ /* draw the top */ p[0][0]=x-halfside; p[0][1]=y+halfside; p[0][2]=z-halfside; p[1][0]=x-halfside; p[1][1]=y+halfside; p[1][2]=z+halfside; p[2][0]=x+halfside; p[2][1]=y+halfside; p[2][2]=z+halfside; p[3][0]=x+halfside; p[3][1]=y+halfside; p[3][2]=z-halfside; color(GREEN); bfpolf(4,p); /* draw a filled green face */ /* draw the bottom */ p[0][0]=x-halfside; p[0][1]=y-halfside; p[0][2]=z-halfside; p[1][0]=x+halfside; p[1][1]=y-halfside; p[1][2]=z-halfside; p[2][0]=x+halfside; p[2][1]=y-halfside; p[2][2]=z+halfside; p[3][0]=x-halfside; p[3][1]=y-halfside; p[3][2]=z+halfside; color(WHITE); bfpolf(4,p); /* draw a filled white face */ /* draw the left side */ p[0][0]=x-halfside; p[0][1]=y-halfside; p[0][2]=z-halfside; p[1][0]=x-halfside; p[1][1]=y-halfside; p[1][2]=z+halfside; p[2][0]=x-halfside; p[2][1]=y+halfside; p[2][2]=z+halfside; p[3][0]=x-halfside; p[3][1]=y+halfside; p[3][2]=z-halfside; color(YELLOW); bfpolf(4,p); /* draw a filled yellow face */ /* draw the right side */ p[0][0]=x+halfside; p[0][1]=y-halfside; p[0][2]=z-halfside; p[1][0]=x+halfside; p[1][1]=y+halfside; p[1][2]=z-halfside; p[2][0]=x+halfside; p[2][1]=y+halfside; p[2][2]=z+halfside; p[3][0]=x+halfside; p[3][1]=y-halfside; p[3][2]=z+halfside; color(MAGENTA); bfpolf(4,p); /* draw a magenta filled face */ /* the cube is drawn */ /* restore attributes before exiting */ popattributes(); } /* the actual vertex ordering package... */ /* this is file backface.c Written by: Michael J. Zyda Naval Postgraduate School Code 52, Dept. of Computer Science Monterey, California 93943-5100 (408) 646-2305 It contains routines that simplify the use of backface polygon removal. The routines: bfinside(x,y,z): This routine sets the inside point that is used for reference in orienting the polygons counterclockwise. This point should be an interior point of the object being drawn. bfmv(x,y,z): This routine issues the first point of a polygon. It is just like IRIS routine pmv. bfdr(x,y,z): This routine is used to specify all other points of the polygon after a bfmv has been called. This routine is just like IRIS routine pdr. bfclos(): This routine closes the polygon. No IRIS drawing commands are issued until this routine is called. This routine checks the orientation of the polygon with respect to the inside point and issues drawing commands for a counterclockwise oriented version of the previously input polygon. This routine is like IRIS routine pclos(). bfpolf(ncoords,xyz): This routine is just like IRIS routine polf except that is checks the orientation of the polygon before sending the coordinates. */ #include "gl.h" #include "device.h" /* Global Definitions for backface polygon removal */ #define MAXPOINTS 1000 /* max number of points in any polygon */ float insidex,insidey,insidez; /* inside point of the object This value is set by routine bfinside */ float coordinates[MAXPOINTS][3]; /* temp array to hold the polygon points */ long last = -1; /* last written coordinate */ /* this is routine bfinside This routine records the inside point of the object for polygon orientation reference. */ bfinside(x,y,z) float x,y,z; { /* record the point in a global array */ insidex = x; insidey = y; insidez = z; } /* this is routine bfmv This routine starts a polygon's definition and recording in the global data structures. */ bfmv(x,y,z) float x,y,z; { /* reset the global pointer at how many coords we have saved */ last = 0; coordinates[last][0] = x; coordinates[last][1] = y; coordinates[last][2] = z; } /* this is routine bfdr This routine saves away the polygon points in global arrays. */ bfdr(x,y,z) float x,y,z; { /* get the next spot in the save array */ last = last +1; if(last >= MAXPOINTS) { printf("BFDR: MAXPOINTS not large enough for this polygon's definition!\n"); last = last -1; return; } /* there was space, record the point */ coordinates[last][0] = x; coordinates[last][1] = y; coordinates[last][2] = z; } /* this is routine bfclos This routine checks the orientation of the polygon and then sends its definition out via IRIS graphics calls. The polygon is sent out so that its vertices are oriented counterclockwise with respect to the inside point specified. */ bfclos() { long polygonclockwise(); /* polygon orientation routine = 1 if clockwise = 0 if counterclockwise */ long i; /* temp loop variable */ /* check the polygon's orientation */ if(polygonclockwise(last+1,coordinates,insidex,insidey,insidez)) { /* the polygon is clockwise, must send out backwards */ for(i=last; i >= 0; i=i-1) { if(i == last) { pmv(coordinates[i][0],coordinates[i][1],coordinates[i][2]); } else { pdr(coordinates[i][0],coordinates[i][1],coordinates[i][2]); } } /* close the polygon */ pclos(); } /* endif polygon was oriented clockwise */ else { /* the polygon is already oriented counterclockwise */ polf(last+1,coordinates); } } /* this is routine bfpolf It performs just like routine polf in the IRIS package except that it orients the output polygon counterclockwise with respect to the inside point. */ bfpolf(ncoords,xyz) long ncoords; /* the number of coordinates */ float xyz[][3]; /* the input coordinates */ { long polygonclockwise(); /* polygon orientation routine = 1 if clockwise = 0 if counterclockwise */ long i; /* temp loop variable */ /* check the polygon's orientation */ if(polygonclockwise(ncoords,xyz,insidex,insidey,insidez)) { /* the polygon is clockwise, must send out backwards */ for(i=ncoords-1; i >= 0; i=i-1) { if(i == ncoords-1) { pmv(xyz[i][0],xyz[i][1],xyz[i][2]); } else { pdr(xyz[i][0],xyz[i][1],xyz[i][2]); } } /* close the polygon */ pclos(); } /* endif polygon was oriented clockwise */ else { /* the polygon is already oriented counterclockwise */ polf(ncoords,xyz); } } /* this is function polygonclockwise It is a function that determines if a polygon is clockwise or counterclockwise. = polygonclockwise(ncoords,xyz,xinside,yinside,zinside); ncoords = number of 3d coordinates. xyz[][3] = the 3d floating point coords. xinside, yinside, zinside = reference coordinate to compare against in determining direction. This coordinate should be inside the object for which polygon orientation is desired. Value returned = 1 if clockwise. = 0 if counterclockwise. */ #include long polygonclockwise(ncoords,xyz,xinside,yinside,zinside) long ncoords; float xyz[][3]; float xinside, yinside, zinside; { long i,j; /* loop temps */ float center[3]; /* center coordinate of the polygon */ float inside[3]; /* vector from inside point to center coordinate */ float a[3], b[3]; /* vector hold locations for the vectors that run from the center coordinate to the points of the polygon */ float xn[3], xmn[3]; /* points on line containing normal that are on opposite sides of the plane containing the polygon. */ float distton; /* distance to point n from pt inside. */ float disttomn; /* distance to point -n from pt inside. */ float normal[3]; /* the normal vector computed from a x b */ /* compute the center coordinate of the polygon */ center[0] = 0.0; center[1] = 0.0; center[2] = 0.0; for(i=0; i < ncoords; i=i+1) { for(j=0; j < 3; j=j+1) { center[j] = center[j] + xyz[i][j]; } } /* divide out by the number of coordinates */ for(j=0; j < 3; j=j+1) { center[j] = center[j]/(float)ncoords; } /* compute the vector that runs from the inside point towards the center coordinate */ inside[0] = center[0] - xinside; inside[1] = center[1] - yinside; inside[2] = center[2] - zinside; /* check the first 2 coordinates of the polygon for their direction */ /* compute vector a. It runs from the center coordinate to coordinate 0 */ for(j=0; j < 3; j=j+1) { a[j] = xyz[0][j] - center[j]; } /* compute vector b. It runs from the center coordinate to coordinate 1 */ for(j=0; j <3; j=j+1) { b[j] = xyz[1][j] - center[j]; } /* compute a x b to get the normal vector */ normal[0] = a[1]*b[2] - a[2]*b[1]; normal[1] = a[2]*b[0] - a[0]*b[2]; normal[2] = a[0]*b[1] - a[1]*b[0]; /* compute point n, offset pt from center in direction of normal */ for(j=0; j < 3; j=j+1) { xn[j] = center[j] + normal[j]; } /* compute point -n, offset pt from center in opposite direction from normal. */ for(j=0; j < 3; j=j+1) { xmn[j] = center[j] - normal[j]; } /* compute the distance the inside pt is from point n */ distton = sqrt((xn[0] - xinside) * (xn[0] - xinside) + (xn[1] - yinside) * (xn[1] - yinside) + (xn[2] - zinside) * (xn[2] - zinside)); /* compute the distance the inside pt is from point -n */ disttomn = sqrt((xmn[0] - xinside) * (xmn[0] - xinside) + (xmn[1] - yinside) * (xmn[1] - yinside) + (xmn[2] - zinside) * (xmn[2] - zinside)); /* if the dist(n) < dist(-n), then n points back towards the inside point and is on the same side of the plane as inside. a x b is then clockwise. */ if(distton < disttomn) { return(1); /* clockwise */ } else { return(0); /* counterclockwise */ } }