home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume38 / tessel / part01 / tessel.c < prev    next >
C/C++ Source or Header  |  1993-06-20  |  12KB  |  344 lines
  1. /*+-----------------------------------------------------------------------+
  2.  *| This file contains subroutines used to tesselate convex and concave   |
  3.  *| N-point polygons into triangles. At present, it does not handle       |
  4.  *| complex polygons.                                                     |
  5.  *|                                                                       |
  6.  *| Author: Michael S. A. Robb         Version: 1.1        Date: 29/05/93 |
  7.  *+-----------------------------------------------------------------------+
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12.  
  13. #include "triangle.h"
  14. #include "tessel.h"
  15.  
  16. /*
  17.  *+-----------------------------------------------------------------------+
  18.  *| These global variables are used to reference the polygon vertex list. |
  19.  *+-----------------------------------------------------------------------+
  20.  */
  21.  
  22. void (*polygon_proc)( COORD *triangle );    /* User defined function.    */
  23.  
  24. /*                                                                                                    
  25.  *+-----------------------------------------------------------------------+
  26.  *| This subroutine is used to set the user-defined procedure called to   |
  27.  *| render a triangle.                                                    |
  28.  *+-----------------------------------------------------------------------+
  29.  */
  30.  
  31. void polygon_setproc( proc )
  32.   void (*proc)();
  33.   {
  34.   polygon_proc = proc;                    /* Set the polygon procedure.  */
  35.   }
  36.  
  37. /*
  38.  *+-----------------------------------------------------------------------+
  39.  *| This subroutine is used to reverse the coordinates in the polygon     |
  40.  *| vertex list. Used to handle anti-clockwise ordering of vertices.      |
  41.  *+-----------------------------------------------------------------------+
  42.  */
  43.  
  44. void polygon_reverse( nverts, vlist )
  45.   int nverts;
  46.   COORD *vlist;
  47.   {
  48.   COORD temp;                             /* Used for copying.           */
  49.   int   from = 0, to = nverts;            /* Start and finish of list.   */
  50.  
  51.   while ( ++from < --to )                 /* Swap until both ends meet.  */
  52.     {
  53.     temp        = vlist[from];
  54.     vlist[from] = vlist[to];
  55.     vlist[to]   = temp;
  56.     }
  57.   }
  58.  
  59. /*
  60.  *+------------------------------------------------------------------------+
  61.  *| This suboutine is used to determine the intersection between the line  |
  62.  *| vectors from P1 to P2 and P3 to P4. A result of TRUE is returned if    |
  63.  *| the two vectors intersect within the end-points, and <point> is filled |
  64.  *| with the point of intersection. Otherwise, a result of FALSE occurs.   |
  65.  *+------------------------------------------------------------------------+
  66.  */
  67.  
  68. int coord_intersection( point, p1, p2, p3, p4 )
  69.   COORD *point,
  70.         *p1, *p2,
  71.         *p3, *p4;
  72.   {
  73.   MATDATA val_det, val_t, val_s;           /* Determinants of matrices.  */
  74.  
  75.   val_det = MATRIX_DET_2X2( *p1, *p2, *p3, *p4 );
  76.  
  77.   if ( val_det != 0 )                      /* Intersection point exists? */
  78.     {
  79.     val_t = MATRIX_DET_2X2( *p1, *p3, *p3, *p4 )
  80.           * CONSTANT_ONE / val_det;
  81.  
  82.     val_s = MATRIX_DET_2X2( *p1, *p2, *p3, *p1 )
  83.           * CONSTANT_ONE / val_det;
  84.  
  85.     if ( val_t <= 0L && val_s >= CONSTANT_ONE || /* Within range of edge */
  86.          val_s <= 0L && val_t >= CONSTANT_ONE )  /* segments?            */
  87.       /* Do nothing */
  88.       {}
  89.     else
  90.     if ( val_t >= 0 && val_t <= CONSTANT_ONE && /* Are results within    */
  91.          val_s >= 0 && val_s <= CONSTANT_ONE )  /* bounds of the two     */
  92.       {                                         /* edges?                */
  93.  
  94.       point -> c_xpos                           /* Calculate X coordinate. */
  95.           = p1 -> c_xpos
  96.           + (int)( val_t * ( p2 -> c_xpos - p1 -> c_xpos ) / CONSTANT_ONE );
  97.  
  98.       point -> c_ypos                           /* Calculate Y coordinate. */
  99.           = p1 -> c_ypos
  100.           + (int)( val_t * ( p2 -> c_ypos - p1 -> c_ypos ) / CONSTANT_ONE );
  101.  
  102.       return( 1 );
  103.       }
  104.     }
  105.  
  106.   return( 0 );
  107.   }
  108.  
  109. /*
  110.  *+-----------------------------------------------------------------------+
  111.  *| This subroutine is used to determine whether the given polygon is     |
  112.  *| bow-tied or not (has edges which cross over ie. bow-tie). A result of |
  113.  *| TRUE is returned if the polygon is bow-tied. Otherwise, a result of   |
  114.  *| FALSE is returned.                                                    |
  115.  *+-----------------------------------------------------------------------+
  116.  */
  117.  
  118. int polygon_complex( nverts, vertlist )
  119.   int    nverts;
  120.   COORD *vertlist;
  121.   {
  122.   int          m, n, i, j;                  /* Loop counters             */
  123.   static COORD point;                       /* Point of intersection.    */
  124.  
  125.   if ( nverts <= 3 )                        /* Triangles can never be    */
  126.     return( 0 );                            /* bow-tied.                 */
  127.  
  128.   for ( m = 0, n = 1; n < nverts; m++, n++) /* First edge segment.       */
  129.     for ( i = n; i < nverts; i++ )          /* Second edge segment.      */
  130.       {
  131.       j = ( i+1 == nverts ? 0 : i+1 );
  132.  
  133.       if ( coord_intersection( &point,      /* Check for intersection of */
  134.              vertlist+m, vertlist+n,        /* edges.                    */
  135.              vertlist+i, vertlist+j ) )
  136.         return( 1 );                        /* Intersection exists, so   */
  137.       }                                     /* the polygon is bow-tied.  */
  138.  
  139.   return( 0 );                              /* Polygon is not bow-tied.  */
  140.   }
  141.  
  142. /*
  143.  *+-----------------------------------------------------------------------+
  144.  *| This subroutine is used to determine whether the vertices of the      |
  145.  *| polygon are ordered clockwise or anticlockwise. A result of TRUE is   |
  146.  *| returned for clockwise polygons. A result of FALSE is returned for    |
  147.  *| anticlockwise polygons.                                               |
  148.  *+-----------------------------------------------------------------------+
  149.  */
  150.  
  151. int polygon_clockwise( nverts, vlist )
  152.   int    nverts;
  153.   COORD *vlist;
  154.   {
  155.   int  n, p, q = 0, r;                      /* Vertex indices/counters.  */
  156.   MATDATA lowx_val = vlist[0].c_xpos;       /* Used for X coord. checks. */
  157.   MATDATA lowy_val = vlist[0].c_ypos;       /* Used for Y coord. checks. */
  158.  
  159.   for ( n = 1; n < nverts; n++ )            /* For each vertex.          */
  160.     if ( vlist[n].c_xpos < lowx_val )       /* Vertex has lower X coord? */
  161.       {
  162.       q        = n;                         /* Yes, so set index and     */
  163.       lowx_val = vlist[n].c_xpos;           /* the best X coordinate.    */
  164.       lowy_val = vlist[n].c_ypos;
  165.       }
  166.     else
  167.       if (vlist[n].c_xpos == lowx_val &&    /* No, but is X coord. equal */
  168.           vlist[n].c_ypos  < lowy_val )     /* and Y coordinate lower?   */
  169.         {
  170.         q        = n;                       /* Yes, so set index and the */
  171.         lowy_val = vlist[n].c_ypos;         /* best Y coordinate.        */
  172.         }
  173.  
  174.   p = ( q > 0        ? q-1 : nverts-1 );    /* Find index values of the  */
  175.   r = ( q < nverts-1 ? q+1 : 0        );    /* adjacent vertices.        */
  176.  
  177.   return( ANGLE_CONVEX( vlist, p, q, r ) ); /* Then return the result of */
  178.   }                                         /* the convex angle test.    */
  179.  
  180. /*
  181.  *+-----------------------------------------------------------------------+
  182.  *| This subroutine is used to determine whether the polygon is convex or |
  183.  *| not. It returns a Boolean value of TRUE for convex polygons. FALSE is |
  184.  *| returned for concave polygons.                                        |
  185.  *+-----------------------------------------------------------------------+
  186.  */
  187.  
  188. int polygon_convex( nverts, vlist )
  189.   int    nverts;
  190.   COORD *vlist;
  191.   {
  192.   int p = 0, q = 1, r = 2;                  /* Vertex indices/counters.  */
  193.  
  194.   if ( nverts == 3 )                        /* Triangle is always convex */
  195.     return( 1 );                            /* So return immediately.    */
  196.  
  197.   for ( p = 0; p < nverts; p++ )            /* For each vertex.          */
  198.     {
  199.     if ( ANGLE_NONCONVEX( vlist, p, q, r) ) /* Is angle <= 90 degrees?   */
  200.       return( 0 );                          /* Yes, polygon is concave.  */
  201.  
  202.     q = ( ++q == nverts ? 0 : q );          /* Update second vertex.     */
  203.     r = ( ++r == nverts ? 0 : r );          /* Update third vertex.      */
  204.     }
  205.                                                                                                 
  206.   return( 1 );                              /* Polygon is convex.        */
  207.   }
  208.  
  209. /* 
  210.  *+-----------------------------------------------------------------------+
  211.  *| This subroutine is used to render the polygon in the display buffer.  |
  212.  *+-----------------------------------------------------------------------+
  213.  */
  214.  
  215. void store_triangle( vlist, p, q, r )
  216.   COORD *vlist;
  217.   int p, q, r;
  218.   {
  219.   static COORD triangle_table[3];           /* Used to render triangle.  */
  220.  
  221.   triangle_table[0] = vlist[p];             /* Copy the three vertices.  */
  222.   triangle_table[1] = vlist[q];
  223.   triangle_table[2] = vlist[r];
  224.  
  225.   (*polygon_proc)( triangle_table );        /* Call the user process.    */
  226.   }
  227.  
  228. /*
  229.  *+-----------------------------------------------------------------------+
  230.  *| This subroutine is used to process simple (convex) polygons.          |
  231.  *+-----------------------------------------------------------------------+
  232.  */
  233.  
  234. void polygon_tesselate_convex( nverts, vlist )
  235.   int    nverts;
  236.   COORD *vlist;
  237.   {
  238.   int n, p = 0, q = 1, r = 2;               /* Vertex indices/counters.  */
  239.  
  240.   for ( n = 0; n < nverts - 2; n++ )        /* For each vertex.          */
  241.     {
  242.     store_triangle( vlist, p, q, r );       /* Render triangle PQR.      */
  243.  
  244.     q = ( q+1 == nverts ? 0 : q+1 );        /* P remains the same, but Q */
  245.     r = ( r+1 == nverts ? 0 : r+1 );        /* and R are incremented.    */
  246.     }
  247.   }
  248.  
  249. /*
  250.  *+-----------------------------------------------------------------------+
  251.  *| This subroutine is used to process complex (concave) polygons.        |
  252.  *+-----------------------------------------------------------------------+
  253.  */
  254.  
  255. #define REMOVE_VERTEX( CL, I, N )\
  256.   { int v; for ( v = (I); v < (N); v++ ) CL[v] = CL[v+1]; }
  257.  
  258. void polygon_tesselate_concave( n, cl )
  259.   int    n;
  260.   COORD *cl;
  261.   {
  262.   int h, i, j, k, m;
  263.  
  264.   i = n-1;
  265.  
  266.   while (n > 3 )
  267.     {
  268.     h = i;
  269.     i = (i == n-1 ? 0 : i+1);
  270.     j = (i == n-1 ? 0 : i+1);
  271.  
  272.     if ( ANGLE_NONCONVEX( cl, h, i, j ) )
  273.       continue;
  274.  
  275.     k = (j == n-1 ? 0 : j+1);               /* k is vertex after j  */
  276.     m = n-3;
  277.  
  278.     while (m--)
  279.       if ( COORD_OUTSIDE_TRIANGLE( cl, h, i, j, k ) )
  280.         k = (k == n-1 ? 0 : k+1);
  281.       else
  282.         break;
  283.  
  284.       if (k != h)                            /* Vertex k not outside */
  285.         continue;                            /*   triangle PhPiPj    */
  286.  
  287.     store_triangle( cl, h, i, j );
  288.  
  289.     REMOVE_VERTEX( cl, i, n );
  290.     n--;
  291.     i = (i == 0 ? n-1 : i-1);
  292.     }
  293.  
  294.   store_triangle( cl, 0, 1, 2 );            /* Final triangle.      */
  295.   }
  296.  
  297. /*
  298.  *+-----------------------------------------------------------------------+
  299.  *| This subroutine is used to render non-complex polygons.               |
  300.  *+-----------------------------------------------------------------------+
  301.  */
  302.  
  303. void polygon_tesselate_noncomplex( num, vl )
  304.   int    num;
  305.   COORD *vl;
  306.   {
  307.   if ( !polygon_clockwise( num, vl ) )      
  308.     polygon_reverse( num, vl );             
  309.  
  310.   if ( polygon_convex( num, vl ) )          
  311.     polygon_tesselate_convex( num, vl );    
  312.   else                                      
  313.     polygon_tesselate_concave( num, vl );   
  314.   }                                         
  315.  
  316. /*
  317.  *+-----------------------------------------------------------------------+
  318.  *| This subroutine is used to render complex polygons.                   |
  319.  *+-----------------------------------------------------------------------+
  320.  */
  321.  
  322. void polygon_tesselate_complex( num, vl )
  323.   int    num;
  324.   COORD *vl;
  325.   {
  326.   /* ... to be implemented in the near future ... */
  327.   }
  328.  
  329. /*
  330.  *+-----------------------------------------------------------------------+
  331.  *| This subroutine is used to render all types of polygon.               |
  332.  *+-----------------------------------------------------------------------+
  333.  */
  334.  
  335. void polygon_tesselate( num, vl )
  336.   int    num;                               
  337.   COORD *vl;                                
  338.   {
  339.   if ( polygon_complex( num, vl ) )         
  340.     polygon_tesselate_complex( num, vl );   
  341.   else
  342.     polygon_tesselate_noncomplex( num, vl );
  343.   }                                         
  344.