kludge3d-20040822/src/tools.c

/*
 * File:         tools.c
 *
 * Description:  performs various manipulations on verts, etc.
 *               Anything more complicated than a simple translation of a
 *               single vert should end up in here.
 *
 *
 * This source code is part of kludge3d, and is released under the
 * GNU General Public License.
 *
 *
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


#include "model.h"
#include "tools.h"
#include "undo.h"
#include "vector.h"
#include "misc.h"
#include "selection.h"

#ifdef MEMWATCH
#include "memwatch.h"
#endif


/* STRUCTS **************************************************************/

typedef struct _Edge Edge;
struct _Edge {
	Vertex *v1;
	Vertex *v2;
	int flag;
};


/* PROTOTYPES ***********************************************************/

GSList *tools_find_near_verts( GSList *verts, Vertex *v ) ;
void tools_find_texcoords_for_vert( Poly *p, Vertex *vert, GSList *verts,
	float *u, float *v ) ;
void tools_find_texcoords_for_middlevert( Poly *p, float *u, float *v ) ;

GSList * tools_convert_edgelist_to_vertlist( GSList *edges ) ;
int tools_edgelist_can_be_subdivided( GSList *edges ) ;
GSList * tools_sort_edge_into_bins( GSList **bins, Edge *edge ) ;
GSList *tools_find_outside_edges( GSList *polys ) ;
gboolean tools_edges_isNotEqual( Edge *e1, Edge *e2 ) ;
gboolean tools_edges_areConnected( Edge *e1, Edge *e2 ) ;
gboolean tools_edge_hasVertex( Edge *e, Vertex *v ) ;


/* VERTEX TOOLS *********************************************************/

void tools_vertices_move( Model *model, GSList *verts, float deltaX, float deltaY, float deltaZ ) {

    for ( ; verts != NULL; verts = verts->next ) {
        // go through all the vertices and move them

        vertex_move( ( Vertex * ) verts->data, deltaX, deltaY, deltaZ );
    }
}


void tools_vertices_snap_to_grid( Model *model, GSList * verts, float spacing ) {

    Vertex * v = NULL;
    float mult;
    int i;

    while( verts != NULL ) {
        v = (Vertex*)verts->data;

        for( i = 0; i < 3; i++ ) {
            mult = v->v[i] / spacing;
            v->v[i] = spacing * rint( mult );
        }

        verts = verts->next;
    }

    action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );
}


void tools_vertices_snap_together( Model *model, GSList * plist ) {

    GSList * pts = NULL;
    Vertex average;
    Vertex * p = NULL;
    int i;

    vertices_find_mean( plist, &average );

    pts = plist;
    while( pts != NULL ) {
        p = (Vertex*)pts->data;

        for( i = 0; i < 3; i++ ) {
            p->v[i] = average.v[i];
        }

        pts = pts->next;
    }

    action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );
}


void tools_vertices_snap_together_along_axis( Model *model, GSList * plist, int axis ) {

    GSList * pts = NULL;
    Vertex average;
    Vertex * p = NULL;
    int i;

    vertices_find_mean( plist, &average );

    pts = plist;
    while( pts != NULL ) {
        p = (Vertex*)pts->data;

        // align vertices along active axis only
        for( i = 0; i < 3; i++ ) {
            if( i != axis )
                p->v[i] = average.v[i];
        }

        pts = pts->next;
    }

    action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );
}


void tools_vertices_rotate_90( Model *model, GSList * pts, int axis ) {

    float tempf[4];
    int tempi[1];

    tempf[0] = tempf[1] = tempf[2] = 0.0f;
    tempf[3] = M_PI / 2.0;
    tempi[0] = axis;

    action_do( model, ACTION_VERTEX_ROT, pts, NULL, NULL, tempf, tempi, NULL );

    while( pts != NULL ) {

        Vertex* p = (Vertex*)(pts->data);
        float temp;

        if( axis == 0 ) {
            temp = p->v[1];
            p->v[1] = p->v[2];
            p->v[2] = temp * -1.0;
        } else if( axis == 1 ) {
            temp = p->v[0];
            p->v[0] = p->v[2];
            p->v[2] = temp * -1.0;
        } else if( axis == 2 ) {
            temp = p->v[0];
            p->v[0] = p->v[1];
            p->v[1] = temp * -1.0;
        }

        pts = pts->next;
    }

}

void tools_vertices_rotate( Model *model, GSList * pts, int axis, float angle ) {

    float tempf[4];
    int tempi[1];
    float cosine = cos(angle);
    float sine = sin(angle);

    tempf[0] = tempf[1] = tempf[2] = 0.0f;
    tempf[3] = angle;
    tempi[0] = axis;

    action_do( model, ACTION_VERTEX_ROT, pts, NULL, NULL, tempf, tempi, NULL );

    while( pts != NULL ) {

        Vertex* p = (Vertex*)(pts->data);
        float temp0, temp1, temp2;

        if( axis == 0 ) {
            temp1 = p->v[1];
            temp2 = p->v[2];

	    p->v[1] = temp1*cosine - temp2*sine;
	    p->v[2] = temp1*sine + temp2*cosine;
        } else if( axis == 1 ) {
            temp0 = p->v[0];
            temp2 = p->v[2];

	    p->v[0] =   temp0*cosine + temp2*sine;
	    p->v[2] = - temp0*sine + temp2*cosine;
        } else if( axis == 2 ) {
            temp0 = p->v[0];
            temp1 = p->v[1];

	    p->v[0] = temp0*cosine - temp1*sine;
	    p->v[1] = temp0*sine + temp1*cosine;
        }

        pts = pts->next;
    }

}

void tools_vertices_rotate_about_point( Model *model,
	GSList * pts, int axis, float pt[], float angle,
	int register_with_undo_sys )
{

	float tempf[4];
	int tempi[1];
    float cosine = cos(angle);
    float sine = sin(angle);

    if( pt == NULL )
        return;

	if( register_with_undo_sys ) {
		vector_copy( tempf, pt );
		tempf[3] = angle;
		tempi[0] = axis;
		action_do( model, ACTION_VERTEX_ROT, pts, NULL, NULL, tempf, tempi, NULL );
	}

    while( pts != NULL ) {

        Vertex* p = (Vertex*)(pts->data);
        float temp0, temp1, temp2;

        if( axis == 0 ) {
            temp1 = p->v[1] - pt[1];
            temp2 = p->v[2] - pt[2];

	    p->v[1] = temp1*cosine - temp2*sine + pt[1];
	    p->v[2] = temp1*sine + temp2*cosine + pt[2];
        } else if( axis == 1 ) {
            temp0 = p->v[0] - pt[0];
            temp2 = p->v[2] - pt[2];

	    p->v[0] =   temp0*cosine + temp2*sine + pt[0];
	    p->v[2] = - temp0*sine + temp2*cosine + pt[2];
        } else if( axis == 2 ) {
            temp0 = p->v[0] - pt[0];
            temp1 = p->v[1] - pt[1];

	    p->v[0] = temp0*cosine - temp1*sine + pt[0];
	    p->v[1] = temp0*sine + temp1*cosine + pt[1];
        }

        pts = pts->next;
    }

}

void tools_vertices_flip( Model *model, GSList * pts, int axis ) {

    Vertex average;

    if( axis < 0 || axis > 2 )
        return;

    vertices_find_mean( pts, &average );

    while( pts != NULL ) {

        Vertex* p = (Vertex*)(pts->data);

        p->v[axis] -= average.v[axis];
        p->v[axis] = p->v[axis] * -1.0;
        p->v[axis] += average.v[axis];

        pts = pts->next;
    }

    action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );
}


void tools_vertices_scale_about_point( Model *model,
	GSList * plist, float *factor, float *point, int register_with_undo_sys )
{

	GSList * pts = NULL;
	Vertex * p = NULL;

	if( plist == NULL ) return;
	if( factor == NULL || point == NULL ) return;

	pts = plist;
	while( pts != NULL ) {
		p = (Vertex*)(pts->data);

		vector_sub( p->v, p->v, point );
		vector_mul_piecewise( p->v, p->v, factor );
		vector_add( p->v, p->v, point );

		pts = pts->next;
	}

	if( register_with_undo_sys ) {
		float temp[6];
		vector_copy( temp, factor );
		vector_copy( temp + 3, point );
		action_do( model, ACTION_VERTEX_SCALE,
			(plist == model->selected_verts ? NULL : plist),
			NULL, NULL, temp, NULL, NULL );
	}

}


void tools_vertices_scale_about_center( Model *model,
	GSList * plist, float *factor, int register_with_undo_sys )
{
	Vertex average;
	vertices_find_mean( plist, &average );
	tools_vertices_scale_about_point( model,
		plist, factor, average.v, register_with_undo_sys );
}


void tools_vertices_scale_symmetrically_about_center( Model *model,
	GSList * plist, float factor, int register_with_undo_sys )
{
	float f_v[3];
	f_v[0] = f_v[1] = f_v[2] = factor;
	tools_vertices_scale_about_center( model, plist, f_v, register_with_undo_sys );
}


void tools_vertices_scale_about_origin( Model *model,
	GSList * plist, float factor, int register_with_undo_sys )
{
	float f_v[3], pt[3];
	f_v[0] = f_v[1] = f_v[2] = factor;
	pt[0] = pt[1] = pt[2] = 0.0;
	tools_vertices_scale_about_point( model, plist, f_v, pt, register_with_undo_sys );
}


void tools_vertices_weld_list( Model *model, GSList *verts ) {

	GSList *l;
	Vertex *first;

	if( verts == NULL ) return;
	if( g_slist_length( verts ) < 2 ) return;

	tools_vertices_snap_together( model, verts );

	l = verts;
	first = (Vertex*)l->data;
	l = l->next;
	for( ; l; l = l->next ) {
		tools_vertices_weld( model, first, (Vertex*)l->data );
	}
}


/* replaces all instances of v2 with v1 */
void tools_vertices_weld( Model *model, Vertex *v1, Vertex *v2 ) {
	int i, num_polys;
	Poly *poly;
	Poly **polylist;

	if( v1 == NULL || v2 == NULL ) return;
	if( v1 == v2 ) return;

	/*
	for every poly using v2
		if poly uses both v1 & v2
			remove v2 from poly
		else (poly uses only v2)
			replace v2 with v1 in poly
		if v2 is no longer used by any polys in poly->mesh
			remove v2 from poly->mesh
		if poly has fewer than 3 verts
			remove poly from model
	remove v2 from model
	*/

	num_polys = v2->num_polys;
	polylist = (Poly**)malloc( num_polys * sizeof( Poly* ) );
	memcpy( polylist, v2->polys, num_polys * sizeof( Poly* ) );

	for( i = 0; i < num_polys; i++ ) {
		poly = polylist[i];
		if( poly_has_vertex( poly, v1 ) ) {
			poly_remove_vertex( poly, v2 );
		} else {
			poly_replace_vertex( poly, v1,
				array_find( (void**)poly->verts, poly->num_verts, v2 ) );
		}

		if( ! mesh_is_using_vertex( poly->mesh, v2 ) ) {
			mesh_vertex_remove( poly->mesh, v2 );
		}

		/* yes, 3.  not 2.  while 2-vertex polys *are* legal, it is expected
		behavior to remove such polys when performing a weld. */
		if( poly->num_verts < 3 ) {
			model_polygon_remove( model, poly );
		}
	}

	free( polylist );

	model_vertex_remove( model, v2 );
}


/* searches model for verts that are close together, and welds them */
void tools_vertices_weld_modelwide( Model *model ) {
	/*
	copy model's vert list
	for every vert1 in copied list
		if vert1 still exists in model vert list
			find all verts near vert1, and weld them all together
	*/

	GSList *listcopy, *l, *nearverts;
	Vertex *v;

	if( model == NULL ) return;
	if( model->verts == NULL ) return;

	listcopy = g_slist_copy( model->verts );
	for( l = listcopy; l; l = l->next ) {
		v = (Vertex *)l->data;

		if( g_slist_find( model->verts, v ) == NULL )
			continue;

		nearverts = tools_find_near_verts( model->verts, v );
		if( nearverts ) {
			tools_vertices_weld_list( model, nearverts );
			g_slist_free( nearverts );
		}
	}

	g_slist_free( listcopy );
}


/* returns a list of all verts near v, including v */
GSList *tools_find_near_verts( GSList *verts, Vertex *v ) {
	GSList *result = NULL;

	if( verts == NULL || v == NULL ) return NULL;

	while( verts ) {
		verts = g_slist_find_custom( verts, v,
									(GCompareFunc) vertices_isNotEqual );
		if( verts ) {
			result = g_slist_append( result, verts->data );
			verts = verts->next;
		}
	}

	return result;
}


/* POLYGON TOOLS ********************************************************/

/* Deprecated */
void tools_polys_move( Model *model, GSList *polys, float dX, float dY, float dZ ) {

    GSList *verts = NULL;

    verts = polys_get_verts_unique( polys );

    tools_vertices_move( model, verts, dX, dY, dZ );
    g_slist_free( verts );
}


/* Deprecated */
void tools_poly_move( Model *model, Poly * p, float dX, float dY, float dZ ) {

    int i;
    if( p == NULL ) return;

    for( i = 0; i < p->num_verts; i++ ) {
        vertex_move( p->verts[i], dX, dY, dZ );
    }
}


/* extrudes members of 'polys' individually.  returns list of polys created,
 * with members of 'polys' at head of list.  returned list must be freed.
 */
GSList * tools_polys_extrude( Model *model, GSList *polys ) {
	GSList *result = NULL, *temp;

	result = g_slist_copy( polys );

    for( ; polys != NULL; polys = polys->next ) {
        temp = tools_poly_extrude( model, (Poly*)polys->data );
		/* the first item in temp is polys->data.  remove it. */
		temp = g_slist_delete_link( temp, temp );
		result = g_slist_concat( result, temp );
    }

	return result;
}


/* extrudes poly p.  returns list of polys created, with p at head of list.
 * returned list must be freed.
 */
GSList * tools_poly_extrude( Model *model, Poly *p ) {
	GSList *result = NULL;
	int i;
    Vertex *original_verts[POLY_MAX_VERTS];
    Poly *new_poly;
    Vertex *new_vert;

    if( p == NULL )
        return NULL;
    if( p->mesh == NULL || p->mesh->polygons == NULL )
        return NULL;

	result = g_slist_append( result, p );

    /* first, re-calc the normal, just to be safe */
    poly_find_normal( p );

    /* create n new verts, dupes of the original n */
    for( i = 0; i < p->num_verts; i++ ) {
        original_verts[i] = p->verts[i];
        new_vert = vertex_dup( p->verts[i] );
        model_vertex_add( model, new_vert );
        mesh_vertex_add( p->mesh, new_vert );

        /* replace the old with the new */
		poly_replace_vertex( p, new_vert, i );
    }

    /* create n new polys */
    for( i = 0; i < p->num_verts; i++ ) {
        new_poly = poly_new();
        poly_add_vertex( new_poly, original_verts[i] );
        poly_add_vertex( new_poly, original_verts[ (i+1) % p->num_verts ] );
        poly_add_vertex( new_poly, p->verts[ (i+1) % p->num_verts ] );
        poly_add_vertex( new_poly, p->verts[i] );
        mesh_polygon_add( p->mesh, new_poly );
		result = g_slist_append( result, new_poly );
    }

	return result;
}


/* extrudes members of 'polys' such that they will remain connected.
 * returns list of polys created, with members of 'polys' at head of list.
 * returned list must be freed.
 */
GSList * tools_polys_extrude_connected( Model *model, GSList *polys ) {
	GSList *result = NULL;
    GSList *l;
    GHashTable *verts_old2new_hash;
    GHashTable *verts_new2old_hash;
    Poly *p;
    int i;
    Poly *new_poly;
    Vertex *new_vert;
    Vertex *orig_vert1, *orig_vert2;

	result = g_slist_copy( polys );

    verts_old2new_hash = g_hash_table_new( g_direct_hash,
                                   (GCompareFunc)vertices_isIdentical );
    verts_new2old_hash = g_hash_table_new( g_direct_hash,
                                   (GCompareFunc)vertices_isIdentical );

    /* note that it's *probably* ok to pass in a list of polys from various
       meshes (as opposed to polys from the *same* mesh), but I haven't
       tested this well...  */
    for( l = polys; l != NULL; l = l->next ) {
        p = (Poly*)l->data;

        /* create n new verts, dupes of the original n */
        /* remember them in the hash so other polys can use them too */
        for( i = 0; i < p->num_verts; i++ ) {
            new_vert = g_hash_table_lookup( verts_old2new_hash, p->verts[i] );
            if( new_vert == NULL ) {
                new_vert = vertex_dup( p->verts[i] );
                g_hash_table_insert( verts_old2new_hash, p->verts[i], new_vert );
                g_hash_table_insert( verts_new2old_hash, new_vert, p->verts[i] );
                model_vertex_add( model, new_vert );
                mesh_vertex_add( p->mesh, new_vert );
            }

            /* replace the old with the new */
			poly_replace_vertex( p, new_vert, i );
        }

    }

    for( l = polys; l != NULL; l = l->next ) {
        p = (Poly*)l->data;

        /* first, re-calc the normal, just to be safe */
        poly_find_normal( p );

        /* create n new polys */
        for( i = 0; i < p->num_verts; i++ ) {
            int j = (i+1) % p->num_verts;

            orig_vert1 = g_hash_table_lookup( verts_new2old_hash, p->verts[i] );
            orig_vert2 = g_hash_table_lookup( verts_new2old_hash, p->verts[j] );

            /* if this edge is shared with others in polys, then skip it */
            if( polys_count_edge_usage( polys, p->verts[i], p->verts[j]) > 1 ) {
                continue;
            }

            new_poly = poly_new();
            poly_add_vertex( new_poly, orig_vert1 );
            poly_add_vertex( new_poly, orig_vert2 );
            poly_add_vertex( new_poly, p->verts[j] );
            poly_add_vertex( new_poly, p->verts[i] );
            mesh_polygon_add( p->mesh, new_poly );
			result = g_slist_append( result, new_poly );
        }
    }

    g_hash_table_destroy( verts_old2new_hash );
    g_hash_table_destroy( verts_new2old_hash );

	return result;
}


void tools_polys_turn_edge( Model *model, GSList *polys ) {

	Poly *p1, *p2;
	Vertex *shared_v1, *shared_v2;
	Vertex *not_shared_v1, *not_shared_v2;
	int i, shared_edges=0;
	TexCoord *nsv1tc, *nsv2tc;
	float nsv1tc_u, nsv1tc_v, nsv2tc_u, nsv2tc_v;

	if( polys == NULL ) return;
	if( g_slist_length( polys ) != 2 ) {
		printf( "Turn edge: exactly 2 polys must be selected\n" );
		return;
	}

	p1 = (Poly*)polys->data;
	p2 = (Poly*)polys->next->data;

	/* check to make sure that all polys are triangles */
	if( p1->num_verts != 3 || p2->num_verts != 3 ) {
		printf( "Turn edge: both polygons must be triangles\n" );
		return;
	}

	/* check to make sure that the two polys are in the same mesh */
	if( p1->mesh != p2->mesh ) {
		printf( "Turn edge: both polygons must be in the same mesh\n" );
		return;
	}

	/* check to make sure that the two polys share exactly one edge */
	for( i = 0; i < p1->num_verts; i++ ) {
		if( poly_has_edge( p2,
				p1->verts[i], p1->verts[(i+1)%p1->num_verts] ) )
		{
			shared_edges ++;
			shared_v1 = p1->verts[i];
			shared_v2 = p1->verts[(i+1)%p1->num_verts];
		}
	}
	if( shared_edges != 1 ) {
		printf( "Turn edge: polygons must be adjacent\n" );
		return;
	}

	/* find out which two verts are *not* shared */
	for( i = 0; i < p1->num_verts; i++ ) {
		if( p1->verts[i] != shared_v1 && p1->verts[i] != shared_v2 )
			not_shared_v1 = p1->verts[i];
	}
	for( i = 0; i < p2->num_verts; i++ ) {
		if( p2->verts[i] != shared_v1 && p2->verts[i] != shared_v2 )
			not_shared_v2 = p2->verts[i];
	}

	/* remember the texcoords */
	/* remember p2's nsv2, to be used for p1 */
	nsv2tc = poly_get_texcoord( p2, not_shared_v2 );
	nsv2tc_u = nsv2tc->x;
	nsv2tc_v = nsv2tc->y;
	/* remember p1's nsv1, to be used for p2 */
	nsv1tc = poly_get_texcoord( p1, not_shared_v1 );
	nsv1tc_u = nsv1tc->x;
	nsv1tc_v = nsv1tc->y;

	/* perform the swap */
	poly_replace_vertex( p1, not_shared_v2,
		array_find( (void**)p1->verts, p1->num_verts, shared_v2 ) );
	poly_replace_vertex( p2, not_shared_v1,
		array_find( (void**)p2->verts, p2->num_verts, shared_v1 ) );

	/* set the texcoords to the proper values */
	texcoord_change_values( poly_get_texcoord( p1, not_shared_v2 ),
							nsv2tc_u, nsv2tc_v );
	texcoord_change_values( poly_get_texcoord( p2, not_shared_v1 ),
							nsv1tc_u, nsv1tc_v );
}


void tools_polys_make_triangles( Model *model, GSList *plist ) {

	GSList *l, *polys;
	Poly *p, *newpoly;
	int i;

	if( plist == NULL ) return;

	polys = g_slist_copy( plist );

	for( l = polys; l; l = l->next ) {
		p = (Poly *)l->data;
		if( p->num_verts < 4 )
			continue;

		for( i = 2; i < p->num_verts; i++ ) {
			newpoly = poly_new();
			poly_add_vertex( newpoly, p->verts[0] );
			texcoord_change_values(
				poly_get_texcoord( newpoly, p->verts[0] ),
				p->tc[0]->x, p->tc[0]->y );
			poly_add_vertex( newpoly, p->verts[i-1] );
			texcoord_change_values(
				poly_get_texcoord( newpoly, p->verts[i-1] ),
				p->tc[i-1]->x, p->tc[i-1]->y );
			poly_add_vertex( newpoly, p->verts[i] );
			texcoord_change_values(
				poly_get_texcoord( newpoly, p->verts[i] ),
				p->tc[i]->x, p->tc[i]->y );
			mesh_polygon_add( p->mesh, newpoly );
		}
		model_polygon_remove( model, p );
	}

	g_slist_free( polys );
}


#define TOOLS_ADD_VERT_AND_CHANGE_TC( THE_VERT ) \
	poly_add_vertex( newpoly, THE_VERT );\
	tools_find_texcoords_for_vert( p, THE_VERT, verts_for_new_polys, &u, &v );\
	texcoord_change_values( poly_get_texcoord( newpoly, THE_VERT ), u, v );
#define TOOLS_ADD_MIDDLEVERT_AND_CHANGE_TC( THE_VERT ) \
	poly_add_vertex( newpoly, THE_VERT );\
	tools_find_texcoords_for_middlevert( p, &u, &v );\
	texcoord_change_values( poly_get_texcoord( newpoly, THE_VERT ), u, v );

void tools_polys_subdivide_midpoint( Model *model, GSList *plist ) {

	GSList *l, *ll, *polys, *nearverts, *verts_for_new_polys = NULL;
	Poly *p, *newpoly;
	Vertex *newvert, *middlevert;
	int i;
	float u, v;

	if( plist == NULL ) return;

	polys = g_slist_copy( plist );

	for( l = polys; l; l = l->next ) {
		p = (Poly *)l->data;
		if( p->num_verts < 3 )
			continue;

		/* for each edge, insert a vert at the midpoint */
		for( i = 0; i < p->num_verts; i++ ) {
			int next_i = (i + 1) % p->num_verts;
			verts_for_new_polys = g_slist_append( verts_for_new_polys, p->verts[i] );

			newvert = vertex_new();

			/* find the middle of the edge */
			vector_add( newvert->v, p->verts[i]->v, p->verts[next_i]->v );
			vector_mul( newvert->v, newvert->v, 1. / 2. );

			nearverts = tools_find_near_verts( model->verts, newvert );

			if( nearverts != NULL ) {
				/* if an existing vert was found near newvert */
				vertex_delete( newvert );
				newvert = (Vertex*)nearverts->data;
				g_slist_free( nearverts );
			} else {
				model_vertex_add( model, newvert );
			}

			verts_for_new_polys = g_slist_append( verts_for_new_polys, newvert );
		}

		/* if this is not a triangle, create one more vert at the middle */
		if( p->num_verts >= 4 ) {
			middlevert = vertex_new();
			vertices_find_mean( verts_for_new_polys, middlevert );
			model_vertex_add( model, middlevert );
		}

		for( ll = verts_for_new_polys; ll && ll->next;  ) {
			int first = (ll == verts_for_new_polys);
			Vertex *firstvert;
			newpoly = poly_new();

			if( first ) {
				/* if this is the first poly to be created in place of p, then
				we have some special-case things to do */
				firstvert = (Vertex*)(g_slist_last(verts_for_new_polys)->data);
			} else {
				firstvert = (Vertex*)ll->data;
				ll = ll->next;
			}
			TOOLS_ADD_VERT_AND_CHANGE_TC( firstvert )

			TOOLS_ADD_VERT_AND_CHANGE_TC( (Vertex*)ll->data )
			ll = ll->next;
			TOOLS_ADD_VERT_AND_CHANGE_TC( (Vertex*)ll->data )

			if( p->num_verts >= 4 ) {
				/* if this is not a triangle, the final vert in newpoly should
				be the middlevert */
				TOOLS_ADD_MIDDLEVERT_AND_CHANGE_TC( middlevert )
			}

			mesh_polygon_add( p->mesh, newpoly );
		}

		if( p->num_verts == 3 ) {
			/* if this is a triangle, add the final (middle) new poly */
			newpoly = poly_new();
			TOOLS_ADD_VERT_AND_CHANGE_TC(
				(Vertex*)verts_for_new_polys->next->data )
			TOOLS_ADD_VERT_AND_CHANGE_TC(
				(Vertex*)verts_for_new_polys->next->next->next->data )
			TOOLS_ADD_VERT_AND_CHANGE_TC(
				(Vertex*)(g_slist_last(verts_for_new_polys)->data) )
			mesh_polygon_add( p->mesh, newpoly );
		}

		g_slist_free( verts_for_new_polys );
		verts_for_new_polys = NULL;

		model_polygon_remove( model, p );
	}

	g_slist_free( polys );
}


void tools_polys_subdivide_quads( Model *model, GSList *plist ) {

	GSList *l, *ll, *polys, *nearverts, *verts_for_new_polys = NULL;
	Poly *p, *newpoly;
	Vertex *newvert, *middlevert;
	int i;
	float u, v;

	if( plist == NULL ) return;

	polys = g_slist_copy( plist );

	for( l = polys; l; l = l->next ) {
		p = (Poly *)l->data;
		if( p->num_verts < 3 )
			continue;

		/* for each edge, insert a vert at the midpoint */
		for( i = 0; i < p->num_verts; i++ ) {
			int next_i = (i + 1) % p->num_verts;
			verts_for_new_polys = g_slist_append( verts_for_new_polys, p->verts[i] );

			newvert = vertex_new();

			/* find the middle of the edge */
			vector_add( newvert->v, p->verts[i]->v, p->verts[next_i]->v );
			vector_mul( newvert->v, newvert->v, 1. / 2. );

			nearverts = tools_find_near_verts( model->verts, newvert );

			if( nearverts != NULL ) {
				/* if an existing vert was found near newvert */
				vertex_delete( newvert );
				newvert = (Vertex*)nearverts->data;
				g_slist_free( nearverts );
			} else {
				model_vertex_add( model, newvert );
			}

			verts_for_new_polys = g_slist_append( verts_for_new_polys, newvert );
		}

		/* create one more vert at the middle */
		middlevert = vertex_new();
		vertices_find_mean( verts_for_new_polys, middlevert );
		model_vertex_add( model, middlevert );

		for( ll = verts_for_new_polys; ll && ll->next;  ) {
			int first = (ll == verts_for_new_polys);
			Vertex *firstvert;
			newpoly = poly_new();

			if( first ) {
				/* if this is the first poly to be created in place of p, then
				we have some special-case things to do */
				firstvert = (Vertex*)(g_slist_last(verts_for_new_polys)->data);
			} else {
				firstvert = (Vertex*)ll->data;
				ll = ll->next;
			}
			TOOLS_ADD_VERT_AND_CHANGE_TC( firstvert )

			TOOLS_ADD_VERT_AND_CHANGE_TC( (Vertex*)ll->data )
			ll = ll->next;
			TOOLS_ADD_VERT_AND_CHANGE_TC( (Vertex*)ll->data )

			/* the fourth (final) vert in newpoly should be the middlevert */
			TOOLS_ADD_MIDDLEVERT_AND_CHANGE_TC( middlevert )

			mesh_polygon_add( p->mesh, newpoly );
		}

		g_slist_free( verts_for_new_polys );
		verts_for_new_polys = NULL;

		model_polygon_remove( model, p );
	}

	g_slist_free( polys );
}


void tools_polys_subdivide_tris( Model *model, GSList *plist ) {

	GSList *l, *polys, *verts_for_new_polys = NULL;
	Poly *p, *newpoly;
	Vertex *middlevert;
	int i;
	float u, v;

	if( plist == NULL ) return;

	polys = g_slist_copy( plist );

	for( l = polys; l; l = l->next ) {
		p = (Poly *)l->data;
		if( p->num_verts < 3 )
			continue;

		/* build a list of the verts, for use by vertices_find_mean and the
		texture coordinate stuff */
		for( i = 0; i < p->num_verts; i++ ) {
			verts_for_new_polys = g_slist_append( verts_for_new_polys, p->verts[i] );
		}

		/* create one vert at the middle */
		middlevert = vertex_new();
		vertices_find_mean( verts_for_new_polys, middlevert );
		model_vertex_add( model, middlevert );

		/* for each edge, create a triangle using the two verts on the edge
		and the middle vert */
		for( i = 0; i < p->num_verts; i++ ) {
			int next_i = (i + 1) % p->num_verts;
			newpoly = poly_new();

			TOOLS_ADD_VERT_AND_CHANGE_TC( p->verts[i] )
			TOOLS_ADD_VERT_AND_CHANGE_TC( p->verts[next_i] )
			TOOLS_ADD_MIDDLEVERT_AND_CHANGE_TC( middlevert )

			mesh_polygon_add( p->mesh, newpoly );
		}

		g_slist_free( verts_for_new_polys );
		verts_for_new_polys = NULL;

		model_polygon_remove( model, p );
	}

	g_slist_free( polys );
}


void tools_find_texcoords_for_vert( Poly *p, Vertex *vert, GSList *verts,
	float *u, float *v )
{
	TexCoord *tc, *nexttc, *prevtc;
	GSList *listelem, *nextelem, *prevelem;
	int elem_index;

	// fixme - check for NULL

	*u = 0.;
	*v = 0.;

	/* if the vert is already in the poly, we can retrieve its
	texcoord vals directly */
	tc = poly_get_texcoord( p, vert );
	if( tc ) {
		*u = tc->x;
		*v = tc->y;
		return;
	}

	/* if it is not in the poly, find its location in the list, as well as
	the next and previous verts in the list */
	listelem = g_slist_find( verts, vert );
	if( listelem == NULL )
		return;

	nextelem = listelem->next;
	if( nextelem == NULL )
		/* loop around to beginning of list */
		nextelem = verts;

	elem_index = g_slist_position( verts, listelem );
	if( elem_index == 0 )
		/* loop around to end of list */
		elem_index = g_slist_length( verts ) - 1;
	else
		elem_index--;
	prevelem = g_slist_nth( verts, elem_index );

	/* Because of the way in which the verts list is set up (see the
	tools_polys_subdivide funcs) the verts in the list alternate between
	new and existing vertices.  As such, since we know that 'vert' is a new
	vert, the verts before and after v in the list *should* exist in poly p,
	and hence have texture coordinates.  We will use those texture coordinates
	to calculate the coords for 'vert'. */

	nexttc = poly_get_texcoord( p, (Vertex*)nextelem->data );
	prevtc = poly_get_texcoord( p, (Vertex*)prevelem->data );

	if( nexttc == NULL || prevtc == NULL ) return;

	*u = (nexttc->x + prevtc->x) / 2.;
	*v = (nexttc->y + prevtc->y) / 2.;

}


void tools_find_texcoords_for_middlevert( Poly *p, float *u, float *v )
{
	int i;
	*u = 0.;
	*v = 0.;
	for( i = 0; i < p->num_verts; i++ ) {
		*u += p->tc[i]->x;
		*v += p->tc[i]->y;
	}
	*u /= (float)p->num_verts;
	*v /= (float)p->num_verts;
}


void tools_polys_smooth( Model *model, GSList *polys, float factor ) {

	GSList *vertlist, *l;
	GSList *adjacent_polys, *adjacent_verts;
	GSList *templist;
	GHashTable *verthash;
	Vertex *v, avgVert;
	float *tempPt, delta[3];

	/* verthash will hold the new locations for the vertices */

	vertlist = polys_get_verts_unique( polys );
	verthash = g_hash_table_new_full( NULL, NULL, NULL, g_free );
	/* populate verthash */
	for( l = vertlist; l; l = l->next ) {
		v = (Vertex *)l->data;
		tempPt = g_malloc( sizeof( float ) * 3 );
		vector_copy( tempPt, v->v );
		g_hash_table_insert( verthash, v, tempPt );
	}

	/* for each vert, record its new position in the hash table */
	for( l = vertlist; l; l = l->next ) {
		v = (Vertex *)l->data;
		tempPt = g_hash_table_lookup( verthash, v );

		/* for each vert, find all verts that are adjacent to it */
		templist = g_slist_append( NULL, v );
		adjacent_polys = verts_get_polys_unique( templist );
		g_slist_free( templist );
		adjacent_verts = polys_get_verts_unique( adjacent_polys );
		/* v will be in adjacent_verts, but that's OK */

		/* using the list of adjacent verts, find their average */
		vertices_find_mean( adjacent_verts, &avgVert );

		/* move the vert closer to the average */
		vector_sub( delta, avgVert.v, v->v );
		vector_mul( delta, delta, factor );
		vector_add( tempPt, tempPt, delta );

		g_slist_free( adjacent_polys );
		g_slist_free( adjacent_verts );
	}

	/* now move all of the verts */
	for( l = vertlist; l; l = l->next ) {
		v = (Vertex *)l->data;
		tempPt = g_hash_table_lookup( verthash, v );
		vector_copy( v->v, tempPt );
	}

	g_slist_free( vertlist );
	g_hash_table_destroy( verthash );

	action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );
}

/* any more edges than this and it doesn't count as a hole */
#define TOOLS_HOLE_THRESHOLD 4

void tools_polys_find_holes( Model *model, GSList *polys ) {
	/* Finds holes and 'T' junctions in the list of polys.
	Any group of "outside edges" consisting of fewer than a certain number
	of edges will be tagged as a hole.  Note that, because of this and because
	of the way in which outside edges are grouped, it currently can not
	detect "figure-eight" type holes (ie two holes that share a vertex). */

	/* Here's how this *should* have been implemented:
		- find the outside edges
		- construct a graph of the edges and verts
		- form 'holes' by
			- performing shortest-path on the graph
			- once shortest-loop-from-an-edge-back-to-itself is found,
			  remove involved edges from graph and form a vertlist.  This is
			  one hole.
		- form holes until there are no edges left in graph, or (error state)
		  the remaining edges don't form any loops
		- any holes smaller than a certain threshold can be selected,
		  filled-in by poly, etc.
	*/

	GSList *l, *ll;
	GSList *outside_edges;
	GSList *holes = NULL;
	GSList *bins = NULL, *bins_copy;
	GSList *bin, *bl;
	int bin_is_part_of_another_bin;

	outside_edges = tools_find_outside_edges( polys );

	/* sort the edges into bins */
	for( l = outside_edges; l; l = l->next ) {
		tools_sort_edge_into_bins( &bins, (Edge*)l->data );
	}

	/* now we must consolidate the bins as much as possible */
	/* For every bin in 'bins', remove it from bins
	and try adding its contents back into 'bins'.  The idea is that, if the
	smaller bin should actually be part of a larger bin, some of its contents
	will be added to that larger bin and the smaller bin (if it re-forms at
	all) will have fewer edges.  However, if the smaller bin *is* its own,
	independent bin, it will be completely re-formed as its contents are
	added back into 'bins'.  If we repeat this process until there are no bins
	that are part of other bins, we will have consolidated all of the bins
	as much as possible. */
	do {
		bin_is_part_of_another_bin = FALSE;
		bins_copy = g_slist_copy( bins );
		for( bin = bins_copy; bin; bin = bin->next ) {
			GSList *binlist, *btemp, *bin_that_first_edge_was_added_to = NULL;
			/* remove bin from bins */
			binlist = bin->data;
			bins = g_slist_remove( bins, binlist );

			for( bl = binlist; bl; bl = bl->next ) {
				btemp = tools_sort_edge_into_bins( &bins, (Edge*)bl->data );
				if( bin_that_first_edge_was_added_to == NULL ) {
					bin_that_first_edge_was_added_to = btemp;
					if( g_slist_length( bin_that_first_edge_was_added_to->data ) > 1 )
						/* bin is part of another bin */
						bin_is_part_of_another_bin = TRUE;
				}
				if( bin_that_first_edge_was_added_to != btemp ) {
					/* bin is part of another bin */
					bin_is_part_of_another_bin = TRUE;
				}
			}
			g_slist_free( binlist );
		}
		g_slist_free( bins_copy );
	} while( bin_is_part_of_another_bin );

	/* Now traverse 'bins', and for each bin shorter than the threshold add
	its contents to the holes list.  Finally, free the bin. */
	for( bin = bins; bin; bin = bin->next ) {
		if( !(g_slist_length( bin->data ) > TOOLS_HOLE_THRESHOLD) ) {
			/* holes smaller than the TOOLS_HOLE_THRESHOLD are assumed
			not to be figure-8 holes, and can be converted directly into
			a vertlist */
			holes = g_slist_append( holes,
						tools_convert_edgelist_to_vertlist( bin->data ) );
		} else {
			/* the edgelist may or may not be a figure-8 hole.  we should
			determine if it is a figure-8, and if so attempt to subdivide it. */
			if( tools_edgelist_can_be_subdivided( bin->data ) ) {
				printf( "Found a figure-eight hole, with %i edges\n", g_slist_length( bin->data ) );
			}
		}

		g_slist_free( bin->data );
		bin->data = NULL;
	}
	g_slist_free( bins );

	/* free edges */
	for( l = outside_edges; l; l = l->next ) {
		free( l->data );
	}
	g_slist_free( outside_edges );

	/* We now have a list of lists of verts.  Each list of verts represents
	a 'hole' in the poly-list surface. */

	/*print the lists, select the verts*/
	sel_vert_unselect_all( model );
	printf( "%s : found %i holes\n", __FUNCTION__, g_slist_length( holes ) );
	for( l = holes; l; l = l->next ) {
		printf( "\tverts: " );
		sel_vert_select_list( l->data );
		for( ll = l->data; ll; ll = ll->next ) {
			printf( "%x ", (unsigned int)ll->data );
		}
		printf( "\n" );
	}
}


GSList * tools_convert_edgelist_to_vertlist( GSList *edges ) {

	GSList *l, *verts = NULL;
	Edge *e, *prev = NULL;
	int num_edges = g_slist_length( edges );

	while( g_slist_length(verts) < num_edges ) {
		for( l = edges; l; l = l->next ) {
			e = (Edge *)l->data;
			if( prev == NULL )
			{
				verts = g_slist_append( verts, e->v1 );
				verts = g_slist_append( verts, e->v2 );
				e->flag = TRUE;
				prev = e;
			}
			else if( !(e->flag) &&
						tools_edges_areConnected( e, prev ) &&
						tools_edges_isNotEqual( e, prev ) )
			{
				Vertex *v = NULL;
				/* now figure out which vert should be next */
				if( e->v1 == prev->v1 || e->v1 == prev->v2 )
					v = e->v2;
				else if( e->v2 == prev->v1 || e->v1 == prev->v2 )
					v = e->v1;

				if( v && g_slist_find( verts, v ) == NULL )
					verts = g_slist_append( verts, v );
				e->flag = TRUE;
				prev = e;
			}
		}
	}

	return verts;
}


int tools_edgelist_can_be_subdivided( GSList *edges ) {
	/*  */
	int figure_eight = FALSE;
	int well_behaved = TRUE;
	GSList *l, *ll;
	Edge *e;
	Vertex *v;
	int edges_with_v;

	for( l = edges; l; l = l->next ) {
		e = (Edge *)l->data;
		v = e->v1;
		while( v ) {
			edges_with_v = 0;
			for( ll = edges; ll; ll = ll->next ) {
				if( tools_edge_hasVertex( (Edge*)ll->data, v ) )
					edges_with_v++;
			}
			if( edges_with_v > 2 )
				figure_eight = TRUE;
			if( edges_with_v % 2 )
				well_behaved = FALSE;
			v = (v==e->v1) ? e->v2 : NULL;
		}
	}

	return( figure_eight && well_behaved );
}


GSList * tools_sort_edge_into_bins( GSList **bins, Edge *edge ) {
	/* returns the bin that edge was placed in */

	GSList *l, *ll;
	GSList *destination_bin = NULL;
	int largest_matching_bin_size = -1;

	/* look for a proper bin to put edge into.  It is important that, if an
	edge could go in one of several bins, we add the edge to the largest
	bin. */
	for( l = *bins; l; l = l->next ) {
		int bin_size = g_slist_length( l->data );
		for( ll = l->data; ll; ll = ll->next ) {
			if( tools_edges_areConnected( edge, (Edge*)ll->data ) &&
			    bin_size >= largest_matching_bin_size ) {
				destination_bin = l;
				largest_matching_bin_size = bin_size;
			}
		}
	}

	/* if couldn't find a proper bin, create one and add it to bins */
	if( destination_bin == NULL ) {
		*bins = g_slist_append( *bins, NULL );
		destination_bin = g_slist_last( *bins );
		destination_bin->data = NULL;
	}

	/* append edge to destination_bin */
	destination_bin->data = g_slist_append( destination_bin->data, edge );

	return destination_bin;
}


GSList *tools_find_outside_edges( GSList *polys ) {
	GSList *edges = NULL;
	GSList *l;
	Poly *p;
	Edge *e;
	int i, next_i;

	for( l = polys; l; l = l->next ) {
		p = (Poly *)l->data;

		for( i = 0; i < p->num_verts; i++ ) {
			next_i = (i+1) % p->num_verts;

			/* this edge is not an outside edge if it is shared with others
			in 'polys' */
			if( polys_count_edge_usage( polys,
										p->verts[i], p->verts[next_i]) > 1 )
				continue;

			/* create an Edge for this edge */
			e = (Edge *)malloc( sizeof( Edge ) );
			memset( e, '\0', sizeof( Edge ) );
			e->v1 = p->verts[i];
			e->v2 = p->verts[next_i];
			/* check to see if it is already in the list */
			if( g_slist_find_custom( edges, e,
				(GCompareFunc)tools_edges_isNotEqual ) )
			{
				free( e );
				continue;
			}
			/* and add it to the list */
			edges = g_slist_prepend( edges, e );
		}
	}

	return edges;
}


gboolean tools_edges_isNotEqual( Edge *e1, Edge *e2 ) {
	int equal = FALSE;

	if( e1->v1 == e2->v1 && e1->v2 == e2->v2 )
		equal = TRUE;
	if( e1->v2 == e2->v1 && e1->v1 == e2->v2 )
		equal = TRUE;

	return !equal;
}


gboolean tools_edges_areConnected( Edge *e1, Edge *e2 ) {
	int connected = FALSE;

	if( e1->v1 == e2->v1 || e1->v2 == e2->v2 ||
		e1->v2 == e2->v1 || e1->v1 == e2->v2 )
		connected = TRUE;

	return connected;
}


gboolean tools_edge_hasVertex( Edge *e, Vertex *v ) {
	int result = FALSE;

	if( e->v1 == v || e->v2 == v )
		result = TRUE;

	return result;
}


/* MISC TOOLS ***********************************************************/

void tools_scale_along_normals( Model *model, GSList *polys, GSList *verts, float factor ) {

	/* Note: this will likely *never* be undo-able.  The polygon thin/fatten
	seems to behave predictably, but vertex thin/fatten tends to cause the
	vertices to start "wandering" after a few manipulations.  These errors
	will get very bad, very quickly.  As such, the application of this tool,
	followed by an application of this tool with a negated 'factor', does not
	necessarily return the model to its original state.  This makes it very
	impractical to implement undo-ability for this tool. */

    GSList *l, *list_to_free = NULL;
    Vertex *v;
    int i;
	float avg_normal[3], temp[3], len;

	if( polys == NULL && verts == NULL )
		return;

	if( verts == NULL ) {
		verts = polys_get_verts_unique( polys );
		list_to_free = verts;
	} else if( polys == NULL ) {
		polys = verts_get_polys_unique( verts );
		list_to_free = polys;
	}

	/* have all polys update their normal */
	for( l = polys; l; l = l->next ) {
		poly_find_normal( (Poly *)l->data );
	}

	/* for each vert... */
	for( l = verts; l != NULL; l = l->next ) {
		v = (Vertex*)l->data;

		if( v->num_polys == 0 )
			/* should never happen, but... */
			continue;

		vector_zero( avg_normal );

		/* find the average normal, over all polys using this vert */
		for( i = 0; i < v->num_polys; i++ ) {
			vector_add( avg_normal, avg_normal, v->polys[i]->normal );
		}
		vector_mul( avg_normal, avg_normal, 1. / (float)v->num_polys );

		/* normalize the avg_normal vector, also make sure it wasn't
		   zero-length before it was normalized (which would indicate
		   that something weird happened, like co-planar polys with normals
		   pointing in opposite directions, etc) */
		len = vector_normalize( avg_normal );
		if( len < 0.01 )
			continue;

		/* scale vertex in direction avg_normal is pointing */
		vector_find_point( temp, v->v, avg_normal, factor );
		vector_copy( v->v, temp );
	}

	action_do( model, ACTION_UNKNOWN, NULL, NULL, NULL, NULL, NULL, NULL );

	g_slist_free( list_to_free );
}