SGI SI GLU library
[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: 2001/03/17 00:25:41 $ $Revision: 1.1 $
39 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/tess.c,v 1.1 2001/03/17 00:25:41 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 }
173 } else {
174 switch( tess->state ) {
175 case T_IN_CONTOUR:
176 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
177 gluTessEndContour( tess );
178 break;
179 case T_IN_POLYGON:
180 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
181 /* gluTessEndPolygon( tess ) is too much work! */
182 MakeDormant( tess );
183 break;
184 }
185 }
186 }
187 }
188
189
190 void GLAPIENTRY
191 gluDeleteTess( GLUtesselator *tess )
192 {
193 RequireState( tess, T_DORMANT );
194 memFree( tess );
195 }
196
197
198 void GLAPIENTRY
199 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
200 {
201 GLenum windingRule;
202
203 switch( which ) {
204 case GLU_TESS_TOLERANCE:
205 if( value < 0.0 || value > 1.0 ) break;
206 tess->relTolerance = value;
207 return;
208
209 case GLU_TESS_WINDING_RULE:
210 windingRule = (GLenum) value;
211 if( windingRule != value ) break; /* not an integer */
212
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;
220 return;
221 default:
222 break;
223 }
224
225 case GLU_TESS_BOUNDARY_ONLY:
226 tess->boundaryOnly = (value != 0);
227 return;
228
229 default:
230 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
231 return;
232 }
233 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
234 }
235
236 /* Returns tessellator property */
237 void GLAPIENTRY
238 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
239 {
240 switch (which) {
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;
245 break;
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;
253 break;
254 case GLU_TESS_BOUNDARY_ONLY:
255 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
256 *value= tess->boundaryOnly;
257 break;
258 default:
259 *value= 0.0;
260 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
261 break;
262 }
263 } /* gluGetTessProperty() */
264
265 void GLAPIENTRY
266 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
267 {
268 tess->normal[0] = x;
269 tess->normal[1] = y;
270 tess->normal[2] = z;
271 }
272
273 void GLAPIENTRY
274 gluTessCallback( GLUtesselator *tess, GLenum which, void (GLAPIENTRY *fn)())
275 {
276 switch( which ) {
277 case GLU_TESS_BEGIN:
278 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
279 return;
280 case GLU_TESS_BEGIN_DATA:
281 tess->callBeginData = (fn == NULL) ?
282 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
283 return;
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).
289 */
290 tess->flagBoundary = (fn != NULL);
291 return;
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).
297 */
298 tess->flagBoundary = (fn != NULL);
299 return;
300 case GLU_TESS_VERTEX:
301 tess->callVertex = (fn == NULL) ? &noVertex :
302 (void (GLAPIENTRY *)(void *)) fn;
303 return;
304 case GLU_TESS_VERTEX_DATA:
305 tess->callVertexData = (fn == NULL) ?
306 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
307 return;
308 case GLU_TESS_END:
309 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
310 return;
311 case GLU_TESS_END_DATA:
312 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
313 (void (GLAPIENTRY *)(void *)) fn;
314 return;
315 case GLU_TESS_ERROR:
316 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
317 return;
318 case GLU_TESS_ERROR_DATA:
319 tess->callErrorData = (fn == NULL) ?
320 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
321 return;
322 case GLU_TESS_COMBINE:
323 tess->callCombine = (fn == NULL) ? &noCombine :
324 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
325 return;
326 case GLU_TESS_COMBINE_DATA:
327 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
328 (void (GLAPIENTRY *)(GLdouble [3],
329 void *[4],
330 GLfloat [4],
331 void **,
332 void *)) fn;
333 return;
334 case GLU_TESS_MESH:
335 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
336 return;
337 default:
338 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
339 return;
340 }
341 }
342
343 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
344 {
345 GLUhalfEdge *e;
346
347 e = tess->lastEdge;
348 if( e == NULL ) {
349 /* Make a self-loop (one vertex, one edge). */
350
351 e = __gl_meshMakeEdge( tess->mesh );
352 if (e == NULL) return 0;
353 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
354 } else {
355 /* Create a new vertex and edge which immediately follow e
356 * in the ordering around the left face.
357 */
358 if (__gl_meshSplitEdge( e ) == NULL) return 0;
359 e = e->Lnext;
360 }
361
362 /* The new vertex is now e->Org. */
363 e->Org->data = data;
364 e->Org->coords[0] = coords[0];
365 e->Org->coords[1] = coords[1];
366 e->Org->coords[2] = coords[2];
367
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.
372 */
373 e->winding = 1;
374 e->Sym->winding = -1;
375
376 tess->lastEdge = e;
377
378 return 1;
379 }
380
381
382 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
383 {
384 CachedVertex *v = &tess->cache[tess->cacheCount];
385
386 v->data = data;
387 v->coords[0] = coords[0];
388 v->coords[1] = coords[1];
389 v->coords[2] = coords[2];
390 ++tess->cacheCount;
391 }
392
393
394 static int EmptyCache( GLUtesselator *tess )
395 {
396 CachedVertex *v = tess->cache;
397 CachedVertex *vLast;
398
399 tess->mesh = __gl_meshNewMesh();
400 if (tess->mesh == NULL) return 0;
401
402 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
403 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
404 }
405 tess->cacheCount = 0;
406 tess->emptyCache = FALSE;
407
408 return 1;
409 }
410
411
412 void GLAPIENTRY
413 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
414 {
415 int i, tooLarge = FALSE;
416 GLdouble x, clamped[3];
417
418 RequireState( tess, T_IN_CONTOUR );
419
420 if( tess->emptyCache ) {
421 if ( !EmptyCache( tess ) ) {
422 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
423 return;
424 }
425 tess->lastEdge = NULL;
426 }
427 for( i = 0; i < 3; ++i ) {
428 x = coords[i];
429 if( x < - GLU_TESS_MAX_COORD ) {
430 x = - GLU_TESS_MAX_COORD;
431 tooLarge = TRUE;
432 }
433 if( x > GLU_TESS_MAX_COORD ) {
434 x = GLU_TESS_MAX_COORD;
435 tooLarge = TRUE;
436 }
437 clamped[i] = x;
438 }
439 if( tooLarge ) {
440 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
441 }
442
443 if( tess->mesh == NULL ) {
444 if( tess->cacheCount < TESS_MAX_CACHE ) {
445 CacheVertex( tess, clamped, data );
446 return;
447 }
448 if ( !EmptyCache( tess ) ) {
449 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
450 return;
451 }
452 }
453 if ( !AddVertex( tess, clamped, data ) ) {
454 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
455 }
456 }
457
458
459 void GLAPIENTRY
460 gluTessBeginPolygon( GLUtesselator *tess, void *data )
461 {
462 RequireState( tess, T_DORMANT );
463
464 tess->state = T_IN_POLYGON;
465 tess->cacheCount = 0;
466 tess->emptyCache = FALSE;
467 tess->mesh = NULL;
468
469 tess->polygonData= data;
470 }
471
472
473 void GLAPIENTRY
474 gluTessBeginContour( GLUtesselator *tess )
475 {
476 RequireState( tess, T_IN_POLYGON );
477
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.
484 */
485 tess->emptyCache = TRUE;
486 }
487 }
488
489
490 void GLAPIENTRY
491 gluTessEndContour( GLUtesselator *tess )
492 {
493 RequireState( tess, T_IN_CONTOUR );
494 tess->state = T_IN_POLYGON;
495 }
496
497 void GLAPIENTRY
498 gluTessEndPolygon( GLUtesselator *tess )
499 {
500 GLUmesh *mesh;
501
502 if (setjmp(tess->env) != 0) {
503 /* come back here if out of memory */
504 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
505 return;
506 }
507
508 RequireState( tess, T_IN_POLYGON );
509 tess->state = T_DORMANT;
510
511 if( tess->mesh == NULL ) {
512 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
513
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.
518 */
519 if( __gl_renderCache( tess )) {
520 tess->polygonData= NULL;
521 return;
522 }
523 }
524 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
525 }
526
527 /* Determine the polygon normal and project vertices onto the plane
528 * of the polygon.
529 */
530 __gl_projectPolygon( tess );
531
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.
537 */
538 if ( !__gl_computeInterior( tess ) ) {
539 longjmp(tess->env,1); /* could've used a label */
540 }
541
542 mesh = tess->mesh;
543 if( ! tess->fatalError ) {
544 int rc = 1;
545
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".
549 */
550 if( tess->boundaryOnly ) {
551 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
552 } else {
553 rc = __gl_meshTessellateInterior( mesh );
554 }
555 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
556
557 __gl_meshCheckMesh( mesh );
558
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 )
565 {
566 if( tess->boundaryOnly ) {
567 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
568 } else {
569 __gl_renderMesh( tess, mesh ); /* output strips and fans */
570 }
571 }
572 if( tess->callMesh != &noMesh ) {
573
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.
579 */
580 __gl_meshDiscardExterior( mesh );
581 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
582 tess->mesh = NULL;
583 tess->polygonData= NULL;
584 return;
585 }
586 }
587 __gl_meshDeleteMesh( mesh );
588 tess->polygonData= NULL;
589 tess->mesh = NULL;
590 }
591
592
593 /*XXXblythe unused function*/
594 #if 0
595 void GLAPIENTRY
596 gluDeleteMesh( GLUmesh *mesh )
597 {
598 __gl_meshDeleteMesh( mesh );
599 }
600 #endif
601
602
603
604 /*******************************************************/
605
606 /* Obsolete calls -- for backward compatibility */
607
608 void GLAPIENTRY
609 gluBeginPolygon( GLUtesselator *tess )
610 {
611 gluTessBeginPolygon( tess, NULL );
612 gluTessBeginContour( tess );
613 }
614
615
616 /*ARGSUSED*/
617 void GLAPIENTRY
618 gluNextContour( GLUtesselator *tess, GLenum type )
619 {
620 gluTessEndContour( tess );
621 gluTessBeginContour( tess );
622 }
623
624
625 void GLAPIENTRY
626 gluEndPolygon( GLUtesselator *tess )
627 {
628 gluTessEndContour( tess );
629 gluTessEndPolygon( tess );
630 }