Butterbur: Tesselation support for filling closed paths
[sdk] / deps / 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 */
39
40 #include "gluos.h"
41 #include <stddef.h>
42 #include <assert.h>
43 #include <setjmp.h>
44 #include "memalloc.h"
45 #include "tess.h"
46 #include "mesh.h"
47 #include "normal.h"
48 #include "sweep.h"
49 #include "tessmono.h"
50 #include "render.h"
51
52 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
53 #define GLU_TESS_MESH           100112  /* void (*)(GLUmesh *mesh)          */
54
55 #define TRUE 1
56 #define FALSE 0
57
58 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
59 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
61 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
62 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
63 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
64                                     GLfloat weight[4], void **dataOut ) {}
65 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
66
67
68 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
69                                              void *polygonData ) {}
70 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
71                                        void *polygonData ) {}
72 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
73                                               void *polygonData ) {}
74 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
75 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
76                                              void *polygonData ) {}
77 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
78                                                void *data[4],
79                                                GLfloat weight[4],
80                                                void **outData,
81                                                void *polygonData ) {}
82
83 /* Half-edges are allocated in pairs (see mesh.c) */
84 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
85
86 #undef  MAX
87 #define MAX(a,b)        ((a) > (b) ? (a) : (b))
88 #define MAX_FAST_ALLOC  (MAX(sizeof(EdgePair), \
89                          MAX(sizeof(GLUvertex),sizeof(GLUface))))
90
91
92 GLUtesselator * GLAPIENTRY
93 gluNewTess( void )
94 {
95   GLUtesselator *tess;
96
97   /* Only initialize fields which can be changed by the api.  Other fields
98    * are initialized where they are used.
99    */
100
101   tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
102   if (tess == NULL) {
103      return 0;                  /* out of memory */
104   }
105
106   tess->state = T_DORMANT;
107
108   tess->normal[0] = 0;
109   tess->normal[1] = 0;
110   tess->normal[2] = 0;
111
112   tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
113   tess->windingRule = GLU_TESS_WINDING_ODD;
114   tess->flagBoundary = FALSE;
115   tess->boundaryOnly = FALSE;
116
117   tess->callBegin = &noBegin;
118   tess->callEdgeFlag = &noEdgeFlag;
119   tess->callVertex = &noVertex;
120   tess->callEnd = &noEnd;
121
122   tess->callError = &noError;
123   tess->callCombine = &noCombine;
124   tess->callMesh = &noMesh;
125
126   tess->callBeginData= &__gl_noBeginData;
127   tess->callEdgeFlagData= &__gl_noEdgeFlagData;
128   tess->callVertexData= &__gl_noVertexData;
129   tess->callEndData= &__gl_noEndData;
130   tess->callErrorData= &__gl_noErrorData;
131   tess->callCombineData= &__gl_noCombineData;
132
133   tess->polygonData= NULL;
134
135   return tess;
136 }
137
138 static void MakeDormant( GLUtesselator *tess )
139 {
140   /* Return the tessellator to its original dormant state. */
141
142   if( tess->mesh != NULL ) {
143     __gl_meshDeleteMesh( tess->mesh );
144   }
145   tess->state = T_DORMANT;
146   tess->lastEdge = NULL;
147   tess->mesh = NULL;
148 }
149
150 #define RequireState( tess, s )   if( tess->state != s ) GotoState(tess,s)
151
152 static void GotoState( GLUtesselator *tess, enum TessState newState )
153 {
154   while( tess->state != newState ) {
155     /* We change the current state one level at a time, to get to
156      * the desired state.
157      */
158     if( tess->state < newState ) {
159       switch( tess->state ) {
160       case T_DORMANT:
161         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
162         gluTessBeginPolygon( tess, NULL );
163         break;
164       case T_IN_POLYGON:
165         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
166         gluTessBeginContour( tess );
167         break;
168       default:
169          ;
170       }
171     } else {
172       switch( tess->state ) {
173       case T_IN_CONTOUR:
174         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
175         gluTessEndContour( tess );
176         break;
177       case T_IN_POLYGON:
178         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
179         /* gluTessEndPolygon( tess ) is too much work! */
180         MakeDormant( tess );
181         break;
182       default:
183          ;
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, _GLUfuncptr 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   /*  No idea why, but setjmp() has suddenly started to crash...
503   if (setjmp(tess->env) != 0) {
504      // come back here if out of memory
505      CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
506      return;
507   }
508   */
509
510   RequireState( tess, T_IN_POLYGON );
511   tess->state = T_DORMANT;
512
513   if( tess->mesh == NULL ) {
514     if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
515
516       /* Try some special code to make the easy cases go quickly
517        * (eg. convex polygons).  This code does NOT handle multiple contours,
518        * intersections, edge flags, and of course it does not generate
519        * an explicit mesh either.
520        */
521       if( __gl_renderCache( tess )) {
522         tess->polygonData= NULL;
523         return;
524       }
525     }
526     if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
527   }
528
529   /* Determine the polygon normal and project vertices onto the plane
530    * of the polygon.
531    */
532   __gl_projectPolygon( tess );
533
534   /* __gl_computeInterior( tess ) computes the planar arrangement specified
535    * by the given contours, and further subdivides this arrangement
536    * into regions.  Each region is marked "inside" if it belongs
537    * to the polygon, according to the rule given by tess->windingRule.
538    * Each interior region is guaranteed be monotone.
539    */
540   if ( !__gl_computeInterior( tess ) ) {
541      longjmp(tess->env,1);      /* could've used a label */
542   }
543
544   mesh = tess->mesh;
545   if( ! tess->fatalError ) {
546     int rc = 1;
547
548     /* If the user wants only the boundary contours, we throw away all edges
549      * except those which separate the interior from the exterior.
550      * Otherwise we tessellate all the regions marked "inside".
551      */
552     if( tess->boundaryOnly ) {
553       rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
554     } else {
555       rc = __gl_meshTessellateInterior( mesh );
556     }
557     if (rc == 0) longjmp(tess->env,1);  /* could've used a label */
558
559     __gl_meshCheckMesh( mesh );
560
561     if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
562        || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
563        || tess->callBeginData != &__gl_noBeginData
564        || tess->callEndData != &__gl_noEndData
565        || tess->callVertexData != &__gl_noVertexData
566        || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
567     {
568       if( tess->boundaryOnly ) {
569         __gl_renderBoundary( tess, mesh );  /* output boundary contours */
570       } else {
571         __gl_renderMesh( tess, mesh );     /* output strips and fans */
572       }
573     }
574     if( tess->callMesh != &noMesh ) {
575
576       /* Throw away the exterior faces, so that all faces are interior.
577        * This way the user doesn't have to check the "inside" flag,
578        * and we don't need to even reveal its existence.  It also leaves
579        * the freedom for an implementation to not generate the exterior
580        * faces in the first place.
581        */
582       __gl_meshDiscardExterior( mesh );
583       (*tess->callMesh)( mesh );                /* user wants the mesh itself */
584       tess->mesh = NULL;
585       tess->polygonData= NULL;
586       return;
587     }
588   }
589   __gl_meshDeleteMesh( mesh );
590   tess->polygonData= NULL;
591   tess->mesh = NULL;
592 }
593
594
595 /*XXXblythe unused function*/
596 #if 0
597 void GLAPIENTRY
598 gluDeleteMesh( GLUmesh *mesh )
599 {
600   __gl_meshDeleteMesh( mesh );
601 }
602 #endif
603
604
605
606 /*******************************************************/
607
608 /* Obsolete calls -- for backward compatibility */
609
610 void GLAPIENTRY
611 gluBeginPolygon( GLUtesselator *tess )
612 {
613   gluTessBeginPolygon( tess, NULL );
614   gluTessBeginContour( tess );
615 }
616
617
618 /*ARGSUSED*/
619 void GLAPIENTRY
620 gluNextContour( GLUtesselator *tess, GLenum type )
621 {
622   gluTessEndContour( tess );
623   gluTessBeginContour( tess );
624 }
625
626
627 void GLAPIENTRY
628 gluEndPolygon( GLUtesselator *tess )
629 {
630   gluTessEndContour( tess );
631   gluTessEndPolygon( tess );
632 }