Jump to content

Like
0Likes
Dislike
Polygon to triangles


triangle color int float vertex count vertices return polygon

4: Adsense

/*

 * 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 */

0 Comments

Note: GameDev.net moderates article comments.