Jump to content

  • Log In with Google      Sign In   
  • Create Account


Like
0Likes
Dislike

Polygon to triangles

By Unknown Author | Published Jul 16 1999 11:58 AM in Math and Physics

triangle color int float vertex count vertices return polygon
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

/*

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





Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS