2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
36 ** Author: Eric Veach, July 1994.
38 ** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
39 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/normal.c,v 1.1 2001/03/17 00:25:41 brianp Exp $
52 #define Dot(u,v) (u[0]*v[0] + u[1]*v[1] + u[2]*v[2])
54 static void Normalize( GLdouble v
[3] )
56 GLdouble len
= v
[0]*v
[0] + v
[1]*v
[1] + v
[2]*v
[2];
65 #define ABS(x) ((x) < 0 ? -(x) : (x))
67 static int LongAxis( GLdouble v
[3] )
71 if( ABS(v
[1]) > ABS(v
[0]) ) { i
= 1; }
72 if( ABS(v
[2]) > ABS(v
[i
]) ) { i
= 2; }
76 static void ComputeNormal( GLUtesselator
*tess
, GLdouble norm
[3] )
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
;
85 maxVal
[0] = maxVal
[1] = maxVal
[2] = -2 * GLU_TESS_MAX_COORD
;
86 minVal
[0] = minVal
[1] = minVal
[2] = 2 * GLU_TESS_MAX_COORD
;
88 for( v
= vHead
->next
; v
!= vHead
; v
= v
->next
) {
89 for( i
= 0; i
< 3; ++i
) {
91 if( c
< minVal
[i
] ) { minVal
[i
] = c
; minVert
[i
] = v
; }
92 if( c
> maxVal
[i
] ) { maxVal
[i
] = c
; maxVert
[i
] = v
; }
96 /* Find two vertices separated by at least 1/sqrt(3) of the maximum
97 * distance between any two vertices
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;
108 /* Look for a third vertex which forms the triangle with maximum area
109 * (Length of normal == twice the triangle area)
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
) {
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;
141 static void CheckOrientation( GLUtesselator
*tess
)
144 GLUface
*f
, *fHead
= &tess
->mesh
->fHead
;
145 GLUvertex
*v
, *vHead
= &tess
->mesh
->vHead
;
148 /* When we compute the normal automatically, we choose the orientation
149 * so that the the sum of the signed areas of all contours is non-negative.
152 for( f
= fHead
->next
; f
!= fHead
; f
= f
->next
) {
154 if( e
->winding
<= 0 ) continue;
156 area
+= (e
->Org
->s
- e
->Dst
->s
) * (e
->Org
->t
+ e
->Dst
->t
);
158 } while( e
!= f
->anEdge
);
161 /* Reverse the orientation by flipping all the t-coordinates */
162 for( v
= vHead
->next
; v
!= vHead
; v
= v
->next
) {
165 tess
->tUnit
[0] = - tess
->tUnit
[0];
166 tess
->tUnit
[1] = - tess
->tUnit
[1];
167 tess
->tUnit
[2] = - tess
->tUnit
[2];
171 #ifdef FOR_TRITE_TEST_PROGRAM
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)
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
187 #define S_UNIT_X 0.50941539564955385 /* Pre-normalized */
188 #define S_UNIT_Y 0.86052074622010633
195 /* Determine the polygon normal and project vertices onto the plane
198 void __gl_projectPolygon( GLUtesselator
*tess
)
200 GLUvertex
*v
, *vHead
= &tess
->mesh
->vHead
;
202 GLdouble
*sUnit
, *tUnit
;
203 int i
, computedNormal
= FALSE
;
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
;
214 i
= LongAxis( norm
);
216 #if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
217 /* Choose the initial sUnit vector to be approximately perpendicular
223 sUnit
[(i
+1)%3] = S_UNIT_X
;
224 sUnit
[(i
+2)%3] = S_UNIT_Y
;
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];
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];
239 /* Project perpendicular to a coordinate axis -- better numerically */
241 sUnit
[(i
+1)%3] = S_UNIT_X
;
242 sUnit
[(i
+2)%3] = S_UNIT_Y
;
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
;
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
);
254 if( computedNormal
) {
255 CheckOrientation( tess
);