src/ot/o_instance.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  o_instance.c - routines for creating octrees for other octrees.
 *
 *     11/11/88
 */

#include  "standard.h"

#include  "object.h"

#include  "octree.h"

#include  "instance.h"

#include  "plocate.h"

/*
 *      To determine if two cubes intersect:
 *
 *      1) Check to see if any vertices of first cube are inside the
 *         second (intersection).
 *
 *      2) Check to see if all vertices of first are to one side of
 *         second (no intersection).
 *
 *      3) Perform 1 and 2 with roles reversed.
 *
 *      4) Check to see if any portion of any edge of second is inside
 *         first (intersection).
 *
 *      5) If test 4 fails, we have no intersection.
 *
 *      Note that if we were testing two boxes, we would need
 *  to check that neither had any edges inside the other to be sure.
 *      Since an octree is a volume rather than a surface, we will
 *  return a value of 2 if the cube is entirely within the octree.
 */


o_instance(o, cu)                       /* determine if cubes intersect */
OBJREC  *o;
CUBE  *cu;
{
        static int  vstart[4] = {0, 3, 5, 6};
        FVECT  cumin, cumax;
        FVECT  vert[8];
        FVECT  v1, v2;
        register INSTANCE  *in;
        int  vloc, vout;
        register int  i, j;
                                        /* get octree arguments */
        in = getinstance(o, IO_BOUNDS);
                                        /* check if cube vertex in octree */
        for (j = 0; j < 3; j++)
                cumax[j] = (cumin[j] = in->obj->scube.cuorg[j]) +
                                in->obj->scube.cusize;
        vloc = ABOVE | BELOW;
        vout = 0;
        for (i = 0; i < 8; i++) {
                for (j = 0; j < 3; j++) {
                        v1[j] = cu->cuorg[j];
                        if (i & 1<<j)
                                v1[j] += cu->cusize;
                }
                multp3(v2, v1, in->x.b.xfm);
                if (j = plocate(v2, cumin, cumax))
                        vout++;
                vloc &= j;
        }
        if (vout == 0)                  /* all inside */
                return(O_IN);
        if (vout < 8)                   /* some inside */
                return(O_HIT);
        if (vloc)                       /* all to one side */
                return(O_MISS);
                                        /* octree vertices in cube? */
        for (j = 0; j < 3; j++)
                cumax[j] = (cumin[j] = cu->cuorg[j]) + cu->cusize;
        vloc = ABOVE | BELOW;
        for (i = 0; i < 8; i++) {
                for (j = 0; j < 3; j++) {
                        v1[j] = in->obj->scube.cuorg[j];
                        if (i & 1<<j)
                                v1[j] += in->obj->scube.cusize;
                }
                multp3(vert[i], v1, in->x.f.xfm);
                if (j = plocate(vert[i], cumin, cumax))
                        vloc &= j;
                else
                        return(O_HIT);  /* vertex inside */
        }
        if (vloc)                       /* all to one side */
                return(O_MISS);
                                        /* check edges */
        for (i = 0; i < 4; i++)
                for (j = 0; j < 3; j++) {
                                                /* clip modifies vertices! */
                        VCOPY(v1, vert[vstart[i]]);
                        VCOPY(v2, vert[vstart[i] ^ 1<<j]);
                        if (clip(v1, v2, cumin, cumax))
                                return(O_HIT);          /* edge inside */
                }

        return(O_MISS);                 /* no intersection */
}
Revision:	2.2
Committed:	Sat Feb 22 02:07:26 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.1:	+3 -4 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.2	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4			/*
5			* o_instance.c - routines for creating octrees for other octrees.
6			*
7			* 11/11/88
8			*/
9
10			#include "standard.h"
11
12			#include "object.h"
13	greg	2.2
14			#include "octree.h"
15	greg	1.1
16			#include "instance.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			o_instance(o, cu) /* determine if cubes intersect */
44			OBJREC *o;
45			CUBE *cu;
46			{
47	greg	1.2	static int vstart[4] = {0, 3, 5, 6};
48	greg	1.1	FVECT cumin, cumax;
49			FVECT vert[8];
50			FVECT v1, v2;
51			register INSTANCE *in;
52			int vloc, vout;
53			register int i, j;
54			/* get octree arguments */
55	greg	1.4	in = getinstance(o, IO_BOUNDS);
56	greg	1.1	/* check if cube vertex in octree */
57			for (j = 0; j < 3; j++)
58	greg	1.7	cumax[j] = (cumin[j] = in->obj->scube.cuorg[j]) +
59			in->obj->scube.cusize;
60	greg	1.1	vloc = ABOVE \| BELOW;
61			vout = 0;
62			for (i = 0; i < 8; i++) {
63			for (j = 0; j < 3; j++) {
64			v1[j] = cu->cuorg[j];
65			if (i & 1<<j)
66			v1[j] += cu->cusize;
67			}
68	greg	1.5	multp3(v2, v1, in->x.b.xfm);
69	greg	1.1	if (j = plocate(v2, cumin, cumax))
70			vout++;
71			vloc &= j;
72			}
73			if (vout == 0) /* all inside */
74	greg	1.3	return(O_IN);
75	greg	1.1	if (vout < 8) /* some inside */
76	greg	1.3	return(O_HIT);
77	greg	1.1	if (vloc) /* all to one side */
78	greg	1.3	return(O_MISS);
79	greg	1.1	/* octree vertices in cube? */
80			for (j = 0; j < 3; j++)
81			cumax[j] = (cumin[j] = cu->cuorg[j]) + cu->cusize;
82			vloc = ABOVE \| BELOW;
83			for (i = 0; i < 8; i++) {
84			for (j = 0; j < 3; j++) {
85			v1[j] = in->obj->scube.cuorg[j];
86			if (i & 1<<j)
87			v1[j] += in->obj->scube.cusize;
88			}
89	greg	1.5	multp3(vert[i], v1, in->x.f.xfm);
90	greg	1.1	if (j = plocate(vert[i], cumin, cumax))
91			vloc &= j;
92			else
93	greg	1.3	return(O_HIT); /* vertex inside */
94	greg	1.1	}
95			if (vloc) /* all to one side */
96	greg	1.3	return(O_MISS);
97	greg	1.1	/* check edges */
98			for (i = 0; i < 4; i++)
99			for (j = 0; j < 3; j++) {
100			/* clip modifies vertices! */
101			VCOPY(v1, vert[vstart[i]]);
102			VCOPY(v2, vert[vstart[i] ^ 1<<j]);
103			if (clip(v1, v2, cumin, cumax))
104	greg	1.3	return(O_HIT); /* edge inside */
105	greg	1.1	}
106
107	greg	1.3	return(O_MISS); /* no intersection */
108	greg	1.1	}