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