/*****************************************************************************
The Dark Mod GPL Source Code

This file is part of the The Dark Mod Source Code, originally based
on the Doom 3 GPL Source Code as published in 2011.

The Dark Mod Source Code is free software: you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3 of the License,
or (at your option) any later version. For details, see LICENSE.TXT.

Project: The Dark Mod (http://www.thedarkmod.com/)

******************************************************************************/

#include "precompiled.h"
#pragma hdrstop



#include "dmap.h"
#ifdef WIN32
#include <windows.h>
//#include <GL/gl.h>
#endif

/*

  New vertexes will be created where edges cross.

  optimization requires an accurate t junction fixer.



*/

idBounds	optBounds;

#define	MAX_OPT_VERTEXES	0x10000
int			numOptVerts;
optVertex_t optVerts[MAX_OPT_VERTEXES];

#define	MAX_OPT_EDGES		0x40000
static	int		numOptEdges;
static	optEdge_t	optEdges[MAX_OPT_EDGES];

static bool IsTriangleValid( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 );
static bool IsTriangleDegenerate( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 );

static idRandom orandom;

/*
==============
ValidateEdgeCounts
==============
*/
static void ValidateEdgeCounts( optIsland_t *island ) {
	optVertex_t	*vert;
	optEdge_t	*e;
	int			c;

	for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
		c = 0;
		for ( e = vert->edges ; e ; ) {
			c++;
			if ( e->v1 == vert ) {
				e = e->v1link;
			} else if ( e->v2 == vert ) {
				e = e->v2link;
			} else {
				common->Error( "ValidateEdgeCounts: mislinked" );
			}
		}
		if ( c != 2 && c != 0 ) {
			// this can still happen at diamond intersections
//			common->Printf( "ValidateEdgeCounts: %i edges\n", c );
		}
	}
}


/*
====================
AllocEdge
====================
*/
static optEdge_t	*AllocEdge( void ) {
	optEdge_t	*e;

	if ( numOptEdges == MAX_OPT_EDGES ) {
		common->Error( "MAX_OPT_EDGES" );
	}
	e = &optEdges[ numOptEdges ];
	numOptEdges++;
	memset( e, 0, sizeof( *e ) );

	return e;
}

/*
====================
RemoveEdgeFromVert
====================
*/
static	void RemoveEdgeFromVert( optEdge_t *e1, optVertex_t *vert ) {
	optEdge_t	**prev;
	optEdge_t	*e;

	if ( !vert ) {
		return;
	}
	prev = &vert->edges;
	while ( *prev ) {
		e = *prev;
		if ( e == e1 ) {
			if ( e1->v1 == vert ) {
				*prev = e1->v1link;
			} else if ( e1->v2 == vert ) {
				*prev = e1->v2link;
			} else {
				common->Error( "RemoveEdgeFromVert: vert not found" );
			}
			return;
		}

		if ( e->v1 == vert ) {
			prev = &e->v1link;
		} else if ( e->v2 == vert ) {
			prev = &e->v2link;
		} else {
			common->Error( "RemoveEdgeFromVert: vert not found" );
		}
	}
}

/*
====================
UnlinkEdge
====================
*/
static	void UnlinkEdge( optEdge_t *e, optIsland_t *island ) {
	optEdge_t	**prev;

	RemoveEdgeFromVert( e, e->v1 );
	RemoveEdgeFromVert( e, e->v2 );

	for ( prev = &island->edges ; *prev ; prev = &(*prev)->islandLink ) {
		if ( *prev == e ) {
			*prev = e->islandLink;
			return;
		}
	}

	common->Error( "RemoveEdgeFromIsland: couldn't free edge" );
}


/*
====================
LinkEdge
====================
*/
static	void LinkEdge( optEdge_t *e ) {
	e->v1link = e->v1->edges;
	e->v1->edges = e;

	e->v2link = e->v2->edges;
	e->v2->edges = e;
}

/*
================
FindOptVertex
================
*/
static optVertex_t *FindOptVertex( idDrawVert *v, optimizeGroup_t *opt ) {
	int		i;
	float	x, y;
	optVertex_t	*vert;

	// deal with everything strictly as 2D
	x = (float)idVec3d(v->xyz).Dot(idVec3d(opt->axis[0]));
	y = (float)idVec3d(v->xyz).Dot(idVec3d(opt->axis[1]));

	// should we match based on the t-junction fixing hash verts?
	for ( i = 0 ; i < numOptVerts ; i++ ) {
		if ( optVerts[i].pv[0] == x && optVerts[i].pv[1] == y ) {
			return &optVerts[i];
		}
	}

	if ( numOptVerts >= MAX_OPT_VERTEXES ) {
		common->Error( "MAX_OPT_VERTEXES" );
		return NULL;
	}
	
	numOptVerts++;

	vert = &optVerts[i];
	memset( vert, 0, sizeof( *vert ) );
	vert->v = *v;
	vert->pv[0] = x;
	vert->pv[1] = y;
	vert->pv[2] = 0;

	optBounds.AddPoint( vert->pv );

	return vert;
}

/*
================
DrawAllEdges
================
*/
static	void DrawAllEdges( void ) {
	int		i;

	if ( !dmapGlobals.drawflag ) {
		return;
	}

	Draw_ClearWindow();

	qglBegin( GL_LINES );
	for ( i = 0 ; i < numOptEdges ; i++ ) {
		if ( optEdges[i].v1 == NULL ) {
			continue;
		}
		qglColor3f( 1, 0, 0 );
		qglVertex3fv( optEdges[i].v1->pv.ToFloatPtr() );
		qglColor3f( 0, 0, 0 );
		qglVertex3fv( optEdges[i].v2->pv.ToFloatPtr() );
	}
	qglEnd();
	qglFlush();

//	GLimp_SwapBuffers();
}

/*
================
DrawVerts
================
*/
static void DrawVerts( optIsland_t *island ) {
	optVertex_t	*vert;

	if ( !dmapGlobals.drawflag ) {
		return;
	}

	qglEnable( GL_BLEND );
	qglBlendFunc( GL_ONE, GL_ONE );
	qglColor3f( 0.3f, 0.3f, 0.3f );
	qglPointSize( 3 );
	qglBegin( GL_POINTS );
	for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
		qglVertex3fv( vert->pv.ToFloatPtr() );
	}
	qglEnd();
	qglDisable( GL_BLEND );
	qglFlush();
}

/*
================
DrawEdges
================
*/
static	void DrawEdges( optIsland_t *island ) {
	optEdge_t	*edge;

	if ( !dmapGlobals.drawflag ) {
		return;
	}

	Draw_ClearWindow();

	qglBegin( GL_LINES );
	for ( edge = island->edges ; edge ; edge = edge->islandLink ) {
		if ( edge->v1 == NULL ) {
			continue;
		}
		qglColor3f( 1, 0, 0 );
		qglVertex3fv( edge->v1->pv.ToFloatPtr() );
		qglColor3f( 0, 0, 0 );
		qglVertex3fv( edge->v2->pv.ToFloatPtr() );
	}
	qglEnd();
	qglFlush();
	qglFinish();

//	GLimp_SwapBuffers();
}

//=================================================================

/*
=================
VertexBetween
=================
*/
static bool VertexBetween( const optVertex_t *p1, const optVertex_t *v1, const optVertex_t *v2 ) {
	idVec3d	d1, d2;
	float	d;

	d1 = idVec3d(p1->pv) - idVec3d(v1->pv);
	d2 = idVec3d(p1->pv) - idVec3d(v2->pv);
	d = (float) d1.Dot(d2);
	if ( d < 0 ) {
		return true;
	}
	return false;
}


idCVar dmap_optimizeExactTjuncIntersection(
	"dmap_optimizeExactTjuncIntersection", "1", CVAR_BOOL | CVAR_SYSTEM,
	"Ensure that exact T-junctions are computed exactly in "
	"EdgeIntersection function of optimize triangulation algorithm "
	"(small improvement in TDM 2.10 and later)"
);

/*
====================
EdgeIntersection

Creates a new optVertex_t where the line segments cross.
This should only be called if PointsStraddleLine returned true

Will return NULL if the lines are colinear
====================
*/
static	optVertex_t *EdgeIntersection( const optVertex_t *p1, const optVertex_t *p2, 
									  const optVertex_t *l1, const optVertex_t *l2, optimizeGroup_t *opt ) {
	double	f;
	idDrawVert	*v;
	idVec3d	dir1, dir2, cross1, cross2;

	dir1 = idVec3d(p1->pv) - idVec3d(l1->pv);
	dir2 = idVec3d(p1->pv) - idVec3d(l2->pv);
	cross1 = dir1.Cross( dir2 );

	dir1 = idVec3d(p2->pv) - idVec3d(l1->pv);
	dir2 = idVec3d(p2->pv) - idVec3d(l2->pv);
	cross2 = dir1.Cross( dir2 );

	if (dmap_optimizeExactTjuncIntersection.GetBool() && cross1.z != 0.0 && cross2.z != 0.0) {
		//stgatilov: check if l1 or l2 is T-junction
		dir1 = idVec3d(l1->pv) - idVec3d(p1->pv);
		dir2 = idVec3d(l1->pv) - idVec3d(p2->pv);
		idVec3d cross1x = dir1.Cross( dir2 );
		dir1 = idVec3d(l2->pv) - idVec3d(p1->pv);
		dir2 = idVec3d(l2->pv) - idVec3d(p2->pv);
		idVec3d cross2x = dir1.Cross( dir2 );
		if (cross1x.z == 0.0 || cross2x.z == 0.0) {
			//intersect lines in opposite direction
			//so that T-junction is found exactly
			idSwap(l1, p1);
			idSwap(l2, p2);
			cross1 = cross1x;
			cross2 = cross2x;
		}
	}

	if ( float(cross1[2] - cross2[2]) == 0 ) {
		return NULL;
	}

	f = cross1[2] / ( cross1[2] - cross2[2] );

	// FIXME: how are we freeing this, since it doesn't belong to a tri?
	v = (idDrawVert *)Mem_Alloc( sizeof( *v ) );
	memset( v, 0, sizeof( *v ) );

	v->xyz = idVec3( idVec3d(p1->v.xyz) * ( 1.0 - f ) + idVec3d(p2->v.xyz) * f );
	v->normal = idVec3( idVec3d(p1->v.normal) * ( 1.0 - f ) + idVec3d(p2->v.normal) * f );
	v->normal.Normalize();
	v->st[0] = p1->v.st[0] * ( 1.0 - f ) + p2->v.st[0] * f;
	v->st[1] = p1->v.st[1] * ( 1.0 - f ) + p2->v.st[1] * f;

	return FindOptVertex( v, opt );
}


/*
====================
PointsStraddleLine

Colinear is considdered crossing.
====================
*/
static	bool PointsStraddleLine( optVertex_t *p1, optVertex_t *p2, optVertex_t *l1, optVertex_t *l2 ) {
	bool	t1, t2;

	t1 = IsTriangleDegenerate( l1, l2, p1 );
	t2 = IsTriangleDegenerate( l1, l2, p2 );
	if ( t1 && t2 ) {
		// colinear case
		float	s1, s2, s3, s4;
		bool	positive, negative;

		s1 = ( p1->pv - l1->pv ) * ( l2->pv - l1->pv );
		s2 = ( p2->pv - l1->pv ) * ( l2->pv - l1->pv );
		s3 = ( p1->pv - l2->pv ) * ( l2->pv - l1->pv );
		s4 = ( p2->pv - l2->pv ) * ( l2->pv - l1->pv );

		if ( s1 > 0 || s2 > 0 || s3 > 0 || s4 > 0 ) {
			positive = true;
		} else {
			positive = false;
		}
		if ( s1 < 0 || s2 < 0 || s3 < 0 || s4 < 0 ) {
			negative = true;
		} else {
			negative = false;
		}

		if ( positive && negative ) {
			return true;
		}
		return false;
	} else if ( p1 != l1 && p1 != l2 && p2 != l1 && p2 != l2 ) {
		// no shared verts
		t1 = IsTriangleValid( l1, l2, p1 );
		t2 = IsTriangleValid( l1, l2, p2 );
		if ( t1 && t2 ) {
			return false;
		}

		t1 = IsTriangleValid( l1, p1, l2 );
		t2 = IsTriangleValid( l1, p2, l2 );
		if ( t1 && t2 ) {
			return false;
		}

		return true;
	} else {
		// a shared vert, not colinear, so not crossing
		return false;
	}
}


/*
====================
EdgesCross
====================
*/
static	bool EdgesCross( optVertex_t *a1, optVertex_t *a2, optVertex_t *b1, optVertex_t *b2 ) {
	// if both verts match, consider it to be crossed
	if ( a1 == b1 && a2 == b2 ) {
		return true;
	}
	if ( a1 == b2 && a2 == b1 ) {
		return true;
	}
	// if only one vert matches, it might still be colinear, which
	// would be considered crossing

	// if both lines' verts are on opposite sides of the other
	// line, it is crossed
	if ( !PointsStraddleLine( a1, a2, b1, b2 ) ) {
		return false;
	}
	if ( !PointsStraddleLine( b1, b2, a1, a2 ) ) {
		return false;
	}

	return true;
}

/*
====================
TryAddNewEdge

====================
*/
static	bool TryAddNewEdge( optVertex_t *v1, optVertex_t *v2, optIsland_t *island ) {
	optEdge_t	*e;

	// if the new edge crosses any other edges, don't add it
	for ( e = island->edges ; e ; e = e->islandLink ) {
		if ( EdgesCross( e->v1, e->v2, v1, v2 ) ) {
			return false;
		}
	}

	if ( dmapGlobals.drawflag ) {
		qglBegin( GL_LINES );
		qglColor3f( 0, ( 128 + orandom.RandomInt( 127 ) )/ 255.0, 0 );
		qglVertex3fv( v1->pv.ToFloatPtr() );
		qglVertex3fv( v2->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}
	// add it
	e = AllocEdge();

	e->islandLink = island->edges;
	island->edges = e;
	e->v1 = v1;
	e->v2 = v2;

	e->created = true;

	// link the edge to its verts
	LinkEdge( e );

	return true;
}

typedef struct {
	optVertex_t	*v1, *v2;
	float		length;
} edgeLength_t;


static	int LengthSort( const void *a, const void *b ) {
	const edgeLength_t	*ea, *eb;

	ea = (const edgeLength_t	*)a;
	eb = (const edgeLength_t	*)b;
	if ( ea->length < eb->length ) {
		return -1;
	}
	if ( ea->length > eb->length ) {
		return 1;
	}
	return 0;
}

idCVar dmap_optimizeTriangulation(
	"dmap_optimizeTriangulation", "1", CVAR_BOOL | CVAR_SYSTEM,
	"Controls which algorithm is used to optimize triangulations (see #5488):\n"
	"  0 - slow greedy algorithm: insert edges by length increasing\n"
	"      (default in TDM 2.09 and before)\n"
	"  1 - fast algorithm based on planar graph and ear cutting triangulation\n"
	"      (default in TDM 2.10 and after)\n"
);

static void AddTriangulationEdges( optIsland_t *island );
/*
==================
AddInteriorEdges

Add all possible edges between the verts
==================
*/
static	void AddInteriorEdges( optIsland_t *island ) {
	if (dmap_optimizeTriangulation.GetBool()) {
		AddTriangulationEdges( island );
		return;
	}

	int		c_addedEdges;
	optVertex_t	*vert, *vert2;
	int		c_verts;
	edgeLength_t	*lengths;
	int				numLengths;
	int				i;

	DrawVerts( island );

	// count the verts
	c_verts = 0;
	for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
		if ( !vert->edges ) {
			continue;
		}
		c_verts++;
	}

	// allocate space for all the lengths
	lengths = (edgeLength_t *)Mem_Alloc( sizeof( *lengths ) * c_verts * c_verts / 2 );
	numLengths = 0;
	for ( vert = island->verts ; vert ; vert = vert->islandLink ) {
		if ( !vert->edges ) {
			continue;
		}
		for ( vert2 = vert->islandLink ; vert2 ; vert2 = vert2->islandLink ) {
			idVec3		dir;

			if ( !vert2->edges ) {
				continue;
			}
			lengths[numLengths].v1 = vert;
			lengths[numLengths].v2 = vert2;
			dir = ( vert->pv - vert2->pv ) ;
			lengths[numLengths].length = dir.Length();
			numLengths++;
		}
	}


	// sort by length, shortest first
	qsort( lengths, numLengths, sizeof( lengths[0] ), LengthSort );

	// try to create them in that order
	c_addedEdges = 0;
	for ( i = 0 ; i < numLengths ; i++ ) {
		if ( TryAddNewEdge( lengths[i].v1, lengths[i].v2, island ) ) {
			c_addedEdges++;
		}
	}

	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i tested segments\n", numLengths );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i added interior edges\n", c_addedEdges );

	Mem_Free( lengths );
}



//==================================================================

/*
====================
RemoveIfColinear

====================
*/
#define	COLINEAR_EPSILON	0.1
static	void RemoveIfColinear( optVertex_t *ov, optIsland_t *island ) {
	optEdge_t	*e, *e1, *e2;
	optVertex_t *v1, *v2, *v3;
	idVec3		dir1, dir2;
	float		dist;
	idVec3		point;
	idVec3		offset;
	float		off;

	v2 = ov;

	// we must find exactly two edges before testing for colinear
	e1 = NULL;
	e2 = NULL;
	for ( e = ov->edges ; e ; ) {
		if ( !e1 ) {
			e1 = e;
		} else if ( !e2 ) {
			e2 = e;
		} else {
			return;		// can't remove a vertex with three edges
		}
		if ( e->v1 == v2 ) {
			e = e->v1link;
		} else if ( e->v2 == v2 ) {
			e = e->v2link;
		} else {
			common->Error( "RemoveIfColinear: mislinked edge" );
            return;
		}
	}

	// can't remove if no edges
	if ( !e1 ) {
		return;
	}

	if ( !e2 ) {
		// this may still happen legally when a tiny triangle is
		// the only thing in a group
		PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "WARNING: vertex with only one edge\n" );
		return;
	}

	if ( e1->v1 == v2 ) {
		v1 = e1->v2;
	} else if ( e1->v2 == v2 ) {
		v1 = e1->v1;
	} else {
		common->Error( "RemoveIfColinear: mislinked edge" );
        return;
	}
	if ( e2->v1 == v2 ) {
		v3 = e2->v2;
	} else if ( e2->v2 == v2 ) {
		v3 = e2->v1;
	} else {
		common->Error( "RemoveIfColinear: mislinked edge" );
        return;
	}

	if ( v1 == v3 ) {
		common->Error( "RemoveIfColinear: mislinked edge" );
        return;
	}

	// they must point in opposite directions
	dist = ( v3->pv - v2->pv ) * ( v1->pv - v2->pv );
	if ( dist >= 0 ) {
		return;
	}

	// see if they are colinear
	VectorSubtract( v3->v.xyz, v1->v.xyz, dir1 );
	dir1.Normalize();
	VectorSubtract( v2->v.xyz, v1->v.xyz, dir2 );
	dist = DotProduct( dir2, dir1 );
	VectorMA( v1->v.xyz, dist, dir1, point );
	VectorSubtract( point, v2->v.xyz, offset );
	off = offset.Length();

	if ( off > COLINEAR_EPSILON ) {
		return;
	}

	if ( dmapGlobals.drawflag ) {
		qglBegin( GL_LINES );
		qglColor3f( 1, 1, 0 );
		qglVertex3fv( v1->pv.ToFloatPtr() );
		qglVertex3fv( v2->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
		qglBegin( GL_LINES );
		qglColor3f( 0, 1, 1 );
		qglVertex3fv( v2->pv.ToFloatPtr() );
		qglVertex3fv( v3->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}

	// replace the two edges with a single edge
	UnlinkEdge( e1, island );
	UnlinkEdge( e2, island );

	// v2 should have no edges now
	if ( v2->edges ) {
		common->Error( "RemoveIfColinear: didn't remove properly" );
        return;
	}


	// if there is an existing edge that already
	// has these exact verts, we have just collapsed a
	// sliver triangle out of existance, and all the edges
	// can be removed
	for ( e = island->edges ; e ; e = e->islandLink ) {
		if ( ( e->v1 == v1 && e->v2 == v3 ) 
		|| ( e->v1 == v3 && e->v2 == v1 ) ) {
			UnlinkEdge( e, island );
			RemoveIfColinear( v1, island );
			RemoveIfColinear( v3, island );
			return;
		}
	}

	// if we can't add the combined edge, link
	// the originals back in
	if ( !TryAddNewEdge( v1, v3, island ) ) {
		e1->islandLink = island->edges;
		island->edges = e1;
		LinkEdge( e1 );

		e2->islandLink = island->edges;
		island->edges = e2;
		LinkEdge( e2 );
		return;
	}

	// recursively try to combine both verts now,
	// because things may have changed since the last combine test
	RemoveIfColinear( v1, island );
	RemoveIfColinear( v3, island );
}

/*
====================
CombineColinearEdges
====================
*/
static	void CombineColinearEdges( optIsland_t *island ) {
	int			c_edges;
	optVertex_t	*ov;
	optEdge_t	*e;

	c_edges = 0;
	for ( e = island->edges ; e ; e = e->islandLink ) {
		c_edges++;
	}
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original exterior edges\n", c_edges );

	for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
		RemoveIfColinear( ov, island );
	}

	c_edges = 0;
	for ( e = island->edges ; e ; e = e->islandLink ) {
		c_edges++;
	}
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i optimized exterior edges\n", c_edges );
}


//==================================================================

/*
===================
FreeOptTriangles

===================
*/
static void FreeOptTriangles( optIsland_t *island ) {
	optTri_t	*opt, *next;

	for ( opt = island->tris ; opt ; opt = next ) {
		next = opt->next;
		Mem_Free( opt );
	}

	island->tris = NULL;
}


/*
=================
IsTriangleValid

empty area will be considered invalid.
Due to some truly aweful epsilon issues, a triangle can switch between
valid and invalid depending on which order you look at the verts, so
consider it invalid if any one of the possibilities is invalid.
=================
*/
static bool IsTriangleValid( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 ) {
	idVec3d	d1, d2, normal;

	d1 = idVec3d(v2->pv) - idVec3d(v1->pv);
	d2 = idVec3d(v3->pv) - idVec3d(v1->pv);
	normal = d1.Cross( d2 );
	if ( float(normal[2]) <= 0 ) {
		return false;
	}

	d1 = idVec3d(v3->pv) - idVec3d(v2->pv);
	d2 = idVec3d(v1->pv) - idVec3d(v2->pv);
	normal = d1.Cross( d2 );
	if ( float(normal[2]) <= 0 ) {
		return false;
	}

	d1 = idVec3d(v1->pv) - idVec3d(v3->pv);
	d2 = idVec3d(v2->pv) - idVec3d(v3->pv);
	normal = d1.Cross( d2 );
	if ( float(normal[2]) <= 0 ) {
		return false;
	}

	return true;
}


/*
=================
IsTriangleDegenerate

Returns false if it is either front or back facing
=================
*/
static bool IsTriangleDegenerate( const optVertex_t *v1, const optVertex_t *v2, const optVertex_t *v3 ) {
#if 1
	auto d1 = idVec3d(v2->pv) - idVec3d(v1->pv);
	auto d2 = idVec3d(v3->pv) - idVec3d(v1->pv);
	idVec3d normal = d1.Cross( d2 );
	if ( float(normal[2]) == 0 ) {
		return true;
	}
	return false;
#else
	return (bool)!IsTriangleValid( v1, v2, v3 );
#endif
}


/*
==================
PointInTri

Tests if a 2D point is inside an original triangle
==================
*/
static bool PointInTri( const idVec3 &p, const mapTri_t *tri, optIsland_t *island ) {
	idVec3d	d1, d2, normal;

	// the normal[2] == 0 case is not uncommon when a square is triangulated in
	// the opposite manner to the original

	d1 = idVec3d(tri->optVert[0]->pv) - idVec3d(p);
	d2 = idVec3d(tri->optVert[1]->pv) - idVec3d(p);
	normal = d1.Cross( d2 );
	if ( (float)normal[2] < 0 ) {
		return false;
	}

	d1 = idVec3d(tri->optVert[1]->pv) - idVec3d(p);
	d2 = idVec3d(tri->optVert[2]->pv) - idVec3d(p);
	normal = d1.Cross( d2 );
	if ( (float)normal[2] < 0 ) {
		return false;
	}

	d1 = idVec3d(tri->optVert[2]->pv) - idVec3d(p);
	d2 = idVec3d(tri->optVert[0]->pv) - idVec3d(p);
	normal = d1.Cross( d2 );
	if ( (float)normal[2] < 0 ) {
		return false;
	}

	return true;
}


/*
====================
LinkTriToEdge

====================
*/
static void LinkTriToEdge( optTri_t *optTri, optEdge_t *edge ) {
	if ( ( edge->v1 == optTri->v[0] && edge->v2 == optTri->v[1] )
		|| ( edge->v1 == optTri->v[1] && edge->v2 == optTri->v[2] )
		|| ( edge->v1 == optTri->v[2] && edge->v2 == optTri->v[0] ) ) {
		if ( edge->backTri ) {
			PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "Warning: LinkTriToEdge: already in use\n" );
			return;
		}
		edge->backTri = optTri;
		return;
	}
	if ( ( edge->v1 == optTri->v[1] && edge->v2 == optTri->v[0] )
		|| ( edge->v1 == optTri->v[2] && edge->v2 == optTri->v[1] )
		|| ( edge->v1 == optTri->v[0] && edge->v2 == optTri->v[2] ) ) {
		if ( edge->frontTri ) {
			PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "Warning: LinkTriToEdge: already in use\n" );
			return;
		}
		edge->frontTri = optTri;
		return;
	}
	common->Error( "LinkTriToEdge: edge not found on tri" );
}

/*
===============
CreateOptTri
===============
*/
static void CreateOptTri( optVertex_t *first, optEdge_t *e1, optEdge_t *e2, optIsland_t *island ) {
	optEdge_t		*opposite;
	optVertex_t		*second, *third;
	optTri_t		*optTri;
	mapTri_t		*tri;

	if ( e1->v1 == first ) {
		second = e1->v2;
	} else if ( e1->v2 == first ) {
		second = e1->v1;
	} else {
		common->Error( "CreateOptTri: mislinked edge" );
        return;
	}

	if ( e2->v1 == first ) {
		third = e2->v2;
	} else if ( e2->v2 == first ) {
		third = e2->v1;
	} else {
		common->Error( "CreateOptTri: mislinked edge" );
        return;
	}

	if ( !IsTriangleValid( first, second, third ) ) {
		common->Error( "CreateOptTri: invalid" );
        return;
	}

//DrawEdges( island );

		// identify the third edge
	if ( dmapGlobals.drawflag ) {
		qglColor3f(1,1,0);
		qglBegin( GL_LINES );
		qglVertex3fv( e1->v1->pv.ToFloatPtr() );
		qglVertex3fv( e1->v2->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
		qglColor3f(0,1,1);
		qglBegin( GL_LINES );
		qglVertex3fv( e2->v1->pv.ToFloatPtr() );
		qglVertex3fv( e2->v2->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}

	for ( opposite = second->edges ; opposite ; ) {
		if ( opposite != e1 && ( opposite->v1 == third || opposite->v2 == third ) ) {
			break;
		}
		if ( opposite->v1 == second ) {
			opposite = opposite->v1link;
		} else if ( opposite->v2 == second ) {
			opposite = opposite->v2link;
		} else {
			common->Error( "BuildOptTriangles: mislinked edge" );
            return;
		}
	}

	if ( !opposite ) {
		PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "Warning: BuildOptTriangles: couldn't locate opposite\n" );
		return;
	}

	if ( dmapGlobals.drawflag ) {
		qglColor3f(1,0,1);
		qglBegin( GL_LINES );
		qglVertex3fv( opposite->v1->pv.ToFloatPtr() );
		qglVertex3fv( opposite->v2->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}

	// create new triangle
	optTri = (optTri_t *)Mem_Alloc( sizeof( *optTri ) );
	optTri->v[0] = first;
	optTri->v[1] = second;
	optTri->v[2] = third;
	optTri->midpoint = ( optTri->v[0]->pv + optTri->v[1]->pv + optTri->v[2]->pv ) * ( 1.0f / 3.0f );
	optTri->next = island->tris;
	island->tris = optTri;

	if ( dmapGlobals.drawflag ) {
		qglColor3f( 1, 1, 1 );
		qglPointSize( 4 );
		qglBegin( GL_POINTS );
		qglVertex3fv( optTri->midpoint.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}

	// find the midpoint, and scan through all the original triangles to
	// see if it is inside any of them
	for ( tri = island->group->triList ; tri ; tri = tri->next ) {
		if ( PointInTri( optTri->midpoint, tri, island ) ) {
			break;
		}
	}
	if ( tri ) {
		optTri->filled = true;
	} else {
		optTri->filled = false;
	}
	if ( dmapGlobals.drawflag ) {
		if ( optTri->filled ) {
			qglColor3f( ( 128 + orandom.RandomInt( 127 ) )/ 255.0, 0, 0 );
		} else {
			qglColor3f( 0, ( 128 + orandom.RandomInt( 127 ) ) / 255.0, 0 );
		}
		qglBegin( GL_TRIANGLES );
		qglVertex3fv( optTri->v[0]->pv.ToFloatPtr() );
		qglVertex3fv( optTri->v[1]->pv.ToFloatPtr() );
		qglVertex3fv( optTri->v[2]->pv.ToFloatPtr() );
		qglEnd();
		qglColor3f( 1, 1, 1 );
		qglBegin( GL_LINE_LOOP );
		qglVertex3fv( optTri->v[0]->pv.ToFloatPtr() );
		qglVertex3fv( optTri->v[1]->pv.ToFloatPtr() );
		qglVertex3fv( optTri->v[2]->pv.ToFloatPtr() );
		qglEnd();
		qglFlush();
	}

	// link the triangle to it's edges
	LinkTriToEdge( optTri, e1 );
	LinkTriToEdge( optTri, e2 );
	LinkTriToEdge( optTri, opposite );
}

// debugging tool
#if 0
static void ReportNearbyVertexes( const optVertex_t *v, const optIsland_t *island ) {
	const optVertex_t	*ov;
	float		d;
	idVec3		vec;

	common->Printf( "verts near 0x%p (%f, %f)\n", v,  v->pv[0], v->pv[1] );
	for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
		if ( ov == v ) {
			continue;
		}

		vec = ov->pv - v->pv;

		d = vec.Length();
		if ( d < 1 ) {
			common->Printf( "0x%p = (%f, %f)\n", ov, ov->pv[0], ov->pv[1] );
		}
	}
}
#endif

/*
====================
BuildOptTriangles

Generate a new list of triangles from the optEdeges
====================
*/
static void BuildOptTriangles( optIsland_t *island ) {
    optVertex_t		*ov, *second = NULL, *third = NULL, *middle = NULL;
    optEdge_t		*e1, *e1Next = NULL, *e2, *e2Next = NULL, *check, *checkNext = NULL;

	// free them
	FreeOptTriangles( island );

	// clear the vertex emitted flags
	for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
		ov->emited = false;
	}

	// clear the edge triangle links
	for ( check = island->edges ; check ; check = check->islandLink ) {
		check->frontTri = check->backTri = NULL;
	}

	// check all possible triangle made up out of the
	// edges coming off the vertex
	for ( ov = island->verts ; ov ; ov = ov->islandLink ) {
		if ( !ov->edges ) {
			continue;
		}

#if 0
if ( dmapGlobals.drawflag && ov == (optVertex_t *)0x1845a60 ) {
for ( e1 = ov->edges ; e1 ; e1 = e1Next ) {
	qglBegin( GL_LINES );
	qglColor3f( 0,1,0 );
	qglVertex3fv( e1->v1->pv.ToFloatPtr() );
	qglVertex3fv( e1->v2->pv.ToFloatPtr() );
	qglEnd();
	qglFlush();
	if ( e1->v1 == ov ) {
		e1Next = e1->v1link;
	} else if ( e1->v2 == ov ) {
		e1Next = e1->v2link;
	}
}
}
#endif
		for ( e1 = ov->edges ; e1 ; e1 = e1Next ) {
			if ( e1->v1 == ov ) {
				second = e1->v2;
				e1Next = e1->v1link;
			} else if ( e1->v2 == ov ) {
				second = e1->v1;
				e1Next = e1->v2link;
			} else {
				common->Error( "BuildOptTriangles: mislinked edge" );
			}

			// if the vertex has already been used, it can't be used again
			if ( second->emited ) {
				continue;
			}

			for ( e2 = ov->edges ; e2 ; e2 = e2Next ) {
				if ( e2->v1 == ov ) {
					third = e2->v2;
					e2Next = e2->v1link;
				} else if ( e2->v2 == ov ) {
					third = e2->v1;
					e2Next = e2->v2link;
				} else {
					common->Error( "BuildOptTriangles: mislinked edge" );
				}
				if ( e2 == e1 ) {
					continue;
				}

				// if the vertex has already been used, it can't be used again
				if ( third->emited ) {
					continue;
				}

				// if the triangle is backwards or degenerate, don't use it
				if ( !IsTriangleValid( ov, second, third ) ) {
					continue;
				}

				// see if any other edge bisects these two, which means
				// this triangle shouldn't be used
				for ( check = ov->edges ; check ; check = checkNext ) {
					if ( check->v1 == ov ) {
						middle = check->v2;
						checkNext = check->v1link;
					} else if ( check->v2 == ov ) {
						middle = check->v1;
						checkNext = check->v2link;
					} else {
						common->Error( "BuildOptTriangles: mislinked edge" );
					}

					if ( check == e1 || check == e2 ) {
						continue;
					}

					if ( IsTriangleValid( ov, second, middle ) 
						&& IsTriangleValid( ov, middle, third ) ) {
						break;	// should use the subdivided ones
					}
				}

				if ( check ) {
					continue;	// don't use it
				}

				// the triangle is valid
				CreateOptTri( ov, e1, e2, island );
			}
		}

		// later vertexes will not emit triangles that use an
		// edge that this vert has already used
		ov->emited = true;
	}
}



/*
====================
RegenerateTriangles

Add new triangles to the group's regeneratedTris
====================
*/
static	void	RegenerateTriangles( optIsland_t *island ) {
	optTri_t		*optTri;
	mapTri_t		*tri;
	int				c_out;

	c_out = 0;

	for ( optTri = island->tris ; optTri ; optTri = optTri->next ) {
		if ( !optTri->filled ) {
			continue;
		}

		// create a new mapTri_t
		tri = AllocTri();

		tri->material = island->group->material;
		tri->mergeGroup = island->group->mergeGroup;

		tri->v[0] = optTri->v[0]->v;
		tri->v[1] = optTri->v[1]->v;
		tri->v[2] = optTri->v[2]->v;

		idPlane plane;
		PlaneForTri( tri, plane );
		if ( plane.Normal() * dmapGlobals.mapPlanes[ island->group->planeNum ].Normal() <= 0 ) {
			// this can happen reasonably when a triangle is nearly degenerate in
			// optimization planar space, and winds up being degenerate in 3D space
			PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "WARNING: backwards triangle generated!\n" );
			// discard it
			FreeTri( tri );
			continue;
		}

		c_out++;
		tri->next = island->group->regeneratedTris;
		island->group->regeneratedTris = tri;
	}

	FreeOptTriangles( island );

	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i tris out\n", c_out );
}

//===========================================================================

/*
====================
RemoveInteriorEdges

Edges that have triangles of the same type (filled / empty)
on both sides will be removed
====================
*/
static	void RemoveInteriorEdges( optIsland_t *island ) {
	int		c_interiorEdges;
	int		c_exteriorEdges;
	optEdge_t	*e, *next;
	bool	front, back;

	c_exteriorEdges = 0;
	c_interiorEdges = 0;
	for ( e = island->edges ; e ; e = next ) {
		// we might remove the edge, so get the next link now
		next = e->islandLink;

		if ( !e->frontTri ) {
			front = false;
		} else {
			front = e->frontTri->filled;
		}
		if ( !e->backTri ) {
			back = false;
		} else {
			back = e->backTri->filled;
		}

		if ( front == back ) {
			// free the edge
			UnlinkEdge( e, island );
			c_interiorEdges++;
			continue;
		}

		c_exteriorEdges++;
	}

	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original interior edges\n", c_interiorEdges );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original exterior edges\n", c_exteriorEdges );
}

//==================================================================================

typedef struct {
	optVertex_t	*v1, *v2;
} originalEdges_t;

/*
=================
AddEdgeIfNotAlready
=================
*/
void AddEdgeIfNotAlready( optVertex_t *v1, optVertex_t *v2 ) {
	optEdge_t	*e;

	// make sure that there isn't an identical edge already added
	for ( e = v1->edges ; e ; ) {
		if ( ( e->v1 == v1 && e->v2 == v2 ) || ( e->v1 == v2 && e->v2 == v1 ) ) {
			return;		// already added
		}
		if ( e->v1 == v1 ) {
			e = e->v1link;
		} else if ( e->v2 == v1 ) {
			e = e->v2link;
		} else {
			common->Error( "SplitEdgeByList: bad edge link" );
		}
	}

	// this edge is a keeper
	e = AllocEdge();
	e->v1 = v1;
	e->v2 = v2;

	e->islandLink = NULL;

	// link the edge to its verts
	LinkEdge( e );
}



/*
=================
DrawOriginalEdges
=================
*/
static void DrawOriginalEdges( int numOriginalEdges, originalEdges_t *originalEdges ) {
	int		i;

	if ( !dmapGlobals.drawflag ) {
		return;
	}
	Draw_ClearWindow();

	qglBegin( GL_LINES );
	for ( i = 0 ; i < numOriginalEdges ; i++ ) {
		qglColor3f( 1, 0, 0 );
		qglVertex3fv( originalEdges[i].v1->pv.ToFloatPtr() );
		qglColor3f( 0, 0, 0 );
		qglVertex3fv( originalEdges[i].v2->pv.ToFloatPtr() );
	}
	qglEnd();
	qglFlush();
}


typedef struct edgeCrossing_s {
	struct edgeCrossing_s	*next;
	optVertex_t		*ov;
} edgeCrossing_t;

static	originalEdges_t	*originalEdges;
static	int				numOriginalEdges;

/*
=================
AddOriginalTriangle
=================
*/
static void AddOriginalTriangle( optVertex_t *v[3] ) {
	optVertex_t		*v1, *v2;

	// if this triangle is backwards (possible with epsilon issues)
	// ignore it completely
	if ( !IsTriangleValid( v[0], v[1], v[2] ) ) {
		PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "WARNING: backwards triangle in input!\n" );
		return;
	}

	for ( int i = 0 ; i < 3 ; i++ ) {
		v1 = v[i];
		v2 = v[(i+1)%3];

		if ( v1 == v2 ) {
			// this probably shouldn't happen, because the
			// tri would be degenerate
			continue;
		}
		int j;
		// see if there is an existing one
		for ( j = 0 ; j < numOriginalEdges ; j++ ) {
			if ( originalEdges[j].v1 == v1 && originalEdges[j].v2 == v2 ) {
				break;
			}
			if ( originalEdges[j].v2 == v1 && originalEdges[j].v1 == v2 ) {
				break;
			}
		}

		if ( j == numOriginalEdges ) {
			// add it
			originalEdges[j].v1 = v1;
			originalEdges[j].v2 = v2;
			numOriginalEdges++;
		}
	}
}

/*
=================
AddOriginalEdges
=================
*/
static	void AddOriginalEdges( optimizeGroup_t *opt ) {
	mapTri_t		*tri;
	optVertex_t		*v[3];
	int				numTris;

	PrintIfVerbosityAtLeast( VL_VERBOSE, "----\n" );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original tris\n", CountTriList( opt->triList ) );

	optBounds.Clear();

	// allocate space for max possible edges
	numTris = CountTriList( opt->triList );
	originalEdges = (originalEdges_t *)Mem_Alloc( numTris * 3 * sizeof( *originalEdges ) );
	numOriginalEdges = 0;

	// add all unique triangle edges
	numOptVerts = 0;
	numOptEdges = 0;
	for ( tri = opt->triList ; tri ; tri = tri->next ) {
		v[0] = tri->optVert[0] = FindOptVertex( &tri->v[0], opt );
		v[1] = tri->optVert[1] = FindOptVertex( &tri->v[1], opt );
		v[2] = tri->optVert[2] = FindOptVertex( &tri->v[2], opt );

		AddOriginalTriangle( v );
	}
}

/*
=====================
SplitOriginalEdgesAtCrossings
=====================
*/
void SplitOriginalEdgesAtCrossings( optimizeGroup_t *opt ) {
	int				i, j, k, l;
	int				numOriginalVerts;
	edgeCrossing_t	**crossings;

	numOriginalVerts = numOptVerts;
	// now split any crossing edges and create optEdges
	// linked to the vertexes

	// debug drawing bounds
	dmapGlobals.drawBounds = optBounds;

	dmapGlobals.drawBounds[0][0] -= 2;
	dmapGlobals.drawBounds[0][1] -= 2;
	dmapGlobals.drawBounds[1][0] += 2;
	dmapGlobals.drawBounds[1][1] += 2;

	// generate crossing points between all the original edges
	crossings = (edgeCrossing_t **)Mem_ClearedAlloc( numOriginalEdges * sizeof( *crossings ) );

	for ( i = 0 ; i < numOriginalEdges ; i++ ) {
		if ( dmapGlobals.drawflag ) {
			DrawOriginalEdges( numOriginalEdges, originalEdges );
			qglBegin( GL_LINES );
			qglColor3f( 0, 1, 0 );
			qglVertex3fv( originalEdges[i].v1->pv.ToFloatPtr() );
			qglColor3f( 0, 0, 1 );
			qglVertex3fv( originalEdges[i].v2->pv.ToFloatPtr() );
			qglEnd();
			qglFlush();
		}
		for ( j = i+1 ; j < numOriginalEdges ; j++ ) {
			optVertex_t	*v1, *v2, *v3, *v4;
			optVertex_t	*newVert;
			edgeCrossing_t	*cross;

			v1 = originalEdges[i].v1;
			v2 = originalEdges[i].v2;
			v3 = originalEdges[j].v1;
			v4 = originalEdges[j].v2;

			if ( !EdgesCross( v1, v2, v3, v4 ) ) {
				continue;
			}

			// this is the only point in optimization where
			// completely new points are created, and it only
			// happens if there is overlapping coplanar
			// geometry in the source triangles
			newVert = EdgeIntersection( v1, v2, v3, v4, opt );

			if ( !newVert ) {
//common->Printf( "lines %i (%i to %i) and %i (%i to %i) are colinear\n", i, v1 - optVerts, v2 - optVerts, 
//		   j, v3 - optVerts, v4 - optVerts );	// !@#
				// colinear, so add both verts of each edge to opposite
				if ( VertexBetween( v3, v1, v2 ) ) {
					cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
					cross->ov = v3;
					cross->next = crossings[i];
					crossings[i] = cross;
				}

				if ( VertexBetween( v4, v1, v2 ) ) {
					cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
					cross->ov = v4;
					cross->next = crossings[i];
					crossings[i] = cross;
				}

				if ( VertexBetween( v1, v3, v4 ) ) {
					cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
					cross->ov = v1;
					cross->next = crossings[j];
					crossings[j] = cross;
				}

				if ( VertexBetween( v2, v3, v4 ) ) {
					cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
					cross->ov = v2;
					cross->next = crossings[j];
					crossings[j] = cross;
				}

				continue;
			}
#if 0
if ( newVert && newVert != v1 && newVert != v2 && newVert != v3 && newVert != v4 ) {
common->Printf( "lines %i (%i to %i) and %i (%i to %i) cross at new point %i\n", i, v1 - optVerts, v2 - optVerts, 
		   j, v3 - optVerts, v4 - optVerts, newVert - optVerts );
} else if ( newVert ) {
common->Printf( "lines %i (%i to %i) and %i (%i to %i) intersect at old point %i\n", i, v1 - optVerts, v2 - optVerts, 
		  j, v3 - optVerts, v4 - optVerts, newVert - optVerts );
}
#endif
			if ( newVert != v1 && newVert != v2 ) {
				cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
				cross->ov = newVert;
				cross->next = crossings[i];
				crossings[i] = cross;
			}

			if ( newVert != v3 && newVert != v4 ) {
				cross = (edgeCrossing_t *)Mem_ClearedAlloc( sizeof( *cross ) );
				cross->ov = newVert;
				cross->next = crossings[j];
				crossings[j] = cross;
			}

		}
	}


	// now split each edge by its crossing points
	// colinear edges will have duplicated edges added, but it won't hurt anything
	for ( i = 0 ; i < numOriginalEdges ; i++ ) {
		edgeCrossing_t	*cross, *nextCross;
		int				numCross;
		optVertex_t		**sorted;

		numCross = 0;
		for ( cross = crossings[i] ; cross ; cross = cross->next ) {
			numCross++;
		}
		numCross += 2;	// account for originals
		sorted = (optVertex_t **)Mem_Alloc( numCross * sizeof( *sorted ) );
		sorted[0] = originalEdges[i].v1;
		sorted[1] = originalEdges[i].v2;
		j = 2;
		for ( cross = crossings[i] ; cross ; cross = nextCross ) {
			nextCross = cross->next;
			sorted[j] = cross->ov;
			Mem_Free( cross );
			j++;
		}

		// add all possible fragment combinations that aren't divided
		// by another point
		for ( j = 0 ; j < numCross ; j++ ) {
			for ( k = j+1 ; k < numCross ; k++ ) {
				if ( sorted[j] == sorted[k] ) {
					continue;
				}
				for ( l = 0 ; l < numCross ; l++ ) {
					if ( sorted[l] == sorted[j] || sorted[l] == sorted[k] ) {
						continue;
					}
					if ( VertexBetween( sorted[l], sorted[j], sorted[k] ) ) {
						break;
					}
				}
				if ( l == numCross ) {
//common->Printf( "line %i fragment from point %i to %i\n", i, sorted[j] - optVerts, sorted[k] - optVerts );
					AddEdgeIfNotAlready( sorted[j], sorted[k] );
				}
			}
		}

		Mem_Free( sorted );
	}


	Mem_Free( crossings );
	Mem_Free( originalEdges );

	// check for duplicated edges
	for ( i = 0 ; i < numOptEdges ; i++ ) {
		for ( j = i+1 ; j < numOptEdges ; j++ ) {
			if ( ( optEdges[i].v1 == optEdges[j].v1 && optEdges[i].v2 == optEdges[j].v2 ) 
				|| ( optEdges[i].v1 == optEdges[j].v2 && optEdges[i].v2 == optEdges[j].v1 ) ) {
				PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "duplicated optEdge\n" );
			}
		}
	}

	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original edges\n", numOriginalEdges );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i edges after splits\n", numOptEdges );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i original vertexes\n", numOriginalVerts );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i vertexes after splits\n", numOptVerts );
}

//=================================================================


/*
===================
CullUnusedVerts

Unlink any verts with no edges, so they
won't be used in the retriangulation
===================
*/
static void CullUnusedVerts( optIsland_t *island ) {
	optVertex_t	**prev, *vert;
	int			c_keep, c_free;
	optEdge_t	*edge;

	c_keep = 0;
	c_free = 0;

	for ( prev = &island->verts ; *prev ; ) {
		vert = *prev;

		if ( !vert->edges ) {
			// free it
			*prev = vert->islandLink;
			c_free++;
		} else {
			edge = vert->edges;
			if ( ( edge->v1 == vert && !edge->v1link )
				|| ( edge->v2 == vert && !edge->v2link ) ) {
				// is is occasionally possible to get a vert
				// with only a single edge when colinear optimizations
				// crunch down a complex sliver
				UnlinkEdge( edge, island );
				// free it
				*prev = vert->islandLink;
				c_free++;
			} else {
				prev = &vert->islandLink;
				c_keep++;
			}
		}
	}

	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i verts kept\n", c_keep );
	PrintIfVerbosityAtLeast( VL_VERBOSE, "%6i verts freed\n", c_free );
}




#include "planargraph.h"
/*
==================
AddTriangulationEdges

Add all edges inside every outermost loop
(faster version of AddInteriorEdges)
==================
*/
static void AddTriangulationEdges( optIsland_t *island ) {
	//actual storage
	static PlanarGraph planarGraph;
	static idList<PlanarGraph::Triangle> pgAddedTris;
	static idList<PlanarGraph::AddedEdge> pgAddedEdges;
	static idList<optVertex_t*> pgActiveVerts;

	planarGraph.Reset();
	planarGraph.SetOptimizeGroup(island->group);

	//add vertices
	pgActiveVerts.SetNum(0, false);
	for (optVertex_t *v = island->verts; v; v = v->islandLink) {
		if (!v->edges) {
			//omit isolated vertices: they are not considered in T-junctions removal
			//as the result, they can easily lie on other edges
			continue;
		}
		pgActiveVerts.AddGrow(v);
		v->idx = planarGraph.AddVertex(v->pv.ToVec2());
	}
	//add edges
	for (optEdge_t *e = island->edges; e; e = e->islandLink)
		planarGraph.AddEdge(e->v1->idx, e->v2->idx);
	//finalize graph
	planarGraph.Finish();

	planarGraph.BuildFaces();

	pgAddedTris.SetNum(0, false);
	pgAddedEdges.SetNum(0, false);
	planarGraph.TriangulateFaces(pgAddedTris, pgAddedEdges);

	for (int i = 0; i < pgAddedEdges.Num(); i++) {
		const int *ids = pgAddedEdges[i].ids;
		TryAddNewEdge(pgActiveVerts[ids[0]], pgActiveVerts[ids[1]], island);
	}
}

/*
====================
OptimizeIsland

At this point, all needed vertexes are already in the
list, including any that were added at crossing points.

Interior and colinear vertexes will be removed, and
a new triangulation will be created.
====================
*/
static void OptimizeIsland( optIsland_t *island ) {
	// add space-filling fake edges so we have a complete
	// triangulation of a convex hull before optimization
	AddInteriorEdges( island );
	DrawEdges( island );

	// determine all the possible triangles, and decide if
	// the are filled or empty
	BuildOptTriangles( island );

	// remove interior vertexes that have filled triangles
	// between all their edges
	RemoveInteriorEdges( island );
	DrawEdges( island );

	ValidateEdgeCounts( island );

	// remove vertexes that only have two colinear edges
	CombineColinearEdges( island );
	CullUnusedVerts( island );
	DrawEdges( island );

	// add new internal edges between the remaining exterior edges
	// to give us a full triangulation again
	AddInteriorEdges( island );
	DrawEdges( island );

	// determine all the possible triangles, and decide if
	// the are filled or empty
	BuildOptTriangles( island );

	// make mapTri_t out of the filled optTri_t
	RegenerateTriangles( island );
}

/*
================
AddVertexToIsland_r
================
*/
#if 0
static void AddVertexToIsland_r( optVertex_t *vert, optIsland_t *island ) {
	optEdge_t	*e;

	// we can't just check islandLink, because the
	// last vert will have a NULL
	if ( vert->addedToIsland ) {
		return;
	}
	vert->addedToIsland = true;
	vert->islandLink = island->verts;
	island->verts = vert;

	for ( e = vert->edges ; e ; ) {
		if ( !e->addedToIsland ) {
			e->addedToIsland = true;

			e->islandLink = island->edges;
			island->edges = e;
		}

		if ( e->v1 == vert ) {
			AddVertexToIsland_r( e->v2, island );
			e = e->v1link;
			continue;
		}
		if ( e->v2 == vert ) {
			AddVertexToIsland_r( e->v1, island );
			e = e->v2link;
			continue;
		}
		common->Error( "AddVertexToIsland_r: mislinked vert" );
	}

}
#endif

/*
====================
SeparateIslands

While the algorithm should theoretically handle any collection
of triangles, there are speed and stability benefits to making
it work on as small a list as possible, so separate disconnected
collections of edges and process separately.

FIXME: we need to separate the source triangles before
doing this, because PointInSourceTris() can give a bad answer if
the source list has triangles not used in the optimization
====================
*/
#if 0
static void SeparateIslands( optimizeGroup_t *opt ) {
	int		i;
	optIsland_t	island;
	int		numIslands;

	DrawAllEdges();

	numIslands = 0;
	for ( i = 0 ; i < numOptVerts ; i++ ) {
		if ( optVerts[i].addedToIsland ) {
			continue;
		}
		numIslands++;
		memset( &island, 0, sizeof( island ) );
		island.group = opt;
		AddVertexToIsland_r( &optVerts[i], &island );
		OptimizeIsland( &island );
	}
	if ( dmapGlobals.verbose ) {
		common->Printf( "%6i islands\n", numIslands );
	}
}
#endif

static void DontSeparateIslands( optimizeGroup_t *opt ) {
	int		i;
	optIsland_t	island;

	DrawAllEdges();

	memset( &island, 0, sizeof( island ) );
	island.group = opt;

	// link everything together
	for ( i = 0 ; i < numOptVerts ; i++ ) {
		optVerts[i].islandLink = island.verts;
		island.verts = &optVerts[i];
	}

	for ( i = 0 ; i < numOptEdges ; i++ ) {
		optEdges[i].islandLink = island.edges;
		island.edges = &optEdges[i];
	}

	OptimizeIsland( &island );
}


/*
====================
PointInSourceTris

This is a sloppy bounding box check
====================
*/
#if 0
static bool PointInSourceTris( float x, float y, float z, optimizeGroup_t *opt ) {
	mapTri_t	*tri;
	idBounds	b;
	idVec3		p;

	if ( !opt->material->IsDrawn() ) {
		return false;
	}

	p[0] = x;
	p[1] = y;
	p[2] = z;
	for ( tri = opt->triList ; tri ; tri = tri->next ) {
		b.Clear();
		b.AddPoint( tri->v[0].xyz );
		b.AddPoint( tri->v[1].xyz );
		b.AddPoint( tri->v[2].xyz );

		if ( b.ContainsPoint( p ) ) {
			return true;
		}
	}
	return false;
}
#endif

/*
====================
OptimizeOptList
====================
*/
static	void OptimizeOptList( optimizeGroup_t *opt ) {
	optimizeGroup_t	*oldNext;

	// fix the t junctions among this single list
	// so we can match edges
	// can we avoid doing this if colinear vertexes break edges?
	oldNext = opt->nextGroup;
	opt->nextGroup = NULL;
	FixAreaGroupsTjunctions( opt );
	opt->nextGroup = oldNext;

	// create the 2D vectors
	dmapGlobals.mapPlanes[opt->planeNum].Normal().NormalVectors( opt->axis[0], opt->axis[1] );

	AddOriginalEdges( opt );
	SplitOriginalEdgesAtCrossings( opt );

#if 0
	// seperate any discontinuous areas for individual optimization
	// to reduce the scope of the problem
	SeparateIslands( opt );
#else
	DontSeparateIslands( opt );
#endif

	// now free the hash verts
	FreeTJunctionHash();

	// free the original list and use the new one
	FreeTriList( opt->triList );
	opt->triList = opt->regeneratedTris;
	opt->regeneratedTris = NULL;
}

idStr ReportWorldPositionInOptimizeGroup(const idVec2 &pos, optimizeGroup_t *group) {
	if (group == nullptr)
		return "???";
	const idPlane &plane = dmapGlobals.mapPlanes[group->planeNum];
	idVec3 origin = plane.Normal() * plane.Dist();
	idVec3 worldPos = origin + group->axis[0] * pos.x + group->axis[1] * pos.y;
	return worldPos.ToString();
}


/*
==================
SetGroupTriPlaneNums

Copies the group planeNum to every triangle in each group
==================
*/
void SetGroupTriPlaneNums( optimizeGroup_t *groups ) {
	mapTri_t	*tri;
	optimizeGroup_t	*group;

	for ( group = groups ; group ; group = group->nextGroup ) {
		for ( tri = group->triList ; tri ; tri = tri->next ) {
			tri->planeNum = group->planeNum;
		}
	}
}


/*
===================
OptimizeGroupList

This will also fix tjunctions

===================
*/
void	OptimizeGroupList( optimizeGroup_t *groupList ) {
	int			c_in, c_edge, c_tjunc2;
	optimizeGroup_t	*group;

	if ( !groupList ) {
		return;
	}

	c_in = CountGroupListTris( groupList );

	// optimize and remove colinear edges, which will
	// re-introduce some t junctions
	int idx = 0;
	for ( group = groupList ; group ; group = group->nextGroup ) {
		OptimizeOptList( group );
		idx++;
	}
	c_edge = CountGroupListTris( groupList );

	// fix t junctions again
	FixAreaGroupsTjunctions( groupList );
	FreeTJunctionHash();
	c_tjunc2 = CountGroupListTris( groupList );

	SetGroupTriPlaneNums( groupList );

	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- OptimizeAreaGroups Results -----\n" );
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "%6i tris in\n", c_in );
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "%6i tris after edge removal optimization\n", c_edge );
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "%6i tris after final t junction fixing\n", c_tjunc2 );
}


/*
==================
OptimizeEntity
==================
*/
void	OptimizeEntity( uEntity_t *e ) {
	int		i;

	TRACE_CPU_SCOPE_TEXT("OptimizeEntity", e->nameEntity)
	PrintIfVerbosityAtLeast( VL_ORIGDEFAULT, "----- OptimizeEntity -----\n" );
	for ( i = 0 ; i < e->numAreas ; i++ ) {
		TRACE_CPU_SCOPE_FORMAT("OptimizeArea", "area%d", i);
		OptimizeGroupList( e->areas[i].groups );
	}
}