Tizen 2.0 Release
[profile/ivi/osmesa.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 #ifndef TRUE
51 #define TRUE 1
52 #endif
53 #ifndef FALSE
54 #define FALSE 0
55 #endif
56
57 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
58 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
59 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
60 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
61 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
62 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
63                                     GLfloat weight[4], void **dataOut ) {}
64 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
65
66
67 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
68                                              void *polygonData ) {}
69 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
70                                        void *polygonData ) {}
71 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
72                                               void *polygonData ) {}
73 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
74 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
75                                              void *polygonData ) {}
76 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
77                                                void *data[4],
78                                                GLfloat weight[4],
79                                                void **outData,
80                                                void *polygonData ) {}
81
82 /* Half-edges are allocated in pairs (see mesh.c) */
83 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
84
85 #undef  MAX
86 #define MAX(a,b)        ((a) > (b) ? (a) : (b))
87 #define MAX_FAST_ALLOC  (MAX(sizeof(EdgePair), \
88                          MAX(sizeof(GLUvertex),sizeof(GLUface))))
89
90
91 GLUtesselator * GLAPIENTRY
92 gluNewTess( void )
93 {
94   GLUtesselator *tess;
95
96   /* Only initialize fields which can be changed by the api.  Other fields
97    * are initialized where they are used.
98    */
99
100   if (memInit( MAX_FAST_ALLOC ) == 0) {
101      return 0;                  /* out of memory */
102   }
103   tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator ));
104   if (tess == NULL) {
105      return 0;                  /* out of memory */
106   }
107
108   tess->state = T_DORMANT;
109
110   tess->normal[0] = 0;
111   tess->normal[1] = 0;
112   tess->normal[2] = 0;
113
114   tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
115   tess->windingRule = GLU_TESS_WINDING_ODD;
116   tess->flagBoundary = FALSE;
117   tess->boundaryOnly = FALSE;
118
119   tess->callBegin = &noBegin;
120   tess->callEdgeFlag = &noEdgeFlag;
121   tess->callVertex = &noVertex;
122   tess->callEnd = &noEnd;
123
124   tess->callError = &noError;
125   tess->callCombine = &noCombine;
126   tess->callMesh = &noMesh;
127
128   tess->callBeginData= &__gl_noBeginData;
129   tess->callEdgeFlagData= &__gl_noEdgeFlagData;
130   tess->callVertexData= &__gl_noVertexData;
131   tess->callEndData= &__gl_noEndData;
132   tess->callErrorData= &__gl_noErrorData;
133   tess->callCombineData= &__gl_noCombineData;
134
135   tess->polygonData= NULL;
136
137   return tess;
138 }
139
140 static void MakeDormant( GLUtesselator *tess )
141 {
142   /* Return the tessellator to its original dormant state. */
143
144   if( tess->mesh != NULL ) {
145     __gl_meshDeleteMesh( tess->mesh );
146   }
147   tess->state = T_DORMANT;
148   tess->lastEdge = NULL;
149   tess->mesh = NULL;
150 }
151
152 #define RequireState( tess, s )   if( tess->state != s ) GotoState(tess,s)
153
154 static void GotoState( GLUtesselator *tess, enum TessState newState )
155 {
156   while( tess->state != newState ) {
157     /* We change the current state one level at a time, to get to
158      * the desired state.
159      */
160     if( tess->state < newState ) {
161       switch( tess->state ) {
162       case T_DORMANT:
163         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
164         gluTessBeginPolygon( tess, NULL );
165         break;
166       case T_IN_POLYGON:
167         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
168         gluTessBeginContour( tess );
169         break;
170       default:
171          ;
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       default:
185          ;
186       }
187     }
188   }
189 }
190
191
192 void GLAPIENTRY
193 gluDeleteTess( GLUtesselator *tess )
194 {
195   RequireState( tess, T_DORMANT );
196   memFree( tess );
197 }
198
199
200 void GLAPIENTRY
201 gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
202 {
203   GLenum windingRule;
204
205   switch( which ) {
206   case GLU_TESS_TOLERANCE:
207     if( value < 0.0 || value > 1.0 ) break;
208     tess->relTolerance = value;
209     return;
210
211   case GLU_TESS_WINDING_RULE:
212     windingRule = (GLenum) value;
213     if( windingRule != value ) break;   /* not an integer */
214
215     switch( windingRule ) {
216     case GLU_TESS_WINDING_ODD:
217     case GLU_TESS_WINDING_NONZERO:
218     case GLU_TESS_WINDING_POSITIVE:
219     case GLU_TESS_WINDING_NEGATIVE:
220     case GLU_TESS_WINDING_ABS_GEQ_TWO:
221       tess->windingRule = windingRule;
222       return;
223     default:
224       break;
225     }
226
227   case GLU_TESS_BOUNDARY_ONLY:
228     tess->boundaryOnly = (value != 0);
229     return;
230
231   default:
232     CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
233     return;
234   }
235   CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
236 }
237
238 /* Returns tessellator property */
239 void GLAPIENTRY
240 gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
241 {
242    switch (which) {
243    case GLU_TESS_TOLERANCE:
244       /* tolerance should be in range [0..1] */
245       assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
246       *value= tess->relTolerance;
247       break;
248    case GLU_TESS_WINDING_RULE:
249       assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
250              tess->windingRule == GLU_TESS_WINDING_NONZERO ||
251              tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
252              tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
253              tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
254       *value= tess->windingRule;
255       break;
256    case GLU_TESS_BOUNDARY_ONLY:
257       assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
258       *value= tess->boundaryOnly;
259       break;
260    default:
261       *value= 0.0;
262       CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
263       break;
264    }
265 } /* gluGetTessProperty() */
266
267 void GLAPIENTRY
268 gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
269 {
270   tess->normal[0] = x;
271   tess->normal[1] = y;
272   tess->normal[2] = z;
273 }
274
275 void GLAPIENTRY
276 gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
277 {
278   switch( which ) {
279   case GLU_TESS_BEGIN:
280     tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
281     return;
282   case GLU_TESS_BEGIN_DATA:
283     tess->callBeginData = (fn == NULL) ?
284         &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
285     return;
286   case GLU_TESS_EDGE_FLAG:
287     tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
288                                         (void (GLAPIENTRY *)(GLboolean)) fn;
289     /* If the client wants boundary edges to be flagged,
290      * we render everything as separate triangles (no strips or fans).
291      */
292     tess->flagBoundary = (fn != NULL);
293     return;
294   case GLU_TESS_EDGE_FLAG_DATA:
295     tess->callEdgeFlagData= (fn == NULL) ?
296         &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
297     /* If the client wants boundary edges to be flagged,
298      * we render everything as separate triangles (no strips or fans).
299      */
300     tess->flagBoundary = (fn != NULL);
301     return;
302   case GLU_TESS_VERTEX:
303     tess->callVertex = (fn == NULL) ? &noVertex :
304                                       (void (GLAPIENTRY *)(void *)) fn;
305     return;
306   case GLU_TESS_VERTEX_DATA:
307     tess->callVertexData = (fn == NULL) ?
308         &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
309     return;
310   case GLU_TESS_END:
311     tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
312     return;
313   case GLU_TESS_END_DATA:
314     tess->callEndData = (fn == NULL) ? &__gl_noEndData :
315                                        (void (GLAPIENTRY *)(void *)) fn;
316     return;
317   case GLU_TESS_ERROR:
318     tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
319     return;
320   case GLU_TESS_ERROR_DATA:
321     tess->callErrorData = (fn == NULL) ?
322         &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
323     return;
324   case GLU_TESS_COMBINE:
325     tess->callCombine = (fn == NULL) ? &noCombine :
326         (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
327     return;
328   case GLU_TESS_COMBINE_DATA:
329     tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
330                                            (void (GLAPIENTRY *)(GLdouble [3],
331                                                      void *[4],
332                                                      GLfloat [4],
333                                                      void **,
334                                                      void *)) fn;
335     return;
336   case GLU_TESS_MESH:
337     tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
338     return;
339   default:
340     CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
341     return;
342   }
343 }
344
345 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
346 {
347   GLUhalfEdge *e;
348
349   e = tess->lastEdge;
350   if( e == NULL ) {
351     /* Make a self-loop (one vertex, one edge). */
352
353     e = __gl_meshMakeEdge( tess->mesh );
354     if (e == NULL) return 0;
355     if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
356   } else {
357     /* Create a new vertex and edge which immediately follow e
358      * in the ordering around the left face.
359      */
360     if (__gl_meshSplitEdge( e ) == NULL) return 0;
361     e = e->Lnext;
362   }
363
364   /* The new vertex is now e->Org. */
365   e->Org->data = data;
366   e->Org->coords[0] = coords[0];
367   e->Org->coords[1] = coords[1];
368   e->Org->coords[2] = coords[2];
369
370   /* The winding of an edge says how the winding number changes as we
371    * cross from the edge''s right face to its left face.  We add the
372    * vertices in such an order that a CCW contour will add +1 to
373    * the winding number of the region inside the contour.
374    */
375   e->winding = 1;
376   e->Sym->winding = -1;
377
378   tess->lastEdge = e;
379
380   return 1;
381 }
382
383
384 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
385 {
386   CachedVertex *v = &tess->cache[tess->cacheCount];
387
388   v->data = data;
389   v->coords[0] = coords[0];
390   v->coords[1] = coords[1];
391   v->coords[2] = coords[2];
392   ++tess->cacheCount;
393 }
394
395
396 static int EmptyCache( GLUtesselator *tess )
397 {
398   CachedVertex *v = tess->cache;
399   CachedVertex *vLast;
400
401   tess->mesh = __gl_meshNewMesh();
402   if (tess->mesh == NULL) return 0;
403
404   for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
405     if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
406   }
407   tess->cacheCount = 0;
408   tess->emptyCache = FALSE;
409
410   return 1;
411 }
412
413
414 void GLAPIENTRY
415 gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
416 {
417   int i, tooLarge = FALSE;
418   GLdouble x, clamped[3];
419
420   RequireState( tess, T_IN_CONTOUR );
421
422   if( tess->emptyCache ) {
423     if ( !EmptyCache( tess ) ) {
424        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
425        return;
426     }
427     tess->lastEdge = NULL;
428   }
429   for( i = 0; i < 3; ++i ) {
430     x = coords[i];
431     if( x < - GLU_TESS_MAX_COORD ) {
432       x = - GLU_TESS_MAX_COORD;
433       tooLarge = TRUE;
434     }
435     if( x > GLU_TESS_MAX_COORD ) {
436       x = GLU_TESS_MAX_COORD;
437       tooLarge = TRUE;
438     }
439     clamped[i] = x;
440   }
441   if( tooLarge ) {
442     CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
443   }
444
445   if( tess->mesh == NULL ) {
446     if( tess->cacheCount < TESS_MAX_CACHE ) {
447       CacheVertex( tess, clamped, data );
448       return;
449     }
450     if ( !EmptyCache( tess ) ) {
451        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
452        return;
453     }
454   }
455   if ( !AddVertex( tess, clamped, data ) ) {
456        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
457   }
458 }
459
460
461 void GLAPIENTRY
462 gluTessBeginPolygon( GLUtesselator *tess, void *data )
463 {
464   RequireState( tess, T_DORMANT );
465
466   tess->state = T_IN_POLYGON;
467   tess->cacheCount = 0;
468   tess->emptyCache = FALSE;
469   tess->mesh = NULL;
470
471   tess->polygonData= data;
472 }
473
474
475 void GLAPIENTRY
476 gluTessBeginContour( GLUtesselator *tess )
477 {
478   RequireState( tess, T_IN_POLYGON );
479
480   tess->state = T_IN_CONTOUR;
481   tess->lastEdge = NULL;
482   if( tess->cacheCount > 0 ) {
483     /* Just set a flag so we don't get confused by empty contours
484      * -- these can be generated accidentally with the obsolete
485      * NextContour() interface.
486      */
487     tess->emptyCache = TRUE;
488   }
489 }
490
491
492 void GLAPIENTRY
493 gluTessEndContour( GLUtesselator *tess )
494 {
495   RequireState( tess, T_IN_CONTOUR );
496   tess->state = T_IN_POLYGON;
497 }
498
499 void GLAPIENTRY
500 gluTessEndPolygon( GLUtesselator *tess )
501 {
502   GLUmesh *mesh;
503
504   if (setjmp(tess->env) != 0) { 
505      /* come back here if out of memory */
506      CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
507      return;
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 }