1 |
greg |
1.7 |
/* Copyright (c) 1991 Regents of the University of California */ |
2 |
greg |
1.1 |
|
3 |
|
|
#ifndef lint |
4 |
|
|
static char SCCSid[] = "$SunId$ LBL"; |
5 |
|
|
#endif |
6 |
|
|
|
7 |
|
|
/* |
8 |
|
|
* o_instance.c - routines for creating octrees for other octrees. |
9 |
|
|
* |
10 |
|
|
* 11/11/88 |
11 |
|
|
*/ |
12 |
|
|
|
13 |
|
|
#include "standard.h" |
14 |
|
|
|
15 |
|
|
#include "object.h" |
16 |
|
|
|
17 |
|
|
#include "instance.h" |
18 |
|
|
|
19 |
|
|
#include "plocate.h" |
20 |
|
|
|
21 |
|
|
/* |
22 |
|
|
* To determine if two cubes intersect: |
23 |
|
|
* |
24 |
|
|
* 1) Check to see if any vertices of first cube are inside the |
25 |
|
|
* second (intersection). |
26 |
|
|
* |
27 |
|
|
* 2) Check to see if all vertices of first are to one side of |
28 |
|
|
* second (no intersection). |
29 |
|
|
* |
30 |
|
|
* 3) Perform 1 and 2 with roles reversed. |
31 |
|
|
* |
32 |
|
|
* 4) Check to see if any portion of any edge of second is inside |
33 |
|
|
* first (intersection). |
34 |
|
|
* |
35 |
|
|
* 5) If test 4 fails, we have no intersection. |
36 |
|
|
* |
37 |
|
|
* Note that if we were testing two boxes, we would need |
38 |
|
|
* to check that neither had any edges inside the other to be sure. |
39 |
|
|
* Since an octree is a volume rather than a surface, we will |
40 |
|
|
* return a value of 2 if the cube is entirely within the octree. |
41 |
|
|
*/ |
42 |
|
|
|
43 |
|
|
|
44 |
|
|
o_instance(o, cu) /* determine if cubes intersect */ |
45 |
|
|
OBJREC *o; |
46 |
|
|
CUBE *cu; |
47 |
|
|
{ |
48 |
greg |
1.2 |
static int vstart[4] = {0, 3, 5, 6}; |
49 |
greg |
1.1 |
FVECT cumin, cumax; |
50 |
|
|
FVECT vert[8]; |
51 |
|
|
FVECT v1, v2; |
52 |
|
|
register INSTANCE *in; |
53 |
|
|
int vloc, vout; |
54 |
|
|
register int i, j; |
55 |
|
|
/* get octree arguments */ |
56 |
greg |
1.4 |
in = getinstance(o, IO_BOUNDS); |
57 |
greg |
1.1 |
/* check if cube vertex in octree */ |
58 |
|
|
for (j = 0; j < 3; j++) |
59 |
greg |
1.7 |
cumax[j] = (cumin[j] = in->obj->scube.cuorg[j]) + |
60 |
|
|
in->obj->scube.cusize; |
61 |
greg |
1.1 |
vloc = ABOVE | BELOW; |
62 |
|
|
vout = 0; |
63 |
|
|
for (i = 0; i < 8; i++) { |
64 |
|
|
for (j = 0; j < 3; j++) { |
65 |
|
|
v1[j] = cu->cuorg[j]; |
66 |
|
|
if (i & 1<<j) |
67 |
|
|
v1[j] += cu->cusize; |
68 |
|
|
} |
69 |
greg |
1.5 |
multp3(v2, v1, in->x.b.xfm); |
70 |
greg |
1.1 |
if (j = plocate(v2, cumin, cumax)) |
71 |
|
|
vout++; |
72 |
|
|
vloc &= j; |
73 |
|
|
} |
74 |
|
|
if (vout == 0) /* all inside */ |
75 |
greg |
1.3 |
return(O_IN); |
76 |
greg |
1.1 |
if (vout < 8) /* some inside */ |
77 |
greg |
1.3 |
return(O_HIT); |
78 |
greg |
1.1 |
if (vloc) /* all to one side */ |
79 |
greg |
1.3 |
return(O_MISS); |
80 |
greg |
1.1 |
/* octree vertices in cube? */ |
81 |
|
|
for (j = 0; j < 3; j++) |
82 |
|
|
cumax[j] = (cumin[j] = cu->cuorg[j]) + cu->cusize; |
83 |
|
|
vloc = ABOVE | BELOW; |
84 |
|
|
for (i = 0; i < 8; i++) { |
85 |
|
|
for (j = 0; j < 3; j++) { |
86 |
|
|
v1[j] = in->obj->scube.cuorg[j]; |
87 |
|
|
if (i & 1<<j) |
88 |
|
|
v1[j] += in->obj->scube.cusize; |
89 |
|
|
} |
90 |
greg |
1.5 |
multp3(vert[i], v1, in->x.f.xfm); |
91 |
greg |
1.1 |
if (j = plocate(vert[i], cumin, cumax)) |
92 |
|
|
vloc &= j; |
93 |
|
|
else |
94 |
greg |
1.3 |
return(O_HIT); /* vertex inside */ |
95 |
greg |
1.1 |
} |
96 |
|
|
if (vloc) /* all to one side */ |
97 |
greg |
1.3 |
return(O_MISS); |
98 |
greg |
1.1 |
/* check edges */ |
99 |
|
|
for (i = 0; i < 4; i++) |
100 |
|
|
for (j = 0; j < 3; j++) { |
101 |
|
|
/* clip modifies vertices! */ |
102 |
|
|
VCOPY(v1, vert[vstart[i]]); |
103 |
|
|
VCOPY(v2, vert[vstart[i] ^ 1<<j]); |
104 |
|
|
if (clip(v1, v2, cumin, cumax)) |
105 |
greg |
1.3 |
return(O_HIT); /* edge inside */ |
106 |
greg |
1.1 |
} |
107 |
|
|
|
108 |
greg |
1.3 |
return(O_MISS); /* no intersection */ |
109 |
greg |
1.1 |
} |