houlala

// 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(){	// 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 && he != ptr->edge)		{			v2 = he->tail->id;			he = he->next;			current.push_back(v2);						if(he && he != ptr->edge)			{				v3 = he->tail->id;				he = he->next;				current.push_back(v3);				f.push_back(current);				if(he && he != ptr->edge)				{					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();	}}float beta(int _n){	return 5 / 4.0 - pow(3 + 2 * cos(2 * M_PI / _n), 2) / 32.0;}float alpha(int _n){	return (_n * (1.0 - beta(_n))) / beta(_n);}// 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->ngbr.clear();		// 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 = new heVertex((he->tail->coord + he->head->coord) / 2.0);				heEdge	 * edge;								// 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();						// ajout de l'arete			if(edges == NULL)			{				lastEdge = in;				edges    = lastEdge;			}			else			{				lastEdge->next = in;				lastEdge       = lastEdge->next;			}						// link des points			in->half->tail = origin[i]->head;			in->half->head = origin[i]->prev->tail;						// link des aretes			origin[i]->next 	  = in->half;			origin[i]->prev->prev = in->half;			in->half->prev 		  = origin[i];						in->half->next 		  = origin[i]->prev;						// 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;		}	}		lastVertex->next = NULL;	lastEdge->next 	 = NULL;		lastFace->next   = NULL;		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);		}				}}// 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;}