//
//    File: mesh.cc
//
//    (C) 2000-2008 Helmut Cantzler
//
//    Licensed under the terms of the Lesser General Public License.
//

#include "mesh.h"

#ifndef WIN32
//    #include <values.h>
    #include <limits.h>
#else
    #include <float.h>
    #define MAXFLOAT FLT_MAX
#endif

Mesh::Mesh()
{
  edgeNr = verNr = triNr = 0;
  xMin = xMax = yMin = yMax = zMin = zMax = 0;

  modelCentroid.setZero();
  modelScale = 1.0;

  shapes = new vector<Shape*>;
  triangles = new list<Triangle*>;
  vertices = new list<Vertex*>;
  edges = new list<Edge*>;

  path = NULL;
  fileName = NULL;
}

Mesh::~Mesh()
{
  clear();

  delete shapes;
  delete triangles;
  delete edges;
  delete vertices;

  delete path;
  delete fileName;
}

void Mesh::clear(void)
{
  vector<Shape*>::iterator is;
  list<Triangle*>::iterator it;
  list<Edge*>::iterator ie;
  list<Vertex*>::iterator iv;

  for (is=shapes->begin(); is != shapes->end(); is++)
    delete *is;
  for (it=triangles->begin(); it != triangles->end(); it++)
    delete *it;
  for (ie=edges->begin(); ie != edges->end(); ie++)
    delete *ie;
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    delete *iv;

  shapes->clear();
  triangles->clear();
  edges->clear();
  vertices->clear();

  edgeNr = verNr = triNr = 0;
  xMin = xMax = yMin = yMax = zMin = zMax = 0;
}

int Mesh::numberOfVertices(void) const
{
  return verNr;
}

int Mesh::numberOfEdges(void) const
{
  return edgeNr;
}

int Mesh::numberOfTriangles(void) const
{
  return triNr;
}

float Mesh::getXMin(void) const
{
  return xMin;
}

float Mesh::getXMax(void) const
{
  return xMax;
}

float Mesh::getYMin(void) const
{
  return yMin;
}

float Mesh::getYMax(void) const
{
  return yMax;
}

float Mesh::getZMin(void) const
{
  return zMin;
}

float Mesh::getZMax(void) const
{
  return zMax;
}

void Mesh::addTriangle(Triangle *t)
{
  triangles->push_back(t);
  t->name = ++triNr;
}

void Mesh::addEdge(Edge *e)
{
  edges->push_back(e);
  e->name = ++edgeNr;
}

void Mesh::addVertex(Vertex *v)
{
  vertices->push_back(v);
  v->name = ++verNr;
}

void Mesh::remove(Vertex *v)
{
  vector<Shape*>::iterator is;

  vertices->remove(v);
  for (is=shapes->begin(); is != shapes->end(); is++)
    (*is)->vertices->remove(v);

  delete v;
}

void Mesh::remove(Edge *e)
{
  vector<Shape*>::iterator is;

  edges->remove(e);
  for (is=shapes->begin(); is != shapes->end(); is++)
    if ((*is)->edges != NULL)
      (*is)->edges->remove(e);

  delete e;
}

void Mesh::remove(Triangle *t)
{
  vector<Shape*>::iterator is;

  triangles->remove(t);
  for (is=shapes->begin(); is != shapes->end(); is++)
    (*is)->triangles->remove(t);

  delete t;
}

void Mesh::addVertices(list<Vertex*> *newVertices)
{
  list<Vertex*>::iterator iv;
  list<Vertex*> *shapeVertices;
  Vertex *ver;

  shapeVertices = new list<Vertex*>;

  for (iv=newVertices->begin(); iv != newVertices->end(); iv++)
    {
      ver = new Vertex( (*iv)->x(), (*iv)->y(), (*iv)->z() );
      addVertex(ver);
      shapeVertices->push_back(ver);
    }

  shapes->push_back(new Shape(shapeVertices));
}

void Mesh::addEdges(list<Edge*> *newEdges, int clearMap)
{
  // mapping from old to new vertices
  map<Vertex*, Vertex*>::iterator iv;
  list<Edge*>::iterator ie;
  list<Vertex*> *shapeVertices;
  list<Edge*> *shapeEdges;
  Vertex *ver, *v[2];
  Edge *edg;
  int i;

  shapeVertices = new list<Vertex*>;
  shapeEdges = new list<Edge*>;

  for (ie=newEdges->begin(); ie != newEdges->end(); ie++)
    {
      // Get or create the two new vertices
      for (i=0; i < 2; i++)
	{
	  ver=(*ie)->vertices[i];
	  // avoid using vertices more than once
	  iv=vertexMap.find(ver);
	  if (iv == vertexMap.end())
	    {
	      // Create one new vertex
	      v[i] = new Vertex( ver->x(), ver->y(), ver->z() );
	      addVertex(v[i]);
	      shapeVertices->push_back(v[i]);
	      // old vertex => new vertex
	      vertexMap[ver] = v[i];
	    }
	  else
	    // We found the vertex in our list
	    v[i]=(*iv).second;
	}
	    
      // Create one new edge with the two vertices
      edg = new Edge(v[0], v[1]);
      addEdge(edg);
      shapeEdges->push_back(edg);
    }

  shapes->push_back(new Shape(shapeEdges, shapeVertices));

  if (clearMap)
    vertexMap.clear();
}

void Mesh::addTriangles(list<Triangle*> *newTriangles, 
			 const char *textureName, int clearMap)
{
  // mapping from old to new vertices
  map<Vertex*, Vertex*>::iterator iv;
  list<Triangle*>::iterator it;
  list<Triangle*> *shapeTriangles;
  list<Vertex*> *shapeVertices;
  Vertex *ver, *v[3];
  Triangle *tri;
  int i;

  shapeTriangles = new list<Triangle*>;
  shapeVertices = new list<Vertex*>;

  for (it=newTriangles->begin(); it != newTriangles->end(); it++)
    {
      // Get or create the three new vertices
      for (i=0; i < 3; i++)
	{
	  ver=(*it)->vertices[i];
	  // avoid using vertices more than once
	  iv=vertexMap.find(ver);
	  if (iv == vertexMap.end())
	    {
	      // Create one new vertex
	      v[i] = new Vertex( ver->x(), ver->y(), ver->z() );
	      addVertex(v[i]);
	      shapeVertices->push_back(v[i]);
	      // old vertex => new vertex
	      vertexMap[ver] = v[i];
	    }
	  else
	    // We found the vertex in our list
	    v[i]=(*iv).second;
	}
      
      // Create one new triangle with the three vertices
      tri = new Triangle(v[0], v[1], v[2]);
      for (i=0; i < 3; i++)
	tri->setTextCoordinates( i, (*it)->getTextS(i),
				 (*it)->getTextT(i) );
      addTriangle(tri);
      shapeTriangles->push_back(tri);
    }

  shapes->push_back(new Shape(shapeTriangles, 
			      shapeVertices, textureName));

  if (clearMap)
    vertexMap.clear();
}

void Mesh::addMesh(Mesh *mesh)
{
  // adding shapes, triangles or edges automatically creates the vertices

  if (mesh != NULL)
    if (mesh->numberOfShapes() > 0)
      {
	for (int i=0; i < mesh->numberOfShapes(); i++)
	  if (mesh->getShape(i)->numberOfTriangles() > 0)
	    addTriangles(mesh->getShape(i)->triangles,
			 mesh->getShape(i)->getTextureName(), FALSE);
	  else if (mesh->getShape(i)->numberOfEdges() > 0)
	    addEdges(mesh->getShape(i)->edges, FALSE);
	  else if (mesh->getShape(i)->numberOfVertices() > 0)
	    addVertices(mesh->getShape(i)->vertices);
	
	vertexMap.clear();
      }
    else
      {
	if (mesh->numberOfTriangles() > 0)
	  addTriangles(mesh->triangles);
	else if (mesh->numberOfEdges() > 0)
	  addEdges(mesh->getEdges());
	else if (mesh->numberOfVertices() > 0)
	  addVertices(mesh->getVertices());
      }
}

void Mesh::setMesh(Mesh *mesh)
{
  modelCentroid = mesh->modelCentroid;
  modelScale = mesh->modelScale;

  clear();

  addMesh(mesh);
  setMinMaxValues();
}

int Mesh::read(FILE *f, int (*updateProgress)(int pos),
	       void (*setTotal)(int size))
{
  return 99;
}

void Mesh::write(FILE *f, const char *comment)
{
}

Vertex* Mesh::getVertex(unsigned int name) const
{
  list<Vertex*>::iterator iv;

  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    if ((*iv)->name == name)
      return *iv;

  return NULL;
}

Edge* Mesh::getEdge(unsigned int name) const
{
  list<Edge*>::iterator ie;

  for (ie=edges->begin(); ie != edges->end(); ie++)
    if ((*ie)->name == name)
      return *ie;

  return NULL;
}

Triangle* Mesh::getTriangle(unsigned int name) const
{
  list<Triangle*>::iterator it;

  for (it=triangles->begin(); it != triangles->end(); it++)
    if ((*it)->name == name)
      return *it;

  return NULL;
}

int Mesh::type(FILE *f)
{
  char s1[21], s2[21];
  int g, endOfLine1, endOfLine2;
  float p;

  if (fscanf(f,"%20s %20s", s1, s2) != 2) // Read the first two strings
    return UNKNOWN_MESH; // Unknown file format
  endOfLine2 = fgetc(f) == '\n' ? TRUE : FALSE;
  rewind(f);

  // added for shallo mesh; end of line after first argument?
  fscanf(f, "%20s", s1);
  endOfLine1 = fgetc(f) == '\n' ? TRUE : FALSE;

  rewind(f);

  // check vtk
  if ((strcasecmp(s2,"vtk") == 0) || (strcasecmp(s1,"#vtk") == 0))
    return VTK_MESH;

  // check geomview (both OFF or COFF)
  if ((strcasecmp(s1,"COFF") == 0) || (strcasecmp(s1,"OFF") == 0))
    return GEOMVIEW_MESH;
  
	// check ply
  if (strcasecmp(s1,"PLY") == 0)
    return PLY_MESH;
	
  // check vrml1
  else if (strcasecmp(s1,"#VRML") == 0 && strcasecmp(s2,"V1.0") == 0)
    return VRML1_MESH;

  // check vrml2
  else if (strcasecmp(s1,"#VRML") == 0 && strcasecmp(s2,"V2.0") == 0)
    return VRML2_MESH;

  // check pmesh
  else if (strcasecmp(s1,"#PMESH") == 0 || 
	  (strcasecmp(s1,"V") == 0 && sscanf(s2,"%f",&p) == 1 && !endOfLine2))
    return P_MESH;

  // check obj
  else if (strcmp(s1,"g") == 0 || 
          (strcasecmp(s1,"mtllib") == 0) ||
	  (strcasecmp(s1,"usemtl") == 0) ||
	  (strcmp(s1,"v") == 0 && sscanf(s2,"%f",&p) == 1 && !endOfLine2))
    return OBJ_MESH;

  // check gts
  else if (sscanf(s1,"%d",&g) == 1 && sscanf(s2,"%d",&g) == 1 && !endOfLine2 & !endOfLine1)
    return GTS_MESH;

  // check shallo mesh (only 1 int in first line = number of vertices)
  else if (sscanf(s1,"%d",&g) == 1 && sscanf(s2,"%f",&p) == 1 && endOfLine1)
    return SHALLO_MESH;

  // check features
  else if (strcasecmp(s1,"#FEATURES") == 0)
    return FEATURES_MESH;

  // check mesh list
  else if (strcasecmp(s1,"#LIST") == 0)
    return LIST_MESH;

	// re-check gts with initial comments skipped
	// skip any preceeding GTS or OBJ comment lines 
        // (like those produced in k3d GTS files)
	
	else {
		while (s1[0] == '#'){
			while ((fgetc(f) != '\n') && (!(feof(f)))) // Reads till end of the line
				;
			if (fscanf(f,"%20s %20s", s1, s2) != 2) // re-read the first two strings
				return UNKNOWN_MESH; // Unknown file format
		}
		endOfLine2 = fgetc(f) == '\n' ? TRUE : FALSE;
		if (sscanf(s1,"%d",&g) == 1 && sscanf(s2,"%d",&g) == 1 && !endOfLine2){
			return GTS_MESH;
		} else if (strcmp(s1,"g") == 0 || (strcasecmp(s1,"mtllib") == 0) ||
		         (strcasecmp(s1,"usemtl") == 0) ||
		         (strcmp(s1,"v") == 0 && sscanf(s2,"%f",&p) == 1 && !endOfLine2)){	
			return OBJ_MESH;
		}
	}
	
  return UNKNOWN_MESH; // Unknown file format
}

void Mesh::setName(const char *n)
{
  delete fileName;
  fileName = new char[strlen(n)+1];
  strcpy(fileName, n);
}

void Mesh::setPath(const char *p)
{
  delete path;
  path = new char[strlen(p)+1];
  strcpy(path, p);
}

char* Mesh::getName() const
{
  return fileName;
}

char* Mesh::getPath() const
{
  return path;
}

int Mesh::numberOfShapes(void) const
{
  return (int) shapes->size();
}

list<Triangle*>* Mesh::getTriangles(void) const
{
  return triangles;
}

list<Vertex*>* Mesh::getVertices(void) const
{
  return vertices;
}

list<Edge*>* Mesh::getEdges(void) const
{
  return edges;
}

Shape* Mesh::getShape(unsigned int no) const
{
  if (no < shapes->size())
    return (*shapes)[no];

  return NULL;
}

list<Edge*>* Mesh::getEdges(list<Edge*> *es) const
{
  list<Edge*> *edgeList = new list<Edge*>;
  list<Edge*>::iterator ie1, ie2;

  for (ie1=es->begin(); ie1 != es->end(); ie1++)
    for (ie2=edges->begin(); ie2 != edges->end(); ie2++)
      if ((*ie2)->equal(*ie1))
	edgeList->push_back(*ie2);

  return edgeList;
}

Edge* Mesh::getEdge(map<pair<Vertex*,Vertex*>,Edge*> *edgeMap, 
		     Vertex *v1, Vertex *v2)
{
  map<pair<Vertex*,Vertex*>,Edge*>::iterator ei;

  // search in map (hash table)
  // first try to get the edge
  ei=edgeMap->find( pair<Vertex*,Vertex*> (v1, v2) );
  // second try to get the edge (reverse order)
  if (ei == edgeMap->end())
    ei=edgeMap->find( pair<Vertex*,Vertex*> (v2, v1) );
  if (ei == edgeMap->end())
    {
      // create new edge
      Edge *e = new Edge(v1, v2);
      addEdge(e);

      // new hash entry
      (*edgeMap)[ pair<Vertex*,Vertex*> (v1, v2) ] = e;
      return e;
    }
  else
    return (*ei).second;
}

void Mesh::createEdges(void)
{
  list<Triangle*>::iterator it;
  map<pair<Vertex*,Vertex*>,Edge*> edgeMap;
  Edge *e;

  for (it=triangles->begin(); it != triangles->end(); it++)
    {
      // edge 1
      e = getEdge(&edgeMap, (*it)->vertices[0], (*it)->vertices[1]);
      (*it)->edges[0]=e;   e->addTriangle(*it);

      // edge 2
      e = getEdge(&edgeMap, (*it)->vertices[0], (*it)->vertices[2]);
      (*it)->edges[1]=e;   e->addTriangle(*it);

      // edge 3
      e = getEdge(&edgeMap, (*it)->vertices[1], (*it)->vertices[2]);
      (*it)->edges[2]=e;   e->addTriangle(*it);
    }
}

float Mesh::averageTriangleSize(void) const
{
  list<Triangle*>::iterator it;
  float size=0.0;

  for (it=triangles->begin(); it != triangles->end(); it++)
    size+=(*it)->perimeter();

  return size/triNr;
}

void Mesh::setMinMaxValues(void)
{
  list<Vertex*>::iterator iv;

  xMin = xMax = yMin = yMax = zMin = zMax = 0;

  // find smalles & largest vertex in all directions (x, y, z)
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    {
      if (xMin > (*iv)->x())
	xMin = (*iv)->x();
      if (xMax < (*iv)->x())
	xMax = (*iv)->x();
      if (yMin > (*iv)->y())
	yMin = (*iv)->y();
      if (yMax < (*iv)->y())
	yMax = (*iv)->y();
      if (zMin > (*iv)->z())
	zMin = (*iv)->z();
      if (zMax < (*iv)->z())
	zMax = (*iv)->z();
    }
}

void Mesh::moveToCentre(void)
{
  modelCentroid = getCentroid();
  modelCentroid.negation();
  move(&modelCentroid);
  modelCentroid.negation();
}

MathVector Mesh::getCentroid(void) const
{
  list<Vertex*>::iterator iv;
  MathVector c;

  // find centroid
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    c.add((*iv)->mathData());
  c.scale(1.0/verNr);

  return c;
}

void Mesh::move(const MathVector *v)
{
  list<Triangle*>::iterator it;
  list<Vertex*>::iterator iv;

  // Move vertices and triangle centroids
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    (*iv)->move(v);
  for (it=triangles->begin(); it != triangles->end(); it++)
    (*it)->moveCentroid(v);
}

void Mesh::scaleIntoNormalSphere(void)
{
  // Scaling mesh into +/- 1 sphere
  modelScale = sqrt(getMaxVertexLength())/2;
  scale( modelScale );
  modelScale = 1.0 / modelScale;
  setMinMaxValues();
}

float Mesh::getMaxVertexLength(void) const
{
  list<Vertex*>::iterator iv;
  float length=0.0;

  // Finding the length
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    length = MAX( float, (*iv)->length(), length );

  return length;
}

void Mesh::scale(float scale)
{
  list<Triangle*>::iterator it;
  list<Edge*>::iterator ie;
  list<Vertex*>::iterator iv;

  // Scaling vertices
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    (*iv)->scale(scale);
  // Recalculate triangle centroid, size, perimeter and so on
  for (it=triangles->begin(); it != triangles->end(); it++)
    (*it)->calcProperties();
  // Recalculate edge centroid, length and so on
  for (ie=edges->begin(); ie != edges->end(); ie++)
    (*ie)->calcProperties();
}

void Mesh::calcOriginalCoordinates(const Vertex *v, Vertex *org) const
{
  org->set(v);
  org->scale(modelScale);
  org->move(&modelCentroid);
}

MathVector Mesh::getModelCentroid(void) const
{
  return modelCentroid;
}

float Mesh::getModelScale(void) const
{
  return modelScale;
}

void Mesh::scaleAccordingToReferenceMesh(const Mesh *mesh)
{
  modelCentroid = mesh->getModelCentroid();
  modelScale = 1.0/mesh->getModelScale();
  modelCentroid.negation();

  move(&modelCentroid);
  scale(modelScale);

  modelScale = 1.0/modelScale;
  modelCentroid.negation();
  setMinMaxValues();
}

void Mesh::clearSelection(void)
{
  selectedVertices.clear();
  selectedEdges.clear();
  selectedTriangles.clear();
}

Vertex* Mesh::selectVertex(unsigned int name)
{
  Vertex *v = getVertex(name);

  if (v != NULL)
    selectedVertices.push_back(v);

  return v;
}

Edge* Mesh::selectEdge(unsigned int name)
{
  Edge *e = getEdge(name);

  if (e != NULL)
    selectedEdges.push_back(e);

  return e;
}

Triangle* Mesh::selectTriangle(unsigned int name)
{
  Triangle *t = getTriangle(name);

  if (t != NULL)
    selectedTriangles.push_back(t);

  return t;
}

void Mesh::negateSurfaceNormals(void)
{
  list<Triangle*>::iterator it;

  // negate all triangle surface normals
  for (it=triangles->begin(); it != triangles->end(); it++)
    (*it)->negateNormal();
}

void Mesh::removeDoublePoints(void)
{
  // the MathVector represents the x, y and z coordinates of the vertex
  map<MathVector, Vertex*> vertexMap;
  map<MathVector, Vertex*>::iterator iMap;
  list<Vertex*>::iterator iList;
  list<Triangle*>::iterator it;
  list<Triangle*> *verTriangles;
  list<Edge*>::iterator ie;
  list<Edge*> *verEdges;

  for (iList=vertices->begin(); iList != vertices->end();)
    {
      // Check if we have the vertex already
      iMap=vertexMap.find( *(*iList)->mathData() );
      if (iMap == vertexMap.end())
	{
	  // Create a new entry
	  vertexMap[ *(*iList)->mathData() ] = *iList;
	  iList++;
	}
      else
	{
	  // change all references to the vertex
	  verTriangles=(*iList)->getTriangles();
	  for (it=verTriangles->begin(); it != verTriangles->end(); it++)
	    (*it)->changeVertex(*iList, (*iMap).second);
	  verEdges=(*iList)->getEdges();
	  for (ie=verEdges->begin(); ie != verEdges->end(); ie++)
	    (*ie)->changeVertex(*iList, (*iMap).second);

	  // remove from shapes
	  for (int i=0; i < numberOfShapes(); i++)
	    getShape(i)->changeVertex(*iList, (*iMap).second);

	  // delete vertex and remove from list
	  delete *iList;
	  iList=vertices->erase(iList);
	}
    }

  verNr= (int) vertices->size();
}

Vertex* Mesh::findClosedPoint(const Vertex *v) const
{
  list<Vertex*>::iterator iv;
  MathVector con;
  Vertex *best = NULL;
  float bestLength;

  bestLength=MAXFLOAT;
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    {
      MathVector::sub((*iv)->mathData(), v->mathData(), &con);
      if (con.length() < bestLength)
	{
	  bestLength=con.length();
	  best=*iv;
	}
    }
 
  return best;
}

void Mesh::writeGtsPoints(FILE *f) const
{
  int n;
  list<Vertex*>::iterator iv;

  // header
  fprintf(f,"%d 0 0\n", verNr);

  // vertex::number == vertex::name ???

  n=0;   // vertices
  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    {
      fprintf(f,"%f %f %f\n", (*iv)->x(), (*iv)->y(), (*iv)->z());
      n++;
      (*iv)->number=n;
    }
}

void Mesh::writePoints(FILE *f) const
{
  list<Vertex*>::iterator iv;

  for (iv=vertices->begin(); iv != vertices->end(); iv++)
    fprintf(f,"%f %f %f\n", (*iv)->x(), (*iv)->y(), (*iv)->z());
}