1 |
greg |
1.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 |
greg |
1.3 |
return(O_MISS); |
58 |
greg |
1.1 |
/* compute cube boundaries */ |
59 |
|
|
for (j = 0; j < 3; j++) |
60 |
greg |
1.4 |
cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY) |
61 |
|
|
+ cu->cusize + 2.0*FTINY; |
62 |
greg |
1.1 |
|
63 |
|
|
vloc = ABOVE | BELOW; /* check vertices */ |
64 |
|
|
for (i = 0; i < f->nv; i++) |
65 |
|
|
if (j = plocate(VERTEX(f,i), cumin, cumax)) |
66 |
|
|
vloc &= j; |
67 |
|
|
else |
68 |
greg |
1.3 |
return(O_HIT); /* vertex inside */ |
69 |
greg |
1.1 |
|
70 |
|
|
if (vloc) /* all to one side */ |
71 |
greg |
1.3 |
return(O_MISS); |
72 |
greg |
1.1 |
|
73 |
|
|
for (i = 0; i < f->nv; i++) { /* check edges */ |
74 |
|
|
if ((j = i + 1) >= f->nv) |
75 |
|
|
j = 0; /* wrap around */ |
76 |
|
|
VCOPY(v1, VERTEX(f,i)); /* clip modifies */ |
77 |
|
|
VCOPY(v2, VERTEX(f,j)); /* the vertices! */ |
78 |
|
|
if (clip(v1, v2, cumin, cumax)) |
79 |
greg |
1.3 |
return(O_HIT); /* edge inside */ |
80 |
greg |
1.1 |
} |
81 |
|
|
/* see if cube cuts plane */ |
82 |
|
|
for (j = 0; j < 3; j++) |
83 |
|
|
if (f->norm[j] > 0.0) { |
84 |
|
|
v1[j] = cumin[j]; |
85 |
|
|
v2[j] = cumax[j]; |
86 |
|
|
} else { |
87 |
|
|
v1[j] = cumax[j]; |
88 |
|
|
v2[j] = cumin[j]; |
89 |
|
|
} |
90 |
greg |
1.2 |
if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY) |
91 |
greg |
1.3 |
return(O_MISS); |
92 |
greg |
1.2 |
if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY) |
93 |
greg |
1.3 |
return(O_MISS); |
94 |
greg |
1.1 |
/* intersect face */ |
95 |
|
|
for (j = 0; j < 3; j++) |
96 |
|
|
v1[j] = (v1[j]*d2 - v2[j]*d1)/(d2 - d1); |
97 |
|
|
if (inface(v1, f)) |
98 |
greg |
1.3 |
return(O_HIT); |
99 |
greg |
1.1 |
|
100 |
greg |
1.3 |
return(O_MISS); /* no intersection */ |
101 |
greg |
1.1 |
} |