/*	=====================================================================
 *	(C) 2005 Universitat Jaume I
 *	=====================================================================
 *	PROYECT:	GAME TOOLS
 *	=====================================================================
 *	CONTENT:	Make triangle strip meshes from triangle list meshes.
 *
 *
 *	@file	GeoMeshStripifier.cpp
 *	=====================================================================*/

#include "GeoMeshStripifier.h"

using namespace Geometry;
using	namespace	std;

//-------------------------------------------------------------------------
//	Private.
//-------------------------------------------------------------------------


///	stripify:	Make triangle strips for a given mesh.
int CustomStripifier::stripify (Geometry::Mesh	*geoMesh)
{
	int			oddStrip;
	int				i;
	unsigned int	j;
	int				num_vert	=	0;
	int				num_faces	=	0;
	int				num_tris    = 0;
	int				totalStripIndices;

	Geometry::SubMesh*	geoSubMesh;
	vector_int v_indices;
 
	//	Process OK.
	mError = 0;

	StripFaceAdj = NULL;

	//	Progress bar.
	float	percent;
	percent	=	float(100.0 / (geoMesh->mSubMeshCount * 10.0));

	//	For all submeshes.
	for(unsigned int k = 0; k < geoMesh->mSubMeshCount; k++)
	{
		//	Leaves submesh doesn't stripify.
		if (mSubMeshLeaves != k)
		{
			//Free structures
			v_indices.clear();
			StripFaces.clear();
			my_vector.clear();
			my_vector.push_back(v_indices);

			if (StripFaceAdj != NULL)
				free(StripFaceAdj);

			StripFaceAdj = NULL;

			for (int i=0;i<StripEdges.size();i++)
				StripEdges[i].clear();

			StripEdges.clear();

			if (StripArray != NULL)
			{
				for (int i=0;i<60;i++)
					StripArray[i].clear();

			}

			for (int i=0;i<StripVertices.size();i++)
				StripVertices[i].clear();

			StripVertices.clear();

			//Let's start striping
			num_tiras	=	0;

			//	Actual submesh.
			geoSubMesh	=	&geoMesh->mSubMesh[k];

			//	Mesh type.
			geoSubMesh->mType	=	GEO_TRIANGLE_STRIPS;

			num_vert	=	int(geoSubMesh->mVertexBuffer->mVertexCount);
			num_faces	=	int(geoSubMesh->mIndexCount / 3);
			num_tris	=	num_faces;

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent*2);
			}

			//	Load the object into memory.
			ReadData(geoSubMesh, num_faces, num_vert);

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			FindAdjacencies(num_faces,num_vert);

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			//	If the mesh is not manifold.
			if (mError)
			{
				return	0;
			}

			StoreAdjacencies(num_faces);

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			Stripification();

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			num_vert	=	num_tiras;

			totalStripIndices	=	0;

			geoSubMesh->mStripCount	=	num_tiras;

			//	Memory for the array of strips beginnigs
			geoSubMesh->mStrip = (Index**) malloc(sizeof(Index*) * geoSubMesh->mStripCount);

			// The first one will be different
			v_indices	=	my_vector[1];

			//	Number of vertices of a strip odd or even.
			if(v_indices.size() % 2)
			{
				oddStrip	= true;
			}
			else
			{
				oddStrip	=	false;
			}

			//	Obtiene el total de indices de la primera strip.
			geoSubMesh->mIndexCount	=	v_indices.size();

			//	Calculate the Index Count.
			for (i = 2; i <= num_tiras; i++)
			{
				v_indices								=		my_vector[i];
				geoSubMesh->mIndexCount	+=	v_indices.size() + 2;

				//	Insert a new vertex if the strip es odd.
				if(oddStrip)
				{
					geoSubMesh->mIndexCount++;
				}

				//	Number of vertices of a strip odd or even.
				if(v_indices.size() % 2)
					oddStrip	= true;
				else
					oddStrip	=	false;
			}

			//	Delete the actual indices.
			delete[]	geoSubMesh->mIndex;
			geoSubMesh->mIndex	=	new	Index[geoSubMesh->mIndexCount];
			//--------------------------------------------

			// First time will be different
			v_indices =	my_vector[1];

			//	Copy first strip in the index array
			for(j = 0;j < v_indices.size();j++)
			{
				geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[j];
			}

			//Assign beginning of first strip
			geoSubMesh->mStrip[0]	=	&geoSubMesh->mIndex[0];

			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}

			//	Number of vertices of a strip odd or even.
			if(v_indices.size() % 2)
			{
				oddStrip	= true;
			}
			else
			{
				oddStrip	=	false;
			}

			//For all the strips but the first one
			for(i	=	2;	i <= num_tiras;	i++)
			{
				//	initial degenerate triangle (copy last twice)
				geoSubMesh->mIndex[totalStripIndices++]	=	geoSubMesh->
					mIndex[totalStripIndices-1];

				v_indices								=	my_vector[i];

				//	initial degenerate triangle (copy first twice)
				
				geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[0];

				//	Asigna el inicio de la tira de triangulos.
				geoSubMesh->mStrip[i-1]	=	&geoSubMesh->mIndex[totalStripIndices - 1];

				//	Degenerate Triangle
				geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[0];

				//	Insert a new vertex if the strip es odd.
				if(oddStrip)
				{
					geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[0];
				}

				//	Number of vertices of a strip odd or even.
				if(v_indices.size() % 2)
				{
					oddStrip	= true;
				}
				else
				{
					oddStrip	=	false;
				}
				
				//	Copy current strip
				for(j	=	1;	j < v_indices.size();	j++)
				{
					geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[j];
				}
			}


		}
	}//	End For. SubMeshes.

	//	Updtate progress bar.
	if (mUPB)
	{
		mUPB(100.0);
	}

	return	1;
}


///	Getlower:
void CustomStripifier::GetLower (int *x, int *y)
{
  int temp;
  
  if (*y < *x)
  {
    temp	=	*x;
    *x		=	*y;
    *y		=	temp;
  }
}

///	Different:
//Return the vertex of the first triangle that is not in the second
int CustomStripifier::Different(int id1,int id2,int id3,int id4,int id5, int id6, int *x, int *y)
{
  if ((id1 != id4) && (id1 != id5) && (id1 != id6))
    {
      *x = id2;
      *y = id3;
      return id1;
    }
  if ((id2 != id4) && (id2 != id5) && (id2 != id6))
    {
      *x = id1;
      *y = id3;
      return id2;
    }
  if ((id3 != id4) && (id3 != id5) && (id3 != id6))
    {
      *x = id1;
      *y = id2;
      return id3;
    }
  
  *x = id5;
  *y = id6;

  return id4;
}

///Orient:
void CustomStripifier::Orient(int vertex1, int vertex2,int vertex3)
{ 
  int original_vertex[3];
  int vertices,index,i=0;
  int verts;

	do {  
		index = 0;
		verts=StripVertices[vertex1-1][i];
		i++;
		for (vertices = 0; vertices < 3;vertices++) {
			if (vertex1 == StripFaces[verts].array[vertices]+1 || vertex2 == StripFaces[verts].array[vertices]+1 ||
				vertex3 == StripFaces[verts].array[vertices]+1 )
					original_vertex[index++] = StripFaces[verts].array[vertices]+1;      

			if (index == 3)
			break;
		}
	if (index == 3)
		break;
	} 
	while (i< (int) StripVertices[vertex1-1].size());

	i=0;

	if (index == 3) 
		return;
  
	do {
		verts=StripVertices[vertex2-1][i];
		i++;
		index = 0;
		for (vertices = 0; vertices < 3;vertices++) {
		if (vertex1 == StripFaces[verts] .array[vertices]+1 || vertex2 == StripFaces[verts] .array[vertices]+1 ||
			vertex3 == StripFaces[verts] .array[vertices]+1 )
				original_vertex[index++] = StripFaces[verts] .array[vertices]+1;   
		if (index == 3)
			break;
		}
	}
	while (i< (int) StripVertices[vertex2-1].size());

  	if (index == 3) 
		return;

    do {    
  	  verts=StripVertices[vertex3-1][i];
      i++;
      index = 0;
      for (vertices = 0; vertices < 3;vertices++) {
		if (vertex1 == StripFaces[verts] .array[vertices]+1 || vertex2 == StripFaces[verts] .array[vertices]+1 ||
			vertex3 == StripFaces[verts] .array[vertices]+1 )
			original_vertex[index++] = StripFaces[verts] .array[vertices]+1;      

        if (index == 3)
          break;
      }
    } 
	while (i< (int) StripVertices[vertex3-1].size());
  
  if ( ( original_vertex[0] == vertex3 && original_vertex[1] == vertex2 && original_vertex[2] == vertex1   ) ||
       ( original_vertex[0] == vertex2 && original_vertex[1] == vertex1 && original_vertex[2] == vertex3   ) ||
       ( original_vertex[0] == vertex1 && original_vertex[1] == vertex3 && original_vertex[2] == vertex2   ))
			my_vector[num_tiras].push_back(vertex2-1);

}

///	AddTri:
void CustomStripifier::AddTri(int id1, int id2, int id3, int flag, int where)
{
  /*   We will save everything into a list, rather than output at once,
       as was done in the old routine. This way for future modifications
       we can change the strips later on if we want to  */
  
  if (flag == -10)
  {
	  vector_int nada;
	  my_vector.push_back(nada);

	  num_tiras++;
      Finished();
  }
  else
  {
      StoreStrip(id1, where);
      StoreStrip(id2, where);
      StoreStrip(id3, where);
      
	  lastTri[0]=id1;
	  lastTri[1]=id2;
	  lastTri[2]=id3;
  }
}

///	GoBack:
void CustomStripifier::GoBack(int face_id, int *ties,int tie)
{
  int NumAdj,next_face,x,y,z,f,i;   
  int correct=0;

  if (Strips.size() > 3)
  {
	x = Strips[0];
	y = Strips[1];
	z = Strips[2];
  }
 
  for (i=0; i<3 ; i++)
  {
		correct=0;
      
		if ( (i !=2) && (( (StripFaces[face_id].array[i] == x) && (StripFaces[face_id].array[i+1] == y)) ||
			(StripFaces[face_id].array[i] == y) && (StripFaces[face_id].array[i+1] == x)))
				correct=1;

		else if ( (i == 2) &&
			( ((StripFaces[face_id].array[0] == x) && (StripFaces[face_id].array[2]== y)) ||
				(StripFaces[face_id].array[0] == y) && (StripFaces[face_id].array[2] == x)))
				correct=1;

		if (correct)
		{
			next_face = Find_Face(face_id,x,y,&NumAdj);

			if (next_face == -1)
				break;

			for (f=0;;f++)
			{
				if (StripArray[NumAdj][f] == next_face)
				{
					lastTri[0]=z;
					lastTri[1]=y;
					lastTri[2]=x;
					StoreTri(StripArray[NumAdj][f],NumAdj,NumAdj,ties,tie,0);
					return;
				}
			}
		}
  }
}

///	StoreTri:
void CustomStripifier::StoreTri(int face_id,int NumAdj,int original_adj, int *ties, int tie, int where)
{
  static int begin = true;
  int old_face,next_face_id,next_NumAdj,e1,e2,e3,other1,other2,other3;

  e1=lastTri[0];
  e2=lastTri[1];
  e3=lastTri[2];
  
  if (NumAdj == 0)
  {
	  next_face_id = Different(StripFaces[face_id].array[0],StripFaces[face_id].array[1],
				   StripFaces[face_id].array[2],e1,e2,e3,&other1,&other2);

	  if ((e2 ==0) && (e3 == 0))
	  {
	      e2 = other1;
	      e3 = other2;
	  }
	  
	  AddTri(e2,e3,next_face_id,true, where);

	  if (StripFaceAdj[face_id].NumAdj == 0)
	    StripFaceAdj[face_id].finish = true;

	  StripArray[NumAdj].erase(find(StripArray[NumAdj].begin(), StripArray[NumAdj].end(), face_id));

	  begin = true;
  }
  else
  {
      next_face_id = UpdateAdjacencies(face_id,&next_NumAdj, &e1,&e2,ties);
	  old_face = next_face_id;
	  
  	  if (last == 1)
		  old_face=ties_array[0];
	  else
		  old_face=Prediction();
	  
	  if (next_face_id == -1)
	  {
	      StoreTri(face_id,0,NumAdj,ties,tie, where);
	      return;
	  }
	  	  
	  if (old_face != next_face_id)
	  {
	    next_face_id = old_face;
	    e3 = GetEdge(&e1,&e2,StripFaces[face_id].array,next_face_id);
	 }
	  
	  // Find the other vertex
	  if ((StripFaces[face_id].array[0]==e1)||(StripFaces[face_id].array[0]==e2))
	  {
		if ((StripFaces[face_id].array[1]==e1)||(StripFaces[face_id].array[1]==e2))
			e3=StripFaces[face_id].array[2];
		else
			e3=StripFaces[face_id].array[1];
	  }
	  else
	  {
		e3=StripFaces[face_id].array[0];
	  }
	  
	  other1=lastTri[0];
	  other2=lastTri[1];
	  other3=lastTri[2];
	  
	  if ((other1 != 0) && (other2 != 0))
	  {
		if ((e1 != other2) && (e1 != other3))
		{
			e3 = e1;
		}
	    else
		{
			if ((e2 != other2) && (e2 != other3))
			{
				e3 = e2;
			}
			else
			{
				StoreTri(face_id,0,NumAdj,ties,tie, where);
				return;
			}
		}
	      
	    if ((other2 != e1) && (other2 != e2))
		{
		  other1 = other2;
		  other2 = other3;
		}
	    else
		{
			if ((other3 != e1) && (other3 != e2))
				other1 = other3;
			else
			{
				AddTri(other1,other2,e3,begin, where);
				if (StripFaceAdj[face_id].NumAdj == NumAdj)
					StripFaceAdj[face_id].finish = true;

				StripArray[NumAdj].erase(find(StripArray[NumAdj].begin(), StripArray[NumAdj].end(), face_id));

				begin = false;
				return;
			}
	     }   
	  }
	  else 
	  {
	      other1 = e3;
	      e3 = e2;
	      other2 = e1;
	  }

	  AddTri(other1,other2,e3,begin, where);

	  if (StripFaceAdj[face_id].NumAdj == NumAdj)
			StripFaceAdj[face_id].finish = true;

	  StripArray[NumAdj].erase(find(StripArray[NumAdj].begin(), StripArray[NumAdj].end(), face_id));

	  begin = false;
	  
	  if (StripFaceAdj[next_face_id].finish)
		exit(0);

	  StoreTri(next_face_id,next_NumAdj,next_NumAdj, ties,tie, where);
	}
}

///	StoreAdjacencies:
void CustomStripifier::StoreAdjacencies(int num_faces)
{
  int i,adjacency;
  
  for (i=0;i<num_faces;i++)
  {
	adjacency=0;
		  
	adjacency += NumAdj(StripFaces[i].array[0],StripFaces[i].array[1]);
	adjacency += NumAdj(StripFaces[i].array[1],StripFaces[i].array[2]);
	adjacency += NumAdj(StripFaces[i].array[0],StripFaces[i].array[2]);
	      
    StoreAdjacency(adjacency,i);
  }
}

///	GetNumAdjacencies:
int CustomStripifier::GetNumAdjacencies(int id1, int id2, int curr_id)
{
  int size,y,count=0;
  int temp2;
  int there= false;
  
	GetLower(&id1,&id2);

	if (StripEdges[id1].empty())
		return 0;

	while (StripEdges[id1][count].array[0] != id2)
	{
		count++;
	                            
		if (count>=StripEdges[id1].size())
			return 0;
	}

	if (StripEdges[id1][count].array[2] == -1)
		return 0;

	if (curr_id != StripEdges[id1][count].array[1])
	{
		temp2 = StripEdges[id1][count].array[1];

		if (StripFaceAdj[StripEdges[id1][count].array[1]].finish) 
			return 0;
			
		size = StripFaceAdj[StripEdges[id1][count].array[1]].NumAdj;
	}
	else
	{
		temp2 = StripEdges[id1][count].array[2];

		if (StripFaceAdj[StripEdges[id1][count].array[2]].finish) 
			return 0;
			
		size = StripFaceAdj[StripEdges[id1][count].array[2]].NumAdj;
	}
    
	if (temp2<StripFaces.size())
	{
		for (y = 0; y< 3; y++)
		{
			if (y != 2)
			{
			if(((id1 == StripFaces[temp2].array[y]) && (id2 == StripFaces[temp2].array[y+1])) ||
				((id2 == StripFaces[temp2].array[y]) && (id1 == StripFaces[temp2].array[y+1])))
					there = true;
			}
			else
			{
			if(((id1 == StripFaces[temp2].array[0]) && (id2 == StripFaces[temp2].array[2])) ||
				((id2 == StripFaces[temp2].array[0]) && (id1 == StripFaces[temp2].array[2])))
					there = true;
			}
		}
	}
    
	return there;
}

///	MinimumAd:
int CustomStripifier::MinimumAd(int id)
{
  int t,x=60;

  if (StripFaceAdj[id].finish) 
	  return 60;
  
  if ( id< StripFaces.size() )
  {
	    t = GetNumAdjacencies(StripFaces[id].array[0],StripFaces[id].array[1],id);
		if (t < x)
			x = t;

		t = GetNumAdjacencies(StripFaces[id].array[1],StripFaces[id].array[2],id);
		if (t < x)
			x = t;

	    t = GetNumAdjacencies(StripFaces[id].array[0],StripFaces[id].array[2],id);
		if (t < x)
			x = t;
  }

  return x;
}

///	Find_Face:
int CustomStripifier::Find_Face(int current_face, int id1, int id2, int *NumAdj)
{
  int y,count=0;    
  int next_face;
  int there = false;
  
	GetLower(&id1,&id2);

	if (StripEdges[id1].empty())
		return -1;
  
	while (StripEdges[id1][count].array[0] != id2)
    {
		count++;
      
	    if (count>=StripEdges[id1].size())
			return -1;
    }


	if (StripEdges[id1][count].array[2] == -1)
		return -1;

	if (StripEdges[id1][count].array[2] == current_face)
		next_face =  StripEdges[id1][count].array[1];
	else 
		next_face = StripEdges[id1][count].array[2];
	
    
	if (StripFaceAdj[next_face].finish) 
	  return -1;
  
	*NumAdj = StripFaceAdj[next_face].NumAdj;
  
	if( ((id1 == StripFaces[next_face].array[0]) && (id2 == StripFaces[next_face].array[1]))
	|| ((id2 == StripFaces[next_face].array[0]) && (id1 == StripFaces[next_face].array[1])))
		there = true;

	if( ((id1 == StripFaces[next_face].array[1]) && (id2 == StripFaces[next_face].array[2]))
	|| ((id2 == StripFaces[next_face].array[1]) && (id1 == StripFaces[next_face].array[2])))
		there = true;

	if(((id1 == StripFaces[next_face].array[0]) && (id2 ==StripFaces[next_face].array[2])) ||
	((id2 == StripFaces[next_face].array[0]) && (id1 ==StripFaces[next_face].array[2])))
		there = true;
  
  if (!there)
    return -1;
  else
    return next_face;
}

///	Look_Up:
int CustomStripifier::Look_Up(int id1,int id2,int face_id)
{
  int x,count = 0;

  GetLower(&id1,&id2);
  
  if (StripEdges[id1].empty())
    return 0;
  
  while (StripEdges[id1][count].array[0] != id2)
    {
      count++;
 
	  if (count>=StripEdges[id1].size())
		return 0;
    }

  if ((StripEdges[id1][count].array[2] == face_id) || (StripEdges[id1][count].array[1] == face_id))
  {
      // The edge 
	  if (((StripFaces[face_id].array[0]==id1)||(StripFaces[face_id].array[1]==id1)||(StripFaces[face_id].array[2]==id1))&&
		 ((StripFaces[face_id].array[0]==id2)||(StripFaces[face_id].array[1]==id2)||(StripFaces[face_id].array[2]==id2)))
		return 1;
  }

  return 0;
}

///	StoreStrip:
void CustomStripifier::StoreStrip(int id, int where)
{

    if (where == 1)
	{
		Strips.push_back(id);
	}
    else
	{
		if (Strips.empty())
			Strips.push_back(id);
		else
			Strips.insert(Strips.begin(),id);
	}
 
}

///	NumAdj:
int CustomStripifier::NumAdj(int id1, int id2)
{
  int count=0;

  GetLower(&id1,&id2);
  
  while (StripEdges[id1][count].array[0] != id2)
    count++;

  if (StripEdges[id1][count].array[2] == -1)
    return 0;

  return 1;
}

///	StoreAdjacency:
void CustomStripifier::StoreAdjacency(int NumAdj,int face_id)
{
    StripFaceAdj[face_id].NumAdj = NumAdj;
    StripFaceAdj[face_id].finish = false;

	if (StripArray[NumAdj].empty())
		StripArray[NumAdj].push_back(face_id);
	else
		StripArray[NumAdj].insert(StripArray[NumAdj].begin(),face_id);

}

///	Find_Adjacencies:
void CustomStripifier::FindAdjacencies(int num_faces, int num_verts)
{
  int	x;
  vector_vector3 aux;


	for (x=0; x < num_verts; x++)
		StripEdges.push_back(aux);

	for (x=0;x<num_faces;x++)
	{
		if (x<StripFaces.size())
		{
			//v1,v2,face,index
			AddAdjEdge(StripFaces[x].array[0],StripFaces[x].array[1],x);
			AddAdjEdge(StripFaces[x].array[1],StripFaces[x].array[2],x); 
			AddAdjEdge(StripFaces[x].array[0],StripFaces[x].array[2],x);
		}
	}
}

///	Prediction:
int CustomStripifier::Prediction()
{
  int id[60],t,x,f=0,min = 60;
  
	for (x = 0; x < last; x++)
    {
		t = MinimumAd(ties_array[x]);

	    if (t == min)
			id[f++] = ties_array[x];
      
		if (t < min)
		{
			f = 0;
			min = t;
			id[f++] = ties_array[x];
		}
    }
  
	if ( f == 1)
		return id[0];
  
	if (min == 0)
		return id[0];

	x = rand();

	while (x >= f)
		x = x/20;

  return (id[x]);

}

///	AddNewFace:
void CustomStripifier::AddNewFace(int ids[3], int face_id)
{
 
  for (int i = 0; i < 3; i++)
  {
		StripFaces[face_id-1].array[i] = ids[i];

		if (StripVertices[ids[i]].empty())
			StripVertices[ids[i]].push_back(face_id-1);
		else
			StripVertices[ids[i]].insert(StripVertices[ids[i]].begin(),face_id-1);
  }
}

///	AddAdjEdge:
void CustomStripifier::AddAdjEdge(int v1,int v2,int fnum )
{
  int	flag	=	true;
  int	t,count=0;
  int	v3		=	-1;
  vector3 aux;
 
	GetLower (&v1, &v2);

	if (StripEdges[v1].empty())
	{
 		flag	=	false;
	}

	while (flag)
	{
		if (v2 == StripEdges[v1][count].array[0])
		{
			if (StripEdges[v1][count].array[2] == -1)
			{
				StripEdges[v1][count].array[2] = fnum;
			}
			else
			{
				v3	=	StripEdges[v1][count].array[2];

				mError	=	1;
			}

			flag = false;
		}
		else
		{
			count++;

			if (count>=StripEdges[v1].size())
			{
				flag	=	false;
			}
		}
  }

  if (count>=StripEdges[v1].size())
  {
	aux.array[0]	=	v2;
	aux.array[1]	=	fnum;
	aux.array[2]	=	v3;

	StripEdges[v1].push_back(aux);
  }
}

///	GetEdge:
int CustomStripifier::GetEdge(int *edge1,int *edge2,int *index,int face_id)
{
  int x;
  int reversed = -1;
  int set = false;
  
  for (x=0; x< 3; x++)
  {
    if (x == 2)
	{
	    if ((*(index) == 0) && (*(index+2)==0))
		{
	      if (set)
			return 1;

	      reversed = 1;
	    }
	    else if ((*(index) == 0) && (*(index+2)==0))
	    {
	      if (set)
		    return 0;
	      reversed = 0;
	    }
	  
	    if (Look_Up(*(index),*(index+2),face_id))
	    {
	      
		  set = true;
		  *edge1 = *(index);
		  *edge2 = *(index+2);
		
	      if ((reversed != -1))  
		    return reversed;
	    }
	}		
    else
	{
		if ((*(index+x) == 0) && (*(index+x+1)==0))
	    {
	      if (set)
			return 0;
	      reversed = 0;
	    }
		else if ((*(index+x) == 0) && (*(index+x+1)==0))
	    {
	      if (set)
			return 1;
	      reversed = 1;
	    }
	  
		if (Look_Up(*(index+x),*(index+x+1),face_id))
	    {
		  set = true;
		  *edge1 = *(index+x);
		  *edge2 = *(index+x + 1);

	      if ((reversed != -1))
			return reversed;
	    }
	}
  }			

	if ((x == 3) && (reversed != -1))
      exit(0);

  return reversed;
}

///	Update_FaceEx:
void CustomStripifier::UpdateFaces(int *next_NumAdj,int *min_face, int face_id, int *e1, int *e2,int temp1, int temp2,int *ties)
{
  int i; 
  int there = false;
  
 	      	
  if (face_id<StripFaces.size())
  {
    for (i = 0; i< 3; i++)
	{
		if (i != 2)
	    {
	      if( ((temp1 == StripFaces[face_id].array[i]) && 
		   (temp2 ==StripFaces[face_id].array[i+1])) ||
		   ((temp2 == StripFaces[face_id].array[i]) &&
		   (temp1 ==StripFaces[face_id].array[i+1])))
				there = true;
	    }
		else
	    {
	      if( ((temp1 == StripFaces[face_id].array[0]) && 
		   (temp2 ==StripFaces[face_id].array[2])) ||
		  ((temp2 == StripFaces[face_id].array[0]) &&
		   (temp1 ==StripFaces[face_id].array[2])))
					there = true;
	    }
	}
      
    if (!there)
		return;
     
    if (StripFaceAdj[face_id].finish)
		return;

	i = StripFaceAdj[face_id].NumAdj;

    if (i==0)
		return;

    StoreAdjacency(i-1,face_id);

	StripArray[i].erase(find(StripArray[i].begin(), StripArray[i].end(), face_id));

    if (*next_NumAdj == (i-1))
	{
	  ties_array[last++] = face_id;
	}

    if (*next_NumAdj > (i-1))
	{
	  *next_NumAdj = i-1;
	  *min_face = face_id;
	  *e1 = temp1;
	  *e2 = temp2;
	  last=0;
	  ties_array[last++] = face_id;
	}
  }
}

///	DeleteAdj:
//Looking for another adajacent face
void CustomStripifier::DeleteAdj(int id1, int id2, int *next_NumAdj, int *min_face, 
		  							int current_face, int *e1, int *e2, int *ties)
{
  int count=0;
  int next_face;
  
  GetLower(&id1,&id2);
  
  if (StripEdges[id1].empty())
    return;

  while (StripEdges[id1][count].array[0] != id2)
  {
      count++;

	  if (count>=StripEdges[id1].size())
		return;
  }

  if (StripEdges[id1][count].array[2] == -1) //No more adjacencies
  {
    return;
  }
  else
  {
    if (StripEdges[id1][count].array[2] == current_face)
	  next_face = StripEdges[id1][count].array[1];
    else 
	  next_face = StripEdges[id1][count].array[2];
  }

  UpdateFaces(next_NumAdj, min_face, next_face,e1,e2,id1,id2,ties);
}

///	UpdateAdjacencies:
int CustomStripifier::UpdateAdjacencies(int face_id, int *next_NumAdj, int *e1, int *e2,  int *ties)
{
  int min_face = -1;
  
  *next_NumAdj = 60;

  if ( face_id >= StripFaces.size() )
      exit(0);

  DeleteAdj(StripFaces[face_id].array[0],StripFaces[face_id].array[1],
			next_NumAdj,&min_face,face_id,e1,e2,ties);
  DeleteAdj(StripFaces[face_id].array[1],StripFaces[face_id].array[2],
				next_NumAdj,&min_face,face_id,e1,e2,ties);
  DeleteAdj(StripFaces[face_id].array[0],StripFaces[face_id].array[2],
				next_NumAdj,&min_face,face_id,e1,e2,ties);

  return (min_face);
}

///	Stripification:
void CustomStripifier::Stripification()
{
  int	max,NumAdj	=	0;
  int					whole_flag	=	true;
  int						dummy				= 0;
  int						cont				=	0;
  int face,ties=0;
  
  lastTri[0]=0;
  lastTri[1]=0;
  lastTri[2]=0;
  
  while (whole_flag)
  {
	NumAdj = -1;

    while (NumAdj < 59)
	{
		NumAdj++;
	
		max = StripArray[NumAdj].size();

		if (max > 0)
		{
			face=StripArray[NumAdj][0];

			StoreTri(face,NumAdj,NumAdj,&ties,3,1);

			if (NumAdj >= 2) 
					GoBack(face,&ties,3);

			break;  
		}
	}


	if ((NumAdj == 59) && (max == 0))
	{
			whole_flag = false;
	}
    else
	{
			AddTri(-1,-2,-3,-10,1);
			lastTri[0]=0;
			lastTri[1]=0;
			lastTri[2]=0;
			cont++;
	}
  }
}


///	Finished:
int CustomStripifier::Finished()
{
  int num,x,vertex1,vertex2;
  int id[2],other1,other2,index = 0,a,b,c;
  vector_int::iterator iter;
  
  num = Strips.size();

  if (num==0)
	return 0;

  if (num<4)
  {
		Orient(Strips[2]+1,Strips[1]+1,Strips[0]+1);
	  
		my_vector[num_tiras].push_back(Strips[2]);
		my_vector[num_tiras].push_back(Strips[1]);
		my_vector[num_tiras].push_back(Strips[0]);
    
	    Strips.clear();

	    return 1;
  }
  
  if (num<6)
  {
    exit(0);
  }
  
  vertex1 = Different(Strips[0],Strips[1],Strips[2], Strips[3],Strips[4],Strips[5], &other1,&other2);
  vertex2 = Different(Strips[3],Strips[4],Strips[5], Strips[0],Strips[1],Strips[2], &other1,&other2);
  
 if (Strips.size()>6)
    other1 = Different(Strips[8],Strips[3],Strips[4], Strips[6],Strips[7],Strips[8],&other1,&a);
  
  id[index] = vertex1; index = !index;
  id[index] = other1; index = !index;
  id[index] = other2; index = !index;
  
  a = Strips[3]; 
  b = Strips[4]; 
  c = Strips[5];
  
  Orient(vertex1+1,other1+1,other2+1);
    
  my_vector[num_tiras].push_back(vertex1);
  my_vector[num_tiras].push_back(other1);
  my_vector[num_tiras].push_back(other2);

  for (x = 6; x < num ; x = x+3)
  {
    //    Error checking
	if (((id[0] != a) && (id[0] != b) && (id[0] != c)) ||
		((id[1] != a) && (id[1] != b) && (id[1] != c)) ||
		((vertex2 != a) && (vertex2 != b) && (vertex2 != c)))
    {
		vector_int nada;
		my_vector.push_back(nada);

		num_tiras++;

        vertex1 = Different(a,b,c,Strips[x],Strips[x+1],Strips[x+2],&other1,&other2);
        vertex2 = Different(Strips[x],Strips[x+1],Strips[x+2], a,b,c,&other1,&other2);
	  
        id[index] = vertex1; index = !index;
        id[index] = other1; index = !index;
        id[index] = other2; index = !index;
	}
      
     
    if ((id[0] == id[1]) || (id[0] == vertex2))
        continue;
      
    if ((id[index] == Strips[x]) || (id[index] == Strips[x+1]) || (id[index] == Strips[x+2]))
    {

		my_vector[num_tiras].push_back(id[index]);


        index = !index;
	}
      
	my_vector[num_tiras].push_back(vertex2);

    id[index] = vertex2; index = !index;
      
	vertex2	=	Different(Strips[x],Strips[x+1],Strips[x+2], a,b,c,&other1,&other2);
	a		=	Strips[x];
	b		=	Strips[x+1];
	c		=	Strips[x+2];
  }

  my_vector[num_tiras].push_back(vertex2);

  Strips.clear();

  return (num/3);        
}


///	ReadData: Loads the object in memory.
void CustomStripifier::ReadData(Geometry::SubMesh *geoSubMesh,int num_faces, int num_vert)
{
  int i,face_id =	0;
  vector3 aux;
  vector_int aux2;

  //Allocate space for faces and vertices
  for (i=0; i<num_faces; i++)
		StripFaces.push_back(aux);
   
  for (i=0; i < num_vert; i++)  
		StripVertices.push_back(aux2);

  for(unsigned int j = 0; j < geoSubMesh->mIndexCount; j = j + 3)
  {
		face_id++;

		ids[0]=geoSubMesh->mIndex[j+0];
		ids[1]=geoSubMesh->mIndex[j+1];
		ids[2]=geoSubMesh->mIndex[j+2];

		AddNewFace(ids,face_id);
  }

  num_faces	= face_id;

  if (StripFaceAdj != NULL)
  {
    free(StripFaceAdj); 
  }
  
  StripFaceAdj = (adj*) malloc (sizeof(adj) * num_faces);
}


//-------------------------------------------------------------------------
//	Constructors.
//-------------------------------------------------------------------------

MeshStripifier::MeshStripifier()
{
}

MeshStripifier::MeshStripifier(	const	Geometry::Mesh	*geoMesh)
{
}

CustomStripifier::CustomStripifier()
{
}
CustomStripifier::CustomStripifier(	const	Geometry::Mesh	*geoMesh)
{
	MeshGlobal	=	new Geometry::Mesh();
	*MeshGlobal	=	*geoMesh;

	//	Initialize the leaves submesh index.
	mSubMeshLeaves	=	-1;

	//	Sets the actual progress bar function.
	mUPB	=	NULL;
}

//-------------------------------------------------------------------------
//	Destroyers.
//-------------------------------------------------------------------------
CustomStripifier::~CustomStripifier()
{	
	printf("Voy a borrar\n");
	delete	MeshGlobal;
	printf("Borro\n");
}

MeshStripifier::~MeshStripifier()
{
}

//-------------------------------------------------------------------------
//	Public.
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
//	Stripify.
//-------------------------------------------------------------------------
int CustomStripifier::Stripify()
{
	//	Init variables
	last				=	0;

	//	Make Triangle Strips.
	return	stripify(MeshGlobal);
}

//-------------------------------------------------------------------------
//	GetMesh: Return de current Mesh.
//-------------------------------------------------------------------------
Mesh*	CustomStripifier::GetMesh()
{
	Mesh		*mesh_stripified;

	mesh_stripified			=	new Mesh();
	*mesh_stripified		=	*MeshGlobal;

	return	mesh_stripified;
}

//-------------------------------------------------------------------------
//	Set the progress bar function.
//-------------------------------------------------------------------------
void	CustomStripifier::SetProgressFunc(TIPOFUNC upb)
{
	//	Sets the actual progress bar function.
	mUPB	=	upb;
}

//-------------------------------------------------------------------------
// Sets what is the submesh that stores the leaves.
//-------------------------------------------------------------------------
void CustomStripifier::SetSubMeshLeaves(size_t	submesh)
{
	mSubMeshLeaves	=	submesh;
}