silence a bunch of warnings
[mesa.git] / src / glu / sgi / libtess / tess.c
1 /*
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:
9 **
10 ** http://oss.sgi.com/projects/FreeB
11 **
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.
17 **
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.
23 **
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.
33 **
34 */
35 /*
36 ** Author: Eric Veach, July 1994.
37 **
38 ** $Date: 2002/11/01 23:45:31 $ $Revision: 1.3 $
39 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/tess.c,v 1.3 2002/11/01 23:45:31 brianp Exp $
40 */
41
42 #include "gluos.h"
43 #include <stddef.h>
44 #include <assert.h>
45 #include <setjmp.h>
46 #include "memalloc.h"
47 #include "tess.h"
48 #include "mesh.h"
49 #include "normal.h"
50 #include "sweep.h"
51 #include "tessmono.h"
52 #include "render.h"
53
54 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
55 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
56
57 #define TRUE 1
58 #define FALSE 0
59
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 ) {}
68
69
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],
80 void *data[4],
81 GLfloat weight[4],
82 void **outData,
83 void *polygonData ) {}
84
85 /* Half-edges are allocated in pairs (see mesh.c) */
86 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
87
88 #define MAX(a,b) ((a) > (b) ? (a) : (b))
89 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
90 MAX(sizeof(GLUvertex),sizeof(GLUface))))
91
92
93 GLUtesselator * GLAPIENTRY
94 gluNewTess( void )
95 {
96 GLUtesselator *tess;
97
98 /* Only initialize fields which can be changed by the api. Other fields
99 * are initialized where they are used.
100 */
101
102 if (memInit( MAX_FAST_ALLOC ) == 0) {
103 return 0; /* out of memory */
104 }
105 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
106 if (tess == NULL) {
107 return 0; /* out of memory */
108 }
109
110 tess->state = T_DORMANT;
111
112 tess->normal[0] = 0;
113 tess->normal[1] = 0;
114 tess->normal[2] = 0;
115
116 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
117 tess->windingRule = GLU_TESS_WINDING_ODD;
118 tess->flagBoundary = FALSE;
119 tess->boundaryOnly = FALSE;
120
121 tess->callBegin = &noBegin;
122 tess->callEdgeFlag = &noEdgeFlag;
123 tess->callVertex = &noVertex;
124 tess->callEnd = &noEnd;
125
126 tess->callError = &noError;
127 tess->callCombine = &noCombine;
128 tess->callMesh = &noMesh;
129
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;
136
137 tess->polygonData= NULL;
138
139 return tess;
140 }
141
142 static void MakeDormant( GLUtesselator *tess )
143 {
144 /* Return the tessellator to its original dormant state. */
145
146 if( tess->mesh != NULL ) {
147 __gl_meshDeleteMesh( tess->mesh );
148 }
149 tess->state = T_DORMANT;
150 tess->lastEdge = NULL;
151 tess->mesh = NULL;
152 }
153
154 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
155
156 static void GotoState( GLUtesselator *tess, enum TessState newState )
157 {
158 while( tess->state != newState ) {
159 /* We change the current state one level at a time, to get to
160 * the desired state.
161 */
162 if( tess->state < newState ) {
163 switch( tess->state ) {
164 case T_DORMANT:
165 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
166 gluTessBeginPolygon( tess, NULL );
167 break;
168 case T_IN_POLYGON:
169 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
170 gluTessBeginContour( tess );
171 break;
172 default:
173 ;
174 }
175 } else {
176 switch( tess->state ) {
177 case T_IN_CONTOUR:
178 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
179 gluTessEndContour( tess );
180 break;
181 case T_IN_POLYGON:
182 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
183 /* gluTessEndPolygon( tess ) is too much work! */
184 MakeDormant( tess );
185 break;
186 default:
187 ;
188 }
189 }
190 }
191 }
192
193
194 void GLAPIENTRY
195 gluDeleteTess( GLUtesselator *tess )
196 {
197 RequireState( tess, T_DORMANT );
198 memFree( tess );
199 }
200
201
202 void GLAPIENTRY
203 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
204 {
205 GLenum windingRule;
206
207 switch( which ) {
208 case GLU_TESS_TOLERANCE:
209 if( value < 0.0 || value > 1.0 ) break;
210 tess->relTolerance = value;
211 return;
212
213 case GLU_TESS_WINDING_RULE:
214 windingRule = (GLenum) value;
215 if( windingRule != value ) break; /* not an integer */
216
217 switch( windingRule ) {
218 case GLU_TESS_WINDING_ODD:
219 case GLU_TESS_WINDING_NONZERO:
220 case GLU_TESS_WINDING_POSITIVE:
221 case GLU_TESS_WINDING_NEGATIVE:
222 case GLU_TESS_WINDING_ABS_GEQ_TWO:
223 tess->windingRule = windingRule;
224 return;
225 default:
226 break;
227 }
228
229 case GLU_TESS_BOUNDARY_ONLY:
230 tess->boundaryOnly = (value != 0);
231 return;
232
233 default:
234 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
235 return;
236 }
237 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
238 }
239
240 /* Returns tessellator property */
241 void GLAPIENTRY
242 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
243 {
244 switch (which) {
245 case GLU_TESS_TOLERANCE:
246 /* tolerance should be in range [0..1] */
247 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
248 *value= tess->relTolerance;
249 break;
250 case GLU_TESS_WINDING_RULE:
251 assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
252 tess->windingRule == GLU_TESS_WINDING_NONZERO ||
253 tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
254 tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
255 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
256 *value= tess->windingRule;
257 break;
258 case GLU_TESS_BOUNDARY_ONLY:
259 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
260 *value= tess->boundaryOnly;
261 break;
262 default:
263 *value= 0.0;
264 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
265 break;
266 }
267 } /* gluGetTessProperty() */
268
269 void GLAPIENTRY
270 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
271 {
272 tess->normal[0] = x;
273 tess->normal[1] = y;
274 tess->normal[2] = z;
275 }
276
277 void GLAPIENTRY
278 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
279 {
280 switch( which ) {
281 case GLU_TESS_BEGIN:
282 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
283 return;
284 case GLU_TESS_BEGIN_DATA:
285 tess->callBeginData = (fn == NULL) ?
286 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
287 return;
288 case GLU_TESS_EDGE_FLAG:
289 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
290 (void (GLAPIENTRY *)(GLboolean)) fn;
291 /* If the client wants boundary edges to be flagged,
292 * we render everything as separate triangles (no strips or fans).
293 */
294 tess->flagBoundary = (fn != NULL);
295 return;
296 case GLU_TESS_EDGE_FLAG_DATA:
297 tess->callEdgeFlagData= (fn == NULL) ?
298 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
299 /* If the client wants boundary edges to be flagged,
300 * we render everything as separate triangles (no strips or fans).
301 */
302 tess->flagBoundary = (fn != NULL);
303 return;
304 case GLU_TESS_VERTEX:
305 tess->callVertex = (fn == NULL) ? &noVertex :
306 (void (GLAPIENTRY *)(void *)) fn;
307 return;
308 case GLU_TESS_VERTEX_DATA:
309 tess->callVertexData = (fn == NULL) ?
310 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
311 return;
312 case GLU_TESS_END:
313 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
314 return;
315 case GLU_TESS_END_DATA:
316 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
317 (void (GLAPIENTRY *)(void *)) fn;
318 return;
319 case GLU_TESS_ERROR:
320 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
321 return;
322 case GLU_TESS_ERROR_DATA:
323 tess->callErrorData = (fn == NULL) ?
324 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
325 return;
326 case GLU_TESS_COMBINE:
327 tess->callCombine = (fn == NULL) ? &noCombine :
328 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
329 return;
330 case GLU_TESS_COMBINE_DATA:
331 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
332 (void (GLAPIENTRY *)(GLdouble [3],
333 void *[4],
334 GLfloat [4],
335 void **,
336 void *)) fn;
337 return;
338 case GLU_TESS_MESH:
339 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
340 return;
341 default:
342 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
343 return;
344 }
345 }
346
347 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
348 {
349 GLUhalfEdge *e;
350
351 e = tess->lastEdge;
352 if( e == NULL ) {
353 /* Make a self-loop (one vertex, one edge). */
354
355 e = __gl_meshMakeEdge( tess->mesh );
356 if (e == NULL) return 0;
357 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
358 } else {
359 /* Create a new vertex and edge which immediately follow e
360 * in the ordering around the left face.
361 */
362 if (__gl_meshSplitEdge( e ) == NULL) return 0;
363 e = e->Lnext;
364 }
365
366 /* The new vertex is now e->Org. */
367 e->Org->data = data;
368 e->Org->coords[0] = coords[0];
369 e->Org->coords[1] = coords[1];
370 e->Org->coords[2] = coords[2];
371
372 /* The winding of an edge says how the winding number changes as we
373 * cross from the edge''s right face to its left face. We add the
374 * vertices in such an order that a CCW contour will add +1 to
375 * the winding number of the region inside the contour.
376 */
377 e->winding = 1;
378 e->Sym->winding = -1;
379
380 tess->lastEdge = e;
381
382 return 1;
383 }
384
385
386 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
387 {
388 CachedVertex *v = &tess->cache[tess->cacheCount];
389
390 v->data = data;
391 v->coords[0] = coords[0];
392 v->coords[1] = coords[1];
393 v->coords[2] = coords[2];
394 ++tess->cacheCount;
395 }
396
397
398 static int EmptyCache( GLUtesselator *tess )
399 {
400 CachedVertex *v = tess->cache;
401 CachedVertex *vLast;
402
403 tess->mesh = __gl_meshNewMesh();
404 if (tess->mesh == NULL) return 0;
405
406 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
407 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
408 }
409 tess->cacheCount = 0;
410 tess->emptyCache = FALSE;
411
412 return 1;
413 }
414
415
416 void GLAPIENTRY
417 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
418 {
419 int i, tooLarge = FALSE;
420 GLdouble x, clamped[3];
421
422 RequireState( tess, T_IN_CONTOUR );
423
424 if( tess->emptyCache ) {
425 if ( !EmptyCache( tess ) ) {
426 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
427 return;
428 }
429 tess->lastEdge = NULL;
430 }
431 for( i = 0; i < 3; ++i ) {
432 x = coords[i];
433 if( x < - GLU_TESS_MAX_COORD ) {
434 x = - GLU_TESS_MAX_COORD;
435 tooLarge = TRUE;
436 }
437 if( x > GLU_TESS_MAX_COORD ) {
438 x = GLU_TESS_MAX_COORD;
439 tooLarge = TRUE;
440 }
441 clamped[i] = x;
442 }
443 if( tooLarge ) {
444 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
445 }
446
447 if( tess->mesh == NULL ) {
448 if( tess->cacheCount < TESS_MAX_CACHE ) {
449 CacheVertex( tess, clamped, data );
450 return;
451 }
452 if ( !EmptyCache( tess ) ) {
453 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
454 return;
455 }
456 }
457 if ( !AddVertex( tess, clamped, data ) ) {
458 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
459 }
460 }
461
462
463 void GLAPIENTRY
464 gluTessBeginPolygon( GLUtesselator *tess, void *data )
465 {
466 RequireState( tess, T_DORMANT );
467
468 tess->state = T_IN_POLYGON;
469 tess->cacheCount = 0;
470 tess->emptyCache = FALSE;
471 tess->mesh = NULL;
472
473 tess->polygonData= data;
474 }
475
476
477 void GLAPIENTRY
478 gluTessBeginContour( GLUtesselator *tess )
479 {
480 RequireState( tess, T_IN_POLYGON );
481
482 tess->state = T_IN_CONTOUR;
483 tess->lastEdge = NULL;
484 if( tess->cacheCount > 0 ) {
485 /* Just set a flag so we don't get confused by empty contours
486 * -- these can be generated accidentally with the obsolete
487 * NextContour() interface.
488 */
489 tess->emptyCache = TRUE;
490 }
491 }
492
493
494 void GLAPIENTRY
495 gluTessEndContour( GLUtesselator *tess )
496 {
497 RequireState( tess, T_IN_CONTOUR );
498 tess->state = T_IN_POLYGON;
499 }
500
501 void GLAPIENTRY
502 gluTessEndPolygon( GLUtesselator *tess )
503 {
504 GLUmesh *mesh;
505
506 if (setjmp(tess->env) != 0) {
507 /* come back here if out of memory */
508 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
509 return;
510 }
511
512 RequireState( tess, T_IN_POLYGON );
513 tess->state = T_DORMANT;
514
515 if( tess->mesh == NULL ) {
516 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
517
518 /* Try some special code to make the easy cases go quickly
519 * (eg. convex polygons). This code does NOT handle multiple contours,
520 * intersections, edge flags, and of course it does not generate
521 * an explicit mesh either.
522 */
523 if( __gl_renderCache( tess )) {
524 tess->polygonData= NULL;
525 return;
526 }
527 }
528 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
529 }
530
531 /* Determine the polygon normal and project vertices onto the plane
532 * of the polygon.
533 */
534 __gl_projectPolygon( tess );
535
536 /* __gl_computeInterior( tess ) computes the planar arrangement specified
537 * by the given contours, and further subdivides this arrangement
538 * into regions. Each region is marked "inside" if it belongs
539 * to the polygon, according to the rule given by tess->windingRule.
540 * Each interior region is guaranteed be monotone.
541 */
542 if ( !__gl_computeInterior( tess ) ) {
543 longjmp(tess->env,1); /* could've used a label */
544 }
545
546 mesh = tess->mesh;
547 if( ! tess->fatalError ) {
548 int rc = 1;
549
550 /* If the user wants only the boundary contours, we throw away all edges
551 * except those which separate the interior from the exterior.
552 * Otherwise we tessellate all the regions marked "inside".
553 */
554 if( tess->boundaryOnly ) {
555 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
556 } else {
557 rc = __gl_meshTessellateInterior( mesh );
558 }
559 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
560
561 __gl_meshCheckMesh( mesh );
562
563 if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
564 || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
565 || tess->callBeginData != &__gl_noBeginData
566 || tess->callEndData != &__gl_noEndData
567 || tess->callVertexData != &__gl_noVertexData
568 || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
569 {
570 if( tess->boundaryOnly ) {
571 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
572 } else {
573 __gl_renderMesh( tess, mesh ); /* output strips and fans */
574 }
575 }
576 if( tess->callMesh != &noMesh ) {
577
578 /* Throw away the exterior faces, so that all faces are interior.
579 * This way the user doesn't have to check the "inside" flag,
580 * and we don't need to even reveal its existence. It also leaves
581 * the freedom for an implementation to not generate the exterior
582 * faces in the first place.
583 */
584 __gl_meshDiscardExterior( mesh );
585 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
586 tess->mesh = NULL;
587 tess->polygonData= NULL;
588 return;
589 }
590 }
591 __gl_meshDeleteMesh( mesh );
592 tess->polygonData= NULL;
593 tess->mesh = NULL;
594 }
595
596
597 /*XXXblythe unused function*/
598 #if 0
599 void GLAPIENTRY
600 gluDeleteMesh( GLUmesh *mesh )
601 {
602 __gl_meshDeleteMesh( mesh );
603 }
604 #endif
605
606
607
608 /*******************************************************/
609
610 /* Obsolete calls -- for backward compatibility */
611
612 void GLAPIENTRY
613 gluBeginPolygon( GLUtesselator *tess )
614 {
615 gluTessBeginPolygon( tess, NULL );
616 gluTessBeginContour( tess );
617 }
618
619
620 /*ARGSUSED*/
621 void GLAPIENTRY
622 gluNextContour( GLUtesselator *tess, GLenum type )
623 {
624 gluTessEndContour( tess );
625 gluTessBeginContour( tess );
626 }
627
628
629 void GLAPIENTRY
630 gluEndPolygon( GLUtesselator *tess )
631 {
632 gluTessEndContour( tess );
633 gluTessEndPolygon( tess );
634 }