src/ot/o_face.c

#ifndef lint
static const char       RCSid[] = "$Id: o_face.c,v 2.4 2004/03/27 12:41:45 schorsch Exp $";
#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.
 */

int
o_face(         /* 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.5
Committed:	Tue Mar 30 16:13:00 2004 UTC (20 years, 6 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad4R2P2, rad5R0, rad5R1, rad3R7P2, rad3R7P1, rad4R2, rad4R1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9, rad4R2P1, rad5R3, HEAD
Changes since 2.4:	+2 -3 lines
Log Message:	Continued ANSIfication. There are only bits and pieces left now.
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	schorsch	2.5	static const char RCSid[] = "$Id: o_face.c,v 2.4 2004/03/27 12:41:45 schorsch Exp $";
3	greg	1.1	#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	schorsch	2.4	int
41	schorsch	2.5	o_face( /* determine if face intersects cube */
42	schorsch	2.4	OBJREC *o,
43			CUBE *cu
44			)
45	greg	1.1	{
46			FVECT cumin, cumax;
47			FVECT v1, v2;
48			double d1, d2;
49			int vloc;
50			register FACE *f;
51			register int i, j;
52			/* get face arguments */
53			f = getface(o);
54			if (f->area == 0.0) /* empty face */
55	greg	1.3	return(O_MISS);
56	greg	1.1	/* compute cube boundaries */
57			for (j = 0; j < 3; j++)
58	greg	1.4	cumax[j] = (cumin[j] = cu->cuorg[j]-FTINY)
59			+ cu->cusize + 2.0*FTINY;
60	greg	1.1
61			vloc = ABOVE \| BELOW; /* check vertices */
62			for (i = 0; i < f->nv; i++)
63	schorsch	2.3	if ( (j = plocate(VERTEX(f,i), cumin, cumax)) )
64	greg	1.1	vloc &= j;
65			else
66	greg	1.3	return(O_HIT); /* vertex inside */
67	greg	1.1
68			if (vloc) /* all to one side */
69	greg	1.3	return(O_MISS);
70	greg	1.1
71			for (i = 0; i < f->nv; i++) { /* check edges */
72			if ((j = i + 1) >= f->nv)
73			j = 0; /* wrap around */
74			VCOPY(v1, VERTEX(f,i)); /* clip modifies */
75			VCOPY(v2, VERTEX(f,j)); /* the vertices! */
76			if (clip(v1, v2, cumin, cumax))
77	greg	1.3	return(O_HIT); /* edge inside */
78	greg	1.1	}
79			/* see if cube cuts plane */
80			for (j = 0; j < 3; j++)
81			if (f->norm[j] > 0.0) {
82			v1[j] = cumin[j];
83			v2[j] = cumax[j];
84			} else {
85			v1[j] = cumax[j];
86			v2[j] = cumin[j];
87			}
88	greg	1.2	if ((d1 = DOT(v1, f->norm) - f->offset) > FTINY)
89	greg	1.3	return(O_MISS);
90	greg	1.2	if ((d2 = DOT(v2, f->norm) - f->offset) < -FTINY)
91	greg	1.3	return(O_MISS);
92	greg	1.1	/* intersect face */
93			for (j = 0; j < 3; j++)
94			v1[j] = (v1[j]d2 - v2[j]d1)/(d2 - d1);
95			if (inface(v1, f))
96	greg	1.3	return(O_HIT);
97	greg	1.1
98	greg	1.3	return(O_MISS); /* no intersection */
99	greg	1.1	}