// 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> {</ttexturemeshp>

	typedef TTextureMeshP *pointer_type;

	typedef TTextureMeshP *&reference_type;

	typedef TTextureMesh pointed_type;

};

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

template <>

struct point_traits<polygonvertex> {</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=""></typename>

void thresholdRaster(const TRasterPT<pix> &ras, TRasterGR8P &out, const Pix &transp)</pix>

{

	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=""></typename>

void thresholdRasterGr(const TRasterPT<pix> &ras, TRasterGR8P &out, const Pix &transp)</pix>

{

	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=""></typename>

inline void delete_(T t) { delete t; }

template <typename t=""></typename>

struct Vector : public std::vector<t> {</t>

	Vector() : std::vector<t>() {}</t>

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

};

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

typedef std::vector<tpoint> RasterBorder;</tpoint>

typedef std::vector<polygonvertex> Polygon;</polygonvertex>

typedef Vector<polygon *=""> Family;</polygon>

typedef Vector<family *=""> Tribe;</family>

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

struct PolygonReader {

	Polygon *m_polygon;

public:

	typedef tcg::cyclic_iterator<rasterborder::iterator> cyclic_iter;</rasterborder::iterator>

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></tpixelgr8>

{

public:

	Vector<rasterborder *=""> m_borders;</rasterborder>

	RasterBorder *m_current;

public:

	BordersReader()

		: ImageMeshesReaderT<tpixelgr8>(PixelSelector<tpixelgr8>(false)), m_current(0) {}</tpixelgr8></tpixelgr8>

	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>

	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(</cyclic_iter>

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

	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,</rasterborder>

				   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();</imagemeshp>

	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();</ttexturemeshp>

	// 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)());</double></ttexturemesh>

		// 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)();</double>

		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();</ttexturemeshp>

	tcg::sequential_reader<std::vector<ttexturemeshp>> reader(&meshes);</std::vector<ttexturemeshp>

	tcg::gluTriangulate(tribe->begin(), tribe->end(), reader);

	delete tribe;

	// Perform meshes refinement

	refineMeshes(meshImage, opts);

	return meshImage;

}