// 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 <he_mesh.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
#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;
}


// 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;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;
	
	load(_filename);
}


// constructeur par copie
//
// recopie le maillage mesh
//
heMesh :: heMesh(const heMesh & _mesh)
{
	vector<heVertex *> v;
	vector<vector<uint> > f;
	
	vertices   = NULL;
	lastVertex = NULL;
	
	edges    = NULL;
	lastEdge = NULL;
	
	faces    = NULL;
	lastFace = NULL;
	
	nVertices = 0;
	nEdges    = 0;
	nFaces    = 0;
	
	for(heVertex * ptr = _mesh.vertices; ptr; ptr = ptr->next)
		v.push_back(new heVertex(ptr->coord));
	
	for(heFace * ptr = _mesh.faces; ptr; ptr = ptr->next)
	{
		vector<uint> current;	
		heHalfEdge * he = ptr->edge;
		
		do
		{
			current.push_back(he->tail->id);
			he = he->next;					
		}
		while(he != ptr->edge);
		
		f.push_back(current);		
	}
	
	buildMesh(v, f);
}


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


// 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(new heVertex(c));
			}
			
			// 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;
						
				}
			}
		}
	}
	
	// construction du maillage
	return buildMesh(coords, faces);
}


// methode de construction d'une arete
//
// prend en parametre deux sommets et cree une arete
//
heEdge * heMesh :: buildEdge(heVertex * _t, heVertex * _h)
{
	heEdge     * e  = new heEdge();
	heHalfEdge * he = new heHalfEdge();
	
	e->half = he;
	e->next = NULL;
	
	he->head = _h;
	he->tail = _t;
	
	he->tail->edge = he;
	
	return e;
}


// methode de construction d'une face
//
// prend en parametre un tableau d'aretes et cree une face
//
heFace * heMesh :: buildFace(const vector<heEdge *> & _e)
{
	heFace * f = new heFace();
	
	f->edge = _e[0]->half;
	for(uint i(0); i < _e.size(); i++)
		_e[i]->half->face = f;
	
	linkFaceEdges(_e);	
	return f;
}


// methode de recherche d'arete jumelle dans un tableau de listes
//
// prend en parametre un tableau de liste de d'aretes et recherche l'arete jumelle de celle passee en parametre
//
heEdge * heMesh :: findPairEdge(heHalfEdge * _he, const std::vector<heEdge *> & _l) const
{
	for(uint i(0); i < _l.size(); i++)
	{
		if(_l[i]->half->pair == NULL)
		{
			if(_l[i]->half->head == _he->tail && _l[i]->half->tail == _he->head)
				return _l[i];
		}
	}
	
	return NULL;
}


// methode de link d'une face
//
// prend en parametre un tableau d'aretes et lie les aretes entre elles
//
void heMesh :: linkFaceEdges(const std::vector<heEdge *> & _e)
{
	uint n = _e.size();
	
	for(uint i(0); i < n; i++)
	{
		_e[i]->half->next = _e[(i + 1) % n]->half;
		_e[(i + 1) % n]->half->prev = _e[i]->half;

		_e[i]->half->head = _e[i]->half->next->tail;
	}
}



// methode de construction du maillage
//
// prend en parametre un tableau de coordonnees et un tableau de faces pour construire le maillage
//
bool heMesh :: buildMesh(const std::vector<heVertex *> & _c, const std::vector<vector<uint> > & _f)
{
	uint v1, v2, n, min, max;
	vector<vector<heEdge *> > E;
	map<heVertex *, vector<heEdge *> > M;
	
	clear();
	
	if(_c.size() == 0 || _f.size() == 0)
		return false;	
	
	min = max = _f[0].size();
	
	for(uint i(0); i < _f.size(); i++)
	{
		vector<heEdge *> F;
		
		n = _f[i].size();
		
		if(n < min)
			min = n;
		
		if(max < n)
			max = n;
		
		for(uint j(0); j < n; j++)
		{
			v1 = _f[i][j % n];
			v2 = _f[i][(j + 1) % n];
			
			F.push_back(buildEdge(_c[v1], _c[v2]));			
			M[_c[v1]].push_back(F.back());
		}
		
		E.push_back(F);
		
		nFaces++;
		if(faces == NULL)
		{
			lastFace = buildFace(F);
			faces    = lastFace;
		}
		else
		{			
			lastFace->next = buildFace(F);
			lastFace       = lastFace->next;
		}
	}
	
	for(uint i(0); i < _c.size(); i++)
	{
		_c[i]->id = i;
		
		nVertices++;
		if(vertices == NULL)
		{
			lastVertex = _c[i];
			vertices   = lastVertex;
		}
		else
		{
			lastVertex->next = _c[i];
			lastVertex       = lastVertex->next;
		}
	}

	for(uint i(0); i < E.size(); i++)
	{
		for(uint j(0); j < E[i].size(); j++)
		{
			nEdges++;
			if(edges == NULL)
			{
				lastEdge = E[i][j];
				edges    = lastEdge;
			}
			else
			{
				lastEdge->next = E[i][j];
				lastEdge       = lastEdge->next;
			}
		}
	}
	
	lastVertex->next = NULL;
	lastFace->next   = NULL;
	lastEdge->next   = NULL;
	
	
	heEdge * twin;
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		if(ptr->half->pair == NULL)
		{
			twin = findPairEdge(ptr->half, M[ptr->half->head]);
			
			if(twin != NULL)
			{
				ptr->half->pair  = twin->half;
				twin->half->pair = ptr->half;
			}
		}
	}
	
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		if(ptr->half->pair != NULL)
			ptr->half->tail->ngbr.push_back(ptr->half->head);
		else
		{
			ptr->half->tail->ngbr.push_back(ptr->half->head);
			ptr->half->head->ngbr.push_back(ptr->half->tail);
		}			
	}
	
	type = MeshOther;
	if(min == max)
	{
		if(min == 3)
			type = MeshTriangulated;
		
		if(min == 4)
			type = MeshQuadrangulated;		
	}
	
	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 viadage 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;	
}


// 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)
	{
		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()
{
	////////////////
	return;
	////////////////
	
	// 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()
{
	vector<heVertex *> v;
	vector<vector<uint> > f;
	uint v1, v2, v3;
	
	if(type == MeshTriangulated)
		return;
	
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		v.push_back(new heVertex(ptr->coord));
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		vector<uint> current;
		
		heHalfEdge * he = ptr->edge;
		
		v1 = he->tail->id;
		he = he->next;		
		current.push_back(v1);
		
		if(he)
		{
			v2 = he->tail->id;
			he = he->next;
			current.push_back(v2);
			
			if(he)
			{
				v3 = he->tail->id;
				he = he->next;
				current.push_back(v3);

				f.push_back(current);
				do
				{
					current.clear();
					
					v2 = v3;
					v3 = he->tail->id;
					
					current.push_back(v1);
					current.push_back(v2);
					current.push_back(v3);
					
					f.push_back(current);					
					he = he->next;					
				}
				while(he != ptr->edge);
			}
			else
				f.push_back(current);
		}
		else
			f.push_back(current);
	}
	
	buildMesh(v, f);
}


// 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;
		
		he = ptr->edge;		
		// parcours de chaque sommet de la face
		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() const
{	
	int primitive;
	
	switch(type)
	{
		case MeshTriangulated :
			primitive = GL_TRIANGLES;
			break;
		
		case MeshQuadrangulated :
			primitive = GL_QUADS;
			break;
		
		default : 
			primitive = GL_POLYGON;
	}
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		glBegin(primitive);
		//glNormal3fv(ptr->normal);

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


// methode qui permet de subdiviser un maillage par la methode de Loop
//
// subdivise le maillage en creant un point au milieu de chaques aretes, ajuste par la suite
//
void heMesh :: subLoop()
{
	heHalfEdge * he;
	
	if(type != MeshTriangulated)
		return;	
		
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		ptr->newpoint = false;
	
	// ajout des nouveaux points
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		he = ptr->edge;
		do
		{
			// si l'arete n'a pas de jumelle (arete de bord), on subdiviser
			// si l'arete suivante n'a pas de jumelle, on 
			if((!he->next->pair) || (he->next->pair->next->pair != he))
			{
				heVertex * mid;
				heEdge	 * edge;
				
				mid = new heVertex((he->tail->coord + he->head->coord) / 2.0);
				mid->newpoint = true;	
				
				// ajout du point
				if(vertices == NULL)
				{
					lastVertex = mid;
					vertices   = mid;
				}
				else
				{			
					lastVertex->next = mid;
					lastVertex       = lastVertex->next;
				}
				
				edge       = new heEdge();
				edge->half = new heHalfEdge();
				
				mid->edge = edge->half;
				
				// link des points
				edge->half->head = he->head;
				edge->half->tail = mid;			
				he->head		 = mid;
				
				// link des aretes
				edge->half->prev = he;
				edge->half->next = he->next;
				he->next->prev	 = edge->half;
				he->next 		 = edge->half;	
				
				// link des faces et de l'arete jumelle
				edge->half->pair = he->pair;			
				edge->half->face = he->face;
				
				if(edges == NULL)
				{
					lastEdge = edge;
					edges	 = edge;
				}
				else
				{			
					lastEdge->next = edge;
					lastEdge   	   = lastEdge->next;
				}
				
				// split de l'arete jumelle
				if(he->pair != NULL)
				{					
					heEdge * twin;
					
					he->pair->pair = edge->half;
					
					twin       = new heEdge();
					twin->half = new heHalfEdge();
					
					// link des points
					twin->half->head = he->pair->head;
					twin->half->tail = mid;
					he->pair->head   = mid;
					
					// link des aretes
					twin->half->prev 	 = he->pair;
					twin->half->next 	 = he->pair->next;
					he->pair->next->prev = twin->half;
					he->pair->next       = twin->half;
					
					// jumelage
					twin->half->pair = he;
					he->pair   		 = twin->half;
					
					// link des faces
					twin->half->face = he->face;
					
					if(edges == NULL)
					{
						lastEdge = twin;
						edges	 = twin;
					}
					else
					{			
						lastEdge->next = twin;
						lastEdge   	   = lastEdge->next;
					}
				}			
			}
			
			he = he->next->next;
		}
		while(he != ptr->edge);
	}
	
	lastVertex->next = NULL;
	lastEdge->next 	 = NULL;	
	
	// ajout des nouvelles aretes
	heFace * last = lastFace;
	for(heFace * ptr = faces; ptr && ptr != last->next; ptr = ptr->next)
	{
		heHalfEdge * origin[3];
		heFace 	   * face;
		
		// aretes d'origines
		origin[0] = ptr->edge;
		origin[1] = ptr->edge->next->next;
		origin[2] = ptr->edge->prev->prev;
		
		// pour chacune des aretes, creation des aretes internes
		for(uint i(0); i < 3; i++)
		{
			heEdge * in = new heEdge();
			in->half    = new heHalfEdge();
			
			// link des points
			in->half->tail = origin[i]->head;
			in->half->head = origin[i]->prev->tail;
			
			// link des aretes
			in->half->next 		  = origin[i]->next;
			in->half->prev 		  = origin[i];
			origin[i]->next 	  = in->half;
			origin[i]->prev->prev = in->half;
			
			// creation de la face si elle n'existe pas
			if(origin[i]->face->edge != origin[i])
			{
				face = new heFace();
				
				// link de la face
				face->edge      = origin[i];
				origin[i]->face = face;
				
				// ajout de la face
				if(faces == NULL)
				{
					lastFace = face;
					faces    = face;
				}
				else
				{			
					lastFace->next = face;
					lastFace       = lastFace->next;
				}
			}
			
			// link aretes -> faces
			in->half->face 		  = origin[i]->face;
			origin[i]->prev->face = origin[i]->face;
			
			// creation de l'arete interne inverse
			in 		 = new heEdge();
			in->half = new heHalfEdge();
			
			in->half->tail = origin[i]->next->head;
			in->half->head = origin[i]->head;
			
			// jumelage
			in->half->pair = origin[i]->next;
			origin[i]->next->pair = in->half;
			
			// ajout de l'arete
			if(edges == NULL)
			{
				lastEdge = in;
				edges    = lastEdge;
			}
			else
			{
				lastEdge->next = in;
				lastEdge       = lastEdge->next;
			}
			
			// stockage de l'arete interne cree
			origin[i] = in->half;
		}
		
		// creation de la face interieure
		face = new heFace();
		face->edge = origin[0];
		
		for(uint i(0); i < 3; i++)
		{
			origin[i]->face = face;
			
			origin[i]->next = origin[(i + 1) % 3];
			origin[i]->prev = origin[(i - 1) % 3];
		}
		
		if(faces == NULL)
		{
			lastFace = face;
			faces    = face;
		}
		else
		{			
			lastFace->next = face;
			lastFace       = lastFace->next;
		}
	}
	
	lastFace->next = NULL;
}


// 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;
}