| 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 |
}
|
