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.
52 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
53 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
58 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
59 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
61 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
62 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
63 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
64 GLfloat weight[4], void **dataOut ) {}
65 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
68 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
69 void *polygonData ) {}
70 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
71 void *polygonData ) {}
72 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
73 void *polygonData ) {}
74 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
75 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
76 void *polygonData ) {}
77 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
81 void *polygonData ) {}
83 /* Half-edges are allocated in pairs (see mesh.c) */
84 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
87 #define MAX(a,b) ((a) > (b) ? (a) : (b))
88 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
89 MAX(sizeof(GLUvertex),sizeof(GLUface))))
92 GLUtesselator * GLAPIENTRY
97 /* Only initialize fields which can be changed by the api. Other fields
98 * are initialized where they are used.
101 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
103 return 0; /* out of memory */
106 tess->state = T_DORMANT;
112 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
113 tess->windingRule = GLU_TESS_WINDING_ODD;
114 tess->flagBoundary = FALSE;
115 tess->boundaryOnly = FALSE;
117 tess->callBegin = &noBegin;
118 tess->callEdgeFlag = &noEdgeFlag;
119 tess->callVertex = &noVertex;
120 tess->callEnd = &noEnd;
122 tess->callError = &noError;
123 tess->callCombine = &noCombine;
124 tess->callMesh = &noMesh;
126 tess->callBeginData= &__gl_noBeginData;
127 tess->callEdgeFlagData= &__gl_noEdgeFlagData;
128 tess->callVertexData= &__gl_noVertexData;
129 tess->callEndData= &__gl_noEndData;
130 tess->callErrorData= &__gl_noErrorData;
131 tess->callCombineData= &__gl_noCombineData;
133 tess->polygonData= NULL;
138 static void MakeDormant( GLUtesselator *tess )
140 /* Return the tessellator to its original dormant state. */
142 if( tess->mesh != NULL ) {
143 __gl_meshDeleteMesh( tess->mesh );
145 tess->state = T_DORMANT;
146 tess->lastEdge = NULL;
150 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
152 static void GotoState( GLUtesselator *tess, enum TessState newState )
154 while( tess->state != newState ) {
155 /* We change the current state one level at a time, to get to
158 if( tess->state < newState ) {
159 switch( tess->state ) {
161 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
162 gluTessBeginPolygon( tess, NULL );
165 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
166 gluTessBeginContour( tess );
172 switch( tess->state ) {
174 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
175 gluTessEndContour( tess );
178 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
179 /* gluTessEndPolygon( tess ) is too much work! */
191 gluDeleteTess( GLUtesselator *tess )
193 RequireState( tess, T_DORMANT );
199 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
204 case GLU_TESS_TOLERANCE:
205 if( value < 0.0 || value > 1.0 ) break;
206 tess->relTolerance = value;
209 case GLU_TESS_WINDING_RULE:
210 windingRule = (GLenum) value;
211 if( windingRule != value ) break; /* not an integer */
213 switch( windingRule ) {
214 case GLU_TESS_WINDING_ODD:
215 case GLU_TESS_WINDING_NONZERO:
216 case GLU_TESS_WINDING_POSITIVE:
217 case GLU_TESS_WINDING_NEGATIVE:
218 case GLU_TESS_WINDING_ABS_GEQ_TWO:
219 tess->windingRule = windingRule;
225 case GLU_TESS_BOUNDARY_ONLY:
226 tess->boundaryOnly = (value != 0);
230 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
233 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
236 /* Returns tessellator property */
238 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
241 case GLU_TESS_TOLERANCE:
242 /* tolerance should be in range [0..1] */
243 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
244 *value= tess->relTolerance;
246 case GLU_TESS_WINDING_RULE:
247 assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
248 tess->windingRule == GLU_TESS_WINDING_NONZERO ||
249 tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
250 tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
251 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
252 *value= tess->windingRule;
254 case GLU_TESS_BOUNDARY_ONLY:
255 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
256 *value= tess->boundaryOnly;
260 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
263 } /* gluGetTessProperty() */
266 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
274 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
278 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
280 case GLU_TESS_BEGIN_DATA:
281 tess->callBeginData = (fn == NULL) ?
282 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
284 case GLU_TESS_EDGE_FLAG:
285 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
286 (void (GLAPIENTRY *)(GLboolean)) fn;
287 /* If the client wants boundary edges to be flagged,
288 * we render everything as separate triangles (no strips or fans).
290 tess->flagBoundary = (fn != NULL);
292 case GLU_TESS_EDGE_FLAG_DATA:
293 tess->callEdgeFlagData= (fn == NULL) ?
294 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
295 /* If the client wants boundary edges to be flagged,
296 * we render everything as separate triangles (no strips or fans).
298 tess->flagBoundary = (fn != NULL);
300 case GLU_TESS_VERTEX:
301 tess->callVertex = (fn == NULL) ? &noVertex :
302 (void (GLAPIENTRY *)(void *)) fn;
304 case GLU_TESS_VERTEX_DATA:
305 tess->callVertexData = (fn == NULL) ?
306 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
309 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
311 case GLU_TESS_END_DATA:
312 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
313 (void (GLAPIENTRY *)(void *)) fn;
316 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
318 case GLU_TESS_ERROR_DATA:
319 tess->callErrorData = (fn == NULL) ?
320 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
322 case GLU_TESS_COMBINE:
323 tess->callCombine = (fn == NULL) ? &noCombine :
324 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
326 case GLU_TESS_COMBINE_DATA:
327 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
328 (void (GLAPIENTRY *)(GLdouble [3],
335 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
338 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
343 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
349 /* Make a self-loop (one vertex, one edge). */
351 e = __gl_meshMakeEdge( tess->mesh );
352 if (e == NULL) return 0;
353 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
355 /* Create a new vertex and edge which immediately follow e
356 * in the ordering around the left face.
358 if (__gl_meshSplitEdge( e ) == NULL) return 0;
362 /* The new vertex is now e->Org. */
364 e->Org->coords[0] = coords[0];
365 e->Org->coords[1] = coords[1];
366 e->Org->coords[2] = coords[2];
368 /* The winding of an edge says how the winding number changes as we
369 * cross from the edge''s right face to its left face. We add the
370 * vertices in such an order that a CCW contour will add +1 to
371 * the winding number of the region inside the contour.
374 e->Sym->winding = -1;
382 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
384 CachedVertex *v = &tess->cache[tess->cacheCount];
387 v->coords[0] = coords[0];
388 v->coords[1] = coords[1];
389 v->coords[2] = coords[2];
394 static int EmptyCache( GLUtesselator *tess )
396 CachedVertex *v = tess->cache;
399 tess->mesh = __gl_meshNewMesh();
400 if (tess->mesh == NULL) return 0;
402 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
403 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
405 tess->cacheCount = 0;
406 tess->emptyCache = FALSE;
413 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
415 int i, tooLarge = FALSE;
416 GLdouble x, clamped[3];
418 RequireState( tess, T_IN_CONTOUR );
420 if( tess->emptyCache ) {
421 if ( !EmptyCache( tess ) ) {
422 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
425 tess->lastEdge = NULL;
427 for( i = 0; i < 3; ++i ) {
429 if( x < - GLU_TESS_MAX_COORD ) {
430 x = - GLU_TESS_MAX_COORD;
433 if( x > GLU_TESS_MAX_COORD ) {
434 x = GLU_TESS_MAX_COORD;
440 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
443 if( tess->mesh == NULL ) {
444 if( tess->cacheCount < TESS_MAX_CACHE ) {
445 CacheVertex( tess, clamped, data );
448 if ( !EmptyCache( tess ) ) {
449 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
453 if ( !AddVertex( tess, clamped, data ) ) {
454 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
460 gluTessBeginPolygon( GLUtesselator *tess, void *data )
462 RequireState( tess, T_DORMANT );
464 tess->state = T_IN_POLYGON;
465 tess->cacheCount = 0;
466 tess->emptyCache = FALSE;
469 tess->polygonData= data;
474 gluTessBeginContour( GLUtesselator *tess )
476 RequireState( tess, T_IN_POLYGON );
478 tess->state = T_IN_CONTOUR;
479 tess->lastEdge = NULL;
480 if( tess->cacheCount > 0 ) {
481 /* Just set a flag so we don't get confused by empty contours
482 * -- these can be generated accidentally with the obsolete
483 * NextContour() interface.
485 tess->emptyCache = TRUE;
491 gluTessEndContour( GLUtesselator *tess )
493 RequireState( tess, T_IN_CONTOUR );
494 tess->state = T_IN_POLYGON;
498 gluTessEndPolygon( GLUtesselator *tess )
502 /* No idea why, but setjmp() has suddenly started to crash...
503 if (setjmp(tess->env) != 0) {
504 // come back here if out of memory
505 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
510 RequireState( tess, T_IN_POLYGON );
511 tess->state = T_DORMANT;
513 if( tess->mesh == NULL ) {
514 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
516 /* Try some special code to make the easy cases go quickly
517 * (eg. convex polygons). This code does NOT handle multiple contours,
518 * intersections, edge flags, and of course it does not generate
519 * an explicit mesh either.
521 if( __gl_renderCache( tess )) {
522 tess->polygonData= NULL;
526 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
529 /* Determine the polygon normal and project vertices onto the plane
532 __gl_projectPolygon( tess );
534 /* __gl_computeInterior( tess ) computes the planar arrangement specified
535 * by the given contours, and further subdivides this arrangement
536 * into regions. Each region is marked "inside" if it belongs
537 * to the polygon, according to the rule given by tess->windingRule.
538 * Each interior region is guaranteed be monotone.
540 if ( !__gl_computeInterior( tess ) ) {
541 longjmp(tess->env,1); /* could've used a label */
545 if( ! tess->fatalError ) {
548 /* If the user wants only the boundary contours, we throw away all edges
549 * except those which separate the interior from the exterior.
550 * Otherwise we tessellate all the regions marked "inside".
552 if( tess->boundaryOnly ) {
553 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
555 rc = __gl_meshTessellateInterior( mesh );
557 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
559 __gl_meshCheckMesh( mesh );
561 if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
562 || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
563 || tess->callBeginData != &__gl_noBeginData
564 || tess->callEndData != &__gl_noEndData
565 || tess->callVertexData != &__gl_noVertexData
566 || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
568 if( tess->boundaryOnly ) {
569 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
571 __gl_renderMesh( tess, mesh ); /* output strips and fans */
574 if( tess->callMesh != &noMesh ) {
576 /* Throw away the exterior faces, so that all faces are interior.
577 * This way the user doesn't have to check the "inside" flag,
578 * and we don't need to even reveal its existence. It also leaves
579 * the freedom for an implementation to not generate the exterior
580 * faces in the first place.
582 __gl_meshDiscardExterior( mesh );
583 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
585 tess->polygonData= NULL;
589 __gl_meshDeleteMesh( mesh );
590 tess->polygonData= NULL;
595 /*XXXblythe unused function*/
598 gluDeleteMesh( GLUmesh *mesh )
600 __gl_meshDeleteMesh( mesh );
606 /*******************************************************/
608 /* Obsolete calls -- for backward compatibility */
611 gluBeginPolygon( GLUtesselator *tess )
613 gluTessBeginPolygon( tess, NULL );
614 gluTessBeginContour( tess );
620 gluNextContour( GLUtesselator *tess, GLenum type )
622 gluTessEndContour( tess );
623 gluTessBeginContour( tess );
628 gluEndPolygon( GLUtesselator *tess )
630 gluTessEndContour( tess );
631 gluTessEndPolygon( tess );