home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src-glu / tess_clip.c < prev    next >
C/C++ Source or Header  |  1999-12-06  |  66KB  |  2,491 lines
  1. /* $Id: tess_clip.c,v 1.1.2.9 1999/12/05 02:04:30 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 polygon clipping
  30.  *
  31.  * Gareth Hughes <garethh@bell-labs.com>, November 1999
  32.  *
  33.  * Originally based on a modified version of the algorithms in the Generic
  34.  * Polygon Clipper (GPC), which are a modified version of the algorithms in
  35.  * Vatti 1992.
  36.  *
  37.  * GPC is Copyright (C) 1997-1999 Alan Murta (amurta@cs.man.ac.uk),
  38.  * Advanced Interfaces Group, University of Manchester.
  39.  *
  40.  *****************************************************************************/
  41.  
  42. #include <stdio.h>
  43. #include <stdlib.h>
  44. #include <math.h>
  45.  
  46. #include "gluP.h"
  47.  
  48. #include "tess.h"
  49. #include "tess_macros.h"
  50. #include "tess_clip.h"
  51.  
  52.  
  53. /*****************************************************************************
  54.  * Internal definitions:
  55.  *****************************************************************************/
  56.  
  57. #define LEFT            0
  58. #define RIGHT            1
  59.  
  60. #define ABOVE            0
  61. #define BELOW            1
  62.  
  63. #define CLIP                   0
  64. #define SUBJ                   1
  65.  
  66. #define BOT                   0
  67. #define TOP                   1
  68.  
  69. /* Edge intersection classes: */
  70. #define EDGE_EMPTY        0x0
  71. #define EDGE_EXT_MAX        0x1
  72. #define EDGE_EXT_LI        0x2
  73. #define EDGE_TOP        0x3
  74. #define EDGE_EXT_RI        0x4
  75. #define EDGE_RIGHT        0x5
  76. #define EDGE_INT_MAX_MIN    0x6
  77. #define EDGE_INT_MIN        0x7
  78. #define EDGE_EXT_MIN        0x8
  79. #define EDGE_EXT_MAX_MIN    0x9
  80. #define EDGE_LEFT        0xa
  81. #define EDGE_INT_LI        0xb
  82. #define EDGE_BOTTOM        0xc
  83. #define EDGE_INT_RI        0xd
  84. #define EDGE_INT_MAX        0xe
  85. #define EDGE_FULL        0xf
  86.  
  87. /* Edge bundle states: */
  88. #define UNBUNDLED        0
  89. #define BUNDLE_HEAD        1
  90. #define BUNDLE_TAIL        2
  91.  
  92. /* Horizontal edge states: */
  93. #define HORIZ_NONE        0
  94. #define HORIZ_BOT        1
  95. #define HORIZ_TOP        2
  96.  
  97. /* Winding number quadrants: */
  98. #define WIND_NE            0
  99. #define WIND_SE            1
  100. #define WIND_SW            2
  101. #define WIND_NW            3
  102.  
  103. /* Horizontal edge state transitions within scanbeam boundary: */
  104. const GLuint next_state[3][6] =
  105. {
  106.     { HORIZ_BOT, HORIZ_TOP,    HORIZ_TOP, HORIZ_BOT,    HORIZ_NONE, HORIZ_NONE },
  107.     { HORIZ_NONE, HORIZ_NONE,  HORIZ_NONE, HORIZ_NONE,  HORIZ_TOP, HORIZ_TOP },
  108.     { HORIZ_NONE, HORIZ_NONE,  HORIZ_NONE, HORIZ_NONE,  HORIZ_BOT, HORIZ_BOT }
  109. };
  110.  
  111. #define OPTIMAL( vertex )                        \
  112.         ( ( vertex->v[Y] != vertex->prev->v[Y] ) ||            \
  113.           ( vertex->v[Y] != vertex->next->v[Y] ) )
  114.  
  115. #define FWD_MIN( edge )                            \
  116.         ( ( edge->prev->vertex->v[Y] >= edge->vertex->v[Y] ) &&    \
  117.           ( edge->next->vertex->v[Y] > edge->vertex->v[Y] ) )
  118.  
  119. #define FWD_MAX( edge )                            \
  120.         ( edge->next->vertex->v[Y] <= edge->vertex->v[Y] )
  121.  
  122. #define REV_MIN( edge )                            \
  123.         ( ( edge->prev->vertex->v[Y] > edge->vertex->v[Y] ) &&    \
  124.           ( edge->next->vertex->v[Y] >= edge->vertex->v[Y] ) )
  125.  
  126. #define REV_MAX( edge )                            \
  127.         ( edge->prev->vertex->v[Y] <= edge->vertex->v[Y] )
  128.  
  129.  
  130. /*****************************************************************************
  131.  * Internal type definitions:
  132.  *****************************************************************************/
  133.  
  134. typedef struct tess_edge_s
  135. {
  136.     tess_vertex_t    *vertex;
  137.     struct tess_edge_s    *prev;
  138.     struct tess_edge_s    *next;
  139. } tess_edge_t;
  140.  
  141. typedef struct clip_contour_s
  142. {
  143.     GLint        active;
  144.     GLint        hole;
  145.     tess_vertex_t    *vertices[2];
  146.     tess_vertex_t    *floating[2];
  147.     struct clip_contour_s *next;
  148.     struct clip_contour_s *proxy;
  149. } clip_contour_t;
  150.  
  151. typedef struct edge_node_s
  152. {
  153.     tess_vertex_t    *vertices[2];
  154.     GLdouble        bot[2];
  155.     GLdouble        top[2];
  156.     GLdouble        xbot;
  157.     GLdouble        xtop;
  158.     GLdouble        dx;
  159.     GLint        type;
  160.     GLboolean        forward;
  161.     GLboolean        bundle[2][2];
  162.     GLuint        bside[2];
  163.     GLuint        bstate[2];
  164.     clip_contour_t    *out[2];
  165.     struct edge_node_s    *prev;
  166.     struct edge_node_s    *next;
  167.     struct edge_node_s    *pred;
  168.     struct edge_node_s    *succ;
  169.     struct edge_node_s    *next_bound;
  170. } edge_node_t;
  171.  
  172. typedef struct lmt_node_s
  173. {
  174.     GLdouble        y;
  175.     edge_node_t        *bounds;
  176.     struct lmt_node_s    *next;
  177. } lmt_node_t;
  178.  
  179. typedef struct sb_tree_s
  180. {
  181.     GLdouble        y;
  182.     struct sb_tree_s    *less;
  183.     struct sb_tree_s    *more;
  184. } sb_tree_t;
  185.  
  186. typedef struct it_node_s
  187. {
  188.     edge_node_t        *ie[2];
  189.     GLdouble        v[2];
  190.     GLdouble        coords[3];
  191.     void        *data;
  192.     struct it_node_s    *next;
  193. } it_node_t;
  194.  
  195. typedef struct st_node_s
  196. {
  197.     edge_node_t        *edge;
  198.     GLdouble        xbot;
  199.     GLdouble        xtop;
  200.     GLdouble        dx;
  201.     struct st_node_s    *prev;
  202. } st_node_t;
  203.  
  204.  
  205. /*****************************************************************************
  206.  *
  207.  *            POLYGON CLIPPING FUNCTIONS
  208.  *
  209.  *****************************************************************************/
  210.  
  211.  
  212. /*****************************************************************************
  213.  * insert_bound
  214.  *
  215.  * Insert the given bound e (where a bound is the set of edges from a local
  216.  * minimum to a local maximum) into the edge table b.
  217.  *****************************************************************************/
  218. static void insert_bound( edge_node_t **b, edge_node_t *e )
  219. {
  220.     edge_node_t        *bound;
  221.  
  222.     if ( !*b )
  223.     {
  224.     MSG( 1, "                  bound() new tail (%.2f, %.2f)\n",
  225.          e->bot[X], e->bot[Y] );
  226.  
  227.     /* Link node e to the tail of the list */
  228.     *b = e;
  229.     }
  230.     else
  231.     {
  232.     /* Do primary sort on the x field */
  233.     if ( e->bot[X] < (*b)->bot[X] )
  234.     {
  235.         MSG( 1, "                  bound() x less, insert (%.2f, %.2f)\n",
  236.          e->bot[X], e->bot[Y] );
  237.  
  238.         /* Insert a new node mid-list */
  239.         bound = *b;
  240.         *b = e;
  241.         (*b)->next_bound = bound;
  242.     }
  243.     else
  244.     {
  245.         if ( e->bot[X] == (*b)->bot[X] )
  246.         {
  247.         /* Do secondary sort on the dx field */
  248.         if ( e->dx < (*b)->dx )
  249.         {
  250.             MSG( 1, "                  bound() dx less, insert (%.2f, %.2f)\n",
  251.              e->bot[X], e->bot[Y] );
  252.  
  253.             /* Insert a new node mid-list */
  254.             bound = *b;
  255.             *b = e;
  256.             (*b)->next_bound = bound;
  257.         }
  258.         else
  259.         {
  260.             /* Head further down the list */
  261.             insert_bound( &((*b)->next_bound), e );
  262.         }
  263.         }
  264.         else
  265.         {
  266.         /* Head further down the list */
  267.         insert_bound( &((*b)->next_bound), e );
  268.         }
  269.     }
  270.     }
  271. }
  272.  
  273. /*****************************************************************************
  274.  * bound_list
  275.  *
  276.  * Return the bound list for the left and right bounds of a given local
  277.  * minima table entry.
  278.  *****************************************************************************/
  279. static edge_node_t **bound_list( lmt_node_t **lmt, tess_vertex_t *vertex )
  280. {
  281.     lmt_node_t        *node;
  282.  
  283.     if ( !*lmt )
  284.     {
  285.     MSG( 1, "                  bound_list() new tail node\n" );
  286.  
  287.     /* Add node onto the tail end of the LMT */
  288.     *lmt = (lmt_node_t *) malloc( sizeof(lmt_node_t) );
  289.  
  290.     (*lmt)->y = vertex->v[Y];
  291.     (*lmt)->bounds = NULL;
  292.     (*lmt)->next = NULL;
  293.  
  294.     return &((*lmt)->bounds);
  295.     }
  296.     else
  297.     {
  298.     if ( vertex->v[Y] < (*lmt)->y )
  299.     {
  300.         MSG( 1, "                  bound_list() new node before y: %.2f\n",
  301.          (*lmt)->y );
  302.  
  303.         /* Insert a new LMT node before the current node */
  304.         node = *lmt;
  305.  
  306.         *lmt = (lmt_node_t *) malloc( sizeof(lmt_node_t) );
  307.  
  308.         (*lmt)->y = vertex->v[Y];
  309.         (*lmt)->bounds = NULL;
  310.         (*lmt)->next = node;
  311.  
  312.         return &((*lmt)->bounds);
  313.     }
  314.     else
  315.     {
  316.         if ( vertex->v[Y] > (*lmt)->y )
  317.         {
  318.         /* Head further up the LMT */
  319.         return bound_list( &((*lmt)->next), vertex );
  320.         }
  321.         else
  322.         {
  323.         MSG( 1, "                  bound_list() use current y: %.2f\n",
  324.              (*lmt)->y );
  325.  
  326.         /* Use this existing LMT node */
  327.         return &((*lmt)->bounds);
  328.         }
  329.     }
  330.     }
  331. }
  332.  
  333.  
  334. /*****************************************************************************
  335.  * add_to_sb_tree
  336.  *
  337.  * Add the given vertex to the scanbeam tree.
  338.  *****************************************************************************/
  339. static void add_to_sb_tree( GLint *entries, sb_tree_t **sb_tree,
  340.                 tess_vertex_t *vertex )
  341. {
  342.     if ( !*sb_tree )
  343.     {
  344.     MSG( 1, "              sb_tree() adding y: %.2f\n", vertex->v[Y] );
  345.  
  346.     /* Add a new tree node here */
  347.     *sb_tree = (sb_tree_t *) malloc( sizeof(sb_tree_t) );
  348.  
  349.     (*sb_tree)->y = vertex->v[Y];
  350.     (*sb_tree)->less = NULL;
  351.     (*sb_tree)->more = NULL;
  352.  
  353.     (*entries)++;
  354.     }
  355.     else
  356.     {
  357.     if ( (*sb_tree)->y > vertex->v[Y] )
  358.     {
  359.         /* Head into the 'less' sub-tree */
  360.         add_to_sb_tree( entries, &((*sb_tree)->less), vertex );
  361.     }
  362.     else if ( (*sb_tree)->y < vertex->v[Y] )
  363.     {
  364.         /* Head into the 'more' sub-tree */
  365.         add_to_sb_tree( entries, &((*sb_tree)->more), vertex );
  366.     }
  367.     else
  368.     {
  369.         MSG( 1, "              sb_tree() not adding, same y: %.2f\n",
  370.          vertex->v[Y] );
  371.     }
  372.     }
  373. }
  374.  
  375. /*****************************************************************************
  376.  * build_sbt
  377.  *
  378.  * From the given scanbeam tree, construct the scanbeam table.  This table
  379.  * consists only of an array of y values, and has no vertex information.
  380.  *****************************************************************************/
  381. static void build_sbt( GLint *entries, GLdouble *sbt, sb_tree_t *sb_tree )
  382. {
  383.     if ( sb_tree->less ) {
  384.     build_sbt( entries, sbt, sb_tree->less );
  385.     }
  386.  
  387.  
  388.     MSG( 1, "          sbt[%d] = %.2f\n", *entries, sb_tree->y );
  389.     sbt[*entries] = sb_tree->y;
  390.     (*entries)++;
  391.  
  392.     if ( sb_tree->more ) {
  393.     build_sbt( entries, sbt, sb_tree->more );
  394.     }
  395. }
  396.  
  397. /*****************************************************************************
  398.  * cleanup_sb_tree
  399.  *
  400.  * Clean up the given scanbeam tree.
  401.  *****************************************************************************/
  402. static void cleanup_sb_tree( sb_tree_t **sb_tree )
  403. {
  404.     if ( *sb_tree )
  405.     {
  406.     cleanup_sb_tree( &((*sb_tree)->less) );
  407.     cleanup_sb_tree( &((*sb_tree)->more) );
  408.  
  409.     free( *sb_tree );
  410.     }
  411. }
  412.  
  413.  
  414. /*****************************************************************************
  415.  * count_optimal_vertices
  416.  *
  417.  * Count the number of vertices, not including any horizontally collinear
  418.  * vertices.
  419.  *****************************************************************************/
  420. static GLint count_optimal_vertices( tess_contour_t *contour )
  421. {
  422.     tess_vertex_t    *vertex = contour->vertices;
  423.     GLint        ret = 0;
  424.     GLint        i;
  425.  
  426.     /* Ignore non-contributing contours */
  427.     if ( contour->num_vertices > 0 )
  428.     {
  429.     for ( i = 0 ; i < contour->num_vertices ; i++)
  430.     {
  431.         /* Ignore superfluous vertices embedded in horizontal edges */
  432.         if ( OPTIMAL( vertex ) ) {
  433.         ret++;
  434.         }
  435.         vertex = vertex->next;
  436.     }
  437.     }
  438.  
  439.     return ret;
  440. }
  441.  
  442. /*****************************************************************************
  443.  * print_lmt
  444.  *
  445.  * Dump the contents of the local minima table.
  446.  *****************************************************************************/
  447. static void print_lmt( lmt_node_t *lmt )
  448. {
  449. #ifdef DEBUG
  450.     lmt_node_t        *node;
  451.     edge_node_t        *bound;
  452.     edge_node_t        *edge;
  453.  
  454.     MSG( 1, "\n" );
  455.     MSG( 1, "            lmt contents:\n" );
  456.  
  457.     for ( node = lmt ; node ; node = node->next )
  458.     {
  459.     MSG( 1, "              min at %.2f:\n", node->y );
  460.  
  461.     for ( bound = node->bounds ; bound ; bound = bound->next_bound )
  462.     {
  463.         MSG( 1, "                bound:\n" );
  464.  
  465.         for ( edge = bound ; edge ; edge = edge->succ )
  466.         {
  467.         MSG( 1, "                  edge (%.2f, %.2f) -> (%.2f, %.2f)\n",
  468.              edge->bot[X], edge->bot[Y],
  469.              edge->top[X], edge->top[Y] );
  470.         }
  471.     }
  472.     }
  473.     MSG( 1, "\n" );
  474. #endif
  475. }
  476.  
  477. /*****************************************************************************
  478.  * build_lmt
  479.  *
  480.  * Construct the local minima table for the input polygon, possibly
  481.  * consisting of several contours, associated with the tessellator object.
  482.  *****************************************************************************/
  483. static edge_node_t *build_lmt( GLUtesselator *tobj,
  484.                    lmt_node_t **lmt, sb_tree_t **sb_tree,
  485.                    GLint *sbt_entries )
  486. {
  487.     GLint        num_edges, num_vertices;
  488.     GLint        total_vertices = 0, e_index = 0;
  489.     edge_node_t        *edge_table;
  490.     edge_node_t        *edge;
  491.     tess_contour_t    *contour;
  492.     tess_vertex_t    *vertex;
  493.     tess_edge_t        *edges, *min, *max, *e;
  494.     GLint        i, j;
  495.  
  496.     MSG( 1, "      --> build_lmt()\n" );
  497.  
  498.     for ( contour = tobj->contours ; contour ; contour = contour->next ) {
  499.     total_vertices += count_optimal_vertices( contour );
  500.     }
  501.     MSG( 1, "            optimal vertices: %d\n", total_vertices );
  502.  
  503.     /* Create the entire input polygon edge table in one go */
  504.     edges = (tess_edge_t *)
  505.     malloc( total_vertices * sizeof(tess_edge_t) );
  506.     edge_table = (edge_node_t *)
  507.     malloc( total_vertices * sizeof(edge_node_t) );
  508.  
  509.     for ( contour = tobj->contours ; contour ; contour = contour->next )
  510.     {
  511.     if ( contour->num_vertices < 0 )
  512.     {
  513.         /* Ignore the non-contributing contour and repair the vertex
  514.            count */
  515.         contour->num_vertices = -contour->num_vertices;
  516.     }
  517.     else
  518.     {
  519.         /* Perform contour optimisation */
  520.         num_vertices = 0;
  521.         vertex = contour->vertices;
  522.  
  523.         for ( i = 0 ; i < contour->num_vertices ; i++ )
  524.         {
  525.         if ( OPTIMAL( vertex ) )
  526.         {
  527.             MSG( 1, "            adding edge: %d v: (%.2f, %.2f)\n",
  528.              num_vertices, vertex->v[X], vertex->v[Y] );
  529.  
  530.             edges[num_vertices].vertex = vertex;
  531.  
  532.             /* Set up linked list inside the array */
  533.             if ( i > 0 ) {
  534.             edges[num_vertices].prev =
  535.                 &edges[num_vertices-1];
  536.             edges[num_vertices-1].next =
  537.                 &edges[num_vertices];
  538.             }
  539.  
  540.             /* Record vertex in the scanbeam table */
  541.             add_to_sb_tree( sbt_entries, sb_tree, vertex );
  542.  
  543.             num_vertices++;
  544.         }
  545.         else
  546.         {
  547.             MSG( 1, "            not adding v: (%.2f, %.2f)\n",
  548.              vertex->v[X], vertex->v[Y] );
  549.         }
  550.  
  551.         vertex = vertex->next;
  552.         }
  553.  
  554. #ifdef DEBUG
  555.         edges[0].prev = NULL;
  556.         edges[num_vertices-1].next = NULL;
  557.  
  558.         MSG( 1, "            edge table:\n" );
  559.         for ( e = edges ; e ; e = e->next ) {
  560.         MSG( 1, "              v: (%.2f, %.2f)\n",
  561.              e->vertex->v[X], e->vertex->v[Y] );
  562.         }
  563. #endif
  564.         /* Wrap linked list of edges */
  565.         edges[0].prev = &edges[num_vertices-1];
  566.         edges[num_vertices-1].next = &edges[0];
  567.  
  568.         /*
  569.          * ****** CONTOUR FORWARD PASS ******
  570.          */
  571.         MSG( 1, "            fwd pass:\n" );
  572.  
  573.         for ( min = edges, i = 0 ; i < num_vertices ;
  574.           min = min->next, i++ )
  575.         {
  576.         /* If a forward local minimum... */
  577.         if ( FWD_MIN( min ) )
  578.         {
  579.             MSG( 1, "              local min (%.2f, %.2f)\n",
  580.              min->vertex->v[X], min->vertex->v[Y] );
  581.  
  582.             /* Search for the next local maximum... */
  583.             num_edges = 1;
  584.             max = min->next;
  585.  
  586.             while ( ! FWD_MAX( max ) )
  587.             {
  588.             MSG( 1, "              not local max (%.2f, %.2f)\n",
  589.                  max->vertex->v[X], max->vertex->v[Y] );
  590.  
  591.             num_edges++;
  592.             max = max->next;
  593.             }
  594.  
  595.             MSG( 1, "              local max (%.2f, %.2f), %d edges (%d)\n",
  596.              max->vertex->v[X], max->vertex->v[Y],
  597.              num_edges, e_index );
  598.  
  599.             /* Build the next edge list */
  600.             edge = &edge_table[e_index];
  601.             e_index += num_edges;
  602.             e = min;
  603.  
  604.             edge[0].bstate[BELOW] = UNBUNDLED;
  605.             edge[0].bundle[BELOW][CLIP] = GL_FALSE;
  606.             edge[0].bundle[BELOW][SUBJ] = GL_FALSE;
  607.  
  608.             for ( j = 0 ; j < num_edges ; j++ )
  609.             {
  610.             edge[j].vertices[BOT] = e->vertex;
  611.             edge[j].vertices[TOP] = e->vertex->next;
  612.  
  613.             edge[j].xbot   = e->vertex->v[X];
  614.             edge[j].bot[X] = e->vertex->v[X];
  615.             edge[j].bot[Y] = e->vertex->v[Y];
  616.  
  617.             e = e->next;
  618.  
  619.             edge[j].top[X] = e->vertex->v[X];
  620.             edge[j].top[Y] = e->vertex->v[Y];
  621.             edge[j].dx = ( (e->vertex->v[X] - edge[j].bot[X]) /
  622.                        ( edge[j].top[Y] - edge[j].bot[Y] ) );
  623.  
  624.             edge[j].type = SUBJ;
  625.             edge[j].forward = GL_TRUE;
  626.             edge[j].out[ABOVE] = NULL;
  627.             edge[j].out[BELOW] = NULL;
  628.             edge[j].next = NULL;
  629.             edge[j].prev = NULL;
  630.  
  631.             edge[j].succ =
  632.                 ( ( num_edges > 1 ) &&
  633.                   ( j < (num_edges - 1) ) ) ? &(edge[j+1]) : NULL;
  634.             edge[j].pred =
  635.                 ( ( num_edges > 1 ) &&
  636.                   ( j > 0 ) ) ? &(edge[j-1]) : NULL;
  637.  
  638.             edge[j].next_bound = NULL;
  639.             edge[j].bside[CLIP] = LEFT;
  640.             edge[j].bside[SUBJ] = LEFT;
  641.  
  642.             MSG( 1, "                edge b: (%.2f, %.2f) t: (%.2f, %.2f)\n", edge[j].bot[X], edge[j].bot[Y], edge[j].top[X], edge[j].top[Y] );
  643.             MSG( 1, "                vertex: (%.2f, %.2f) -> (%.2f, %.2f)\n", edge[j].vertices[BOT]->v[X], edge[j].vertices[BOT]->v[Y], edge[j].vertices[TOP]->v[X], edge[j].vertices[TOP]->v[Y] );
  644.             }
  645.  
  646.             insert_bound( bound_list( lmt, min->vertex ), edge );
  647.         }
  648.         }
  649.         MSG( 1, "            fwd pass complete!\n" );
  650.  
  651.         /*
  652.          * ****** CONTOUR REVERSE PASS ******
  653.          */
  654.         MSG( 1, "            rev pass:\n" );
  655.  
  656.         for ( min = edges, i = 0 ; i < num_vertices ;
  657.           min = min->next, i++ )
  658.         {
  659.         /* If a reverse local minimum... */
  660.         if ( REV_MIN( min ) )
  661.         {
  662.             MSG( 1, "              local min (%.2f, %.2f)\n",
  663.              min->vertex->v[X], min->vertex->v[Y] );
  664.  
  665.             /* Search for the previous local maximum... */
  666.             num_edges = 1;
  667.             max = min->prev;
  668.  
  669.             while ( ! REV_MAX( max ) )
  670.             {
  671.             MSG( 1, "              not local max (%.2f, %.2f)\n",
  672.                  max->vertex->v[X], max->vertex->v[Y] );
  673.  
  674.             num_edges++;
  675.             max = max->prev;
  676.             }
  677.             MSG( 1, "              local max (%.2f, %.2f), %d edges (%d)\n",
  678.              max->vertex->v[X], max->vertex->v[Y],
  679.              num_edges, e_index );
  680.  
  681.             /* Build the previous edge list */
  682.             edge = &edge_table[e_index];
  683.             e_index += num_edges;
  684.             e = min;
  685.  
  686.             edge[0].bstate[BELOW] = UNBUNDLED;
  687.             edge[0].bundle[BELOW][CLIP] = GL_FALSE;
  688.             edge[0].bundle[BELOW][SUBJ] = GL_FALSE;
  689.  
  690.             for ( j = 0 ; j < num_edges ; j++ )
  691.             {
  692.             edge[j].vertices[BOT] = e->vertex;
  693.             edge[j].vertices[TOP] = e->vertex->prev;
  694.  
  695.             edge[j].xbot   = e->vertex->v[X];
  696.             edge[j].bot[X] = e->vertex->v[X];
  697.             edge[j].bot[Y] = e->vertex->v[Y];
  698.  
  699.             e = e->prev;
  700.  
  701.             edge[j].top[X] = e->vertex->v[X];
  702.             edge[j].top[Y] = e->vertex->v[Y];
  703.             edge[j].dx = ( ( e->vertex->v[X] - edge[j].bot[X] ) /
  704.                        ( edge[j].top[Y] - edge[j].bot[Y] ) );
  705.  
  706.             edge[j].type = SUBJ;
  707.             edge[j].forward = GL_FALSE;
  708.             edge[j].out[ABOVE] = NULL;
  709.             edge[j].out[BELOW] = NULL;
  710.             edge[j].next = NULL;
  711.             edge[j].prev = NULL;
  712.  
  713.             edge[j].succ =
  714.                 ( ( num_edges > 1 ) &&
  715.                   ( j < (num_edges - 1) ) ) ? &(edge[j+1]) : NULL;
  716.             edge[j].pred =
  717.                 ( ( num_edges > 1 ) &&
  718.                   ( j > 0 ) ) ? &(edge[j-1]) : NULL;
  719.  
  720.             edge[j].next_bound = NULL;
  721.             edge[j].bside[CLIP] = LEFT;
  722.             edge[j].bside[SUBJ] = LEFT;
  723.  
  724.             MSG( 1, "                edge b: (%.2f, %.2f) t: (%.2f, %.2f)\n", edge[j].bot[X], edge[j].bot[Y], edge[j].top[X], edge[j].top[Y] );
  725.             MSG( 1, "                vertex: (%.2f, %.2f) <- (%.2f, %.2f)\n", edge[j].vertices[BOT]->v[X], edge[j].vertices[BOT]->v[Y], edge[j].vertices[TOP]->v[X], edge[j].vertices[TOP]->v[Y] );
  726.             }
  727.  
  728.             insert_bound( bound_list( lmt, min->vertex ), edge );
  729.         }
  730.         }
  731.         MSG( 1, "            rev pass complete!\n" );
  732.     }
  733.     }
  734.  
  735.     /* Free temporary edge list */
  736.     if ( edges ) {
  737.     free( edges );
  738.     }
  739.  
  740.     print_lmt( *lmt );
  741.  
  742.     MSG( 1, "      <-- build_lmt()\n" );
  743.     return edge_table;
  744. }
  745.  
  746. /*****************************************************************************
  747.  * cleanup_lmt
  748.  *
  749.  * Clean up the given local minima table.
  750.  *****************************************************************************/
  751. static void cleanup_lmt( lmt_node_t **lmt )
  752. {
  753.     lmt_node_t    *node;
  754.  
  755.     while ( *lmt )
  756.     {
  757.     node = (*lmt)->next;
  758.     free( *lmt );
  759.  
  760.     *lmt = node;
  761.     }
  762. }
  763.  
  764.  
  765. /*****************************************************************************
  766.  * add_edge_to_aet
  767.  *
  768.  * Add the given edge to the active edge table.  The active edge table is
  769.  * sorted by x coordinate, using an insertion sort.
  770.  *****************************************************************************/
  771. static void add_edge_to_aet( edge_node_t **aet,
  772.                  edge_node_t *edge, edge_node_t *prev )
  773. {
  774.     if ( !*aet )
  775.     {
  776.     MSG( 1, "              aet() new tail (%.2f, %.2f)\n",
  777.          edge->bot[X], edge->bot[Y] );
  778.  
  779.     /* Append edge onto the tail end of the AET */
  780.     *aet = edge;
  781.     edge->prev = prev;
  782.     edge->next = NULL;
  783.     }
  784.     else
  785.     {
  786.     /* Do primary sort on the xb field */
  787.     if ( edge->xbot < (*aet)->xbot )
  788.     {
  789.         MSG( 1, "              aet() x less, insert (%.2f, %.2f)\n",
  790.          edge->bot[X], edge->bot[Y] );
  791.  
  792.         /* Insert edge here (before the AET edge) */
  793.         edge->prev = prev;
  794.         edge->next = *aet;
  795.         (*aet)->prev = edge;
  796.         *aet = edge;
  797.     }
  798.     else if ( edge->xbot == (*aet)->xbot )
  799.     {
  800.         /* Do secondary sort on the dx field */
  801.         if ( edge->dx < (*aet)->dx )
  802.         {
  803.         MSG( 1, "              aet() dx less, insert (%.2f, %.2f)\n",
  804.              edge->bot[X], edge->bot[Y] );
  805.  
  806.         /* Insert edge here (before the AET edge) */
  807.         edge->prev = prev;
  808.         edge->next = *aet;
  809.         (*aet)->prev = edge;
  810.         *aet = edge;
  811.         }
  812.         else
  813.         {
  814.         /* Head further into the AET */
  815.         add_edge_to_aet( &((*aet)->next), edge, *aet );
  816.         }
  817.     }
  818.     else
  819.     {
  820.         /* Head further into the AET */
  821.         add_edge_to_aet( &((*aet)->next), edge, *aet );
  822.     }
  823.     }
  824. }
  825.  
  826.  
  827. /*****************************************************************************
  828.  * tess_combine_callback
  829.  *****************************************************************************/
  830. void tess_combine_callback( GLUtesselator *tobj, GLdouble coords[3],
  831.                 void *vertex_data[4], GLfloat weight[4],
  832.                 void **out_data )
  833. {
  834.     if ( tobj->callbacks.combineData != NULL )
  835.     {
  836.     ( tobj->callbacks.combineData )( coords, vertex_data, weight,
  837.                      out_data, tobj->data );
  838.     }
  839.     else if ( tobj->callbacks.combine != NULL )
  840.     {
  841.     ( tobj->callbacks.combine )( coords, vertex_data, weight, out_data );
  842.     }
  843. }
  844.  
  845. /*****************************************************************************
  846.  * intersect_edges
  847.  *
  848.  * Intersect edges (a, b) and (c, d) to obtain the 3D intersection point
  849.  * and any data from the combine callback.
  850.  *****************************************************************************/
  851. static GLboolean intersect_edges( GLUtesselator *tobj, it_node_t *it,
  852.                   tess_vertex_t *a, tess_vertex_t *b,
  853.                   tess_vertex_t *c, tess_vertex_t *d )
  854. {
  855.     /*
  856.      * Calculate the values required for the intersection test.  Taken
  857.      *  directly from the comp.graphics.algorithms FAQ.
  858.      */
  859.     GLdouble    denom =
  860.     ( ( b->v[X] - a->v[X] ) * ( d->v[Y] - c->v[Y] ) ) -
  861.     ( ( b->v[Y] - a->v[Y] ) * ( d->v[X] - c->v[X] ) );
  862.  
  863.     GLdouble    r =
  864.     ( ( a->v[Y] - c->v[Y] ) * ( d->v[X] - c->v[X] ) ) -
  865.     ( ( a->v[X] - c->v[X] ) * ( d->v[Y] - c->v[Y] ) );
  866.  
  867.     GLdouble    s =
  868.     ( ( a->v[Y] - c->v[Y] ) * ( b->v[X] - a->v[X] ) ) -
  869.     ( ( a->v[X] - c->v[X] ) * ( b->v[Y] - a->v[Y] ) );
  870.  
  871.     void    *vertex_data[4];
  872.     GLfloat    weight[4];
  873.  
  874.     /* Return false if lines are parallel */
  875.     if ( ABSD( denom ) < GLU_TESS_EPSILON ) return GL_FALSE;
  876.  
  877.     r = r / denom;
  878.     s = s / denom;
  879.  
  880.     /* Return false if the line segments do not intersect. */
  881.     if ( ( r <= 0.0 ) || ( r >= 1.0 ) ||
  882.      ( s <= 0.0 ) || ( s >= 1.0 ) )
  883.     {
  884.     return GL_FALSE;
  885.     }
  886.  
  887.     ASSIGN_4V( vertex_data,
  888.            a->data, b->data, c->data, d->data );
  889.     ASSIGN_4V( weight,
  890.            (GLfloat)(( 1.0 - r ) * 0.5), (GLfloat)(r * 0.5),
  891.            (GLfloat)(( 1.0 - s ) * 0.5), (GLfloat)(s * 0.5) );
  892.  
  893.     /*
  894.      * Calculate the actual point of intersection.  Again, taken
  895.      *  from the comp.graphics.alrogithms FAQ.
  896.      */
  897.     it->coords[X] = a->coords[X] + r * ( b->coords[X] - a->coords[X] );
  898.     it->coords[Y] = a->coords[Y] + r * ( b->coords[Y] - a->coords[Y] );
  899.     it->coords[Z] = a->coords[Z] + r * ( b->coords[Z] - a->coords[Z] );
  900.  
  901.     it->v[X] = a->v[X] + r * ( b->v[X] - a->v[X] );
  902.     it->v[Y] = a->v[Y] + r * ( b->v[Y] - a->v[Y] );
  903.  
  904.     it->data = NULL;
  905.  
  906.     /* Combine the intersection into a new vertex. */
  907.     tess_combine_callback( tobj, it->coords, vertex_data,
  908.                weight, &(it->data) );
  909.  
  910.     MSG( 1, "                  r: %.2f s: %.2f new: (%.2f, %.2f, %.2f)\n",
  911.      r, s, it->coords[X], it->coords[Y], it->coords[Z] );
  912.  
  913.     return GL_TRUE;
  914. }
  915.  
  916. /*****************************************************************************
  917.  * it_vertex
  918.  *
  919.  * Using the given intersection table entry, create a new vertex at the
  920.  * intersection point with the data from the combine callback.
  921.  *****************************************************************************/
  922. static tess_vertex_t *it_vertex( GLUtesselator *tobj, it_node_t *it )
  923. {
  924.     tess_vertex_t    *vertex;
  925.  
  926.     MSG( 15, "it_vertex() v: (%.2f, %.2f) data: %p\n",
  927.      it->v[X], it->v[Y], it->data );
  928.  
  929.     /* Create a new vertex at the intersection point */
  930.     vertex = (tess_vertex_t *) malloc( sizeof(tess_vertex_t) );
  931.  
  932.     vertex->index = -1;
  933.     vertex->data = it->data;
  934.  
  935.     vertex->coords[X] = it->coords[X];
  936.     vertex->coords[Y] = it->coords[Y];
  937.     vertex->coords[Z] = it->coords[Z];
  938.  
  939.     vertex->v[X] = it->v[X];
  940.     vertex->v[Y] = it->v[Y];
  941.  
  942.     vertex->edge_flag = GL_TRUE;
  943.  
  944.     vertex->side = 0.0;
  945.  
  946.     vertex->next = vertex->prev = NULL;
  947.  
  948.     /* Increment the global number of vertices */
  949.     tobj->num_vertices++;
  950.  
  951.     return vertex;
  952. }
  953.  
  954. /*****************************************************************************
  955.  * add_intersection
  956.  *
  957.  * Add an entry to the intersection table at the given point between the
  958.  * given two edges.
  959.  *****************************************************************************/
  960. static void add_intersection( GLUtesselator *tobj, it_node_t **it,
  961.                   edge_node_t *edge0, edge_node_t *edge1,
  962.                   GLdouble x, GLdouble y )
  963. {
  964.     it_node_t    *node;
  965.  
  966.     if ( !*it )
  967.     {
  968.     MSG( 1, "                it() new tail (%.2f, %.2f)\n", x, y );
  969.  
  970.     /* Append a new node to the tail of the list */
  971.     *it = (it_node_t *) malloc( sizeof(it_node_t) );
  972.  
  973.     (*it)->ie[0] = edge0;
  974.     (*it)->ie[1] = edge1;
  975.     (*it)->v[X] = x;
  976.     (*it)->v[Y] = y;
  977.     (*it)->next = NULL;
  978.  
  979.     /* Perform tessellation combine callback */
  980.     intersect_edges( tobj, *it,
  981.              edge0->vertices[BOT], edge0->vertices[TOP],
  982.              edge1->vertices[BOT], edge1->vertices[TOP] );
  983.     }
  984.     else
  985.     {
  986.     if ( (*it)->v[Y] > y )
  987.     {
  988.         MSG( 1, "                it() insert (%.2f, %.2f)\n", x, y );
  989.  
  990.         /* Insert a new node mid-list */
  991.         node = *it;
  992.  
  993.         *it = (it_node_t *) malloc( sizeof(it_node_t) );
  994.  
  995.         (*it)->ie[0] = edge0;
  996.         (*it)->ie[1] = edge1;
  997.         (*it)->v[X] = x;
  998.         (*it)->v[Y] = y;
  999.         (*it)->next = node;
  1000.  
  1001.         /* Perform tessellation combine callback */
  1002.         intersect_edges( tobj, *it,
  1003.                  edge0->vertices[BOT], edge0->vertices[TOP],
  1004.                  edge1->vertices[BOT], edge1->vertices[TOP] );
  1005.     }
  1006.     else
  1007.     {
  1008.         /* Head further down the list */
  1009.         add_intersection( tobj, &((*it)->next), edge0, edge1, x, y );
  1010.     }
  1011.     }
  1012. }
  1013.  
  1014. /*****************************************************************************
  1015.  * add_st_edge
  1016.  *
  1017.  * Add the edge to the sorted edge table.  If the edge intersects another
  1018.  * edge already in the table, calculate the required intersection
  1019.  * information.
  1020.  *****************************************************************************/
  1021. static void add_st_edge( GLUtesselator *tobj, st_node_t **st, it_node_t **it,
  1022.              edge_node_t *edge, GLdouble dy )
  1023. {
  1024.     st_node_t    *node;
  1025.     GLdouble    den, r, x, y;
  1026.  
  1027.     if ( !*st )
  1028.     {
  1029.     MSG( 1, "                st() new tail (%.2f, %.2f)\n",
  1030.          edge->bot[X], edge->bot[Y] );
  1031.  
  1032.     /* Append edge onto the tail end of the ST */
  1033.     *st = (st_node_t *) malloc( sizeof(st_node_t) );
  1034.  
  1035.     (*st)->edge = edge;
  1036.     (*st)->xbot = edge->xbot;
  1037.     (*st)->xtop = edge->xtop;
  1038.     (*st)->dx = edge->dx;
  1039.     (*st)->prev = NULL;
  1040.     }
  1041.     else
  1042.     {
  1043.     den = ((*st)->xtop - (*st)->xbot) - (edge->xtop - edge->xbot);
  1044.  
  1045.     /* If new edge and ST edge don't cross */
  1046.     if ( ( edge->xtop >= (*st)->xtop ) || ( edge->dx == (*st)->dx ) ||
  1047.          ( ABSD( den ) <= GLU_TESS_EPSILON ) )
  1048.     {
  1049.         MSG( 1, "                st() insert (%.2f, %.2f)\n",
  1050.          edge->bot[X], edge->bot[Y] );
  1051.  
  1052.         /* No intersection - insert edge here (before the ST edge) */
  1053.         node = *st;
  1054.  
  1055.         *st = (st_node_t *) malloc( sizeof(st_node_t) );
  1056.  
  1057.         (*st)->edge = edge;
  1058.         (*st)->xbot = edge->xbot;
  1059.         (*st)->xtop = edge->xtop;
  1060.         (*st)->dx = edge->dx;
  1061.         (*st)->prev = node;
  1062.     }
  1063.     else
  1064.     {
  1065.         /* Compute intersection between new edge and ST edge */
  1066.         r = (edge->xbot - (*st)->xbot) / den;
  1067.         x = (*st)->xbot + r * ((*st)->xtop - (*st)->xbot);
  1068.         y = (*st)->edge->bot[Y] + r * dy;
  1069.  
  1070.         MSG( 1, "            *** st() intersection at (%.2f, %.2f)\n",
  1071.          x, y );
  1072.  
  1073.         /* Insert the edge pointers and the intersection point in the IT */
  1074.         add_intersection( tobj, it, (*st)->edge, edge, x, y );
  1075.  
  1076.         /* Head further into the ST */
  1077.         add_st_edge( tobj, &((*st)->prev), it, edge, dy );
  1078.     }
  1079.     }
  1080. }
  1081.  
  1082. /*****************************************************************************
  1083.  * cleanup_it
  1084.  *
  1085.  * Clean up the given intersection table.
  1086.  *****************************************************************************/
  1087. static void cleanup_it( it_node_t **it )
  1088. {
  1089.     it_node_t    *node;
  1090.  
  1091.     while ( *it )
  1092.     {
  1093.     node = (*it)->next;
  1094.     free( *it );
  1095.  
  1096.     *it = node;
  1097.     }
  1098. }
  1099.  
  1100. /*****************************************************************************
  1101.  * build_intersection_table
  1102.  *
  1103.  * From the current active edge table, build the corresponding intersection
  1104.  * table for the current scanbeam.
  1105.  *****************************************************************************/
  1106. static void build_intersection_table( GLUtesselator *tobj, it_node_t **it,
  1107.                       edge_node_t *aet, GLdouble dy )
  1108. {
  1109.     st_node_t        *st, *stp;
  1110.     edge_node_t        *edge;
  1111.  
  1112.     /* Build intersection table for the current scanbeam */
  1113.     cleanup_it( it );
  1114.     st = NULL;
  1115.  
  1116.     /* Process each AET edge */
  1117.     for ( edge = aet ; edge ; edge = edge->next )
  1118.     {
  1119.     if ( ( edge->bstate[ABOVE] == BUNDLE_HEAD ) ||
  1120.          edge->bundle[ABOVE][CLIP] || edge->bundle[ABOVE][SUBJ] )
  1121.     {
  1122.         add_st_edge( tobj, &st, it, edge, dy );
  1123.     }
  1124.     }
  1125.  
  1126.     /* Free the sorted edge table */
  1127.     while ( st )
  1128.     {
  1129.     stp = st->prev;
  1130.     free( st );
  1131.     st = stp;
  1132.     }
  1133. }
  1134.  
  1135. /*****************************************************************************
  1136.  * find_intersection
  1137.  *
  1138.  * Find the point of intersection between the given edge and an edge in the
  1139.  * AET that lies in the given scanbeam.  Return the quadrant that the area
  1140.  * with the highest winding number lies in.
  1141.  *****************************************************************************/
  1142. static GLint find_intersection( GLUtesselator *tobj, it_node_t **it,
  1143.                 edge_node_t *aet, edge_node_t *edge,
  1144.                 GLdouble ybot, GLdouble ytop )
  1145. {
  1146.     edge_node_t        *e;
  1147.     tess_vertex_t    *horiz[2] = { NULL, NULL };
  1148.     GLboolean        forward = GL_FALSE;
  1149.     GLboolean        done = GL_FALSE;
  1150.     GLint        ret = -1;
  1151.  
  1152.     MSG( 1, "            *** searching for intersection...\n" );
  1153.  
  1154.     /* Make sure the intersection table node is empty before we begin */
  1155.     cleanup_it( it );
  1156.  
  1157.     /* Allocate a new intersection table entry */
  1158.     *it = (it_node_t *) malloc( sizeof(it_node_t) );
  1159.     if ( *it == NULL ) {
  1160.     tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  1161.     return ret;
  1162.     }
  1163.  
  1164.     (*it)->next = NULL;
  1165.  
  1166.     /* Process each AET edge */
  1167.     for ( e = aet ; e ; e = e->next )
  1168.     {
  1169.     MSG( 1, "                e (%.2f, %.2f) -> (%.2f %.2f)\n",
  1170.          e->bot[X], e->bot[Y], e->top[X], e->top[Y] );
  1171.  
  1172.     if ( e == edge ) continue;
  1173.  
  1174.     /* Test if the two edges intersect */
  1175.     done = intersect_edges( tobj, *it,
  1176.                 edge->vertices[BOT], edge->vertices[TOP],
  1177.                 e->vertices[BOT], e->vertices[TOP] );
  1178.  
  1179.     if ( done && ( ( (*it)->v[Y] < ybot ) || ( (*it)->v[Y] > ytop ) ) )
  1180.     {
  1181.         /*
  1182.          * The intersection point lies outside the current scanbeam,
  1183.          * so we need to keep looking.
  1184.          */
  1185.         MSG( 1, "                int %.2f outside yb: %.2f yt: %.2f\n",
  1186.          (*it)->v[Y], ybot, ytop );
  1187.         done = GL_FALSE;
  1188.     }
  1189.  
  1190.     /*
  1191.      * FIXME: This is a little dodgy, and should become a list of all
  1192.      * horizontal edges on the current scanline.  Then, all these edges
  1193.      * should be tested for intersection.
  1194.      */
  1195.  
  1196.     /* Save the current horizontal edge, if one exists */
  1197.     if ( horiz[BOT] == NULL )
  1198.     {
  1199.         if ( e->vertices[BOT]->v[Y] == ybot )
  1200.         {
  1201.         horiz[BOT] = e->vertices[BOT];
  1202.         forward = GL_TRUE;
  1203.         }
  1204.         else if ( e->vertices[TOP]->v[Y] == ybot )
  1205.         {
  1206.         horiz[BOT] = e->vertices[TOP];
  1207.         forward = GL_FALSE;
  1208.         }
  1209.     }
  1210.     if ( e->vertices[BOT]->v[Y] == ybot ) {
  1211.         horiz[TOP] = e->vertices[BOT];
  1212.     } else if ( e->vertices[TOP]->v[Y] == ybot ) {
  1213.         horiz[TOP] = e->vertices[TOP];
  1214.     }
  1215.  
  1216.     /*
  1217.      * If a valid intersection point has been found, exit here so the
  1218.      * intersecting edge is saved.
  1219.      */
  1220.     if ( done ) {
  1221.         break;
  1222.     }
  1223.     }
  1224.  
  1225.     /* Check the horizontal edge that is implicitly in the AET */
  1226.     if ( !done )
  1227.     {
  1228.     MSG( 1, "            *** checking horizontal edge...\n" );
  1229.     MSG( 1, "                e (%.2f, %.2f) -> (%.2f %.2f)\n",
  1230.          horiz[BOT]->v[X], horiz[BOT]->v[Y],
  1231.          horiz[TOP]->v[X], horiz[TOP]->v[Y] );
  1232.  
  1233.     done = intersect_edges( tobj, *it,
  1234.                 edge->vertices[BOT], edge->vertices[TOP],
  1235.                 horiz[BOT], horiz[TOP] );
  1236.  
  1237.     if ( done )
  1238.     {
  1239.         MSG( 1, "                found int (%.2f, %.2f)\n",
  1240.          (*it)->v[X], (*it)->v[Y] );
  1241.     }
  1242.     else
  1243.     {
  1244.         MSG( 1, "something's really wrong here...\n" );
  1245.     }
  1246.     }
  1247.     else
  1248.     {
  1249.     forward = e->forward;
  1250.     }
  1251.  
  1252.     /* Calculate the quadrant with the highest winding number */
  1253.     if ( edge->forward )
  1254.     {
  1255.     ret = ( forward ) ? WIND_NW : WIND_SW;
  1256.     }
  1257.     else
  1258.     {
  1259.     ret = ( forward ) ? WIND_NE : WIND_SE;
  1260.     }
  1261.  
  1262. #ifdef DEBUG
  1263.     switch ( ret )
  1264.     {
  1265.     case WIND_NE:
  1266.     MSG( 1, "                highest winding number NE\n" );
  1267.     break;
  1268.     case WIND_SE:
  1269.     MSG( 1, "                highest winding number SE\n" );
  1270.     break;
  1271.     case WIND_SW:
  1272.     MSG( 1, "                highest winding number SW\n" );
  1273.     break;
  1274.     case WIND_NW:
  1275.     MSG( 1, "                highest winding number NW\n" );
  1276.     break;
  1277.     }
  1278. #endif
  1279.     return ret;
  1280. }
  1281.  
  1282.  
  1283. /*****************************************************************************
  1284.  * add_left
  1285.  *
  1286.  * Add the given vertex to the left end of the contour's vertex list.
  1287.  *****************************************************************************/
  1288. static void add_left( clip_contour_t *contour, tess_vertex_t *vertex )
  1289. {
  1290.     vertex->prev = contour->proxy->vertices[RIGHT];
  1291.     vertex->next = contour->proxy->vertices[LEFT];
  1292.  
  1293.     contour->proxy->vertices[LEFT]->prev  = vertex;
  1294.     contour->proxy->vertices[RIGHT]->next = vertex;
  1295.  
  1296.     contour->proxy->vertices[LEFT] = vertex;
  1297.  
  1298.     MSG( 1, "  add_left()       v: (%.2f, %.2f)\n",
  1299.      vertex->v[X], vertex->v[Y] );
  1300. }
  1301.  
  1302. /*****************************************************************************
  1303.  * merge_left
  1304.  *****************************************************************************/
  1305. static void merge_left( clip_contour_t *p, clip_contour_t *q,
  1306.             clip_contour_t *list )
  1307. {
  1308.     clip_contour_t    *target;
  1309.  
  1310.     MSG( 1, "  merge_left()\n" );
  1311.  
  1312.     /* Label contour as a hole */
  1313.     q->proxy->hole = GL_TRUE;
  1314.  
  1315.     if ( p->proxy != q->proxy )
  1316.     {
  1317.     /* Assign p's vertex list to the left end of q's list */
  1318.     p->proxy->vertices[RIGHT]->next = q->proxy->vertices[LEFT];
  1319.     p->proxy->vertices[LEFT]->prev = q->proxy->vertices[RIGHT];
  1320.  
  1321.     q->proxy->vertices[LEFT]->prev = p->proxy->vertices[RIGHT];
  1322.     q->proxy->vertices[RIGHT]->next = p->proxy->vertices[LEFT];
  1323.  
  1324.     q->proxy->vertices[LEFT] = p->proxy->vertices[LEFT];
  1325.     p->proxy->vertices[RIGHT] = q->proxy->vertices[RIGHT];
  1326.  
  1327.     /* Redirect any p->proxy references to q->proxy */
  1328.     for ( target = p->proxy ; list ; list = list->next )
  1329.     {
  1330.         if ( list->proxy == target )
  1331.         {
  1332.         list->active = GL_FALSE;
  1333.         list->proxy = q->proxy;
  1334.         }
  1335.     }
  1336.     }
  1337. }
  1338.  
  1339. /*****************************************************************************
  1340.  * add_right
  1341.  *
  1342.  * Add the given vertex to the right end of the contour's vertex list.
  1343.  *****************************************************************************/
  1344. static void add_right( clip_contour_t *contour, tess_vertex_t *vertex )
  1345. {
  1346.     vertex->prev = contour->proxy->vertices[RIGHT];
  1347.     vertex->next = contour->proxy->vertices[LEFT];
  1348.  
  1349.     contour->proxy->vertices[RIGHT]->next = vertex;
  1350.     contour->proxy->vertices[LEFT]->prev  = vertex;
  1351.  
  1352.     contour->proxy->vertices[RIGHT] = vertex;
  1353.  
  1354.     MSG( 1, "  add_right()      v: (%.2f, %.2f)\n",
  1355.      vertex->v[X], vertex->v[Y] );
  1356. }
  1357.  
  1358. /*****************************************************************************
  1359.  * merge_right
  1360.  *****************************************************************************/
  1361. static void merge_right( clip_contour_t *p, clip_contour_t *q,
  1362.              clip_contour_t *list )
  1363. {
  1364.     clip_contour_t    *target;
  1365.  
  1366.     MSG( 1, "  merge_right()\n" );
  1367.  
  1368.     /* Label contour as external */
  1369.     q->proxy->hole = GL_FALSE;
  1370.  
  1371.     if ( p->proxy != q->proxy )
  1372.     {
  1373.     /* Assign p's vertex list to the right end of q's list */
  1374.     q->proxy->vertices[RIGHT]->next = p->proxy->vertices[LEFT];
  1375.     q->proxy->vertices[LEFT]->prev = p->proxy->vertices[RIGHT];
  1376.  
  1377.     p->proxy->vertices[LEFT]->prev = q->proxy->vertices[RIGHT];
  1378.     p->proxy->vertices[RIGHT]->next = q->proxy->vertices[LEFT];
  1379.  
  1380.     p->proxy->vertices[LEFT] = p->proxy->vertices[LEFT];
  1381.     q->proxy->vertices[RIGHT] = p->proxy->vertices[RIGHT];
  1382.  
  1383.     /* Redirect any p->proxy references to q->proxy */
  1384.     for ( target = p->proxy ; list ; list = list->next )
  1385.     {
  1386.         if ( list->proxy == target )
  1387.         {
  1388.         list->active = GL_FALSE;
  1389.         list->proxy = q->proxy;
  1390.         }
  1391.     }
  1392.     }
  1393. }
  1394.  
  1395. /*****************************************************************************
  1396.  * add_local_min
  1397.  *
  1398.  * Add the given vertex as a new local minimum.  Create a new contour entry
  1399.  * to hold the new local minimum.
  1400.  *****************************************************************************/
  1401. static void add_local_min( clip_contour_t **contour, edge_node_t *edge,
  1402.                tess_vertex_t *vertex )
  1403. {
  1404.     clip_contour_t    *min;
  1405.  
  1406.     min = *contour;
  1407.  
  1408.     *contour = (clip_contour_t *) malloc( sizeof(clip_contour_t) );
  1409.  
  1410.     vertex->prev = NULL;
  1411.     vertex->next = NULL;
  1412.  
  1413.     /* Initialise proxy to point to p itself */
  1414.     (*contour)->proxy = (*contour);
  1415.     (*contour)->active = GL_TRUE;
  1416.     (*contour)->next = min;
  1417.  
  1418.     /* Make v[LEFT] and v[RIGHT] point to new vertex nv */
  1419.     (*contour)->vertices[LEFT]  = vertex;
  1420.     (*contour)->vertices[RIGHT] = vertex;
  1421.  
  1422.     /* Assign polygon p to the edge */
  1423.     edge->out[ABOVE] = *contour;
  1424.  
  1425.     MSG( 1, "  add_local_min()  v: (%.2f, %.2f)\n",
  1426.      (*contour)->vertices[LEFT]->v[X], (*contour)->vertices[LEFT]->v[Y] );
  1427. }
  1428.  
  1429.  
  1430. /*****************************************************************************
  1431.  * new_contour
  1432.  *
  1433.  * Create a new output contour.
  1434.  *****************************************************************************/
  1435. static tess_contour_t *new_contour( GLUtesselator *tobj )
  1436. {
  1437.     tess_contour_t    *contour;
  1438.  
  1439.     contour = malloc( sizeof(tess_contour_t) );
  1440.     if ( contour == NULL ) {
  1441.     tess_error_callback( tobj, GLU_OUT_OF_MEMORY );
  1442.     return NULL;
  1443.     }
  1444.  
  1445.     COPY_3V( contour->plane.normal, tobj->plane.normal );
  1446.     contour->plane.dist = tobj->plane.dist;
  1447.  
  1448.     contour->area = 0.0;
  1449.     contour->orientation = GLU_UNKNOWN;
  1450.  
  1451.     contour->label = 0;
  1452.     contour->winding = 0;
  1453.  
  1454.     contour->rotx = contour->roty = 0.0;
  1455.  
  1456.     CLEAR_BBOX_2DV( contour->mins, contour->maxs );
  1457.  
  1458.     contour->num_vertices = 0;
  1459.     contour->vertices = contour->last_vertex = NULL;
  1460.  
  1461.     contour->reflex_vertices = NULL;
  1462.  
  1463.     return contour;
  1464. }
  1465.  
  1466. /*****************************************************************************
  1467.  * inspect_contour
  1468.  *****************************************************************************/
  1469. static void inspect_contour( tess_contour_t *contour )
  1470. {
  1471.     tess_vertex_t    *vertex = contour->vertices;
  1472.     GLdouble        area;
  1473.     GLint        i;
  1474.  
  1475.     for ( i = 0; i < contour->num_vertices; i++ )
  1476.     {
  1477.     ACC_BBOX_2V( vertex->v, contour->mins, contour->maxs );
  1478.  
  1479.     vertex = vertex->next;
  1480.     }
  1481.  
  1482.     area = twice_contour_area( contour );
  1483.  
  1484.     if ( area >= 0.0 )
  1485.     {
  1486.     contour->orientation = GLU_CCW;
  1487.     contour->area = area;
  1488.     }
  1489.     else
  1490.     {
  1491.     contour->orientation = GLU_CW;
  1492.     contour->area = -area;
  1493.     }
  1494.  
  1495.     MSG( 1, "              contour area: %.2f\n", contour->area );
  1496. }
  1497.  
  1498. /*****************************************************************************
  1499.  * output_contours
  1500.  *
  1501.  * Create the new contour entries for all valid clip contours.
  1502.  *****************************************************************************/
  1503. static void output_contours( GLUtesselator *tobj, clip_contour_t *out )
  1504. {
  1505.     tess_contour_t    *contour, *next_contour;
  1506.     tess_vertex_t    *vertex, *next_vertex;
  1507.     clip_contour_t    *clip, *next_clip;
  1508.     GLint        num_contours, num_vertices;
  1509.     GLint        i;
  1510.  
  1511.     MSG( 1, "      --> output_contours( tobj:%p out:%p )\n", tobj, out );
  1512.  
  1513.     for ( clip = out, num_contours = 0 ; clip ; clip = clip->next )
  1514.     {
  1515.     if ( clip->active )
  1516.     {
  1517.         /* Count the vertices in the current contour */
  1518.         num_vertices = 0;
  1519.         vertex = clip->proxy->vertices[LEFT];
  1520.         do
  1521.         {
  1522.         num_vertices++;
  1523.         vertex = vertex->next;
  1524.         }
  1525.         while ( vertex != clip->proxy->vertices[LEFT] );
  1526.  
  1527.         MSG( 1, "            clip: %p nv: %d\n", clip, num_vertices );
  1528.  
  1529.         /* Record valid vertex counts in the active field */
  1530.         if ( num_vertices > 2 )
  1531.         {
  1532.         clip->active = num_vertices;
  1533.         num_contours++;
  1534.         }
  1535.         else
  1536.         {
  1537.         /* Invalid contour: just free the heap */
  1538.         vertex = clip->proxy->vertices[LEFT];
  1539.         do
  1540.         {
  1541.             next_vertex = vertex->next;
  1542.             free( vertex );
  1543.             vertex = next_vertex;
  1544.         }
  1545.         while ( vertex != clip->proxy->vertices[LEFT] );
  1546.  
  1547.         clip->active = 0;
  1548.         }
  1549.     }
  1550.     }
  1551.     MSG( 1, "            num contours: %d\n", num_contours );
  1552.  
  1553.     /* Delete all existing contours */
  1554.     for ( contour = tobj->contours, i = 0 ; i < tobj->num_contours ; i++ )
  1555.     {
  1556.     next_contour = contour->next;
  1557.     free( contour );
  1558.     contour = next_contour;
  1559.     }
  1560.  
  1561.     tobj->contours = NULL;
  1562.     tobj->last_contour = NULL;
  1563.     tobj->num_contours = num_contours;
  1564.  
  1565.     if ( tobj->num_contours > 0 )
  1566.     {
  1567.     for ( clip = out ; clip ; clip = next_clip )
  1568.     {
  1569.         next_clip = clip->next;
  1570.  
  1571.         if ( clip->active )
  1572.         {
  1573.         /* Generate a new contour */
  1574.         tobj->current_contour = new_contour( tobj );
  1575.  
  1576.         tobj->current_contour->num_vertices = clip->active;
  1577.  
  1578.         /* Extract the vertex loop and assign it to the new contour */
  1579.         tobj->current_contour->vertices =
  1580.             clip->proxy->vertices[LEFT];
  1581.         tobj->current_contour->last_vertex =
  1582.             clip->proxy->vertices[RIGHT];
  1583.  
  1584.         /* Ensure the vertex loop is closed correctly */
  1585.         tobj->current_contour->vertices->prev =
  1586.             tobj->current_contour->last_vertex;
  1587.         tobj->current_contour->last_vertex->next =
  1588.             tobj->current_contour->vertices;
  1589.  
  1590.         /* Calculate the bounding box, area and orientation */
  1591.         inspect_contour( tobj->current_contour );
  1592.  
  1593.         /* Save the new contour */
  1594.         if ( tobj->contours == NULL )
  1595.         {
  1596.             tobj->current_contour->next =
  1597.             tobj->current_contour->prev = NULL;
  1598.  
  1599.             tobj->contours = tobj->current_contour;
  1600.             tobj->last_contour = tobj->current_contour;
  1601.         }
  1602.         else
  1603.         {
  1604.             tobj->last_contour->next = tobj->current_contour;
  1605.             tobj->current_contour->prev = tobj->last_contour;
  1606.  
  1607.             tobj->last_contour = tobj->current_contour;
  1608.         }
  1609. #ifdef DEBUG
  1610.         contour_dump( tobj->current_contour );
  1611. #endif
  1612.         tobj->current_contour = NULL;
  1613.         }
  1614.  
  1615.         free( clip );
  1616.     }
  1617.  
  1618.     /* Ensure the contour loop is closed correctly */
  1619.     tobj->last_contour->next = tobj->contours;
  1620.     tobj->contours->prev = tobj->last_contour;
  1621.     }
  1622.  
  1623.     MSG( 1, "      <-- output_contours( tobj:%p out:%p )\n", tobj, out );
  1624. }
  1625.  
  1626. /*****************************************************************************
  1627.  * print_contour
  1628.  *****************************************************************************/
  1629. static void print_contour( clip_contour_t *clip )
  1630. {
  1631.     tess_vertex_t    *vertex;
  1632.     GLint        i = 0;
  1633.  
  1634.     MSG( 1, "    contour: %p proxy: %p active: %d\n",
  1635.      clip, clip->proxy, clip->active );
  1636.     MSG( 1, "    l: (%.2f, %.2f) r: (%.2f, %.2f)\n",
  1637.      clip->proxy->vertices[LEFT]->v[X],
  1638.      clip->proxy->vertices[LEFT]->v[Y],
  1639.      clip->proxy->vertices[RIGHT]->v[X],
  1640.      clip->proxy->vertices[RIGHT]->v[Y] );
  1641.  
  1642.     vertex = clip->proxy->vertices[LEFT];
  1643.     do
  1644.     {
  1645.     MSG( 1, "      v: (%.2f, %.2f)\n", vertex->v[X], vertex->v[Y] );
  1646.     vertex = vertex->next;
  1647.     i++;
  1648.     }
  1649.     while ( ( vertex != NULL ) &&
  1650.         ( vertex != clip->proxy->vertices[LEFT] ) &&
  1651.         ( i < 20 ) );
  1652. }
  1653.  
  1654. /*****************************************************************************
  1655.  * print_contours
  1656.  *****************************************************************************/
  1657. static void print_all_contours( clip_contour_t *out )
  1658. {
  1659.     clip_contour_t    *clip;
  1660.  
  1661.     for ( clip = out ; clip ; clip = clip->next )
  1662.     {
  1663.     if ( clip->active ) {
  1664.         print_contour( clip );
  1665.     }
  1666.     }
  1667. }
  1668.  
  1669.  
  1670. /*****************************************************************************
  1671.  * class_string
  1672.  *
  1673.  * Print out the given class as a meaningful string.
  1674.  *****************************************************************************/
  1675. static char *class_string( GLint vclass )
  1676. {
  1677.     switch ( vclass )
  1678.     {
  1679.     case EDGE_EMPTY:
  1680.     return "EMPTY";
  1681.     case EDGE_EXT_MAX:
  1682.     return "EXT_MAX";
  1683.     case EDGE_EXT_LI:
  1684.     return "EXT_LI";
  1685.     case EDGE_TOP:
  1686.     return "TOP";
  1687.     case EDGE_EXT_RI:
  1688.     return "EXT_RI";
  1689.     case EDGE_RIGHT:
  1690.     return "RIGHT";
  1691.     case EDGE_INT_MAX_MIN:
  1692.     return "INT_MAX_MIN";
  1693.     case EDGE_INT_MIN:
  1694.     return "INT_MIN";
  1695.     case EDGE_EXT_MIN:
  1696.     return "EXT_MIN";
  1697.     case EDGE_EXT_MAX_MIN:
  1698.     return "EXT_MAX_MIN";
  1699.     case EDGE_LEFT:
  1700.     return "LEFT";
  1701.     case EDGE_INT_LI:
  1702.     return "INT_LI";
  1703.     case EDGE_BOTTOM:
  1704.     return "BOTTOM";
  1705.     case EDGE_INT_RI:
  1706.     return "INT_RI";
  1707.     case EDGE_INT_MAX:
  1708.     return "INT_MAX";
  1709.     case EDGE_FULL:
  1710.     return "FULL";
  1711.     default:
  1712.     return "UNKNOWN";
  1713.     }
  1714. }
  1715.  
  1716.  
  1717. /*****************************************************************************
  1718.  * tess_clip_polygons
  1719.  *
  1720.  * Perform any contour clipping (boolean operations) on the input contours
  1721.  * as required.
  1722.  *****************************************************************************/
  1723. GLenum tess_clip_polygons( GLUtesselator *tobj )
  1724. {
  1725.     sb_tree_t        *sb_tree = NULL;
  1726.     it_node_t        *it = NULL, *intersect;
  1727.     edge_node_t        *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
  1728.     edge_node_t        *aet = NULL, *heap = NULL;
  1729.     lmt_node_t        *lmt = NULL, *local_min;
  1730.     clip_contour_t    *out_poly = NULL, *p, *q;
  1731.     clip_contour_t    *current[2] = { NULL, NULL };
  1732.     GLint        horiz[2];
  1733.     GLint        in[2], exists[2], parity[2] = { LEFT, LEFT };
  1734.     GLint        contributing, scanbeam = 0, sbt_entries = 0;
  1735.     GLint        vclass, bl, br, tl, tr;
  1736.     GLdouble        *sbt = NULL;
  1737.     GLdouble        xb, prevx, yb = 0.0, yt = 0.0, dy = 0.0;
  1738.     GLdouble        ix = 0.0, iy = 0.0;
  1739.     GLboolean        forward;
  1740.     GLboolean        search;
  1741.     GLint        quadrant;
  1742.  
  1743.     MSG( 1, "    --> clip_polygons( tobj:%p )\n", tobj );
  1744.  
  1745.     /* Break the contour loop for now. */
  1746.     tobj->contours->prev = NULL;
  1747.     tobj->last_contour->next = NULL;
  1748.  
  1749.     /* Build LMT */
  1750.     if ( tobj->num_contours > 0 ) {
  1751.     heap = build_lmt( tobj, &lmt, &sb_tree, &sbt_entries );
  1752.     }
  1753.  
  1754.     /* Return a NULL result if no contours contribute */
  1755.     if ( lmt == NULL )
  1756.     {
  1757.     /* FIXME: Delete all contour entries as well... */
  1758.     tobj->num_contours = 0;
  1759.     tobj->contours = NULL;
  1760.     cleanup_lmt( &lmt );
  1761.     free( heap );
  1762.     return GLU_NO_ERROR;
  1763.     }
  1764.  
  1765.     /* Build scanbeam table from scanbeam tree */
  1766.     sbt = (GLdouble *) malloc( sbt_entries * sizeof(GLdouble) );
  1767.  
  1768.     build_sbt( &scanbeam, sbt, sb_tree );
  1769.     cleanup_sb_tree( &sb_tree );
  1770.  
  1771.     scanbeam = 0;
  1772.     local_min = lmt;
  1773.  
  1774.     MSG( 1, "          processing scanbeams...\n" );
  1775.  
  1776.     while ( scanbeam < sbt_entries )
  1777.     {
  1778.     /* Set yb and yt to the bottom and top of the scanbeam */
  1779.     yb = sbt[scanbeam++];
  1780.     if ( scanbeam < sbt_entries ) {
  1781.         yt = sbt[scanbeam];
  1782.         dy = yt - yb;
  1783.     }
  1784.  
  1785.     MSG( 1, "\n" );
  1786.     MSG( 1, "   ****** scanbeam %d yb: %.2f yt: %.2f dy: %.2f\n", scanbeam - 1, yb, yt, dy );
  1787.     MSG( 1, "\n" );
  1788.  
  1789.     /*
  1790.      * ****** SCANBEAM BOUNDARY PROCESSING ******
  1791.      */
  1792.  
  1793.     /* If LMT node corresponding to yb exists */
  1794.     if ( ( local_min ) && ( local_min->y == yb ) )
  1795.     {
  1796.         /* Add edges starting at this local minimum to the AET */
  1797.         for ( edge = local_min->bounds ; edge ;
  1798.           edge = edge->next_bound )
  1799.         {
  1800.         MSG( 1, "            edge (%.2f, %.2f) -> (%.2f, %.2f)\n",
  1801.              edge->bot[X], edge->bot[Y], edge->top[X], edge->top[Y] );
  1802.  
  1803.         add_edge_to_aet( &aet, edge, NULL );
  1804.         }
  1805.  
  1806.         local_min = local_min->next;
  1807.  
  1808.         MSG( 1, "\n" );
  1809.     }
  1810.  
  1811.     /* Set dummy previous x value */
  1812.     prevx = -DBL_MAX;
  1813.  
  1814.     /* Create bundles within AET */
  1815.     e0 = aet;
  1816.     e1 = aet;
  1817.  
  1818.     /* Set up bundle fields of first edge */
  1819.     aet->bundle[ABOVE][ aet->type] = (GLboolean)( aet->top[Y] != yb );
  1820.     aet->bundle[ABOVE][!aet->type] = GL_FALSE;
  1821.     aet->bstate[ABOVE] = UNBUNDLED;
  1822.  
  1823.     for ( next_edge = aet->next ; next_edge ; next_edge = next_edge->next )
  1824.     {
  1825.         /* Set up bundle fields of next edge */
  1826.         next_edge->bundle[ABOVE][ next_edge->type] =
  1827.         (GLboolean)( next_edge->top[Y] != yb );
  1828.         next_edge->bundle[ABOVE][!next_edge->type] = GL_FALSE;
  1829.         next_edge->bstate[ABOVE] = UNBUNDLED;
  1830.  
  1831.         /* Bundle edges above the scanbeam boundary if they coincide */
  1832.         if ( next_edge->bundle[ABOVE][next_edge->type] )
  1833.         {
  1834.         if ( IS_EQUAL( e0->xbot, next_edge->xbot ) &&
  1835.              IS_EQUAL( e0->dx, next_edge->dx ) &&
  1836.              ( e0->top[Y] != yb ) )
  1837.         {
  1838.             next_edge->bundle[ABOVE][next_edge->type] ^=
  1839.             e0->bundle[ABOVE][next_edge->type];
  1840.  
  1841.             next_edge->bundle[ABOVE][!next_edge->type] =
  1842.             e0->bundle[ABOVE][!next_edge->type];
  1843.  
  1844.             next_edge->bstate[ABOVE] = BUNDLE_HEAD;
  1845.  
  1846.             e0->bundle[ABOVE][CLIP] = GL_FALSE;
  1847.             e0->bundle[ABOVE][SUBJ] = GL_FALSE;
  1848.             e0->bstate[ABOVE] = BUNDLE_TAIL;
  1849.         }
  1850.  
  1851.         e0 = next_edge;
  1852.         }
  1853.  
  1854.         MSG( 1, "            next (%.2f, %.2f) -> (%.2f %.2f)\n",
  1855.          next_edge->bot[X], next_edge->bot[Y],
  1856.          next_edge->top[X], next_edge->top[Y] );
  1857.         MSG( 1, "              bundle: %s state: %s forward: %s\n",
  1858.          ( next_edge->bundle[ABOVE][SUBJ] ) ? "TRUE" : "FALSE",
  1859.          ( next_edge->bstate[ABOVE] == BUNDLE_HEAD ) ? "HEAD" :
  1860.          ( next_edge->bstate[ABOVE] == BUNDLE_TAIL ) ? "TAIL" : "UNBUNDLED",
  1861.          ( next_edge->forward ) ? "TRUE" : "FALSE" );
  1862.  
  1863.     }
  1864.     MSG( 1, "\n" );
  1865.  
  1866.     horiz[CLIP] = HORIZ_NONE;
  1867.     horiz[SUBJ] = HORIZ_NONE;
  1868.  
  1869.     /* Process each edge at this scanbeam boundary */
  1870.     for ( edge = aet ; edge ; edge = edge->next )
  1871.     {
  1872.         exists[CLIP] = edge->bundle[ABOVE][CLIP] +
  1873.         (edge->bundle[BELOW][CLIP] << 1);
  1874.         exists[SUBJ] = edge->bundle[ABOVE][SUBJ] +
  1875.         (edge->bundle[BELOW][SUBJ] << 1);
  1876.  
  1877.         MSG( 1, "            edge (%.2f, %.2f) -> (%.2f, %.2f) e: %d\n",
  1878.          edge->bot[X], edge->bot[Y], edge->top[X], edge->top[Y],
  1879.          exists[SUBJ] );
  1880.  
  1881.         if ( exists[CLIP] || exists[SUBJ] )
  1882.         {
  1883.         MSG( 1, "              parity s: %s forward: %s\n",
  1884.              ( parity[SUBJ] ) ? "RIGHT" : "LEFT",
  1885.              ( edge->forward ) ? "TRUE" : "FALSE" );
  1886.  
  1887.         /* Set bundle side */
  1888.         edge->bside[CLIP] = parity[CLIP];
  1889.         edge->bside[SUBJ] = parity[SUBJ];
  1890.  
  1891.         /* Determine contributing status and quadrant occupancies */
  1892.         contributing = exists[SUBJ];
  1893.  
  1894.         br = ( parity[SUBJ] );
  1895.  
  1896.         bl = ( parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ] );
  1897.  
  1898.         tr = ( parity[SUBJ] ^ ( horiz[SUBJ] != HORIZ_NONE ) );
  1899.  
  1900.         tl = ( parity[SUBJ] ^ ( horiz[SUBJ] != HORIZ_NONE )
  1901.                ^ edge->bundle[BELOW][SUBJ] );
  1902.  
  1903.         /* If the edge has been reversed, swap the flags */
  1904.         if ( ( ( parity[SUBJ] == LEFT ) && edge->forward ) ||
  1905.              ( ( parity[SUBJ] == RIGHT ) && !edge->forward ) )
  1906.         {
  1907.             br = !br; bl = !bl; tr = !tr; tl = !tl;
  1908.         }
  1909.  
  1910.         /* Update parity */
  1911.         parity[CLIP] ^= edge->bundle[ABOVE][CLIP];
  1912.         parity[SUBJ] ^= edge->bundle[ABOVE][SUBJ];
  1913.  
  1914.         /* Update horizontal state */
  1915.         if ( exists[CLIP] )
  1916.         {
  1917.             horiz[CLIP] =
  1918.             next_state[ horiz[CLIP] ][ ((exists[CLIP]-1)<<1) + parity[CLIP] ];
  1919.         }
  1920.         if ( exists[SUBJ] )
  1921.         {
  1922.             horiz[SUBJ] =
  1923.             next_state[ horiz[SUBJ] ][ ((exists[SUBJ]-1)<<1) + parity[SUBJ] ];
  1924.         }
  1925.  
  1926.         vclass = tr + (tl << 1) + (br << 2) + (bl << 3);
  1927.  
  1928.         MSG( 1, "              cont: %d bl: %d br: %d tl: %d tr: %d %s\n",
  1929.              contributing, bl, br, tl, tr, class_string( vclass ) );
  1930.  
  1931.         MSG( 1, "\n" );
  1932.         MSG( 1, "BEFORE:\n" );
  1933.         if ( current[ABOVE] ) {
  1934.             MSG( 1, "  ca:\n" );
  1935.             print_contour( current[ABOVE] );
  1936.         }
  1937.         if ( current[BELOW] ) {
  1938.             MSG( 1, "  cb:\n" );
  1939.             print_contour( current[BELOW] );
  1940.         }
  1941.         if ( edge->out[ABOVE] ) {
  1942.             MSG( 1, "  above:\n" );
  1943.             print_contour( edge->out[ABOVE] );
  1944.         }
  1945.         if ( edge->out[BELOW] ) {
  1946.             MSG( 1, "  below:\n" );
  1947.             print_contour( edge->out[BELOW] );
  1948.         }
  1949.         MSG( 1, "\n" );
  1950.  
  1951.         if ( contributing )
  1952.         {
  1953.             xb = edge->xbot;
  1954.  
  1955.             MSG( 1, "              xb: %.2f px: %.2f\n",
  1956.              xb, ( prevx != -DBL_MAX ) ? prevx : -666.0 );
  1957.             MSG( 1, "                  add (%.2f, %.2f)\n", xb, yb );
  1958.  
  1959.             switch ( vclass )
  1960.             {
  1961.             case EDGE_EXT_MIN:
  1962.             case EDGE_INT_MIN:
  1963.             add_local_min( &out_poly, edge, edge->vertices[BOT] );
  1964.             prevx = xb;
  1965.             current[BELOW] = edge->out[ABOVE];
  1966.             forward = edge->forward;
  1967.             break;
  1968.             case EDGE_EXT_RI:
  1969.             if ( xb != prevx )
  1970.             {
  1971.                 add_right( current[BELOW], edge->vertices[BOT] );
  1972.                 prevx = xb;
  1973.             }
  1974.             edge->out[ABOVE] = current[BELOW];
  1975.             current[BELOW] = NULL;
  1976.             break;
  1977.             case EDGE_EXT_LI:
  1978.             add_left( edge->out[BELOW], edge->vertices[TOP] );
  1979.             prevx = xb;
  1980.             current[BELOW] = edge->out[BELOW];
  1981.             forward = edge->forward;
  1982.             break;
  1983.             case EDGE_EXT_MAX:
  1984.             if ( xb != prevx )
  1985.             {
  1986.                 add_right( current[BELOW], edge->vertices[TOP] );
  1987.                 prevx = xb;
  1988.             }
  1989.             merge_left( current[BELOW], edge->out[BELOW],
  1990.                     out_poly );
  1991.             current[BELOW] = NULL;
  1992.             break;
  1993.             case EDGE_INT_MAX:
  1994.             if ( xb != prevx )
  1995.             {
  1996.                 add_left( current[BELOW], edge->vertices[TOP] );
  1997.                 prevx = xb;
  1998.             }
  1999.             merge_right( current[BELOW], edge->out[BELOW],
  2000.                      out_poly );
  2001.             current[BELOW] = NULL;
  2002.             break;
  2003.             case EDGE_INT_LI:
  2004.             if ( xb != prevx )
  2005.             {
  2006.                 add_left( current[BELOW], edge->vertices[BOT] );
  2007.                 prevx = xb;
  2008.             }
  2009.             edge->out[ABOVE] = current[BELOW];
  2010.             current[BELOW] = NULL;
  2011.             break;
  2012.             case EDGE_INT_RI:
  2013.             add_right( edge->out[BELOW], edge->vertices[TOP] );
  2014.             prevx = xb;
  2015.             current[BELOW] = edge->out[BELOW];
  2016.             edge->out[BELOW] = NULL;
  2017.             break;
  2018.             case EDGE_EXT_MAX_MIN:
  2019.             case EDGE_INT_MAX_MIN:
  2020.             quadrant = find_intersection( tobj, &it,
  2021.                               aet, edge, yb, yt );
  2022.             switch ( quadrant )
  2023.             {
  2024.             case WIND_NE:
  2025.                 if ( xb != prevx ) {
  2026.                 add_right( current[BELOW],
  2027.                        it_vertex( tobj, it ) );
  2028.                 merge_left( current[BELOW], edge->out[BELOW],
  2029.                         out_poly );
  2030.                 }
  2031.                 add_local_min( &out_poly, edge,
  2032.                        it_vertex( tobj, it ) );
  2033.                 prevx = xb;
  2034.                 current[BELOW] = edge->out[ABOVE];
  2035.                 forward = edge->forward;
  2036.                 break;
  2037.             case WIND_SE:
  2038.                 if ( xb != prevx ) {
  2039.                 add_left( current[BELOW],
  2040.                       it_vertex( tobj, it ) );
  2041.                 }
  2042.                 add_left( edge->out[BELOW],
  2043.                       it_vertex( tobj, it ) );
  2044.                 prevx = xb;
  2045.                 edge->out[ABOVE] = current[BELOW];
  2046.                 current[BELOW] = edge->out[BELOW];
  2047.                 break;
  2048.             case WIND_SW:
  2049.                 if ( xb != prevx ) {
  2050.                 add_left( current[BELOW],
  2051.                       it_vertex( tobj, it ) );
  2052.                 merge_right( current[BELOW], edge->out[BELOW],
  2053.                          out_poly );
  2054.                 }
  2055.                 add_local_min( &out_poly, edge,
  2056.                        it_vertex( tobj, it ) );
  2057.                 prevx = xb;
  2058.                 current[BELOW] = edge->out[ABOVE];
  2059.                 forward = edge->forward;
  2060.                 break;
  2061.             case WIND_NW:
  2062.                 if ( xb != prevx ) {
  2063.                 add_right( current[BELOW],
  2064.                        it_vertex( tobj, it ) );
  2065.                 }
  2066.                 add_right( edge->out[BELOW],
  2067.                        it_vertex( tobj, it ) );
  2068.                 prevx = xb;
  2069.                 edge->out[ABOVE] = current[BELOW];
  2070.                 current[BELOW] = edge->out[BELOW];
  2071.                 edge->out[BELOW] = NULL;
  2072.                 break;
  2073.             }
  2074.             break;
  2075.             case EDGE_LEFT:
  2076.             if ( edge->bot[Y] == yb ) {
  2077.                 add_left( edge->out[BELOW], edge->vertices[BOT] );
  2078.             }
  2079.             edge->out[ABOVE] = edge->out[BELOW];
  2080.             prevx = xb;
  2081.             break;
  2082.             case EDGE_RIGHT:
  2083.             if ( edge->bot[Y] == yb ) {
  2084.                 add_right( edge->out[BELOW], edge->vertices[BOT] );
  2085.             }
  2086.             edge->out[ABOVE] = edge->out[BELOW];
  2087.             prevx = xb;
  2088.             break;
  2089.             default:
  2090.             break;
  2091.             }
  2092.         }
  2093.  
  2094.         MSG( 1, "\n" );
  2095.         MSG( 1, "AFTER:\n" );
  2096.         if ( current[BELOW] ) {
  2097.             MSG( 1, "  cb:\n" );
  2098.             print_contour( current[BELOW] );
  2099.         }
  2100.         if ( out_poly ) {
  2101.             MSG( 1, "  out:\n" );
  2102.             print_all_contours( out_poly );
  2103.         }
  2104.         }
  2105.         MSG( 1, "\n" );
  2106.     }
  2107.  
  2108.     /* Delete terminating edges from the AET, otherwise compute xt */
  2109.     for ( edge = aet ; edge ; edge = edge->next )
  2110.     {
  2111.         if ( edge->top[Y] == yb )
  2112.         {
  2113.         prev_edge = edge->prev;
  2114.         next_edge = edge->next;
  2115.  
  2116.         if ( prev_edge ) {
  2117.             prev_edge->next = next_edge;
  2118.         } else {
  2119.             aet= next_edge;
  2120.         }
  2121.  
  2122.         if ( next_edge ) {
  2123.             next_edge->prev = prev_edge;
  2124.         }
  2125.  
  2126.         /* Copy bundle state to the adjacent tail edge if required */
  2127.         if ( ( edge->bstate[BELOW] == BUNDLE_HEAD ) && prev_edge )
  2128.         {
  2129.             if ( prev_edge->bstate[BELOW] == BUNDLE_TAIL )
  2130.             {
  2131.             prev_edge->out[BELOW] = edge->out[BELOW];
  2132.             prev_edge->bstate[BELOW] = UNBUNDLED;
  2133.  
  2134.             if ( ( prev_edge->prev ) &&
  2135.                  ( prev_edge->prev->bstate[BELOW]
  2136.                    == BUNDLE_TAIL ) )
  2137.             {
  2138.                 prev_edge->bstate[BELOW] = BUNDLE_HEAD;
  2139.             }
  2140.             }
  2141.         }
  2142.         }
  2143.         else
  2144.         {
  2145.         if ( edge->top[Y] == yt ) {
  2146.             edge->xtop = edge->top[X];
  2147.         } else {
  2148.             edge->xtop = edge->bot[X]
  2149.             + edge->dx * (yt - edge->bot[Y]);
  2150.         }
  2151.         }
  2152.     }
  2153.  
  2154.     if ( scanbeam < sbt_entries )
  2155.     {
  2156.         /*
  2157.          * ****** SCANBEAM INTERIOR PROCESSING ******
  2158.          */
  2159.  
  2160.         build_intersection_table( tobj, &it, aet, dy );
  2161.  
  2162.         /* Process each node in the intersection table */
  2163.         for ( intersect = it; intersect ; intersect = intersect->next )
  2164.         {
  2165.         e0 = intersect->ie[0];
  2166.         e1 = intersect->ie[1];
  2167.  
  2168.         MSG( 1, "          *** intersect: (%.2f, %.2f) e0: %d e1: %d\n",
  2169.              intersect->v[X], intersect->v[Y],
  2170.              e0->forward, e1->forward );
  2171.  
  2172.         MSG( 1, "            e0 (%.2f, %.2f) -> (%.2f, %.2f)\n",
  2173.              e0->bot[X], e0->bot[Y], e0->top[X], e0->top[Y] );
  2174.         MSG( 1, "            e1 (%.2f, %.2f) -> (%.2f, %.2f)\n",
  2175.              e1->bot[X], e1->bot[Y], e1->top[X], e1->top[Y] );
  2176.  
  2177.         /* Only generate output for contributing intersections */
  2178.         if ( ( e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ] ) &&
  2179.              ( e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ] ) )
  2180.         {
  2181.             p = e0->out[ABOVE];
  2182.             q = e1->out[ABOVE];
  2183.  
  2184.             ix = intersect->v[X];
  2185.             iy = intersect->v[Y];
  2186.  
  2187.             in[CLIP] =
  2188.             (  e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP] ) ||
  2189.             (  e1->bundle[ABOVE][CLIP] &&  e1->bside[CLIP] ) ||
  2190.             ( !e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
  2191.               && e0->bside[CLIP] && e1->bside[CLIP] );
  2192.  
  2193.             in[SUBJ] =
  2194.             (  e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ] ) ||
  2195.             (  e1->bundle[ABOVE][SUBJ] &&  e1->bside[SUBJ] ) ||
  2196.             ( !e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
  2197.                 && e0->bside[SUBJ] && e1->bside[SUBJ] );
  2198.  
  2199.             /* Determine quadrant occupancies */
  2200.             tr = ( in[SUBJ] );
  2201.  
  2202.             tl = ( in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] );
  2203.  
  2204.             br = ( in[SUBJ] ^ e0->bundle[ABOVE][SUBJ] );
  2205.  
  2206.             bl = ( in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]
  2207.                ^ e0->bundle[ABOVE][SUBJ] );
  2208.  
  2209.             vclass = tr + (tl << 1) + (br << 2) + (bl << 3);
  2210.  
  2211.             MSG( 1, "              bl: %d br: %d tl: %d tr: %d %s\n",
  2212.              bl, br, tl, tr, class_string( vclass ) );
  2213.  
  2214.             MSG( 1, "                  add (%.2f, %.2f)\n", ix, iy );
  2215.  
  2216.             MSG( 1, "\n" );
  2217.             MSG( 1, "BEFORE:\n" );
  2218.             if ( p ) {
  2219.             MSG( 1, "  p:\n" );
  2220.             print_contour( p );
  2221.             }
  2222.             if ( q ) {
  2223.             MSG( 1, "  q:\n" );
  2224.             print_contour( q );
  2225.             }
  2226.             if ( e0->out[ABOVE] ) {
  2227.             MSG( 1, "  e0 above:\n" );
  2228.             print_contour( e0->out[ABOVE] );
  2229.             }
  2230.             if ( e0->out[BELOW] ) {
  2231.             MSG( 1, "  e0 below:\n" );
  2232.             print_contour( e0->out[BELOW] );
  2233.             }
  2234.             if ( e1->out[ABOVE] ) {
  2235.             MSG( 1, "  e1 above:\n" );
  2236.             print_contour( e1->out[ABOVE] );
  2237.             }
  2238.             if ( e1->out[BELOW] ) {
  2239.             MSG( 1, "  e1 below:\n" );
  2240.             print_contour( e1->out[BELOW] );
  2241.             }
  2242.             MSG( 1, "\n" );
  2243.  
  2244.             switch ( vclass )
  2245.             {
  2246.             case EDGE_EXT_MIN:
  2247.             add_local_min( &out_poly, e0,
  2248.                        it_vertex( tobj, intersect ) );
  2249.             e1->out[ABOVE] = e0->out[ABOVE];
  2250.             break;
  2251.             case EDGE_EXT_RI:
  2252.             if ( p )
  2253.             {
  2254.                 add_right( p, e1->vertices[BOT] );
  2255.                 e1->out[ABOVE] = p;
  2256.                 e0->out[ABOVE] = NULL;
  2257.             }
  2258.             break;
  2259.             case EDGE_EXT_LI:
  2260.             if ( q )
  2261.             {
  2262.                 add_left( q, e0->vertices[TOP] );
  2263.                 e0->out[ABOVE] = q;
  2264.                 e1->out[ABOVE] = NULL;
  2265.             }
  2266.             break;
  2267.             case EDGE_EXT_MAX:
  2268.             if ( p && q )
  2269.             {
  2270.                 add_left( p, e1->vertices[TOP] );
  2271.                 merge_right( p, q, out_poly );
  2272.                 e0->out[ABOVE] = NULL;
  2273.                 e1->out[ABOVE] = NULL;
  2274.             }
  2275.             break;
  2276.             case EDGE_INT_MIN:
  2277.             add_local_min( &out_poly, e0, e0->vertices[BOT] );
  2278.             e1->out[ABOVE] = e0->out[ABOVE];
  2279.             break;
  2280.             case EDGE_INT_LI:
  2281.             if ( p )
  2282.             {
  2283.                 add_left( p, e1->vertices[BOT] );
  2284.                 e1->out[ABOVE] = p;
  2285.                 e0->out[ABOVE] = NULL;
  2286.             }
  2287.             break;
  2288.             case EDGE_INT_RI:
  2289.             if ( q )
  2290.             {
  2291.                 add_right( q, e0->vertices[TOP] );
  2292.                 e0->out[ABOVE] = q;
  2293.                 e1->out[ABOVE] = NULL;
  2294.             }
  2295.             break;
  2296.             case EDGE_INT_MAX:
  2297.             if ( p && q )
  2298.             {
  2299.                 add_right( p, e1->vertices[TOP] );
  2300.                 merge_left( p, q, out_poly );
  2301.                 e0->out[ABOVE] = NULL;
  2302.                 e1->out[ABOVE] = NULL;
  2303.             }
  2304.             break;
  2305.             case EDGE_INT_MAX_MIN:
  2306.             if ( p && q )
  2307.             {
  2308.                 add_right( p, it_vertex( tobj, intersect ) );
  2309.                 merge_left( p, q, out_poly );
  2310.                 add_local_min( &out_poly, e0,
  2311.                        it_vertex( tobj, intersect ) );
  2312.                 e1->out[ABOVE] = e0->out[ABOVE];
  2313.             }
  2314.             break;
  2315.             case EDGE_EXT_MAX_MIN:
  2316.             if ( p && q )
  2317.             {
  2318.                 if ( e0->forward ) {
  2319.                 add_right( p, it_vertex( tobj, intersect ) );
  2320.                 } else {
  2321.                 add_left( p, it_vertex( tobj, intersect ) );
  2322.                 }
  2323.                 if ( e1->forward ) {
  2324.                 add_right( q, it_vertex( tobj, intersect ) );
  2325.                 } else {
  2326.                 add_left( q, it_vertex( tobj, intersect ) );
  2327.                 }
  2328.  
  2329.                 e0->out[ABOVE] = q;
  2330.                 e1->out[ABOVE] = p;
  2331.             }
  2332.             break;
  2333.             default:
  2334.             break;
  2335.             }
  2336.  
  2337.             MSG( 1, "\n" );
  2338.             MSG( 1, "AFTER:\n" );
  2339.             if ( p ) {
  2340.             MSG( 1, "  p:\n" );
  2341.             print_contour( p );
  2342.             }
  2343.             if ( q ) {
  2344.             MSG( 1, "  q:\n" );
  2345.             print_contour( q );
  2346.             }
  2347.             if ( e0->out[ABOVE] ) {
  2348.             MSG( 1, "  e0 above:\n" );
  2349.             print_contour( e0->out[ABOVE] );
  2350.             }
  2351.             if ( e0->out[BELOW] ) {
  2352.             MSG( 1, "  e0 below:\n" );
  2353.             print_contour( e0->out[BELOW] );
  2354.             }
  2355.             if ( e1->out[ABOVE] ) {
  2356.             MSG( 1, "  e1 above:\n" );
  2357.             print_contour( e1->out[ABOVE] );
  2358.             }
  2359.             if ( e1->out[BELOW] ) {
  2360.             MSG( 1, "  e1 below:\n" );
  2361.             print_contour( e1->out[BELOW] );
  2362.             }
  2363.             if ( out_poly ) {
  2364.             MSG( 1, "  out:\n" );
  2365.             print_all_contours( out_poly );
  2366.             }
  2367.             MSG( 1, "\n" );
  2368.         }
  2369.  
  2370.         /* Swap bundle sides in response to edge crossing */
  2371.         if ( e0->bundle[ABOVE][CLIP] ) {
  2372.             e1->bside[CLIP] = !e1->bside[CLIP];
  2373.         }
  2374.         if ( e1->bundle[ABOVE][CLIP] ) {
  2375.             e0->bside[CLIP] = !e0->bside[CLIP];
  2376.         }
  2377.         if ( e0->bundle[ABOVE][SUBJ] ) {
  2378.             e1->bside[SUBJ] = !e1->bside[SUBJ];
  2379.         }
  2380.         if ( e1->bundle[ABOVE][SUBJ] ) {
  2381.             e0->bside[SUBJ] = !e0->bside[SUBJ];
  2382.         }
  2383.  
  2384.         /* Swap e0 and e1 bundles in the AET */
  2385.         prev_edge = e0->prev;
  2386.         next_edge = e1->next;
  2387.  
  2388.         if ( next_edge ) {
  2389.             next_edge->prev= e0;
  2390.         }
  2391.  
  2392.         if ( e0->bstate[ABOVE] == BUNDLE_HEAD )
  2393.         {
  2394.             search = GL_TRUE;
  2395.  
  2396.             while ( search )
  2397.             {
  2398.             prev_edge = prev_edge->prev;
  2399.  
  2400.             if ( prev_edge )
  2401.             {
  2402.                 if ( prev_edge->bstate[ABOVE] != BUNDLE_TAIL ) {
  2403.                 search = GL_FALSE;
  2404.                 }
  2405.             }
  2406.             else
  2407.             {
  2408.                 search = GL_FALSE;
  2409.             }
  2410.             }
  2411.         }
  2412.  
  2413.         if ( !prev_edge )
  2414.         {
  2415.             aet->prev = e1;
  2416.             e1->next = aet;
  2417.             aet = e0->next;
  2418.         }
  2419.         else
  2420.         {
  2421.             prev_edge->next->prev = e1;
  2422.             e1->next = prev_edge->next;
  2423.             prev_edge->next = e0->next;
  2424.         }
  2425.  
  2426.         e0->next->prev = prev_edge;
  2427.         e1->next->prev = e1;
  2428.         e0->next = next_edge;
  2429.         }
  2430.  
  2431.         /* Prepare for next scanbeam */
  2432.         for ( edge = aet ; edge ; edge = next_edge )
  2433.         {
  2434.         next_edge = edge->next;
  2435.         succ_edge = edge->succ;
  2436.  
  2437.         if ( ( edge->top[Y] == yt ) && succ_edge )
  2438.         {
  2439.             /* Replace AET edge by its successor */
  2440.             succ_edge->out[BELOW] = edge->out[ABOVE];
  2441.             succ_edge->bstate[BELOW] = edge->bstate[ABOVE];
  2442.             succ_edge->bundle[BELOW][CLIP] = edge->bundle[ABOVE][CLIP];
  2443.             succ_edge->bundle[BELOW][SUBJ] = edge->bundle[ABOVE][SUBJ];
  2444.             prev_edge = edge->prev;
  2445.  
  2446.             if ( prev_edge ) {
  2447.             prev_edge->next = succ_edge;
  2448.             } else {
  2449.             aet = succ_edge;
  2450.             }
  2451.  
  2452.             if ( next_edge ) {
  2453.             next_edge->prev = succ_edge;
  2454.             }
  2455.  
  2456.             succ_edge->prev = prev_edge;
  2457.             succ_edge->next = next_edge;
  2458.         }
  2459.         else
  2460.         {
  2461.             /* Update this edge */
  2462.             edge->out[BELOW] = edge->out[ABOVE];
  2463.             edge->bstate[BELOW] = edge->bstate[ABOVE];
  2464.             edge->bundle[BELOW][CLIP] = edge->bundle[ABOVE][CLIP];
  2465.             edge->bundle[BELOW][SUBJ] = edge->bundle[ABOVE][SUBJ];
  2466.             edge->xbot = edge->xtop;
  2467.         }
  2468.  
  2469.         edge->out[ABOVE] = NULL;
  2470.         }
  2471.     }
  2472.     }
  2473.     MSG( 1, "\n" );
  2474.     MSG( 1, "          scanbeam processing complete!\n" );
  2475.  
  2476.     output_contours( tobj, out_poly );
  2477.  
  2478.     cleanup_it( &it );
  2479.     cleanup_lmt( &lmt );
  2480.  
  2481.     if ( heap ) {
  2482.     free( heap );
  2483.     }
  2484.     if ( sbt ) {
  2485.     free( sbt );
  2486.     }
  2487.  
  2488.     MSG( 1, "    <-- clip_polygons( tobj:%p )\n", tobj );
  2489.     return GLU_NO_ERROR;
  2490. }
  2491.