home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Assembler / dse-src3.dms / in.adf / Source / Vectors / Poly2Tri.lha / polygon2triangles.c
Encoding:
C/C++ Source or Header  |  1993-01-06  |  7.0 KB  |  283 lines
  1. /*
  2.  * poly_tri.c
  3.  *
  4.  * Program to take a polygon definition and convert it into triangles
  5.  * that may then be rendered by the standard triangle rendering
  6.  * algorithms.  This assumes all transformations have been performed
  7.  * already and cuts them up into optimal triangles based on their
  8.  * screen-space representation.
  9.  *
  10.  *    Copyright (c) 1988, Evans & Sutherland Computer Corporation
  11.  *
  12.  * Permission to use all or part of this program without fee is
  13.  * granted provided that it is not used or distributed for direct
  14.  * commercial gain, the above copyright notice appears, and
  15.  * notice is given that use is by permission of Evans & Sutherland
  16.  * Computer Corporation.
  17.  *
  18.  *    Written by Reid Judd and Scott R. Nelson at
  19.  *    Evans & Sutherland Computer Corporation (January, 1988)
  20.  *
  21.  * To use this program, either write your own "draw_triangle" routine
  22.  * that can draw triangles from the definitions below, or modify the
  23.  * code to call your own triangle or polygon rendering code.  Call
  24.  * "draw_poly" from your main program.
  25.  */
  26.  
  27. #include <stdio.h>
  28.  
  29.  
  30. /* A single vertex */
  31.  
  32. typedef struct {
  33.     int color;        /* RGB */
  34.     float x;
  35.     float y;
  36.     float z;
  37. } vertex;
  38.  
  39.  
  40. /* A triangle made up of three vertices */
  41.  
  42. typedef vertex triangle[3];
  43.  
  44.  
  45. #define V_MAX 100    /* Maximum number of vertices allowed (arbitrary) */
  46.  
  47. #define BIG 1.0e30    /* A number bigger than we expect to find here */
  48.  
  49. #define COUNTER_CLOCKWISE 0
  50. #define CLOCKWISE 1
  51.  
  52.  
  53.  
  54. /*
  55.  * orientation
  56.  *
  57.  * Return either clockwise or counter_clockwise for the orientation
  58.  * of the polygon.
  59.  */
  60.  
  61. int orientation( n, v )
  62.     int n;            /* Number of vertices */
  63.     vertex v[];            /* The vertex list */
  64. {
  65.     float area;
  66.     int i;
  67.  
  68.     /* Do the wrap-around first */
  69.     area = v[n-1].x * v[0].y - v[0].x * v[n-1].y;
  70.  
  71.     /* Compute the area (times 2) of the polygon */
  72.     for (i = 0; i < n-1; i++)
  73.     area += v[i].x * v[i+1].y - v[i+1].x * v[i].y;
  74.  
  75.     if (area >= 0.0)
  76.     return COUNTER_CLOCKWISE;
  77.     else
  78.     return CLOCKWISE;
  79. } /* End of orientation */
  80.  
  81.  
  82.  
  83. /*
  84.  * determinant
  85.  *
  86.  * Computes the determinant of the three points.
  87.  * Returns whether the triangle is clockwise or counter-clockwise.
  88.  */
  89.  
  90. int determinant( p1, p2, p3, v )
  91.     int p1, p2, p3;        /* The vertices to consider */
  92.     vertex v[];            /* The vertex list */
  93. {
  94.     float x1, x2, x3, y1, y2, y3;
  95.     float determ;
  96.  
  97.     x1 = v[p1].x;
  98.     y1 = v[p1].y;
  99.     x2 = v[p2].x;
  100.     y2 = v[p2].y;
  101.     x3 = v[p3].x;
  102.     y3 = v[p3].y;
  103.  
  104.     determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
  105.     if (determ >= 0.0)
  106.     return COUNTER_CLOCKWISE;
  107.     else
  108.     return CLOCKWISE;
  109. } /* End of determinant */
  110.  
  111.  
  112.  
  113. /*
  114.  * distance2
  115.  *
  116.  * Returns the square of the distance between the two points
  117.  */
  118.  
  119. float distance2( x1, y1, x2, y2 )
  120.     float x1, y1, x2, y2;
  121. {
  122.     float xd, yd;        /* The distances in X and Y */
  123.     float dist2;        /* The square of the actual distance */
  124.  
  125.     xd = x1 - x2;
  126.     yd = y1 - y2;
  127.     dist2 = xd * xd + yd * yd;
  128.  
  129.     return dist2;
  130. } /* End of distance2 */
  131.  
  132.  
  133.  
  134. /*
  135.  * no_interior
  136.  *
  137.  * Returns 1 if no other point in the vertex list is inside
  138.  * the triangle specified by the three points.  Returns
  139.  * 0 otherwise.
  140.  */
  141.  
  142. int no_interior( p1, p2, p3, v, vp, n, poly_or )
  143.     int p1, p2, p3;        /* The vertices to consider */
  144.     vertex v[];            /* The vertex list */
  145.     int vp[];            /* The vertex pointers (which are left) */
  146.     int n;            /* Number of vertices */
  147.     int poly_or;        /* Polygon orientation */
  148. {
  149.     int i;            /* Iterative counter */
  150.     int p;            /* The test point */
  151.  
  152.     for (i = 0; i < n; i++) {
  153.     p = vp[i];        /* The point to test */
  154.     if ((p == p1) || (p == p2) || (p == p3))
  155.         continue;        /* Don't bother checking against yourself */
  156.     if (   (determinant( p2, p1, p, v ) == poly_or)
  157.         || (determinant( p1, p3, p, v ) == poly_or)
  158.         || (determinant( p3, p2, p, v ) == poly_or) ) {
  159.         continue;        /* This point is outside */
  160.     } else {
  161.         return 0;        /* The point is inside */
  162.     }
  163.     }
  164.     return 1;            /* No points inside this triangle */
  165. } /* End of no_interior */
  166.  
  167.  
  168.  
  169. /*
  170.  * draw_poly
  171.  *
  172.  * Call this procedure with a polygon, this divides it into triangles
  173.  * and calls the triangle routine once for each triangle.
  174.  *
  175.  * Note that this does not work for polygons with holes or self
  176.  * penetrations.
  177.  */
  178.  
  179. draw_poly( n, v )
  180.     int n;            /* Number of vertices in triangle */
  181.     vertex v[];            /* The vertex list (implicit closure) */
  182. {
  183.     int prev, cur, next;    /* Three points currently being considered */
  184.     int vp[V_MAX];        /* Pointers to vertices still left */
  185.     int count;            /* How many vertices left */
  186.     int min_vert;        /* Vertex with minimum distance */
  187.     int i;            /* Iterative counter */
  188.     float dist;            /* Distance across this one */
  189.     float min_dist;        /* Minimum distance so far */
  190.     int poly_orientation;    /* Polygon orientation */
  191.     triangle t;            /* Triangle structure */
  192.  
  193.     if (n > V_MAX) {
  194.     fprintf( stderr, "Error, more than %d vertices.\n", V_MAX);
  195.     return;
  196.     }
  197.  
  198.     poly_orientation = orientation( n, v );
  199.  
  200.     for (i = 0; i < n; i++)
  201.     vp[i] = i;        /* Put vertices in order to begin */
  202.  
  203. /* Slice off clean triangles until nothing remains */
  204.  
  205.     count = n;
  206.     while (count > 3) {
  207.     min_dist = BIG;        /* A real big number */
  208.     min_vert = 0;        /* Just in case we don't find one... */
  209.     for (cur = 0; cur < count; cur++) {
  210.         prev = cur - 1;
  211.         next = cur + 1;
  212.         if (cur == 0)    /* Wrap around on the ends */
  213.         prev = count - 1;
  214.         else if (cur == count)
  215.         next = 0;
  216.         /* Pick out shortest distance that forms a good triangle */
  217.         if (   (determinant( vp[prev], vp[cur], vp[next], v ) == poly_orientation)
  218.             /* Same orientation as polygon */
  219.         && no_interior( vp[prev], vp[cur], vp[next], v, vp, count, poly_orientation )
  220.             /* No points inside */
  221.         && ((dist = distance2( v[vp[prev]].x, v[vp[prev]].y,
  222.                        v[vp[next]].x, v[vp[next]].y )) < min_dist) )
  223.             /* Better than any so far */
  224.         {
  225.         min_dist = dist;
  226.         min_vert = cur;
  227.         }
  228.     } /* End of for each vertex (cur) */
  229.  
  230.     /* The following error should "never happen". */
  231.     if (min_dist == BIG)
  232.         fprintf( stderr, "Error: Didn't find a triangle.\n" );
  233.  
  234.     prev = min_vert - 1;
  235.     next = min_vert + 1;
  236.     if (min_vert == 0)    /* Wrap around on the ends */
  237.         prev = count - 1;
  238.     else if (min_vert == count)
  239.         next = 0;
  240.  
  241. /* Output this triangle */
  242.  
  243.     t[0].x = v[vp[prev]].x;
  244.     t[0].y = v[vp[prev]].y;
  245.     t[0].z = v[vp[prev]].z;
  246.     t[0].color = v[vp[prev]].color;
  247.     t[1].x = v[vp[min_vert]].x;
  248.     t[1].y = v[vp[min_vert]].y;
  249.     t[1].z = v[vp[min_vert]].z;
  250.     t[1].color = v[vp[min_vert]].color;
  251.     t[2].x = v[vp[next]].x;
  252.     t[2].y = v[vp[next]].y;
  253.     t[2].z = v[vp[next]].z;
  254.     t[2].color = v[vp[next]].color;
  255.  
  256.     draw_triangle( t );
  257.  
  258. /* Remove the triangle from the polygon */
  259.  
  260.     count -= 1;
  261.     for (i = min_vert; i < count; i++)
  262.         vp[i] = vp[i+1];
  263.     }
  264.  
  265. /* Output the final triangle */
  266.  
  267.     t[0].x = v[vp[0]].x;
  268.     t[0].y = v[vp[0]].y;
  269.     t[0].z = v[vp[0]].z;
  270.     t[0].color = v[vp[0]].color;
  271.     t[1].x = v[vp[1]].x;
  272.     t[1].y = v[vp[1]].y;
  273.     t[1].z = v[vp[1]].z;
  274.     t[1].color = v[vp[1]].color;
  275.     t[2].x = v[vp[2]].x;
  276.     t[2].y = v[vp[2]].y;
  277.     t[2].z = v[vp[2]].z;
  278.     t[2].color = v[vp[2]].color;
  279.  
  280.     draw_triangle( t );
  281.  
  282. } /* End of draw_poly */
  283. /* End of poly_tri.c */