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