/* -----------------------------------------------------------------------------
	GSFramework
	Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
----------------------------------------------------------------------------- */


		#include "core/geometry_reducer.h"
		#include "core/geometry.h"

		using namespace GS::Core;


//------------------------------------------------------------------------------
void				GeometryReducer::RemoveVertex (uint v)
{
	vlist[v].active = false;
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
float				GeometryReducer::ComputeEdgeCost(Geometry *sg, nLLEDGE *edg)
{
	#define	nMAXTRIPEREDGE	512	// FIXME

	nLLTRI *sidetri[nMAXTRIPEREDGE];
	nTENTRY	*te;

	uint nsidetri = 0, n;

	te = tlist.lut[edg->a];
	while (te)
	{
		if	(te->tri->UseVertex(edg->b))
			sidetri[nsidetri++] = te->tri;
		te = te->n;
	}

	float curvature = 0.f;

	te = tlist.lut[edg->a];

	while (te)
	{
		float mincurv = 1.f;

		for	(n = 0; n < nsidetri; ++n)
		{
			float dot = te->tri->normal.Dot(sidetri[n]->normal);
			dot = (1.f - dot) / 2.f;
			if	(dot < mincurv)
				mincurv = dot;
		}
		if	(mincurv > curvature)
			curvature = mincurv;
		te = te->n;
	}

	return curvature * Vector4::Dist(sg->vtx[edg->a], sg->vtx[edg->b]);
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
void				GeometryReducer::ComputeVertexCost(Geometry *sg, uint v)
{
	nEENTRY	*te = elist.lut[v];
	vlist[v].cost = -1.f;

	// cheapest collapse target for this vertex...
	while (te)
	{
		float ecost = ComputeEdgeCost (sg, te->edge);
		if	( (vlist[v].cost == -1.f) || (ecost < vlist[v].cost) )
		{
			vlist[v].tgtcollapse = te->edge->b;
			vlist[v].cost = ecost;
		}
		te = te->n;
	}
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
void				nLLTRI::ReplaceVertex(uint f, uint t)
{
			if	( a == f ) a = t;
	else	if	( b == f ) b = t;
	else	if	( c == f ) c = t;
}
char				nLLTRI::UseVertex(uint i)
{
	if	((a == i) || (b == i) || (c == i))
		return	true;
	return	false;
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
char				GeometryReducer::IsBorder(uint v)
{
	/*
		If any of the edge going trough the vertex owns only one polygon then
		the vertex is on a border...
	`*/
	for (nEENTRY *pedg = elist.lut[v]; pedg; pedg = pedg->n)
	{
		uint ecnt = 0;
		for (nTENTRY *ptri = tlist.lut[v]; ptri; ptri = ptri->n)
			if	(ptri->tri->UseVertex (pedg->edge->b))
				++ecnt;

		if	(ecnt < 2)
			return true;
	}
	return false;
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
Geometry			*GeometryReducer::Reduce(Geometry *sg, float k)
{
	if	(!sg->pol.GetCount())	return	NULL;
	if	(k <= 0.f)	return	NULL;
	if	(k >= 1.f)	return	NULL;

#ifdef	DEBUG_COMPILATION
	__LOG__ << "Geometry reducer invoked: " << k << "...\n";
#endif

	// Allocate
	Geometry *ng = new Geometry;
	if	(!ng)
		return NULL;

	// Triangulate geometry.
	uint	n, m;
	nLLTRI	*ctri;

	elist.SetVertexCount (sg->vtx.GetCount());
	tlist.SetGeo (sg);

	for	(n = 0; n < sg->pol.GetCount(); ++n)
	{
		const Polygon &p = sg->pol[n];

		for	(m = 1; m < (uint)(p.vtx_count - 1); ++m)
		{
			ctri = tlist.Add(p.binding[0], p.binding[m], p.binding[m+1]);
			ctri->m = p.material;
			tlist.ComputeNormal(ctri);

				// insert edges
			elist.Add(p.binding[0], p.binding[m]);
			elist.Add(p.binding[m], p.binding[m+1]);

			elist.Add(p.binding[m], p.binding[0]);
			elist.Add(p.binding[m+1], p.binding[m]);
		}

		elist.Add(p.binding[0], p.binding[m]);
		elist.Add(p.binding[m], p.binding[0]);
	}

		// create vertice list
	vlist = new nLVERTEX[sg->vtx.GetCount()];
	for	( n = 0; n < sg->vtx.GetCount(); n++ )
	{
		vlist[n].active = true;
		vlist[n].locked = IsBorder (n);
		vlist[n].tgtcollapse = n;
		ComputeVertexCost (sg, n);
	}

		// collapse until we reach target...
	uint		_tgt = (uint)((float)tlist.ntri * k);
#ifdef	DEBUG_COMPILATION
	__LOG__ << "Collapsing from " << tlist.ntri << " to " << _tgt << "...\n";
	float		pcttri = (float)(tlist.ntri - _tgt) * 0.01f;
#endif

	while	( tlist.ntri > _tgt )
	{
			// get the cheapest vertex to collapse
		int	vtx = -1;
		float	cst = 10000000.f;
		for	( n = 0; n < sg->vtx.GetCount(); n++ )
		{
			if	( vlist[n].active && (!vlist[n].locked) && (vlist[n].cost < cst) )
			{
				vtx = n;
				cst = vlist[n].cost;
			}
		}

/*			// move vertex
		if	( !vlist[vlist[vtx].tgtcollapse].locked )
		{
			VEC_INC (sg->vtx[vlist[vtx].tgtcollapse], sg->vtx[vtx]);
			VEC_SCALEK (sg->vtx[vlist[vtx].tgtcollapse], 0.5f);
		}
*/
			// remap triangles
		tlist.ReplaceVertex (vtx, vlist[vtx].tgtcollapse);
		elist.RemapEdges (vtx, vlist[vtx].tgtcollapse);

			// recompute cost for all modified vertice
		ComputeVertexCost (sg, vlist[vtx].tgtcollapse);

		nEENTRY	*pedg = elist.lut[vlist[vtx].tgtcollapse];
		while	( pedg )
		{
			ComputeVertexCost (sg, pedg->edge->b);
			pedg = pedg->n;
		}

#ifdef	DEBUG_COMPILATION
		if	(!(tlist.ntri & 4095))
			__LOG__ << (float)(100.f - ((float)(tlist.ntri - _tgt) / pcttri)) << "%%...\n";
#endif
		// Invalidate vertex.
		vlist[vtx].active = false;
	}

	_safe_delete_array(vlist);

#ifdef	DEBUG_COMPILATION
	__LOG__ << "Geometry reduction done.\n";
#endif

	// Convert to mesh datas...
	char *usevtx = new char[sg->vtx.GetCount()];
	GS::Memory::Set(usevtx, 0, sg->vtx.GetCount());

	ctri = tlist.root;
	while	( ctri )
	{
		usevtx[ctri->a] = true;
		usevtx[ctri->b] = true;
		usevtx[ctri->c] = true;
		ctri = ctri->n;
	}	

	m = 0;
	for	( n = 0; n < sg->vtx.GetCount(); n++ )
		if	( usevtx[n] )
			m++;

	// Fill new geometry.
	ng->pol.Allocate(tlist.ntri);
	ng->binding.Allocate(ng->pol.GetCount() * 3);
	ng->vtx.Allocate(m);
	uint	*rmpvtx = new uint[sg->vtx.GetCount()];

	// Copy vertice.
	m = 0;
	for	( n = 0; n < sg->vtx.GetCount(); n++ )
		if	( usevtx[n] )
		{
			rmpvtx[n] = m;
			ng->vtx[m++] = sg->vtx[n];
		}
	_safe_delete_array(usevtx);

	// Setup polygons.
	m = 0;
	ctri = tlist.root;
	for	( n = 0; n < ng->pol.GetCount(); n++ )
	{
		ng->pol[n].vtx_count = 3;
		ng->pol[n].binding = &ng->binding[m];
		ng->binding[m++] = rmpvtx[ctri->a];
		ng->binding[m++] = rmpvtx[ctri->b];
		ng->binding[m++] = rmpvtx[ctri->c];
		ng->pol[n].material = ctri->m;
		ctri = ctri->n;
	}
	_safe_delete_array(rmpvtx);

	// Copy material.
	if	(!ng->material_table.Allocate(sg->material_table.GetCount()))
		return NULL;
	for	(n = 0; n < ng->material_table.GetCount(); n++)
		ng->material_table[n] = sg->material_table[n];

	// Setup geometry.
	ng->ComputeVertexNormal();

	return	ng;
}
//------------------------------------------------------------------------------

//---------------------------------------------------
void				nLTRILIST::ComputeNormal (nLLTRI *ctri)
//---------------------------------------------------
{
	Vector4	va = sg->vtx[ctri->c] - sg->vtx[ctri->a];
	Vector4	vb = sg->vtx[ctri->b] - sg->vtx[ctri->a];
	ctri->normal = vb.Cross(va).Normalized();
}

//--------------------------------------------
void				nLTRILIST::SetGeo (Geometry *g)
//--------------------------------------------
{
	sg = g;
	lut = new pnTENTRY[g->vtx.GetCount()];
	for	( uint c = 0; c < g->vtx.GetCount(); c++ )
		lut[c] = NULL;
}

//-----------------------------------------------------------
nLLTRI				*nLTRILIST::Add (uint a, uint b, uint c)
//-----------------------------------------------------------
{
	nLLTRI	*tri = new nLLTRI;
	tri->a = a;
	tri->b = b;
	tri->c = c;

	tri->n = root;
	tri->p = NULL;
	if	( root )
		root->p = tri;
	root = tri;

	// Register in vertex to poly.
	AddTriToVertex(tri, a);
	AddTriToVertex(tri, b);
	AddTriToVertex(tri, c);
	ntri++;

	return tri;
}

//--------------------------------------------
void				nLTRILIST::Remove(nLLTRI *t)
//--------------------------------------------
{
	RemoveTriFromVertex(t, t->a);
	RemoveTriFromVertex(t, t->b);
	RemoveTriFromVertex(t, t->c);

	if	(t->p)
			t->p->n = t->n;
	else	root = t->n;
	if	(t->n)
		t->n->p = t->p;
	delete t;
	ntri--;
}

//--------------------------------------------------------------------
void				nLTRILIST::RemoveTriFromVertex(nLLTRI *t, uint v)
//--------------------------------------------------------------------
{
	nTENTRY	*n = lut[v], *p = NULL;
	while (n)
	{
		if (n->tri == t)
			break;
		p = n;
		n = n->n;
	}
	if (!n)
		return;
	if (!p)
			lut[v] = n->n;
	else	p->n = n->n;
	_safe_delete(n);
}

//---------------------------------------------------------------
void				nLTRILIST::AddTriToVertex (nLLTRI *t, uint v)
//---------------------------------------------------------------
{
	nTENTRY	*n = lut[v];
	while	( n && (n->tri != t ))
		n = n->n;
	if	( n )	return;

	n = new nTENTRY;
	n->tri = t;
	n->n = lut[v];
	lut[v] = n;
}

//----------------------------------------------------------
void				nLTRILIST::ReplaceVertex (uint a, uint b)
//----------------------------------------------------------
{
	nTENTRY	*s = lut[a], *n;
	while	( s )
	{
		n = s->n;

		if	( s->tri->UseVertex (b) )
			Remove (s->tri);
		else
		{
			s->tri->ReplaceVertex (a, b);
			AddTriToVertex (s->tri, b);
			ComputeNormal (s->tri);
			RemoveTriFromVertex (s->tri, a);
		}

		s = n;
	}
}

//---------------------------
nLTRILIST::nLTRILIST ()
//---------------------------
{
	ntri = 0;
	root = NULL;
}

//----------------------------
nLTRILIST::~nLTRILIST ()
//----------------------------
{
	uint	i;
	for	( i = 0; i < sg->vtx.GetCount(); i++ )
	{
		nTENTRY	*s = lut[i], *n;
		while	( s )
		{
			n = s->n;
			delete	s;
			s = n;
		}
	}
	delete	[]	lut;
	lut = NULL;

	nLLTRI	*s = root, *n;
	while	( s )
	{
		n = s->n;
		delete	s;
		s = n;
	}
	root = NULL;
	ntri = 0;
}

//--------------------------------------------
void				nEDGELIST::Add (uint a, uint b)
//--------------------------------------------
{
	nEENTRY	*pedg;
	if	( a == b )
		return;

	pedg = lut[a];
	while	( pedg )
	{
		if	( pedg->edge->b == b )
			return;
		pedg = pedg->n;
	}

	nLLEDGE	*edg = new nLLEDGE;
	edg->a = a;
	edg->b = b;	

	edg->n = root;
	edg->p = NULL;
	if	( root )
		root->p = edg;
	root = edg;

		// update lut
	pedg = new nEENTRY;
	pedg->edge = edg;
	pedg->n = lut[a];
	lut[a] = pedg;
nedg++;
}

//--------------------------------------------
void				nEDGELIST::Remove (nLLEDGE *edg)
//--------------------------------------------
{
	if	( !edg )
		return;
	if	( edg->n )
		edg->n->p = edg->p;
	if	( edg->p )
			edg->p->n = edg->n;
	else	root = edg->n;

		// update lut
	nEENTRY	*pedg = lut[edg->a], *ledg = NULL;
	while	( pedg )
	{
		if	( pedg->edge == edg )
			break;
		ledg = pedg;
		pedg = pedg->n;
	}
	if	( pedg )
	{
		if	( ledg )
				ledg->n = pedg->n;
		else	lut[edg->a] = pedg->n;
		delete	pedg;
	}
	delete	edg;
}

//-----------------------------------------------------
nLLEDGE				*nEDGELIST::GetEdge (uint a, uint b)
//-----------------------------------------------------
{
	nEENTRY	*pedg = lut[a];
	while	( pedg && (pedg->edge->b != b) )
		pedg = pedg->n;
	if	( !pedg )
		return	NULL;
	return	pedg->edge;
}

//---------------------------------------------------
void				nEDGELIST::RemapEdges (uint a, uint b)
//---------------------------------------------------
{
	nEENTRY	*pedg = lut[a], *nedg;

		// remap all edges and wipe invalid ones
	while	( pedg )
	{
		uint	ob = pedg->edge->b;
		nedg = pedg->n;

		Remove (GetEdge (pedg->edge->b, pedg->edge->a));
		Remove (pedg->edge);

		Add (b, ob);
		Add (ob, b);

		pedg = nedg;
	}
}

//---------------------------------------------
void				nEDGELIST::SetVertexCount (uint v)
//---------------------------------------------
{
	lut = new pnEENTRY[v];
	for	( uint n = 0; n < v; n++ )
		lut[n] = NULL;
	vtx_count = v;
}

//---------------------------
nEDGELIST::nEDGELIST ()
//---------------------------
{
	lut = NULL;
	root = NULL;
	nedg = 0;
}

//----------------------------
nEDGELIST::~nEDGELIST ()
//----------------------------
{
	uint	n;
	for	(n = 0; n < vtx_count; n++)
	{
		nEENTRY	*pedg = lut[n], *nedg;
		while	(pedg)
		{
			nedg = pedg->n;
			delete	pedg;
			pedg = nedg;
		}
	}
	_safe_delete_array(lut);

	nLLEDGE	*pedg = root, *nedg;
	while	(pedg)
	{
		nedg = pedg->n;
		delete	pedg;
		pedg = nedg;
	}
	root = NULL;
}