dlls/glu32/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 <stdarg.h>
  36 #include <assert.h>
  37
  38 #include "windef.h"
  39 #include "winbase.h"
  40
  41 #include "tess.h"
  42 #include "mesh.h"
  43
  44 #define GLU_TESS_DEFAULT_TOLERANCE 0.0
  45 #define GLU_TESS_MESH           100112  /* void (*)(GLUmesh *mesh)          */
  46
  47 /*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {}
  48 /*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {}
  49 /*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {}
  50 /*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {}
  51 /*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {}
  52 /*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4],
  53                                     GLfloat weight[4], void **dataOut ) {}
  54 /*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {}
  55
  56
  57 /*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type,
  58                                              void *polygonData ) {}
  59 /*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge,
  60                                        void *polygonData ) {}
  61 /*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data,
  62                                               void *polygonData ) {}
  63 /*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {}
  64 /*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum,
  65                                              void *polygonData ) {}
  66 /*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3],
  67                                                void *data[4],
  68                                                GLfloat weight[4],
  69                                                void **outData,
  70                                                void *polygonData ) {}
  71
  72 /* Half-edges are allocated in pairs (see mesh.c) */
  73 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
  74
  75 #undef  MAX
  76 #define MAX(a,b)        ((a) > (b) ? (a) : (b))
  77 #define MAX_FAST_ALLOC  (MAX(sizeof(EdgePair), \
  78                          MAX(sizeof(GLUvertex),sizeof(GLUface))))
  79
  80 /* normal support (used to be in normal.c) */
  81
  82 #define Dot(u,v)        (u[0]*v[0] + u[1]*v[1] + u[2]*v[2])
  83
  84 #undef  ABS
  85 #define ABS(x)  ((x) < 0 ? -(x) : (x))
  86
  87 static int LongAxis( GLdouble v[3] )
  88 {
  89   int i = 0;
  90
  91   if( ABS(v[1]) > ABS(v[0]) ) { i = 1; }
  92   if( ABS(v[2]) > ABS(v[i]) ) { i = 2; }
  93   return i;
  94 }
  95
  96 static void ComputeNormal( GLUtesselator *tess, GLdouble norm[3] )
  97 {
  98   GLUvertex *v, *v1, *v2;
  99   GLdouble c, tLen2, maxLen2;
 100   GLdouble maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
 101   GLUvertex *maxVert[3], *minVert[3];
 102   GLUvertex *vHead = &tess->mesh->vHead;
 103   int i;
 104
 105   maxVal[0] = maxVal[1] = maxVal[2] = -2 * GLU_TESS_MAX_COORD;
 106   minVal[0] = minVal[1] = minVal[2] = 2 * GLU_TESS_MAX_COORD;
 107
 108   for( v = vHead->next; v != vHead; v = v->next ) {
 109     for( i = 0; i < 3; ++i ) {
 110       c = v->coords[i];
 111       if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; }
 112       if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; }
 113     }
 114   }
 115
 116   /* Find two vertices separated by at least 1/sqrt(3) of the maximum
 117    * distance between any two vertices
 118    */
 119   i = 0;
 120   if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; }
 121   if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; }
 122   if( minVal[i] >= maxVal[i] ) {
 123     /* All vertices are the same -- normal doesn't matter */
 124     norm[0] = 0; norm[1] = 0; norm[2] = 1;
 125     return;
 126   }
 127
 128   /* Look for a third vertex which forms the triangle with maximum area
 129    * (Length of normal == twice the triangle area)
 130    */
 131   maxLen2 = 0;
 132   v1 = minVert[i];
 133   v2 = maxVert[i];
 134   d1[0] = v1->coords[0] - v2->coords[0];
 135   d1[1] = v1->coords[1] - v2->coords[1];
 136   d1[2] = v1->coords[2] - v2->coords[2];
 137   for( v = vHead->next; v != vHead; v = v->next ) {
 138     d2[0] = v->coords[0] - v2->coords[0];
 139     d2[1] = v->coords[1] - v2->coords[1];
 140     d2[2] = v->coords[2] - v2->coords[2];
 141     tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1];
 142     tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2];
 143     tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0];
 144     tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2];
 145     if( tLen2 > maxLen2 ) {
 146       maxLen2 = tLen2;
 147       norm[0] = tNorm[0];
 148       norm[1] = tNorm[1];
 149       norm[2] = tNorm[2];
 150     }
 151   }
 152
 153   if( maxLen2 <= 0 ) {
 154     /* All points lie on a single line -- any decent normal will do */
 155     norm[0] = norm[1] = norm[2] = 0;
 156     norm[LongAxis(d1)] = 1;
 157   }
 158 }
 159
 160
 161 static void CheckOrientation( GLUtesselator *tess )
 162 {
 163   GLdouble area;
 164   GLUface *f, *fHead = &tess->mesh->fHead;
 165   GLUvertex *v, *vHead = &tess->mesh->vHead;
 166   GLUhalfEdge *e;
 167
 168   /* When we compute the normal automatically, we choose the orientation
 169    * so that the sum of the signed areas of all contours is non-negative.
 170    */
 171   area = 0;
 172   for( f = fHead->next; f != fHead; f = f->next ) {
 173     e = f->anEdge;
 174     if( e->winding <= 0 ) continue;
 175     do {
 176       area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t);
 177       e = e->Lnext;
 178     } while( e != f->anEdge );
 179   }
 180   if( area < 0 ) {
 181     /* Reverse the orientation by flipping all the t-coordinates */
 182     for( v = vHead->next; v != vHead; v = v->next ) {
 183       v->t = - v->t;
 184     }
 185     tess->tUnit[0] = - tess->tUnit[0];
 186     tess->tUnit[1] = - tess->tUnit[1];
 187     tess->tUnit[2] = - tess->tUnit[2];
 188   }
 189 }
 190
 191 #if defined(SLANTED_SWEEP)
 192 /* The "feature merging" is not intended to be complete.  There are
 193  * special cases where edges are nearly parallel to the sweep line
 194  * which are not implemented.  The algorithm should still behave
 195  * robustly (ie. produce a reasonable tessellation) in the presence
 196  * of such edges, however it may miss features which could have been
 197  * merged.  We could minimize this effect by choosing the sweep line
 198  * direction to be something unusual (ie. not parallel to one of the
 199  * coordinate axes).
 200  */
 201 #define S_UNIT_X        0.50941539564955385     /* Pre-normalized */
 202 #define S_UNIT_Y        0.86052074622010633
 203 #else
 204 #define S_UNIT_X        1.0
 205 #define S_UNIT_Y        0.0
 206 #endif
 207
 208 /* Determine the polygon normal and project vertices onto the plane
 209  * of the polygon.
 210  */
 211 static void __gl_projectPolygon( GLUtesselator *tess )
 212 {
 213   GLUvertex *v, *vHead = &tess->mesh->vHead;
 214   GLdouble norm[3];
 215   GLdouble *sUnit, *tUnit;
 216   int i, computedNormal = FALSE;
 217
 218   norm[0] = tess->normal[0];
 219   norm[1] = tess->normal[1];
 220   norm[2] = tess->normal[2];
 221   if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
 222     ComputeNormal( tess, norm );
 223     computedNormal = TRUE;
 224   }
 225   sUnit = tess->sUnit;
 226   tUnit = tess->tUnit;
 227   i = LongAxis( norm );
 228
 229   /* Project perpendicular to a coordinate axis -- better numerically */
 230   sUnit[i] = 0;
 231   sUnit[(i+1)%3] = S_UNIT_X;
 232   sUnit[(i+2)%3] = S_UNIT_Y;
 233
 234   tUnit[i] = 0;
 235   tUnit[(i+1)%3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y;
 236   tUnit[(i+2)%3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X;
 237
 238   /* Project the vertices onto the sweep plane */
 239   for( v = vHead->next; v != vHead; v = v->next ) {
 240     v->s = Dot( v->coords, sUnit );
 241     v->t = Dot( v->coords, tUnit );
 242   }
 243   if( computedNormal ) {
 244     CheckOrientation( tess );
 245   }
 246 }
 247
 248
 249 /***********************************************************************
 250  *              gluNewTess (GLU32.@)
 251  */
 252 GLUtesselator * WINAPI gluNewTess(void)
 253 {
 254   GLUtesselator *tess;
 255
 256   /* Only initialize fields which can be changed by the api.  Other fields
 257    * are initialized where they are used.
 258    */
 259
 260   tess = HeapAlloc(GetProcessHeap(), 0, sizeof( GLUtesselator ));
 261   if (tess == NULL) {
 262      return 0;                  /* out of memory */
 263   }
 264
 265   tess->state = T_DORMANT;
 266
 267   tess->normal[0] = 0;
 268   tess->normal[1] = 0;
 269   tess->normal[2] = 0;
 270
 271   tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE;
 272   tess->windingRule = GLU_TESS_WINDING_ODD;
 273   tess->flagBoundary = FALSE;
 274   tess->boundaryOnly = FALSE;
 275
 276   tess->callBegin = &noBegin;
 277   tess->callEdgeFlag = &noEdgeFlag;
 278   tess->callVertex = &noVertex;
 279   tess->callEnd = &noEnd;
 280
 281   tess->callError = &noError;
 282   tess->callCombine = &noCombine;
 283   tess->callMesh = &noMesh;
 284
 285   tess->callBeginData= &__gl_noBeginData;
 286   tess->callEdgeFlagData= &__gl_noEdgeFlagData;
 287   tess->callVertexData= &__gl_noVertexData;
 288   tess->callEndData= &__gl_noEndData;
 289   tess->callErrorData= &__gl_noErrorData;
 290   tess->callCombineData= &__gl_noCombineData;
 291
 292   tess->polygonData= NULL;
 293
 294   return tess;
 295 }
 296
 297 static void MakeDormant( GLUtesselator *tess )
 298 {
 299   /* Return the tessellator to its original dormant state. */
 300
 301   if( tess->mesh != NULL ) {
 302     __gl_meshDeleteMesh( tess->mesh );
 303   }
 304   tess->state = T_DORMANT;
 305   tess->lastEdge = NULL;
 306   tess->mesh = NULL;
 307 }
 308
 309 #define RequireState( tess, s )   if( tess->state != s ) GotoState(tess,s)
 310
 311 static void GotoState( GLUtesselator *tess, enum TessState newState )
 312 {
 313   while( tess->state != newState ) {
 314     /* We change the current state one level at a time, to get to
 315      * the desired state.
 316      */
 317     if( tess->state < newState ) {
 318       switch( tess->state ) {
 319       case T_DORMANT:
 320         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON );
 321         gluTessBeginPolygon( tess, NULL );
 322         break;
 323       case T_IN_POLYGON:
 324         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR );
 325         gluTessBeginContour( tess );
 326         break;
 327       default:
 328          ;
 329       }
 330     } else {
 331       switch( tess->state ) {
 332       case T_IN_CONTOUR:
 333         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR );
 334         gluTessEndContour( tess );
 335         break;
 336       case T_IN_POLYGON:
 337         CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON );
 338         /* gluTessEndPolygon( tess ) is too much work! */
 339         MakeDormant( tess );
 340         break;
 341       default:
 342          ;
 343       }
 344     }
 345   }
 346 }
 347
 348
 349 /***********************************************************************
 350  *              gluDeleteTess (GLU32.@)
 351  */
 352 void WINAPI gluDeleteTess( GLUtesselator *tess )
 353 {
 354   RequireState( tess, T_DORMANT );
 355   HeapFree( GetProcessHeap(), 0, tess );
 356 }
 357
 358
 359 /***********************************************************************
 360  *              gluTessProperty (GLU32.@)
 361  */
 362 void WINAPI gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value )
 363 {
 364   GLenum windingRule;
 365
 366   switch( which ) {
 367   case GLU_TESS_TOLERANCE:
 368     if( value < 0.0 || value > 1.0 ) break;
 369     tess->relTolerance = value;
 370     return;
 371
 372   case GLU_TESS_WINDING_RULE:
 373     windingRule = (GLenum) value;
 374     if( windingRule != value ) break;   /* not an integer */
 375
 376     switch( windingRule ) {
 377     case GLU_TESS_WINDING_ODD:
 378     case GLU_TESS_WINDING_NONZERO:
 379     case GLU_TESS_WINDING_POSITIVE:
 380     case GLU_TESS_WINDING_NEGATIVE:
 381     case GLU_TESS_WINDING_ABS_GEQ_TWO:
 382       tess->windingRule = windingRule;
 383       return;
 384     default:
 385       break;
 386     }
 387
 388   case GLU_TESS_BOUNDARY_ONLY:
 389     tess->boundaryOnly = (value != 0);
 390     return;
 391
 392   default:
 393     CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
 394     return;
 395   }
 396   CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE );
 397 }
 398
 399 /* Returns tessellator property */
 400 /***********************************************************************
 401  *              gluGetTessProperty (GLU32.@)
 402  */
 403 void WINAPI gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value )
 404 {
 405    switch (which) {
 406    case GLU_TESS_TOLERANCE:
 407       /* tolerance should be in range [0..1] */
 408       assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0);
 409       *value= tess->relTolerance;
 410       break;
 411    case GLU_TESS_WINDING_RULE:
 412       assert(tess->windingRule == GLU_TESS_WINDING_ODD ||
 413              tess->windingRule == GLU_TESS_WINDING_NONZERO ||
 414              tess->windingRule == GLU_TESS_WINDING_POSITIVE ||
 415              tess->windingRule == GLU_TESS_WINDING_NEGATIVE ||
 416              tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO);
 417       *value= tess->windingRule;
 418       break;
 419    case GLU_TESS_BOUNDARY_ONLY:
 420       assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE);
 421       *value= tess->boundaryOnly;
 422       break;
 423    default:
 424       *value= 0.0;
 425       CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
 426       break;
 427    }
 428 } /* gluGetTessProperty() */
 429
 430 /***********************************************************************
 431  *              gluTessNormal (GLU32.@)
 432  */
 433 void WINAPI gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z )
 434 {
 435   tess->normal[0] = x;
 436   tess->normal[1] = y;
 437   tess->normal[2] = z;
 438 }
 439
 440 /***********************************************************************
 441  *              gluTessCallback (GLU32.@)
 442  */
 443 void WINAPI gluTessCallback( GLUtesselator *tess, GLenum which, void (CALLBACK *fn)(void))
 444 {
 445   switch( which ) {
 446   case GLU_TESS_BEGIN:
 447     tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn;
 448     return;
 449   case GLU_TESS_BEGIN_DATA:
 450     tess->callBeginData = (fn == NULL) ?
 451         &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
 452     return;
 453   case GLU_TESS_EDGE_FLAG:
 454     tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag :
 455                                         (void (GLAPIENTRY *)(GLboolean)) fn;
 456     /* If the client wants boundary edges to be flagged,
 457      * we render everything as separate triangles (no strips or fans).
 458      */
 459     tess->flagBoundary = (fn != NULL);
 460     return;
 461   case GLU_TESS_EDGE_FLAG_DATA:
 462     tess->callEdgeFlagData= (fn == NULL) ?
 463         &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn;
 464     /* If the client wants boundary edges to be flagged,
 465      * we render everything as separate triangles (no strips or fans).
 466      */
 467     tess->flagBoundary = (fn != NULL);
 468     return;
 469   case GLU_TESS_VERTEX:
 470     tess->callVertex = (fn == NULL) ? &noVertex :
 471                                       (void (GLAPIENTRY *)(void *)) fn;
 472     return;
 473   case GLU_TESS_VERTEX_DATA:
 474     tess->callVertexData = (fn == NULL) ?
 475         &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn;
 476     return;
 477   case GLU_TESS_END:
 478     tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn;
 479     return;
 480   case GLU_TESS_END_DATA:
 481     tess->callEndData = (fn == NULL) ? &__gl_noEndData :
 482                                        (void (GLAPIENTRY *)(void *)) fn;
 483     return;
 484   case GLU_TESS_ERROR:
 485     tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn;
 486     return;
 487   case GLU_TESS_ERROR_DATA:
 488     tess->callErrorData = (fn == NULL) ?
 489         &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn;
 490     return;
 491   case GLU_TESS_COMBINE:
 492     tess->callCombine = (fn == NULL) ? &noCombine :
 493         (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn;
 494     return;
 495   case GLU_TESS_COMBINE_DATA:
 496     tess->callCombineData = (fn == NULL) ? &__gl_noCombineData :
 497                                            (void (GLAPIENTRY *)(GLdouble [3],
 498                                                      void *[4],
 499                                                      GLfloat [4],
 500                                                      void **,
 501                                                      void *)) fn;
 502     return;
 503   case GLU_TESS_MESH:
 504     tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn;
 505     return;
 506   default:
 507     CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM );
 508     return;
 509   }
 510 }
 511
 512 static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
 513 {
 514   GLUhalfEdge *e;
 515
 516   e = tess->lastEdge;
 517   if( e == NULL ) {
 518     /* Make a self-loop (one vertex, one edge). */
 519
 520     e = __gl_meshMakeEdge( tess->mesh );
 521     if (e == NULL) return 0;
 522     if ( !__gl_meshSplice( e, e->Sym ) ) return 0;
 523   } else {
 524     /* Create a new vertex and edge which immediately follow e
 525      * in the ordering around the left face.
 526      */
 527     if (__gl_meshSplitEdge( e ) == NULL) return 0;
 528     e = e->Lnext;
 529   }
 530
 531   /* The new vertex is now e->Org. */
 532   e->Org->data = data;
 533   e->Org->coords[0] = coords[0];
 534   e->Org->coords[1] = coords[1];
 535   e->Org->coords[2] = coords[2];
 536
 537   /* The winding of an edge says how the winding number changes as we
 538    * cross from the edge''s right face to its left face.  We add the
 539    * vertices in such an order that a CCW contour will add +1 to
 540    * the winding number of the region inside the contour.
 541    */
 542   e->winding = 1;
 543   e->Sym->winding = -1;
 544
 545   tess->lastEdge = e;
 546
 547   return 1;
 548 }
 549
 550
 551 static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
 552 {
 553   CachedVertex *v = &tess->cache[tess->cacheCount];
 554
 555   v->data = data;
 556   v->coords[0] = coords[0];
 557   v->coords[1] = coords[1];
 558   v->coords[2] = coords[2];
 559   ++tess->cacheCount;
 560 }
 561
 562
 563 static int EmptyCache( GLUtesselator *tess )
 564 {
 565   CachedVertex *v = tess->cache;
 566   CachedVertex *vLast;
 567
 568   tess->mesh = __gl_meshNewMesh();
 569   if (tess->mesh == NULL) return 0;
 570
 571   for( vLast = v + tess->cacheCount; v < vLast; ++v ) {
 572     if ( !AddVertex( tess, v->coords, v->data ) ) return 0;
 573   }
 574   tess->cacheCount = 0;
 575   tess->emptyCache = FALSE;
 576
 577   return 1;
 578 }
 579
 580
 581 /***********************************************************************
 582  *              gluTessVertex (GLU32.@)
 583  */
 584 void WINAPI gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data )
 585 {
 586   int i, tooLarge = FALSE;
 587   GLdouble x, clamped[3];
 588
 589   RequireState( tess, T_IN_CONTOUR );
 590
 591   if( tess->emptyCache ) {
 592     if ( !EmptyCache( tess ) ) {
 593        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
 594        return;
 595     }
 596     tess->lastEdge = NULL;
 597   }
 598   for( i = 0; i < 3; ++i ) {
 599     x = coords[i];
 600     if( x < - GLU_TESS_MAX_COORD ) {
 601       x = - GLU_TESS_MAX_COORD;
 602       tooLarge = TRUE;
 603     }
 604     if( x > GLU_TESS_MAX_COORD ) {
 605       x = GLU_TESS_MAX_COORD;
 606       tooLarge = TRUE;
 607     }
 608     clamped[i] = x;
 609   }
 610   if( tooLarge ) {
 611     CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE );
 612   }
 613
 614   if( tess->mesh == NULL ) {
 615     if( tess->cacheCount < TESS_MAX_CACHE ) {
 616       CacheVertex( tess, clamped, data );
 617       return;
 618     }
 619     if ( !EmptyCache( tess ) ) {
 620        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
 621        return;
 622     }
 623   }
 624   if ( !AddVertex( tess, clamped, data ) ) {
 625        CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
 626   }
 627 }
 628
 629
 630 /***********************************************************************
 631  *              gluTessBeginPolygon (GLU32.@)
 632  */
 633 void WINAPI gluTessBeginPolygon( GLUtesselator *tess, void *data )
 634 {
 635   RequireState( tess, T_DORMANT );
 636
 637   tess->state = T_IN_POLYGON;
 638   tess->cacheCount = 0;
 639   tess->emptyCache = FALSE;
 640   tess->mesh = NULL;
 641
 642   tess->polygonData= data;
 643 }
 644
 645
 646 /***********************************************************************
 647  *              gluTessBeginContour (GLU32.@)
 648  */
 649 void WINAPI gluTessBeginContour( GLUtesselator *tess )
 650 {
 651   RequireState( tess, T_IN_POLYGON );
 652
 653   tess->state = T_IN_CONTOUR;
 654   tess->lastEdge = NULL;
 655   if( tess->cacheCount > 0 ) {
 656     /* Just set a flag so we don't get confused by empty contours
 657      * -- these can be generated accidentally with the obsolete
 658      * NextContour() interface.
 659      */
 660     tess->emptyCache = TRUE;
 661   }
 662 }
 663
 664
 665 /***********************************************************************
 666  *              gluTessEndContour (GLU32.@)
 667  */
 668 void WINAPI gluTessEndContour( GLUtesselator *tess )
 669 {
 670   RequireState( tess, T_IN_CONTOUR );
 671   tess->state = T_IN_POLYGON;
 672 }
 673
 674 /***********************************************************************
 675  *              gluTessEndPolygon (GLU32.@)
 676  */
 677 void WINAPI gluTessEndPolygon( GLUtesselator *tess )
 678 {
 679   GLUmesh *mesh;
 680
 681   if (setjmp(tess->env) != 0) {
 682      /* come back here if out of memory */
 683      CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY );
 684      return;
 685   }
 686
 687   RequireState( tess, T_IN_POLYGON );
 688   tess->state = T_DORMANT;
 689
 690   if( tess->mesh == NULL ) {
 691     if( ! tess->flagBoundary && tess->callMesh == &noMesh ) {
 692
 693       /* Try some special code to make the easy cases go quickly
 694        * (eg. convex polygons).  This code does NOT handle multiple contours,
 695        * intersections, edge flags, and of course it does not generate
 696        * an explicit mesh either.
 697        */
 698       if( __gl_renderCache( tess )) {
 699         tess->polygonData= NULL;
 700         return;
 701       }
 702     }
 703     if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/
 704   }
 705
 706   /* Determine the polygon normal and project vertices onto the plane
 707    * of the polygon.
 708    */
 709   __gl_projectPolygon( tess );
 710
 711   /* __gl_computeInterior( tess ) computes the planar arrangement specified
 712    * by the given contours, and further subdivides this arrangement
 713    * into regions.  Each region is marked "inside" if it belongs
 714    * to the polygon, according to the rule given by tess->windingRule.
 715    * Each interior region is guaranteed be monotone.
 716    */
 717   if ( !__gl_computeInterior( tess ) ) {
 718      longjmp(tess->env,1);      /* could've used a label */
 719   }
 720
 721   mesh = tess->mesh;
 722   if( ! tess->fatalError ) {
 723     int rc = 1;
 724
 725     /* If the user wants only the boundary contours, we throw away all edges
 726      * except those which separate the interior from the exterior.
 727      * Otherwise we tessellate all the regions marked "inside".
 728      */
 729     if( tess->boundaryOnly ) {
 730       rc = __gl_meshSetWindingNumber( mesh, 1, TRUE );
 731     } else {
 732       rc = __gl_meshTessellateInterior( mesh );
 733     }
 734     if (rc == 0) longjmp(tess->env,1);  /* could've used a label */
 735
 736     __gl_meshCheckMesh( mesh );
 737
 738     if( tess->callBegin != &noBegin || tess->callEnd != &noEnd
 739        || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag
 740        || tess->callBeginData != &__gl_noBeginData
 741        || tess->callEndData != &__gl_noEndData
 742        || tess->callVertexData != &__gl_noVertexData
 743        || tess->callEdgeFlagData != &__gl_noEdgeFlagData )
 744     {
 745       if( tess->boundaryOnly ) {
 746         __gl_renderBoundary( tess, mesh );  /* output boundary contours */
 747       } else {
 748         __gl_renderMesh( tess, mesh );     /* output strips and fans */
 749       }
 750     }
 751     if( tess->callMesh != &noMesh ) {
 752
 753       /* Throw away the exterior faces, so that all faces are interior.
 754        * This way the user doesn't have to check the "inside" flag,
 755        * and we don't need to even reveal its existence.  It also leaves
 756        * the freedom for an implementation to not generate the exterior
 757        * faces in the first place.
 758        */
 759       __gl_meshDiscardExterior( mesh );
 760       (*tess->callMesh)( mesh );                /* user wants the mesh itself */
 761       tess->mesh = NULL;
 762       tess->polygonData= NULL;
 763       return;
 764     }
 765   }
 766   __gl_meshDeleteMesh( mesh );
 767   tess->polygonData= NULL;
 768   tess->mesh = NULL;
 769 }
 770
 771
 772 /*XXXblythe unused function*/
 773 #if 0
 774 void GLAPIENTRY
 775 gluDeleteMesh( GLUmesh *mesh )
 776 {
 777   __gl_meshDeleteMesh( mesh );
 778 }
 779 #endif
 780
 781
 782
 783 /*******************************************************/
 784
 785 /* Obsolete calls -- for backward compatibility */
 786
 787 /***********************************************************************
 788  *              gluBeginPolygon (GLU32.@)
 789  */
 790 void WINAPI gluBeginPolygon( GLUtesselator *tess )
 791 {
 792   gluTessBeginPolygon( tess, NULL );
 793   gluTessBeginContour( tess );
 794 }
 795
 796 /***********************************************************************
 797  *              gluNextContour (GLU32.@)
 798  */
 799 void WINAPI gluNextContour( GLUtesselator *tess, GLenum type )
 800 {
 801   gluTessEndContour( tess );
 802   gluTessBeginContour( tess );
 803 }
 804
 805 /***********************************************************************
 806  *              gluEndPolygon (GLU32.@)
 807  */
 808 void WINAPI gluEndPolygon( GLUtesselator *tess )
 809 {
 810   gluTessEndContour( tess );
 811   gluTessEndPolygon( tess );
 812 }