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