ReactOS 0.4.15-dev-7788-g1ad9096
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{
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}
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
_STLP_DECLSPEC complex< float > _STLP_CALL sqrt(const complex< float > &)
Definition: complex.cpp:188
#define GLU_TESS_MAX_COORD
Definition: glu.h:284
#define assert(x)
Definition: debug.h:53
const GLdouble * v
Definition: gl.h:2040
double GLdouble
Definition: gl.h:163
const GLubyte * c
Definition: glext.h:8905
GLfloat f
Definition: glext.h:7540
GLenum GLsizei len
Definition: glext.h:6722
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
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
#define e
Definition: ke_i.h:82
#define f
Definition: ke_i.h:83
#define c
Definition: ke_i.h:80
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
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
Definition: mesh.h:126
GLUface * next
Definition: mesh.h:127
GLUvertex vHead
Definition: mesh.h:164
GLUface fHead
Definition: mesh.h:165
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
GLdouble coords[3]
Definition: mesh.h:121
GLUvertex * next
Definition: mesh.h:115