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** $Date$ $Revision$ 39** $Header: //depot/main/gfx/lib/glu/libtess/tess.c#7 $ 40*/ 41 42#include "gluos.h" 43#include <stddef.h> 44#include <assert.h> 45#include <setjmp.h> 46#include "memalloc.h" 47#include "tess.h" 48#include "mesh.h" 49#include "normal.h" 50#include "sweep.h" 51#include "tessmono.h" 52#include "render.h" 53 54#define GLU_TESS_DEFAULT_TOLERANCE 0.0 55#define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */ 56 57#define TRUE 1 58#define FALSE 0 59 60/*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {} 61/*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {} 62/*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {} 63/*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {} 64/*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {} 65/*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4], 66 GLfloat weight[4], void **dataOut ) {} 67/*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {} 68 69 70/*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type, 71 void *polygonData ) {} 72/*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge, 73 void *polygonData ) {} 74/*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data, 75 void *polygonData ) {} 76/*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {} 77/*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum, 78 void *polygonData ) {} 79/*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3], 80 void *data[4], 81 GLfloat weight[4], 82 void **outData, 83 void *polygonData ) {} 84 85/* Half-edges are allocated in pairs (see mesh.c) */ 86typedef struct { GLUhalfEdge e, eSym; } EdgePair; 87 88#define MAX(a,b) ((a) > (b) ? (a) : (b)) 89#define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \ 90 MAX(sizeof(GLUvertex),sizeof(GLUface)))) 91 92 93GLUtesselator * GLAPIENTRY 94gluNewTess( void ) 95{ 96 GLUtesselator *tess; 97 98 /* Only initialize fields which can be changed by the api. Other fields 99 * are initialized where they are used. 100 */ 101 102 if (memInit( MAX_FAST_ALLOC ) == 0) { 103 return 0; /* out of memory */ 104 } 105 tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator )); 106 if (tess == NULL) { 107 return 0; /* out of memory */ 108 } 109 110 tess->state = T_DORMANT; 111 112 tess->normal[0] = 0; 113 tess->normal[1] = 0; 114 tess->normal[2] = 0; 115 116 tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE; 117 tess->windingRule = GLU_TESS_WINDING_ODD; 118 tess->flagBoundary = FALSE; 119 tess->boundaryOnly = FALSE; 120 121 tess->callBegin = &noBegin; 122 tess->callEdgeFlag = &noEdgeFlag; 123 tess->callVertex = &noVertex; 124 tess->callEnd = &noEnd; 125 126 tess->callError = &noError; 127 tess->callCombine = &noCombine; 128 tess->callMesh = &noMesh; 129 130 tess->callBeginData= &__gl_noBeginData; 131 tess->callEdgeFlagData= &__gl_noEdgeFlagData; 132 tess->callVertexData= &__gl_noVertexData; 133 tess->callEndData= &__gl_noEndData; 134 tess->callErrorData= &__gl_noErrorData; 135 tess->callCombineData= &__gl_noCombineData; 136 137 tess->polygonData= NULL; 138 139 return tess; 140} 141 142static void MakeDormant( GLUtesselator *tess ) 143{ 144 /* Return the tessellator to its original dormant state. */ 145 146 if( tess->mesh != NULL ) { 147 __gl_meshDeleteMesh( tess->mesh ); 148 } 149 tess->state = T_DORMANT; 150 tess->lastEdge = NULL; 151 tess->mesh = NULL; 152} 153 154#define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s) 155 156static void GotoState( GLUtesselator *tess, enum TessState newState ) 157{ 158 while( tess->state != newState ) { 159 /* We change the current state one level at a time, to get to 160 * the desired state. 161 */ 162 if( tess->state < newState ) { 163 switch( tess->state ) { 164 case T_DORMANT: 165 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON ); 166 gluTessBeginPolygon( tess, NULL ); 167 break; 168 case T_IN_POLYGON: 169 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR ); 170 gluTessBeginContour( tess ); 171 break; 172 default: 173 assert(0); 174 break; 175 } 176 } else { 177 switch( tess->state ) { 178 case T_IN_CONTOUR: 179 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR ); 180 gluTessEndContour( tess ); 181 break; 182 case T_IN_POLYGON: 183 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON ); 184 /* gluTessEndPolygon( tess ) is too much work! */ 185 MakeDormant( tess ); 186 break; 187 default: 188 assert(0); 189 break; 190 } 191 } 192 } 193} 194 195 196void GLAPIENTRY 197gluDeleteTess( GLUtesselator *tess ) 198{ 199 RequireState( tess, T_DORMANT ); 200 memFree( tess ); 201} 202 203 204void GLAPIENTRY 205gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value ) 206{ 207 GLenum windingRule; 208 209 switch( which ) { 210 case GLU_TESS_TOLERANCE: 211 if( value < 0.0 || value > 1.0 ) break; 212 tess->relTolerance = value; 213 return; 214 215 case GLU_TESS_WINDING_RULE: 216 windingRule = (GLenum) value; 217 if( windingRule != value ) break; /* not an integer */ 218 219 switch( windingRule ) { 220 case GLU_TESS_WINDING_ODD: 221 case GLU_TESS_WINDING_NONZERO: 222 case GLU_TESS_WINDING_POSITIVE: 223 case GLU_TESS_WINDING_NEGATIVE: 224 case GLU_TESS_WINDING_ABS_GEQ_TWO: 225 tess->windingRule = windingRule; 226 return; 227 default: 228 break; 229 } 230 231 case GLU_TESS_BOUNDARY_ONLY: 232 tess->boundaryOnly = (value != 0); 233 return; 234 235 default: 236 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); 237 return; 238 } 239 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE ); 240} 241 242/* Returns tessellator property */ 243void GLAPIENTRY 244gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value ) 245{ 246 switch (which) { 247 case GLU_TESS_TOLERANCE: 248 /* tolerance should be in range [0..1] */ 249 assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0); 250 *value= tess->relTolerance; 251 break; 252 case GLU_TESS_WINDING_RULE: 253 assert(tess->windingRule == GLU_TESS_WINDING_ODD || 254 tess->windingRule == GLU_TESS_WINDING_NONZERO || 255 tess->windingRule == GLU_TESS_WINDING_POSITIVE || 256 tess->windingRule == GLU_TESS_WINDING_NEGATIVE || 257 tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO); 258 *value= tess->windingRule; 259 break; 260 case GLU_TESS_BOUNDARY_ONLY: 261 assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE); 262 *value= tess->boundaryOnly; 263 break; 264 default: 265 *value= 0.0; 266 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); 267 break; 268 } 269} /* gluGetTessProperty() */ 270 271void GLAPIENTRY 272gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z ) 273{ 274 tess->normal[0] = x; 275 tess->normal[1] = y; 276 tess->normal[2] = z; 277} 278 279void GLAPIENTRY 280gluTessCallback( GLUtesselator *tess, GLenum which, void (GLAPIENTRY *fn)()) 281{ 282 switch( which ) { 283 case GLU_TESS_BEGIN: 284 tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn; 285 return; 286 case GLU_TESS_BEGIN_DATA: 287 tess->callBeginData = (fn == NULL) ? 288 &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn; 289 return; 290 case GLU_TESS_EDGE_FLAG: 291 tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag : 292 (void (GLAPIENTRY *)(GLboolean)) 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_EDGE_FLAG_DATA: 299 tess->callEdgeFlagData= (fn == NULL) ? 300 &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn; 301 /* If the client wants boundary edges to be flagged, 302 * we render everything as separate triangles (no strips or fans). 303 */ 304 tess->flagBoundary = (fn != NULL); 305 return; 306 case GLU_TESS_VERTEX: 307 tess->callVertex = (fn == NULL) ? &noVertex : 308 (void (GLAPIENTRY *)(void *)) fn; 309 return; 310 case GLU_TESS_VERTEX_DATA: 311 tess->callVertexData = (fn == NULL) ? 312 &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn; 313 return; 314 case GLU_TESS_END: 315 tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn; 316 return; 317 case GLU_TESS_END_DATA: 318 tess->callEndData = (fn == NULL) ? &__gl_noEndData : 319 (void (GLAPIENTRY *)(void *)) fn; 320 return; 321 case GLU_TESS_ERROR: 322 tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn; 323 return; 324 case GLU_TESS_ERROR_DATA: 325 tess->callErrorData = (fn == NULL) ? 326 &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn; 327 return; 328 case GLU_TESS_COMBINE: 329 tess->callCombine = (fn == NULL) ? &noCombine : 330 (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn; 331 return; 332 case GLU_TESS_COMBINE_DATA: 333 tess->callCombineData = (fn == NULL) ? &__gl_noCombineData : 334 (void (GLAPIENTRY *)(GLdouble [3], 335 void *[4], 336 GLfloat [4], 337 void **, 338 void *)) fn; 339 return; 340 case GLU_TESS_MESH: 341 tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn; 342 return; 343 default: 344 CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); 345 return; 346 } 347} 348 349static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) 350{ 351 GLUhalfEdge *e; 352 353 e = tess->lastEdge; 354 if( e == NULL ) { 355 /* Make a self-loop (one vertex, one edge). */ 356 357 e = __gl_meshMakeEdge( tess->mesh ); 358 if (e == NULL) return 0; 359 if ( !__gl_meshSplice( e, e->Sym ) ) return 0; 360 } else { 361 /* Create a new vertex and edge which immediately follow e 362 * in the ordering around the left face. 363 */ 364 if (__gl_meshSplitEdge( e ) == NULL) return 0; 365 e = e->Lnext; 366 } 367 368 /* The new vertex is now e->Org. */ 369 e->Org->data = data; 370 e->Org->coords[0] = coords[0]; 371 e->Org->coords[1] = coords[1]; 372 e->Org->coords[2] = coords[2]; 373 374 /* The winding of an edge says how the winding number changes as we 375 * cross from the edge''s right face to its left face. We add the 376 * vertices in such an order that a CCW contour will add +1 to 377 * the winding number of the region inside the contour. 378 */ 379 e->winding = 1; 380 e->Sym->winding = -1; 381 382 tess->lastEdge = e; 383 384 return 1; 385} 386 387 388static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) 389{ 390 CachedVertex *v = &tess->cache[tess->cacheCount]; 391 392 v->data = data; 393 v->coords[0] = coords[0]; 394 v->coords[1] = coords[1]; 395 v->coords[2] = coords[2]; 396 ++tess->cacheCount; 397} 398 399 400static int EmptyCache( GLUtesselator *tess ) 401{ 402 CachedVertex *v = tess->cache; 403 CachedVertex *vLast; 404 405 tess->mesh = __gl_meshNewMesh(); 406 if (tess->mesh == NULL) return 0; 407 408 for( vLast = v + tess->cacheCount; v < vLast; ++v ) { 409 if ( !AddVertex( tess, v->coords, v->data ) ) return 0; 410 } 411 tess->cacheCount = 0; 412 tess->emptyCache = FALSE; 413 414 return 1; 415} 416 417 418void GLAPIENTRY 419gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) 420{ 421 int i, tooLarge = FALSE; 422 GLdouble x, clamped[3]; 423 424 RequireState( tess, T_IN_CONTOUR ); 425 426 if( tess->emptyCache ) { 427 if ( !EmptyCache( tess ) ) { 428 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); 429 return; 430 } 431 tess->lastEdge = NULL; 432 } 433 for( i = 0; i < 3; ++i ) { 434 x = coords[i]; 435 if( x < - GLU_TESS_MAX_COORD ) { 436 x = - GLU_TESS_MAX_COORD; 437 tooLarge = TRUE; 438 } 439 if( x > GLU_TESS_MAX_COORD ) { 440 x = GLU_TESS_MAX_COORD; 441 tooLarge = TRUE; 442 } 443 clamped[i] = x; 444 } 445 if( tooLarge ) { 446 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE ); 447 } 448 449 if( tess->mesh == NULL ) { 450 if( tess->cacheCount < TESS_MAX_CACHE ) { 451 CacheVertex( tess, clamped, data ); 452 return; 453 } 454 if ( !EmptyCache( tess ) ) { 455 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); 456 return; 457 } 458 } 459 if ( !AddVertex( tess, clamped, data ) ) { 460 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); 461 } 462} 463 464 465void GLAPIENTRY 466gluTessBeginPolygon( GLUtesselator *tess, void *data ) 467{ 468 RequireState( tess, T_DORMANT ); 469 470 tess->state = T_IN_POLYGON; 471 tess->cacheCount = 0; 472 tess->emptyCache = FALSE; 473 tess->mesh = NULL; 474 475 tess->polygonData= data; 476} 477 478 479void GLAPIENTRY 480gluTessBeginContour( GLUtesselator *tess ) 481{ 482 RequireState( tess, T_IN_POLYGON ); 483 484 tess->state = T_IN_CONTOUR; 485 tess->lastEdge = NULL; 486 if( tess->cacheCount > 0 ) { 487 /* Just set a flag so we don't get confused by empty contours 488 * -- these can be generated accidentally with the obsolete 489 * NextContour() interface. 490 */ 491 tess->emptyCache = TRUE; 492 } 493} 494 495 496void GLAPIENTRY 497gluTessEndContour( GLUtesselator *tess ) 498{ 499 RequireState( tess, T_IN_CONTOUR ); 500 tess->state = T_IN_POLYGON; 501} 502 503void GLAPIENTRY 504gluTessEndPolygon( GLUtesselator *tess ) 505{ 506 GLUmesh *mesh; 507 508 if (setjmp(tess->env) != 0) { 509 /* come back here if out of memory */ 510 CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); 511 return; 512 } 513 514 RequireState( tess, T_IN_POLYGON ); 515 tess->state = T_DORMANT; 516 517 if( tess->mesh == NULL ) { 518 if( ! tess->flagBoundary && tess->callMesh == &noMesh ) { 519 520 /* Try some special code to make the easy cases go quickly 521 * (eg. convex polygons). This code does NOT handle multiple contours, 522 * intersections, edge flags, and of course it does not generate 523 * an explicit mesh either. 524 */ 525 if( __gl_renderCache( tess )) { 526 tess->polygonData= NULL; 527 return; 528 } 529 } 530 if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/ 531 } 532 533 /* Determine the polygon normal and project vertices onto the plane 534 * of the polygon. 535 */ 536 __gl_projectPolygon( tess ); 537 538 /* __gl_computeInterior( tess ) computes the planar arrangement specified 539 * by the given contours, and further subdivides this arrangement 540 * into regions. Each region is marked "inside" if it belongs 541 * to the polygon, according to the rule given by tess->windingRule. 542 * Each interior region is guaranteed be monotone. 543 */ 544 if ( !__gl_computeInterior( tess ) ) { 545 longjmp(tess->env,1); /* could've used a label */ 546 } 547 548 mesh = tess->mesh; 549 if( ! tess->fatalError ) { 550 int rc = 1; 551 552 /* If the user wants only the boundary contours, we throw away all edges 553 * except those which separate the interior from the exterior. 554 * Otherwise we tessellate all the regions marked "inside". 555 */ 556 if( tess->boundaryOnly ) { 557 rc = __gl_meshSetWindingNumber( mesh, 1, TRUE ); 558 } else { 559 rc = __gl_meshTessellateInterior( mesh ); 560 } 561 if (rc == 0) longjmp(tess->env,1); /* could've used a label */ 562 563 __gl_meshCheckMesh( mesh ); 564 565 if( tess->callBegin != &noBegin || tess->callEnd != &noEnd 566 || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag 567 || tess->callBeginData != &__gl_noBeginData 568 || tess->callEndData != &__gl_noEndData 569 || tess->callVertexData != &__gl_noVertexData 570 || tess->callEdgeFlagData != &__gl_noEdgeFlagData ) 571 { 572 if( tess->boundaryOnly ) { 573 __gl_renderBoundary( tess, mesh ); /* output boundary contours */ 574 } else { 575 __gl_renderMesh( tess, mesh ); /* output strips and fans */ 576 } 577 } 578 if( tess->callMesh != &noMesh ) { 579 580 /* Throw away the exterior faces, so that all faces are interior. 581 * This way the user doesn't have to check the "inside" flag, 582 * and we don't need to even reveal its existence. It also leaves 583 * the freedom for an implementation to not generate the exterior 584 * faces in the first place. 585 */ 586 __gl_meshDiscardExterior( mesh ); 587 (*tess->callMesh)( mesh ); /* user wants the mesh itself */ 588 tess->mesh = NULL; 589 tess->polygonData= NULL; 590 return; 591 } 592 } 593 __gl_meshDeleteMesh( mesh ); 594 tess->polygonData= NULL; 595 tess->mesh = NULL; 596} 597 598 599/*XXXblythe unused function*/ 600#if 0 601void GLAPIENTRY 602gluDeleteMesh( GLUmesh *mesh ) 603{ 604 __gl_meshDeleteMesh( mesh ); 605} 606#endif 607 608 609 610/*******************************************************/ 611 612/* Obsolete calls -- for backward compatibility */ 613 614#if 0 615void GLAPIENTRY 616gluBeginPolygon( GLUtesselator *tess ) 617{ 618 gluTessBeginPolygon( tess, NULL ); 619 gluTessBeginContour( tess ); 620} 621 622 623/*ARGSUSED*/ 624void GLAPIENTRY 625gluNextContour( GLUtesselator *tess, GLenum type ) 626{ 627 gluTessEndContour( tess ); 628 gluTessBeginContour( tess ); 629} 630 631 632void GLAPIENTRY 633gluEndPolygon( GLUtesselator *tess ) 634{ 635 gluTessEndContour( tess ); 636 gluTessEndPolygon( tess ); 637} 638#endif 639