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.
50 /* This structure remembers the information we need about a primitive
51 * to be able to render it later, once we have determined which
52 * primitive is able to use the most triangles.
55 long size
; /* number of triangles used */
56 GLUhalfEdge
*eStart
; /* edge where this primitive starts */
57 void (*render
)(GLUtesselator
*, GLUhalfEdge
*, long);
58 /* routine to render this primitive */
61 static struct FaceCount
MaximumFan( GLUhalfEdge
*eOrig
);
62 static struct FaceCount
MaximumStrip( GLUhalfEdge
*eOrig
);
64 static void RenderFan( GLUtesselator
*tess
, GLUhalfEdge
*eStart
, long size
);
65 static void RenderStrip( GLUtesselator
*tess
, GLUhalfEdge
*eStart
, long size
);
66 static void RenderTriangle( GLUtesselator
*tess
, GLUhalfEdge
*eStart
,
69 static void RenderMaximumFaceGroup( GLUtesselator
*tess
, GLUface
*fOrig
);
70 static void RenderLonelyTriangles( GLUtesselator
*tess
, GLUface
*head
);
74 /************************ Strips and Fans decomposition ******************/
76 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
77 * fans, strips, and separate triangles. A substantial effort is made
78 * to use as few rendering primitives as possible (ie. to make the fans
79 * and strips as large as possible).
81 * The rendering output is provided as callbacks (see the api).
83 void __gl_renderMesh( GLUtesselator
*tess
, GLUmesh
*mesh
)
87 /* Make a list of separate triangles so we can render them all at once */
88 tess
->lonelyTriList
= NULL
;
90 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= f
->next
) {
93 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= f
->next
) {
95 /* We examine all faces in an arbitrary order. Whenever we find
96 * an unprocessed face F, we output a group of faces including F
97 * whose size is maximum.
99 if( f
->inside
&& ! f
->marked
) {
100 RenderMaximumFaceGroup( tess
, f
);
104 if( tess
->lonelyTriList
!= NULL
) {
105 RenderLonelyTriangles( tess
, tess
->lonelyTriList
);
106 tess
->lonelyTriList
= NULL
;
111 static void RenderMaximumFaceGroup( GLUtesselator
*tess
, GLUface
*fOrig
)
113 /* We want to find the largest triangle fan or strip of unmarked faces
114 * which includes the given face fOrig. There are 3 possible fans
115 * passing through fOrig (one centered at each vertex), and 3 possible
116 * strips (one for each CCW permutation of the vertices). Our strategy
117 * is to try all of these, and take the primitive which uses the most
118 * triangles (a greedy approach).
120 GLUhalfEdge
*e
= fOrig
->anEdge
;
121 struct FaceCount max
, newFace
;
125 max
.render
= &RenderTriangle
;
127 if( ! tess
->flagBoundary
) {
128 newFace
= MaximumFan( e
); if( newFace
.size
> max
.size
) { max
= newFace
; }
129 newFace
= MaximumFan( e
->Lnext
); if( newFace
.size
> max
.size
) { max
= newFace
; }
130 newFace
= MaximumFan( e
->Lprev
); if( newFace
.size
> max
.size
) { max
= newFace
; }
132 newFace
= MaximumStrip( e
); if( newFace
.size
> max
.size
) { max
= newFace
; }
133 newFace
= MaximumStrip( e
->Lnext
); if( newFace
.size
> max
.size
) { max
= newFace
; }
134 newFace
= MaximumStrip( e
->Lprev
); if( newFace
.size
> max
.size
) { max
= newFace
; }
136 (*(max
.render
))( tess
, max
.eStart
, max
.size
);
140 /* Macros which keep track of faces we have marked temporarily, and allow
141 * us to backtrack when necessary. With triangle fans, this is not
142 * really necessary, since the only awkward case is a loop of triangles
143 * around a single origin vertex. However with strips the situation is
144 * more complicated, and we need a general tracking method like the
147 #define Marked(f) (! (f)->inside || (f)->marked)
149 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
151 #define FreeTrail(t) if( 1 ) { \
152 while( (t) != NULL ) { \
153 (t)->marked = FALSE; t = (t)->trail; \
155 } else /* absorb trailing semicolon */
159 static struct FaceCount
MaximumFan( GLUhalfEdge
*eOrig
)
161 /* eOrig->Lface is the face we want to render. We want to find the size
162 * of a maximal fan around eOrig->Org. To do this we just walk around
163 * the origin vertex as far as possible in both directions.
165 struct FaceCount newFace
= { 0, NULL
, &RenderFan
};
166 GLUface
*trail
= NULL
;
169 for( e
= eOrig
; ! Marked( e
->Lface
); e
= e
->Onext
) {
170 AddToTrail( e
->Lface
, trail
);
173 for( e
= eOrig
; ! Marked( e
->Rface
); e
= e
->Oprev
) {
174 AddToTrail( e
->Rface
, trail
);
184 #define IsEven(n) (((n) & 1) == 0)
186 static struct FaceCount
MaximumStrip( GLUhalfEdge
*eOrig
)
188 /* Here we are looking for a maximal strip that contains the vertices
189 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
190 * reverse, such that all triangles are oriented CCW).
192 * Again we walk forward and backward as far as possible. However for
193 * strips there is a twist: to get CCW orientations, there must be
194 * an *even* number of triangles in the strip on one side of eOrig.
195 * We walk the strip starting on a side with an even number of triangles;
196 * if both side have an odd number, we are forced to shorten one side.
198 struct FaceCount newFace
= { 0, NULL
, &RenderStrip
};
199 long headSize
= 0, tailSize
= 0;
200 GLUface
*trail
= NULL
;
201 GLUhalfEdge
*e
, *eTail
, *eHead
;
203 for( e
= eOrig
; ! Marked( e
->Lface
); ++tailSize
, e
= e
->Onext
) {
204 AddToTrail( e
->Lface
, trail
);
207 if( Marked( e
->Lface
)) break;
208 AddToTrail( e
->Lface
, trail
);
212 for( e
= eOrig
; ! Marked( e
->Rface
); ++headSize
, e
= e
->Dnext
) {
213 AddToTrail( e
->Rface
, trail
);
216 if( Marked( e
->Rface
)) break;
217 AddToTrail( e
->Rface
, trail
);
221 newFace
.size
= tailSize
+ headSize
;
222 if( IsEven( tailSize
)) {
223 newFace
.eStart
= eTail
->Sym
;
224 } else if( IsEven( headSize
)) {
225 newFace
.eStart
= eHead
;
227 /* Both sides have odd length, we must shorten one of them. In fact,
228 * we must start from eHead to guarantee inclusion of eOrig->Lface.
231 newFace
.eStart
= eHead
->Onext
;
239 static void RenderTriangle( GLUtesselator
*tess
, GLUhalfEdge
*e
, long size
)
241 /* Just add the triangle to a triangle list, so we can render all
242 * the separate triangles at once.
245 AddToTrail( e
->Lface
, tess
->lonelyTriList
);
249 static void RenderLonelyTriangles( GLUtesselator
*tess
, GLUface
*f
)
251 /* Now we render all the separate triangles which could not be
252 * grouped into a triangle fan or strip.
256 int edgeState
= -1; /* force edge state output for first vertex */
258 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES
);
260 for( ; f
!= NULL
; f
= f
->trail
) {
261 /* Loop once for each edge (there will always be 3 edges) */
265 if( tess
->flagBoundary
) {
266 /* Set the "edge state" to TRUE just before we output the
267 * first vertex of each edge on the polygon boundary.
269 newState
= ! e
->Rface
->inside
;
270 if( edgeState
!= newState
) {
271 edgeState
= newState
;
272 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState
);
275 CALL_VERTEX_OR_VERTEX_DATA( e
->Org
->data
);
278 } while( e
!= f
->anEdge
);
280 CALL_END_OR_END_DATA();
284 static void RenderFan( GLUtesselator
*tess
, GLUhalfEdge
*e
, long size
)
286 /* Render as many CCW triangles as possible in a fan starting from
287 * edge "e". The fan *should* contain exactly "size" triangles
288 * (otherwise we've goofed up somewhere).
290 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN
);
291 CALL_VERTEX_OR_VERTEX_DATA( e
->Org
->data
);
292 CALL_VERTEX_OR_VERTEX_DATA( e
->Dst
->data
);
294 while( ! Marked( e
->Lface
)) {
295 e
->Lface
->marked
= TRUE
;
298 CALL_VERTEX_OR_VERTEX_DATA( e
->Dst
->data
);
302 CALL_END_OR_END_DATA();
306 static void RenderStrip( GLUtesselator
*tess
, GLUhalfEdge
*e
, long size
)
308 /* Render as many CCW triangles as possible in a strip starting from
309 * edge "e". The strip *should* contain exactly "size" triangles
310 * (otherwise we've goofed up somewhere).
312 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP
);
313 CALL_VERTEX_OR_VERTEX_DATA( e
->Org
->data
);
314 CALL_VERTEX_OR_VERTEX_DATA( e
->Dst
->data
);
316 while( ! Marked( e
->Lface
)) {
317 e
->Lface
->marked
= TRUE
;
320 CALL_VERTEX_OR_VERTEX_DATA( e
->Org
->data
);
321 if( Marked( e
->Lface
)) break;
323 e
->Lface
->marked
= TRUE
;
326 CALL_VERTEX_OR_VERTEX_DATA( e
->Dst
->data
);
330 CALL_END_OR_END_DATA();
334 /************************ Boundary contour decomposition ******************/
336 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
337 * contour for each face marked "inside". The rendering output is
338 * provided as callbacks (see the api).
340 void __gl_renderBoundary( GLUtesselator
*tess
, GLUmesh
*mesh
)
345 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= f
->next
) {
347 CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP
);
350 CALL_VERTEX_OR_VERTEX_DATA( e
->Org
->data
);
352 } while( e
!= f
->anEdge
);
353 CALL_END_OR_END_DATA();
359 /************************ Quick-and-dirty decomposition ******************/
361 #define SIGN_INCONSISTENT 2
363 static int ComputeNormal( GLUtesselator
*tess
, GLdouble norm
[3], int check
)
365 * If check==FALSE, we compute the polygon normal and place it in norm[].
366 * If check==TRUE, we check that each triangle in the fan from v0 has a
367 * consistent orientation with respect to norm[]. If triangles are
368 * consistently oriented CCW, return 1; if CW, return -1; if all triangles
369 * are degenerate return 0; otherwise (no consistent orientation) return
373 CachedVertex
*v0
= tess
->cache
;
374 CachedVertex
*vn
= v0
+ tess
->cacheCount
;
376 GLdouble dot
, xc
, yc
, zc
, xp
, yp
, zp
, n
[3];
379 /* Find the polygon normal. It is important to get a reasonable
380 * normal even when the polygon is self-intersecting (eg. a bowtie).
381 * Otherwise, the computed normal could be very tiny, but perpendicular
382 * to the true plane of the polygon due to numerical noise. Then all
383 * the triangles would appear to be degenerate and we would incorrectly
384 * decompose the polygon as a fan (or simply not render it at all).
386 * We use a sum-of-triangles normal algorithm rather than the more
387 * efficient sum-of-trapezoids method (used in CheckOrientation()
388 * in normal.c). This lets us explicitly reverse the signed area
389 * of some triangles to get a reasonable normal in the self-intersecting
393 norm
[0] = norm
[1] = norm
[2] = 0.0;
397 xc
= vc
->coords
[0] - v0
->coords
[0];
398 yc
= vc
->coords
[1] - v0
->coords
[1];
399 zc
= vc
->coords
[2] - v0
->coords
[2];
401 xp
= xc
; yp
= yc
; zp
= zc
;
402 xc
= vc
->coords
[0] - v0
->coords
[0];
403 yc
= vc
->coords
[1] - v0
->coords
[1];
404 zc
= vc
->coords
[2] - v0
->coords
[2];
406 /* Compute (vp - v0) cross (vc - v0) */
407 n
[0] = yp
*zc
- zp
*yc
;
408 n
[1] = zp
*xc
- xp
*zc
;
409 n
[2] = xp
*yc
- yp
*xc
;
411 dot
= n
[0]*norm
[0] + n
[1]*norm
[1] + n
[2]*norm
[2];
413 /* Reverse the contribution of back-facing triangles to get
414 * a reasonable normal for self-intersecting polygons (see above)
417 norm
[0] += n
[0]; norm
[1] += n
[1]; norm
[2] += n
[2];
419 norm
[0] -= n
[0]; norm
[1] -= n
[1]; norm
[2] -= n
[2];
421 } else if( dot
!= 0 ) {
422 /* Check the new orientation for consistency with previous triangles */
424 if( sign
< 0 ) return SIGN_INCONSISTENT
;
427 if( sign
> 0 ) return SIGN_INCONSISTENT
;
435 /* __gl_renderCache( tess ) takes a single contour and tries to render it
436 * as a triangle fan. This handles convex polygons, as well as some
437 * non-convex polygons if we get lucky.
439 * Returns TRUE if the polygon was successfully rendered. The rendering
440 * output is provided as callbacks (see the api).
442 GLboolean
__gl_renderCache( GLUtesselator
*tess
)
444 CachedVertex
*v0
= tess
->cache
;
445 CachedVertex
*vn
= v0
+ tess
->cacheCount
;
450 if( tess
->cacheCount
< 3 ) {
451 /* Degenerate contour -- no output */
455 norm
[0] = tess
->normal
[0];
456 norm
[1] = tess
->normal
[1];
457 norm
[2] = tess
->normal
[2];
458 if( norm
[0] == 0 && norm
[1] == 0 && norm
[2] == 0 ) {
459 ComputeNormal( tess
, norm
, FALSE
);
462 sign
= ComputeNormal( tess
, norm
, TRUE
);
463 if( sign
== SIGN_INCONSISTENT
) {
464 /* Fan triangles did not have a consistent orientation */
468 /* All triangles were degenerate */
472 /* Make sure we do the right thing for each winding rule */
473 switch( tess
->windingRule
) {
474 case GLU_TESS_WINDING_ODD
:
475 case GLU_TESS_WINDING_NONZERO
:
477 case GLU_TESS_WINDING_POSITIVE
:
478 if( sign
< 0 ) return TRUE
;
480 case GLU_TESS_WINDING_NEGATIVE
:
481 if( sign
> 0 ) return TRUE
;
483 case GLU_TESS_WINDING_ABS_GEQ_TWO
:
487 CALL_BEGIN_OR_BEGIN_DATA( tess
->boundaryOnly
? GL_LINE_LOOP
488 : (tess
->cacheCount
> 3) ? GL_TRIANGLE_FAN
491 CALL_VERTEX_OR_VERTEX_DATA( v0
->data
);
493 for( vc
= v0
+1; vc
< vn
; ++vc
) {
494 CALL_VERTEX_OR_VERTEX_DATA( vc
->data
);
497 for( vc
= vn
-1; vc
> v0
; --vc
) {
498 CALL_VERTEX_OR_VERTEX_DATA( vc
->data
);
501 CALL_END_OR_END_DATA();