Logo ROOT  
Reference Guide
normal.c
Go to the documentation of this file.
1/*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
29 */
30/*
31** Author: Eric Veach, July 1994.
32**
33*/
34
35#include "gluos.h"
36#include "mesh.h"
37#include "tess.h"
38#include "normal.h"
39#include <math.h>
40#include <assert.h>
41
42#ifndef TRUE
43#define TRUE 1
44#endif
45#ifndef FALSE
46#define FALSE 0
47#endif
48
49#define Dot(u,v) (u[0]*v[0] + u[1]*v[1] + u[2]*v[2])
50
51#if 0
52static void Normalize( GLdouble v[3] )
53{
54 GLdouble len = v[0]*v[0] + v[1]*v[1] + v[2]*v[2];
55
56 assert( len > 0 );
57 len = sqrt( len );
58 v[0] /= len;
59 v[1] /= len;
60 v[2] /= len;
61}
62#endif
63
64#undef ABS
65#define ABS(x) ((x) < 0 ? -(x) : (x))
66
67static int LongAxis( GLdouble v[3] )
68{
69 int i = 0;
70
71 if( ABS(v[1]) > ABS(v[0]) ) { i = 1; }
72 if( ABS(v[2]) > ABS(v[i]) ) { i = 2; }
73 return i;
74}
75
76static void ComputeNormal( GLUtesselator *tess, GLdouble norm[3] )
77{
78 GLUvertex *v, *v1, *v2;
79 GLdouble c, tLen2, maxLen2;
80 GLdouble maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
81 GLUvertex *maxVert[3], *minVert[3];
82 GLUvertex *vHead = &tess->mesh->vHead;
83 int i;
84
85 maxVal[0] = maxVal[1] = maxVal[2] = -2 * GLU_TESS_MAX_COORD;
86 minVal[0] = minVal[1] = minVal[2] = 2 * GLU_TESS_MAX_COORD;
87
88 for( v = vHead->next; v != vHead; v = v->next ) {
89 for( i = 0; i < 3; ++i ) {
90 c = v->coords[i];
91 if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; }
92 if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; }
93 }
94 }
95
96 /* Find two vertices separated by at least 1/sqrt(3) of the maximum
97 * distance between any two vertices
98 */
99 i = 0;
100 if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; }
101 if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; }
102 if( minVal[i] >= maxVal[i] ) {
103 /* All vertices are the same -- normal doesn't matter */
104 norm[0] = 0; norm[1] = 0; norm[2] = 1;
105 return;
106 }
107
108 /* Look for a third vertex which forms the triangle with maximum area
109 * (Length of normal == twice the triangle area)
110 */
111 maxLen2 = 0;
112 v1 = minVert[i];
113 v2 = maxVert[i];
114 d1[0] = v1->coords[0] - v2->coords[0];
115 d1[1] = v1->coords[1] - v2->coords[1];
116 d1[2] = v1->coords[2] - v2->coords[2];
117 for( v = vHead->next; v != vHead; v = v->next ) {
118 d2[0] = v->coords[0] - v2->coords[0];
119 d2[1] = v->coords[1] - v2->coords[1];
120 d2[2] = v->coords[2] - v2->coords[2];
121 tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1];
122 tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2];
123 tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0];
124 tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2];
125 if( tLen2 > maxLen2 ) {
126 maxLen2 = tLen2;
127 norm[0] = tNorm[0];
128 norm[1] = tNorm[1];
129 norm[2] = tNorm[2];
130 }
131 }
132
133 if( maxLen2 <= 0 ) {
134 /* All points lie on a single line -- any decent normal will do */
135 norm[0] = norm[1] = norm[2] = 0;
136 norm[LongAxis(d1)] = 1;
137 }
138}
139
140
141static void CheckOrientation( GLUtesselator *tess )
142{
143 GLdouble area;
144 GLUface *f, *fHead = &tess->mesh->fHead;
145 GLUvertex *v, *vHead = &tess->mesh->vHead;
146 GLUhalfEdge *e;
147
148 /* When we compute the normal automatically, we choose the orientation
149 * so that the sum of the signed areas of all contours is non-negative.
150 */
151 area = 0;
152 for( f = fHead->next; f != fHead; f = f->next ) {
153 e = f->anEdge;
154 if( e->winding <= 0 ) continue;
155 do {
156 area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t);
157 e = e->Lnext;
158 } while( e != f->anEdge );
159 }
160 if( area < 0 ) {
161 /* Reverse the orientation by flipping all the t-coordinates */
162 for( v = vHead->next; v != vHead; v = v->next ) {
163 v->t = - v->t;
164 }
165 tess->tUnit[0] = - tess->tUnit[0];
166 tess->tUnit[1] = - tess->tUnit[1];
167 tess->tUnit[2] = - tess->tUnit[2];
168 }
169}
170
171#ifdef FOR_TRITE_TEST_PROGRAM
172#include <stdlib.h>
173extern int RandomSweep;
174#define S_UNIT_X (RandomSweep ? (2*drand48()-1) : 1.0)
175#define S_UNIT_Y (RandomSweep ? (2*drand48()-1) : 0.0)
176#else
177#if defined(SLANTED_SWEEP)
178/* The "feature merging" is not intended to be complete. There are
179 * special cases where edges are nearly parallel to the sweep line
180 * which are not implemented. The algorithm should still behave
181 * robustly (ie. produce a reasonable tesselation) in the presence
182 * of such edges, however it may miss features which could have been
183 * merged. We could minimize this effect by choosing the sweep line
184 * direction to be something unusual (ie. not parallel to one of the
185 * coordinate axes).
186 */
187#define S_UNIT_X 0.50941539564955385 /* Pre-normalized */
188#define S_UNIT_Y 0.86052074622010633
189#else
190#define S_UNIT_X 1.0
191#define S_UNIT_Y 0.0
192#endif
193#endif
194
195/* Determine the polygon normal and project vertices onto the plane
196 * of the polygon.
197 */
199{
200 GLUvertex *v, *vHead = &tess->mesh->vHead;
201 GLdouble norm[3];
202 GLdouble *sUnit, *tUnit;
203 int i, computedNormal = FALSE;
204
205 norm[0] = tess->normal[0];
206 norm[1] = tess->normal[1];
207 norm[2] = tess->normal[2];
208 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
209 ComputeNormal( tess, norm );
210 computedNormal = TRUE;
211 }
212 sUnit = tess->sUnit;
213 tUnit = tess->tUnit;
214 i = LongAxis( norm );
215
216#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
217 /* Choose the initial sUnit vector to be approximately perpendicular
218 * to the normal.
219 */
220 Normalize( norm );
221
222 sUnit[i] = 0;
223 sUnit[(i+1)%3] = S_UNIT_X;
224 sUnit[(i+2)%3] = S_UNIT_Y;
225
226 /* Now make it exactly perpendicular */
227 w = Dot( sUnit, norm );
228 sUnit[0] -= w * norm[0];
229 sUnit[1] -= w * norm[1];
230 sUnit[2] -= w * norm[2];
231 Normalize( sUnit );
232
233 /* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */
234 tUnit[0] = norm[1]*sUnit[2] - norm[2]*sUnit[1];
235 tUnit[1] = norm[2]*sUnit[0] - norm[0]*sUnit[2];
236 tUnit[2] = norm[0]*sUnit[1] - norm[1]*sUnit[0];
237 Normalize( tUnit );
238#else
239 /* Project perpendicular to a coordinate axis -- better numerically */
240 sUnit[i] = 0;
241 sUnit[(i+1)%3] = S_UNIT_X;
242 sUnit[(i+2)%3] = S_UNIT_Y;
243
244 tUnit[i] = 0;
245 tUnit[(i+1)%3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y;
246 tUnit[(i+2)%3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X;
247#endif
248
249 /* Project the vertices onto the sweep plane */
250 for( v = vHead->next; v != vHead; v = v->next ) {
251 v->s = Dot( v->coords, sUnit );
252 v->t = Dot( v->coords, tUnit );
253 }
254 if( computedNormal ) {
255 CheckOrientation( tess );
256 }
257}
double GLdouble
Definition: GL_glu.h:279
#define GLU_TESS_MAX_COORD
Definition: GL_glu.h:311
#define f(i)
Definition: RSha256.hxx:104
#define c(i)
Definition: RSha256.hxx:101
#define e(i)
Definition: RSha256.hxx:103
double sqrt(double)
Float_t Normalize(Float_t v[3])
Normalize a vector v in place.
Definition: TMath.cxx:495
void __gl_projectPolygon(GLUtesselator *tess)
Definition: normal.c:198
static void ComputeNormal(GLUtesselator *tess, GLdouble norm[3])
Definition: normal.c:76
#define S_UNIT_X
Definition: normal.c:190
static int LongAxis(GLdouble v[3])
Definition: normal.c:67
#define ABS(x)
Definition: normal.c:65
#define TRUE
Definition: normal.c:43
#define FALSE
Definition: normal.c:46
static void CheckOrientation(GLUtesselator *tess)
Definition: normal.c:141
#define Dot(u, v)
Definition: normal.c:49
#define S_UNIT_Y
Definition: normal.c:191
Definition: mesh.h:126
GLUface * next
Definition: mesh.h:127
GLUvertex vHead
Definition: mesh.h:169
GLUface fHead
Definition: mesh.h:170
GLdouble tUnit[3]
Definition: tess.h:75
GLdouble sUnit[3]
Definition: tess.h:74
GLdouble normal[3]
Definition: tess.h:73
GLUmesh * mesh
Definition: tess.h:66
GLUvertex * next
Definition: mesh.h:115