src/ot/o_face.c

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

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