// TnzCore includes
#include "trop.h"
#include "trop_borders.h"
#include "tpixelutils.h"

// tcg includes
#include "tcg_wrap.h"

#include "tcg/tcg_point.h"
#include "tcg/tcg_cyclic.h"
#include "tcg/tcg_containers_reader.h"

#define INCLUDE_HPP
#include "tcg/tcg_triangulate.h"
#undef INCLUDE_HPP

// TnzExt includes
#define INCLUDE_HPP
#include "../common/trop/raster_edge_evaluator.h"
#undef INCLUDE_HPP

#include "ext/meshbuilder.h"

//**************************************************************************************
//    Local namespace
//**************************************************************************************

namespace
{

struct PolygonVertex {
	double m_pos[3];
	int m_idx;

	PolygonVertex(const TPoint &p)
		: m_idx(-1) { m_pos[0] = p.x, m_pos[1] = p.y, m_pos[2] = 0.0; }
};

} // namespace

//**************************************************************************************
//    tcg  stuff
//**************************************************************************************

namespace tcg
{

template <>
struct traits<TTextureMeshP> {
	typedef TTextureMeshP *pointer_type;
	typedef TTextureMeshP *&reference_type;
	typedef TTextureMesh pointed_type;
};

//--------------------------------------------------------------------------

template <>
struct point_traits<PolygonVertex> {
	typedef PolygonVertex point_type;
	typedef double value_type;
	typedef double float_type;

	inline static value_type x(const point_type &p) { return p.m_pos[0]; }
	inline static value_type y(const point_type &p) { return p.m_pos[1]; }
};

} // namespace tcg

//**************************************************************************************
//    MeshBuilder Locals
//**************************************************************************************

namespace
{

//======================================================================================
//    Thresholding  stuff
//======================================================================================

template <typename Pix>
void thresholdRaster(const TRasterPT<Pix> &ras, TRasterGR8P &out, const Pix &transp)
{
	int lx = ras->getLx(), y, ly = ras->getLy();
	for (y = 0; y < ly; ++y) {
		Pix *pix, *line = ras->pixels(y), *lineEnd = line + lx;
		TPixelGR8 *gr, *grLine = out->pixels(y);

		for (pix = line, gr = grLine; pix != lineEnd; ++pix, ++gr)
			gr->value = (pix->m && *pix != transp) ? 0 : 255;
	}
}

//--------------------------------------------------------------------------

template <typename Pix>
void thresholdRasterGr(const TRasterPT<Pix> &ras, TRasterGR8P &out, const Pix &transp)
{
	int lx = ras->getLx(), y, ly = ras->getLy();
	for (y = 0; y < ly; ++y) {
		Pix *pix, *line = ras->pixels(y), *lineEnd = line + lx;
		TPixelGR8 *gr, *grLine = out->pixels(y);

		for (pix = line, gr = grLine; pix != lineEnd; ++pix, ++gr)
			gr->value = (*pix != transp) ? 0 : 255;
	}
}

//--------------------------------------------------------------------------

void thresholdRasterCM32(const TRasterCM32P &ras, TRasterGR8P &out)
{
	int lx = ras->getLx(), y, ly = ras->getLy();
	for (y = 0; y < ly; ++y) {
		TPixelCM32 *pix, *line = ras->pixels(y), *lineEnd = line + lx;
		TPixelGR8 *gr, *grLine = out->pixels(y);

		for (pix = line, gr = grLine; pix != lineEnd; ++pix, ++gr)
			gr->value = (pix->isPurePaint() && !pix->getPaint()) ? 255 : 0;
	}
}

//--------------------------------------------------------------------------

TRasterGR8P thresholdRaster(const TRasterP &ras, const MeshBuilderOptions &opts)
{
	TRasterGR8P binaryRas(ras->getLx(), ras->getLy());

	TRasterCM32P rasCM(ras);
	if (rasCM)
		thresholdRasterCM32(rasCM, binaryRas);
	else
		switch (ras->getPixelSize()) {
		case 1: {
			TRasterGR8P rasGR8(ras);
			thresholdRasterGr(rasGR8, binaryRas, TPixelGR8::from(toPixel32(opts.m_transparentColor)));
		}

			CASE 2:
			{
				TRasterGR16P rasGR16(ras);
				thresholdRasterGr(rasGR16, binaryRas, TPixelGR16::from(opts.m_transparentColor));
			}

			CASE 4:
			{
				TRaster32P ras32(ras);
				thresholdRaster(ras32, binaryRas, toPixel32(opts.m_transparentColor));
			}

			CASE 8:
			{
				TRaster64P ras64(ras);
				thresholdRaster(ras64, binaryRas, opts.m_transparentColor);
			}

		DEFAULT:
			assert(false);
		}

	// Build an enlarged ras to preserve borders. 5 pixels should be fine.
	TRasterGR8P result(ras->getLx(), ras->getLy());
	TRop::blur(result, binaryRas, opts.m_margin, 0, 0);

	thresholdRasterGr(result, result, TPixelGR8::White);

	return result;
}

//======================================================================================
//    Borders Extraction  stuff
//======================================================================================

using namespace TRop::borders;

//--------------------------------------------------------------------------

template <typename T>
inline void delete_(T t) { delete t; }

template <typename T>
struct Vector : public std::vector<T> {

	Vector() : std::vector<T>() {}
	~Vector() { std::for_each(this->begin(), this->end(), delete_<T>); }
};

//--------------------------------------------------------------------------

typedef std::vector<TPoint> RasterBorder;
typedef std::vector<PolygonVertex> Polygon;
typedef Vector<Polygon *> Family;
typedef Vector<Family *> Tribe;

//--------------------------------------------------------------------------

struct PolygonReader {
	Polygon *m_polygon;

public:
	typedef tcg::cyclic_iterator<RasterBorder::iterator> cyclic_iter;

public:
	PolygonReader() : m_polygon(0) {}

	void openContainer(const cyclic_iter &ct)
	{
		m_polygon = new Polygon;
		m_polygon->push_back(PolygonVertex(*ct));
	}

	void addElement(const cyclic_iter &ct) { m_polygon->push_back(PolygonVertex(*ct)); }

	void closeContainer() {}
};

//--------------------------------------------------------------------------

class BordersReader : public ImageMeshesReaderT<TPixelGR8>
{
public:
	Vector<RasterBorder *> m_borders;
	RasterBorder *m_current;

public:
	BordersReader()
		: ImageMeshesReaderT<TPixelGR8>(PixelSelector<TPixelGR8>(false)), m_current(0) {}

	void openFace(ImageMesh *mesh, int faceIdx, const TPixelGR8 &color)
	{
		ImageMeshesReader::openFace(mesh, faceIdx); // defines imageIndex

		if (mesh) {
			ImageMesh::face_type &fc = mesh->face(faceIdx);
			fc.imageIndex() = (color.value) ? 0 : 1; // redefines iI
		}
	}

	//--------------------------------------------------------------------------

	void openEdge(const raster_edge_iterator &it)
	{
		m_current = new RasterBorder;
		m_current->push_back(it.pos());
	}

	//--------------------------------------------------------------------------

	void addVertex(const raster_edge_iterator &it)
	{
		m_current->push_back(it.pos());
	}

	//--------------------------------------------------------------------------

	void closeEdge(ImageMesh *mesh, int edgeIdx)
	{
		ImageMesh::edge_type &ed = mesh->edge(edgeIdx);
		ed.imageIndex() = m_borders.size();

		m_borders.push_back(m_current);
		m_current = 0;

		ImageMeshesReader::closeEdge(mesh, edgeIdx);
	}
};

//--------------------------------------------------------------------------

Polygon *reduceBorder(RasterBorder *border)
{
	typedef RasterBorder::iterator iter;
	typedef tcg::cyclic_iterator<iter> cyclic_iter;

	iter b(border->begin()), e(border->end());

	cyclic_iter cBegin(b, b, e - 1, 0),
		cEnd(b + 1, b, e - 1, 1);

	RasterEdgeEvaluator<cyclic_iter> eval(
		cBegin - 1, cEnd + 1, 2.0, (std::numeric_limits<double>::max)());

	PolygonReader reader;
	tcg::sequence_ops::minimalPath(cBegin, cEnd, eval, reader);

	return reader.m_polygon;
}

//--------------------------------------------------------------------------

void reduceBorders(Tribe *tribe, const ImageMeshesReader &reader, const Vector<RasterBorder *> &borders,
				   int meshIdx, const ImageMesh::face_type &fc)
{
	// Traverse the image structure. Each time a black face is encountered, add its associated family to the
	// resulting tribe.

	const tcg::list<ImageMeshP> &meshes = reader.meshes();

	if (meshIdx >= 0 && fc.imageIndex()) {
		// Build a family. Start by extracting the face's contour
		Family *family = new Family;
		tribe->push_back(family);

		const ImageMeshP &mesh = meshes[meshIdx];

		Polygon *outerBorder = reduceBorder(borders[mesh->edge(0).imageIndex()]);
		family->push_back(outerBorder);

		// Then, extract the contours of every sub-mesh
		int m, mCount = fc.meshesCount();
		for (m = 0; m < mCount; ++m) {
			int mIdx = fc.mesh(m);
			const ImageMeshP &childMesh = meshes[mIdx];

			Polygon *innerBorder = reduceBorder(borders[childMesh->edge(0).imageIndex()]);
			family->push_back(innerBorder);

			reduceBorders(tribe, reader, borders, mIdx, childMesh->face(0));
		}
	}

	// Recursive on the face's sub-mesh faces
	int m, mCount = fc.meshesCount();
	for (m = 0; m < mCount; ++m) {
		int mIdx = fc.mesh(m);
		reduceBorders(tribe, reader, borders, mIdx, meshes[mIdx]->face(0));
	}
}

//--------------------------------------------------------------------------

Tribe *extractBorders(const TRasterGR8P &ras)
{
	Tribe *result = new Tribe;

	BordersReader reader;
	TRop::borders::readMeshes(ras, reader);

	reduceBorders(result, reader, reader.m_borders, -1, reader.outerFace());

	return result;
}

//======================================================================================
//    Maximum Edge Length  stuff
//======================================================================================

double buildMinimumEdgeLength(Tribe *tribe, int targetMaxVerticesCount)
{
	// Calculate the tribe's total area
	double area = 0.0;

	Tribe::iterator ft, fEnd(tribe->end());
	for (ft = tribe->begin(); ft != fEnd; ++ft) {
		Family *fam = *ft;

		// Add area corresponding to the external border
		area += fabs(tcg::polyline_ops::area(fam->front()->begin(), fam->front()->end()));

		// Then, subtract all the internal ones
		Family::iterator pt, pEnd(fam->end());
		for (pt = ++fam->begin(); pt != pEnd; ++pt)
			area -= fabs(tcg::polyline_ops::area((*pt)->begin(), (*pt)->end()));
	}

	// Given the area, find the approximate edge length corresponding to the required
	// vertices count

	// The idea is: given a polygon, its uniform triangular mesh - made of, say, lots of equilateral
	// triangles, has vertices count proportional to ( polygon area / sq(mean mesh edge length) ).

	// Under this assumption, take an equilater triangle as our polygon, and assume that its built
	// mesh is the regular mesh obtained by subdividing it multiple times, Sierpinsky-like.

	// Since it can easily be sheared to a corresponding half-square, it can be SEEN that in
	// this case its vertices count is EXACTLY  (l / e_length)^2 / 2,  l being the large
	// triangle's edge. By extension, if A is the area of the triangle, then we have:

	//    A = l^2 * sqrt(3/2) / 2;      => l = sqrt(2 * K * A),     K = 1.0 / sqrt(3/2);
	//    V = K * A / e_length^2;       => e_length = sqrt(KA / V);

	// And we just extend this from 'triangle' to 'polygon'.

	return sqrt(area / (sqrt(1.5) * targetMaxVerticesCount));
}

//======================================================================================
//    Mesh Refinement  stuff
//======================================================================================

void refineMeshes(const TMeshImageP &mi, const MeshBuilderOptions &options)
{
	std::vector<TTextureMeshP> &meshes = mi->meshes();

	// Refine every mesh to achieve a target mesh density dependent on the image size
	/*TRectD bbox(mi->getBBox());
  double targetLength = sqrt(bbox.getLx() * bbox.getLy()) * relativeMeshDensity;*/

	double targetLength = options.m_targetEdgeLength;

	int m, mCount = meshes.size();
	for (m = 0; m < mCount; ++m) {
		const TTextureMeshP &mesh = meshes[m];

		tcg::TriMeshStuff::DefaultEvaluator<TTextureMesh> eval(0.0, (std::numeric_limits<double>::max)());

		// First, perform edge swaps alone. This is useful since results from gluTriangulate
		// tend to be unbalanced to vertical - this is a good correction.
		tcg::refineMesh(*mesh, eval);

		// Now, launch a full-scale, finishing simplification
		eval.m_collapseValue = targetLength * 0.6;
		eval.m_splitValue = targetLength * 1.4;
		tcg::refineMesh(*mesh, eval, 20000); //Max 10000 iterations - to avoid loops

		// Since we stopped at a max number of iterations, separate collapses from splits
		// and simplify until the procedure stops.
		eval.m_collapseValue = 0.0;
		eval.m_splitValue = 1.4 * targetLength;
		tcg::refineMesh(*mesh, eval);

		eval.m_splitValue = (std::numeric_limits<double>::max)();
		eval.m_collapseValue = targetLength * 0.6;
		tcg::refineMesh(*mesh, eval);

		// Perform 1000 final iterations with uniform split and collapses
		eval.m_splitValue = targetLength * 1.4;
		tcg::refineMesh(*mesh, eval, 1000);

		// Finally, squeeze the mesh to ensure that VEF containers are tight
		mesh->squeeze();
	}
}

} // namespace

//**************************************************************************************
//    Mesh Builder  function
//**************************************************************************************

TMeshImageP buildMesh(const TRasterP &ras, const MeshBuilderOptions &options)
{
	// Convert the input image to a binary raster
	TRasterGR8P binaryRas = thresholdRaster(ras, options);

	// Extract the image borders
	Tribe *tribe = extractBorders(binaryRas);

	// Calculate maximum edge length
	double minEdgeLength = buildMinimumEdgeLength(tribe, options.m_targetMaxVerticesCount);

	MeshBuilderOptions opts(options);
	opts.m_targetEdgeLength = tmax(opts.m_targetEdgeLength, minEdgeLength);

	// Perform tessellation
	TMeshImageP meshImage(new TMeshImage);
	std::vector<TTextureMeshP> &meshes = meshImage->meshes();

	tcg::sequential_reader<std::vector<TTextureMeshP>> reader(&meshes);
	tcg::gluTriangulate(tribe->begin(), tribe->end(), reader);

	delete tribe;

	// Perform meshes refinement
	refineMeshes(meshImage, opts);

	return meshImage;
}