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.
38 ** $Date: 2001/09/20 21:47:52 $ $Revision: 1.2 $
39 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/tess.c,v 1.2 2001/09/20 21:47:52 kschultz Exp $
54 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
55 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
60 /*ARGSUSED*/ static void GLAPIENTRY
noBegin( GLenum type
) {}
61 /*ARGSUSED*/ static void GLAPIENTRY
noEdgeFlag( GLboolean boundaryEdge
) {}
62 /*ARGSUSED*/ static void GLAPIENTRY
noVertex( void *data
) {}
63 /*ARGSUSED*/ static void GLAPIENTRY
noEnd( void ) {}
64 /*ARGSUSED*/ static void GLAPIENTRY
noError( GLenum errnum
) {}
65 /*ARGSUSED*/ static void GLAPIENTRY
noCombine( GLdouble coords
[3], void *data
[4],
66 GLfloat weight
[4], void **dataOut
) {}
67 /*ARGSUSED*/ static void GLAPIENTRY
noMesh( GLUmesh
*mesh
) {}
70 /*ARGSUSED*/ void GLAPIENTRY
__gl_noBeginData( GLenum type
,
71 void *polygonData
) {}
72 /*ARGSUSED*/ void GLAPIENTRY
__gl_noEdgeFlagData( GLboolean boundaryEdge
,
73 void *polygonData
) {}
74 /*ARGSUSED*/ void GLAPIENTRY
__gl_noVertexData( void *data
,
75 void *polygonData
) {}
76 /*ARGSUSED*/ void GLAPIENTRY
__gl_noEndData( void *polygonData
) {}
77 /*ARGSUSED*/ void GLAPIENTRY
__gl_noErrorData( GLenum errnum
,
78 void *polygonData
) {}
79 /*ARGSUSED*/ void GLAPIENTRY
__gl_noCombineData( GLdouble coords
[3],
83 void *polygonData
) {}
85 /* Half-edges are allocated in pairs (see mesh.c) */
86 typedef struct { GLUhalfEdge e
, eSym
; } EdgePair
;
88 #define MAX(a,b) ((a) > (b) ? (a) : (b))
89 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
90 MAX(sizeof(GLUvertex),sizeof(GLUface))))
93 GLUtesselator
* GLAPIENTRY
98 /* Only initialize fields which can be changed by the api. Other fields
99 * are initialized where they are used.
102 if (memInit( MAX_FAST_ALLOC
) == 0) {
103 return 0; /* out of memory */
105 tess
= (GLUtesselator
*)memAlloc( sizeof( GLUtesselator
));
107 return 0; /* out of memory */
110 tess
->state
= T_DORMANT
;
116 tess
->relTolerance
= GLU_TESS_DEFAULT_TOLERANCE
;
117 tess
->windingRule
= GLU_TESS_WINDING_ODD
;
118 tess
->flagBoundary
= FALSE
;
119 tess
->boundaryOnly
= FALSE
;
121 tess
->callBegin
= &noBegin
;
122 tess
->callEdgeFlag
= &noEdgeFlag
;
123 tess
->callVertex
= &noVertex
;
124 tess
->callEnd
= &noEnd
;
126 tess
->callError
= &noError
;
127 tess
->callCombine
= &noCombine
;
128 tess
->callMesh
= &noMesh
;
130 tess
->callBeginData
= &__gl_noBeginData
;
131 tess
->callEdgeFlagData
= &__gl_noEdgeFlagData
;
132 tess
->callVertexData
= &__gl_noVertexData
;
133 tess
->callEndData
= &__gl_noEndData
;
134 tess
->callErrorData
= &__gl_noErrorData
;
135 tess
->callCombineData
= &__gl_noCombineData
;
137 tess
->polygonData
= NULL
;
142 static void MakeDormant( GLUtesselator
*tess
)
144 /* Return the tessellator to its original dormant state. */
146 if( tess
->mesh
!= NULL
) {
147 __gl_meshDeleteMesh( tess
->mesh
);
149 tess
->state
= T_DORMANT
;
150 tess
->lastEdge
= NULL
;
154 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
156 static void GotoState( GLUtesselator
*tess
, enum TessState newState
)
158 while( tess
->state
!= newState
) {
159 /* We change the current state one level at a time, to get to
162 if( tess
->state
< newState
) {
163 switch( tess
->state
) {
165 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON
);
166 gluTessBeginPolygon( tess
, NULL
);
169 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR
);
170 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! */
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 if (setjmp(tess
->env
) != 0) {
503 /* come back here if out of memory */
504 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY
);
508 RequireState( tess
, T_IN_POLYGON
);
509 tess
->state
= T_DORMANT
;
511 if( tess
->mesh
== NULL
) {
512 if( ! tess
->flagBoundary
&& tess
->callMesh
== &noMesh
) {
514 /* Try some special code to make the easy cases go quickly
515 * (eg. convex polygons). This code does NOT handle multiple contours,
516 * intersections, edge flags, and of course it does not generate
517 * an explicit mesh either.
519 if( __gl_renderCache( tess
)) {
520 tess
->polygonData
= NULL
;
524 if ( !EmptyCache( tess
) ) longjmp(tess
->env
,1); /* could've used a label*/
527 /* Determine the polygon normal and project vertices onto the plane
530 __gl_projectPolygon( tess
);
532 /* __gl_computeInterior( tess ) computes the planar arrangement specified
533 * by the given contours, and further subdivides this arrangement
534 * into regions. Each region is marked "inside" if it belongs
535 * to the polygon, according to the rule given by tess->windingRule.
536 * Each interior region is guaranteed be monotone.
538 if ( !__gl_computeInterior( tess
) ) {
539 longjmp(tess
->env
,1); /* could've used a label */
543 if( ! tess
->fatalError
) {
546 /* If the user wants only the boundary contours, we throw away all edges
547 * except those which separate the interior from the exterior.
548 * Otherwise we tessellate all the regions marked "inside".
550 if( tess
->boundaryOnly
) {
551 rc
= __gl_meshSetWindingNumber( mesh
, 1, TRUE
);
553 rc
= __gl_meshTessellateInterior( mesh
);
555 if (rc
== 0) longjmp(tess
->env
,1); /* could've used a label */
557 __gl_meshCheckMesh( mesh
);
559 if( tess
->callBegin
!= &noBegin
|| tess
->callEnd
!= &noEnd
560 || tess
->callVertex
!= &noVertex
|| tess
->callEdgeFlag
!= &noEdgeFlag
561 || tess
->callBeginData
!= &__gl_noBeginData
562 || tess
->callEndData
!= &__gl_noEndData
563 || tess
->callVertexData
!= &__gl_noVertexData
564 || tess
->callEdgeFlagData
!= &__gl_noEdgeFlagData
)
566 if( tess
->boundaryOnly
) {
567 __gl_renderBoundary( tess
, mesh
); /* output boundary contours */
569 __gl_renderMesh( tess
, mesh
); /* output strips and fans */
572 if( tess
->callMesh
!= &noMesh
) {
574 /* Throw away the exterior faces, so that all faces are interior.
575 * This way the user doesn't have to check the "inside" flag,
576 * and we don't need to even reveal its existence. It also leaves
577 * the freedom for an implementation to not generate the exterior
578 * faces in the first place.
580 __gl_meshDiscardExterior( mesh
);
581 (*tess
->callMesh
)( mesh
); /* user wants the mesh itself */
583 tess
->polygonData
= NULL
;
587 __gl_meshDeleteMesh( mesh
);
588 tess
->polygonData
= NULL
;
593 /*XXXblythe unused function*/
596 gluDeleteMesh( GLUmesh
*mesh
)
598 __gl_meshDeleteMesh( mesh
);
604 /*******************************************************/
606 /* Obsolete calls -- for backward compatibility */
609 gluBeginPolygon( GLUtesselator
*tess
)
611 gluTessBeginPolygon( tess
, NULL
);
612 gluTessBeginContour( tess
);
618 gluNextContour( GLUtesselator
*tess
, GLenum type
)
620 gluTessEndContour( tess
);
621 gluTessBeginContour( tess
);
626 gluEndPolygon( GLUtesselator
*tess
)
628 gluTessEndContour( tess
);
629 gluTessEndPolygon( tess
);