houlala

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