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) */
53 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
54 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
55 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
56 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
57 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
58 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
59 GLfloat weight[4], void **dataOut ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
63 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
64 void *polygonData ) {}
65 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
66 void *polygonData ) {}
67 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
68 void *polygonData ) {}
69 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
70 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
71 void *polygonData ) {}
72 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
76 void *polygonData ) {}
78 /* Half-edges are allocated in pairs (see mesh.c) */
79 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
82 #define MAX(a,b) ((a) > (b) ? (a) : (b))
83 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
84 MAX(sizeof(GLUvertex),sizeof(GLUface))))
87 GLUtesselator * GLAPIENTRY
92 /* Only initialize fields which can be changed by the api. Other fields
93 * are initialized where they are used.
96 if (memInit( MAX_FAST_ALLOC ) == 0) {
97 return 0; /* out of memory */
99 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
101 return 0; /* out of memory */
104 tess->state = T_DORMANT;
110 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
111 tess->windingRule = GLU_TESS_WINDING_ODD;
112 tess->flagBoundary = FALSE;
113 tess->boundaryOnly = FALSE;
115 tess->callBegin = &noBegin;
116 tess->callEdgeFlag = &noEdgeFlag;
117 tess->callVertex = &noVertex;
118 tess->callEnd = &noEnd;
120 tess->callError = &noError;
121 tess->callCombine = &noCombine;
122 tess->callMesh = &noMesh;
124 tess->callBeginData= &__gl_noBeginData;
125 tess->callEdgeFlagData= &__gl_noEdgeFlagData;
126 tess->callVertexData= &__gl_noVertexData;
127 tess->callEndData= &__gl_noEndData;
128 tess->callErrorData= &__gl_noErrorData;
129 tess->callCombineData= &__gl_noCombineData;
131 tess->polygonData= NULL;
136 static void MakeDormant( GLUtesselator *tess )
138 /* Return the tessellator to its original dormant state. */
140 if( tess->mesh != NULL ) {
141 __gl_meshDeleteMesh( tess->mesh );
143 tess->state = T_DORMANT;
144 tess->lastEdge = NULL;
148 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
150 static void GotoState( GLUtesselator *tess, enum TessState newState )
152 while( tess->state != newState ) {
153 /* We change the current state one level at a time, to get to
156 if( tess->state < newState ) {
157 switch( tess->state ) {
159 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
160 gluTessBeginPolygon( tess, NULL );
163 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
164 gluTessBeginContour( tess );
170 switch( tess->state ) {
172 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
173 gluTessEndContour( tess );
176 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
177 /* gluTessEndPolygon( tess ) is too much work! */
189 gluDeleteTess( GLUtesselator *tess )
191 RequireState( tess, T_DORMANT );
197 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
202 case GLU_TESS_TOLERANCE:
203 if( value < 0.0 || value > 1.0 ) break;
204 tess->relTolerance = value;
207 case GLU_TESS_WINDING_RULE:
208 windingRule = (GLenum) value;
209 if( windingRule != value ) break; /* not an integer */
211 switch( windingRule ) {
212 case GLU_TESS_WINDING_ODD:
213 case GLU_TESS_WINDING_NONZERO:
214 case GLU_TESS_WINDING_POSITIVE:
215 case GLU_TESS_WINDING_NEGATIVE:
216 case GLU_TESS_WINDING_ABS_GEQ_TWO:
217 tess->windingRule = windingRule;
223 case GLU_TESS_BOUNDARY_ONLY:
224 tess->boundaryOnly = (value != 0);
228 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
231 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
234 /* Returns tessellator property */
236 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
239 case GLU_TESS_TOLERANCE:
240 /* tolerance should be in range [0..1] */
241 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
242 *value= tess->relTolerance;
244 case GLU_TESS_WINDING_RULE:
245 assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
246 tess->windingRule == GLU_TESS_WINDING_NONZERO ||
247 tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
248 tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
249 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
250 *value= tess->windingRule;
252 case GLU_TESS_BOUNDARY_ONLY:
253 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
254 *value= tess->boundaryOnly;
258 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
261 } /* gluGetTessProperty() */
264 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
272 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
276 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
278 case GLU_TESS_BEGIN_DATA:
279 tess->callBeginData = (fn == NULL) ?
280 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
282 case GLU_TESS_EDGE_FLAG:
283 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
284 (void (GLAPIENTRY *)(GLboolean)) fn;
285 /* If the client wants boundary edges to be flagged,
286 * we render everything as separate triangles (no strips or fans).
288 tess->flagBoundary = (fn != NULL);
290 case GLU_TESS_EDGE_FLAG_DATA:
291 tess->callEdgeFlagData= (fn == NULL) ?
292 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
293 /* If the client wants boundary edges to be flagged,
294 * we render everything as separate triangles (no strips or fans).
296 tess->flagBoundary = (fn != NULL);
298 case GLU_TESS_VERTEX:
299 tess->callVertex = (fn == NULL) ? &noVertex :
300 (void (GLAPIENTRY *)(void *)) fn;
302 case GLU_TESS_VERTEX_DATA:
303 tess->callVertexData = (fn == NULL) ?
304 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
307 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
309 case GLU_TESS_END_DATA:
310 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
311 (void (GLAPIENTRY *)(void *)) fn;
314 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
316 case GLU_TESS_ERROR_DATA:
317 tess->callErrorData = (fn == NULL) ?
318 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
320 case GLU_TESS_COMBINE:
321 tess->callCombine = (fn == NULL) ? &noCombine :
322 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
324 case GLU_TESS_COMBINE_DATA:
325 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
326 (void (GLAPIENTRY *)(GLdouble [3],
333 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
336 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
341 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
347 /* Make a self-loop (one vertex, one edge). */
349 e = __gl_meshMakeEdge( tess->mesh );
350 if (e == NULL) return 0;
351 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
353 /* Create a new vertex and edge which immediately follow e
354 * in the ordering around the left face.
356 if (__gl_meshSplitEdge( e ) == NULL) return 0;
360 /* The new vertex is now e->Org. */
362 e->Org->coords[0] = coords[0];
363 e->Org->coords[1] = coords[1];
364 e->Org->coords[2] = coords[2];
366 /* The winding of an edge says how the winding number changes as we
367 * cross from the edge''s right face to its left face. We add the
368 * vertices in such an order that a CCW contour will add +1 to
369 * the winding number of the region inside the contour.
372 e->Sym->winding = -1;
380 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
382 CachedVertex *v = &tess->cache[tess->cacheCount];
385 v->coords[0] = coords[0];
386 v->coords[1] = coords[1];
387 v->coords[2] = coords[2];
392 static int EmptyCache( GLUtesselator *tess )
394 CachedVertex *v = tess->cache;
397 tess->mesh = __gl_meshNewMesh();
398 if (tess->mesh == NULL) return 0;
400 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
401 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
403 tess->cacheCount = 0;
404 tess->emptyCache = FALSE;
411 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
413 int i, tooLarge = FALSE;
414 GLdouble x, clamped[3];
416 RequireState( tess, T_IN_CONTOUR );
418 if( tess->emptyCache ) {
419 if ( !EmptyCache( tess ) ) {
420 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
423 tess->lastEdge = NULL;
425 for( i = 0; i < 3; ++i ) {
427 if( x < - GLU_TESS_MAX_COORD ) {
428 x = - GLU_TESS_MAX_COORD;
431 if( x > GLU_TESS_MAX_COORD ) {
432 x = GLU_TESS_MAX_COORD;
438 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
441 if( tess->mesh == NULL ) {
442 if( tess->cacheCount < TESS_MAX_CACHE ) {
443 CacheVertex( tess, clamped, data );
446 if ( !EmptyCache( tess ) ) {
447 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
451 if ( !AddVertex( tess, clamped, data ) ) {
452 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
458 gluTessBeginPolygon( GLUtesselator *tess, void *data )
460 RequireState( tess, T_DORMANT );
462 tess->state = T_IN_POLYGON;
463 tess->cacheCount = 0;
464 tess->emptyCache = FALSE;
467 tess->polygonData= data;
472 gluTessBeginContour( GLUtesselator *tess )
474 RequireState( tess, T_IN_POLYGON );
476 tess->state = T_IN_CONTOUR;
477 tess->lastEdge = NULL;
478 if( tess->cacheCount > 0 ) {
479 /* Just set a flag so we don't get confused by empty contours
480 * -- these can be generated accidentally with the obsolete
481 * NextContour() interface.
483 tess->emptyCache = TRUE;
489 gluTessEndContour( GLUtesselator *tess )
491 RequireState( tess, T_IN_CONTOUR );
492 tess->state = T_IN_POLYGON;
496 gluTessEndPolygon( GLUtesselator *tess )
500 if (setjmp(tess->env) != 0) {
501 /* come back here if out of memory */
502 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
506 RequireState( tess, T_IN_POLYGON );
507 tess->state = T_DORMANT;
509 if( tess->mesh == NULL ) {
510 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
512 /* Try some special code to make the easy cases go quickly
513 * (eg. convex polygons). This code does NOT handle multiple contours,
514 * intersections, edge flags, and of course it does not generate
515 * an explicit mesh either.
517 if( __gl_renderCache( tess )) {
518 tess->polygonData= NULL;
522 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
525 /* Determine the polygon normal and project vertices onto the plane
528 __gl_projectPolygon( tess );
530 /* __gl_computeInterior( tess ) computes the planar arrangement specified
531 * by the given contours, and further subdivides this arrangement
532 * into regions. Each region is marked "inside" if it belongs
533 * to the polygon, according to the rule given by tess->windingRule.
534 * Each interior region is guaranteed be monotone.
536 if ( !__gl_computeInterior( tess ) ) {
537 longjmp(tess->env,1); /* could've used a label */
541 if( ! tess->fatalError ) {
544 /* If the user wants only the boundary contours, we throw away all edges
545 * except those which separate the interior from the exterior.
546 * Otherwise we tessellate all the regions marked "inside".
548 if( tess->boundaryOnly ) {
549 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
551 rc = __gl_meshTessellateInterior( mesh );
553 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
555 __gl_meshCheckMesh( mesh );
557 if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
558 || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
559 || tess->callBeginData != &__gl_noBeginData
560 || tess->callEndData != &__gl_noEndData
561 || tess->callVertexData != &__gl_noVertexData
562 || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
564 if( tess->boundaryOnly ) {
565 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
567 __gl_renderMesh( tess, mesh ); /* output strips and fans */
570 if( tess->callMesh != &noMesh ) {
572 /* Throw away the exterior faces, so that all faces are interior.
573 * This way the user doesn't have to check the "inside" flag,
574 * and we don't need to even reveal its existence. It also leaves
575 * the freedom for an implementation to not generate the exterior
576 * faces in the first place.
578 __gl_meshDiscardExterior( mesh );
579 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
581 tess->polygonData= NULL;
585 __gl_meshDeleteMesh( mesh );
586 tess->polygonData= NULL;
591 /*XXXblythe unused function*/
594 gluDeleteMesh( GLUmesh *mesh )
596 __gl_meshDeleteMesh( mesh );
602 /*******************************************************/
604 /* Obsolete calls -- for backward compatibility */
607 gluBeginPolygon( GLUtesselator *tess )
609 gluTessBeginPolygon( tess, NULL );
610 gluTessBeginContour( tess );
616 gluNextContour( GLUtesselator *tess, GLenum type )
618 gluTessEndContour( tess );
619 gluTessBeginContour( tess );
624 gluEndPolygon( GLUtesselator *tess )
626 gluTessEndContour( tess );
627 gluTessEndPolygon( tess );