src/common/face.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  face.c - routines dealing with polygonal faces.
 */

/* ====================================================================
 * The Radiance Software License, Version 1.0
 *
 * Copyright (c) 1990 - 2002 The Regents of the University of California,
 * through Lawrence Berkeley National Laboratory.   All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *         notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *           if any, must include the following acknowledgment:
 *             "This product includes Radiance software
 *                 (http://radsite.lbl.gov/)
 *                 developed by the Lawrence Berkeley National Laboratory
 *               (http://www.lbl.gov/)."
 *       Alternately, this acknowledgment may appear in the software itself,
 *       if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
 *       and "The Regents of the University of California" must
 *       not be used to endorse or promote products derived from this
 *       software without prior written permission. For written
 *       permission, please contact [email protected].
 *
 * 5. Products derived from this software may not be called "Radiance",
 *       nor may "Radiance" appear in their name, without prior written
 *       permission of Lawrence Berkeley National Laboratory.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.   IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
 * information on Lawrence Berkeley National Laboratory, please see
 * <http://www.lbl.gov/>.
 */

#include  "standard.h"

#include  "object.h"

#include  "face.h"

/*
 *      A face is given as a list of 3D vertices.  The normal
 *  direction and therefore the surface orientation is determined
 *  by the ordering of the vertices.  Looking in the direction opposite
 *  the normal (at the front of the face), the vertices will be
 *  listed in counter-clockwise order.
 *      There is no checking done to insure that the edges do not cross
 *  one another.  This was considered too expensive and should be unnecessary.
 *  The last vertex is automatically connected to the first.
 */

#ifdef  SMLFLT
#define  VERTEPS        1e-2            /* allowed vertex error */
#else
#define  VERTEPS        1e-4            /* allowed vertex error */
#endif


FACE *
getface(o)                      /* get arguments for a face */
OBJREC  *o;
{
        double  d1;
        int  badvert;
        FVECT  v1, v2, v3;
        register FACE  *f;
        register int  i;

        if ((f = (FACE *)o->os) != NULL)
                return(f);                      /* already done */

        f = (FACE *)malloc(sizeof(FACE));
        if (f == NULL)
                error(SYSTEM, "out of memory in makeface");

        if (o->oargs.nfargs < 9 || o->oargs.nfargs % 3)
                objerror(o, USER, "bad # arguments");

        o->os = (char *)f;                      /* save face */

        f->va = o->oargs.farg;
        f->nv = o->oargs.nfargs / 3;
                                                /* check for last==first */
        if (dist2(VERTEX(f,0),VERTEX(f,f->nv-1)) <= FTINY*FTINY)
                f->nv--;
                                                /* compute area and normal */
        f->norm[0] = f->norm[1] = f->norm[2] = 0.0;
        v1[0] = VERTEX(f,1)[0] - VERTEX(f,0)[0];
        v1[1] = VERTEX(f,1)[1] - VERTEX(f,0)[1];
        v1[2] = VERTEX(f,1)[2] - VERTEX(f,0)[2];
        for (i = 2; i < f->nv; i++) {
                v2[0] = VERTEX(f,i)[0] - VERTEX(f,0)[0];
                v2[1] = VERTEX(f,i)[1] - VERTEX(f,0)[1];
                v2[2] = VERTEX(f,i)[2] - VERTEX(f,0)[2];
                fcross(v3, v1, v2);
                f->norm[0] += v3[0];
                f->norm[1] += v3[1];
                f->norm[2] += v3[2];
                VCOPY(v1, v2);
        }
        f->area = normalize(f->norm);
        if (f->area == 0.0) {
                objerror(o, WARNING, "zero area");      /* used to be fatal */
                f->offset = 0.0;
                f->ax = 0;
                return(f);
        }
        f->area *= 0.5;
                                                /* compute offset */
        badvert = 0;
        f->offset = DOT(f->norm, VERTEX(f,0));
        for (i = 1; i < f->nv; i++) {
                d1 = DOT(f->norm, VERTEX(f,i));
                badvert += fabs(d1 - f->offset/i) > VERTEPS;
                f->offset += d1;
        }
        f->offset /= (double)f->nv;
        if (badvert)
                objerror(o, WARNING, "non-planar vertex");
                                                /* find axis */
        f->ax = fabs(f->norm[0]) > fabs(f->norm[1]) ? 0 : 1;
        if (fabs(f->norm[2]) > fabs(f->norm[f->ax]))
                f->ax = 2;

        return(f);
}


void
freeface(o)                     /* free memory associated with face */
OBJREC  *o;
{
        if (o->os == NULL)
                return;
        free(o->os);
        o->os = NULL;
}


int
inface(p, f)                    /* determine if point is in face */
FVECT  p;
FACE  *f;
{
        int  ncross, n;
        double  x, y;
        register int  xi, yi;
        register FLOAT  *p0, *p1;

        xi = (f->ax+1)%3;
        yi = (f->ax+2)%3;
        x = p[xi];
        y = p[yi];
        n = f->nv;
        p0 = f->va + 3*(n-1);           /* connect last to first */
        p1 = f->va;
        ncross = 0;
                                        /* positive x axis cross test */
        while (n--) {
                if ((p0[yi] > y) ^ (p1[yi] > y))
                        if (p0[xi] > x && p1[xi] > x)
                                ncross++;
                        else if (p0[xi] > x || p1[xi] > x)
                                ncross += (p1[yi] > p0[yi]) ^
                                                ((p0[yi]-y)*(p1[xi]-x) >
                                                (p0[xi]-x)*(p1[yi]-y));
                p0 = p1;
                p1 += 3;
        }
        return(ncross & 01);
}
Revision:	2.6
Committed:	Sat Feb 22 02:07:22 2003 UTC (22 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.5:	+59 -5 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
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.6	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4			/*
5			* face.c - routines dealing with polygonal faces.
6	greg	2.6	*/
7
8			/* ====================================================================
9			* The Radiance Software License, Version 1.0
10			*
11			* Copyright (c) 1990 - 2002 The Regents of the University of California,
12			* through Lawrence Berkeley National Laboratory. All rights reserved.
13			*
14			* Redistribution and use in source and binary forms, with or without
15			* modification, are permitted provided that the following conditions
16			* are met:
17			*
18			* 1. Redistributions of source code must retain the above copyright
19			* notice, this list of conditions and the following disclaimer.
20			*
21			* 2. Redistributions in binary form must reproduce the above copyright
22			* notice, this list of conditions and the following disclaimer in
23			* the documentation and/or other materials provided with the
24			* distribution.
25			*
26			* 3. The end-user documentation included with the redistribution,
27			* if any, must include the following acknowledgment:
28			* "This product includes Radiance software
29			* (http://radsite.lbl.gov/)
30			* developed by the Lawrence Berkeley National Laboratory
31			* (http://www.lbl.gov/)."
32			* Alternately, this acknowledgment may appear in the software itself,
33			* if and wherever such third-party acknowledgments normally appear.
34			*
35			* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
36			* and "The Regents of the University of California" must
37			* not be used to endorse or promote products derived from this
38			* software without prior written permission. For written
39			* permission, please contact [email protected].
40			*
41			* 5. Products derived from this software may not be called "Radiance",
42			* nor may "Radiance" appear in their name, without prior written
43			* permission of Lawrence Berkeley National Laboratory.
44			*
45			* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
46			* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
47			* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
48			* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
49			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51			* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
52			* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
53			* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
54			* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
55			* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56			* SUCH DAMAGE.
57			* ====================================================================
58	greg	1.1	*
59	greg	2.6	* This software consists of voluntary contributions made by many
60			* individuals on behalf of Lawrence Berkeley National Laboratory. For more
61			* information on Lawrence Berkeley National Laboratory, please see
62			* <http://www.lbl.gov/>.
63	greg	1.1	*/
64
65			#include "standard.h"
66
67			#include "object.h"
68
69			#include "face.h"
70
71			/*
72			* A face is given as a list of 3D vertices. The normal
73			* direction and therefore the surface orientation is determined
74			* by the ordering of the vertices. Looking in the direction opposite
75			* the normal (at the front of the face), the vertices will be
76			* listed in counter-clockwise order.
77			* There is no checking done to insure that the edges do not cross
78			* one another. This was considered too expensive and should be unnecessary.
79			* The last vertex is automatically connected to the first.
80			*/
81
82	greg	2.3	#ifdef SMLFLT
83			#define VERTEPS 1e-2 /* allowed vertex error */
84			#else
85	greg	1.1	#define VERTEPS 1e-4 /* allowed vertex error */
86	greg	2.3	#endif
87	greg	1.1
88
89			FACE *
90			getface(o) /* get arguments for a face */
91			OBJREC *o;
92			{
93			double d1;
94			int badvert;
95			FVECT v1, v2, v3;
96			register FACE *f;
97			register int i;
98
99			if ((f = (FACE *)o->os) != NULL)
100			return(f); /* already done */
101
102			f = (FACE *)malloc(sizeof(FACE));
103			if (f == NULL)
104			error(SYSTEM, "out of memory in makeface");
105
106			if (o->oargs.nfargs < 9 \|\| o->oargs.nfargs % 3)
107			objerror(o, USER, "bad # arguments");
108
109	greg	1.3	o->os = (char )f; / save face */
110
111	greg	1.1	f->va = o->oargs.farg;
112			f->nv = o->oargs.nfargs / 3;
113	greg	2.4	/* check for last==first */
114			if (dist2(VERTEX(f,0),VERTEX(f,f->nv-1)) <= FTINY*FTINY)
115			f->nv--;
116	greg	1.1	/* compute area and normal */
117			f->norm[0] = f->norm[1] = f->norm[2] = 0.0;
118	greg	2.5	v1[0] = VERTEX(f,1)[0] - VERTEX(f,0)[0];
119			v1[1] = VERTEX(f,1)[1] - VERTEX(f,0)[1];
120			v1[2] = VERTEX(f,1)[2] - VERTEX(f,0)[2];
121			for (i = 2; i < f->nv; i++) {
122	greg	1.1	v2[0] = VERTEX(f,i)[0] - VERTEX(f,0)[0];
123			v2[1] = VERTEX(f,i)[1] - VERTEX(f,0)[1];
124			v2[2] = VERTEX(f,i)[2] - VERTEX(f,0)[2];
125			fcross(v3, v1, v2);
126			f->norm[0] += v3[0];
127			f->norm[1] += v3[1];
128			f->norm[2] += v3[2];
129			VCOPY(v1, v2);
130			}
131			f->area = normalize(f->norm);
132			if (f->area == 0.0) {
133			objerror(o, WARNING, "zero area"); /* used to be fatal */
134	greg	1.2	f->offset = 0.0;
135	greg	1.1	f->ax = 0;
136			return(f);
137			}
138			f->area *= 0.5;
139	greg	1.2	/* compute offset */
140	greg	1.1	badvert = 0;
141	greg	1.2	f->offset = DOT(f->norm, VERTEX(f,0));
142	greg	1.1	for (i = 1; i < f->nv; i++) {
143			d1 = DOT(f->norm, VERTEX(f,i));
144	greg	1.2	badvert += fabs(d1 - f->offset/i) > VERTEPS;
145			f->offset += d1;
146	greg	1.1	}
147	greg	1.5	f->offset /= (double)f->nv;
148	greg	1.1	if (badvert)
149			objerror(o, WARNING, "non-planar vertex");
150			/* find axis */
151			f->ax = fabs(f->norm[0]) > fabs(f->norm[1]) ? 0 : 1;
152			if (fabs(f->norm[2]) > fabs(f->norm[f->ax]))
153			f->ax = 2;
154
155			return(f);
156			}
157
158
159	greg	2.6	void
160	greg	1.1	freeface(o) /* free memory associated with face */
161			OBJREC *o;
162			{
163	greg	1.4	if (o->os == NULL)
164			return;
165	greg	1.1	free(o->os);
166			o->os = NULL;
167			}
168
169
170	greg	2.6	int
171	greg	1.1	inface(p, f) /* determine if point is in face */
172			FVECT p;
173			FACE *f;
174			{
175			int ncross, n;
176			double x, y;
177			register int xi, yi;
178	greg	1.6	register FLOAT p0, p1;
179	greg	1.1
180			xi = (f->ax+1)%3;
181			yi = (f->ax+2)%3;
182			x = p[xi];
183			y = p[yi];
184			n = f->nv;
185			p0 = f->va + 3(n-1); / connect last to first */
186			p1 = f->va;
187			ncross = 0;
188			/* positive x axis cross test */
189			while (n--) {
190			if ((p0[yi] > y) ^ (p1[yi] > y))
191			if (p0[xi] > x && p1[xi] > x)
192			ncross++;
193			else if (p0[xi] > x \|\| p1[xi] > x)
194			ncross += (p1[yi] > p0[yi]) ^
195			((p0[yi]-y)*(p1[xi]-x) >
196			(p0[xi]-x)*(p1[yi]-y));
197			p0 = p1;
198			p1 += 3;
199			}
200			return(ncross & 01);
201			}