// Dimitri Kudelski (Master SIS 2 Pro - Imagerie Numerique)
// Projet de Modelisation Geometrique : surfaces de subdivision
//
// Derniere modification : 08 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() : type(MeshOther)
{
	vertices   = NULL;
	lastVertex = NULL;
	
	edges    = NULL;
	lastEdge = NULL;
	
	faces    = NULL;
	lastFace = NULL;
}


// 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;
	
	load(_filename);
}


// constructeur par copie
//
// recopie le maillage mesh
//
heMesh :: heMesh(const heMesh & _mesh)
{
	vector<heVertex *> v;
	vector<vector<uint> > f;
	heHalfEdge * he;
	
	/*for(list<heVertex *>::const_iterator it = _mesh.vertices.begin(); it != _mesh.vertices.end(); it++)
	{
		v.push_back(new heVertex((*it)->coord));
	}*/
	for(heVertex * ptr = _mesh.vertices; ptr; ptr = ptr->next)
		v.push_back(new heVertex(ptr->coord));
	
	/*for(list<heFace *>::const_iterator it = _mesh.faces.begin(); it != _mesh.faces.end(); it++)
	{
		vector<uint> current;
		e = (*it)->edge;
		
		do
		{
			current.push_back(e->tail->id);
			e = e->next;					
		}
		while(e != (*it)->edge);
		
		f.push_back(current);		
	}*/
	for(heFace * ptr = _mesh.faces; ptr; ptr = ptr->next)
	{
		vector<uint> current;
		he = ptr->edge;
		
		do
		{
			current.push_back(he->tail->id);
			he = he->next;					
		}
		while(he != ptr->edge);
		
		f.push_back(current);		
	}
	
	buildMesh(v, f);
}


// 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 vector<*/heEdge */*> &*/ _l)
{
	/*if(_l.size() < _he->head->id)
		return NULL;
	*/
	for(heEdge * ptr = _l/*[_he->head->id]*/; ptr; ptr = ptr->next)
	{
		if(ptr->half->head == _he->tail && ptr->half->tail == _he->head)
			return ptr;
	}
	
	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;
	//vector<heEdge *>     	  Eid(_c.size());
	map<heVertex *, vector<heEdge *> > M;
	heEdge * ptrE;
	
	clear();
	
	if(_c.size() == 0 || _f.size() == 0)
		return false;	
	
	min = max = _f[0].size();
	
	//for(uint i(0); i < _c.size(); i++)
	//	Eid[i] = NULL;
	
	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());
/*
			ptrE       = F.back();
			ptrE->next = Eid[v1];
			Eid[v1]	   = ptrE;*/
		}
		
		E.push_back(F);
		//faces.push_back(buildFace(F));
		
		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;
		vertices.push_back(_c[i]);
	}*/
	for(uint i(0); i < _c.size(); i++)
	{
		_c[i]->id = i;
		
		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++)			
			edges.push_back(E[i][j]);
	}*/

	for(uint i(0); i < E.size(); i++)
	{
		for(uint j(0); j < E[i].size(); j++)
		{
			if(edges == NULL)
			{
				lastEdge = E[i][j];
				edges    = lastEdge;
			}
			else
			{
				lastEdge->next = E[i][j];
				lastEdge       = lastEdge->next;
			}			
			//edges.push_back(E[i][j]);
		}
	}
	
	lastVertex->next = NULL;
	lastFace->next   = NULL;
	lastEdge->next   = NULL;
	
	
	heEdge * twin;
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		if(ptr->half->pair == NULL)
		{
			for(uint i(0); i < M[ptr->half->head].size(); i++)
			{
				twin = M[ptr->half->head][i];
				
				if(twin->half->pair == NULL)
				{				
					if(ptr->half->head == twin->half->tail && //_he->tail && ptr->half->tail == _he->head)
						ptr->half->tail == twin->half->head)
					{
						ptr->half->pair  = twin->half;
						twin->half->pair = ptr->half;
					}
				}
			}
		}
	}
	/*
	heEdge * twin;
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		if(ptr->half->pair == NULL)
		{
			twin = findPairEdge(ptr->half, Eid[ptr->half->head->id]);
			
			if(twin != NULL)
			{
				ptr->half->pair  = twin->half;
				twin->half->pair = ptr->half;
			}
		}
	}*/
	/*for(list<heEdge *>::iterator it = edges.begin(); it != edges.end(); it++)
	{	
		if((*it)->pair == NULL)
		{
			twin = findPairEdge(*it, Eid);
		
			if(twin != NULL)
			{
				(*it)->pair = twin;
				twin->pair  = (*it);
			}
		}
	}*/
	
	type = MeshOther;
	if(min == max)
	{
		if(min == 3)
			type = MeshTriangulated;
		
		if(min == 4)
			type = MeshQuadrangulated;		
	}
	/*
	for(heEdge * ptr = edges; ptr; ptr = ptr->next)
	{
		cout << "[" << ptr->half << "] : (" << ptr->half->tail->id << ", " << ptr->half->head->id << ") (twin : " << ptr->half->pair << ")" << endl;
	}*/
	
	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() 
{
	vertices = lastVertex = NULL;
	faces = lastFace = NULL;
	edges = lastEdge = NULL;
	// destruction des sommets
	//for(list<heVertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
	//	delete *it;
	
	// destruction des aretes
	//for(list<heEdge *>::iterator it = edges.begin(); it != edges.end(); it++)
	//	delete *it;
	
	// destruction des faces
	//for(list<heFace *>::iterator it = faces.begin(); it != faces.end(); it++)
	//	delete *it;
	
	// vidage des listes
	//vertices.clear();
	//edges.clear();
	//faces.clear();	
}


// methode d'enregistrement du maillage
//
// enregistre le maillage dans le fichier passe en parametre
//
bool heMesh :: save(const char * _filename) const
{
	ofstream file(_filename);
	heHalfEdge * he, * begin;
	
	if(!file)
	{
		cerr << "[heMesh::save] Erreur. Le maillage ne peut pas etre enregistre dans le fichier \"" << _filename << "\"." << endl;
		return false;
	}
	/*
	for(list<heVertex *>::const_iterator it = vertices.begin(); it != vertices.end(); it++)
	{
		file << "v " << (*it)->coord.x << " " << (*it)->coord.y << " " << (*it)->coord.z << "\n";
	}*/
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		file << "v " << ptr->coord.x << " " << ptr->coord.y << " " << ptr->coord.z << "\n";
	
	/*for(list<heFace *>::const_iterator it = faces.begin(); it != faces.end(); it++)
	{
		begin = (*it)->edge;
		e     = begin;
		
		file << "f";
		do
		{
			file << " " << (e->tail->id + 1);
			e = e->next;
		}
		while(e != begin);
		file << "\n";
	}*/
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		begin = ptr->edge;
		he    = begin;
		
		file << "f";
		do
		{
			file << " " << (he->tail->id + 1);
			he = he->next;
		}
		while(he != begin);
		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.size() == 0)*/
	if(vertices == NULL)
		return;
	
	// recherche du min et max
	//min = max = (*vertices.begin())->coord;
	min = max = vertices->coord;
	/*for(list<heVertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
	{
		if((*it)->coord.x > max.x)
			max.x = (*it)->coord.x;
		
		if((*it)->coord.y > max.y)
			max.y = (*it)->coord.y;
		
		if((*it)->coord.z > max.z)
			max.z = (*it)->coord.z;
		
		if((*it)->coord.x < min.x)
			min.x = (*it)->coord.x;
		
		if((*it)->coord.y < min.y)
			min.y = (*it)->coord.y;
		
		if((*it)->coord.z < min.z)
			min.z = (*it)->coord.z;
	}*/
	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(list<heVertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
	{
		(*it)->coord -= center;		
		(*it)->coord *= scale;
	}*/
	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;
	heHalfEdge * he;
	
	if(type == MeshTriangulated)
		return;
	
	/*for(list<heVertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
	{
		v.push_back(new heVertex((*it)->coord));
	}*/
	for(heVertex * ptr = vertices; ptr; ptr = ptr->next)
		v.push_back(new heVertex(ptr->coord));
	
	/*for(list<heFace *>::iterator it = faces.begin(); it != faces.end(); it++)
	{
		vector<uint> current;
		
		e = (*it)->edge;
		
		v1 = e->tail->id;
		e  = e->next;		
		current.push_back(v1);
		
		if(e)
		{
			v2 = e->tail->id;
			e  = e->next;
			current.push_back(v2);
			
			if(e)
			{
				v3 = e->tail->id;
				e  = e->next;
				current.push_back(v3);

				f.push_back(current);
				do
				{
					current.clear();
					
					v2 = v3;
					v3 = e->tail->id;
					
					current.push_back(v1);
					current.push_back(v2);
					current.push_back(v3);
					
					f.push_back(current);					
					e = e->next;					
				}
				while(e != (*it)->edge);
			}
			else
				f.push_back(current);
		}
		else
			f.push_back(current);
	}*/
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		vector<uint> current;
		
		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
	list<int>::iterator it;
	vec3 v1, v2, n;
	heHalfEdge * he;
	
	// parcours de toutes les faces
	/*for(list<heFace *>::iterator it = faces.begin(); it != faces.end(); it++)
	{
		e = (*it)->edge;
		n = vec3 :: zero;
		
		// parcours de chaque sommet de la face
		do
		{
			v1 = e->tail->coord;
			v2 = e->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);

			e = e->next;
		}
		while(e != (*it)->edge);
		
		// normalisation et affectation
		n.normalize();
		(*it)->normal = n;
		
		e = (*it)->edge;		
		// parcours de chaque sommet de la face
		do
		{
			e->tail->normal += n;			
			e = e->next;
		}
		while(e != (*it)->edge);
	}*/
	
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		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(list<heVertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
	{
		// normalisation
		(*it)->normal.normalize();
	}*/
	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
{	
	heHalfEdge * begin, * ptrE;
	int primitive;
	
	switch(type)
	{
		case MeshTriangulated :
			primitive = GL_TRIANGLES;
			break;
		
		case MeshQuadrangulated :
			primitive = GL_QUADS;
			break;
		
		default : 
			primitive = GL_POLYGON;
	}
	
	
	/*for(list<heFace *>::const_iterator it = faces.begin(); it != faces.end(); it++)
	{
		glBegin(primitive);

		begin = (*it)->edge;
		ptr   = begin;
		
		do
		{
			glNormal3fv(ptr->tail->normal);
			glVertex3fv(ptr->tail->coord);				
			ptr = ptr->next;
		}
		while(ptr != begin);
		
		glEnd();
	}*/
	for(heFace * ptr = faces; ptr; ptr = ptr->next)
	{
		glBegin(primitive);

		begin = ptr->edge;
		ptrE  = begin;
		
		do
		{
			glNormal3fv(ptrE->tail->normal);
			glVertex3fv(ptrE->tail->coord);				
			ptrE = ptrE->next;
		}
		while(ptrE != begin);
		
		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()
{
	if(type != MeshTriangulated)
		return;
	
	
}


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


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


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


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