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

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

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

                       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)));

      break;

    }

    case 2: {

      TRasterGR16P rasGR16(ras);

      thresholdRasterGr(rasGR16, binaryRas,

                        TPixelGR16::from(opts.m_transparentColor));

      break;

    }

    case 4: {

      TRaster32P ras32(ras);

      thresholdRaster(ras32, binaryRas, toPixel32(opts.m_transparentColor));

      break;

    }

    case 8: {

      TRaster64P ras64(ras);

      thresholdRaster(ras64, binaryRas, opts.m_transparentColor);

      break;

    }

    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 final : 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 final : public ImageMeshesReaderT<tpixelgr8> {</tpixelgr8>

public:

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

  RasterBorder *m_current;

public:

  BordersReader()

      : ImageMeshesReaderT<tpixelgr8>(PixelSelector<tpixelgr8>(false))</tpixelgr8></tpixelgr8>

      , m_current(0) {}

  void openFace(ImageMesh *mesh, int faceIdx, const TPixelGR8 &color) override {

    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) override {

    m_current = new RasterBorder;

    m_current->push_back(it.pos());

  }

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

  void addVertex(const raster_edge_iterator &it) override {

    m_current->push_back(it.pos());

  }

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

  void closeEdge(ImageMesh *mesh, int edgeIdx) override {

    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(cBegin - 1, cEnd + 1, 2.0,</cyclic_iter>

                                        (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, int meshIdx,</rasterborder>

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

        0.0, (std::numeric_limits<double>::max)());</double>

    // 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 = std::max(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;

}