src/glu/mesa/tess.c

   1 /* $Id: tess.c,v 1.19 1999/11/04 04:07:57 gareth Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  3.1
   6  *
   7  * Copyright (C) 1999  Brian Paul   All Rights Reserved.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a
  10  * copy of this software and associated documentation files (the "Software"),
  11  * to deal in the Software without restriction, including without limitation
  12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13  * and/or sell copies of the Software, and to permit persons to whom the
  14  * Software is furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included
  17  * in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 /*****************************************************************************
  28  *
  29  * GLU 1.3 Polygon Tessellation by Gareth Hughes <garethh@bell-labs.com>
  30  *
  31  *****************************************************************************/
  32
  33 #include <stdarg.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <GL/glu.h>
  37
  38 #include "tess.h"
  39 #include "tess_macros.h"
  40 #include "tess_fist.h"
  41 #if 0
  42 #include "tess_grid.h"
  43 #endif
  44
  45 /*****************************************************************************
  46  * Internal function prototypes:
  47  *****************************************************************************/
  48
  49 static void init_callbacks( tess_callbacks_t *callbacks );
  50
  51 static void tess_cleanup( GLUtesselator *tobj );
  52 static void inspect_current_contour( GLUtesselator *tobj );
  53
  54 void delete_contour( tess_contour_t **contour );
  55 static void delete_all_contours( GLUtesselator *tobj );
  56
  57 #define TESS_CHECK_ERRORS(t)    if ( (t)->error != GLU_NO_ERROR ) goto cleanup
  58
  59 #ifdef DEBUG
  60 GLint           tess_dbg_level;
  61 #endif
  62
  63
  64 /*****************************************************************************
  65  *
  66  *                      GLU TESSELLATION FUNCTIONS
  67  *
  68  *****************************************************************************/
  69
  70
  71 /*****************************************************************************
  72  * gluNewTess
  73  *****************************************************************************/
  74 GLUtesselator* GLAPIENTRY gluNewTess( void )
  75 {
  76     GLUtesselator *tobj;
  77
  78 #ifdef DEBUG
  79     if ( getenv( "GLU_TESS_DBG_LEVEL" ) ) {
  80         tess_dbg_level = atoi( getenv( "GLU_TESS_DBG_LEVEL" ) );
  81     } else {
  82         tess_dbg_level = DBG_LEVEL_BASE;
  83     }
  84 #endif
  85
  86     MSG( 15, "-> gluNewTess()\n" );
  87
  88     tobj = malloc( sizeof(GLUtesselator) );
  89     if ( tobj == NULL ) {
  90         return NULL;
  91     }
  92
  93     init_callbacks( &tobj->callbacks );
  94
  95     tobj->boundary_only = GL_FALSE;
  96     tobj->winding_rule = GLU_TESS_WINDING_ODD;
  97     tobj->tolerance = 0.0;
  98
  99     tobj->plane.normal[X] = 0.0;
 100     tobj->plane.normal[Y] = 0.0;
 101     tobj->plane.normal[Z] = 0.0;
 102     tobj->plane.dist = 0.0;
 103
 104     tobj->contour_count = 0;
 105     tobj->contours = tobj->last_contour = NULL;
 106     tobj->current_contour = NULL;
 107
 108     CLEAR_BBOX_2DV( tobj->mins, tobj->maxs );
 109
 110     tobj->vertex_count = 0;
 111     tobj->sorted_vertices = NULL;
 112 #if 0
 113     tobj->grid = NULL;
 114 #endif
 115     tobj->cvc_lists = NULL;
 116     tobj->data = NULL;
 117     tobj->edge_flag = GL_FALSE;
 118     tobj->label = 0;
 119
 120     tobj->error = GLU_NO_ERROR;
 121
 122     MSG( 15, "<- gluNewTess() tobj:%p\n", tobj );
 123     return tobj;
 124 }
 125
 126
 127 /*****************************************************************************
 128  * gluDeleteTess
 129  *****************************************************************************/
 130 void GLAPIENTRY gluDeleteTess( GLUtesselator *tobj )
 131 {
 132     MSG( 15, "-> gluDeleteTess( tobj:%p )\n", tobj );
 133
 134     if ( ( tobj->error == GLU_NO_ERROR ) && ( tobj->contour_count > 0 ) )
 135     {
 136         /* gluEndPolygon was not called. */
 137         tess_error_callback( tobj, GLU_TESS_ERROR3 );
 138     }
 139
 140     /* Delete all internal structures. */
 141     tess_cleanup( tobj );
 142     free( tobj );
 143
 144     MSG( 15, "<- gluDeleteTess()\n" );
 145 }
 146
 147
 148 /*****************************************************************************
 149  * gluTessBeginPolygon
 150  *****************************************************************************/
 151 void GLAPIENTRY gluTessBeginPolygon( GLUtesselator *tobj, void *polygon_data )
 152 {
 153     MSG( 15, "-> gluTessBeginPolygon( tobj:%p data:%p )\n", tobj, polygon_data );
 154
 155     tobj->error = GLU_NO_ERROR;
 156
 157     if ( tobj->current_contour != NULL )
 158     {
 159         /* gluEndPolygon was not called. */
 160         tess_error_callback( tobj, GLU_TESS_ERROR3 );
 161         tess_cleanup( tobj );
 162     }
 163
 164     tobj->vertex_count = 0;
 165     tobj->data = polygon_data;
 166     tobj->edge_flag = GL_FALSE;
 167     tobj->label = 0;
 168
 169     MSG( 15, "<- gluTessBeginPolygon( tobj:%p data:%p )\n", tobj, polygon_data );
 170 }
 171
 172
 173 /*****************************************************************************
 174  * gluTessBeginContour
 175  *****************************************************************************/
 176 void GLAPIENTRY gluTessBeginContour( GLUtesselator *tobj )
 177 {
 178     MSG( 15, "  -> gluTessBeginContour( tobj:%p )\n", tobj );
 179     TESS_CHECK_ERRORS( tobj );
 180
 181     if ( tobj->current_contour != NULL )
 182     {
 183         /* gluTessEndContour was not called. */
 184         tess_error_callback( tobj, GLU_TESS_ERROR4 );
 185         return;
 186     }
 187
 188     tobj->current_contour = malloc( sizeof(tess_contour_t) );
 189     if ( tobj->current_contour == NULL ) {
 190         tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
 191         return;
 192     }
 193
 194     COPY_3V( tobj->current_contour->plane.normal, tobj->plane.normal );
 195     tobj->current_contour->plane.dist = tobj->plane.dist;
 196
 197     tobj->current_contour->area = 0.0;
 198     tobj->current_contour->orientation = GLU_UNKNOWN;
 199
 200     tobj->current_contour->label = 0;
 201     tobj->current_contour->winding = 0;
 202
 203     tobj->current_contour->rotx = tobj->current_contour->roty = 0.0;
 204
 205     CLEAR_BBOX_2DV( tobj->current_contour->mins,
 206                     tobj->current_contour->maxs );
 207
 208     tobj->current_contour->vertex_count = 0;
 209     tobj->current_contour->vertices =
 210         tobj->current_contour->last_vertex = NULL;
 211
 212     tobj->current_contour->reflex_vertices = NULL;
 213     tobj->current_contour->cross_vertices = hashtable_init( HT_DEFAULT_SIZE );
 214
 215  cleanup:
 216     MSG( 15, "  <- gluTessBeginContour( tobj:%p )\n", tobj );
 217     return;
 218 }
 219
 220
 221 /*****************************************************************************
 222  * gluTessVertex
 223  *****************************************************************************/
 224 void GLAPIENTRY gluTessVertex( GLUtesselator *tobj, GLdouble coords[3],
 225                                void *vertex_data )
 226 {
 227     tess_contour_t              *current = tobj->current_contour;
 228     tess_vertex_t               *last_vertex;
 229
 230     MSG( 15, "    -> gluTessVertex( tobj:%p coords:(%.2f,%.2f,%.2f) )\n", tobj, coords[0], coords[1], coords[2] );
 231     TESS_CHECK_ERRORS( tobj );
 232
 233     if ( current == NULL )
 234     {
 235         /* gluTessBeginContour was not called. */
 236         tess_error_callback( tobj, GLU_TESS_ERROR2 );
 237         return;
 238     }
 239
 240     tobj->vertex_count++;
 241
 242     last_vertex = current->last_vertex;
 243
 244     if ( last_vertex == NULL )
 245     {
 246         last_vertex = malloc( sizeof(tess_vertex_t) );
 247         if ( last_vertex == NULL ) {
 248             tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
 249             return;
 250         }
 251
 252         current->vertices = last_vertex;
 253         current->last_vertex = last_vertex;
 254
 255         last_vertex->index = -1;
 256         last_vertex->data = vertex_data;
 257
 258         last_vertex->coords[X] = coords[X];
 259         last_vertex->coords[Y] = coords[Y];
 260         last_vertex->coords[Z] = coords[Z];
 261
 262         last_vertex->side = 0.0;
 263         last_vertex->label = 0;
 264         last_vertex->mark = 0;
 265
 266         last_vertex->next = NULL;
 267         last_vertex->previous = NULL;
 268
 269         current->vertex_count++;
 270     }
 271     else
 272     {
 273         tess_vertex_t   *vertex;
 274
 275         vertex = malloc( sizeof(tess_vertex_t) );
 276         if ( vertex == NULL ) {
 277             tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
 278             return;
 279         }
 280
 281         vertex->index = -1;
 282         vertex->data = vertex_data;
 283
 284         vertex->coords[X] = coords[X];
 285         vertex->coords[Y] = coords[Y];
 286         vertex->coords[Z] = coords[Z];
 287
 288         vertex->side = 0.0;
 289         vertex->label = 0;
 290         vertex->mark = 0;
 291
 292         vertex->next = NULL;
 293         vertex->previous = last_vertex;
 294
 295         current->vertex_count++;
 296
 297         last_vertex->next = vertex;
 298         current->last_vertex = vertex;
 299     }
 300
 301  cleanup:
 302     MSG( 15, "    <- gluTessVertex( tobj:%p )\n", tobj );
 303     return;
 304 }
 305
 306
 307 /*****************************************************************************
 308  * gluTessEndContour
 309  *****************************************************************************/
 310 void GLAPIENTRY gluTessEndContour( GLUtesselator *tobj )
 311 {
 312     MSG( 15, "  -> gluTessEndContour( tobj:%p )\n", tobj );
 313     TESS_CHECK_ERRORS( tobj );
 314
 315     if ( tobj->current_contour == NULL )
 316     {
 317         /* gluTessBeginContour was not called. */
 318         tess_error_callback( tobj, GLU_TESS_ERROR2 );
 319         return;
 320     }
 321
 322     if ( tobj->current_contour->vertex_count > 0 ) {
 323         inspect_current_contour( tobj );
 324     } else {
 325         delete_contour( &tobj->current_contour );
 326     }
 327
 328  cleanup:
 329     MSG( 15, "  <- gluTessEndContour( tobj:%p )\n", tobj );
 330     return;
 331 }
 332
 333
 334 /*****************************************************************************
 335  * gluTessEndPolygon
 336  *****************************************************************************/
 337 void GLAPIENTRY gluTessEndPolygon( GLUtesselator *tobj )
 338 {
 339     MSG( 15, "-> gluTessEndPolygon( tobj:%p )\n", tobj );
 340     TESS_CHECK_ERRORS( tobj );
 341
 342     if ( tobj->current_contour != NULL )
 343     {
 344         /* gluTessBeginPolygon was not called. */
 345         tess_error_callback( tobj, GLU_TESS_ERROR1 );
 346         return;
 347     }
 348     TESS_CHECK_ERRORS( tobj );
 349
 350     /*
 351      * Ensure we have at least one contour to tessellate.  If we have none,
 352      *  clean up and exit gracefully.
 353      */
 354     if ( tobj->contour_count == 0 ) {
 355         tess_cleanup( tobj );
 356         return;
 357     }
 358
 359     /* Wrap the contour list. */
 360
 361     tobj->last_contour->next = tobj->contours;
 362     tobj->contours->previous = tobj->last_contour;
 363
 364     TESS_CHECK_ERRORS( tobj );
 365
 366     /*
 367      * Before we tessellate the contours, ensure we have the appropriate
 368      *  callbacks registered.  We at least need the begin, vertex and end
 369      *  callbacks to do any meaningful work.
 370      */
 371     if ( ( ( tobj->callbacks.begin != NULL ) ||
 372            ( tobj->callbacks.beginData != NULL ) ) &&
 373          ( ( tobj->callbacks.vertex != NULL ) ||
 374            ( tobj->callbacks.vertexData != NULL ) ) &&
 375          ( ( tobj->callbacks.end != NULL ) ||
 376            ( tobj->callbacks.endData != NULL ) ) )
 377     {
 378         fist_tessellation( tobj );
 379     }
 380
 381  cleanup:
 382     delete_all_contours( tobj );
 383     MSG( 15, "<- gluTessEndPolygon( tobj:%p )\n", tobj );
 384 }
 385
 386
 387 /*****************************************************************************
 388  * gluTessCallback
 389  *****************************************************************************/
 390 void GLAPIENTRY gluTessCallback( GLUtesselator *tobj, GLenum which,
 391                                  void (GLCALLBACK *fn)() )
 392 {
 393     switch ( which )
 394     {
 395         /* Register the begin callbacks. */
 396     case GLU_TESS_BEGIN:
 397         tobj->callbacks.begin = (void (GLCALLBACK*)(GLenum)) fn;
 398         break;
 399     case GLU_TESS_BEGIN_DATA:
 400         tobj->callbacks.beginData = (void (GLCALLBACK*)(GLenum, void *)) fn;
 401         break;
 402
 403         /* Register the edge flag callbacks. */
 404     case GLU_TESS_EDGE_FLAG:
 405         tobj->callbacks.edgeFlag = (void (GLCALLBACK*)(GLboolean)) fn;
 406         break;
 407     case GLU_TESS_EDGE_FLAG_DATA:
 408         tobj->callbacks.edgeFlagData =
 409             (void (GLCALLBACK*)(GLboolean, void *)) fn;
 410         break;
 411
 412         /* Register the vertex callbacks. */
 413     case GLU_TESS_VERTEX:
 414         tobj->callbacks.vertex = (void (GLCALLBACK*)(void *)) fn;
 415         break;
 416     case GLU_TESS_VERTEX_DATA:
 417         tobj->callbacks.vertexData = (void (GLCALLBACK*)(void *, void *)) fn;
 418         break;
 419
 420         /* Register the end callbacks. */
 421     case GLU_TESS_END:
 422         tobj->callbacks.end = (void (GLCALLBACK*)(void)) fn;
 423         break;
 424     case GLU_TESS_END_DATA:
 425         tobj->callbacks.endData = (void (GLCALLBACK*)(void *)) fn;
 426         break;
 427
 428         /* Register the error callbacks. */
 429     case GLU_TESS_ERROR:
 430         tobj->callbacks.error = (void (GLCALLBACK*)(GLenum)) fn;
 431         break;
 432     case GLU_TESS_ERROR_DATA:
 433         tobj->callbacks.errorData = (void (GLCALLBACK*)(GLenum, void *)) fn;
 434         break;
 435
 436         /* Register the combine callbacks. */
 437     case GLU_TESS_COMBINE:
 438         tobj->callbacks.combine =
 439             (void (GLCALLBACK*)(GLdouble[3], void *[4],
 440                                 GLfloat [4], void **)) fn;
 441         break;
 442     case GLU_TESS_COMBINE_DATA:
 443         tobj->callbacks.combineData =
 444             (void (GLCALLBACK*)(GLdouble[3], void *[4], GLfloat [4],
 445                                 void **, void *)) fn;
 446         break;
 447
 448     default:
 449         MSG( 1, "  gluTessCallback( tobj:%p which:%d ) invalid enum\n", tobj, which );
 450         tobj->error = GLU_INVALID_ENUM;
 451         break;
 452     }
 453 }
 454
 455
 456 /*****************************************************************************
 457  * gluTessProperty
 458  *
 459  * Set the current value of the given property.
 460  *****************************************************************************/
 461 void GLAPIENTRY gluTessProperty( GLUtesselator *tobj, GLenum which,
 462                                  GLdouble value )
 463 {
 464     switch ( which )
 465     {
 466     case GLU_TESS_BOUNDARY_ONLY:
 467         tobj->boundary_only = (GLboolean) value;
 468         break;
 469
 470     case GLU_TESS_TOLERANCE:
 471         MSG( 15, "   gluTessProperty( tobj:%p ) tolerance: %0.9f\n", tobj, value );
 472         tobj->tolerance = value;
 473         break;
 474
 475     case GLU_TESS_WINDING_RULE:
 476         tobj->winding_rule = (GLenum) value;
 477         break;
 478
 479     default:
 480         MSG( 1, "   gluTessProperty( tobj:%p which:%d ) invalid enum\n", tobj, which );
 481         tobj->error = GLU_INVALID_ENUM;
 482         break;
 483     }
 484 }
 485
 486
 487 /*****************************************************************************
 488  * gluGetTessProperty
 489  *
 490  * Return the current value of the given property.
 491  *****************************************************************************/
 492 void GLAPIENTRY gluGetTessProperty( GLUtesselator *tobj, GLenum which,
 493                                     GLdouble *value )
 494 {
 495     switch ( which )
 496     {
 497     case GLU_TESS_BOUNDARY_ONLY:
 498         *value = tobj->boundary_only;
 499         break;
 500
 501     case GLU_TESS_TOLERANCE:
 502         *value = tobj->tolerance;
 503         break;
 504
 505     case GLU_TESS_WINDING_RULE:
 506         *value = tobj->winding_rule;
 507         break;
 508
 509     default:
 510         MSG( 1, "   gluGetTessProperty( tobj:%p which:%d ) invalid enum\n", tobj, which );
 511         tobj->error = GLU_INVALID_ENUM;
 512         break;
 513     }
 514 }
 515
 516
 517 /*****************************************************************************
 518  * gluTessNormal
 519  *
 520  * Set the current tessellation normal.
 521  *****************************************************************************/
 522 void GLAPIENTRY gluTessNormal( GLUtesselator *tobj, GLdouble x,
 523                                GLdouble y, GLdouble z )
 524 {
 525     MSG( 15, "   gluTessNormal( tobj:%p n:(%.2f,%.2f,%.2f) )\n", tobj, x, y, z );
 526
 527     tobj->plane.normal[X] = x;
 528     tobj->plane.normal[Y] = y;
 529     tobj->plane.normal[Z] = z;
 530 }
 531
 532
 533
 534 /*****************************************************************************
 535  *
 536  *                      OBSOLETE TESSELLATION FUNCTIONS
 537  *
 538  *****************************************************************************/
 539
 540 void GLAPIENTRY gluBeginPolygon( GLUtesselator *tobj )
 541 {
 542     gluTessBeginPolygon( tobj, NULL );
 543     gluTessBeginContour( tobj );
 544 }
 545
 546 void GLAPIENTRY gluNextContour( GLUtesselator *tobj, GLenum type )
 547 {
 548     gluTessEndContour( tobj );
 549     gluTessBeginContour( tobj );
 550 }
 551
 552 void GLAPIENTRY gluEndPolygon( GLUtesselator *tobj )
 553 {
 554     gluTessEndContour( tobj );
 555     gluTessEndPolygon( tobj );
 556 }
 557
 558
 559
 560 /*****************************************************************************
 561  * tess_error_callback
 562  *
 563  * Internal error handler.  Call the user-registered error callback.
 564  *
 565  * 2nd arg changed from 'errno' to 'errnum' since MSVC defines errnum as
 566  *  a macro (of all things) and thus breaks the build -tjump
 567  *****************************************************************************/
 568
 569 void tess_error_callback( GLUtesselator *tobj, GLenum errnum )
 570 {
 571     if ( tobj->error == GLU_NO_ERROR )
 572     {
 573         tobj->error = errnum;
 574     }
 575
 576     if ( tobj->callbacks.errorData != NULL )
 577     {
 578         ( tobj->callbacks.errorData )( errnum, tobj->data );
 579     }
 580     else if ( tobj->callbacks.error != NULL )
 581     {
 582         ( tobj->callbacks.error )( errnum );
 583     }
 584 }
 585
 586
 587
 588 /*****************************************************************************
 589  *
 590  *                              INTERNAL FUNCTIONS
 591  *
 592  *****************************************************************************/
 593
 594
 595 /*****************************************************************************
 596  * init_callbacks
 597  *****************************************************************************/
 598 static void init_callbacks( tess_callbacks_t *callbacks )
 599 {
 600     callbacks->begin        = ( void (GLCALLBACK*)(GLenum) ) NULL;
 601     callbacks->beginData    = ( void (GLCALLBACK*)(GLenum, void *) ) NULL;
 602     callbacks->edgeFlag     = ( void (GLCALLBACK*)(GLboolean) ) NULL;
 603     callbacks->edgeFlagData = ( void (GLCALLBACK*)(GLboolean, void *) ) NULL;
 604     callbacks->vertex       = ( void (GLCALLBACK*)(void *) ) NULL;
 605     callbacks->vertexData   = ( void (GLCALLBACK*)(void *, void *) ) NULL;
 606     callbacks->end          = ( void (GLCALLBACK*)(void) ) NULL;
 607     callbacks->endData      = ( void (GLCALLBACK*)(void *) ) NULL;
 608     callbacks->error        = ( void (GLCALLBACK*)(GLenum) ) NULL;
 609     callbacks->errorData    = ( void (GLCALLBACK*)(GLenum, void *) ) NULL;
 610     callbacks->combine      = ( void (GLCALLBACK*)(GLdouble [3], void *[4],
 611                                                    GLfloat [4], void **) ) NULL;
 612     callbacks->combineData  = ( void (GLCALLBACK*)(GLdouble [3], void *[4],
 613                                                    GLfloat [4], void **,
 614                                                    void *) ) NULL;
 615 }
 616
 617
 618 /*****************************************************************************
 619  * tess_cleanup
 620  *****************************************************************************/
 621 static void tess_cleanup( GLUtesselator *tobj )
 622 {
 623     MSG( 15, "  -> tess_cleanup( tobj:%p )\n", tobj );
 624
 625     if ( tobj->current_contour != NULL ) {
 626         delete_contour( &tobj->current_contour );
 627     }
 628     if ( tobj->contours != NULL ) {
 629         delete_all_contours( tobj );
 630     }
 631
 632     MSG( 15, "  <- tess_cleanup( tobj:%p )\n", tobj );
 633 }
 634
 635
 636 /*****************************************************************************
 637  * inspect_current_contour
 638  *****************************************************************************/
 639 static GLenum   find_normal( GLUtesselator *tobj );
 640 static void     project_current_contour( GLUtesselator *tobj );
 641 static GLenum   save_current_contour( GLUtesselator *tobj );
 642
 643 static void inspect_current_contour( GLUtesselator *tobj )
 644 {
 645     tess_contour_t *current = tobj->current_contour;
 646     GLdouble origin[3] = { 0.0, 0.0, 0.0 };
 647
 648     MSG( 15, "    -> inspect_current_contour( tobj:%p )\n", tobj );
 649
 650     if ( current->vertex_count < 3 )
 651     {
 652         MSG( 15, "         count %d < 3, deleting\n", current->vertex_count );
 653         delete_contour( &tobj->current_contour );
 654         return;
 655     }
 656
 657     current->last_vertex->next = current->vertices;
 658     current->vertices->previous = current->last_vertex;
 659
 660     if ( ( tobj->contours == NULL ) &&
 661          ( COMPARE_3DV( current->plane.normal, origin ) ) )
 662     {
 663         /* We haven't been given a normal, so let's take a guess. */
 664         if ( find_normal( tobj ) == GLU_ERROR ) {
 665             return;
 666         }
 667         COPY_3V( tobj->plane.normal, current->plane.normal );
 668         tobj->plane.dist = current->plane.dist;
 669     }
 670     else
 671     {
 672         MSG( 15, "         normal: (%.2f,%.2f,%.2f)\n", tobj->plane.normal[X], tobj->plane.normal[Y], tobj->plane.normal[Z] );
 673     }
 674
 675     project_current_contour( tobj );
 676
 677     if ( save_current_contour( tobj ) == GLU_ERROR ) {
 678         return;
 679     }
 680
 681     MSG( 15, "    <- inspect_current_contour( tobj:%p )\n", tobj );
 682 }
 683
 684 /*****************************************************************************
 685  * find_normal
 686  *****************************************************************************/
 687 static GLenum find_normal( GLUtesselator *tobj )
 688 {
 689     tess_contour_t      *contour = tobj->current_contour;
 690     tess_vertex_t       *va, *vb, *vc;
 691     GLdouble            a[3], b[3], c[3];
 692
 693     MSG( 15, "      -> find_normal( tobj:%p )\n", tobj );
 694
 695     if ( contour == NULL ) { return GLU_ERROR; }
 696
 697     va = contour->vertices;
 698     vb = va->next;
 699
 700     /* If va and vb are the same point, keep looking for a different vertex. */
 701
 702     while ( COMPARE_3DV( va->coords, vb->coords ) && ( vb != va ) ) {
 703         vb = vb->next;
 704     }
 705
 706     if ( vb == va ) {
 707         /* FIXME: What error is this? */
 708         tess_error_callback( tobj, GLU_TESS_ERROR7 );
 709     }
 710
 711     SUB_3V( a, vb->coords, va->coords );
 712
 713     for ( vc = vb->next; vc != va; vc = vc->next )
 714     {
 715         SUB_3V( b, vc->coords, va->coords );
 716
 717         CROSS3( c, a, b );
 718
 719         if ( ( ABSD( c[X] ) > EQUAL_EPSILON ) ||
 720              ( ABSD( c[Y] ) > EQUAL_EPSILON ) ||
 721              ( ABSD( c[Z] ) > EQUAL_EPSILON ) )
 722         {
 723             COPY_3V( contour->plane.normal, c );
 724             NORMALIZE_3DV( contour->plane.normal );
 725
 726             contour->plane.dist = - DOT3( contour->plane.normal, va->coords );
 727
 728             MSG( 15, "      <- find_normal( tobj:%p ) n: (%.2f,%.2f,%.2f)\n", tobj, contour->plane.normal[X], contour->plane.normal[Y], contour->plane.normal[Z] );
 729             return GLU_NO_ERROR;
 730         }
 731     }
 732     /* FIXME: What error is this? */
 733     tess_error_callback( tobj, GLU_TESS_ERROR7 );
 734
 735     return GLU_ERROR;
 736 }
 737
 738 /*****************************************************************************
 739  * project_current_contour
 740  *****************************************************************************/
 741 static GLdouble twice_contour_area( tess_vertex_t *vertex,
 742                                     tess_vertex_t *last_vertex );
 743
 744 static void project_current_contour( GLUtesselator *tobj )
 745 {
 746     tess_contour_t      *current = tobj->current_contour;
 747     tess_vertex_t       *vertex;
 748     GLdouble            area;
 749     GLdouble            zaxis[3] = { 0.0, 0.0, 1.0 }, znormal[3], xnormal[3];
 750     GLdouble            dot, rotx, roty;
 751     GLuint              i;
 752
 753     MSG( 15, "      -> project_current_contour( tobj:%p )\n", tobj );
 754
 755     if ( current == NULL ) { return; }
 756
 757     /* Rotate the plane normal around the y-axis. */
 758
 759     znormal[X] = current->plane.normal[X];
 760     znormal[Y] = 0.0;
 761     znormal[Z] = current->plane.normal[Z];
 762
 763     dot = DOT3( znormal, zaxis );
 764     current->roty = roty = acos( dot );
 765
 766     /* Rotate the plane normal around the x-axis. */
 767
 768     xnormal[X] = cos( roty ) * znormal[X] - sin( roty ) * znormal[Z];
 769     xnormal[Y] = znormal[Y];
 770     xnormal[Z] = sin( roty ) * znormal[X] + cos( roty ) * znormal[Z];
 771
 772     dot = DOT3( xnormal, zaxis );
 773     current->rotx = rotx = acos( dot );
 774
 775     for ( vertex = current->vertices, i = 0;
 776           i < current->vertex_count; vertex = vertex->next, i++ )
 777     {
 778         tess_plane_t    *plane = &current->plane;
 779         GLdouble        proj[3], yrot[3], xrot[3];
 780
 781         /* FIXME: This needs a cleanup, 'cos I'm sure it's inefficient. */
 782
 783         proj[X] = vertex->coords[X] - plane->dist * plane->normal[X];
 784         proj[Y] = vertex->coords[Y] - plane->dist * plane->normal[Y];
 785         proj[Z] = vertex->coords[Z] - plane->dist * plane->normal[Z];
 786
 787         yrot[X] = cos( roty ) * proj[X] - sin( roty ) * proj[Z];
 788         yrot[Y] = proj[Y];
 789         yrot[Z] = sin( roty ) * proj[X] + cos( roty ) * proj[Z];
 790
 791         xrot[X] = yrot[X];
 792         xrot[Y] = cos( rotx ) * yrot[Y] - sin( rotx ) * yrot[Z];
 793         xrot[Z] = sin( rotx ) * yrot[Y] + cos( rotx ) * yrot[Z];
 794
 795         vertex->v[X] = xrot[X];
 796         vertex->v[Y] = xrot[Y];
 797
 798         ACC_BBOX_2V( vertex->v, tobj->mins, tobj->maxs );
 799         ACC_BBOX_2V( vertex->v, current->mins, current->maxs );
 800     }
 801
 802     area = twice_contour_area( current->vertices,
 803                                current->last_vertex );
 804     if ( area >= 0.0 )
 805     {
 806         current->orientation = GLU_CCW;
 807         current->area = area;
 808     }
 809     else
 810     {
 811         current->orientation = GLU_CW;
 812         current->area = -area;
 813     }
 814
 815     MSG( 15, "      <- project_current_contour( tobj:%p )\n", tobj );
 816 }
 817
 818 /*****************************************************************************
 819  * twice_contour_area
 820  *****************************************************************************/
 821 static GLdouble twice_contour_area( tess_vertex_t *vertex,
 822                                     tess_vertex_t *last_vertex )
 823 {
 824     tess_vertex_t       *next;
 825     GLdouble            area, x, y;
 826
 827     area = 0.0;
 828
 829     x = vertex->v[X];
 830     y = vertex->v[Y];
 831
 832     vertex = vertex->next;
 833
 834     while ( vertex != last_vertex )
 835     {
 836         next = vertex->next;
 837         area +=
 838             (vertex->v[X] - x) * (next->v[Y] - y) -
 839             (vertex->v[Y] - y) * (next->v[X] - x);
 840
 841         vertex = vertex->next;
 842     }
 843     return area;
 844 }
 845
 846
 847 /*****************************************************************************
 848  * save_current_contour
 849  *****************************************************************************/
 850 static GLenum save_current_contour( GLUtesselator *tobj )
 851 {
 852     tess_contour_t      *current = tobj->current_contour;
 853     tess_vertex_t       *vertex;
 854     GLuint                      i;
 855
 856     if ( current == NULL ) { return GLU_ERROR; }
 857
 858     if ( tobj->contours == NULL )
 859     {
 860         tobj->contours = tobj->last_contour = current;
 861         current->next = current->previous = NULL;
 862     }
 863     else
 864     {
 865         current->previous = tobj->last_contour;
 866
 867         tobj->last_contour->next = current;
 868         tobj->last_contour = current;
 869
 870         current->next = NULL;
 871     }
 872
 873     for ( vertex = current->vertices, i = 0;
 874           i < current->vertex_count; vertex = vertex->next, i++ )
 875     {
 876         vertex->shadow_vertex = NULL;
 877         vertex->edge_flag = GL_TRUE;
 878     }
 879
 880     current->type = GLU_UNKNOWN;
 881
 882     tobj->contour_count++;
 883     tobj->current_contour = NULL;
 884
 885     return GLU_NO_ERROR;
 886 }
 887
 888 /*****************************************************************************
 889  * delete_contour
 890  *
 891  * Delete the given contour and set the pointer to NULL.
 892  *****************************************************************************/
 893 void delete_contour( tess_contour_t **contour )
 894 {
 895     tess_vertex_t       *vertex, *next;
 896     GLuint              i;
 897
 898     if ( *contour == NULL ) { return; }
 899
 900     vertex = (*contour)->vertices;
 901
 902     for ( i = 0 ; i < (*contour)->vertex_count ; i++ )
 903     {
 904         next = vertex->next;
 905         free( vertex );
 906         vertex = next;
 907     }
 908
 909     free( *contour );
 910     *contour = NULL;
 911 }
 912
 913 /*****************************************************************************
 914  * delete_all_contours
 915  *****************************************************************************/
 916 static void delete_all_contours( GLUtesselator *tobj )
 917 {
 918     tess_contour_t      *current, *next_contour;
 919     GLuint              i;
 920
 921     if ( tobj->current_contour != NULL ) {
 922         delete_contour( &tobj->current_contour );
 923     }
 924
 925     for ( current = tobj->contours, i = 0 ; i < tobj->contour_count ; i++ )
 926     {
 927         tess_vertex_t   *vertex = current->vertices, *next_vertex;
 928         GLuint          j;
 929
 930         for ( j = 0 ; j < current->vertex_count ; j ++ )
 931         {
 932             next_vertex = vertex->next;
 933             free( vertex );
 934             vertex = next_vertex;
 935         }
 936         next_contour = current->next;
 937
 938         free( current );
 939         current = next_contour;
 940     }
 941
 942     tobj->contour_count = tobj->vertex_count = 0;
 943     tobj->contours = tobj->last_contour = NULL;
 944
 945     CLEAR_BBOX_2DV( tobj->mins, tobj->maxs );
 946
 947     ZERO_3V( tobj->plane.normal );
 948     tobj->plane.dist = 0.0;
 949 }
 950
 951
 952 /*****************************************************************************
 953  * tess_msg
 954  *****************************************************************************/
 955 INLINE void tess_msg( int level, char *format, ... )
 956 {
 957 #ifdef DEBUG
 958     va_list ap;
 959     va_start( ap, format );
 960
 961     if ( level <= tess_dbg_level ) {
 962         /*fprintf( DBG_STREAM, "%9.9s:%d:\t ", __FILE__, __LINE__ );*/
 963         vfprintf( DBG_STREAM, format, ap );
 964         fflush( DBG_STREAM );
 965     }
 966
 967     va_end( ap );
 968 #endif
 969 }