src/ot/o_instance.c

#ifndef lint
static const char RCSid[] = "$Id: o_instance.c,v 2.5 2004/03/27 12:41:45 schorsch Exp $";
#endif
/*
 *  o_instance.c - routines for creating octrees for other octrees
 */

#include  "standard.h"

#include  "object.h"

#include  "octree.h"

#include  "instance.h"

#include  "mesh.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.
 */


static int o_cube(CUBE  *cu1, FULLXF  *fxf, CUBE  *cu);


static int
o_cube(                 /* determine if cubes intersect */
        CUBE  *cu1,
        FULLXF  *fxf,
        CUBE  *cu
)
{
        static int  vstart[4] = {0, 3, 5, 6};
        FVECT  cumin, cumax;
        FVECT  vert[8];
        FVECT  v1, v2;
        int  vloc, vout;
        register int  i, j;
                                        /* check if cube vertex in octree */
        for (j = 0; j < 3; j++)
                cumax[j] = (cumin[j] = cu1->cuorg[j]) + cu1->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, fxf->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] = cu1->cuorg[j];
                        if (i & 1<<j)
                                v1[j] += cu1->cusize;
                }
                multp3(vert[i], v1, fxf->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 */
}


int
o_instance(                     /* determine if instance intersects */
        OBJREC  *o,
        CUBE  *cu
)
{
        INSTANCE  *ins;
                                        /* get octree bounds */
        ins = getinstance(o, IO_BOUNDS);
                                        /* call o_cube to do the work */
        return(o_cube(&ins->obj->scube, &ins->x, cu));
}


int
o_mesh(                         /* determine if mesh intersects */
        OBJREC  *o,
        CUBE  *cu
)
{
        MESHINST        *mip;
                                        /* get mesh bounds */
        mip = getmeshinst(o, IO_BOUNDS);
                                        /* call o_cube to do the work */
        return(o_cube(&mip->msh->mcube, &mip->x, cu));
}
Revision:	2.6
Committed:	Tue Mar 30 16:13:00 2004 UTC (21 years, 7 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad5R3, rad5R0, rad5R1, rad4R2, rad3R7P2, rad3R7P1, rad6R0, rad4R1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9, rad4R2P1, rad4R2P2, HEAD
Changes since 2.5:	+1 -3 lines
Log Message:	Continued ANSIfication. There are only bits and pieces left now.
#	Content
1	#ifndef lint
2	static const char RCSid[] = "$Id: o_instance.c,v 2.5 2004/03/27 12:41:45 schorsch 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 o_cube(CUBE cu1, FULLXF fxf, CUBE *cu);
44
45
46	static int
47	o_cube( /* determine if cubes intersect */
48	CUBE *cu1,
49	FULLXF *fxf,
50	CUBE *cu
51	)
52	{
53	static int vstart[4] = {0, 3, 5, 6};
54	FVECT cumin, cumax;
55	FVECT vert[8];
56	FVECT v1, v2;
57	int vloc, vout;
58	register int i, j;
59	/* check if cube vertex in octree */
60	for (j = 0; j < 3; j++)
61	cumax[j] = (cumin[j] = cu1->cuorg[j]) + cu1->cusize;
62	vloc = ABOVE \| BELOW;
63	vout = 0;
64	for (i = 0; i < 8; i++) {
65	for (j = 0; j < 3; j++) {
66	v1[j] = cu->cuorg[j];
67	if (i & 1<<j)
68	v1[j] += cu->cusize;
69	}
70	multp3(v2, v1, fxf->b.xfm);
71	if ( (j = plocate(v2, cumin, cumax)) )
72	vout++;
73	vloc &= j;
74	}
75	if (vout == 0) /* all inside */
76	return(O_IN);
77	if (vout < 8) /* some inside */
78	return(O_HIT);
79	if (vloc) /* all to one side */
80	return(O_MISS);
81	/* octree vertices in cube? */
82	for (j = 0; j < 3; j++)
83	cumax[j] = (cumin[j] = cu->cuorg[j]) + cu->cusize;
84	vloc = ABOVE \| BELOW;
85	for (i = 0; i < 8; i++) {
86	for (j = 0; j < 3; j++) {
87	v1[j] = cu1->cuorg[j];
88	if (i & 1<<j)
89	v1[j] += cu1->cusize;
90	}
91	multp3(vert[i], v1, fxf->f.xfm);
92	if ( (j = plocate(vert[i], cumin, cumax)) )
93	vloc &= j;
94	else
95	return(O_HIT); /* vertex inside */
96	}
97	if (vloc) /* all to one side */
98	return(O_MISS);
99	/* check edges */
100	for (i = 0; i < 4; i++)
101	for (j = 0; j < 3; j++) {
102	/* clip modifies vertices! */
103	VCOPY(v1, vert[vstart[i]]);
104	VCOPY(v2, vert[vstart[i] ^ 1<<j]);
105	if (clip(v1, v2, cumin, cumax))
106	return(O_HIT); /* edge inside */
107	}
108
109	return(O_MISS); /* no intersection */
110	}
111
112
113	int
114	o_instance( /* determine if instance intersects */
115	OBJREC *o,
116	CUBE *cu
117	)
118	{
119	INSTANCE *ins;
120	/* get octree bounds */
121	ins = getinstance(o, IO_BOUNDS);
122	/* call o_cube to do the work */
123	return(o_cube(&ins->obj->scube, &ins->x, cu));
124	}
125
126
127	int
128	o_mesh( /* determine if mesh intersects */
129	OBJREC *o,
130	CUBE *cu
131	)
132	{
133	MESHINST *mip;
134	/* get mesh bounds */
135	mip = getmeshinst(o, IO_BOUNDS);
136	/* call o_cube to do the work */
137	return(o_cube(&mip->msh->mcube, &mip->x, cu));
138	}