]> git.jsancho.org Git - lugaru.git/blob - Dependencies/GLU/tess.c
CMake: Purge all the bundled dependencies
[lugaru.git] / Dependencies / GLU / 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 }