File indexing completed on 2024-03-24 15:17:34

0001 /*
0002 ** Author: Eric Veach, July 1994.
0003 **
0004 */
0005 
0006 #include "gluos.h"
0007 #include <stddef.h>
0008 #include <assert.h>
0009 #include <setjmp.h>
0010 #include "memalloc.h"
0011 #include "tess.h"
0012 #include "mesh.h"
0013 #include "normal.h"
0014 #include "sweep.h"
0015 #include "tessmono.h"
0016 #include "render.h"
0017 
0018 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
0019 #define GLU_TESS_MESH              100112 /* void (*)(GLUmesh *mesh)        */
0020 
0021 #ifndef TRUE
0022 #define TRUE 1
0023 #endif
0024 #ifndef FALSE
0025 #define FALSE 0
0026 #endif
0027 
0028 /*ARGSUSED*/ static void GLAPIENTRY noBegin(GLenum type)
0029 {
0030 }
0031 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag(GLboolean boundaryEdge)
0032 {
0033 }
0034 /*ARGSUSED*/ static void GLAPIENTRY noVertex(void *data)
0035 {
0036 }
0037 /*ARGSUSED*/ static void GLAPIENTRY noEnd(void)
0038 {
0039 }
0040 /*ARGSUSED*/ static void GLAPIENTRY noError(GLenum errnum)
0041 {
0042 }
0043 /*ARGSUSED*/ static void GLAPIENTRY noCombine(GLdouble coords[3], void *data[4], GLfloat weight[4], void **dataOut)
0044 {
0045 }
0046 /*ARGSUSED*/ static void GLAPIENTRY noMesh(GLUmesh *mesh)
0047 {
0048 }
0049 
0050 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData(GLenum type, void *polygonData)
0051 {
0052 }
0053 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData(GLboolean boundaryEdge, void *polygonData)
0054 {
0055 }
0056 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData(void *data, void *polygonData)
0057 {
0058 }
0059 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData(void *polygonData)
0060 {
0061 }
0062 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData(GLenum errnum, void *polygonData)
0063 {
0064 }
0065 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData(GLdouble coords[3], void *data[4], GLfloat weight[4], void **outData,
0066                                                 void *polygonData)
0067 {
0068 }
0069 
0070 /* Half-edges are allocated in pairs (see mesh.c) */
0071 typedef struct
0072 {
0073     GLUhalfEdge e, eSym;
0074 } EdgePair;
0075 
0076 #undef MAX
0077 #define MAX(a, b)      ((a) > (b) ? (a) : (b))
0078 #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), MAX(sizeof(GLUvertex), sizeof(GLUface))))
0079 
0080 GLUtesselator *GLAPIENTRY gluNewTess(void)
0081 {
0082     GLUtesselator *tess;
0083 
0084     /* Only initialize fields which can be changed by the api.  Other fields
0085    * are initialized where they are used.
0086    */
0087 
0088     if (memInit(MAX_FAST_ALLOC) == 0)
0089     {
0090         return 0; /* out of memory */
0091     }
0092     tess = (GLUtesselator *)memAlloc(sizeof(GLUtesselator));
0093     if (tess == NULL)
0094     {
0095         return 0; /* out of memory */
0096     }
0097 
0098     tess->state = T_DORMANT;
0099 
0100     tess->normal[0] = 0;
0101     tess->normal[1] = 0;
0102     tess->normal[2] = 0;
0103 
0104     tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
0105     tess->windingRule  = GLU_TESS_WINDING_ODD;
0106     tess->flagBoundary = FALSE;
0107     tess->boundaryOnly = FALSE;
0108 
0109     tess->callBegin    = &noBegin;
0110     tess->callEdgeFlag = &noEdgeFlag;
0111     tess->callVertex   = &noVertex;
0112     tess->callEnd      = &noEnd;
0113 
0114     tess->callError   = &noError;
0115     tess->callCombine = &noCombine;
0116     tess->callMesh    = &noMesh;
0117 
0118     tess->callBeginData    = &__gl_noBeginData;
0119     tess->callEdgeFlagData = &__gl_noEdgeFlagData;
0120     tess->callVertexData   = &__gl_noVertexData;
0121     tess->callEndData      = &__gl_noEndData;
0122     tess->callErrorData    = &__gl_noErrorData;
0123     tess->callCombineData  = &__gl_noCombineData;
0124 
0125     tess->polygonData = NULL;
0126 
0127     return tess;
0128 }
0129 
0130 static void MakeDormant(GLUtesselator *tess)
0131 {
0132     /* Return the tessellator to its original dormant state. */
0133 
0134     if (tess->mesh != NULL)
0135     {
0136         __gl_meshDeleteMesh(tess->mesh);
0137     }
0138     tess->state    = T_DORMANT;
0139     tess->lastEdge = NULL;
0140     tess->mesh     = NULL;
0141 }
0142 
0143 #define RequireState(tess, s) \
0144     if (tess->state != s)     \
0145     GotoState(tess, s)
0146 
0147 static void GotoState(GLUtesselator *tess, enum TessState newState)
0148 {
0149     while (tess->state != newState)
0150     {
0151         /* We change the current state one level at a time, to get to
0152      * the desired state.
0153      */
0154         if (tess->state < newState)
0155         {
0156             switch (tess->state)
0157             {
0158                 case T_DORMANT:
0159                     CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_BEGIN_POLYGON);
0160                     gluTessBeginPolygon(tess, NULL);
0161                     break;
0162                 case T_IN_POLYGON:
0163                     CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_BEGIN_CONTOUR);
0164                     gluTessBeginContour(tess);
0165                     break;
0166                 default:;
0167             }
0168         }
0169         else
0170         {
0171             switch (tess->state)
0172             {
0173                 case T_IN_CONTOUR:
0174                     CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_END_CONTOUR);
0175                     gluTessEndContour(tess);
0176                     break;
0177                 case T_IN_POLYGON:
0178                     CALL_ERROR_OR_ERROR_DATA(GLU_TESS_MISSING_END_POLYGON);
0179                     /* gluTessEndPolygon( tess ) is too much work! */
0180                     MakeDormant(tess);
0181                     break;
0182                 default:;
0183             }
0184         }
0185     }
0186 }
0187 
0188 void GLAPIENTRY gluDeleteTess(GLUtesselator *tess)
0189 {
0190     RequireState(tess, T_DORMANT);
0191     memFree(tess);
0192 }
0193 
0194 void GLAPIENTRY gluTessProperty(GLUtesselator *tess, GLenum which, GLdouble value)
0195 {
0196     GLenum windingRule;
0197 
0198     switch (which)
0199     {
0200         case GLU_TESS_TOLERANCE:
0201             if (value < 0.0 || value > 1.0)
0202                 break;
0203             tess->relTolerance = value;
0204             return;
0205 
0206         case GLU_TESS_WINDING_RULE:
0207             windingRule = (GLenum)value;
0208             if (windingRule != value)
0209                 break; /* not an integer */
0210 
0211             switch (windingRule)
0212             {
0213                 case GLU_TESS_WINDING_ODD:
0214                 case GLU_TESS_WINDING_NONZERO:
0215                 case GLU_TESS_WINDING_POSITIVE:
0216                 case GLU_TESS_WINDING_NEGATIVE:
0217                 case GLU_TESS_WINDING_ABS_GEQ_TWO:
0218                     tess->windingRule = windingRule;
0219                     return;
0220                 default:
0221                     break;
0222             }
0223 
0224         case GLU_TESS_BOUNDARY_ONLY:
0225             tess->boundaryOnly = (value != 0);
0226             return;
0227 
0228         default:
0229             CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM);
0230             return;
0231     }
0232     CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_VALUE);
0233 }
0234 
0235 /* Returns tessellator property */
0236 void GLAPIENTRY gluGetTessProperty(GLUtesselator *tess, GLenum which, GLdouble *value)
0237 {
0238     switch (which)
0239     {
0240         case GLU_TESS_TOLERANCE:
0241             /* tolerance should be in range [0..1] */
0242             assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
0243             *value = tess->relTolerance;
0244             break;
0245         case GLU_TESS_WINDING_RULE:
0246             assert(tess->windingRule == GLU_TESS_WINDING_ODD || tess->windingRule == GLU_TESS_WINDING_NONZERO ||
0247                    tess->windingRule == GLU_TESS_WINDING_POSITIVE || tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
0248                    tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
0249             *value = tess->windingRule;
0250             break;
0251         case GLU_TESS_BOUNDARY_ONLY:
0252             assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
0253             *value = tess->boundaryOnly;
0254             break;
0255         default:
0256             *value = 0.0;
0257             CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM);
0258             break;
0259     }
0260 } /* gluGetTessProperty() */
0261 
0262 void GLAPIENTRY gluTessNormal(GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z)
0263 {
0264     tess->normal[0] = x;
0265     tess->normal[1] = y;
0266     tess->normal[2] = z;
0267 }
0268 
0269 void GLAPIENTRY gluTessCallback(GLUtesselator *tess, GLenum which, _GLUfuncptr fn)
0270 {
0271     switch (which)
0272     {
0273         case GLU_TESS_BEGIN:
0274             tess->callBegin = (fn == NULL) ? &noBegin : (void(GLAPIENTRY *)(GLenum))fn;
0275             return;
0276         case GLU_TESS_BEGIN_DATA:
0277             tess->callBeginData = (fn == NULL) ? &__gl_noBeginData : (void(GLAPIENTRY *)(GLenum, void *))fn;
0278             return;
0279         case GLU_TESS_EDGE_FLAG:
0280             tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag : (void(GLAPIENTRY *)(GLboolean))fn;
0281             /* If the client wants boundary edges to be flagged,
0282      * we render everything as separate triangles (no strips or fans).
0283      */
0284             tess->flagBoundary = (fn != NULL);
0285             return;
0286         case GLU_TESS_EDGE_FLAG_DATA:
0287             tess->callEdgeFlagData = (fn == NULL) ? &__gl_noEdgeFlagData : (void(GLAPIENTRY *)(GLboolean, void *))fn;
0288             /* If the client wants boundary edges to be flagged,
0289      * we render everything as separate triangles (no strips or fans).
0290      */
0291             tess->flagBoundary = (fn != NULL);
0292             return;
0293         case GLU_TESS_VERTEX:
0294             tess->callVertex = (fn == NULL) ? &noVertex : (void(GLAPIENTRY *)(void *))fn;
0295             return;
0296         case GLU_TESS_VERTEX_DATA:
0297             tess->callVertexData = (fn == NULL) ? &__gl_noVertexData : (void(GLAPIENTRY *)(void *, void *))fn;
0298             return;
0299         case GLU_TESS_END:
0300             tess->callEnd = (fn == NULL) ? &noEnd : (void(GLAPIENTRY *)(void))fn;
0301             return;
0302         case GLU_TESS_END_DATA:
0303             tess->callEndData = (fn == NULL) ? &__gl_noEndData : (void(GLAPIENTRY *)(void *))fn;
0304             return;
0305         case GLU_TESS_ERROR:
0306             tess->callError = (fn == NULL) ? &noError : (void(GLAPIENTRY *)(GLenum))fn;
0307             return;
0308         case GLU_TESS_ERROR_DATA:
0309             tess->callErrorData = (fn == NULL) ? &__gl_noErrorData : (void(GLAPIENTRY *)(GLenum, void *))fn;
0310             return;
0311         case GLU_TESS_COMBINE:
0312             tess->callCombine =
0313                 (fn == NULL) ? &noCombine : (void(GLAPIENTRY *)(GLdouble[3], void * [4], GLfloat[4], void **)) fn;
0314             return;
0315         case GLU_TESS_COMBINE_DATA:
0316             tess->callCombineData = (fn == NULL) ?
0317                                         &__gl_noCombineData :
0318                                         (void(GLAPIENTRY *)(GLdouble[3], void * [4], GLfloat[4], void **, void *)) fn;
0319             return;
0320         case GLU_TESS_MESH:
0321             tess->callMesh = (fn == NULL) ? &noMesh : (void(GLAPIENTRY *)(GLUmesh *))fn;
0322             return;
0323         default:
0324             CALL_ERROR_OR_ERROR_DATA(GLU_INVALID_ENUM);
0325             return;
0326     }
0327 }
0328 
0329 static int AddVertex(GLUtesselator *tess, GLdouble coords[3], void *data)
0330 {
0331     GLUhalfEdge *e;
0332 
0333     e = tess->lastEdge;
0334     if (e == NULL)
0335     {
0336         /* Make a self-loop (one vertex, one edge). */
0337 
0338         e = __gl_meshMakeEdge(tess->mesh);
0339         if (e == NULL)
0340             return 0;
0341         if (!__gl_meshSplice(e, e->Sym))
0342             return 0;
0343     }
0344     else
0345     {
0346         /* Create a new vertex and edge which immediately follow e
0347      * in the ordering around the left face.
0348      */
0349         if (__gl_meshSplitEdge(e) == NULL)
0350             return 0;
0351         e = e->Lnext;
0352     }
0353 
0354     /* The new vertex is now e->Org. */
0355     e->Org->data      = data;
0356     e->Org->coords[0] = coords[0];
0357     e->Org->coords[1] = coords[1];
0358     e->Org->coords[2] = coords[2];
0359 
0360     /* The winding of an edge says how the winding number changes as we
0361    * cross from the edge''s right face to its left face.  We add the
0362    * vertices in such an order that a CCW contour will add +1 to
0363    * the winding number of the region inside the contour.
0364    */
0365     e->winding      = 1;
0366     e->Sym->winding = -1;
0367 
0368     tess->lastEdge = e;
0369 
0370     return 1;
0371 }
0372 
0373 static void CacheVertex(GLUtesselator *tess, GLdouble coords[3], void *data)
0374 {
0375     CachedVertex *v = &tess->cache[tess->cacheCount];
0376 
0377     v->data      = data;
0378     v->coords[0] = coords[0];
0379     v->coords[1] = coords[1];
0380     v->coords[2] = coords[2];
0381     ++tess->cacheCount;
0382 }
0383 
0384 static int EmptyCache(GLUtesselator *tess)
0385 {
0386     CachedVertex *v = tess->cache;
0387     CachedVertex *vLast;
0388 
0389     tess->mesh = __gl_meshNewMesh();
0390     if (tess->mesh == NULL)
0391         return 0;
0392 
0393     for (vLast = v + tess->cacheCount; v < vLast; ++v)
0394     {
0395         if (!AddVertex(tess, v->coords, v->data))
0396             return 0;
0397     }
0398     tess->cacheCount = 0;
0399     tess->emptyCache = FALSE;
0400 
0401     return 1;
0402 }
0403 
0404 void GLAPIENTRY gluTessVertex(GLUtesselator *tess, GLdouble coords[3], void *data)
0405 {
0406     int i, tooLarge = FALSE;
0407     GLdouble x, clamped[3];
0408 
0409     RequireState(tess, T_IN_CONTOUR);
0410 
0411     if (tess->emptyCache)
0412     {
0413         if (!EmptyCache(tess))
0414         {
0415             CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY);
0416             return;
0417         }
0418         tess->lastEdge = NULL;
0419     }
0420     for (i = 0; i < 3; ++i)
0421     {
0422         x = coords[i];
0423         if (x < -GLU_TESS_MAX_COORD)
0424         {
0425             x        = -GLU_TESS_MAX_COORD;
0426             tooLarge = TRUE;
0427         }
0428         if (x > GLU_TESS_MAX_COORD)
0429         {
0430             x        = GLU_TESS_MAX_COORD;
0431             tooLarge = TRUE;
0432         }
0433         clamped[i] = x;
0434     }
0435     if (tooLarge)
0436     {
0437         CALL_ERROR_OR_ERROR_DATA(GLU_TESS_COORD_TOO_LARGE);
0438     }
0439 
0440     if (tess->mesh == NULL)
0441     {
0442         if (tess->cacheCount < TESS_MAX_CACHE)
0443         {
0444             CacheVertex(tess, clamped, data);
0445             return;
0446         }
0447         if (!EmptyCache(tess))
0448         {
0449             CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY);
0450             return;
0451         }
0452     }
0453     if (!AddVertex(tess, clamped, data))
0454     {
0455         CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY);
0456     }
0457 }
0458 
0459 void GLAPIENTRY gluTessBeginPolygon(GLUtesselator *tess, void *data)
0460 {
0461     RequireState(tess, T_DORMANT);
0462 
0463     tess->state      = T_IN_POLYGON;
0464     tess->cacheCount = 0;
0465     tess->emptyCache = FALSE;
0466     tess->mesh       = NULL;
0467 
0468     tess->polygonData = data;
0469 }
0470 
0471 void GLAPIENTRY gluTessBeginContour(GLUtesselator *tess)
0472 {
0473     RequireState(tess, T_IN_POLYGON);
0474 
0475     tess->state    = T_IN_CONTOUR;
0476     tess->lastEdge = NULL;
0477     if (tess->cacheCount > 0)
0478     {
0479         /* Just set a flag so we don't get confused by empty contours
0480      * -- these can be generated accidentally with the obsolete
0481      * NextContour() interface.
0482      */
0483         tess->emptyCache = TRUE;
0484     }
0485 }
0486 
0487 void GLAPIENTRY gluTessEndContour(GLUtesselator *tess)
0488 {
0489     RequireState(tess, T_IN_CONTOUR);
0490     tess->state = T_IN_POLYGON;
0491 }
0492 
0493 void GLAPIENTRY gluTessEndPolygon(GLUtesselator *tess)
0494 {
0495     GLUmesh *mesh;
0496 
0497     if (setjmp(tess->env) != 0)
0498     {
0499         /* come back here if out of memory */
0500         CALL_ERROR_OR_ERROR_DATA(GLU_OUT_OF_MEMORY);
0501         return;
0502     }
0503 
0504     RequireState(tess, T_IN_POLYGON);
0505     tess->state = T_DORMANT;
0506 
0507     if (tess->mesh == NULL)
0508     {
0509         if (!tess->flagBoundary && tess->callMesh == &noMesh)
0510         {
0511             /* Try some special code to make the easy cases go quickly
0512        * (eg. convex polygons).  This code does NOT handle multiple contours,
0513        * intersections, edge flags, and of course it does not generate
0514        * an explicit mesh either.
0515        */
0516             if (__gl_renderCache(tess))
0517             {
0518                 tess->polygonData = NULL;
0519                 return;
0520             }
0521         }
0522         if (!EmptyCache(tess))
0523             longjmp(tess->env, 1); /* could've used a label*/
0524     }
0525 
0526     /* Determine the polygon normal and project vertices onto the plane
0527    * of the polygon.
0528    */
0529     __gl_projectPolygon(tess);
0530 
0531     /* __gl_computeInterior( tess ) computes the planar arrangement specified
0532    * by the given contours, and further subdivides this arrangement
0533    * into regions.  Each region is marked "inside" if it belongs
0534    * to the polygon, according to the rule given by tess->windingRule.
0535    * Each interior region is guaranteed be monotone.
0536    */
0537     if (!__gl_computeInterior(tess))
0538     {
0539         longjmp(tess->env, 1); /* could've used a label */
0540     }
0541 
0542     mesh = tess->mesh;
0543     if (!tess->fatalError)
0544     {
0545         int rc = 1;
0546 
0547         /* If the user wants only the boundary contours, we throw away all edges
0548      * except those which separate the interior from the exterior.
0549      * Otherwise we tessellate all the regions marked "inside".
0550      */
0551         if (tess->boundaryOnly)
0552         {
0553             rc = __gl_meshSetWindingNumber(mesh, 1, TRUE);
0554         }
0555         else
0556         {
0557             rc = __gl_meshTessellateInterior(mesh);
0558         }
0559         if (rc == 0)
0560             longjmp(tess->env, 1); /* could've used a label */
0561 
0562         __gl_meshCheckMesh(mesh);
0563 
0564         if (tess->callBegin != &noBegin || tess->callEnd != &noEnd || tess->callVertex != &noVertex ||
0565             tess->callEdgeFlag != &noEdgeFlag || tess->callBeginData != &__gl_noBeginData ||
0566             tess->callEndData != &__gl_noEndData || tess->callVertexData != &__gl_noVertexData ||
0567             tess->callEdgeFlagData != &__gl_noEdgeFlagData)
0568         {
0569             if (tess->boundaryOnly)
0570             {
0571                 __gl_renderBoundary(tess, mesh); /* output boundary contours */
0572             }
0573             else
0574             {
0575                 __gl_renderMesh(tess, mesh); /* output strips and fans */
0576             }
0577         }
0578         if (tess->callMesh != &noMesh)
0579         {
0580             /* Throw away the exterior faces, so that all faces are interior.
0581        * This way the user doesn't have to check the "inside" flag,
0582        * and we don't need to even reveal its existence.  It also leaves
0583        * the freedom for an implementation to not generate the exterior
0584        * faces in the first place.
0585        */
0586             __gl_meshDiscardExterior(mesh);
0587             (*tess->callMesh)(mesh); /* user wants the mesh itself */
0588             tess->mesh        = NULL;
0589             tess->polygonData = NULL;
0590             return;
0591         }
0592     }
0593     __gl_meshDeleteMesh(mesh);
0594     tess->polygonData = NULL;
0595     tess->mesh        = NULL;
0596 }
0597 
0598 /*XXXblythe unused function*/
0599 #if 0
0600 void GLAPIENTRY
0601 gluDeleteMesh( GLUmesh *mesh )
0602 {
0603   __gl_meshDeleteMesh( mesh );
0604 }
0605 #endif
0606 
0607 /*******************************************************/
0608 
0609 /* Obsolete calls -- for backward compatibility */
0610 
0611 void GLAPIENTRY gluBeginPolygon(GLUtesselator *tess)
0612 {
0613     gluTessBeginPolygon(tess, NULL);
0614     gluTessBeginContour(tess);
0615 }
0616 
0617 /*ARGSUSED*/
0618 void GLAPIENTRY gluNextContour(GLUtesselator *tess, GLenum type)
0619 {
0620     gluTessEndContour(tess);
0621     gluTessBeginContour(tess);
0622 }
0623 
0624 void GLAPIENTRY gluEndPolygon(GLUtesselator *tess)
0625 {
0626     gluTessEndContour(tess);
0627     gluTessEndPolygon(tess);
0628 }