houlala

// Dimitri Kudelski (Master SIS 2 Pro - Imagerie Numerique)// Projet de Modelisation Geometrique : surfaces de subdivision//// Derniere modification : 10 Octobre 2007//// classe heSubdivider // he_subdivider.cpp// gestionnaire de subdivisions (undo/redo, etc...)#include <he_subdivider.h>#include <math.h>using namespace std;// constructeur par defaut//// construit le gestionnaire avec les valeurs par defaut//heSubdivider :: heSubdivider() : currentMesh(NULL){}// methode de nettoyage de liste :)//// supprime toute la fin de la liste pour ne pas bugger lors d'un redo//void heSubdivider :: clearEndList(){	list<heMesh *>::iterator it = currentMesh;	meshList.erase(++it, meshList.end());}heMesh * heSubdivider :: subLoop(heMesh * _mesh){	heMesh * result;	// variable de parcours	heHalfEdge * he;		// variables pour le triangle :)	heHalfEdge * he1, * he2, * he3;	vec3 mid;		// coefficient de positionnement	float beta;	int boundaries;		// tableaux pour tenir les nouvelles creations	heVertex * new_vertices[3];	heVertex * new_edges   [3];		if(_mesh->type != heMesh::MeshTriangulated)		return NULL;		result = new heMesh();		// augmentation du niveau de subdivision	result->level = _mesh->level + 1;		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		ptr->half->data = NULL;	}		for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		boundaries = 0;		he1 = NULL;		he2 = NULL;				ptr->data	 = NULL;		ptr->valence = ptr->edges.size();		ptr->average = vec3::zero;				for(list<heHalfEdge *>::iterator it = ptr->edges.begin(); it != ptr->edges.end(); it++)		{			if((*it)->twin == NULL)			{				boundaries++;								if(he1 == NULL)					he1 = *it;				else					he2 = *it;			}						if((*it)->head != ptr)				ptr->average += (*it)->head->coord;			else				ptr->average += (*it)->tail->coord;		}				if(boundaries == 0)		{			beta = (0.625 - pow(0.375 + 0.25 * cos(2.0 * M_PI / ptr->valence), 2)) / ptr->valence;			mid  = ptr->coord * (1.0 - ptr->valence * beta) + ptr->average * beta;		}		else		{			mid = vec3::zero;						if(boundaries != 2)			{				beta = (0.625 - pow(0.375 + 0.25 * cos(2.0 * M_PI / ptr->valence), 2)) / ptr->valence;				mid  = ptr->coord * (1.0 - ptr->valence * beta) + ptr->average * beta;			}			else			{				if(he1->tail != ptr)					mid += he1->tail->coord;				else					mid += he1->head->coord;								if(he2->tail != ptr)					mid += he2->tail->coord;				else					mid += he2->head->coord;								mid += ptr->coord * 6.0;				mid /= 8.0;			}		}				ptr->data = result->buildVertex(mid);	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		he = ptr->edge;		do		{			he1 = he;			he2 = he1->next;						if(he1->data == NULL)			{				mid = (he1->tail->coord + he1->head->coord) * 0.5;								if(he1->twin != NULL)					mid = (he1->tail->coord + he1->head->coord) * 0.375 + (he2->head->coord + he1->twin->next->head->coord) * 0.125;								he1->data = result->buildVertex(mid);								if(he1->twin != NULL)					he1->twin->data = he1->data;			}						he = he->next;		}		while(he != ptr->edge);	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{				uint i = 0;		he = ptr->edge;		do		{			new_vertices[i] = he->tail->data;			new_edges   [i] = he->data;						i++;			he = he->next;		}		while(he != ptr->edge);				he1 = result->buildEdge(new_vertices[0], new_edges[0]   )->half;		he2 = result->buildEdge(new_edges[0],    new_edges[2]   )->half;		he3 = result->buildEdge(new_edges[2],    new_vertices[0])->half;				result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he1);				result->buildFace(he1);				he1 = result->buildEdge(new_vertices[1], new_edges[1]   )->half;		he2 = result->buildEdge(new_edges[1],    new_edges[0]   )->half;		he3 = result->buildEdge(new_edges[0],    new_vertices[1])->half;				result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he1);				result->buildFace(he1);				he1 = result->buildEdge(new_vertices[2], new_edges[2]   )->half;		he2 = result->buildEdge(new_edges[2],    new_edges[1]   )->half;		he3 = result->buildEdge(new_edges[1],    new_vertices[2])->half;				result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he1);				result->buildFace(he1);				he1 = result->buildEdge(new_edges[0], new_edges[1])->half;		he2 = result->buildEdge(new_edges[1], new_edges[2])->half;		he3 = result->buildEdge(new_edges[2], new_edges[0])->half;				result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he1);				result->buildFace(he1);	}		result->type = heMesh::MeshTriangulated;		result->updateVerticesInfo();	return result;}heMesh * heSubdivider :: subCatmullClark(heMesh * _mesh){	heMesh * result = new heMesh();		vec3 mid;	uint n;	heHalfEdge * he, * he1, * he2, * he3, * he4;	float beta;	bool twin;		result->level = _mesh->level + 1;		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		ptr->half->data = NULL;	}		for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		ptr->data = NULL;		ptr->valence = ptr->edges.size();	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		n   = 0;		mid = vec3::zero;		he  = ptr->edge;		do		{			n++;			mid += he->tail->coord;						he = he->next;		}		while(he != ptr->edge);				mid /= n;		ptr->data = result->buildVertex(mid);	}		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		he  = ptr->half;				if(he->data == NULL)		{			mid = he->tail->coord + he->head->coord;						if(he->twin != NULL)			{				mid += he->face->data->coord + he->twin->face->data->coord;				mid *= 0.25;			}			else				mid *= 0.5;						he->data = result->buildVertex(mid);						if(he->twin != NULL)				he->twin->data = he->data;		}	}		vec3 midE, midF;	for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		twin = true;		n = ptr->valence;		mid  = vec3::zero;		midE = vec3::zero;		midF = vec3::zero;				if(n > 2)		{			list<heFace *> faceList;						beta = 1.0 / (n * n);						he1 = he2 = NULL;			for(list<heHalfEdge *>::iterator it = ptr->edges.begin(); it != ptr->edges.end(); it++)			{				if((*it)->twin == NULL)				{					twin = false;					if(he1 == NULL)						he1 = *it;					else						he2 = *it;				}								if((*it)->tail != ptr)					midE += (*it)->tail->coord;				else					midE += (*it)->head->coord;								if(find(faceList.begin(), faceList.end(), (*it)->face) == faceList.end())					faceList.push_back((*it)->face);			}						for(list<heFace *>::iterator it = faceList.begin(); it != faceList.end(); it++)				midF += (*it)->data->coord;						midE *= beta;			midF *= beta;			if(twin == true)				mid = midE + midF + ptr->coord * (n - 2.0) / n;			else			{				if(he1 && he2)				{					mid = ptr->coord * 0.75;										if(he1->tail != ptr)						mid += he1->tail->coord * 0.125;					else						mid += he1->head->coord * 0.125;										if(he2->tail != ptr)						mid += he2->tail->coord * 0.125;					else						mid += he2->head->coord * 0.125;				}				else					mid = ptr->coord;			}		}		else		{			if(n == 2)			{								he1 = ptr->edges.front();				he2 = ptr->edges.back();								if(he1->tail != ptr)					midE += he1->tail->coord;				else					midE += he1->head->coord;								if(he2->tail != ptr)					midE += he2->tail->coord;				else					midE += he2->head->coord;								mid = ptr->coord * 0.75 + midE * 0.125;			}			else			{				mid = ptr->coord;			}		}				ptr->data = result->buildVertex(mid);	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		vector<heVertex *> new_vert;		vector<heVertex *> new_edge;				he = ptr->edge;		do		{			new_vert.push_back(he->tail->data);			new_edge.push_back(he->data);						he = he->next;		}		while(he != ptr->edge);				n = new_vert.size() - 1;		for(uint i(0); i < n; i++)		{			he1 = result->buildEdge(ptr->data, new_edge[i])->half;			he2 = result->buildEdge(new_edge[i], new_vert[i+1])->half;			he3 = result->buildEdge(new_vert[i+1], new_edge[i+1])->half;			he4 = result->buildEdge(new_edge[i+1], ptr->data)->half;			result->linkHalfEdges(he1, he2);			result->linkHalfEdges(he2, he3);			result->linkHalfEdges(he3, he4);			result->linkHalfEdges(he4, he1);						result->buildFace(he1);		}				he1 = result->buildEdge(ptr->data, new_edge[n])->half;		he2 = result->buildEdge(new_edge[n], new_vert[0])->half;		he3 = result->buildEdge(new_vert[0], new_edge[0])->half;		he4 = result->buildEdge(new_edge[0], ptr->data)->half;		result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he4);		result->linkHalfEdges(he4, he1);				result->buildFace(he1);	}		result->updateVerticesInfo();		return result;}heMesh * heSubdivider :: subDooSabin(heMesh * _mesh){	heMesh * result = new heMesh();		vec3 mid;	uint i, n;	heHalfEdge * he, * hebis, * he1, * he2, * new_edges[3];	bool twin;		result->level = _mesh->level + 1;		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		ptr->half->data = NULL;		ptr->half->mark = false;	}		for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		ptr->data 	 = NULL;		ptr->mark 	 = false;		ptr->valence = ptr->edges.size();	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		n   = 0;		mid = vec3::zero;				he  = ptr->edge;		do		{			n++;			he = he->next;		}		while(he != ptr->edge);				he = ptr->edge;		do		{			if(he->twin != NULL)			{				mid = he->tail->coord * (0.25 + 5.0 / (4.0 * n));				i   = 1;								hebis = he->next;				do				{					mid += hebis->tail->coord * (3.0 + 2.0 * cos(2.0 * i * M_PI / n)) / (4.0 * n);					i++;										hebis = hebis->next;				}				while(hebis != he);			}			else			{				he1 = he2 = NULL;				for(list<heHalfEdge *>::iterator it = he->tail->edges.begin(); it != he->tail->edges.end(); it++)				{					if((*it)->twin == NULL)					{						twin = false;						if(he1 == NULL)							he1 = *it;						else							he2 = *it;					}				}								mid = vec3::zero;				if(he1->tail != he->tail)					mid += he1->tail->coord * 0.5;				else					mid += he1->head->coord * 0.5;								if(he2->tail != he->tail)					mid += he2->tail->coord * 0.5;				else					mid += he2->head->coord * 0.5;								//mid = he->tail->coord * 0.75 + he->head->coord * 0.25;			}						he->data = result->buildVertex(mid);			he = he->next;		}		while(he != ptr->edge);	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		he = ptr->edge;				new_edges[0] = new_edges[2] = result->buildEdge(he->data, he->next->data)->half;		he = he->next;		do		{			new_edges[1] = new_edges[2];			new_edges[2] = result->buildEdge(he->data, he->next->data)->half;						result->linkHalfEdges(new_edges[1], new_edges[2]);						he = he->next;		}		while(he != ptr->edge);				result->linkHalfEdges(new_edges[2], new_edges[0]);		result->buildFace(new_edges[0]);	}		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		he = ptr->half;				if(he->twin != NULL && he->twin->mark == false)		{			he->mark 	   = true;			he->twin->mark = true;						new_edges[0] = new_edges[1] = result->buildEdge(he->next->data, he->data)->half;			new_edges[2] = result->buildEdge(he->data, he->twin->next->data)->half;			result->linkHalfEdges(new_edges[1], new_edges[2]);						new_edges[1] = result->buildEdge(he->twin->next->data, he->twin->data)->half;			result->linkHalfEdges(new_edges[2], new_edges[1]);						new_edges[2] = result->buildEdge(he->twin->data, he->next->data)->half;			result->linkHalfEdges(new_edges[1], new_edges[2]);						result->linkHalfEdges(new_edges[2], new_edges[0]);			result->buildFace(new_edges[0]);		}	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		he = ptr->edge;				do		{			if(he->tail->mark == false)			{				twin      	   = true;				he->tail->mark = true;							hebis = he;				do				{					if(hebis->twin == NULL)						twin = false;					else						hebis = hebis->twin->next;				}				while(hebis != he && twin == true);								if(twin == true)				{					hebis = he;										new_edges[0] = new_edges[2] = result->buildEdge(hebis->data, hebis->prev->twin->data)->half;					do					{						hebis = hebis->prev->twin;						new_edges[1] = new_edges[2];																		if(hebis == he)						{							new_edges[2] = new_edges[1];						}						else						{							new_edges[2] = result->buildEdge(hebis->data, hebis->prev->twin->data)->half;							result->linkHalfEdges(new_edges[1], new_edges[2]);						}					}					while(hebis != he);										result->linkHalfEdges(new_edges[2], new_edges[0]);										hebis = new_edges[0];					result->buildFace(new_edges[0]);				}			}						he = he->next;		}		while(he != ptr->edge);	}		result->updateVerticesInfo();	return result;}heMesh * heSubdivider :: subMidEdge(heMesh * _mesh){	heMesh * result = new heMesh();		vec3 mid;	uint n;	heHalfEdge * he, * he1, * he2, * he3, * he4, * new_edges[4];		if(_mesh->type != heMesh::MeshQuadrangulated)		return NULL;		result->level = _mesh->level + 1;		for(heEdge * ptr = _mesh->edges; ptr; ptr = ptr->next)	{		ptr->half->data = NULL;	}		for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		ptr->data = NULL;		ptr->valence = ptr->edges.size();	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		n   = 0;		mid = vec3::zero;				he  = ptr->edge;		do		{			mid = he->tail->coord * 2.0 + (he->head->coord + he->prev->tail->coord);			mid /= 4.0;						he->data = result->buildVertex(mid);			he = he->next;		}		while(he != ptr->edge);	}		for(heFace * ptr = _mesh->faces; ptr; ptr = ptr->next)	{		new_edges[0] = he;		for(uint i(1); i < 4; i++)			new_edges[i] = new_edges[i-1]->next;				he1 = result->buildEdge(new_edges[1]->data, new_edges[0]->data)->half;		he2 = result->buildEdge(new_edges[2]->data, new_edges[1]->data)->half;		he3 = result->buildEdge(new_edges[3]->data, new_edges[2]->data)->half;		he4 = result->buildEdge(new_edges[0]->data, new_edges[3]->data)->half;				result->linkHalfEdges(he1, he2);		result->linkHalfEdges(he2, he3);		result->linkHalfEdges(he3, he4);		result->linkHalfEdges(he4, he1);				result->buildFace(he1);				he = ptr->edge;		do		{			new_edges[0] = he;			for(uint i(1); i < 4; i++)				new_edges[i] = new_edges[i-1]->next;					if(new_edges[0]->twin != NULL)			{				new_edges[2] = new_edges[0]->twin;				new_edges[3] = new_edges[0]->twin->next;			}						he1 = result->buildEdge(new_edges[1]->data, new_edges[0]->data)->half;			he2 = result->buildEdge(new_edges[2]->data, new_edges[1]->data)->half;			he3 = result->buildEdge(new_edges[3]->data, new_edges[2]->data)->half;			he4 = result->buildEdge(new_edges[0]->data, new_edges[3]->data)->half;						result->linkHalfEdges(he1, he2);			result->linkHalfEdges(he2, he3);			result->linkHalfEdges(he3, he4);			result->linkHalfEdges(he4, he1);						result->buildFace(he1);						he = he->next;		}		while(he != ptr->edge);	}		for(heVertex * ptr = _mesh->vertices; ptr; ptr = ptr->next)	{		bool twin = true;		for(list<heHalfEdge *>::iterator it = ptr->edges.begin(); it != ptr->edges.end(); it++)			if((*it)->twin == NULL)				twin = false;					if(twin == true)		{			uint n = 0;			heHalfEdge * ptr_edges[4];						he1 = ptr->edges.front();			if(he1->tail != ptr)				he1 = he1->twin;						he = he1;			do			{				new_edges[n++] = he;				he = he->twin->next;			}			while(he != he1);									for(uint i(0); i < n; i++)				ptr_edges[i] = result->buildEdge(new_edges[(i+1)%n]->data, new_edges[i]->data)->half;						for(uint i(0); i < n; i++)				result->linkHalfEdges(ptr_edges[i], ptr_edges[(i+1)%n]);						result->buildFace(ptr_edges[0]);		}	}		result->updateVerticesInfo();	return result;}// methode de chargement d'un maillage et d'ajout a la liste//// charge un maillage et l'ajoute dans la liste des maillages//bool heSubdivider :: load(const char * _filename){	for(uint i(0); i < meshList.size(); i++)		meshList.clear();		meshList.clear();	meshList.push_back(new heMesh());		if(meshList.size() == 1)		currentMesh = meshList.begin();	else		currentMesh++;		if((*currentMesh)->load(_filename) == true)	{		(*currentMesh)->unitize();		(*currentMesh)->computeNormals();				return true;	}	else		return false;}// methode d'enregistrement d'un maillage//// enregistre le maillage courant//bool heSubdivider :: save(const char * _filename) const{	if(isLoaded())		return (*currentMesh)->save(_filename);	else		return false;}// methode de triangulation du maillage//// prend le maillage courant non-triangule et le triangule a la facon GL_TRIANGLE_FAN//void heSubdivider :: triangulate(){	if(!isLoaded())		return;		clearEndList();		meshList.push_back(new heMesh(*(*currentMesh)));	currentMesh++;		(*currentMesh)->triangulate();	(*currentMesh)->computeNormals();}// methode d'affichage du maillage courant//// affiche le maillage courant dans la liste//void heSubdivider :: display() const{	if(isLoaded())		(*currentMesh)->display();}// methode d'acces au nombre de sommets//// renvoie le nombre de sommets du maillage courant//uint heSubdivider :: getNVertices() const{	if(isLoaded())		return (*currentMesh)->getNVertices();	else		return 0;}// methode d'acces au nombre d'aretes//// renvoie le nombre d'aretes du maillage courant//uint heSubdivider :: getNEdges() const{	if(isLoaded())		return (*currentMesh)->getNEdges();	else		return 0;}// methode d'acces au nombre de faces//// renvoie le nombre de faces du maillage courant//uint heSubdivider :: getNFaces() const{	if(isLoaded())		return (*currentMesh)->getNFaces();	else		return 0;}// methode d'acces au type de maillage//// renvoie le type du maillage courant//uint heSubdivider :: getType() const{	if(isLoaded())		return (*currentMesh)->getType();	else		return 0;}// methode qui permet de connaitre l'etat du manager//// renvoie true si un maillage est charge//bool heSubdivider :: isLoaded() const{	return (meshList.size() > 0);}// methode qui permet de savoir si on peut annuler l'action//// renvoie true si c'est possible//bool heSubdivider :: isUndoable(){	return (currentMesh != meshList.begin() && meshList.size() > 0);}// methode qui permet de savoir si on peut retablir l'action annulee//// renvoie true si c'est possible//bool heSubdivider :: isRedoable(){	if(meshList.size() == 0)		return false;		currentMesh++;	if(currentMesh == meshList.end())	{		currentMesh--;		return false;	}	else	{		currentMesh--;		return true;	}}// methode qui permet d'annuler la derniere action//// annule la derniere action effectuee sur le maillage//void heSubdivider :: undo(){	if(isUndoable())		currentMesh--;}// methode qui permet de retablir la derniere action annulee//// annule l'annulation :)//void heSubdivider :: redo(){	if(isRedoable())		currentMesh++;}// 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 heSubdivider :: subdivide(heScheme _scheme){	if(!isLoaded())		return;			switch(_scheme)	{		case SubLoop :			clearEndList();						meshList.push_back(subLoop(*currentMesh));			currentMesh++;			(*currentMesh)->computeNormals();			break;				case SubCatmullClark :			clearEndList();						meshList.push_back(subCatmullClark(*currentMesh));			currentMesh++;			(*currentMesh)->computeNormals();			break;				case SubDooSabin :			clearEndList();						meshList.push_back(subDooSabin(*currentMesh));			currentMesh++;			(*currentMesh)->computeNormals();			break;				case SubMidEdge :			clearEndList();						meshList.push_back(subMidEdge(*currentMesh));			currentMesh++;			(*currentMesh)->computeNormals();			break;				default :			break;	}	}