/*
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 */
}
}