ReactOS  0.4.14-dev-608-gd495a4f
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
52 static 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 
67 static 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 
76 static 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 
141 static 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>
173 extern 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.h:163
_STLP_DECLSPEC complex< float > _STLP_CALL sqrt(const complex< float > &)
Definition: complex.cpp:188
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
#define S_UNIT_Y
Definition: normal.c:191
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
static void CheckOrientation(GLUtesselator *tess)
Definition: normal.c:141
GLdouble tUnit[3]
Definition: tess.h:75
#define assert(x)
Definition: debug.h:53
GLUface * next
Definition: mesh.h:127
static int LongAxis(GLdouble v[3])
Definition: normal.c:67
GLUvertex vHead
Definition: mesh.h:164
Definition: mesh.h:126
GLdouble normal[3]
Definition: tess.h:73
#define Dot(u, v)
Definition: normal.c:49
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLdouble coords[3]
Definition: mesh.h:121
#define e
Definition: ke_i.h:82
GLdouble sUnit[3]
Definition: tess.h:74
GLUface fHead
Definition: mesh.h:165
GLfloat f
Definition: glext.h:7540
const GLubyte * c
Definition: glext.h:8905
#define TRUE
Definition: normal.c:43
GLUmesh * mesh
Definition: tess.h:66
GLenum GLsizei len
Definition: glext.h:6722
#define FALSE
Definition: normal.c:46
#define ABS(x)
Definition: normal.c:65
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
#define S_UNIT_X
Definition: normal.c:190
const GLdouble * v
Definition: gl.h:2040
GLUvertex * next
Definition: mesh.h:115
#define f
Definition: ke_i.h:83
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
void __gl_projectPolygon(GLUtesselator *tess)
Definition: normal.c:198
#define c
Definition: ke_i.h:80
#define GLU_TESS_MAX_COORD
Definition: glu.h:284
static void ComputeNormal(GLUtesselator *tess, GLdouble norm[3])
Definition: normal.c:76
GLfloat GLfloat v1
Definition: glext.h:6062