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