home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src-glu / tess_winding.c < prev    next >
C/C++ Source or Header  |  1999-12-06  |  13KB  |  474 lines
  1. /* $Id: tess_winding.c,v 1.10.2.6 1999/12/05 07:10:49 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 winding rules
  30.  *
  31.  * Gareth Hughes <garethh@bell-labs.com>, August 1999
  32.  *
  33.  *****************************************************************************/
  34.  
  35. #include <stdio.h>
  36. #include <stdlib.h>
  37. #include <math.h>
  38.  
  39. #include "gluP.h"
  40.  
  41. #include "tess.h"
  42. #include "tess_macros.h"
  43. #include "tess_hash.h"
  44. #include "tess_heap.h"
  45. #include "tess_winding.h"
  46.  
  47.  
  48. /*****************************************************************************
  49.  * Internal definitions:
  50.  *****************************************************************************/
  51. #define INSIDE        1
  52. #define OUTSIDE        2
  53.  
  54.  
  55.  
  56. /*****************************************************************************
  57.  *
  58.  *            CONTOUR PREPROCESSING FUNCTIONS
  59.  *
  60.  *****************************************************************************/
  61.  
  62.  
  63. /*****************************************************************************
  64.  * point_contour_test
  65.  *
  66.  * Determine if the given point lies inside the given contour.  Taken from
  67.  *  O'Rourke 1998 p244.
  68.  *****************************************************************************/
  69. GLboolean point_contour_test( tess_contour_t *contour, tess_vertex_t *point )
  70. {
  71.     tess_vertex_t    *vertex = contour->vertices;
  72.     GLint        rcross = 0, lcross = 0;
  73.     GLboolean        rstrad, lstrad;
  74.     GLdouble        x;
  75.     GLint        i;
  76.  
  77.     MSG( 1, "             comparing c: %d p: %d ...\n",
  78.      contour->vertices->index, point->index );
  79.  
  80.     for ( i = 0 ; i < contour->num_vertices ; i++ )
  81.     {
  82.     /*
  83.      * First check if given point is coicident with a vertex on
  84.      *  the contour.
  85.      */
  86.     if ( vertex->index == point->index ) {
  87.         MSG( 1, "               p: %d coincident\n", point->index );
  88.         return GL_TRUE;
  89.     }
  90.  
  91.     /*
  92.      * Check if current edge straddles the horizontal line through
  93.      *  the given point, with bias above/below.
  94.      */
  95.     rstrad = (GLboolean)( ( vertex->v[Y] > point->v[Y] ) !=
  96.                   ( vertex->next->v[Y] > point->v[Y] ) );
  97.     lstrad = (GLboolean)( ( vertex->v[Y] < point->v[Y] ) !=
  98.                   ( vertex->next->v[Y] < point->v[Y] ) );
  99.  
  100.     if ( rstrad || lstrad )
  101.     {
  102.         MSG( 1, "               edge: %d -> %d r: %d l: %d\n",
  103.          vertex->index, vertex->next->index, rstrad, lstrad );
  104.         /*
  105.          * Compute intersection of current edge with the horizontal
  106.          *  line through the given point.
  107.          */
  108.         x = point->v[X] +
  109.         ( ( vertex->v[X] - point->v[X] ) *
  110.           ( vertex->next->v[Y] - point->v[Y] ) -
  111.           ( vertex->next->v[X] - point->v[X] ) *
  112.           ( vertex->v[Y] - point->v[Y] ) )
  113.         / ( vertex->next->v[Y] - vertex->v[Y] );
  114.  
  115.         if ( rstrad && ( x > point->v[X] ) ) rcross++;
  116.         if ( lstrad && ( x < point->v[X] ) ) lcross++;
  117.  
  118.         MSG( 1, "               x: %.2f p: %.2f rc: %d lc: %d\n",
  119.          x, point->v[X], rcross, lcross );
  120.     }
  121.  
  122.     vertex = vertex->next;
  123.     }
  124.  
  125.     MSG( 1, "             rc: %d lc: %d\n", rcross, lcross );
  126.  
  127.     /*
  128.      * Given point is on an edge if left/right cross counts are not the
  129.      *  same parity.
  130.      */
  131.     if ( ( rcross % 2 ) != ( lcross % 2 ) ) {
  132.     MSG( 1, "               p: %d lies on edge\n", point->index );
  133.     return GL_FALSE;
  134.     }
  135.  
  136.     /*
  137.      * Given point
  138.      */
  139.     if ( ( rcross % 2 ) == 1 ) {
  140.     MSG( 1, "               p: %d strictly inside\n", point->index );
  141.     return GL_TRUE;
  142.     } else {
  143.     MSG( 1, "               p: %d strictly outside\n", point->index );
  144.     return GL_FALSE;
  145.     }
  146. }
  147.  
  148. /*****************************************************************************
  149.  * label_contours
  150.  *
  151.  * Label a set of non-intersecting contours as INSIDE or OUTSIDE.
  152.  *****************************************************************************/
  153. static void label_contours( GLUtesselator *tobj )
  154. {
  155.     tess_contour_t    *contour = tobj->contours, *current;
  156.     GLint        i;
  157.  
  158.     MSG( 1, "    -> label_contours( tobj:%p c: %p )\n", tobj, contour );
  159.  
  160.     for ( i = 0 ; i < tobj->num_contours ; i++ )
  161.     {
  162.     /*
  163.      * As our contours have been sorted by size, we can use the first
  164.      * contour as our outer region.
  165.      */
  166.     contour->label = OUTSIDE;
  167.     contour->winding = ( contour->orientation == GLU_CCW ) ? 1 : -1;
  168.  
  169.     if ( contour != tobj->contours )
  170.     {
  171.         current = contour->prev;
  172.         contour->parent = NULL;
  173.  
  174.         while ( current != contour )
  175.         {
  176.         if ( point_contour_test( current, contour->vertices ) )
  177.         {
  178.             contour->label = INSIDE;
  179.             contour->parent = current;
  180.             break;
  181.         }
  182.  
  183.         current = current->prev;
  184.         }
  185.  
  186.         if ( contour->parent != NULL ) {
  187.         contour->winding += contour->parent->winding;
  188.         }
  189.     }
  190.  
  191.     MSG( 1, "           contour %s w: %d orient: %s\n\n",
  192.          ( contour->label == OUTSIDE ) ? "OUTSIDE" : "INSIDE ",
  193.          contour->winding,
  194.          ( contour->orientation == GLU_CCW ) ? "CCW" : "CW" );
  195.  
  196.     contour = contour->next;
  197.     }
  198.  
  199.     MSG( 1, "    <- label_contours( tobj:%p )\n", tobj );
  200. }
  201.  
  202. /*****************************************************************************
  203.  * remove_contour
  204.  *****************************************************************************/
  205. static void remove_contour( GLUtesselator *tobj, tess_contour_t *contour )
  206. {
  207.     if ( tobj->contours == contour ) {
  208.     tobj->contours = contour->next;
  209.     }
  210.     if ( tobj->last_contour == contour ) {
  211.     tobj->last_contour = contour->prev;
  212.     }
  213.  
  214.     contour->prev->next = contour->next;
  215.     contour->next->prev = contour->prev;
  216.  
  217.     tobj->num_contours--;
  218.     tobj->num_vertices -= contour->num_vertices;
  219. }
  220.  
  221. /*****************************************************************************
  222.  * collect_contours
  223.  *****************************************************************************/
  224. static void collect_contours( GLUtesselator *tobj )
  225. {
  226.     tess_contour_t    *contour = tobj->contours, *next;
  227.     GLint        i;
  228.  
  229.     MSG( 1, "    -> collect_contours( tobj:%p )\n", tobj );
  230.  
  231. #ifdef DEBUG
  232.     switch( tobj->winding_rule )
  233.     {
  234.     case GLU_TESS_WINDING_ODD:
  235.     MSG( 1, "         using ODD winding rule\n" );
  236.     break;
  237.     case GLU_TESS_WINDING_NONZERO:
  238.     MSG( 1, "         using NONZERO winding rule\n" );
  239.     break;
  240.     case GLU_TESS_WINDING_POSITIVE:
  241.     MSG( 1, "         using POSITIVE winding rule\n" );
  242.     break;
  243.     case GLU_TESS_WINDING_NEGATIVE:
  244.     MSG( 1, "         using NEGATIVE winding rule\n" );
  245.     break;
  246.     case GLU_TESS_WINDING_ABS_GEQ_TWO:
  247.     MSG( 1, "         using ABS_GEQ_TWO winding rule\n" );
  248.     break;
  249.  
  250.     default:
  251.     MSG( 1, "         using unknown winding rule\n" );
  252.     break;
  253.     }
  254. #endif
  255.  
  256.     for ( i = 0; i < tobj->num_contours; i++ )
  257.     {
  258.     next = contour->next;
  259.  
  260. #ifdef DEBUG
  261.     switch( contour->label )
  262.     {
  263.     case INSIDE:
  264.         MSG( 1, "           contour: %d label: INSIDE  %s %d\n",
  265.          contour->vertices->index, ( contour->orientation == GLU_CCW ) ? "CCW" : "CW", contour->winding );
  266.         break;
  267.     case OUTSIDE:
  268.         MSG( 1, "           contour: %d label: OUTSIDE %s %d\n",
  269.          contour->vertices->index, ( contour->orientation == GLU_CCW ) ? "CCW" : "CW", contour->winding );
  270.         break;
  271.  
  272.     default:
  273.         MSG( 1, "           contour: %p unknown label\n", contour );
  274.         break;
  275.     }
  276. #endif
  277.     switch ( tobj->winding_rule )
  278.     {
  279.     case GLU_TESS_WINDING_ODD:
  280.         if ( ( ABSI( contour->winding ) % 2 ) == 1 )
  281.         {
  282.         if ( contour->orientation != tobj->orientation )
  283.         {
  284.             MSG( 1, "             rev CW -> CCW\n" );
  285.             reverse_contour( contour );
  286.         }
  287.         }
  288.         else
  289.         {
  290.         if ( contour->orientation == tobj->orientation )
  291.         {
  292.             MSG( 1, "             rev CCW -> CW\n" );
  293.             reverse_contour( contour );
  294.         }
  295.         else if ( tobj->contours == contour )
  296.         {
  297.             MSG( 1, "             deleting contour...\n" );
  298.             remove_contour( tobj, contour );
  299.             delete_contour( &contour );
  300.             i--;
  301.         }
  302.         }
  303.         break;
  304.  
  305.     case GLU_TESS_WINDING_NONZERO:
  306.         if ( ABSI( contour->winding ) == 1 )
  307.         {
  308.         if ( contour->orientation != tobj->orientation )
  309.         {
  310.             MSG( 1, "             rev CW -> CCW\n" );
  311.             reverse_contour( contour );
  312.         }
  313.         }
  314.         else if ( contour->winding == 0 )
  315.         {
  316.         if ( contour->orientation == tobj->orientation )
  317.         {
  318.             MSG( 1, "             rev CCW -> CW\n" );
  319.             reverse_contour( contour );
  320.         }
  321.         else if ( tobj->contours == contour )
  322.         {
  323.             MSG( 1, "             deleting contour...\n" );
  324.             remove_contour( tobj, contour );
  325.             delete_contour( &contour );
  326.             i--;
  327.         }
  328.         }
  329.         else if ( ABSI( contour->winding ) > 1 )
  330.         {
  331.         MSG( 1, "             deleting contour...\n" );
  332.         remove_contour( tobj, contour );
  333.         delete_contour( &contour );
  334.         i--;
  335.         }
  336.         break;
  337.  
  338.     case GLU_TESS_WINDING_POSITIVE:
  339.         if ( contour->winding == 1 )
  340.         {
  341.         if ( contour->orientation != tobj->orientation )
  342.         {
  343.             MSG( 1, "             rev CW -> CCW\n" );
  344.             reverse_contour( contour );
  345.         }
  346.         }
  347.         else if ( contour->winding == 0 )
  348.         {
  349.         if ( contour->orientation == tobj->orientation )
  350.         {
  351.             MSG( 1, "             rev CCW -> CW\n" );
  352.             reverse_contour( contour );
  353.         }
  354.         else if ( tobj->contours == contour )
  355.         {
  356.             MSG( 1, "             deleting contour...\n" );
  357.             remove_contour( tobj, contour );
  358.             delete_contour( &contour );
  359.             i--;
  360.         }
  361.         }
  362.         else if ( ( contour->winding < 0 ) ||
  363.               ( contour->winding > 1 ) )
  364.         {
  365.         MSG( 1, "             deleting contour...\n" );
  366.         remove_contour( tobj, contour );
  367.         delete_contour( &contour );
  368.         i--;
  369.         }
  370.         break;
  371.  
  372.     case GLU_TESS_WINDING_NEGATIVE:
  373.         if ( contour->winding == -1 )
  374.         {
  375.         if ( contour->orientation != tobj->orientation )
  376.         {
  377.             MSG( 1, "             rev CW -> CCW\n" );
  378.             reverse_contour( contour );
  379.         }
  380.         }
  381.         else if ( contour->winding == -2 )
  382.         {
  383.         if ( contour->orientation == tobj->orientation )
  384.         {
  385.             MSG( 1, "             rev CCW -> CW\n" );
  386.             reverse_contour( contour );
  387.         }
  388.         else if ( tobj->contours == contour )
  389.         {
  390.             MSG( 1, "             deleting contour...\n" );
  391.             remove_contour( tobj, contour );
  392.             delete_contour( &contour );
  393.             i--;
  394.         }
  395.         }
  396.         else if ( ( contour->winding < -2 ) ||
  397.               ( contour->winding > -1 ) )
  398.         {
  399.         MSG( 1, "             deleting contour...\n" );
  400.         remove_contour( tobj, contour );
  401.         delete_contour( &contour );
  402.         i--;
  403.         }
  404.         break;
  405.  
  406.     case GLU_TESS_WINDING_ABS_GEQ_TWO:
  407.         if ( ABSI( contour->winding ) == 2 )
  408.         {
  409.         if ( contour->orientation != tobj->orientation )
  410.         {
  411.             MSG( 1, "             rev CW -> CCW\n" );
  412.             reverse_contour( contour );
  413.         }
  414.         }
  415.         else if ( ABSI( contour->winding ) == 1 )
  416.         {
  417.         if ( ( contour->orientation == tobj->orientation ) &&
  418.              ( contour->label == INSIDE ) )
  419.         {
  420.             MSG( 1, "             rev CCW -> CW\n" );
  421.             reverse_contour( contour );
  422.         }
  423.         else if ( tobj->contours == contour )
  424.         {
  425.             MSG( 1, "             deleting contour...\n" );
  426.             remove_contour( tobj, contour );
  427.             delete_contour( &contour );
  428.             i--;
  429.         }
  430.         }
  431.         else if ( ( contour->winding == 0 ) ||
  432.               ( ABSI( contour->winding > 2 ) ) )
  433.         {
  434.         MSG( 1, "             deleting contour...\n" );
  435.         remove_contour( tobj, contour );
  436.         delete_contour( &contour );
  437.         i--;
  438.         }
  439.         break;
  440.  
  441.     default:
  442.         break;
  443.     }
  444.  
  445.     contour = next;
  446.     }
  447.  
  448.     MSG( 1, "    <- collect_contours( tobj:%p ) count: %d\n", tobj, tobj->num_contours );
  449. }
  450.  
  451. /*****************************************************************************
  452.  * cleanup
  453.  *
  454.  * Deallocate any memory that we've used in the contour preprocessing.
  455.  *****************************************************************************/
  456. static void cleanup( GLUtesselator *tobj )
  457. {
  458.     /* FIXME: We don't seem to need to do anything in here anymore... */
  459. }
  460.  
  461. /*****************************************************************************
  462.  * tess_preprocess_contours
  463.  *****************************************************************************/
  464. GLenum tess_preprocess_contours( GLUtesselator *tobj )
  465. {
  466.     label_contours( tobj );
  467.  
  468.     collect_contours( tobj );
  469.  
  470.     cleanup( tobj );
  471.  
  472.     return GLU_NO_ERROR;
  473. }
  474.