Polygon to Triangles ```/* * poly_tri.c * * Program to take a polygon definition and convert it into triangles * that may then be rendered by the standard triangle rendering * algorithms. This assumes all transformations have been performed * already and cuts them up into optimal triangles based on their * screen-space representation. * * Copyright (c) 1988, Evans & Sutherland Computer Corporation * * Permission to use all or part of this program without fee is * granted provided that it is not used or distributed for direct * commercial gain, the above copyright notice appears, and * notice is given that use is by permission of Evans & Sutherland * Computer Corporation. * * Written by Reid Judd and Scott R. Nelson at * Evans & Sutherland Computer Corporation (January, 1988) * * To use this program, either write your own "draw_triangle" routine * that can draw triangles from the definitions below, or modify the * code to call your own triangle or polygon rendering code. Call * "draw_poly" from your main program. */ #include /* A single vertex */ typedef struct { int color; /* RGB */ float x; float y; float z; } vertex; /* A triangle made up of three vertices */ typedef vertex triangle; #define V_MAX 100 /* Maximum number of vertices allowed (arbitrary) */ #define BIG 1.0e30 /* A number bigger than we expect to find here */ #define COUNTER_CLOCKWISE 0 #define CLOCKWISE 1 /* * orientation * * Return either clockwise or counter_clockwise for the orientation * of the polygon. */ int orientation( n, v ) int n; /* Number of vertices */ vertex v[]; /* The vertex list */ { float area; int i; /* Do the wrap-around first */ area = v[n-1].x * v.y - v.x * v[n-1].y; /* Compute the area (times 2) of the polygon */ for (i = 0; i < n-1; i++) area += v[i].x * v[i+1].y - v[i+1].x * v[i].y; if (area >= 0.0) return COUNTER_CLOCKWISE; else return CLOCKWISE; } /* End of orientation */ /* * determinant * * Computes the determinant of the three points. * Returns whether the triangle is clockwise or counter-clockwise. */ int determinant( p1, p2, p3, v ) int p1, p2, p3; /* The vertices to consider */ vertex v[]; /* The vertex list */ { float x1, x2, x3, y1, y2, y3; float determ; x1 = v[p1].x; y1 = v[p1].y; x2 = v[p2].x; y2 = v[p2].y; x3 = v[p3].x; y3 = v[p3].y; determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1); if (determ >= 0.0) return COUNTER_CLOCKWISE; else return CLOCKWISE; } /* End of determinant */ /* * distance2 * * Returns the square of the distance between the two points */ float distance2( x1, y1, x2, y2 ) float x1, y1, x2, y2; { float xd, yd; /* The distances in X and Y */ float dist2; /* The square of the actual distance */ xd = x1 - x2; yd = y1 - y2; dist2 = xd * xd + yd * yd; return dist2; } /* End of distance2 */ /* * no_interior * * Returns 1 if no other point in the vertex list is inside * the triangle specified by the three points. Returns * 0 otherwise. */ int no_interior( p1, p2, p3, v, vp, n, poly_or ) int p1, p2, p3; /* The vertices to consider */ vertex v[]; /* The vertex list */ int vp[]; /* The vertex pointers (which are left) */ int n; /* Number of vertices */ int poly_or; /* Polygon orientation */ { int i; /* Iterative counter */ int p; /* The test point */ for (i = 0; i < n; i++) { p = vp[i]; /* The point to test */ if ((p == p1) || (p == p2) || (p == p3)) continue; /* Don't bother checking against yourself */ if ( (determinant( p2, p1, p, v ) == poly_or) || (determinant( p1, p3, p, v ) == poly_or) || (determinant( p3, p2, p, v ) == poly_or) ) { continue; /* This point is outside */ } else { return 0; /* The point is inside */ } } return 1; /* No points inside this triangle */ } /* End of no_interior */ /* * draw_poly * * Call this procedure with a polygon, this divides it into triangles * and calls the triangle routine once for each triangle. * * Note that this does not work for polygons with holes or self * penetrations. */ draw_poly( n, v ) int n; /* Number of vertices in triangle */ vertex v[]; /* The vertex list (implicit closure) */ { int prev, cur, next; /* Three points currently being considered */ int vp[V_MAX]; /* Pointers to vertices still left */ int count; /* How many vertices left */ int min_vert; /* Vertex with minimum distance */ int i; /* Iterative counter */ float dist; /* Distance across this one */ float min_dist; /* Minimum distance so far */ int poly_orientation; /* Polygon orientation */ triangle t; /* Triangle structure */ if (n > V_MAX) { fprintf( stderr, "Error, more than %d vertices.\n", V_MAX); return; } poly_orientation = orientation( n, v ); for (i = 0; i < n; i++) vp[i] = i; /* Put vertices in order to begin */ /* Slice off clean triangles until nothing remains */ count = n; while (count > 3) { min_dist = BIG; /* A real big number */ min_vert = 0; /* Just in case we don't find one... */ for (cur = 0; cur < count; cur++) { prev = cur - 1; next = cur + 1; if (cur == 0) /* Wrap around on the ends */ prev = count - 1; else if (cur == count - 1) next = 0; /* Pick out shortest distance that forms a good triangle */ if ( (determinant( vp[prev], vp[cur], vp[next], v ) == poly_orientation) /* Same orientation as polygon */ && no_interior( vp[prev], vp[cur], vp[next], v, vp, count, poly_orientation ) /* No points inside */ && ((dist = distance2( v[vp[prev]].x, v[vp[prev]].y, v[vp[next]].x, v[vp[next]].y )) < min_dist) ) /* Better than any so far */ { min_dist = dist; min_vert = cur; } } /* End of for each vertex (cur) */ /* The following error should "never happen". */ if (min_dist == BIG) fprintf( stderr, "Error: Didn't find a triangle.\n" ); prev = min_vert - 1; next = min_vert + 1; if (min_vert == 0) /* Wrap around on the ends */ prev = count - 1; else if (min_vert == count - 1) next = 0; /* Output this triangle */ t.x = v[vp[prev]].x; t.y = v[vp[prev]].y; t.z = v[vp[prev]].z; t.color = v[vp[prev]].color; t.x = v[vp[min_vert]].x; t.y = v[vp[min_vert]].y; t.z = v[vp[min_vert]].z; t.color = v[vp[min_vert]].color; t.x = v[vp[next]].x; t.y = v[vp[next]].y; t.z = v[vp[next]].z; t.color = v[vp[next]].color; draw_triangle( t ); /* Remove the triangle from the polygon */ count -= 1; for (i = min_vert; i < count; i++) vp[i] = vp[i+1]; } /* Output the final triangle */ t.x = v[vp].x; t.y = v[vp].y; t.z = v[vp].z; t.color = v[vp].color; t.x = v[vp].x; t.y = v[vp].y; t.z = v[vp].z; t.color = v[vp].color; t.x = v[vp].x; t.y = v[vp].y; t.z = v[vp].z; t.color = v[vp].color; draw_triangle( t ); } /* End of draw_poly */ /* End of poly_tri.c */ ``` Discuss this article in the forums Date this article was posted to GameDev.net: 7/16/1999 (Note that this date does not necessarily correspond to the date the article was written) See Also: Polygons © 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy Comments? Questions? Feedback? Click here!