Like 0Likes Dislike Polygon to triangles

triangle color int float vertex count vertices return polygon

/*

* 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[3];

#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[0].y - v[0].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[0].x = v[vp[prev]].x;

t[0].y = v[vp[prev]].y;

t[0].z = v[vp[prev]].z;

t[0].color = v[vp[prev]].color;

t[1].x = v[vp[min_vert]].x;

t[1].y = v[vp[min_vert]].y;

t[1].z = v[vp[min_vert]].z;

t[1].color = v[vp[min_vert]].color;

t[2].x = v[vp[next]].x;

t[2].y = v[vp[next]].y;

t[2].z = v[vp[next]].z;

t[2].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[0].x = v[vp[0]].x;

t[0].y = v[vp[0]].y;

t[0].z = v[vp[0]].z;

t[0].color = v[vp[0]].color;

t[1].x = v[vp[1]].x;

t[1].y = v[vp[1]].y;

t[1].z = v[vp[1]].z;

t[1].color = v[vp[1]].color;

t[2].x = v[vp[2]].x;

t[2].y = v[vp[2]].y;

t[2].z = v[vp[2]].z;

t[2].color = v[vp[2]].color;

draw_triangle( t );

} /* End of draw_poly */

/* End of poly_tri.c */