home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src-glu / tess_fist.c < prev    next >
C/C++ Source or Header  |  1999-12-06  |  48KB  |  1,667 lines
  1. /* $Id: tess_fist.c,v 1.21.2.10 1999/12/05 17:22:29 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 - Implementation of FIST algorithm
  30.  *
  31.  * For more info on FIST, see:
  32.  *  http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
  33.  *
  34.  * Gareth Hughes <garethh@bell-labs.com>, April 1999
  35.  *
  36.  *****************************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include <stdlib.h>
  40. #include <math.h>
  41.  
  42. #include "gluP.h"
  43.  
  44. #include "tess.h"
  45. #include "tess_macros.h"
  46. #include "tess_heap.h"
  47. #include "tess_clip.h"
  48. #include "tess_winding.h"
  49. #if 0
  50. #include "tess_grid.h"
  51. #endif
  52. #include "tess_fist.h"
  53.  
  54.  
  55. /*****************************************************************************
  56.  * Internal function prototypes:
  57.  *****************************************************************************/
  58.  
  59. static GLenum remove_coincident_vertices( GLUtesselator *tobj );
  60.  
  61. static GLenum compute_orientations( GLUtesselator *tobj );
  62. static GLenum sort_vertices( GLUtesselator *tobj );
  63. static GLenum transform_build_bridges( GLUtesselator *tobj );
  64. static GLenum classify_angles( GLUtesselator *tobj );
  65. static void classify_vertex( tess_contour_t *contour, tess_vertex_t *vertex,
  66.                  GLenum orientation );
  67. static GLenum tessellate_contours( GLUtesselator *tobj );
  68. static GLenum output_contours( GLUtesselator *tobj );
  69.  
  70. GLdouble point_line_test( GLdouble u[2], GLdouble v[2], GLdouble p[2] );
  71. GLboolean point_triangle_test( tess_vertex_t *triangle, tess_vertex_t *point,
  72.                    GLenum orientation );
  73. GLdouble angle_2dv( GLdouble va[2], GLdouble vb[2], GLdouble vc[2] );
  74.  
  75. static void tess_begin_callback( GLUtesselator *tobj, GLenum mode );
  76. static void tess_vertex_callback( GLUtesselator *tobj, void *vertex_data );
  77. static void tess_end_callback( GLUtesselator *tobj );
  78. static void tess_edgeflag_callback( GLUtesselator *tobj, GLboolean flag );
  79. static void tess_output_triangle( GLUtesselator *tobj, tess_vertex_t *vertex );
  80.  
  81. static void cleanup( GLUtesselator *tobj );
  82.  
  83. void contour_dump( tess_contour_t *contour );
  84.  
  85. extern GLenum tess_clip_polygons( GLUtesselator *tobj );
  86.  
  87. /*****************************************************************************
  88.  * Internal type definitions:
  89.  *****************************************************************************/
  90.  
  91. typedef struct
  92. {
  93.     tess_vertex_t    *vertex;
  94.     GLdouble        dist;
  95. } fist_vecdist_t;
  96.  
  97. #define RV_INSERT(t, r)            \
  98.     hashtable_insert( (t), ((int) r), ((void *) r) )
  99. #define RV_DELETE(t, r)            \
  100.     hashtable_delete( (t), ((int) r) )
  101.  
  102.  
  103. /*****************************************************************************
  104.  *
  105.  *            FAST INDUSTRIAL-STRENGTH TRIANGULATION (FIST)
  106.  *
  107.  *****************************************************************************/
  108.  
  109.  
  110. /*****************************************************************************
  111.  * fist_tessellation
  112.  *
  113.  * The main algorithm.  This is the core triangulation code that implements
  114.  * the Fast Industrial-Strength Triangulation algorithm.
  115.  *****************************************************************************/
  116. GLenum fist_tessellation( GLUtesselator *tobj )
  117. {
  118.     MSG( 5, "  -> fist_tessellation( tobj:%p )\n", tobj );
  119.  
  120. #ifdef DEBUG
  121.     do {
  122.     tess_contour_t    *contour = tobj->contours;
  123.     GLint        i;
  124.  
  125.     for ( i = 0 ; i < tobj->num_contours ; i++ ) {
  126.         contour_dump( contour );
  127.         contour = contour->next;
  128.     }
  129.     } while ( 0 );
  130. #endif
  131.  
  132.     /* Remove zero-length edges. */
  133.     remove_coincident_vertices( tobj );
  134.  
  135.     /*
  136.      * Calculate and add any intersection points, and extract a set of
  137.      * non-intersecting contours.
  138.      */
  139.     tess_clip_polygons( tobj );
  140.  
  141.     /* Sort and renumber the vertices of all the polygons. */
  142.     sort_vertices( tobj );
  143.  
  144.     /* Compute and adjust the orientations of all the polygons. */
  145.     compute_orientations( tobj );
  146.  
  147.     /* Do those fancy calculations for the GLU winding rules. */
  148.     tess_preprocess_contours( tobj );
  149.  
  150. #ifdef DEBUG
  151.     do {
  152.     tess_contour_t    *contour = tobj->contours;
  153.     GLint        i;
  154.  
  155.     for ( i = 0 ; i < tobj->num_contours ; i++ ) {
  156.         contour_dump( contour );
  157.         contour = contour->next;
  158.     }
  159.     } while ( 0 );
  160. #endif
  161.  
  162.     /* Output simple line loops if only the boundary is required. */
  163.     if ( tobj->boundary_only ) {
  164.     output_contours( tobj );
  165.     return tobj->error;
  166.     }
  167.  
  168.     /*
  169.      * Transform multiple polygons into a single polygon by building all
  170.      *  bridges.
  171.      */
  172.     if ( tobj->num_contours > 1 ) {
  173.     transform_build_bridges( tobj );
  174.     }
  175.  
  176.     /* Classify all of the angles of the polygon. */
  177.     classify_angles( tobj );
  178.  
  179.     /* Tessellate all the contours that make up the polygon. */
  180.     tessellate_contours( tobj );
  181.  
  182.     /* Cleanup after tessellation is complete. */
  183.     cleanup( tobj );
  184.  
  185.     MSG( 5, "  <- fist_tessellation( tobj:%p )\n", tobj );
  186.     return tobj->error;
  187. }
  188.  
  189.  
  190. /*****************************************************************************
  191.  * fist_recovery_process
  192.  *
  193.  * The main recovery algorithm.  This is the multi-phase recovery process the
  194.  * FIST algorithm uses when things start going wrong.  It ensures a
  195.  * topologically-valid triangulation is produced, no matter what.
  196.  *****************************************************************************/
  197. GLenum fist_recovery_process( GLUtesselator *tobj, tess_contour_t *contour )
  198. {
  199.     tess_vertex_t    *vertex = contour->vertices;
  200.     GLint        i;
  201.  
  202.     MSG( 5, "  -> fist_recovery_process( tobj:%p c:%p )\n", tobj, contour );
  203.  
  204.     /*
  205.      * We start the multi-phase recovery process by clipping zero area
  206.      *  ears, and ears where a vertex lies on another edge.  This may
  207.      *  get us out of trouble, but if not the hard-core recovery must
  208.      *  take place.
  209.      */
  210.     for ( i = 0 ; i < contour->num_vertices ; i++ )
  211.     {
  212.     if ( vertex->prev->index == vertex->next->index )
  213.     {
  214.         MSG( 5, "       zero area ear: (%d, %d, %d)\n", vertex->prev->index, vertex->index, vertex->next->index );
  215.  
  216.         /* Output the triangle. */
  217.         tess_output_triangle( tobj, vertex );
  218.  
  219.         /* Remove the vertex from the contour as required. */
  220.         vertex->prev->next = vertex->next->next;
  221.         vertex->next->next->prev = vertex->prev;
  222.  
  223.         /* Set the new edge flag. */
  224.         vertex->prev->edge_flag = GL_FALSE;
  225.  
  226.         if ( contour->vertices == vertex ) {
  227.         contour->vertices = vertex->prev;
  228.         }
  229.         contour->num_vertices -= 2;
  230.  
  231.         /*
  232.          * Update the reflex vertex set.  We first need to remove
  233.          *  any entries for the three vertices we have touched,
  234.          *  and then re-classify the two vertices that remain in
  235.          *  the contour.
  236.          */
  237.         RV_DELETE( contour->reflex_vertices, vertex->prev );
  238.         RV_DELETE( contour->reflex_vertices, vertex );
  239.         RV_DELETE( contour->reflex_vertices, vertex->next );
  240.         RV_DELETE( contour->reflex_vertices, vertex->next->next );
  241.  
  242.         classify_vertex( contour, vertex->prev, tobj->orientation );
  243.         classify_vertex( contour, vertex->next->next, tobj->orientation );
  244.  
  245.         free( vertex->next );
  246.         free( vertex );
  247.  
  248.         MSG( 5, "  <- fist_recovery_process( tobj:%p ) okay\n", tobj );
  249.         return GLU_NO_ERROR;
  250.     }
  251.  
  252.     vertex = vertex->next;
  253.     }
  254.  
  255.     /*
  256.      * FIXME: Just output one of the reflex vertices as an ear.
  257.      */
  258. #if 1
  259.     vertex = contour->vertices;
  260.  
  261.     MSG( 5, "       desperate ear: (%d, %d, %d)\n", vertex->prev->index, vertex->index, vertex->next->index );
  262.  
  263.     /* Output the triangle. */
  264.     tess_output_triangle( tobj, vertex );
  265.  
  266.     /* Remove the vertex from the contour as required. */
  267.     vertex->prev->next = vertex->next;
  268.     vertex->next->prev = vertex->prev;
  269.  
  270.     /* Set the new edge flag. */
  271.     vertex->prev->edge_flag = GL_FALSE;
  272.  
  273.     if ( contour->vertices == vertex ) {
  274.     contour->vertices = vertex->prev;
  275.     }
  276.     contour->num_vertices--;
  277.  
  278.     /*
  279.      * Update the reflex vertex set.  We first need to remove
  280.      *  any entries for the three vertices we have touched,
  281.      *  and then re-classify the two vertices that remain in
  282.      *  the contour.
  283.      */
  284.     RV_DELETE( contour->reflex_vertices, vertex->prev );
  285.     RV_DELETE( contour->reflex_vertices, vertex );
  286.     RV_DELETE( contour->reflex_vertices, vertex->next );
  287.  
  288.     classify_vertex( contour, vertex->prev, tobj->orientation );
  289.     classify_vertex( contour, vertex->next, tobj->orientation );
  290.  
  291.     free( vertex );
  292.     
  293.     MSG( 5, "  <- fist_recovery_process( tobj:%p ) okay\n", tobj );
  294.     return GLU_NO_ERROR;
  295. #else
  296.     contour_dump( contour );
  297.  
  298.     /* Report a failure in the recovery process. */
  299.     tess_error_callback( tobj, GLU_TESS_ERROR8 );
  300.  
  301.     MSG( 5, "  <- fist_recovery_process( tobj:%p ) failed!\n", tobj );
  302.     return GLU_ERROR;
  303. #endif
  304. }
  305.  
  306.  
  307.  
  308. /*****************************************************************************
  309.  *
  310.  *                INTERNAL FUNCTIONS
  311.  *
  312.  *****************************************************************************/
  313.  
  314.  
  315. /*****************************************************************************
  316.  * remove_coincident_vertices
  317.  *****************************************************************************/
  318. static GLenum remove_coincident_vertices( GLUtesselator *tobj )
  319. {
  320.     tess_contour_t    *contour = tobj->contours;
  321.     GLint        i;
  322.  
  323.     MSG( 5, "    -> remove_coincident_vertices( tobj:%p )\n", tobj );
  324.  
  325.     for ( i = 0 ; i < tobj->num_contours ; i++ )
  326.     {
  327.     tess_vertex_t    *vertex = contour->vertices;
  328.     GLint        j;
  329.  
  330.     for ( j = 0 ; j < contour->num_vertices ; j++ )
  331.     {
  332.         if ( ( ABSD( vertex->coords[X]
  333.              - vertex->next->coords[X] ) <= tobj->tolerance ) &&
  334.          ( ABSD( vertex->coords[Y]
  335.              - vertex->next->coords[Y] ) <= tobj->tolerance ) &&
  336.          ( ABSD( vertex->coords[Z]
  337.              - vertex->next->coords[Z] ) <= tobj->tolerance ) )
  338.         {
  339.         tess_vertex_t    *coinc = vertex->next;
  340.  
  341.         /* Coincident vertices, so remove one of them. */
  342.         MSG( 5, "         coincident (%.2f,%.2f,%.2f) and (%.2f,%.2f,%.2f) count: %d\n", vertex->coords[X], vertex->coords[Y], vertex->coords[Z], vertex->next->coords[X], vertex->next->coords[Y], vertex->next->coords[Z], contour->num_vertices );
  343.  
  344.         vertex->next = coinc->next;
  345.         coinc->next->prev = vertex;
  346.  
  347.         if ( contour->vertices == coinc ) {
  348.             contour->vertices = vertex;
  349.         }
  350.         if ( contour->last_vertex == coinc ) {
  351.             contour->last_vertex = vertex;
  352.         }
  353.  
  354.         contour->num_vertices--;
  355.         tobj->num_vertices--;
  356.  
  357.         free( coinc );
  358.         }
  359.  
  360.         vertex = vertex->next;
  361.     }
  362.  
  363.     contour = contour->next;
  364.     }
  365.  
  366.     MSG( 5, "    <- remove_coincident_vertices( tobj:%p )\n", tobj );
  367.     return GLU_NO_ERROR;
  368. }
  369.  
  370.  
  371. /*****************************************************************************
  372.  * compute_orientations
  373.  *
  374.  * The orientations of each contour loop previously calculated are inspected
  375.  * and adjusted so that the final triangulation will be CCW with respect to
  376.  * the normal of the triangulation plane.
  377.  *****************************************************************************/
  378. static int compare_contour_areas( const void *c1, const void *c2 );
  379.  
  380. static GLenum compute_orientations( GLUtesselator *tobj )
  381. {
  382.     tess_contour_t    **sorted_contours;
  383.     tess_contour_t    *current;
  384.     GLint        i;
  385.  
  386.     MSG( 15, "    -> compute_orientations( tobj:%p )\n", tobj );
  387.  
  388.     if ( tobj->num_contours > 1 )
  389.     {
  390.     /*
  391.      * If we have multiple contours, sort them by their size to determine
  392.      *  which one is the exterior.  Make sure this exterior contour is
  393.      *  oriented CCW with respect to the tessellation normal, and if it
  394.      *  is not oriented this way reverse all the contours.
  395.      *
  396.      * FIXME: Is this the best place to do this?  I think the winding
  397.      *  rule stuff will work out the exteriour contour better than this.
  398.      */
  399.  
  400.     sorted_contours = (tess_contour_t **)
  401.         malloc( tobj->num_contours * sizeof(tess_contour_t *) );
  402.     if ( sorted_contours == NULL ) {
  403.         tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  404.         return GLU_ERROR;
  405.     }
  406.  
  407.     current = tobj->contours;
  408.     i = 0;
  409.  
  410.     while ( i < tobj->num_contours )
  411.     {
  412.         sorted_contours[ i++ ] = current;
  413.         current = current->next;
  414.     }
  415.  
  416.     /* Sort the contours by their area. */
  417.     qsort( sorted_contours, tobj->num_contours,
  418.            sizeof(tess_contour_t *), compare_contour_areas );
  419.  
  420.     tobj->contours     = sorted_contours[ 0 ];
  421.     tobj->last_contour = sorted_contours[ tobj->num_contours - 1 ];
  422.  
  423.     current = tobj->contours;
  424.  
  425.     for ( i = 1; i < tobj->num_contours; i++ )
  426.     {
  427.         current->next = sorted_contours[ i ];
  428.         sorted_contours[ i ]->prev = current;
  429.  
  430.         current = current->next;
  431.     }
  432.  
  433.     /* Wrap the contour list. */
  434.     tobj->last_contour->next = tobj->contours;
  435.     tobj->contours->prev = tobj->last_contour;
  436.  
  437.     if ( sorted_contours ) {
  438.         free( sorted_contours );
  439.     }
  440.     }
  441.  
  442.     MSG( 15, "    <- compute_orientations( tobj:%p )\n", tobj );
  443.     return GLU_NO_ERROR;
  444. }
  445.  
  446. /*****************************************************************************
  447.  * compare_contour_areas
  448.  *****************************************************************************/
  449. static int compare_contour_areas( const void *c1, const void *c2 )
  450. {
  451.     GLdouble    area1, area2;
  452.  
  453.     area1 = (*((tess_contour_t **) c1))->area;
  454.     area2 = (*((tess_contour_t **) c2))->area;
  455.  
  456.     if ( area1 < area2 ) {
  457.     return 1;
  458.     }
  459.     if ( area1 > area2 ) {
  460.     return -1;
  461.     }
  462.     return 0;
  463. }
  464.  
  465.  
  466. /*****************************************************************************
  467.  * sort_vertices
  468.  *
  469.  * Sort all the vertices from all contours lexicographically, first by
  470.  * x-coordinate, and then by y-coordinate.  Duplicates are removed from this
  471.  * array, so that coincident vertices have the same index in the array.
  472.  *****************************************************************************/
  473. static int compare_vertices( const void *v1, const void *v2 );
  474.  
  475. static GLenum sort_vertices( GLUtesselator *tobj )
  476. {
  477.     tess_contour_t    *current;
  478.     tess_vertex_t    *vertex;
  479.     GLint        i, j, n = 0, num_vertices, removed;
  480.  
  481.     MSG( 15, "    -> sort_vertices( tobj:%p )\n", tobj );
  482.  
  483.     /* Allocate the sorted vertices array. */
  484.  
  485.     tobj->sorted_vertices = (tess_vertex_t **)
  486.     malloc( tobj->num_vertices * sizeof(tess_vertex_t *) );
  487.     if ( tobj->sorted_vertices == NULL ) {
  488.     tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  489.     return GLU_ERROR;
  490.     }
  491.  
  492.     /* Add each vertex from each contour to the array for sorting. */
  493.  
  494.     for ( current = tobj->contours, i = 0;
  495.       i < tobj->num_contours; current = current->next, i++ )
  496.     {
  497.     for ( vertex = current->vertices, j = 0;
  498.           j < current->num_vertices; vertex = vertex->next, j++ )
  499.     {
  500.         tobj->sorted_vertices[ n++ ] = vertex;
  501.     }
  502.     }
  503.  
  504.     /* Sort the array of vertices. */
  505.     qsort( tobj->sorted_vertices, tobj->num_vertices,
  506.        sizeof(tess_vertex_t *), compare_vertices );
  507.  
  508.     tobj->sorted_vertices[0]->index = 0;
  509.  
  510.     num_vertices = tobj->num_vertices;
  511.     removed = 0;
  512.     i = 1;
  513.  
  514.     /*
  515.      * Scan through the array, removing all duplicate entries, and assign
  516.      * each vertex its index in the array.
  517.      */
  518.  
  519.     while ( i < num_vertices )
  520.     {
  521.     tobj->sorted_vertices[ i ] = tobj->sorted_vertices[ i + removed ];
  522.  
  523.     if ( IS_EQUAL_3DV( tobj->sorted_vertices[ i ]->coords,
  524.                tobj->sorted_vertices[ i - 1 ]->coords ) )
  525.     {
  526.         tobj->sorted_vertices[ i ]->index = i - 1;
  527.  
  528.         removed++;
  529.         num_vertices--;
  530.  
  531.         MSG( 25, "         v: (%.2f, %.2f) index: %d\n",
  532.          tobj->sorted_vertices[i]->v[X],
  533.          tobj->sorted_vertices[i]->v[Y],
  534.          tobj->sorted_vertices[i]->index );
  535.     }
  536.     else
  537.     {
  538.         tobj->sorted_vertices[ i ]->index = i;
  539.  
  540.         MSG( 25, "         v: (%.2f, %.2f) index: %d\n",
  541.          tobj->sorted_vertices[i]->v[X],
  542.          tobj->sorted_vertices[i]->v[Y],
  543.          tobj->sorted_vertices[i]->index );
  544.  
  545.         i++;
  546.     }
  547.     }
  548.  
  549.     /*
  550.      * Shuffle each contour around so the head of the vertex list is the
  551.      *  leftmost vertex.
  552.      */
  553.     current = tobj->contours;
  554.  
  555.     for ( i = 0; i < tobj->num_contours; i++ )
  556.     {
  557.     tess_vertex_t    *left = current->vertices;
  558.     tess_vertex_t    *vertex = current->vertices->next;
  559.     GLint        j;
  560.  
  561.     for ( j = 1; j < current->num_vertices; j++ )
  562.     {
  563.         if ( vertex->index < left->index )
  564.         {
  565.         left = vertex;
  566.         }
  567.         vertex = vertex->next;
  568.     }
  569.     current->vertices = left;
  570.     current->last_vertex = left->prev;
  571.  
  572.     current = current->next;
  573.     }
  574.  
  575.     if ( tobj->sorted_vertices != NULL ) {
  576.     free( tobj->sorted_vertices );
  577.     tobj->sorted_vertices = NULL;
  578.     }
  579.  
  580.     MSG( 15, "    <- sort_vertices( tobj:%p )\n", tobj );
  581.     return GLU_NO_ERROR;
  582. }
  583.  
  584. /*****************************************************************************
  585.  * compare_vertices
  586.  *
  587.  * FIXME: Make this faster...  At least it's right now, though.
  588.  *****************************************************************************/
  589. static int compare_vertices( const void *v1, const void *v2 )
  590. {
  591.     tess_vertex_t    *vertex1 = *((tess_vertex_t **) v1);
  592.     tess_vertex_t    *vertex2 = *((tess_vertex_t **) v2);
  593.  
  594.     if ( ! IS_EQUAL( vertex1->v[X], vertex2->v[X] ) )
  595.     {
  596.     return ( vertex1->v[X] > vertex2->v[X] ) ? 1 : -1;
  597.     }
  598.     else
  599.     {
  600.     return ( vertex1->v[Y] > vertex2->v[Y] ) ? 1 : -1;
  601.     }
  602. }
  603.  
  604.  
  605. /*****************************************************************************
  606.  * transform_build_bridges
  607.  *
  608.  * Multiply-connected polygonal areas are transformed into a single degenerate
  609.  * contour by iteratively linking the internal island loops with the outer
  610.  * boundary by means of contour "bridges".  Thus, the triangulation need only
  611.  * deal with a single contour when this process has been completed.
  612.  *****************************************************************************/
  613. static int compare_contour_left_vertices( const void *c1, const void *c2 );
  614. static int compare_vertex_distances( const void *v1, const void *v2 );
  615.  
  616. static GLenum transform_build_bridges( GLUtesselator *tobj )
  617. {
  618.     tess_contour_t    **sorted;
  619.     tess_contour_t    *contour = tobj->contours;
  620.     GLint        i, num_sorted;
  621.  
  622.     MSG( 5, "    -> transform_build_bridges( tobj:%p )\n", tobj );
  623.  
  624.     sorted = (tess_contour_t **)
  625.     malloc( tobj->num_contours * sizeof(tess_contour_t *) );
  626.     if ( sorted == NULL ) {
  627.     tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  628.     return GLU_ERROR;
  629.     }
  630.  
  631.     for ( contour = tobj->contours, num_sorted = 0, i = 0;
  632.       i < tobj->num_contours; contour = contour->next, i++ )
  633.     {
  634.     if ( contour->orientation != tobj->orientation )
  635.     {
  636.         sorted[ num_sorted++ ] = contour;
  637.     }
  638.     }
  639.  
  640.     /* Sort the contours by their leftmost vertices. */
  641.     qsort( sorted, num_sorted, sizeof(tess_contour_t *),
  642.        compare_contour_left_vertices );
  643.  
  644.     for ( i = 0; i < num_sorted; i++ )
  645.     {
  646.     tess_contour_t    *parent = sorted[i]->parent;
  647.     fist_vecdist_t    *closest;
  648.     tess_vertex_t    *vertex, *left_vertex = sorted[i]->vertices;
  649.     tess_vertex_t    *new_edge[2];
  650.     GLint        j, num_closest = 0;
  651.  
  652.     closest = (fist_vecdist_t *)
  653.         malloc( parent->num_vertices * sizeof(fist_vecdist_t) );
  654.     if ( closest == NULL ) {
  655.         tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  656.         return GLU_ERROR;
  657.     }
  658.  
  659.     for ( vertex = parent->vertices, j = 0;
  660.           j < parent->num_vertices; vertex = vertex->next, j++ )
  661.     {
  662.         if ( vertex->index <= left_vertex->index )
  663.         {
  664.         MSG( 5, "         adding %-2d v: %d\n",
  665.              num_closest, vertex->index );
  666.  
  667.         closest[num_closest].vertex = vertex;
  668.         closest[num_closest].dist =
  669.             LEN_SCALAR( vertex->v[X] - left_vertex->v[X],
  670.                 vertex->v[Y] - left_vertex->v[Y] );
  671.         num_closest++;
  672.         }
  673.         else
  674.         {
  675.         MSG( 5, "         not adding v: %d\n", vertex->index );
  676.         }
  677.     }
  678.  
  679.     MSG( 15, "         num closest: %d\n", num_closest );
  680.     for ( j = 0 ; j < num_closest ; j++ ) {
  681.         MSG( 15, "           closest %d: %d\n", j, closest[j].vertex->index );
  682.     }
  683.  
  684.     qsort( closest, num_closest, sizeof(fist_vecdist_t),
  685.            compare_vertex_distances );
  686.  
  687.     /*
  688.      * FIXME:  Check validity of added edge...
  689.      */
  690.  
  691.     MSG( 5, "         left: %d closest: %d\n",
  692.          left_vertex->index, closest[0].vertex->index );
  693.  
  694.     if ( left_vertex->index != closest[0].vertex->index )
  695.     {
  696.         new_edge[0] = (tess_vertex_t *) malloc( sizeof(tess_vertex_t) );
  697.         new_edge[1] = (tess_vertex_t *) malloc( sizeof(tess_vertex_t) );
  698.  
  699.         if ( ( new_edge[0] == NULL ) || ( new_edge[1] == NULL ) ) {
  700.         tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  701.         return GLU_ERROR;
  702.         }
  703.  
  704.         /* FIXME: Describe what the hell is going on in here. */
  705.  
  706.         MEMCPY( new_edge[0], left_vertex, sizeof(tess_vertex_t) );
  707.         MEMCPY( new_edge[1], closest[0].vertex, sizeof(tess_vertex_t) );
  708.  
  709.         new_edge[0]->next = new_edge[1];
  710.         new_edge[1]->prev = new_edge[0];
  711.  
  712.         left_vertex->prev->next = new_edge[0];
  713.         closest[0].vertex->next->prev = new_edge[1];
  714.  
  715.         closest[0].vertex->next = left_vertex;
  716.         left_vertex->prev = closest[0].vertex;
  717.  
  718.         parent->num_vertices += 2 + sorted[ i ]->num_vertices;
  719.     }
  720.     else
  721.     {
  722.         /*
  723.          * The closest and left vertices are coincident, so we don't
  724.          * need to add a new edge.
  725.          */
  726.         left_vertex->prev->next = closest[0].vertex;
  727.         closest[0].vertex->prev->next = left_vertex;
  728.  
  729.         new_edge[0] = left_vertex->prev;
  730.  
  731.         left_vertex->prev = closest[0].vertex->prev;
  732.         closest[0].vertex->prev = new_edge[0];
  733.  
  734.         parent->num_vertices += sorted[ i ]->num_vertices;
  735.     }
  736.  
  737.     sorted[ i ]->prev->next = sorted[ i ]->next;
  738.     sorted[ i ]->next->prev = sorted[ i ]->prev;
  739.  
  740.     if ( sorted[ i ] == tobj->last_contour ) {
  741.         tobj->last_contour = sorted[ i ]->prev;
  742.     }
  743.  
  744.     tobj->num_contours--;
  745.  
  746.     if ( closest ) {
  747.         free( closest );
  748.         closest = NULL;
  749.     }
  750.     if ( sorted[ i ] ) {
  751.         free( sorted[ i ] );
  752.         sorted[ i ] = NULL;
  753.     }
  754.  
  755.     MSG( 5, "         added edges (%d, %d, %d, %d) and (%d, %d, %d, %d)\n", new_edge[0]->prev->index, new_edge[0]->index, new_edge[0]->next->index, new_edge[0]->next->next->index, left_vertex->prev->prev->index, left_vertex->prev->index, left_vertex->index, left_vertex->next->index );
  756.     }
  757.  
  758.     if ( sorted ) {
  759.     free( sorted );
  760.     }
  761.  
  762.     MSG( 5, "    <- transform_build_bridges( tobj:%p ) count: %d\n", tobj, tobj->num_contours );
  763.     return GLU_NO_ERROR;
  764. }
  765.  
  766. /*****************************************************************************
  767.  * compare_contour_left_vertices
  768.  *****************************************************************************/
  769. static int compare_contour_left_vertices( const void *c1, const void *c2 )
  770. {
  771.     tess_vertex_t    *vertex1 = (*((tess_contour_t **) c1))->vertices;
  772.     tess_vertex_t    *vertex2 = (*((tess_contour_t **) c2))->vertices;
  773.  
  774.     return vertex1->index - vertex2->index;
  775. }
  776.  
  777. /*****************************************************************************
  778.  * compare_vertex_distances
  779.  *****************************************************************************/
  780. static int compare_vertex_distances( const void *v1, const void *v2 )
  781. {
  782.     fist_vecdist_t    *vecdist1 = (fist_vecdist_t *) v1;
  783.     fist_vecdist_t    *vecdist2 = (fist_vecdist_t *) v2;
  784.  
  785.     if ( ( vecdist2->dist - vecdist1->dist ) < GLU_TESS_EPSILON ) {
  786.     return 1;
  787.     } else {
  788.     return -1;
  789.     }
  790. }
  791.  
  792.  
  793. /*****************************************************************************
  794.  * classify_angles
  795.  *
  796.  * All the internal angles of the contours are classified as convex or reflex.
  797.  * This enables the geometric hashing that will significantly speed up the
  798.  * triangulation process.
  799.  *****************************************************************************/
  800. static GLenum classify_angles( GLUtesselator *tobj )
  801. {
  802.     tess_contour_t    *contour;
  803.     tess_vertex_t    *vertex;
  804.     GLint        i, j;
  805.  
  806.     MSG( 15, "    -> classify_angles( tobj:%p )\n", tobj );
  807.  
  808.     for ( contour = tobj->contours, i = 0;
  809.       i < tobj->num_contours; contour = contour->next, i++ )
  810.     {
  811.     if ( ! contour->reflex_vertices ) {
  812.         contour->reflex_vertices = hashtable_init( HT_DEFAULT_SIZE );
  813.     }
  814.  
  815.     for ( vertex = contour->vertices, j = 0;
  816.           j < contour->num_vertices; vertex = vertex->next, j++ )
  817.     {
  818.         /*
  819.          * We need to break the classification out of the loops so
  820.          *  we can re-classify the vertices that change when an ear
  821.          *  is clipped.
  822.          */
  823.         classify_vertex( contour, vertex, tobj->orientation );
  824.     }
  825.     }
  826.  
  827.     MSG( 15, "    <- classify_angles( tobj:%p )\n", tobj );
  828.     return GLU_NO_ERROR;
  829. }
  830.  
  831. /*****************************************************************************
  832.  * classify_vertex
  833.  *****************************************************************************/
  834. static void classify_vertex( tess_contour_t *contour, tess_vertex_t *vertex,
  835.                  GLenum orientation )
  836. {
  837.     vertex->side = point_line_test( vertex->prev->v,
  838.                     vertex->v, vertex->next->v );
  839.  
  840.     if ( orientation == GLU_CW ) {
  841.     vertex->side = - vertex->side;
  842.     }
  843.  
  844.     MSG( 5, "         classifying v: %d side: %0.2f\n", vertex->index, vertex->side );
  845.  
  846.     /*
  847.      * We have three cases here:
  848.      *
  849.      *  1) vertex->side > 0  means angle < PI
  850.      *  2) vertex->side == 0 means angle == PI
  851.      *  3) vertex->side < 0  means angle > PI, or reflex
  852.      *
  853.      * So, what we want to grab here are all the vertices with
  854.      *  a 'side' that is less than zero.  We use our epsilon
  855.      *  value to allow for some rounding errors in the calculation
  856.      * FIXME: Is this epsilon value small enough?
  857.      */
  858.     if ( vertex->side < -GLU_TESS_EPSILON ) {
  859.      RV_INSERT( contour->reflex_vertices, vertex );
  860.     }
  861. }
  862.  
  863.  
  864. /*****************************************************************************
  865.  * tessellate_contours
  866.  *
  867.  * Actually perform the ear clipping on the contours.
  868.  *****************************************************************************/
  869. static GLenum determine_ears( GLUtesselator *tobj, tess_contour_t *contour );
  870. static GLboolean earity_test( tess_contour_t *contour, tess_vertex_t *vertex,
  871.                   GLenum orientation );
  872. static GLdouble shape_classifier( tess_vertex_t *vertex );
  873. static heap_elt_t *add_ear_to_heap( heap_t *heap, tess_vertex_t *vertex );
  874. static void cleanup_chain( GLUtesselator *tobj, tess_contour_t *contour,
  875.                tess_vertex_t *vertex );
  876.  
  877. static GLenum tessellate_contours( GLUtesselator *tobj )
  878. {
  879.     tess_contour_t    *contour = tobj->contours;
  880.  
  881.     MSG( 1, "    -> tessellate_contours( tobj:%p )\n", tobj );
  882.  
  883.     if ( tobj->num_contours == 0 )
  884.     {
  885.     MSG( 1, "         no contours, returning...\n" );
  886.     return GLU_NO_ERROR;
  887.     }
  888.  
  889.     /* Break the contour loop into a standard doubly-linked list. */
  890.     tobj->last_contour->next = NULL;
  891.     tobj->contours->prev = NULL;
  892.  
  893.     /*
  894.      * Start outputting the triangles.  At the moment, we just ouput the
  895.      *  ears when we get them.  Could we ouput them in strip order?  It
  896.      *  would be nice, but it really makes the implementation of the
  897.      *  algorithm less general than it is now.  Is the implementation
  898.      *  too general now?  Quite possibly...
  899.      */
  900.     tess_begin_callback( tobj, GL_TRIANGLES );
  901.  
  902.     while ( contour )
  903.     {
  904.     GLboolean    clipped = GL_FALSE;
  905.  
  906.     MSG( 1, "         *** tessellating contour: %d ***\n", contour->vertices->index );
  907.  
  908.     /*
  909.      * Allocate the priority queue for the ears of the polgyon.  We
  910.      *  use a fairly standard implementation of a heap for this queue,
  911.      *  which is sorted by how close an ear is to an equilateral
  912.      *  triangle. This will arguably give a higher-quality tessellation,
  913.      *  at the cost of slightly reduced preformance.
  914.      */
  915.     tobj->ears = heap_init();
  916.  
  917.     determine_ears( tobj, contour );
  918.  
  919.     while ( contour->num_vertices > 3 )
  920.     {
  921.         if ( tobj->ears->size > 0 )
  922.         {
  923.         heap_elt_t    *element = heap_extract_max( tobj->ears );
  924.         heap_elt_t    *next = NULL, *prev = NULL;
  925.         tess_vertex_t    *vertex = HEAP_VERTEX( element );
  926.  
  927.         /* Remove ear from current contour... */
  928.         MSG( 1, "           nv: %2d hs: %d ear: (%d, %d, %d)\n", contour->num_vertices, tobj->ears->size, vertex->prev->index, vertex->index, vertex->next->index );
  929.  
  930.         clipped = GL_TRUE;
  931.  
  932.         /* Output the triangle. */
  933.         tess_output_triangle( tobj, vertex );
  934.  
  935.         /* Remove the vertex from the contour as required. */
  936.         vertex->prev->next = vertex->next;
  937.         vertex->next->prev = vertex->prev;
  938.  
  939.         /*
  940.          * Delete any zero-area ear chains created by the
  941.          * clipping of the current ear.
  942.          */
  943.         if ( ( vertex->next->index == vertex->prev->prev->index ) ||
  944.              ( vertex->prev->index == vertex->next->next->index ) )
  945.         {
  946.             cleanup_chain( tobj, contour, vertex );
  947.             free( element );
  948.             continue;
  949.         }
  950.  
  951.         /* Set the new edge flag. */
  952.         vertex->prev->edge_flag = GL_FALSE;
  953.  
  954.         if ( contour->vertices == vertex ) {
  955.             contour->vertices = vertex->next;
  956.         }
  957.         contour->num_vertices--;
  958.  
  959.         /* Update the ear heap for the previous vertex. */
  960.         if ( element->prev )
  961.         {
  962.             /*
  963.              * An existing entry based on the previous vertex will
  964.              * no longer be valid, so we need to remove it now.
  965.              */
  966.             MSG( 15, "           rem prev ear (%d, %d, %d)\n", vertex->prev->prev->index, vertex->prev->index, vertex->index );
  967.  
  968.             prev = heap_delete( tobj->ears, element->prev->index );
  969.  
  970.             if ( prev )
  971.             {
  972.             /*
  973.              * We can now determine if clipping the current ear
  974.              * will form a new ear based on the previous vertex.
  975.              * If such a new ear is formed, add it to the ear
  976.              * queue.  Otherwise, just clean up.
  977.              */
  978.             if ( earity_test( contour, HEAP_VERTEX( prev ),
  979.                       tobj->orientation ) )
  980.             {
  981.                 prev->value =
  982.                 shape_classifier( HEAP_VERTEX( prev ) );
  983.  
  984.                 heap_insert( tobj->ears, prev );
  985.             }
  986.             else
  987.             {
  988.                 if ( prev->prev ) {
  989.                 prev->prev->next = NULL;
  990.                 }
  991.                 free( prev );
  992.                 prev = NULL;
  993.             }
  994.             }
  995.         }
  996.  
  997.         /* Update the ear heap for the next vertex. */
  998.         if ( element->next )
  999.         {
  1000.             /*
  1001.              * An existing entry based on the next vertex will
  1002.              * no longer be valid, so we need to remove it now.
  1003.              */
  1004.             MSG( 15, "           rem next ear (%d, %d, %d)\n", vertex->index, vertex->next->index, vertex->next->next->index );
  1005.  
  1006.             next = heap_delete( tobj->ears, element->next->index );
  1007.  
  1008.             if ( next )
  1009.             {
  1010.             /*
  1011.              * We can now determine if clipping the current ear
  1012.              * will form a new ear based on the next vertex.  If
  1013.              * such a new ear is formed, add it to the ear queue.
  1014.              * Otherwise, just clean up.
  1015.              */
  1016.             if ( earity_test( contour, HEAP_VERTEX( next ),
  1017.                       tobj->orientation ) )
  1018.             {
  1019.                 next->value =
  1020.                 shape_classifier( HEAP_VERTEX( next ) );
  1021.  
  1022.                 heap_insert( tobj->ears, next );
  1023.             }
  1024.             else
  1025.             {
  1026.                 if ( next->next ) {
  1027.                 next->next->prev = NULL;
  1028.                 }
  1029.                 free( next );
  1030.                 next = NULL;
  1031.             }
  1032.             }
  1033.         }
  1034.  
  1035.         /* Update the previous and next ear queue entries. */
  1036.         if ( prev && next )
  1037.         {
  1038.             prev->next = next;
  1039.             next->prev = prev;
  1040.         }
  1041.         else if ( prev )
  1042.         {
  1043.             prev->next = NULL;
  1044.         }
  1045.         else if ( next )
  1046.         {
  1047.             next->prev = NULL;
  1048.         }
  1049.  
  1050.         /*
  1051.          * Update the reflex vertex set.  We first need to remove
  1052.          *  any entries for the three vertices we have touched,
  1053.          *  and then re-classify the two vertices that remain in
  1054.          *  the contour.
  1055.          */
  1056.         RV_DELETE( contour->reflex_vertices, vertex->prev );
  1057.         RV_DELETE( contour->reflex_vertices, vertex );
  1058.         RV_DELETE( contour->reflex_vertices, vertex->next );
  1059.  
  1060.         classify_vertex( contour, vertex->prev, tobj->orientation );
  1061.         classify_vertex( contour, vertex->next, tobj->orientation );
  1062.  
  1063.         free( vertex );
  1064.         free( element );
  1065.         }
  1066.         else if ( clipped )
  1067.         {
  1068.         clipped = GL_FALSE;
  1069.         determine_ears( tobj, contour );
  1070.         }
  1071.         else
  1072.         {
  1073.         if ( fist_recovery_process( tobj, contour ) == GLU_NO_ERROR )
  1074.         {
  1075.             clipped = GL_TRUE;
  1076.         }
  1077.         else
  1078.         {
  1079.             /* Finish outputting the triangles. */
  1080.             tess_end_callback( tobj );
  1081. #if 0
  1082.             /* Dump the remaining contours as line loops. */
  1083.             output_contours( tobj );
  1084. #endif
  1085.             return GLU_ERROR;
  1086.         }
  1087.         }
  1088.     }
  1089.  
  1090.     if ( contour->num_vertices == 3 )
  1091.     {
  1092.         tess_vertex_t    *vertex = contour->vertices;
  1093.  
  1094.         MSG( 1, "           nv: %2d hs: %d ear: (%d, %d, %d)\n", contour->num_vertices, tobj->ears->size, vertex->prev->index, vertex->index, vertex->next->index );
  1095.  
  1096.         /* Output the last triangle. */
  1097.         tess_output_triangle( tobj, vertex );
  1098.  
  1099.         free( vertex->prev );
  1100.         free( vertex->next );
  1101.         free( vertex );
  1102.     }
  1103.  
  1104.     /* Move on to the next contour. */
  1105.     contour->vertices = NULL;
  1106.     contour->last_vertex = NULL;
  1107.     contour->num_vertices = 0;
  1108.  
  1109.     /* Clean up the potential ear priority queue. */
  1110.     heap_cleanup( &tobj->ears );
  1111.  
  1112.     contour = contour->next;
  1113.     }
  1114.  
  1115.     /* Finish outputting the triangles. */
  1116.     tess_end_callback( tobj );
  1117.  
  1118.     MSG( 1, "    <- tessellate_contours( tobj:%p )\n", tobj );
  1119.     return GLU_NO_ERROR;
  1120. }
  1121.  
  1122. /*****************************************************************************
  1123.  * determine_ears
  1124.  *
  1125.  * Determine the potential ears for the given contour.
  1126.  *****************************************************************************/
  1127. static GLenum determine_ears( GLUtesselator *tobj, tess_contour_t *contour )
  1128. {
  1129.     tess_vertex_t    *vertex = contour->vertices;
  1130.     heap_elt_t        *element = NULL, *prev = NULL, *first = NULL;
  1131.     GLint        i;
  1132.  
  1133.     MSG( 1, "      --> determine_ears( tobj:%p )\n", tobj );
  1134.  
  1135.     contour_dump( contour );
  1136.  
  1137.     for ( i = 0; i < contour->num_vertices; i++ )
  1138.     {
  1139.     if ( earity_test( contour, vertex, tobj->orientation ) )
  1140.     {
  1141.         MSG( 15, "            adding ear: (%d, %d, %d)\n",
  1142.          vertex->prev->index, vertex->index, vertex->next->index );
  1143.  
  1144.         element = add_ear_to_heap( tobj->ears, vertex );
  1145.  
  1146.         if ( element == NULL ) {
  1147.         tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  1148.         return GLU_ERROR;
  1149.         }
  1150.  
  1151.         element->prev = prev;
  1152.  
  1153.         if ( prev ) {
  1154.         prev->next = element;
  1155.         }
  1156.  
  1157.         prev = element;
  1158.  
  1159.         /* Save the first ear */
  1160.         if ( first == NULL ) {
  1161.         first = element;
  1162.         }
  1163.     }
  1164.     else
  1165.     {
  1166.         prev = NULL;
  1167.     }
  1168.  
  1169.     vertex = vertex->next;
  1170.     }
  1171.  
  1172.     /* Wrap the list of ears */
  1173.     if ( first ) {
  1174.     first->prev = prev;
  1175.     }
  1176.     if ( prev ) {
  1177.     prev->next = first;
  1178.     }
  1179.  
  1180.     MSG( 1, "      <-- determine_ears( tobj:%p )\n", tobj );
  1181.     return GLU_NO_ERROR;
  1182. }
  1183.  
  1184. /*****************************************************************************
  1185.  * earity_test
  1186.  *
  1187.  * Is the given vertex part of an ear?  Test all the reflex vertices of the
  1188.  *  contour against the ear, and if none are inside the ear we have a winner.
  1189.  *****************************************************************************/
  1190. static GLboolean earity_test( tess_contour_t *contour, tess_vertex_t *vertex,
  1191.                   GLenum orientation )
  1192. {
  1193.     hashtable_t    *table = contour->reflex_vertices;
  1194.     GLint    i;
  1195.  
  1196.     if ( ( vertex->side < -GLU_TESS_EPSILON ) || ( ! table ) )
  1197.     {
  1198.     return GL_FALSE;
  1199.     }
  1200.     else
  1201.     {
  1202.     for ( i = 0; i < table->size; i++ )
  1203.     {
  1204.         hashtable_elt_t    *elt = table->elements[ i ];
  1205.  
  1206.         while ( elt )
  1207.         {
  1208.         tess_vertex_t    *reflex = (tess_vertex_t *) elt->ptr;
  1209.  
  1210.         if ( point_triangle_test( vertex, reflex, orientation ) ) {
  1211.             return GL_FALSE;
  1212.         }
  1213.  
  1214.         elt = elt->next;
  1215.         }
  1216.     }
  1217.  
  1218.     return GL_TRUE;
  1219.     }
  1220. }
  1221.  
  1222. /*****************************************************************************
  1223.  * shape_classifier
  1224.  *
  1225.  * Return the minimum angle of the triangle made up by vertex, vertex->next
  1226.  *  and vertex->prev.
  1227.  *****************************************************************************/
  1228. static GLdouble shape_classifier( tess_vertex_t *vertex )
  1229. {
  1230.     GLdouble    min, current;
  1231.  
  1232.     min = angle_2dv( vertex->prev->v, vertex->v, vertex->next->v );
  1233.  
  1234.     current = angle_2dv( vertex->v, vertex->next->v, vertex->prev->v );
  1235.     if ( current < min ) { min = current; }
  1236.  
  1237.     current = angle_2dv( vertex->next->v, vertex->prev->v, vertex->v );
  1238.     if ( current < min ) { min = current; }
  1239.  
  1240.     return min;
  1241. }
  1242.  
  1243.  
  1244. /*****************************************************************************
  1245.  * add_ear_to_heap
  1246.  *
  1247.  * Add the ear containing the given vertex to the heap.
  1248.  *****************************************************************************/
  1249. static heap_elt_t *add_ear_to_heap( heap_t *heap, tess_vertex_t *vertex )
  1250. {
  1251.     heap_elt_t    *element;
  1252.  
  1253.     element = (heap_elt_t *) malloc( sizeof(heap_elt_t) );
  1254.     if ( element == NULL ) {
  1255.     return NULL;
  1256.     }
  1257.  
  1258.     element->value = shape_classifier( vertex );
  1259.     element->ptr = (void *) vertex;
  1260.     element->index = 0;
  1261.  
  1262.     element->next = NULL;
  1263.     element->prev = NULL;
  1264.  
  1265.     heap_insert( heap, element );
  1266.  
  1267.     return element;
  1268. }
  1269.  
  1270.  
  1271. /*****************************************************************************
  1272.  * cleanup_chain
  1273.  *
  1274.  * Remove up any zero-area ears created by the clipping of the given vertex.
  1275.  *****************************************************************************/
  1276. static void cleanup_chain( GLUtesselator *tobj, tess_contour_t *contour,
  1277.                tess_vertex_t *vertex )
  1278. {
  1279.     tess_vertex_t    *end;
  1280.     heap_elt_t        *element;
  1281.  
  1282.     MSG( 1, "      --> cleanup_chain( c:%d v:%d )\n", contour->vertices->index, vertex->index );
  1283.  
  1284.     if ( ( vertex->next->index != vertex->prev->prev->index ) &&
  1285.      ( vertex->prev->index != vertex->next->next->index ) )
  1286.     {
  1287.     return;
  1288.     }
  1289.  
  1290.     if ( vertex->next->index == vertex->prev->prev->index )
  1291.     {
  1292.     end = vertex->prev->prev;
  1293.  
  1294.     end->next = vertex->next->next;
  1295.     vertex->next->next->prev = end;
  1296.     }
  1297.     else
  1298.     {
  1299.     end = vertex->next->next;
  1300.  
  1301.     end->prev = vertex->prev->prev;
  1302.     vertex->prev->prev->next = end;
  1303.     }
  1304.  
  1305.     /* Fix the contour's vertex list if required */
  1306.     if ( ( contour->vertices == vertex ) ||
  1307.      ( contour->vertices == vertex->prev ) ||
  1308.      ( contour->vertices == vertex->next ) )
  1309.     {
  1310.     contour->vertices = end;
  1311.     }
  1312.     contour->num_vertices -= 3;
  1313.  
  1314.     /* Remove all entries from the reflex vertex list */
  1315.     RV_DELETE( contour->reflex_vertices, end );
  1316.     RV_DELETE( contour->reflex_vertices, vertex->prev );
  1317.     RV_DELETE( contour->reflex_vertices, vertex );
  1318.     RV_DELETE( contour->reflex_vertices, vertex->next );
  1319.  
  1320.     /* Delete any previously valid ears from the global queue */
  1321.     element = heap_delete_ptr( tobj->ears, vertex->prev );
  1322.     if ( element ) {
  1323.     free( element );
  1324.     }
  1325.     element = heap_delete_ptr( tobj->ears, vertex->next );
  1326.     if ( element ) {
  1327.     free( element );
  1328.     }
  1329.  
  1330.     /* Reclassify the new end vertex */
  1331.     classify_vertex( contour, end, tobj->orientation );
  1332.  
  1333.     MSG( 1, "            free (%d, %d, %d)\n",
  1334.      vertex->prev->index, vertex->index, vertex->next->index );
  1335.  
  1336.     /* Cleanup the zero-area ear */
  1337.     free( vertex->prev );
  1338.     free( vertex->next );
  1339.     free( vertex );
  1340.  
  1341.     vertex = end;
  1342.  
  1343.     /*
  1344.      * If the zero-area ear was the head of a zero-area chain, delete
  1345.      * the entire chain here.
  1346.      */
  1347.     while ( vertex->next->index == vertex->prev->index )
  1348.     {
  1349.     end = vertex->prev;
  1350.  
  1351.     end->next = vertex->next->next;
  1352.     vertex->next->next->prev = end;
  1353.  
  1354.     /* Fix the contour's vertex list if required */
  1355.     if ( ( contour->vertices == vertex ) ||
  1356.          ( contour->vertices == vertex->next ) )
  1357.     {
  1358.         contour->vertices = end;
  1359.     }
  1360.     contour->num_vertices -= 2;
  1361.  
  1362.     /* Remove all entries from the reflex vertex list */
  1363.     RV_DELETE( contour->reflex_vertices, end );
  1364.     RV_DELETE( contour->reflex_vertices, vertex );
  1365.     RV_DELETE( contour->reflex_vertices, vertex->next );
  1366.  
  1367.     /* Delete any previously valid ears from the global queue */
  1368.     element = heap_delete_ptr( tobj->ears, vertex );
  1369.     if ( element ) {
  1370.         free( element );
  1371.     }
  1372.     element = heap_delete_ptr( tobj->ears, vertex->next );
  1373.     if ( element ) {
  1374.         free( element );
  1375.     }
  1376.  
  1377.     /* Reclassify the new end vertex */
  1378.     classify_vertex( contour, end, tobj->orientation );
  1379.  
  1380.     MSG( 1, "            free (%d, %d, %d)\n",
  1381.          vertex->prev->index, vertex->index, vertex->next->index );
  1382.  
  1383.     /* Cleanup the zero-area ear */
  1384.     free( vertex->next );
  1385.     free( vertex );
  1386.  
  1387.     vertex = end;
  1388.     }
  1389.  
  1390.     MSG( 1, "      <-- cleanup_chain( c:%d v:%d )\n", contour->vertices->index, vertex->index );
  1391. }
  1392.  
  1393.  
  1394. /*****************************************************************************
  1395.  * output_contours
  1396.  *
  1397.  * Output the tessellated contours.  Don't think we really need this anymore.
  1398.  *****************************************************************************/
  1399. static GLenum output_contours( GLUtesselator *tobj )
  1400. {
  1401.     tess_contour_t    *contour;
  1402.     tess_vertex_t    *vertex;
  1403.     GLint        i, j;
  1404.  
  1405.     for ( contour = tobj->contours, i = 0;
  1406.       i < tobj->num_contours; contour = contour->next, i++ )
  1407.     {
  1408.     tess_begin_callback( tobj, GL_LINE_LOOP );
  1409.  
  1410.     for ( vertex = contour->vertices, j = 0;
  1411.           j < contour->num_vertices; vertex = vertex->next, j++ )
  1412.     {
  1413.         tess_vertex_callback( tobj, vertex->data );
  1414.     }
  1415.     tess_end_callback( tobj );
  1416.     }
  1417.  
  1418.     return GLU_NO_ERROR;
  1419. }
  1420.  
  1421.  
  1422.  
  1423. /*****************************************************************************
  1424.  * point_line_test
  1425.  *
  1426.  * Return positive if p is on the left of the line segment u -> v, negative
  1427.  * if p is on the right of u -> v, and 0 if p is on u -> v.
  1428.  *****************************************************************************/
  1429. GLdouble point_line_test( GLdouble u[2], GLdouble v[2], GLdouble p[2] )
  1430. {
  1431.     return ( ( u[Y] - v[Y] ) * p[X] +
  1432.          ( v[X] - u[X] ) * p[Y] +
  1433.          ( u[X] * v[Y] - u[Y] * v[X] ) );
  1434. }
  1435.  
  1436. /*****************************************************************************
  1437.  * point_triangle_test
  1438.  *
  1439.  * Determine if the given point is inside the triangle given by the points
  1440.  * triangle, triangle->next and triangle->prev.
  1441.  *****************************************************************************/
  1442. GLboolean point_triangle_test( tess_vertex_t *triangle, tess_vertex_t *point,
  1443.                    GLenum orientation )
  1444. {
  1445.     if ( ( orientation == GLU_CCW ) &&
  1446.      ( point_line_test( triangle->v, triangle->next->v,
  1447.                 point->v ) >= GLU_TESS_EPSILON ) &&
  1448.      ( point_line_test( triangle->next->v, triangle->prev->v,
  1449.                 point->v ) >= GLU_TESS_EPSILON ) &&
  1450.      ( point_line_test( triangle->prev->v, triangle->v,
  1451.                 point->v ) >= GLU_TESS_EPSILON ) )
  1452.     {
  1453.     return GL_TRUE;
  1454.     }
  1455.     else if ( ( orientation == GLU_CW ) &&
  1456.           ( point_line_test( triangle->v, triangle->next->v,
  1457.                  point->v ) <= GLU_TESS_EPSILON ) &&
  1458.           ( point_line_test( triangle->next->v, triangle->prev->v,
  1459.                  point->v ) <= GLU_TESS_EPSILON ) &&
  1460.           ( point_line_test( triangle->prev->v, triangle->v,
  1461.                  point->v ) <= GLU_TESS_EPSILON ) )
  1462.     {
  1463.     return GL_TRUE;
  1464.     }
  1465.     else
  1466.     {
  1467.     return GL_FALSE;
  1468.     }
  1469. }
  1470.  
  1471. /*****************************************************************************
  1472.  * angle_2dv
  1473.  *
  1474.  * Calculate the interior angle between the line segments va->vb and vb->vc.
  1475.  *****************************************************************************/
  1476. GLdouble angle_2dv( GLdouble va[2], GLdouble vb[2], GLdouble vc[2] )
  1477. {
  1478.     GLdouble    u[2], v[2];
  1479.     GLdouble    ret;
  1480.  
  1481.     u[X] = va[X] - vb[X]; u[Y] = va[Y] - vb[Y];
  1482.     v[X] = vc[X] - vb[X]; v[Y] = vc[Y] - vb[Y] ;
  1483.  
  1484.     ret = (GLdouble) ( u[X] * v[X] + u[Y] * v[Y] ) /
  1485.     ( LEN_SCALAR( u[X], u[Y] ) * LEN_SCALAR( v[X], v[Y] ) );
  1486.  
  1487.     return (GLdouble) RAD_TO_DEG( acos( ret ) );
  1488. }
  1489.  
  1490.  
  1491. /*****************************************************************************
  1492.  *
  1493.  *            TESSELLATION CALLBACKS
  1494.  *
  1495.  *****************************************************************************/
  1496.  
  1497. static void tess_begin_callback( GLUtesselator *tobj, GLenum mode )
  1498. {
  1499.     if ( tobj->callbacks.beginData != NULL )
  1500.     {
  1501.     ( tobj->callbacks.beginData )( mode, tobj->data );
  1502.     }
  1503.     else if ( tobj->callbacks.begin != NULL )
  1504.     {
  1505.     ( tobj->callbacks.begin )( mode );
  1506.     }
  1507. }
  1508.  
  1509. static void tess_vertex_callback( GLUtesselator *tobj, void *vertex_data )
  1510. {
  1511.     if ( tobj->callbacks.vertexData != NULL )
  1512.     {
  1513.     ( tobj->callbacks.vertexData )( vertex_data, tobj->data );
  1514.     }
  1515.     else if ( tobj->callbacks.vertex != NULL )
  1516.     {
  1517.     ( tobj->callbacks.vertex )( vertex_data );
  1518.     }
  1519. }
  1520.  
  1521. static void tess_end_callback( GLUtesselator *tobj )
  1522. {
  1523.     if ( tobj->callbacks.endData != NULL )
  1524.     {
  1525.     ( tobj->callbacks.endData )( tobj->data );
  1526.     }
  1527.     else if ( tobj->callbacks.end != NULL )
  1528.     {
  1529.     ( tobj->callbacks.end )();
  1530.     }
  1531. }
  1532.  
  1533. static void tess_edgeflag_callback( GLUtesselator *tobj, GLboolean flag )
  1534. {
  1535.     if ( flag == tobj->edge_flag ) {
  1536.     return;
  1537.     } else {
  1538.     tobj->edge_flag = flag;
  1539.     }
  1540.     MSG( 5, "             setting edge_flag: %s\n", ( flag ) ? "GL_TRUE" : "GL_FALSE" );
  1541.  
  1542.     if ( tobj->callbacks.edgeFlagData != NULL )
  1543.     {
  1544.     ( tobj->callbacks.edgeFlagData )( tobj->edge_flag, tobj->data );
  1545.     }
  1546.     else if ( tobj->callbacks.edgeFlag != NULL )
  1547.     {
  1548.     ( tobj->callbacks.edgeFlag )( tobj->edge_flag );
  1549.     }
  1550. }
  1551.  
  1552. static void tess_output_triangle( GLUtesselator *tobj, tess_vertex_t *vertex )
  1553. {
  1554.     tess_edgeflag_callback( tobj, vertex->edge_flag );
  1555.     tess_vertex_callback( tobj, vertex->data );
  1556.  
  1557.     if ( vertex->next->next == vertex->prev ) {
  1558.     tess_edgeflag_callback( tobj, vertex->edge_flag );
  1559.     } else {
  1560.     tess_edgeflag_callback( tobj, GL_FALSE );
  1561.     }
  1562.     tess_vertex_callback( tobj, vertex->next->data );
  1563.  
  1564.     tess_edgeflag_callback( tobj, vertex->prev->edge_flag );
  1565.     tess_vertex_callback( tobj, vertex->prev->data );
  1566. }
  1567.  
  1568.  
  1569.  
  1570. /*****************************************************************************
  1571.  * cleanup
  1572.  *
  1573.  * Clean up after the triangulation has taken place.  All memory allocated
  1574.  * by the triangulation should be freed before control is handed back to the
  1575.  * GLU functions.
  1576.  *****************************************************************************/
  1577. static void cleanup( GLUtesselator *tobj )
  1578. {
  1579.     tess_contour_t    *contour = tobj->contours;
  1580.     GLint        i;
  1581.  
  1582.     MSG( 5, "    -> cleanup( tobj:%p )\n", tobj );
  1583.  
  1584.     if ( tobj->sorted_vertices != NULL ) {
  1585.     free( tobj->sorted_vertices );
  1586.     }
  1587.     tobj->sorted_vertices = NULL;
  1588.  
  1589.     heap_cleanup( &tobj->ears );
  1590.     tobj->ears = NULL;
  1591.  
  1592.     for ( i = 0; i < tobj->num_contours; i++ )
  1593.     {
  1594.     hashtable_cleanup( &contour->reflex_vertices );
  1595.  
  1596.     contour = contour->next;
  1597.     }
  1598.  
  1599.     MSG( 5, "    <- cleanup( tobj:%p )\n", tobj );
  1600. }
  1601.  
  1602.  
  1603.  
  1604. /*****************************************************************************
  1605.  * contour_dump
  1606.  *
  1607.  * Dump all the vertices, reflex vertices etc for the given contour.
  1608.  *****************************************************************************/
  1609. void contour_dump( tess_contour_t *contour )
  1610. {
  1611. #ifdef DEBUG
  1612.     tess_vertex_t *vertex = contour->vertices;
  1613.     GLint i;
  1614.  
  1615.     if ( tess_dbg_level > 0 )
  1616.     {
  1617.     fprintf( DBG_STREAM, "\ncontour %p - nv: %d area: %.2f orient: %s winding: %d\n",
  1618.          contour, contour->num_vertices, contour->area,
  1619.          ( contour->orientation == GLU_CCW ) ? "GLU_CCW" :
  1620.          ( contour->orientation == GLU_CW ) ? "GLU_CW" : "GLU_UNKNOWN",
  1621.          contour->winding );
  1622.  
  1623.     for ( i = 0; i < contour->num_vertices; i++ )
  1624.     {
  1625.         fprintf( DBG_STREAM, "  v: %-2d (%.2f, %.2f) (%d, %d, %d) e: %d data: %p\n",
  1626.              vertex->index, vertex->v[X], vertex->v[Y],
  1627.              vertex->prev->index, vertex->index, vertex->next->index,
  1628.              vertex->edge_flag, vertex->data );
  1629.  
  1630.         if ( ( i == contour->num_vertices - 1 ) &&
  1631.          ( vertex->next != contour->vertices ) ) {
  1632.         fprintf( DBG_STREAM, "    ***** CONTOUR DOES NOT CLOSE ! *****\n" );
  1633.         }
  1634.         vertex = vertex->next;
  1635.     }
  1636.  
  1637.     fprintf( DBG_STREAM, "\n" );
  1638.  
  1639.     if ( contour->reflex_vertices )
  1640.     {
  1641.         hashtable_t    *table = contour->reflex_vertices;
  1642.  
  1643.         if ( table->num_elements > 0 ) {
  1644.         fprintf( DBG_STREAM, "  r:" );
  1645.         }
  1646.         for ( i = 0; i < table->size; i++ )
  1647.         {
  1648.         hashtable_elt_t    *elt = table->elements[ i ];
  1649.  
  1650.         while ( elt )
  1651.         {
  1652.             tess_vertex_t    *v = HASH_VERTEX( elt );
  1653.             fprintf( DBG_STREAM, " %d", v->index );
  1654.  
  1655.             elt = elt->next;
  1656.         }
  1657.         }
  1658.         if ( table->num_elements > 0 ) {
  1659.         fprintf( DBG_STREAM, "   n: %d\n\n", table->num_elements );
  1660.         }
  1661.     }
  1662.  
  1663.     fflush( DBG_STREAM );
  1664.     }
  1665. #endif
  1666. }
  1667.