// merge.c

#include "bsp5.h"

#define CONTINUOUS_EPSILON      0.001

/*
=============
TryMerge

If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the faces couldn't be merged, or the new face.
The originals will NOT be freed.
=============
*/
face_t *
TryMerge( face_t *f1, face_t *f2 ) {
	vec_t		*p1, *p2, *p3, *p4, *back;
	face_t		*newf;
	int		i, j, k, l;
	vec3_t		normal, delta, planenormal;
	vec_t		dot;
	plane_t		*plane;
	qboolean	keep1, keep2;
	int		nextI, nextJ;

	if( f1->numpoints == -1 || f2->numpoints == -1 )
		return NULL;

	if( f1->planeside != f2->planeside )
		return NULL;

	if( f1->texturenum != f2->texturenum )
		return NULL;

	if( f1->contents[ 0 ] != f2->contents[ 0 ] )
		return NULL;

	if( f1->contents[ 1 ] != f2->contents[ 1 ] )
		return NULL;

	//
	// find a common edge
	//
	p1 = p2 = NULL; // stop compiler warning
	j = 0; //

	for( i = 0; i < f1->numpoints; i++ ) {
		p1 = f1->pts[ i ];
		p2 = f1->pts[ ( i + 1 ) % f1->numpoints ];

		for( j = 0; j < f2->numpoints; j++ ) {
			p3 = f2->pts[ j ];
			p4 = f2->pts[ ( j + 1 ) % f2->numpoints ];

			for( k = 0; k < 3; k++ ) {
				if(
					( fabs( p1[ k ] - p4[ k ] ) > EQUAL_EPSILON ) ||
					( fabs( p2[ k ] - p3[ k ] ) > EQUAL_EPSILON )
					) {
					break;
				}
			}

			if( k == 3 )
				break;
		}
		if( j < f2->numpoints )
			break;
	}

	if( i == f1->numpoints )
		return NULL; // no matching edges

	//
	// check slope of connected lines
	// if the slopes are colinear, the point can be removed
	//
	plane = &planes[ f1->planenum ];

	if( f1->planeside )
		VectorNegate( plane->normal, planenormal );
	else
		VectorCopy( plane->normal, planenormal );

	// get the vert before p1, then a vector from p1 to it, then make a sort of "line normal" using the plane-normal and it
	back = f1->pts[ ( i + f1->numpoints - 1 ) % f1->numpoints ];

	VectorSubtract( p1, back, delta );
	CrossProduct( planenormal, delta, normal );
	VectorNormalize( normal );

	// get the vert after p4, then a vector from it to p1. dotproduct this with the "line normal". if positive, this line is not convex
	back = f2->pts[ ( j + 2 ) % f2->numpoints ];

	VectorSubtract( back, p1, delta );
	dot = DotProduct( delta, normal );

	if( dot > CONTINUOUS_EPSILON )
		return NULL; // not a convex polygon

	// if dot is lower than this, pt1 must be kept ?
	keep1 = dot < -CONTINUOUS_EPSILON;

	// get vert after pt2, vector from it to pt2, make "line normal"
	back = f1->pts[ ( i + 2 ) % f1->numpoints ];

	VectorSubtract( back, p2, delta );
	CrossProduct( planenormal, delta, normal );
	VectorNormalize( normal );

	// get vert before p3, vector from it to p2, dot with "line normal"
	back = f2->pts[ ( j + f2->numpoints - 1 ) % f2->numpoints ];

	VectorSubtract( back, p2, delta );
	dot = DotProduct( delta, normal );

	if( dot > CONTINUOUS_EPSILON )
		return NULL; // not a convex polygon

	keep2 = dot < -CONTINUOUS_EPSILON;

	//
	// build the new polygon
	//
	if( f1->numpoints + f2->numpoints > MAXEDGES ) {
		Message( MSGWARN, "TryMerge: too many edges (%d, max = %d)", f1->numpoints + f2->numpoints, MAXEDGES );
		return NULL;
	}

	newf = NewFaceFromFace( f1 );
	ResizeFace( newf, MAXEDGES );
	newf->numpoints = 0;

	nextI = ( i + 1 ) % f1->numpoints;

	// copy first polygon
	for( k = nextI; k != i; k = ( k + 1 ) % f1->numpoints ) {
		if( k == nextI && !keep2 )
			continue;

		VectorCopy( f1->pts[ k ], newf->pts[ newf->numpoints ] );
		++newf->numpoints;
	}

	nextJ = ( j + 1 ) % f2->numpoints;

	// copy second polygon
	for( l = nextJ; l != j; l = ( l + 1 ) % f2->numpoints ) {
		if( l == nextJ && !keep1 )
			continue;

		VectorCopy( f2->pts[ l ], newf->pts[ newf->numpoints ] );
		++newf->numpoints;
	}

	// Shrink the face back to just what it needs ...
	ResizeFace( newf, newf->numpoints );

	return newf;
}

/*
===============
MergeFaceToList
===============
*/
face_t *
MergeFaceToList( face_t *face, face_t *list ) {
	face_t *newf, *f;

	for( f = list; f; f = f->next ) {
		newf = TryMerge( face, f );
		if( !newf )
			continue;
		FreeFace( face );
		ResizeFace( f, 0 );
		f->numpoints = -1; // merged out
		return MergeFaceToList( newf, list );
	}

	// didn't merge, so add at start
	face->next = list;
	return face;
}

/*
===============
FreeMergeListScraps
===============
*/
face_t *
FreeMergeListScraps( face_t *merged ) {
	face_t *head, *next;

	head = NULL;
	for(; merged; merged = next ) {
		next = merged->next;
		if( merged->numpoints == -1 )
			FreeFace( merged );
		else {
			merged->next = head;
			head = merged;
		}
	}

	return head;
}

/*
===============
MergePlaneFaces
===============
*/
void
MergePlaneFaces( surface_t *plane ) {
	face_t	*f1, *next;
	face_t	*merged;

	merged = NULL;

	for( f1 = plane->faces; f1; f1 = next ) {
		next = f1->next;
		merged = MergeFaceToList( f1, merged );
	}

	// chain all of the non-empty faces to the plane
	plane->faces = FreeMergeListScraps( merged );
}

/*
============
MergeAll
============
*/
void
MergeAll( surface_t *surfhead ) {
	surface_t *surf;
	int	mergefaces;
	face_t	*f;

	Message( MSGNOVERBOSE, "------ MergeAll ------" );

	mergefaces = 0;
	for( surf = surfhead; surf; surf = surf->next ) {
		MergePlaneFaces( surf );
		for( f = surf->faces; f; f = f->next )
			mergefaces++;
	}

	Message( MSGNOVERBOSE, "%6i mergefaces", mergefaces );
}

