Merge commit 'origin/gallium-0.1' into gallium-0.2
[mesa.git] / src / glu / sgi / libtess / tess.c
1 /*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
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:
11 *
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.
16 *
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
23 * SOFTWARE.
24 *
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.
29 */
30 /*
31 ** Author: Eric Veach, July 1994.
32 **
33 */
34
35 #include "gluos.h"
36 #include <stddef.h>
37 #include <assert.h>
38 #include <setjmp.h>
39 #include "memalloc.h"
40 #include "tess.h"
41 #include "mesh.h"
42 #include "normal.h"
43 #include "sweep.h"
44 #include "tessmono.h"
45 #include "render.h"
46
47 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
48 #define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */
49
50 #define TRUE 1
51 #define FALSE 0
52
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 ) {}
61
62
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],
73 void *data[4],
74 GLfloat weight[4],
75 void **outData,
76 void *polygonData ) {}
77
78 /* Half-edges are allocated in pairs (see mesh.c) */
79 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
80
81 #undef MAX
82 #define MAX(a,b) ((a) > (b) ? (a) : (b))
83 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \
84 MAX(sizeof(GLUvertex),sizeof(GLUface))))
85
86
87 GLUtesselator * GLAPIENTRY
88 gluNewTess( void )
89 {
90 GLUtesselator *tess;
91
92 /* Only initialize fields which can be changed by the api. Other fields
93 * are initialized where they are used.
94 */
95
96 if (memInit( MAX_FAST_ALLOC ) == 0) {
97 return 0; /* out of memory */
98 }
99 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
100 if (tess == NULL) {
101 return 0; /* out of memory */
102 }
103
104 tess->state = T_DORMANT;
105
106 tess->normal[0] = 0;
107 tess->normal[1] = 0;
108 tess->normal[2] = 0;
109
110 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
111 tess->windingRule = GLU_TESS_WINDING_ODD;
112 tess->flagBoundary = FALSE;
113 tess->boundaryOnly = FALSE;
114
115 tess->callBegin = &noBegin;
116 tess->callEdgeFlag = &noEdgeFlag;
117 tess->callVertex = &noVertex;
118 tess->callEnd = &noEnd;
119
120 tess->callError = &noError;
121 tess->callCombine = &noCombine;
122 tess->callMesh = &noMesh;
123
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;
130
131 tess->polygonData= NULL;
132
133 return tess;
134 }
135
136 static void MakeDormant( GLUtesselator *tess )
137 {
138 /* Return the tessellator to its original dormant state. */
139
140 if( tess->mesh != NULL ) {
141 __gl_meshDeleteMesh( tess->mesh );
142 }
143 tess->state = T_DORMANT;
144 tess->lastEdge = NULL;
145 tess->mesh = NULL;
146 }
147
148 #define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s)
149
150 static void GotoState( GLUtesselator *tess, enum TessState newState )
151 {
152 while( tess->state != newState ) {
153 /* We change the current state one level at a time, to get to
154 * the desired state.
155 */
156 if( tess->state < newState ) {
157 switch( tess->state ) {
158 case T_DORMANT:
159 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
160 gluTessBeginPolygon( tess, NULL );
161 break;
162 case T_IN_POLYGON:
163 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
164 gluTessBeginContour( tess );
165 break;
166 default:
167 ;
168 }
169 } else {
170 switch( tess->state ) {
171 case T_IN_CONTOUR:
172 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
173 gluTessEndContour( tess );
174 break;
175 case T_IN_POLYGON:
176 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
177 /* gluTessEndPolygon( tess ) is too much work! */
178 MakeDormant( tess );
179 break;
180 default:
181 ;
182 }
183 }
184 }
185 }
186
187
188 void GLAPIENTRY
189 gluDeleteTess( GLUtesselator *tess )
190 {
191 RequireState( tess, T_DORMANT );
192 memFree( tess );
193 }
194
195
196 void GLAPIENTRY
197 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
198 {
199 GLenum windingRule;
200
201 switch( which ) {
202 case GLU_TESS_TOLERANCE:
203 if( value < 0.0 || value > 1.0 ) break;
204 tess->relTolerance = value;
205 return;
206
207 case GLU_TESS_WINDING_RULE:
208 windingRule = (GLenum) value;
209 if( windingRule != value ) break; /* not an integer */
210
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;
218 return;
219 default:
220 break;
221 }
222
223 case GLU_TESS_BOUNDARY_ONLY:
224 tess->boundaryOnly = (value != 0);
225 return;
226
227 default:
228 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
229 return;
230 }
231 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
232 }
233
234 /* Returns tessellator property */
235 void GLAPIENTRY
236 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
237 {
238 switch (which) {
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;
243 break;
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;
251 break;
252 case GLU_TESS_BOUNDARY_ONLY:
253 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
254 *value= tess->boundaryOnly;
255 break;
256 default:
257 *value= 0.0;
258 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
259 break;
260 }
261 } /* gluGetTessProperty() */
262
263 void GLAPIENTRY
264 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
265 {
266 tess->normal[0] = x;
267 tess->normal[1] = y;
268 tess->normal[2] = z;
269 }
270
271 void GLAPIENTRY
272 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
273 {
274 switch( which ) {
275 case GLU_TESS_BEGIN:
276 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
277 return;
278 case GLU_TESS_BEGIN_DATA:
279 tess->callBeginData = (fn == NULL) ?
280 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
281 return;
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).
287 */
288 tess->flagBoundary = (fn != NULL);
289 return;
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).
295 */
296 tess->flagBoundary = (fn != NULL);
297 return;
298 case GLU_TESS_VERTEX:
299 tess->callVertex = (fn == NULL) ? &noVertex :
300 (void (GLAPIENTRY *)(void *)) fn;
301 return;
302 case GLU_TESS_VERTEX_DATA:
303 tess->callVertexData = (fn == NULL) ?
304 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
305 return;
306 case GLU_TESS_END:
307 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
308 return;
309 case GLU_TESS_END_DATA:
310 tess->callEndData = (fn == NULL) ? &__gl_noEndData :
311 (void (GLAPIENTRY *)(void *)) fn;
312 return;
313 case GLU_TESS_ERROR:
314 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
315 return;
316 case GLU_TESS_ERROR_DATA:
317 tess->callErrorData = (fn == NULL) ?
318 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
319 return;
320 case GLU_TESS_COMBINE:
321 tess->callCombine = (fn == NULL) ? &noCombine :
322 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
323 return;
324 case GLU_TESS_COMBINE_DATA:
325 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
326 (void (GLAPIENTRY *)(GLdouble [3],
327 void *[4],
328 GLfloat [4],
329 void **,
330 void *)) fn;
331 return;
332 case GLU_TESS_MESH:
333 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
334 return;
335 default:
336 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
337 return;
338 }
339 }
340
341 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
342 {
343 GLUhalfEdge *e;
344
345 e = tess->lastEdge;
346 if( e == NULL ) {
347 /* Make a self-loop (one vertex, one edge). */
348
349 e = __gl_meshMakeEdge( tess->mesh );
350 if (e == NULL) return 0;
351 if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
352 } else {
353 /* Create a new vertex and edge which immediately follow e
354 * in the ordering around the left face.
355 */
356 if (__gl_meshSplitEdge( e ) == NULL) return 0;
357 e = e->Lnext;
358 }
359
360 /* The new vertex is now e->Org. */
361 e->Org->data = data;
362 e->Org->coords[0] = coords[0];
363 e->Org->coords[1] = coords[1];
364 e->Org->coords[2] = coords[2];
365
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.
370 */
371 e->winding = 1;
372 e->Sym->winding = -1;
373
374 tess->lastEdge = e;
375
376 return 1;
377 }
378
379
380 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
381 {
382 CachedVertex *v = &tess->cache[tess->cacheCount];
383
384 v->data = data;
385 v->coords[0] = coords[0];
386 v->coords[1] = coords[1];
387 v->coords[2] = coords[2];
388 ++tess->cacheCount;
389 }
390
391
392 static int EmptyCache( GLUtesselator *tess )
393 {
394 CachedVertex *v = tess->cache;
395 CachedVertex *vLast;
396
397 tess->mesh = __gl_meshNewMesh();
398 if (tess->mesh == NULL) return 0;
399
400 for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
401 if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
402 }
403 tess->cacheCount = 0;
404 tess->emptyCache = FALSE;
405
406 return 1;
407 }
408
409
410 void GLAPIENTRY
411 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
412 {
413 int i, tooLarge = FALSE;
414 GLdouble x, clamped[3];
415
416 RequireState( tess, T_IN_CONTOUR );
417
418 if( tess->emptyCache ) {
419 if ( !EmptyCache( tess ) ) {
420 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
421 return;
422 }
423 tess->lastEdge = NULL;
424 }
425 for( i = 0; i < 3; ++i ) {
426 x = coords[i];
427 if( x < - GLU_TESS_MAX_COORD ) {
428 x = - GLU_TESS_MAX_COORD;
429 tooLarge = TRUE;
430 }
431 if( x > GLU_TESS_MAX_COORD ) {
432 x = GLU_TESS_MAX_COORD;
433 tooLarge = TRUE;
434 }
435 clamped[i] = x;
436 }
437 if( tooLarge ) {
438 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
439 }
440
441 if( tess->mesh == NULL ) {
442 if( tess->cacheCount < TESS_MAX_CACHE ) {
443 CacheVertex( tess, clamped, data );
444 return;
445 }
446 if ( !EmptyCache( tess ) ) {
447 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
448 return;
449 }
450 }
451 if ( !AddVertex( tess, clamped, data ) ) {
452 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
453 }
454 }
455
456
457 void GLAPIENTRY
458 gluTessBeginPolygon( GLUtesselator *tess, void *data )
459 {
460 RequireState( tess, T_DORMANT );
461
462 tess->state = T_IN_POLYGON;
463 tess->cacheCount = 0;
464 tess->emptyCache = FALSE;
465 tess->mesh = NULL;
466
467 tess->polygonData= data;
468 }
469
470
471 void GLAPIENTRY
472 gluTessBeginContour( GLUtesselator *tess )
473 {
474 RequireState( tess, T_IN_POLYGON );
475
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.
482 */
483 tess->emptyCache = TRUE;
484 }
485 }
486
487
488 void GLAPIENTRY
489 gluTessEndContour( GLUtesselator *tess )
490 {
491 RequireState( tess, T_IN_CONTOUR );
492 tess->state = T_IN_POLYGON;
493 }
494
495 void GLAPIENTRY
496 gluTessEndPolygon( GLUtesselator *tess )
497 {
498 GLUmesh *mesh;
499
500 if (setjmp(tess->env) != 0) {
501 /* come back here if out of memory */
502 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
503 return;
504 }
505
506 RequireState( tess, T_IN_POLYGON );
507 tess->state = T_DORMANT;
508
509 if( tess->mesh == NULL ) {
510 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
511
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.
516 */
517 if( __gl_renderCache( tess )) {
518 tess->polygonData= NULL;
519 return;
520 }
521 }
522 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
523 }
524
525 /* Determine the polygon normal and project vertices onto the plane
526 * of the polygon.
527 */
528 __gl_projectPolygon( tess );
529
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.
535 */
536 if ( !__gl_computeInterior( tess ) ) {
537 longjmp(tess->env,1); /* could've used a label */
538 }
539
540 mesh = tess->mesh;
541 if( ! tess->fatalError ) {
542 int rc = 1;
543
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".
547 */
548 if( tess->boundaryOnly ) {
549 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
550 } else {
551 rc = __gl_meshTessellateInterior( mesh );
552 }
553 if (rc == 0) longjmp(tess->env,1); /* could've used a label */
554
555 __gl_meshCheckMesh( mesh );
556
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 )
563 {
564 if( tess->boundaryOnly ) {
565 __gl_renderBoundary( tess, mesh ); /* output boundary contours */
566 } else {
567 __gl_renderMesh( tess, mesh ); /* output strips and fans */
568 }
569 }
570 if( tess->callMesh != &noMesh ) {
571
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.
577 */
578 __gl_meshDiscardExterior( mesh );
579 (*tess->callMesh)( mesh ); /* user wants the mesh itself */
580 tess->mesh = NULL;
581 tess->polygonData= NULL;
582 return;
583 }
584 }
585 __gl_meshDeleteMesh( mesh );
586 tess->polygonData= NULL;
587 tess->mesh = NULL;
588 }
589
590
591 /*XXXblythe unused function*/
592 #if 0
593 void GLAPIENTRY
594 gluDeleteMesh( GLUmesh *mesh )
595 {
596 __gl_meshDeleteMesh( mesh );
597 }
598 #endif
599
600
601
602 /*******************************************************/
603
604 /* Obsolete calls -- for backward compatibility */
605
606 void GLAPIENTRY
607 gluBeginPolygon( GLUtesselator *tess )
608 {
609 gluTessBeginPolygon( tess, NULL );
610 gluTessBeginContour( tess );
611 }
612
613
614 /*ARGSUSED*/
615 void GLAPIENTRY
616 gluNextContour( GLUtesselator *tess, GLenum type )
617 {
618 gluTessEndContour( tess );
619 gluTessBeginContour( tess );
620 }
621
622
623 void GLAPIENTRY
624 gluEndPolygon( GLUtesselator *tess )
625 {
626 gluTessEndContour( tess );
627 gluTessEndPolygon( tess );
628 }