src/ot/o_face.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  o_face.c - routines for creating octrees for polygonal faces.
 *
 *     8/27/85
 */

#include  "standard.h"

#include  "octree.h"

#include  "object.h"

#include  "face.h"

#include  "plocate.h"

/*
 *      The algorithm for determining a face's intersection
 *  with a cube is relatively straightforward:
 *
 *      1) Check to see if any vertices are inside the cube
 *         (intersection).
 *
 *      2) Check to see if all vertices are to one side of
 *         cube (no intersection).
 *
 *      3) Check to see if any portion of any edge is inside
 *         cube (intersection).
 *
 *      4) Check to see if the cube cuts the plane of the
 *         face and one of its edges passes through
 *         the face (intersection).
 *
 *      5) If test 4 fails, we have no intersection.
 */


o_face(o, cu)                   /* determine if face intersects cube */
OBJREC  *o;
CUBE  *cu;
{
        FVECT  cumin, cumax;
        FVECT  v1, v2;
        double  d1, d2;
        int  vloc;
        register FACE  *f;
        register int  i, j;
                                /* get face arguments */
        f = getface(o);
        if (f->area == 0.0)             /* empty face */
                return(O_MISS);
                                        /* compute cube boundaries */
        for (j = 0; j < 3; j++)
                cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
                                + cu->cusize + 2.0*FTINY;

        vloc = ABOVE | BELOW;           /* check vertices */
        for (i = 0; i < f->nv; i++)
                if (j = plocate(VERTEX(f,i), cumin, cumax))
                        vloc &= j;
                else
                        return(O_HIT);  /* vertex inside */

        if (vloc)                       /* all to one side */
                return(O_MISS);
        
        for (i = 0; i < f->nv; i++) {   /* check edges */
                if ((j = i + 1) >= f->nv)
                        j = 0;                  /* wrap around */
                VCOPY(v1, VERTEX(f,i));         /* clip modifies */
                VCOPY(v2, VERTEX(f,j));         /* the vertices! */
                if (clip(v1, v2, cumin, cumax))
                        return(O_HIT);          /* edge inside */
        }
                                        /* see if cube cuts plane */
        for (j = 0; j < 3; j++)
                if (f->norm[j] > 0.0) {
                        v1[j] = cumin[j];
                        v2[j] = cumax[j];
                } else {
                        v1[j] = cumax[j];
                        v2[j] = cumin[j];
                }
        if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
                return(O_MISS);
        if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
                return(O_MISS);
                                        /* intersect face */
        for (j = 0; j < 3; j++)
                v1[j] = (v1[j]*d2 - v2[j]*d1)/(d2 - d1);
        if (inface(v1, f))
                return(O_HIT);
        
        return(O_MISS);         /* no intersection */
}
Revision:	2.2
Committed:	Sat Feb 22 02:07:26 2003 UTC (21 years, 7 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Changes since 2.1:	+1 -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
#	Content
1	#ifndef lint
2	static const char RCSid[] = "$Id$";
3	#endif
4	/*
5	* o_face.c - routines for creating octrees for polygonal faces.
6	*
7	* 8/27/85
8	*/
9
10	#include "standard.h"
11
12	#include "octree.h"
13
14	#include "object.h"
15
16	#include "face.h"
17
18	#include "plocate.h"
19
20	/*
21	* The algorithm for determining a face's intersection
22	* with a cube is relatively straightforward:
23	*
24	* 1) Check to see if any vertices are inside the cube
25	* (intersection).
26	*
27	* 2) Check to see if all vertices are to one side of
28	* cube (no intersection).
29	*
30	* 3) Check to see if any portion of any edge is inside
31	* cube (intersection).
32	*
33	* 4) Check to see if the cube cuts the plane of the
34	* face and one of its edges passes through
35	* the face (intersection).
36	*
37	* 5) If test 4 fails, we have no intersection.
38	*/
39
40
41	o_face(o, cu) /* determine if face intersects cube */
42	OBJREC *o;
43	CUBE *cu;
44	{
45	FVECT cumin, cumax;
46	FVECT v1, v2;
47	double d1, d2;
48	int vloc;
49	register FACE *f;
50	register int i, j;
51	/* get face arguments */
52	f = getface(o);
53	if (f->area == 0.0) /* empty face */
54	return(O_MISS);
55	/* compute cube boundaries */
56	for (j = 0; j < 3; j++)
57	cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
58	+ cu->cusize + 2.0*FTINY;
59
60	vloc = ABOVE \| BELOW; /* check vertices */
61	for (i = 0; i < f->nv; i++)
62	if (j = plocate(VERTEX(f,i), cumin, cumax))
63	vloc &= j;
64	else
65	return(O_HIT); /* vertex inside */
66
67	if (vloc) /* all to one side */
68	return(O_MISS);
69
70	for (i = 0; i < f->nv; i++) { /* check edges */
71	if ((j = i + 1) >= f->nv)
72	j = 0; /* wrap around */
73	VCOPY(v1, VERTEX(f,i)); /* clip modifies */
74	VCOPY(v2, VERTEX(f,j)); /* the vertices! */
75	if (clip(v1, v2, cumin, cumax))
76	return(O_HIT); /* edge inside */
77	}
78	/* see if cube cuts plane */
79	for (j = 0; j < 3; j++)
80	if (f->norm[j] > 0.0) {
81	v1[j] = cumin[j];
82	v2[j] = cumax[j];
83	} else {
84	v1[j] = cumax[j];
85	v2[j] = cumin[j];
86	}
87	if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
88	return(O_MISS);
89	if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
90	return(O_MISS);
91	/* intersect face */
92	for (j = 0; j < 3; j++)
93	v1[j] = (v1[j]d2 - v2[j]d1)/(d2 - d1);
94	if (inface(v1, f))
95	return(O_HIT);
96
97	return(O_MISS); /* no intersection */
98	}