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.
39 ** $Header: //depot/main/gfx/lib/glu/libtess/render.c#5 $
52 /* This structure remembers the information we need about a primitive
53 * to be able to render it later, once we have determined which
54 * primitive is able to use the most triangles.
57 long size; /* number of triangles used */
58 GLUhalfEdge *eStart; /* edge where this primitive starts */
59 void (*render)(GLUtesselator *, GLUhalfEdge *, long);
60 /* routine to render this primitive */
63 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
64 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );
66 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
67 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
68 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
71 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
72 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );
76 /************************ Strips and Fans decomposition ******************/
78 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
79 * fans, strips, and separate triangles. A substantial effort is made
80 * to use as few rendering primitives as possible (ie. to make the fans
81 * and strips as large as possible).
83 * The rendering output is provided as callbacks (see the api).
85 void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
89 /* Make a list of separate triangles so we can render them all at once */
90 tess->lonelyTriList = NULL;
92 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
95 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
97 /* We examine all faces in an arbitrary order. Whenever we find
98 * an unprocessed face F, we output a group of faces including F
99 * whose size is maximum.
101 if( f->inside && ! f->marked ) {
102 RenderMaximumFaceGroup( tess, f );
106 if( tess->lonelyTriList != NULL ) {
107 RenderLonelyTriangles( tess, tess->lonelyTriList );
108 tess->lonelyTriList = NULL;
113 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
115 /* We want to find the largest triangle fan or strip of unmarked faces
116 * which includes the given face fOrig. There are 3 possible fans
117 * passing through fOrig (one centered at each vertex), and 3 possible
118 * strips (one for each CCW permutation of the vertices). Our strategy
119 * is to try all of these, and take the primitive which uses the most
120 * triangles (a greedy approach).
122 GLUhalfEdge *e = fOrig->anEdge;
123 struct FaceCount max, newFace;
127 max.render = &RenderTriangle;
129 if( ! tess->flagBoundary ) {
130 newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
131 newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
132 newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
134 newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
135 newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
136 newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
138 (*(max.render))( tess, max.eStart, max.size );
142 /* Macros which keep track of faces we have marked temporarily, and allow
143 * us to backtrack when necessary. With triangle fans, this is not
144 * really necessary, since the only awkward case is a loop of triangles
145 * around a single origin vertex. However with strips the situation is
146 * more complicated, and we need a general tracking method like the
149 #define Marked(f) (! (f)->inside || (f)->marked)
151 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
153 #define FreeTrail(t) do { \
154 while( (t) != NULL ) { \
155 (t)->marked = FALSE; t = (t)->trail; \
157 } while(0) /* absorb trailing semicolon */
161 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig )
163 /* eOrig->Lface is the face we want to render. We want to find the size
164 * of a maximal fan around eOrig->Org. To do this we just walk around
165 * the origin vertex as far as possible in both directions.
167 struct FaceCount newFace = { 0, NULL, &RenderFan };
168 GLUface *trail = NULL;
171 for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
172 AddToTrail( e->Lface, trail );
175 for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
176 AddToTrail( e->Rface, trail );
186 #define IsEven(n) (((n) & 1) == 0)
188 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig )
190 /* Here we are looking for a maximal strip that contains the vertices
191 * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
192 * reverse, such that all triangles are oriented CCW).
194 * Again we walk forward and backward as far as possible. However for
195 * strips there is a twist: to get CCW orientations, there must be
196 * an *even* number of triangles in the strip on one side of eOrig.
197 * We walk the strip starting on a side with an even number of triangles;
198 * if both side have an odd number, we are forced to shorten one side.
200 struct FaceCount newFace = { 0, NULL, &RenderStrip };
201 long headSize = 0, tailSize = 0;
202 GLUface *trail = NULL;
203 GLUhalfEdge *e, *eTail, *eHead;
205 for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
206 AddToTrail( e->Lface, trail );
209 if( Marked( e->Lface )) break;
210 AddToTrail( e->Lface, trail );
214 for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
215 AddToTrail( e->Rface, trail );
218 if( Marked( e->Rface )) break;
219 AddToTrail( e->Rface, trail );
223 newFace.size = tailSize + headSize;
224 if( IsEven( tailSize )) {
225 newFace.eStart = eTail->Sym;
226 } else if( IsEven( headSize )) {
227 newFace.eStart = eHead;
229 /* Both sides have odd length, we must shorten one of them. In fact,
230 * we must start from eHead to guarantee inclusion of eOrig->Lface.
233 newFace.eStart = eHead->Onext;
241 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
243 /* Just add the triangle to a triangle list, so we can render all
244 * the separate triangles at once.
247 AddToTrail( e->Lface, tess->lonelyTriList );
251 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
253 /* Now we render all the separate triangles which could not be
254 * grouped into a triangle fan or strip.
258 int edgeState = -1; /* force edge state output for first vertex */
260 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES );
262 for( ; f != NULL; f = f->trail ) {
263 /* Loop once for each edge (there will always be 3 edges) */
267 if( tess->flagBoundary ) {
268 /* Set the "edge state" to TRUE just before we output the
269 * first vertex of each edge on the polygon boundary.
271 newState = ! e->Rface->inside;
272 if( edgeState != newState ) {
273 edgeState = newState;
274 CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState );
277 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
280 } while( e != f->anEdge );
282 CALL_END_OR_END_DATA();
286 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
288 /* Render as many CCW triangles as possible in a fan starting from
289 * edge "e". The fan *should* contain exactly "size" triangles
290 * (otherwise we've goofed up somewhere).
292 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN );
293 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
294 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
296 while( ! Marked( e->Lface )) {
297 e->Lface->marked = TRUE;
300 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
304 CALL_END_OR_END_DATA();
308 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
310 /* Render as many CCW triangles as possible in a strip starting from
311 * edge "e". The strip *should* contain exactly "size" triangles
312 * (otherwise we've goofed up somewhere).
314 CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP );
315 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
316 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
318 while( ! Marked( e->Lface )) {
319 e->Lface->marked = TRUE;
322 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
323 if( Marked( e->Lface )) break;
325 e->Lface->marked = TRUE;
328 CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
332 CALL_END_OR_END_DATA();
336 /************************ Boundary contour decomposition ******************/
338 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
339 * contour for each face marked "inside". The rendering output is
340 * provided as callbacks (see the api).
342 void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh )
347 for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
349 CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP );
352 CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
354 } while( e != f->anEdge );
355 CALL_END_OR_END_DATA();
361 /************************ Quick-and-dirty decomposition ******************/
363 #define SIGN_INCONSISTENT 2
365 static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check )
367 * If check==FALSE, we compute the polygon normal and place it in norm[].
368 * If check==TRUE, we check that each triangle in the fan from v0 has a
369 * consistent orientation with respect to norm[]. If triangles are
370 * consistently oriented CCW, return 1; if CW, return -1; if all triangles
371 * are degenerate return 0; otherwise (no consistent orientation) return
375 CachedVertex *v0 = tess->cache;
376 CachedVertex *vn = v0 + tess->cacheCount;
378 GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
381 /* Find the polygon normal. It is important to get a reasonable
382 * normal even when the polygon is self-intersecting (eg. a bowtie).
383 * Otherwise, the computed normal could be very tiny, but perpendicular
384 * to the true plane of the polygon due to numerical noise. Then all
385 * the triangles would appear to be degenerate and we would incorrectly
386 * decompose the polygon as a fan (or simply not render it at all).
388 * We use a sum-of-triangles normal algorithm rather than the more
389 * efficient sum-of-trapezoids method (used in CheckOrientation()
390 * in normal.c). This lets us explicitly reverse the signed area
391 * of some triangles to get a reasonable normal in the self-intersecting
395 norm[0] = norm[1] = norm[2] = 0.0;
399 xc = vc->coords[0] - v0->coords[0];
400 yc = vc->coords[1] - v0->coords[1];
401 zc = vc->coords[2] - v0->coords[2];
403 xp = xc; yp = yc; zp = zc;
404 xc = vc->coords[0] - v0->coords[0];
405 yc = vc->coords[1] - v0->coords[1];
406 zc = vc->coords[2] - v0->coords[2];
408 /* Compute (vp - v0) cross (vc - v0) */
409 n[0] = yp*zc - zp*yc;
410 n[1] = zp*xc - xp*zc;
411 n[2] = xp*yc - yp*xc;
413 dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
415 /* Reverse the contribution of back-facing triangles to get
416 * a reasonable normal for self-intersecting polygons (see above)
419 norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
421 norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
423 } else if( dot != 0 ) {
424 /* Check the new orientation for consistency with previous triangles */
426 if( sign < 0 ) return SIGN_INCONSISTENT;
429 if( sign > 0 ) return SIGN_INCONSISTENT;
437 /* __gl_renderCache( tess ) takes a single contour and tries to render it
438 * as a triangle fan. This handles convex polygons, as well as some
439 * non-convex polygons if we get lucky.
441 * Returns TRUE if the polygon was successfully rendered. The rendering
442 * output is provided as callbacks (see the api).
444 GLboolean __gl_renderCache( GLUtesselator *tess )
446 CachedVertex *v0 = tess->cache;
447 CachedVertex *vn = v0 + tess->cacheCount;
452 if( tess->cacheCount < 3 ) {
453 /* Degenerate contour -- no output */
457 norm[0] = tess->normal[0];
458 norm[1] = tess->normal[1];
459 norm[2] = tess->normal[2];
460 if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
461 ComputeNormal( tess, norm, FALSE );
464 sign = ComputeNormal( tess, norm, TRUE );
465 if( sign == SIGN_INCONSISTENT ) {
466 /* Fan triangles did not have a consistent orientation */
470 /* All triangles were degenerate */
474 /* Make sure we do the right thing for each winding rule */
475 switch( tess->windingRule ) {
476 case GLU_TESS_WINDING_ODD:
477 case GLU_TESS_WINDING_NONZERO:
479 case GLU_TESS_WINDING_POSITIVE:
480 if( sign < 0 ) return TRUE;
482 case GLU_TESS_WINDING_NEGATIVE:
483 if( sign > 0 ) return TRUE;
485 case GLU_TESS_WINDING_ABS_GEQ_TWO:
489 CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP
490 : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN
493 CALL_VERTEX_OR_VERTEX_DATA( v0->data );
495 for( vc = v0+1; vc < vn; ++vc ) {
496 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
499 for( vc = vn-1; vc > v0; --vc ) {
500 CALL_VERTEX_OR_VERTEX_DATA( vc->data );
503 CALL_END_OR_END_DATA();