src/ot/o_instance.c

/* Copyright (c) 1991 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#endif

/*
 *  o_instance.c - routines for creating octrees for other octrees.
 *
 *     11/11/88
 */

#include  "standard.h"

#include  "object.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.1
Committed:	Tue Nov 12 17:00:49 1991 UTC (34 years ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.7:	+0 -0 lines
Log Message:	updated revision number for release 2.0
#	User	Rev	Content
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	}