| 1 |
#ifndef lint
|
| 2 |
static const char RCSid[] = "$Id: o_face.c,v 2.4 2004/03/27 12:41:45 schorsch Exp $";
|
| 3 |
#endif
|
| 4 |
/*
|
| 5 |
* o_face.c - routines for creating octrees for polygonal faces.
|
| 6 |
*
|
| 7 |
* 8/27/85
|
| 8 |
*/
|
| 9 |
|
| 10 |
#include "standard.h"
|
| 11 |
|
| 12 |
#include "octree.h"
|
| 13 |
|
| 14 |
#include "object.h"
|
| 15 |
|
| 16 |
#include "face.h"
|
| 17 |
|
| 18 |
#include "plocate.h"
|
| 19 |
|
| 20 |
/*
|
| 21 |
* The algorithm for determining a face's intersection
|
| 22 |
* with a cube is relatively straightforward:
|
| 23 |
*
|
| 24 |
* 1) Check to see if any vertices are inside the cube
|
| 25 |
* (intersection).
|
| 26 |
*
|
| 27 |
* 2) Check to see if all vertices are to one side of
|
| 28 |
* cube (no intersection).
|
| 29 |
*
|
| 30 |
* 3) Check to see if any portion of any edge is inside
|
| 31 |
* cube (intersection).
|
| 32 |
*
|
| 33 |
* 4) Check to see if the cube cuts the plane of the
|
| 34 |
* face and one of its edges passes through
|
| 35 |
* the face (intersection).
|
| 36 |
*
|
| 37 |
* 5) If test 4 fails, we have no intersection.
|
| 38 |
*/
|
| 39 |
|
| 40 |
int
|
| 41 |
o_face( /* determine if face intersects cube */
|
| 42 |
OBJREC *o,
|
| 43 |
CUBE *cu
|
| 44 |
)
|
| 45 |
{
|
| 46 |
FVECT cumin, cumax;
|
| 47 |
FVECT v1, v2;
|
| 48 |
double d1, d2;
|
| 49 |
int vloc;
|
| 50 |
register FACE *f;
|
| 51 |
register int i, j;
|
| 52 |
/* get face arguments */
|
| 53 |
f = getface(o);
|
| 54 |
if (f->area == 0.0) /* empty face */
|
| 55 |
return(O_MISS);
|
| 56 |
/* compute cube boundaries */
|
| 57 |
for (j = 0; j < 3; j++)
|
| 58 |
cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
|
| 59 |
+ cu->cusize + 2.0*FTINY;
|
| 60 |
|
| 61 |
vloc = ABOVE | BELOW; /* check vertices */
|
| 62 |
for (i = 0; i < f->nv; i++)
|
| 63 |
if ( (j = plocate(VERTEX(f,i), cumin, cumax)) )
|
| 64 |
vloc &= j;
|
| 65 |
else
|
| 66 |
return(O_HIT); /* vertex inside */
|
| 67 |
|
| 68 |
if (vloc) /* all to one side */
|
| 69 |
return(O_MISS);
|
| 70 |
|
| 71 |
for (i = 0; i < f->nv; i++) { /* check edges */
|
| 72 |
if ((j = i + 1) >= f->nv)
|
| 73 |
j = 0; /* wrap around */
|
| 74 |
VCOPY(v1, VERTEX(f,i)); /* clip modifies */
|
| 75 |
VCOPY(v2, VERTEX(f,j)); /* the vertices! */
|
| 76 |
if (clip(v1, v2, cumin, cumax))
|
| 77 |
return(O_HIT); /* edge inside */
|
| 78 |
}
|
| 79 |
/* see if cube cuts plane */
|
| 80 |
for (j = 0; j < 3; j++)
|
| 81 |
if (f->norm[j] > 0.0) {
|
| 82 |
v1[j] = cumin[j];
|
| 83 |
v2[j] = cumax[j];
|
| 84 |
} else {
|
| 85 |
v1[j] = cumax[j];
|
| 86 |
v2[j] = cumin[j];
|
| 87 |
}
|
| 88 |
if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
|
| 89 |
return(O_MISS);
|
| 90 |
if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
|
| 91 |
return(O_MISS);
|
| 92 |
/* intersect face */
|
| 93 |
for (j = 0; j < 3; j++)
|
| 94 |
v1[j] = (v1[j]*d2 - v2[j]*d1)/(d2 - d1);
|
| 95 |
if (inface(v1, f))
|
| 96 |
return(O_HIT);
|
| 97 |
|
| 98 |
return(O_MISS); /* no intersection */
|
| 99 |
}
|
