2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
31 ** Author: Eric Veach, July 1994.
47 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
48 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
57 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
58 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
59 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
61 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
62 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
63 GLfloat weight[4], void **dataOut ) {}
64 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
67 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
68 void *polygonData ) {}
69 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
70 void *polygonData ) {}
71 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
72 void *polygonData ) {}
73 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
74 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
75 void *polygonData ) {}
76 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
80 void *polygonData ) {}
82 /* Half-edges are allocated in pairs (see mesh.c) */
83 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
86 #define MAX(a,b) ((a) > (b) ? (a) : (b))
87 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
88 MAX(sizeof(GLUvertex),sizeof(GLUface))))
91 GLUtesselator * GLAPIENTRY
96 /* Only initialize fields which can be changed by the api. Other fields
97 * are initialized where they are used.
100 if (memInit( MAX_FAST_ALLOC ) == 0) {
101 return 0; /* out of memory */
103 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
105 return 0; /* out of memory */
108 tess->state = T_DORMANT;
114 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
115 tess->windingRule = GLU_TESS_WINDING_ODD;
116 tess->flagBoundary = FALSE;
117 tess->boundaryOnly = FALSE;
119 tess->callBegin = &noBegin;
120 tess->callEdgeFlag = &noEdgeFlag;
121 tess->callVertex = &noVertex;
122 tess->callEnd = &noEnd;
124 tess->callError = &noError;
125 tess->callCombine = &noCombine;
126 tess->callMesh = &noMesh;
128 tess->callBeginData= &__gl_noBeginData;
129 tess->callEdgeFlagData= &__gl_noEdgeFlagData;
130 tess->callVertexData= &__gl_noVertexData;
131 tess->callEndData= &__gl_noEndData;
132 tess->callErrorData= &__gl_noErrorData;
133 tess->callCombineData= &__gl_noCombineData;
135 tess->polygonData= NULL;
140 static void MakeDormant( GLUtesselator *tess )
142 /* Return the tessellator to its original dormant state. */
144 if( tess->mesh != NULL ) {
145 __gl_meshDeleteMesh( tess->mesh );
147 tess->state = T_DORMANT;
148 tess->lastEdge = NULL;
152 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
154 static void GotoState( GLUtesselator *tess, enum TessState newState )
156 while( tess->state != newState ) {
157 /* We change the current state one level at a time, to get to
160 if( tess->state < newState ) {
161 switch( tess->state ) {
163 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
164 gluTessBeginPolygon( tess, NULL );
167 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
168 gluTessBeginContour( tess );
174 switch( tess->state ) {
176 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
177 gluTessEndContour( tess );
180 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
181 /* gluTessEndPolygon( tess ) is too much work! */
193 gluDeleteTess( GLUtesselator *tess )
195 RequireState( tess, T_DORMANT );
201 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
206 case GLU_TESS_TOLERANCE:
207 if( value < 0.0 || value > 1.0 ) break;
208 tess->relTolerance = value;
211 case GLU_TESS_WINDING_RULE:
212 windingRule = (GLenum) value;
213 if( windingRule != value ) break; /* not an integer */
215 switch( windingRule ) {
216 case GLU_TESS_WINDING_ODD:
217 case GLU_TESS_WINDING_NONZERO:
218 case GLU_TESS_WINDING_POSITIVE:
219 case GLU_TESS_WINDING_NEGATIVE:
220 case GLU_TESS_WINDING_ABS_GEQ_TWO:
221 tess->windingRule = windingRule;
227 case GLU_TESS_BOUNDARY_ONLY:
228 tess->boundaryOnly = (value != 0);
232 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
235 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
238 /* Returns tessellator property */
240 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
243 case GLU_TESS_TOLERANCE:
244 /* tolerance should be in range [0..1] */
245 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
246 *value= tess->relTolerance;
248 case GLU_TESS_WINDING_RULE:
249 assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
250 tess->windingRule == GLU_TESS_WINDING_NONZERO ||
251 tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
252 tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
253 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
254 *value= tess->windingRule;
256 case GLU_TESS_BOUNDARY_ONLY:
257 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
258 *value= tess->boundaryOnly;
262 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
265 } /* gluGetTessProperty() */
268 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
276 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
280 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
282 case GLU_TESS_BEGIN_DATA:
283 tess->callBeginData = (fn == NULL) ?
284 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
286 case GLU_TESS_EDGE_FLAG:
287 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
288 (void (GLAPIENTRY *)(GLboolean)) fn;
289 /* If the client wants boundary edges to be flagged,
290 * we render everything as separate triangles (no strips or fans).
292 tess->flagBoundary = (fn != NULL);
294 case GLU_TESS_EDGE_FLAG_DATA:
295 tess->callEdgeFlagData= (fn == NULL) ?
296 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
297 /* If the client wants boundary edges to be flagged,
298 * we render everything as separate triangles (no strips or fans).
300 tess->flagBoundary = (fn != NULL);
302 case GLU_TESS_VERTEX:
303 tess->callVertex = (fn == NULL) ? &noVertex :
304 (void (GLAPIENTRY *)(void *)) fn;
306 case GLU_TESS_VERTEX_DATA:
307 tess->callVertexData = (fn == NULL) ?
308 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
311 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
313 case GLU_TESS_END_DATA:
314 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
315 (void (GLAPIENTRY *)(void *)) fn;
318 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
320 case GLU_TESS_ERROR_DATA:
321 tess->callErrorData = (fn == NULL) ?
322 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
324 case GLU_TESS_COMBINE:
325 tess->callCombine = (fn == NULL) ? &noCombine :
326 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
328 case GLU_TESS_COMBINE_DATA:
329 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
330 (void (GLAPIENTRY *)(GLdouble [3],
337 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
340 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
345 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
351 /* Make a self-loop (one vertex, one edge). */
353 e = __gl_meshMakeEdge( tess->mesh );
354 if (e == NULL) return 0;
355 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
357 /* Create a new vertex and edge which immediately follow e
358 * in the ordering around the left face.
360 if (__gl_meshSplitEdge( e ) == NULL) return 0;
364 /* The new vertex is now e->Org. */
366 e->Org->coords[0] = coords[0];
367 e->Org->coords[1] = coords[1];
368 e->Org->coords[2] = coords[2];
370 /* The winding of an edge says how the winding number changes as we
371 * cross from the edge''s right face to its left face. We add the
372 * vertices in such an order that a CCW contour will add +1 to
373 * the winding number of the region inside the contour.
376 e->Sym->winding = -1;
384 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
386 CachedVertex *v = &tess->cache[tess->cacheCount];
389 v->coords[0] = coords[0];
390 v->coords[1] = coords[1];
391 v->coords[2] = coords[2];
396 static int EmptyCache( GLUtesselator *tess )
398 CachedVertex *v = tess->cache;
401 tess->mesh = __gl_meshNewMesh();
402 if (tess->mesh == NULL) return 0;
404 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
405 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
407 tess->cacheCount = 0;
408 tess->emptyCache = FALSE;
415 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
417 int i, tooLarge = FALSE;
418 GLdouble x, clamped[3];
420 RequireState( tess, T_IN_CONTOUR );
422 if( tess->emptyCache ) {
423 if ( !EmptyCache( tess ) ) {
424 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
427 tess->lastEdge = NULL;
429 for( i = 0; i < 3; ++i ) {
431 if( x < - GLU_TESS_MAX_COORD ) {
432 x = - GLU_TESS_MAX_COORD;
435 if( x > GLU_TESS_MAX_COORD ) {
436 x = GLU_TESS_MAX_COORD;
442 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
445 if( tess->mesh == NULL ) {
446 if( tess->cacheCount < TESS_MAX_CACHE ) {
447 CacheVertex( tess, clamped, data );
450 if ( !EmptyCache( tess ) ) {
451 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
455 if ( !AddVertex( tess, clamped, data ) ) {
456 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
462 gluTessBeginPolygon( GLUtesselator *tess, void *data )
464 RequireState( tess, T_DORMANT );
466 tess->state = T_IN_POLYGON;
467 tess->cacheCount = 0;
468 tess->emptyCache = FALSE;
471 tess->polygonData= data;
476 gluTessBeginContour( GLUtesselator *tess )
478 RequireState( tess, T_IN_POLYGON );
480 tess->state = T_IN_CONTOUR;
481 tess->lastEdge = NULL;
482 if( tess->cacheCount > 0 ) {
483 /* Just set a flag so we don't get confused by empty contours
484 * -- these can be generated accidentally with the obsolete
485 * NextContour() interface.
487 tess->emptyCache = TRUE;
493 gluTessEndContour( GLUtesselator *tess )
495 RequireState( tess, T_IN_CONTOUR );
496 tess->state = T_IN_POLYGON;
500 gluTessEndPolygon( GLUtesselator *tess )
504 if (setjmp(tess->env) != 0) {
505 /* come back here if out of memory */
506 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 );