// Dimitri Kudelski (Master SIS 2 Pro - Imagerie Numerique)
// Projet de Modelisation Geometrique : surfaces de subdivision
//
// Derniere modification : 10 Octobre 2007
//
// classe heMesh // he_mesh.cpp
// maillage de type Half-Edges


//#include <memory_mngr.h>
#include <he_mesh.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <math.h>
#include <GL/gl.h>

using namespace std;


// constructeur par defaut
//
// construit le maillage avec les valeurs par defaut
//
heMesh :: heMesh()
{
	vertices   = NULL;
	lastVertex = NULL;
	
	edges    = NULL;
	lastEdge = NULL;
	
	faces    = NULL;
	lastFace = NULL;
	
	type = MeshOther;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;
	name	  = 0;
}


// constructeur parametre
//
// construit le maillage et charge le fichier passe en parametre
//
heMesh :: heMesh(const char * _filename)
{	
	vertices   = NULL;
	lastVertex = NULL;
	
	edges    = NULL;
	lastEdge = NULL;
	
	faces    = NULL;
	lastFace = NULL;
	
	type = MeshOther;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;	
	name	  = 0;
	
	load(_filename);
}


// constructeur par copie
//
// recopie le maillage mesh
//
heMesh :: heMesh(const heMesh & _mesh)
{
	vector<heVertex *> coords;
	heHalfEdge * he;
	heEdge * e1, * e2, * beg;
	
	vertices   = NULL;
	lastVertex = NULL;
	
	edges    = NULL;
	lastEdge = NULL;
	
	faces    = NULL;
	lastFace = NULL;
	
	type = _mesh.type;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;
	name	  = 0;
	
	for(heVertex * ptr = _mesh.vertices; ptr; ptr = ptr->next)
	{
		coords.push_back(buildVertex(ptr->coord));
		coords.back()->id = ptr->id;
	}
	
	for(heFace * ptr = _mesh.faces; ptr; ptr = ptr->next)
	{		
		he = ptr->edge;
		beg = e2 = buildEdge(coords[he->tail->id], coords[he->head->id]);
		do
		{
			he = he->next;
			e1 = e2;
			
			if(he == ptr->edge)
				e2 = beg;
			else
				e2 = buildEdge(coords[he->tail->id], coords[he->head->id]);
			
			linkHalfEdges(e1->half, e2->half);
		}
		while(he != ptr->edge);
		
		buildFace(beg->half);
	}
	
	updateVerticesInfo();
}


// destructeur
//
// detruit le mailalge et libere la memoire
//
heMesh :: ~heMesh()
{
	clear();
}


void heMesh :: addVertex(heVertex * _v)
{
	if(vertices == NULL)
	{
		lastVertex = _v;
		vertices   = _v;
	}
	else
	{
		lastVertex->next = _v;
		lastVertex       = lastVertex->next;
	}
	
	nVertices++;
}


void heMesh :: addEdge(heEdge * _e)
{
	if(edges == NULL)
	{
		lastEdge = _e;
		edges    = _e;
	}
	else
	{
		lastEdge->next = _e;
		lastEdge       = lastEdge->next;
	}
	
	nEdges++;
}


void heMesh :: addFace(heFace * _f)
{
	if(faces == NULL)
	{
		lastFace = _f;
		faces    = _f;
	}
	else
	{
		lastFace->next = _f;
		lastFace       = lastFace->next;
	}
	
	nFaces++;
}


heVertex * heMesh :: buildVertex(const vec3 & _c)
{
	heVertex * v = new heVertex();
	
	v->coord = _c;

	addVertex(v);
	
	return v;
}


heEdge * heMesh :: buildEdge(heVertex * _tail, heVertex * _head)
{
	heEdge * e = new heEdge();	
	e->half    = new heHalfEdge();
	
	e->half->tail = _tail;
	e->half->head = _head;
	e->half->edge = e;
	
	addEdge(e);

	return e;	
}


heFace * heMesh :: buildFace(heHalfEdge * _he)
{
	heFace     * f   = new heFace();
	heHalfEdge * ptr = _he;
	
	f->edge = _he;	
	do
	{
		ptr->face = f;
		ptr		  = ptr->next;
	}
	while(ptr != f->edge);
	
	addFace(f);	
	
	return f;
}


void heMesh :: linkHalfEdges(heHalfEdge * _he1, heHalfEdge * _he2)
{
	_he1->next = _he2;
	_he2->prev = _he1;
}


void heMesh :: linkTwinEdges(heHalfEdge * _he, heHalfEdge * _twin)
{
	_he->twin   = _twin;
	_twin->twin = _he;
}


heHalfEdge * heMesh :: findTwinEdge(heHalfEdge * _he) const
{
	if(_he->twin != NULL)
		return _he->twin;
	else
	{
		if(_he->head->edges.size() < _he->tail->edges.size())
		{
			for(list<heHalfEdge *>::iterator it = _he->head->edges.begin(); it != _he->head->edges.end(); it++)
			{
				if((*it)->head == _he->tail)
					return *it;
			}
		}
		else
		{
			for(list<heHalfEdge *>::iterator it = _he->tail->edges.begin(); it != _he->tail->edges.end(); it++)
			{
				if((*it)->tail == _he->head)
					return *it;
			}
		}
		
		return NULL;
	}
}

/*
vec3 heMesh :: exceptionalButterfly(heHalfEdge * _he) const
{
	vec3 r = _he->tail->coord * 0.75;
	
	switch(_he->tail->valence)
	{
		case 0 :
			break;
		
		case 3 :
			r += _he->head->coord * 5.0 / 12.0;
			r -= _he->next->head->coord / 12.0;
			r -= _he->twin->next->head->coord / 12.0;
			break;
		
		case 4 :
			r += _he->head->coord * 3.0 / 8.0;
			r -= _he->prev->twin->next->head->coord / 8.0;
			break;
			
	}
}
*/


void heMesh :: updateVerticesInfo()
{	
	heHalfEdge * he, * ht;
	uint id(0), min, max, size;
	float n;
	
	nVertices = 0;
	for(heVertex * ptr = vertices; ptr; id++, ptr = ptr->next)
	{
		ptr->id = id;
		ptr->edges.clear();
		nVertices++;
	}
	
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		he = ptr->half;

		he->tail->edges.push_back(he);
		he->head->edges.push_back(he);
	}
	
	n = 0;
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		he = ptr->half;		
		ht = findTwinEdge(he);
		
		if(ht != NULL)
		{
			n += 0.5;
			
			linkTwinEdges(he, ht);
			for(list<heHalfEdge *>::iterator it = he->tail->edges.begin(); it != he->tail->edges.end(); it++)
			{
				if((*it) == ht)
					it = he->tail->edges.erase(it);
			}
			
			for(list<heHalfEdge *>::iterator it = ht->tail->edges.begin(); it != ht->tail->edges.end(); it++)
			{
				if((*it) == he)
					it = ht->tail->edges.erase(it);
			}
		}
		else
			n++;
	}
	
	nEdges = (int)n;

	size  = 0;
	he = faces->edge;
	do
	{
		size++;
		he = he->next;
	}
	while(he != faces->edge);
	
	min = max = size;	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		size = 0;
		he = ptr->edge;
		do
		{
			size++;
			he = he->next;
		}
		while(he != ptr->edge);
		
		if(size < min)
			min = size;
		
		if(max < size)
			max = size;
	}
	
	type = MeshOther;
	if(min == max)
	{
		if(min == 3)
			type = MeshTriangulated;
		
		if(min == 4)
			type = MeshQuadrangulated;		
	}
}


// methode de chargement d'un fichier obj
//
// charge le maillage au format obj
//
bool heMesh :: loadObj(const char * _filename)
{
	// variables pour le parsing du fichier obj
	ifstream file(_filename);
	string line;
	vec3 c;
	
	// donnees du fichier obj
	vector<heVertex *> coords;
	vector< vector<uint> > faces;
	
	// tant que le fichier n'est pas lu entierement
	while(!file.eof())
	{
		// variables temporaires de parsing
		istringstream iss;
		string keyword;
		
		// lecture d'une ligne et construction du flot de parsing
		getline(file, line);
		iss.str(line);
		
		// si le premier caractere est un #, alors c'est une ligne de commentaire
		if(iss.peek() != '#')
		{
			// recuperation du mot-cle
			iss >> keyword;
			
			// cas d'un sommet (v)
			if(keyword == "v")
			{
				// lecture des coordonnees du sommet
				iss >> c.x >> c.y >> c.z;
				
				// ajout au tableau
				coords.push_back(buildVertex(c));
				coords.back()->id = coords.size() - 1;
			}
			
			// cas d'une face (f)
			if(keyword == "f")
			{
				// variables temporaires pour le parsing
				char slash;
				uint v, n, t;		// sommet, normale, texture
				vector<uint> f;		// face en cours
				
				// lecture de l'espace
				iss >> std::ws;
				
				// lecture du premier sommet
				iss >> v;
				
				// selon le prochain caractere
				switch(iss.peek())
				{
					// format f v/??? v/??? ...
					case '/' :
						
						// on elimine le slash
						iss.get();
					
						// format f v//n v//n ...
						if(iss.peek() == '/')
						{
							// on elimine le slash
							iss.get();
							
							// on lit le reste de l'element
							iss >> n;								
							
							f.push_back(v - 1);
							// tant que le format est respecte
							while(iss.good())
							{
								// on lit les indices des sommets et des normales
								iss >> v >> slash >> slash >> n >> std::ws;
								
								// on ajoute l'indice a la face								
								f.push_back(v - 1);
							}
							
							// puis on ajoute la face au maillage
							faces.push_back(f);
						}
						else
						{							
							// sinon, on lit l'indice de texture
							iss >> t;
							
							// format f v/t/n v/t/n ...
							if(iss.peek() == '/')
							{
								// on elimine le slash
								iss.get();
								
								// on lit le reste de l'element
								iss >> n;
								
								f.push_back(v - 1);
								// tant que le format est respecte
								while(iss.good())
								{
									// on lit les indices des sommets, des textures et des normales
									iss >> v >> slash >> t >> slash >> n >> std::ws;
								
									// on ajoute l'indice a la face
									f.push_back(v - 1);
								}
								
								// puis on ajoute la face au maillage
								faces.push_back(f);
							}
							// format f v/t v/t ...
							else
							{								
								f.push_back(v - 1);
								// tant que le format est respecte
								while(iss.good())
								{	
									// on lit les indices des sommets et des textures
									iss >> v >> slash >> t >> std::ws;
									
									// et on ajoute l'indice a la face
									f.push_back(v - 1);
								}
								
								// puis on ajoute la face au maillage
								faces.push_back(f);
							}
						}
						
						break;
						
					// format f v v ...
					case ' ' :
					
						f.push_back(v - 1);
						// tant que le format est respecte
						while(iss.good())
						{			
							// on lit les indices des sommets
							iss >> v >> std::ws;
							
							// et on ajoute l'indice a la face
							f.push_back(v - 1);
						}
					
						// puis on ajoute la face au maillage
						faces.push_back(f);
						
						break;
				}
			}
		}
	}
	
	uint min, max;
	if(faces.size() < 1)
		return false;
	
	min = max = faces[0].size();
	
	heEdge * beg, * e1, * e2;
	uint n;
	for(uint i(0); i < faces.size(); i++)
	{
		n = faces[i].size();
		
		if(n < min)
			min = n;
		
		if(max < n)
			max = n;
		
		if(n < 3)
		{
			clear();
			return false;
		}
		
		beg = e2 = buildEdge(coords[faces[i][0]], coords[faces[i][1]]);
		for(uint j(1); j < n; j++)
		{
			e1 = e2;
			e2 = buildEdge(coords[faces[i][j]], coords[faces[i][(j+1) % n]]);
			
			linkHalfEdges(e1->half, e2->half);
		}
		
		linkHalfEdges(e2->half, beg->half);		
		buildFace(beg->half);
	}
	
	updateVerticesInfo();	
	return true;
}


// methode de chargement du maillage
//
// charge le maillage en fonction de l'extension du fichier passe en parametre
//
bool heMesh :: load(const char * _filename) 
{
	char * extension = strrchr(_filename, '.');
	ifstream file(_filename);
	
	if(!file)
	{
		cerr << "[heMesh::load] Erreur. Le fichier \"" << _filename << "\" est introuvable." << endl;
		return false;
	}
	
	file.close();
		
	if(strcmp(extension, ".obj") == 0)
		return loadObj(_filename);
	
	cerr << "[heMesh::load] Erreur. Le format du fichier \"" << _filename << "\" n'est pas reconnu." << endl;	
	return false;
}


// methode de vidage du maillage
//
// supprime les sommets, aretes et faces du maillage
//
void heMesh :: clear() 
{
	heVertex * ptrV;
	heEdge   * ptrE;
	heFace   * ptrF;
	
	type = MeshOther;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;
	
	while(vertices)
	{
		ptrV     = vertices;
		vertices = vertices->next;
		
		delete ptrV;
	}
		
	while(edges)
	{
		ptrE  = edges;
		edges = edges->next;
		
		delete ptrE;
	}
		
	while(faces)
	{
		ptrF  = faces;
		faces = faces->next;
		
		delete ptrF;
	}
	
	vertices = lastVertex = NULL;
	faces    = lastFace   = NULL;
	edges    = lastEdge   = NULL;

	name = 0;
}


// methode d'enregistrement du maillage
//
// enregistre le maillage dans le fichier passe en parametre
//
bool heMesh :: save(const char * _filename) const
{
	ofstream file(_filename);
	
	if(file == NULL)
	{
		cerr << "[heMesh::save] Erreur. Le maillage ne peut pas etre enregistre dans le fichier \"" << _filename << "\"." << endl;
		return false;
	}
	
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		file << "v " << ptr->coord.x << " " << ptr->coord.y << " " << ptr->coord.z << "\n";
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		heHalfEdge * he = ptr->edge;
		
		file << "f";
		do
		{
			file << " " << (he->tail->id + 1);
			he = he->next;
		}
		while(he != ptr->edge);
		file << "\n";
	}
	
	file.close();
	return true;
}


// methode de normalisation du maillage
//
// fait rentrer le maillage dans un cube de cote 1 :)
//
void heMesh :: unitize()
{
	// variables de calcul de boite englobante
	vec3 min, max, center, size;
	float scale;
	
	// s'il n'y a pas de sommet, pas besoin de normaliser :)
	if(vertices == NULL)
	{
		return;
	}
	
	// recherche du min et max
	min = max = vertices->coord;
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
	{
		if(ptr->coord.x > max.x)
			max.x = ptr->coord.x;
		
		if(ptr->coord.y > max.y)
			max.y = ptr->coord.y;
		
		if(ptr->coord.z > max.z)
			max.z = ptr->coord.z;
		
		if(ptr->coord.x < min.x)
			min.x = ptr->coord.x;
		
		if(ptr->coord.y < min.y)
			min.y = ptr->coord.y;
		
		if(ptr->coord.z < min.z)
			min.z = ptr->coord.z;
	}
	
	// calcul de la taille et du centre de la boite
	size.x = fabs(min.x) + fabs(max.x);
	size.y = fabs(min.y) + fabs(max.y);
	size.z = fabs(min.z) + fabs(max.z);	
	center = (min + max) / 2.0;
	
	// calcul du coefficient de mise a l'echelle
	if(size.x > size.y)
	{
		if(size.x > size.z)
			scale = 1.0 / size.x;
		else
		{
			if(size.y > size.z)
				scale = 1.0 / size.y;
			else
				scale = 1.0 / size.z;
		}
	}
	else
	{
		if(size.y > size.z)
			scale = 1.0 / size.y;
		else
		{
			if(size.x > size.z)
				scale = 1.0 / size.x;
			else
				scale = 1.0 / size.z;
		}
	}
	
	// translation + reduction
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
	{
		ptr->coord -= center;		
		ptr->coord *= scale;
	}
}


// methode de triangulation du maillage
//
// prend le maillage non-triangule et le triangule a la facon GL_TRIANGLE_FAN
//
void heMesh :: triangulate()
{
	if(type == MeshTriangulated)
		return;
	
	nEdges = 0;
	nFaces = 0;
	
	heHalfEdge * he;
	heEdge * e1, * e2, * e3;
	heFace * last = lastFace;
	
	for(heFace * ptr = faces; ptr && ptr != last->next; ptr = ptr->next)
	{		
		he = ptr->edge;
		
		e1 = he->edge;
		he = he->next;
		nEdges++;
		
		if(he == ptr->edge)
		{
			e2 = he->edge;
			nEdges++;
			
			linkHalfEdges(e1->half, e2->half);
			linkHalfEdges(e2->half, e1->half);
			nFaces++;
		}
		else
		{
			e2 = he->edge;
			he = he->next;
			nEdges++;
			
			if(he->next == ptr->edge)
			{
				e3 = he->edge;
				nEdges++;
		
				linkHalfEdges(e1->half, e2->half);
				linkHalfEdges(e2->half, e3->half);
				linkHalfEdges(e3->half, e1->half);
				
				ptr->edge = e1->half;
				nFaces++;
			}
			else
			{
				e3 = buildEdge(e2->half->head, e1->half->tail);
				e3->half->face = e1->half->face;
				nFaces++;
			
				linkHalfEdges(e1->half, e2->half);
				linkHalfEdges(e2->half, e3->half);
				linkHalfEdges(e3->half, e1->half);
				
				while(he->next->next != ptr->edge)
				{
					e1 = buildEdge(e3->half->head, e3->half->tail);
					e2 = he->edge;
					nEdges++;
					
					he = he->next;
					e3 = buildEdge(he->tail, e1->half->tail);
					
					linkHalfEdges(e1->half, e2->half);
					linkHalfEdges(e2->half, e3->half);
					linkHalfEdges(e3->half, e1->half);
					buildFace(e1->half);
				}
				
				e1 = buildEdge(e3->half->head, e3->half->tail);
				e2 = he->edge;
				nEdges++;
				
				e3 = he->next->edge;
				nEdges++;
			
				linkHalfEdges(e1->half, e2->half);
				linkHalfEdges(e2->half, e3->half);
				linkHalfEdges(e3->half, e1->half);				
				buildFace(e1->half);
			}
		}
	}
	
	updateVerticesInfo();
}


// methode de calcul des normales du maillage
//
// calcule les normales aux sommets et les normales aux faces
//
void heMesh :: computeNormals()
{
	// iterateur de parcours
	vec3 v1, v2, n;
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		heHalfEdge * he = ptr->edge;
		n  = vec3 :: zero;
		
		// parcours de chaque sommet de la face
		do
		{
			v1 = he->tail->coord;
			v2 = he->head->coord;
			
			// calcul de la normale
			n.x += (v1.z + v2.z) * (v1.y - v2.y);
			n.y += (v1.x + v2.x) * (v1.z - v2.z);
			n.z += (v1.y + v2.y) * (v1.x - v2.x);

			he = he->next;
		}
		while(he != ptr->edge);
		
		// normalisation et affectation
		n.normalize();
		ptr->normal = n;
		
		// parcours de chaque sommet de la face
		he = ptr->edge;		
		do
		{
			he->tail->normal += n;			
			he = he->next;
		}
		while(he != ptr->edge);
	}
	
	// parcours de tous les sommets
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		ptr->normal.normalize();
}


// methode d'affichage du maillage
//
// affiche le maillage grace aux fonctions openGL
//
void heMesh :: display()
{
	if(name == 0)
	{
		heHalfEdge * he;
		
		name = glGenLists(1);
		glNewList(name, GL_COMPILE);
		
		glColor3f(0, 0, 0);
		for(heFace * ptr = faces; ptr; ptr = ptr->next)
		{
			//glBegin(GL_TRIANGLE_FAN);
			glBegin(GL_POLYGON);

			he = ptr->edge;			
			do
			{
				glNormal3fv(he->tail->normal);
				glVertex3fv(he->tail->coord);				
				he = he->next;
			}
			while(he != ptr->edge);
			
			glEnd();
		}
		
		glEndList();
	}
	
	glCallList(name);
}


// methode d'acces au nombre de sommets
//
// renvoie le nombre de sommets du maillage
//
uint heMesh :: getNVertices() const
{
	return nVertices;
}


// methode d'acces au nombre d'aretes
//
// renvoie le nombre d'aretes du maillage
//
uint heMesh :: getNEdges() const
{
	return nEdges;
}


// methode d'acces au nombre de faces
//
// renvoie le nombre de faces du maillage
//
uint heMesh :: getNFaces() const
{
	return nFaces;
}


// methode d'acces au type de maillage
//
// renvoie le type du maillage
//
uint heMesh :: getType() const
{
	return type;
}