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
);