/*	==========================================================================
 *	(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.
//-----------------------------------------------------------------------------

///	InitList:
BOOL CustomStripifier::InitList(PLISTHEAD LHead)
{
	if (LHead == NULL)
	{
		return	FALSE;
	}

	LHead->LHeaders[LISTHEAD] = LHead->LHeaders[LISTTAIL] = NULL;
	LHead->NumList = 0;

	return	TRUE;
}

///	AddHead:
BOOL CustomStripifier::AddHead(PLISTHEAD LHead, PLISTINFO LInfo)
{
	if (LHead == NULL || LInfo == NULL)
	{
		return(FALSE);
	}

	if (EMPTYLIST(LHead))
	{
		LHead->LHeaders[LISTTAIL] = LInfo;
	}
	else
	{
		LHead->LHeaders[LISTHEAD]->ListNode.Previous = (void  *) LInfo;
	}

	LInfo->ListNode.Next			=	(void  *) LHead->LHeaders[LISTHEAD];
	LHead->LHeaders[LISTHEAD]	=	LInfo;
	LInfo->ListNode.Previous	=	NULL;
	LHead->NumList++;

	return(TRUE);
}

///	AddTail
BOOL  CustomStripifier::AddTail(PLISTHEAD LHead, PLISTINFO LInfo)
{
	if (LHead == NULL || LInfo == NULL)
	{
		return	FALSE;
	}

	if (EMPTYLIST(LHead))
	{
		LHead->LHeaders[LISTHEAD] = LInfo;
	}
	else
	{
		LHead->LHeaders[LISTTAIL]->ListNode.Next = (void *) LInfo;
	}

	LInfo->ListNode.Previous	= (void  *) LHead->LHeaders[LISTTAIL];
	LHead->LHeaders[LISTTAIL] = LInfo;
	LInfo->ListNode.Next			= NULL;
	LHead->NumList++;

	return	TRUE;
}

///	InsertNode
BOOL  CustomStripifier::InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo )
{
	PLISTINFO add_node;

  if ( LHead == NULL || LInfo == NULL || nPos > NumOnList( LHead ) )
	{
		return	FALSE;
	}

	if ( nPos == 0 )
	{
		AddHead( LHead, LInfo );
	}
	else if ( nPos == NumOnList( LHead ) )
	{
		AddTail( LHead, LInfo );
	}
	else
	{
		if ( (add_node = PeekList( LHead, LISTHEAD, nPos - 1 )) == NULL )
		{
			return	FALSE;
		}
 
		((PLISTINFO)add_node->ListNode.Next)->ListNode.Previous = LInfo;

		LInfo->ListNode.Next      = add_node->ListNode.Next;
		LInfo->ListNode.Previous  = add_node;
		add_node->ListNode.Next   = LInfo;
		LHead->NumList++;
	}

	return	TRUE;
}

///	RemHead:
PLISTINFO  CustomStripifier::RemHead(PLISTHEAD LHead)
{
	PLISTINFO t, t1;

	if ( LHead == NULL || EMPTYLIST(LHead) )
	{
		return	NULL;
	}

	t													=	LHead->LHeaders[LISTHEAD];
	LHead->LHeaders[LISTHEAD] = (PLISTINFO) t->ListNode.Next;

	if (LHead->LHeaders[LISTHEAD] != NULL)
	{
		t1										= (PLISTINFO) t->ListNode.Next;
		t1->ListNode.Previous = NULL;
	}
	else
	{
		LHead->LHeaders[LISTTAIL] = NULL;
	}
	
	LHead->NumList--;

	return	t;
}

///	RemTail:
PLISTINFO CustomStripifier::RemTail(PLISTHEAD   LHead)
{
	PLISTINFO   t, t1;

	if ( LHead == NULL || EMPTYLIST(LHead) )
	{
		return	NULL;
	}

	t													= LHead->LHeaders[LISTTAIL];
	LHead->LHeaders[LISTTAIL] = (PLISTINFO) t->ListNode.Previous;

	if (LHead->LHeaders[LISTTAIL] != NULL)
	{
		t1 = (PLISTINFO) t->ListNode.Previous;
		t1->ListNode.Next = NULL;
	}
	else
	{
		LHead->LHeaders[LISTHEAD] = NULL;
	}

	LHead->NumList--;

	return	t;
}

///	PeekList:
PLISTINFO CustomStripifier::PeekList(PLISTHEAD LHead, int wch, int index )
{
	PLISTINFO  t;

	if (LHead == NULL)
	{
		return	NULL;
	}

	if ( (t = LHead->LHeaders[wch]) == NULL )
	{
		return	NULL;
	}

	for (; t != NULL && index > 0; index-- )
	{
		t = (wch == LISTHEAD)	?	(PLISTINFO) t->ListNode.Next  
													:	(PLISTINFO) t->ListNode.Previous;
	}

	return	t;
}

///	RemoveList:
PLISTINFO CustomStripifier::RemoveList(PLISTHEAD LHead, PLISTINFO LInfo )
{
	PLISTINFO	t;
	PLISTINFO	t1;

	t	=	LInfo;

	if (LHead == NULL)
	{
		return	NULL;
	}

	if (LHead->LHeaders[LISTHEAD] == t)
	{
		t	=	(PLISTINFO) RemHead(LHead);
	}
	else if (LHead->LHeaders[LISTTAIL] == t)
	{
		t = (PLISTINFO) RemTail(LHead);
	}
	else
	{
		t1                    = (PLISTINFO) t->ListNode.Previous;
		t1->ListNode.Next     = t->ListNode.Next;
		t1                    = (PLISTINFO) t->ListNode.Next;
		t1->ListNode.Previous = t->ListNode.Previous;
		LHead->NumList--;
	}

	return	t;
}

///	SearchList:
///			Try to find a specific node in the queue whose key matches with
///			searching key. Return the pointer to that node if found, return NULL
///			otherwise
///	@param	lpHashTbl       => a far pointer to the hash table.
///	@param	lpKey           => a far poniter to searching key.
///	@param	CompareCallBack => comparision function.
///	@return	a far pointer to the node to be found.
PLISTINFO CustomStripifier::SearchList(
                        PLISTHEAD listHead,
                        PVOID lpSKey,
                        int (* CompareCallBack) ( PVOID, PVOID ) )
{
	PLISTINFO list_info;

	list_info = PeekList( listHead, LISTHEAD, 0);

	while ( list_info != NULL )
	{
		if ( CompareCallBack( list_info, lpSKey ) )
		{
			break;
		}

		list_info	=	(PLISTINFO) GetNextNode( list_info );
	}

	return	list_info;
}

///	init_vert_norms:
void CustomStripifier::init_vert_norms(int num_vert)
{
  /*   Initialize vertex/normal array to have all zeros to
       start with.
  */
  register int x;
  
  for (x = 0; x < num_vert; x++)
	{
		*(vert_norms + x) = 0;
	}
}

///	init_vert_texture:
void CustomStripifier::init_vert_texture(int num_vert)
{
  /*   Initialize vertex/normal array to have all zeros to
       start with.
  */
  register int x;
  
  for (x = 0; x < num_vert; x++)
	{
    *(vert_texture + x) = 0;
	}
}

///	InitVertexTable:
BOOL CustomStripifier::InitVertexTable( int size )
{
  register int index;
  
  /*     Initialize the face table */
  Vertices	=	(ListHead**) malloc(sizeof(ListHead*) * size );
  
  if (Vertices)
	{
		for (index	=	0; index < size; index++)
		{
			Vertices[index] = NULL;
		}

		return	TRUE;

	}

	return	FALSE;
}

///	InitFaceTable:
BOOL CustomStripifier::InitFaceTable( int size )
{
  register int index;
  
  /*     Initialize the face table */
  PolFaces = (ListHead**) malloc(sizeof(ListHead*) * size); 
  
  if (PolFaces)
  {
  	for (index	=	0; index < size; index++)
		{
			PolFaces[index] = NULL;
		}

		return	TRUE;
	}

	return	FALSE;
} 

///	InitEdgeTable:
BOOL CustomStripifier::InitEdgeTable( int size )
{
  register int index;
  
  /*     Initialize the edge table */
  PolEdges	=	(ListHead**) malloc(sizeof(ListHead*) * size );

  if (PolEdges)
	{
		for (index=0; index < size; index++)
		{
			PolEdges[index]	=	NULL;
		}

		return	TRUE;
	}

	return	FALSE;
}

///	InitStripTable:
void CustomStripifier::InitStripTable( )
{
  
  PLISTHEAD list_head;
  
  /*   Initialize the strip table */
  list_head = (PLISTHEAD) malloc(sizeof(ListHead));

  if (list_head)
  {
    InitList(list_head);

    strips[0] = list_head;
  }
  else
  {
    printf("Out of memory !\n");

    exit(0);
  }
  
}

///	Init_Table_SGI:
void CustomStripifier::Init_Table_SGI(int numFaces)
{
  PLISTHEAD			list_head;
  int						max_adj		= 60;
  register			int	x;
  
  /*   This routine will initialize the table that will
       have the faces sorted by the number of adjacent polygons
       to it.
  */
  
  for (x=0; x< max_adj; x++)
  {
		/*	We are allowing the max number of sides of a polygon
				to be max_adj.
    */                      
    list_head = (PLISTHEAD) malloc(sizeof(ListHead));

    if (list_head)
		{
			InitList(list_head);

			array[x]	=	list_head;
		}
    else
		{
			printf("Out of memory !\n");
			exit(0);
		}
	}
  
  if (face_array != NULL) /* It seems this function is called more than */
	{
    free(face_array);     /* once so we'll free up the old stuff */
	}
  
  face_array = (P_FACE_ADJACENCIES) malloc (sizeof(FACE_ADJACENCIES) * numFaces);

  if (face_array == NULL)
	{
    printf("Out of memory !!\n");
    exit(0);
  }
  
}

///	BuildVertexTable:
void CustomStripifier::BuildVertexTable(int size)
{
  register int	index;
  PLISTHEAD			list_head;
  
  for (index	=	0; index < size; index++)
  {
    list_head	=	(PLISTHEAD) malloc(sizeof(ListHead));

    if (list_head)
		{
			InitList(list_head);

			Vertices[index]	=	list_head;
		}
    else
		{
			return;
		}
      
	}
}

///	BuildFaceTable:
void CustomStripifier::BuildFaceTable( int size )
{
  register int	index;
  PLISTHEAD			list_head;
  
  for (index	=	0; index < size; index++)
  {
    list_head	=	(PLISTHEAD) malloc(sizeof(ListHead));

    if (list_head)
		{
			InitList(list_head);

			PolFaces[index]	=	list_head;
		}
		else
		{
			return;
		}
	}
}

///	BuildEdgeTable:
void CustomStripifier::BuildEdgeTable( int size )
{
  register int	index;
  PLISTHEAD			list_head;
  
  for (index	=	0; index < size; index++)
  {
  	list_head	=	(PLISTHEAD) malloc(sizeof(ListHead));

		if (list_head)
		{
	  	InitList(list_head);

	  	PolEdges[index]	=	list_head;
		}
    else
		{
			return;
		}
	}
}

///	Start_Vertex_Struct:
void CustomStripifier::Start_Vertex_Struct(int numVerts)
{
  if (InitVertexTable(numVerts))
  {
    BuildVertexTable(numVerts);
  }
}

///	Start_Face_Struct:
void CustomStripifier::Start_Face_Struct(int numFaces)
{
  if (InitFaceTable(numFaces))
  {
    BuildFaceTable(numFaces);
  }
}

///	Start_Edge_Struct:
void CustomStripifier::Start_Edge_Struct(int numVerts)
{
  if (InitEdgeTable(numVerts))
  {
    BuildEdgeTable(numVerts);
  }
}

///	switch_lower:
void CustomStripifier::switch_lower (int *x, int *y)
{
  register int temp;
  
  /*	Put lower value in x */
  if (*y < *x)
  {
    temp	=	*x;
    *x		=	*y;
    *y		=	temp;
  }
}

///	member:
BOOL CustomStripifier::member(int x , int id1, int id2, int id3)
{
  /*  Is x in the triangle specified by id1,id2,id3 */
  if ((x != id1) && (x != id2) && (x != id3))
	{
    return	FALSE;
	}

  return	TRUE;
}

///	Exist:
BOOL CustomStripifier::Exist(int faceId, int id1, int id2)
{
  /*	Does the edge specified by id1 and id2 exist in this
	face currently? Maybe we deleted in partial triangulation
  */
  ListHead			*list_head;
  PF_FACES			temp;
  register int	x,size;
  BOOL					a	=	FALSE;
	BOOL					b =	FALSE;
  
  list_head	=	PolFaces[faceId];

  temp	=	(PF_FACES) PeekList(list_head, LISTHEAD, 0);
  size	=	temp->nPolSize;

  for (x=0; x<size; x++)
  {
    if (*(temp->pPolygon+x) == id1)
		{
			a = TRUE;
		}
     
		if (*(temp->pPolygon+x) == id2)
		{
			b = TRUE;
		}

    if (a && b)
		{
			return	TRUE;
		}
  }

  return	FALSE;
}

///	Different:
int CustomStripifier::Different(int id1,int id2,int id3,int id4,int id5, int id6, int *x, int *y)
{
  /*    Find the vertex in the first 3 numbers that does not exist in 
	the last three numbers
  */
  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;
    }
  
  /*  Because there are degeneracies in the data, this might occur */
  *x = id5;
  *y = id6;
  return id4;
}

///	Return_Other:
int CustomStripifier::Return_Other(int *index,int e1,int e2)
{
  /*   We have a triangle and want to know the third vertex of it */
  register int x;
  
  for (x=0;x<3;x++)
    {
      if ((*(index+x) != e1) && (*(index+x) != e2))
	return *(index+x);
    }
  /*   If there is a degenerate triangle return arbitrary */
  return e1;
}

///	Get_Other_Vertex:
int CustomStripifier::Get_Other_Vertex(int id1,int id2,int id3,int *index)
{
  /*	We have a list index of 4 numbers and we wish to
	return the number that is not id1,id2 or id3
  */
  register int x;
  
  for (x=0; x<4; x++)
    {
      if ((*(index+x) != id1) && (*(index+x) != id2) &&
	  (*(index+x) != id3))
	return *(index+x);
    }
  /*   If there is some sort of degeneracy this might occur,
       return arbitrary 
  */
//  if (x==4)
    return id1;
}

///	Done:
PLISTINFO CustomStripifier::Done(int face_id, int *bucket)
{
  /*	Check to see whether the polygon with face_id was used
	already, return NULL if it was, otherwise return a pointer to the face.
  */
  
  PLISTINFO lpListInfo;
  
  lpListInfo = (PLISTINFO) face_array[face_id].pfNode;
  if (lpListInfo != NULL) {
    *bucket = face_array[face_id].bucket;
    return lpListInfo;
  }
  else
    return lpListInfo;
}

///	First_Edge:
void CustomStripifier::First_Edge(int *id1,int *id2, int *id3)
{
  /*  Get the first triangle in the strip we just found, we will use this to
      try to extend backwards in the strip
  */
  
  ListHead *pListHead;
  register int num;
  P_STRIPS temp1,temp2,temp3;
  
  pListHead = strips[0];
  num = NumOnList(pListHead);
  
  /*    Did not have a strip */
  if (num < 3)
    return;
  
  temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 0);
  temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 1);
  temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 2);
  *id1 = temp1->face_id;
  *id2 = temp2->face_id;
  *id3 = temp3->face_id;
  
}

///	Last_Edge:
void CustomStripifier::Last_Edge(int *id1, int *id2, int *id3, BOOL save)
{
  /*   We need the last edge that we had  */
  static int v1, v2, v3;
  
  if (save)
    {
      v1 = *id1;
      v2 = *id2;
      v3 = *id3;
    }
  else
    {
      *id1 = v1;
      *id2 = v2;
      *id3 = v3;
    }
}

///	find_triangle_orientation:
void CustomStripifier::find_triangle_orientation(int vertex1,int vertex2,int vertex3,
                                      int *original_vertex)                                 
{
  int vertices,index;
  PF_VERTICES verts;
  
  /* Search through face to match orignal vertices */
  
  /* Start with vertex1's Vertices struct */  
  verts = (PF_VERTICES) PeekList(Vertices[vertex1-1],LISTHEAD,0);
  do {  
    index = 0;
    for (vertices = 0; vertices < verts->face->nOrgSize;vertices++) {
      if (vertex1 == verts->face->pPolygon[vertices]+1 || 
	  vertex2 == verts->face->pPolygon[vertices]+1 ||
	  vertex3 == verts->face->pPolygon[vertices]+1 )
        original_vertex[index++] = verts->face->pPolygon[vertices]+1;      
      if (index == 3)
        break;
    }
    if (index == 3)
      break;
  } while ((verts = (PF_VERTICES) GetNextNode(verts)) != NULL);
  
  if (index != 3) {
    /* Search vertex2's Vertices struct */  
    verts = (PF_VERTICES) PeekList(Vertices[vertex2-1],LISTHEAD,0);
    do {
      index = 0;
      for (vertices = 0; vertices < verts->face->nOrgSize;vertices++) {
        if (vertex1 == verts->face->pPolygon[vertices]+1 || 
	    vertex2 == verts->face->pPolygon[vertices]+1 ||
	    vertex3 == verts->face->pPolygon[vertices]+1 )
          original_vertex[index++] = verts->face->pPolygon[vertices]+1;      
        if (index == 3)
          break;
      }
      if (index == 3)
        break;
    } while ((verts = (PF_VERTICES) GetNextNode(verts)) != NULL);
  }
  
  if (index != 3) {
    /* Search vertex3's Vertices struct */  
    verts = (PF_VERTICES) PeekList(Vertices[vertex3-1],LISTHEAD,0);
    do {    
      index = 0;
      for (vertices = 0; vertices < verts->face->nOrgSize;vertices++) {
        if (vertex1 == verts->face->pPolygon[vertices]+1 || 
	    vertex2 == verts->face->pPolygon[vertices]+1 ||
	    vertex3 == verts->face->pPolygon[vertices]+1 )
          original_vertex[index++] = verts->face->pPolygon[vertices]+1;      
        if (index == 3)
          break;
      }
      if (index == 3)
        break;
    } while ((verts = (PF_VERTICES) GetNextNode(verts)) != NULL);
  }
  
  /*  if (index !=3 )
      printf("Warning: Didn't find a triangle for %d %d %d\n",
      vertex1,vertex2,vertex3);
  */
}

///	preserve_strip_orientation_with_normal:
void CustomStripifier::preserve_strip_orientation_with_normal(FILE *output, int vertex1, int normal1, int vertex2, int normal2, int vertex3, int normal3)
{
  int original_vertex[3];
  
  find_triangle_orientation(vertex1,vertex2,vertex3, original_vertex);
  
  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   ))  {
	// New Triangle is in an opposite orientation.  Add vertex2 to correct it
	fprintf(output," %d//%d",vertex2,normal2);
  }

}

///	preserve_strip_orientation_with_texture:
void CustomStripifier::preserve_strip_orientation_with_texture(FILE *output,
					     int vertex1, int texture1,
					     int vertex2, int texture2,
					     int vertex3, int texture3)
{
  int original_vertex[3];
  
  find_triangle_orientation(vertex1,vertex2,vertex3,                    
                            original_vertex);
  
  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   ) ) {
    /* New Triangle is in an opposite orientation */
    /* Add vertex2 to correct it */
    fprintf(output," %d/%d",vertex2,texture2);
  }
}

///	preserve_strip_orientation_with_texture_and_normal:
void  CustomStripifier::preserve_strip_orientation_with_texture_and_normal(FILE *output,
							 int vertex1, int texture1, int normal1,
							 int vertex2, int texture2, int normal2,
							 int vertex3, int texture3, int normal3)
{
  int original_vertex[3];
  
  find_triangle_orientation(vertex1,vertex2,vertex3,
                            original_vertex);
  
  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   ) ) {
    /* New Triangle is in an opposite orientation */
    /* Add vertex2 to correct it */
    fprintf(output," %d/%d/%d",vertex2,texture2,normal2);
  }
}

///	preserve_strip_orientation:
void CustomStripifier::preserve_strip_orientation(FILE *output,int vertex1, int vertex2,int vertex3)
{ 
  int original_vertex[3];
  
  find_triangle_orientation(vertex1,vertex2,vertex3,
			    original_vertex);
  
  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   ))  {
    /* New Triangle is in an opposite orientation */
    /* Add vertex2 to correct it */
    fprintf(output," %d",vertex2);
	mi_vector[num_tiras].push_back(vertex2-1);
  }
}

///	Output_TriEx:
void CustomStripifier::Output_TriEx(int id1, int id2, int id3, FILE *output, 
		  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.
  */
  
  int swap,temp1,temp2,temp3;
  static int total=0;
  static int tri=0;
  static int strips = 0;
  static int cost = 0;
  
  if (flag == -20)
    {
      cost = cost + where+total+tri+strips+strips;
      printf("We will need to send %d vertices to the renderer\n",cost);
      total = 0;
      tri = 0;
      strips = 0;
      return ;
    }
  
  
  if (flag == -10)
    /*    We are finished, now is time to output the triangle list
     */
  {
		fprintf(output,"\nt");
	  mi_vector_tipo nada;
	  mi_vector.push_back(nada);
	  num_tiras++;
    tri = tri + Finished(&swap,output,1);
    total = total + swap;
    strips++;
      /*printf("There are %d swaps %d tri %d strips\n",total,tri,strips);*/
  }
  else
  {
      Last_Edge(&temp1,&temp2,&temp3,0);
      Add_Id_Strips(id1,where);
      Add_Id_Strips(id2,where);
      Add_Id_Strips(id3,where);
      Last_Edge(&id1,&id2,&id3,1);
  }
}

///	Extend_BackwardsEx:
void CustomStripifier::Extend_BackwardsEx(int face_id, FILE *output, int *ties,
			int tie, int triangulate,
			int swaps,int *next_id)
{
  /*  We just made a strip, now we are going to see if we can extend
      backwards from the starting face, which had 2 or more adjacencies
      to start with.
  */
  
  int bucket,next_face,num,x,y,z,c,max,f;              
  ListHead *pListFace;
  PF_FACES face;
  P_ADJACENCIES temp;
  
  /*  Get the first triangle that we have saved the the strip data 
      structure, so we can see if there are any polygons adjacent
      to this edge or a neighboring one
  */
  First_Edge(&x,&y,&z); 
  
  pListFace  = PolFaces[face_id];
  face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
  
  num = face->nPolSize;
  
  /*  Go through the edges to see if there is an adjacency
      with a vertex in common to the first triangle that was
      outputted in the strip. (maybe edge was deleted....)
  */
  for (c=0; c<num ; c++)
    {
      
      if ( (c != (num-1)) && 
	   (( (*(face->pPolygon+c) == x) && (*(face->pPolygon+c+1) == y)) ||
	    (*(face->pPolygon+c) == y) && (*(face->pPolygon+c+1) == x)))
	{
	  /*  Input edge is still there see if there is an adjacency */
	  next_face = Find_Face(face_id, x, y, &bucket);
	  if (next_face == -1)
	    /*  Could not find a face adjacent to the edge */
	    break;
	  pListFace = array[bucket];
	  max = NumOnList(pListFace);
	  for (f=0;;f++)
	    {
	      temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);	
	      if (temp->face_id == next_face)
		{
		  Last_Edge(&z,&y,&x,1);
		  Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
				   output,ties,tie,triangulate,
				   swaps,next_id,0);
		  return;
		}
	      
	      if (temp == NULL)
		{
		  printf("Error in the new buckets%d %d %d\n",bucket,max,0);
		  exit(0);
		}
	    }
	  
	}
      else if ( (c == (num -1)) &&
		( ((*(face->pPolygon) == x) && (*(face->pPolygon+num-1) == y)) ||
		  (*(face->pPolygon) == y) && (*(face->pPolygon+num-1) == x)))
	{
	  next_face = Find_Face(face_id,x,y,&bucket);
	  if (next_face == -1)
	    /*  Could not find a face adjacent to the edge */
	    break;
	  pListFace = array[bucket];
	  max = NumOnList(pListFace);
	  for (f=0;;f++)
	    {
	      temp = (P_ADJACENCIES) PeekList(pListFace,LISTHEAD,f);
	      if (temp->face_id == next_face)
		{
		  Last_Edge(&z,&y,&x,1);
		  Polygon_OutputEx(temp,temp->face_id,bucket,pListFace,
				   output,ties,tie,triangulate,
				   swaps,next_id,0);
		  return;
		}
	      
	      if (temp == NULL)
		{
		  printf("Error in the new buckets%d %d %d\n",bucket,max,0);
		  exit(0);
		}
	    }
	}
    }
}

///	Polygon_OutputEx:
void CustomStripifier::Polygon_OutputEx(P_ADJACENCIES temp,int face_id,int bucket,
		      ListHead *pListHead, FILE *output,
		      int *ties, int tie, 
		      int triangulate, int swaps,
		      int *next_id, int where)
{
  ListHead *pListFace;
  PF_FACES face;
  static BOOL begin = TRUE;
  int old_face,next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
  P_ADJACENCIES lpListInfo; 
  
  /*      We have a polygon to output, the id is face id, and the number
	  of adjacent polygons to it is bucket.
  */
  
  Last_Edge(&e1,&e2,&e3,0);
  
  /*  Get the polygon with id face_id */
  pListFace  = PolFaces[face_id];
  face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
  
  if (face->nPolSize == 3)
    {
      /*      It is already a triangle */
      if (bucket == 0)
	{
	  /*      It is not adjacent to anything so we do not have to
		  worry about the order of the sides or updating adjacencies
	  */
	  
	  Last_Edge(&e1,&e2,&e3,0);
	  next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),
				   *(face->pPolygon+2),
				   e1,e2,e3,&other1,&other2);
	  /*  No input edge, at the start */
	  if ((e2 ==0) && (e3 == 0))
	    {
	      e2 = other1;
	      e3 = other2;
	    }
	  
	  Output_TriEx(e2,e3,next_face_id,NULL,begin,where);
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  /*      We will be at the beginning of the next strip. */
	  begin = TRUE;
	}
      /*      It is a triangle with adjacencies. This means that we
	      have to:
	      1. Update the adjacencies in the list, because we are
	      using this polygon and it will be deleted.
	      2. Get the next polygon.
      */
      else
	{
	  /*   Return the face_id of the next polygon we will be using,
	       while updating the adjacency list by decrementing the
	       adjacencies of everything adjacent to the current triangle.
	  */
	  
	  next_face_id = Update_AdjacenciesEx(face_id,&next_bucket, &e1,&e2,ties);
	  old_face = next_face_id;
	  
	  /*  Break the tie,  if there was one */
	  if (tie != FIRST)
	    old_face = Get_Next_Face(tie,face_id,triangulate);
	  
	  if (next_face_id == -1)
	    {
	      Polygon_OutputEx(temp,face_id,0,pListHead,output,ties,tie, 
			       triangulate,swaps,next_id,where);
	      return;
	    }
	  
	  
	  /*  We are using a different face */
	  if ((tie != FIRST) && (old_face != next_face_id) && (swaps == ON))
	    {
	      next_face_id = old_face;
	      /*  Get the new output edge, since e1 and e2 are for the
		  original next face that we got.
	      */
	      e3 = Get_EdgeEx(&e1,&e2,face->pPolygon,next_face_id,
			      face->nPolSize,0,0);
	    }
	  
	  /*      Find the other vertex to transmit in the triangle */
	  e3 = Return_Other(face->pPolygon,e1,e2);
	  Last_Edge(&other1,&other2,&other3,0);
	  
	  if ((other1 != 0) && (other2 != 0))
	    {
	      /*   See which vertex in the output edge is not in the input edge */
	      if ((e1 != other2) && (e1 != other3))
		e3 = e1;
	      else if ((e2 != other2) && (e2 != other3))
		e3 = e2;
	      /* can happen with > 2 polys on an edge but won't 
		 form a good strip so stop the strip here
	      */
	      else
		{
		  Polygon_OutputEx(temp,face_id,0,pListHead,output,
				   ties,tie,triangulate,swaps,next_id,where);
		  return;
		}
	      
	      /*   See which vertex of the input edge is not in the output edge */
	      if ((other2 != e1) && (other2 != e2))
		{
		  other1 = other2;
		  other2 = other3;
		}
	      else if ((other3 != e1) && (other3 != e2))
		other1 = other3;
	      else
		{
		  /* Degenerate triangle just return*/
		  Output_TriEx(other1,other2,e3,NULL,begin,where);
		  if (face_array[temp->face_id].head == pListHead)
		    face_array[temp->face_id].pfNode = NULL;
		  RemoveList(pListHead,(PLISTINFO) temp);
		  begin = FALSE;
		  return;
		}
	      
	    }
	  
	  /*  There was not an input edge, we are the first triangle in a strip */
	  else 
	    {
	      /*   Find the correct order to transmit the triangle, what is
		   the output edge that we want ?
	      */
	      other1 = e3;
	      e3 = e2;
	      other2 = e1;
	    }
	  
	  /*   At this point the adjacencies have been updated  and we
	       have the next polygon id 
	  */
	  Output_TriEx(other1,other2,e3,NULL,begin,where);
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  begin = FALSE;
	  
	  if (Done(next_face_id,&next_bucket) == NULL)
	    return;
	  
	  pListHead = array[next_bucket];
	  lpListInfo = face_array[next_face_id].pfNode;
	  if (lpListInfo == NULL)
	    {
	      printf("There is an error finding the next polygon3 %d\n",
		     next_face_id);
	      exit(0);
	    }
	  Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
			   pListHead, output,ties,tie,
			   triangulate,swaps,next_id,where);
	  
	}
    }
  
  else
    {
      /*      It is not a triangle, we have to triangulate it .
	      Since it is not adjacent to anything we can triangulate it
	      blindly
      */
      if (bucket == 0)
        {
	  /*  Check to see if there is not an input edge */
	  Last_Edge(&other1,&other2,&other3,0);
	  if ((other1 == 0) && (other2 ==0))
	    Blind_TriangulateEx(face->nPolSize,face->pPolygon,
				TRUE,where);
	  else
	    Blind_TriangulateEx(face->nPolSize,face->pPolygon,
				FALSE,where);
	  
	  if (face_array[temp->face_id].head == pListHead)        
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  /*      We will be at the beginning of the next strip. */
	  begin = TRUE;
        }
      
      /*  If we have specified PARTIAL triangulation then
	  we will go to special routines that will break the
	  polygon and update the data structure. Else everything
	  below will simply triangulate the whole polygon 
      */
      else if (triangulate == PARTIAL)
        {
	  
	  /*  Return the face_id of the next polygon we will be using,
	   */
	  next_face_id = Min_Face_AdjEx(face_id,&next_bucket,ties);
	  
	  
	  /* Don't do it partially, because we can go inside and get
	     less adjacencies, for a quad we can do the whole thing.
	  */
	  if ((face_id == next_face_id) && (face->nPolSize == 4) && (swaps == ON))
	    {
	      next_face_id = Update_AdjacenciesEx(face_id, &next_bucket,
						  &e1,&e2,ties);
	      if (next_face_id == -1)
		{
		  /*  There is no sequential face to go to, end the strip */
		  Polygon_OutputEx(temp,face_id,0,pListHead,output,
				   ties,tie,triangulate,swaps,next_id,where);
		  return;
		}
	      
	      /* Break the tie,  if there was one */
	      if (tie != FIRST)
		next_face_id = Get_Next_Face(tie,face_id,triangulate);
	      Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon,
				      output,next_face_id,face_id,where);
	      
	      if (face_array[temp->face_id].head == pListHead)          
		face_array[temp->face_id].pfNode = NULL;
	      RemoveList(pListHead,(PLISTINFO) temp);
	    }
	  
          /*   Was not a quad but we still do not want to do it partially for
	       now, since we want to only do one triangle at a time
	  */
	  else if ((face_id == next_face_id) && (swaps == ON))
	    Inside_Polygon(face->nPolSize,face->pPolygon,
			   face_id,pListHead,where);
	  
	  else
	    {
	      if ((tie != FIRST) && (swaps == ON))
		next_face_id = Get_Next_Face(tie,face_id,triangulate);
	      Partial_Triangulate(face->nPolSize,face->pPolygon,
				  output,next_face_id,face_id,next_id,
				  pListHead,temp,where);
	      /*    Check the next bucket again ,maybe it changed 
		    We calculated one less, but that might not be the case
	      */
	    }
	  
	  if (Done(next_face_id,&next_bucket) == NULL)
	    {
	      /*  Check to see if there is not an input edge */
	      Last_Edge(&other1,&other2,&other3,0);
	      if ((other1 == 0) && (other2 ==0))
		Blind_TriangulateEx(face->nPolSize,face->pPolygon, 
				    TRUE,where);
	      else
		Blind_TriangulateEx(face->nPolSize,face->pPolygon,
				    FALSE,where);
	      
	      if (Done(face_id,&bucket) != NULL)
		{
		  pListHead = array[bucket];
		  lpListInfo = face_array[face_id].pfNode;
		  if (face_array[temp->face_id].head == pListHead)
		    face_array[lpListInfo->face_id].pfNode = NULL;
		  RemoveList(pListHead,(PLISTINFO)lpListInfo);
		}
	      begin = TRUE;
	      return;
	    }
	  
	  begin = FALSE;
	  pListHead = array[next_bucket];
	  lpListInfo = face_array[next_face_id].pfNode;
	  if (lpListInfo == NULL)
	    {
	      printf("There is an error finding the next polygon1 %d %d\n",
		     next_face_id,next_bucket);
	      exit(0);
	    }
	  Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
			   pListHead, output,ties,tie,
			   triangulate,swaps,next_id,where);
        }
      
      
      else
	{
          /*  WHOLE triangulation */
          /*  It is not a triangle and has adjacencies. 
	      This means that we have to:
	      1. TriangulateEx this polygon, not blindly because
	      we have an edge that we want to come out on, that
	      is the edge that is adjacent to a polygon with the
	      least number of adjacencies. Also we must come in
	      on the last seen edge.
	      2. Update the adjacencies in the list, because we are
	      using this polygon .
	      3. Get the next polygon.
          */
          /*   Return the face_id of the next polygon we will be using,
	       while updating the adjacency list by decrementing the
	       adjacencies of everything adjacent to the current polygon.
          */
          
          next_face_id = Update_AdjacenciesEx(face_id,&next_bucket, &e1,&e2,ties);
          
          if (Done(next_face_id,&next_bucket) == NULL)
            {
	      Polygon_OutputEx(temp,face_id,0,pListHead,output,ties,tie, 
			       triangulate,swaps,next_id,where);
	      /*    Because maybe there was more than 2 polygons on the edge */
	      return;
            }
          
          /*      Break the tie,  if there was one */
          else if (tie != FIRST)
            next_face_id = Get_Next_Face(tie,face_id,triangulate);
          
          Non_Blind_TriangulateEx(face->nPolSize,face->pPolygon, 
				  output,next_face_id,face_id,where);
	  
          if (face_array[temp->face_id].head == pListHead)
            face_array[temp->face_id].pfNode = NULL;
          RemoveList(pListHead,(PLISTINFO) temp);
          begin = FALSE;
          pListHead = array[next_bucket];
          lpListInfo = face_array[next_face_id].pfNode;
	  
          if (lpListInfo == NULL)
            {
	      printf("There is an error finding the next polygon2 %d %d\n",
		     next_face_id,next_bucket);
	      exit(0);
            }
          Polygon_OutputEx(lpListInfo,next_face_id,next_bucket,
			   pListHead, output,ties,tie,
			   triangulate,swaps,next_id,where);
	}
      
    }
  Last_Edge(&e1,&e2,&e3,0);
}

///	Adjacent:
int CustomStripifier::Adjacent(int id2,int id1, int *list, int size)
{
  /*	Return the vertex that is adjacent to id1,
	but is not id2, in the list of integers.
  */
  
  register int x=0;
  
  while (x < size)
    {
      if (*(list+x) == id1)
	{
	  if ((x != (size -1)) && (x != 0))
	    {
	      if ( *(list+x+1) != id2)
		return *(list+x+1);
	      else
		return *(list+x-1);
	    }
	  else if (x == (size -1))
	    {
	      if (*(list) != id2)
		return *(list);
	      else
		return *(list+x-1);
	    }
	  else
	    {
	      if (*(list+size-1) != id2)
		return *(list+size-1);
	      else
		return *(list+x+1);
	    }
	}
      x++;
    }
  /*   if there are degeneracies */
  return id1;
}

///	Rearrange_Index:
void CustomStripifier::Rearrange_Index(int *index, int size)
{
  /*	If we are in the middle of a strip we must find the
	edge to start on, which is the last edge that we had
	transmitted.
  */
  int x,f,y,e1,e2,e3;
  register int increment = 1;
  int *temp;
  
  /*	Find where the input edge is in the input list */
  Last_Edge(&e1,&e2,&e3,0);
  for (y = 0; y < size; y++)
    {
      if (*(index+y) == e2)
	{
	  if ((y != (size - 1)) && (*(index+y+1) == e3))
	    break;
	  else if ((y == (size - 1)) && (*(index) == e3))
	    break;
	  else if ((y != 0) && (*(index+y-1) == e3))
	    {
	      increment = -1;
	      break;
	    }
	  else if ((y==0) && (*(index+size-1) == e3))
	    {
	      increment = -1;
	      break;
	    }
	}
      if (*(index+y) == e3)
	{
	  if ((y != (size - 1)) && (*(index+y+1) == e2))
	    break;
	  else if ((y == (size - 1)) && (*(index) == e2))
	    break;
	  else if ((y != 0) && (*(index+y-1) == e2))
            {
	      increment = -1;
	      break;
            }
	  else if ((y==0) && (*(index+size-1) == e2))
            {
	      increment = -1;
	      break;
            }
	}
      /*	Edge is not here, we are at the beginning */
      if ((y == (size-1)) && (increment != -1))
	return;
    }
  
  /*	Now put the list into a new list, starting with the
	input edge. Increment tells us whether we have to go 
	forward or backward.
  */
  /*	Was in good position already */
  if ((y == 0) && (increment == 1)) 
    return;
  
  temp = (int *) malloc(sizeof(int) * size);
  memcpy(temp,index,sizeof(int)*size);
  
  if (increment == 1)
    {
      x=0;
      for (f = y ; f< size; f++)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
      /*	Finish the rest of the list */	
      for(f = 0; f < y ; f++)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
    }
  else
    {
      x=0;
      for (f = y ; f >= 0; f--)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
      /*	Finish the rest of the list */	
      for(f = (size - 1); f > y ; f--)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
    }
}

///	Delete_From_List:
void CustomStripifier::Delete_From_List(int id,int *list, int *size)
{
  /*	Delete the occurence of id in the list.
	(list has size size)
  */
  
  int *temp;
  register int x,y=0;
  
  temp = (int *) malloc(sizeof(int) * (*size));
  for (x=0; x<(*size); x++)
    {
      if (*(list+x) != id)
	{
	  *(temp+y) = *(list+x);
	  y++;
	}
    }
  *(temp+y) = -1;
  *size = *size - (*size - y - 1);
  memcpy(list,temp,sizeof(int)*(*size));
}

///	Build_SGI_Table:
void CustomStripifier::Build_SGI_Table(int num_faces)
{
  /*      Build a table that has the polygons sorted by the
	  number of adjacent polygons.
  */
  int x,y,size,tally=0;
  ListHead *pListHead;
  PF_FACES temp = NULL;
  
  /* For each face....*/
  for (x=0;x < num_faces;x++)
    {
      pListHead = PolFaces[x];
      temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
      /*   Check each edge of the face and tally the number of adjacent
	   polygons to this face. 
      */                      
      if ( temp != NULL )
	{
	  /*      Size of the polygon */
	  size = temp->nPolSize;
	  if (size != 1)
	    {
	      for (y = 0; y< size; y++)
		{
		  if (y != (size-1))
		    tally += Num_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1));
		  else
		    tally+= Num_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)));
		}
	      
	      /*   Tally is the number of polygons that is adjacent to
		   the current polygon. 
	      */
	      /*      Now put the face in the proper bucket depending on tally. */
	      Add_Sgi_Adj(tally,x);
	      temp = NULL;
	      tally=0;
	    }
	}
    }
}

///	Triangulate_Quad:
void CustomStripifier::Triangulate_Quad(int out_edge1,int out_edge2,int in_edge1,
			     int in_edge2,int size,int *index,
			     int reversed,int where)
{
  int vertex4,vertex5;
  
  /*	This routine will nonblindly triangulate a quad, meaning
	that there is a definite input and a definite output
	edge that we must adhere to. Reversed will tell the orientation
	of the input edge. (Reversed is -1 is we do not have an input
	edge, in other words we are at the beginning of a strip.)
	Out_edge* is the output edge, and in_edge* is the input edge. 
	Index are the edges of the polygon
	and size is the size of the polygon. Begin is whether we are
	at the start of a new strip.
  */
  
  /*	If we do not have an input edge, then we can make our input
	edge whatever we like, therefore it will be easier to come
	out on the output edge.
  */
  if (reversed == -1)
    {
      vertex4 = Adjacent(out_edge1,out_edge2,index,size);
      vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
      Output_Tri(vertex5,vertex4,out_edge1,where);
      Output_Tri(vertex4,out_edge1,out_edge2,where);
      return;
    }
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*  Are they consecutive so that we form a triangle to
      peel off, but cannot use the whole quad?
  */
  
  if (in_edge2 == out_edge1) 
    {
      /*	Output the triangle that comes out the correct
		edge last. First output the triangle that comes out
		the wrong edge.
      */
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      Output_Tri(vertex4,in_edge2,out_edge2,where);
      return;
    }
  /*	The next case is where it is impossible to come out the
	edge that we want. So we will have to start a new strip to
	come out on that edge. We will output the one triangle
	that we can, and then start the new strip with the triangle
	that comes out on the edge that we want to come out on.
  */
  else if (in_edge1 == out_edge1)
    {
      /*	We want to output the first triangle (whose output
		edge is not the one that we want.
		We have to find the vertex that we need, which is
		the other vertex which we do not have.
      */
      vertex4 = Get_Other_Vertex(in_edge2,in_edge1,out_edge2,index);
      Output_Tri(in_edge2,in_edge1,vertex4,where);
      Output_Tri(vertex4,in_edge1,out_edge2,where);
      return;
    }
  
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_Tri(in_edge2,in_edge1,vertex4,where);
      Output_Tri(vertex4,in_edge1,out_edge1,where);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      Output_Tri(vertex4,in_edge2,out_edge1,where);
      return;
    }
  
  /*	The final case is where we want to come out the opposite
	edge.
  */
  else
    {
      if( ((!reversed) &&
	   (out_edge1 == (Adjacent(in_edge1,in_edge2,index,size)))) ||
	  ((reversed) &&
	   (out_edge2 == (Adjacent(in_edge2,in_edge1,index,size)))))
	{
	  /*	We need to know the orientation of the input
		edge, so we know which way to put the diagonal.
                And also the output edge, so that we triangulate
                correctly.
	  */
	  Output_Tri(in_edge1,in_edge2,out_edge2,where);
	  Output_Tri(in_edge2,out_edge2,out_edge1,where);
	}
      else
	{
	  /*      Input and output orientation was reversed, so diagonal will
		  be reversed from above.
	  */
	  Output_Tri(in_edge1,in_edge2,out_edge1,where);
	  Output_Tri(in_edge2,out_edge1,out_edge2,where);
	}
      return;
    }
}

///	Triangulate_Polygon:
void CustomStripifier::Triangulate_Polygon(	int out_edge1,int out_edge2,
																						int in_edge1,	int in_edge2,
																						int size,			int *index,
																						FILE *output,	int reversed,
																						int face_id,	int where,
																						int color1,		int color2,
																						int color3)
{
  /*	We have a polygon that we need to nonblindly triangulate.
	We will recursively try to triangulate it, until we are left
	with a polygon of size 4, which can use the quad routine
	from above. We will be taking off a triangle at a time
	and outputting it. We will have 3 cases similar to the
	cases for the quad above. The inputs to this routine
	are the same as for the quad routine.
  */
  
  int vertex4;
  int *temp;
  
  
  /*	Since we are calling this recursively, we have to check whether
	we are down to the case of the quad.
  */
  
  if (size == 4)
    {
      Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
		       index,reversed,where);
      return;
    }
  
  
  
  /*	We do not have a specified input edge, and therefore we
	can make it anything we like, as long as we still come out 
	the output edge that we want.
  */
  if (reversed  == -1)
    {
      /*	Get the vertex for the last triangle, which is
		the one coming out the output edge, before we do
		any deletions to the list. We will be doing this
		bottom up.
      */
      vertex4 = Adjacent(out_edge1,out_edge2,index,size);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(out_edge2,index,&size);
      Triangulate_Polygon(out_edge1,vertex4,in_edge2,
			  vertex4,size-1,index,output,reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      /*	Lastly do the triangle that comes out the output
		edge.
      */
      Output_Tri(vertex4,out_edge1,out_edge2,where);
      return;
    }
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*  Are they consecutive so that we form a triangle to
      peel off that comes out the correct output edge, 
      but we cannot use the whole polygon?
  */
  if (in_edge2 == out_edge1) 
    {
      /*	Output the triangle that comes out the correct
		edge last. First recursively do the rest of the
		polygon.
      */
      /*	Do the rest of the polygon without the triangle. 
		We will be doing a fan triangulation.
      */
      /*	Get the vertex adjacent to in_edge1, but is not
		in_edge2.
      */
      vertex4 = Adjacent(in_edge2,in_edge1,index,size);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(in_edge1,index,&size);
      Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
			  vertex4,size-1,index,output,!reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  
  /*	Next case is where it is again consecutive, but the triangle
	formed by the consecutive edges do not come out of the
	correct output edge. For this case, we can not do much to
	keep it sequential. Try and do the fan.
  */
  else if (in_edge1 == out_edge1)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = Adjacent(in_edge1,in_edge2,index,size);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      /*	Since that triangle goes out of the polygon (the
		output edge of it), we can make our new input edge
		anything we like, so we will try to make it good for
		the strip. (This will be like starting a new strip,
		all so that we can go out the correct output edge.)
      */
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(in_edge2,index,&size);
      Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
			  vertex4,size-1,index,output,reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = Adjacent(in_edge1,in_edge2,index,size);
      Output_Tri(in_edge2,in_edge1,vertex4,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(in_edge2,index,&size);
      Triangulate_Polygon(out_edge1,out_edge2,in_edge1,
			  vertex4,size-1,index,output,reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = Adjacent(in_edge2,in_edge1,index,size);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(in_edge1,index,&size);
      Triangulate_Polygon(out_edge1,out_edge2,vertex4,
			  in_edge2,size-1,index,output,reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  
  /*	Else the edge is not consecutive, and it is sufficiently
	far away, for us not to make a conclusion at this time.
	So we can take off a triangle and recursively call this
	function.
  */
  else
    {
      vertex4 = Adjacent(in_edge2,in_edge1,index,size);
      Output_Tri(in_edge1,in_edge2,vertex4,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_List(in_edge1,index,&size);
      Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
			  vertex4,size-1,index,output,!reversed,face_id,
			  where,color1,color2,color3);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
}

///	Triangulate:
void CustomStripifier::Triangulate(int out_edge1,int out_edge2,int in_edge1,
			int in_edge2,int size,int *index,
			FILE *output,int reversed,int face_id, int where,
			int color1, int color2,int color3)
{
  /*	We have the info we need to triangulate a polygon */
  
  if (size == 4)
    Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
		     index,reversed,where);
  else
    Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
			index,output,reversed,face_id,where,color1,color2,color3);
}

///	Non_Blind_Triangulate:
void CustomStripifier::Non_Blind_Triangulate(int size,int *index,
			   FILE *output,int next_face_id,int face_id,int where,
                           int color1,int color2,int color3)
{
  int id1,id2,id3;
  int nedge1,nedge2;
  int reversed;
  /*	We have a polygon that has to be triangulated and we cannot
	do it blindly, ie we will try to come out on the edge that
	has the least number of adjacencies
  */
  
  Last_Edge(&id1,&id2,&id3,0);
  /*	Find the edge that is adjacent to the new face ,
	also return whether the orientation is reversed in the
	face of the input edge, which is id2 and id3.
  */
  if (next_face_id == -1)
    {
      printf("The face is -1 and the size is %d\n",size);
      exit(0);
    }
  
  reversed = Get_Edge(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
  /* Do the triangulation */
  
  /* If reversed is -1, the input edge is not in the polygon, 
     therefore we can have the input edge to be anything we like, 
     since we are at the beginning of a strip
  */
  Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
	      face_id, where,color1,color2,color3);
}

///	Blind_Triangulate:
void CustomStripifier::Blind_Triangulate(int size, int *index, BOOL begin, int where)
{
  /*	save sides in temp array, we need it so we know
	about swaps.
  */
  int mode, decreasing,increasing,e1,e2,e3;
  
  /*	Rearrange the index list so that the input edge is first
   */
  if (!begin)
    Rearrange_Index(index,size);
  
  /*	We are given a polygon of more than 3 sides
	and want to triangulate it. We will output the
	triangles to the output file.
  */
  
  /*	Find where the input edge is in the input list */
  Last_Edge(&e1,&e2,&e3,0);
  if (( (!begin) && (*(index) == e2) ) || (begin))
    {
      Output_Tri(*(index+0),*(index+1),*(index+size-1),where);
      /*	If we have a quad, (chances are yes), then we know that
		we can just add one diagonal and be done. (divide the
		quad into 2 triangles.
      */
      if (size == 4)
        {
	  Output_Tri(*(index+1),*(index+size-1),*(index+2),where);
	  return;
        }
      increasing = 1;
      mode = 1;
      
    }
  else if (!begin)
    {
      Output_Tri(*(index+1),*(index+0),*(index+size-1),where);
      if (size == 4)
        {
	  Output_Tri(*(index+0),*(index+size-1),*(index+2),where);
	  return;
        }
      Output_Tri(*(index+0),*(index+size-1),*(index+2),where);
      increasing = 2;
      mode = 0;
    }
  if (size != 4)
    {
      /*	We do not have a quad, we have something bigger. */
      decreasing = size - 1;		
      do
	{
	  /*	Will be alternating diagonals, so we will be increasing
		and decreasing around the polygon.
	  */
	  if (mode)
	    {
	      Output_Tri(*(index+increasing),*(index+decreasing),
			 *(index+increasing+1),where);
	      increasing++;
	    }
	  else
	    {
	      Output_Tri(*(index+decreasing),*(index+increasing),
			 *(index+decreasing-1),where);
	      decreasing--;
	    }
	  mode = !mode;
	} while ((decreasing - increasing) >= 2);
      
    }
}

///	Get_Edge:
int CustomStripifier::Get_Edge(int *edge1,int *edge2,int *index,int face_id,
	     int size, int id1, int id2)
{
  /*	Put the edge that is adjacent to face_id into edge1
	and edge2. For each edge see if it is adjacent to
	face_id. Id1 and id2 is the input edge, so see if 
	the orientation is reversed, and save it in reversed.
  */
  register int x;
  int reversed = -1;
  BOOL set = FALSE;
  
  for (x=0; x< size; x++)
    {
      if (x == (size-1))
	{
	  if ((*(index) == id1) && (*(index+size-1)==id2))
	    {
	      if (set)
		return 1;
	      reversed = 1;
	    }
	  else if ((*(index) == id2) && (*(index+size-1)==id1))
	    {
	      if (set)
		return 0;
	      reversed = 0;
	    }
	  
	  if (Look_Up(*(index),*(index+size-1),face_id))
	    {
	      if ( (out1 != -1) && 
		   ( (out1 == *(index)) || 
		     (out1 == *(index+size-1)) ) &&
		   ( (out2 == *(index)) || 
		     (out2 == *(index+size-1)) ))
		{
		  set = TRUE;
		  *edge1 = *(index);
		  *edge2 = *(index+size-1);
		}
	      else if (out1 == -1)
		{
		  set = TRUE;
		  *edge1 = *(index);
		  *edge2 = *(index+size-1);
		}
	      if ((reversed != -1) && (set))  
		return reversed;
	    }
	}		
      else
	{
	  if ((*(index+x) == id1) && (*(index+x+1)==id2))
	    {
	      if (set)
		return 0;
	      reversed = 0;
	    }
	  else if ((*(index+x) == id2) && (*(index+x+1)==id1))
	    {
	      if (set)
		return 1;
	      reversed = 1;
	    }
	  
	  if (Look_Up(*(index+x),*(index+x+1),face_id))
	    {
	      if ( (out1 != -1) &&
		   ( (out1 == *(index+x)) ||
		     (out1 == *(index+x+1)) ) &&
		   ((out2 == *(index+x)) ||
		    (out2 == *(index+x+1))))
		{
		  set = TRUE;
		  *edge1 = *(index+x);
		  *edge2 = *(index+x+1);
		}
	      else if (out1 == -1)
		{
		  set = TRUE;
		  *edge1 = *(index+x);
		  *edge2 = *(index+x + 1);
		}
	      if ((reversed != -1) && (set))
		return reversed;
	    }
	}
    }			
  if ((x == size) && (reversed != -1))
    {
      /*	Could not find the output edge */
      printf("Error in the Lookup %d %d %d %d %d %d %d %d\n",
	     face_id,id1,id2,reversed,*edge1,*edge2,out1,out2);
      exit(0);
    }
  return reversed;
}

///	Udate_Face:
void CustomStripifier::Update_Face(int *next_bucket, int *min_face, int face_id, int *e1,
			int *e2,int temp1,int temp2,int *ties)
{
  /*	We have a face id that needs to be decremented.
	We have to determine where it is in the structure,
	so that we can decrement it.
  */
  /*	The number of adjacencies may have changed, so to locate
	it may be a little tricky. However we know that the number
	of adjacencies is less than or equal to the original number
	of adjacencies,
  */
  int y,size;
  ListHead *pListHead;
  PF_FACES temp = NULL;
  PLISTINFO lpListInfo;
  static int each_poly = 0;
  BOOL there = FALSE;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  /*	Check each edge of the face and tally the number of adjacent
	polygons to this face. 
  */	      		
  if ( temp != NULL )
    {
      /*	Size of the polygon */
      size = temp->nPolSize;
      /*  We did it already */
      if (size == 1)
	return;
      for (y = 0; y< size; y++)
	{
	  /*	If we are doing partial triangulation, we must check
		to see whether the edge is still there in the polygon,
		since we might have done a portion of the polygon
		and saved the rest for later.
	  */
	  if (y != (size-1))
	    {
	      if( ((temp1 == *(temp->pPolygon+y)) &&
		   (temp2 ==*(temp->pPolygon+y+1))) ||
		  ((temp2 == *(temp->pPolygon+y)) &&
		   (temp1 ==*(temp->pPolygon+y+1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	  else
	    {
	      if( ((temp1 == *(temp->pPolygon)) &&
		   (temp2 == *(temp->pPolygon+size-1))) ||
		  ((temp2 == *(temp->pPolygon)) &&
		   (temp1 ==*(temp->pPolygon+size-1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	}
      
      if (!there)
	/*	Original edge was already used, we cannot use this polygon */
	return;
      
      /*	We have a starting point to start our search to locate
		this polygon. 
      */
      
      /*	Check to see if this polygon was done */
      lpListInfo = Done(face_id,&y);
      
      if (lpListInfo == NULL)
	return;
      
      /*  Was not done, but there is an error in the adjacency calculations */
      if (y == 0)
	{
	  printf("There is an error in finding the adjacencies\n");
	  exit(0);
	}
      
      /*	Now put the face in the proper bucket depending on tally. */
      /*	First add it to the new bucket, then remove it from the old */
      Add_Sgi_Adj(y-1,face_id);
      RemoveList(array[y],lpListInfo);
      
      /*	Save it if it was the smallest seen so far since then
		it will be the next face 
		Here we will have different options depending on
		what we want for resolving ties:
		1) First one we see we will use
		2) Random resolving
		3) Look ahead
		4) Alternating direction
      */
      /*	At a new strip */
      if (*next_bucket == 60)
	*ties = *ties + each_poly;
      /*	Have a tie */
      if (*next_bucket == (y-1))
	{
	  Add_Ties(face_id);
	  each_poly++;
	}
      /*	At a new minimum */
      if (*next_bucket > (y-1))
	{
	  *next_bucket = y-1;
	  *min_face = face_id;
	  *e1 = temp1;
	  *e2 = temp2;
	  each_poly = 0;
	  Clear_Ties();
	  Add_Ties(face_id);
	}
    }
}

///	Delete_Adj:
void CustomStripifier::Delete_Adj(int id1, int id2,int *next_bucket,int *min_face, 
		       int current_face,int *e1,int *e2,int *ties)
{
  /*	Find the face that is adjacent to the edge and is not the
	current face. Delete one adjacency from it. Save the min
	adjacency seen so far.
  */
  register int count=0;
  PF_EDGES temp = NULL;
  ListHead *pListHead;
  int next_face;
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    /*	It could be a new edge that we created. So we can
	exit, since there is not a face adjacent to it.
    */
    return;
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                                        
      
      if (temp == NULL)
	/*	Was a new edge that was created and therefore
		does not have anything adjacent to it
	*/
	return;
    }
  /*	Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return;
  
  /*	Was adjacent to something */
  else
    {
      if (temp->edge[2] == current_face)
	next_face =  temp->edge[1];
      else 
	next_face = temp->edge[2];
    }
  /*	We have the other face adjacent to this edge, it is 
	next_face. Now we need to decrement this faces' adjacencies.
  */
  Update_Face(next_bucket, min_face, next_face,e1,e2,id1,id2,ties);
}

///	Update_Adjacencies:
int CustomStripifier::Update_Adjacencies(int face_id, int *next_bucket, int *e1, int *e2,
		       int *ties)
{
  /*	Give the face with id face_id, we want to decrement
	all the faces that are adjacent to it, since we will
	be deleting face_id from the data structure.
	We will return the face that has the least number
	of adjacencies.
  */
  PF_FACES temp = NULL;
  ListHead *pListHead;
  int size,y,min_face = -1;
  
  *next_bucket = 60;
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  if ( temp == NULL )
    {
      printf("The face was already deleted, there is an error\n");
      exit(0);
    }
  
  /*	Size of the polygon */
  size = temp->nPolSize;
  for (y = 0; y< size; y++)
    {
      if (y != (size-1))
	Delete_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
		   next_bucket,&min_face,face_id,e1,e2,ties);
      else
	Delete_Adj(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
		   next_bucket,&min_face,face_id,e1,e2,ties);
    }
  return (min_face);
}

///	Old_Adj:
int CustomStripifier::Old_Adj(int face_id)
{
  /*	Find the bucket that the face_id is currently in,
	because maybe we will be deleting it. 
  */
  PF_FACES temp = NULL;
  ListHead *pListHead;
  int y;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  if ( temp == NULL )
    {
      printf("The face was already deleted, there is an error\n");
      exit(0);
    }
  
  if (Done(face_id,&y) == NULL)
    {
      printf("There is an error in finding the face\n");
      exit(0);
    }
  return y;
}

///	Number_Adj:
int CustomStripifier::Number_Adj(int id1, int id2, int curr_id)
{
  /*	Given edge whose endpoints are specified by id1 and id2,
	determine how many polygons share this edge and return that
	number minus one (since we do not want to include the polygon
	that the caller has already).
  */
  
  int size,y,count=0;
  PF_EDGES temp = NULL;
  PF_FACES temp2 = NULL;
  ListHead *pListHead;
  BOOL there= FALSE;
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    /*	new edge that was created might not be here */
    return 0;
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                               
      
      if (temp == NULL)
	/*	This edge was not there in the original, which
		mean that we created it in the partial triangulation.
		So it is adjacent to nothing.
	*/
	return 0;
    }
  /*	Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return 0;
  else
    {
      /* It was adjacent to another polygon, but maybe we did this
	 polygon already, and it was done partially so that this edge
	 could have been done
      */
      if (curr_id != temp->edge[1])
	{
	  /* Did we use this polygon already?and it was deleted
	     completely from the structure
	  */
	  pListHead = PolFaces[temp->edge[1]];
	  temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
	  if (Done(temp->edge[1],&size) == NULL)
	    return 0;
	}
      else
	{
	  pListHead = PolFaces[temp->edge[2]];
	  temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
	  if (Done(temp->edge[2],&size)== NULL)
	    return 0;
	}
      
      /* Now we have to check whether it was partially done, before
	 we can say definitely if it is adjacent.
	 Check each edge of the face and tally the number of adjacent
	 polygons to this face. 
      */	      		
      if ( temp2 != NULL )
	{
	  /* Size of the polygon */
	  size = temp2->nPolSize;
	  for (y = 0; y< size; y++)
	    {
	      /* If we are doing partial triangulation, we must check
		 to see whether the edge is still there in the polygon,
		 since we might have done a portion of the polygon
		 and saved the rest for later.
	      */
	      if (y != (size-1))
		{
		  if(((id1 == *(temp2->pPolygon+y)) &&
		      (id2 ==*(temp2->pPolygon+y+1))) ||
		     ((id2 == *(temp2->pPolygon+y)) && 
		      (id1 ==*(temp2->pPolygon+y+1))))
		    /*	edge is still there we are ok */
		    there = TRUE;
		}
	      else
		{
		  if(((id1 == *(temp2->pPolygon)) &&
		      (id2 == *(temp2->pPolygon+size-1))) ||
		     ((id2 == *(temp2->pPolygon)) && 
		      (id1 ==*(temp2->pPolygon+size-1))))
		    /*	edge is still there we are ok */
		    there = TRUE;
		}
	    }
	}
      
      if (there )
	return 1;
      return 0;
    }
}

///	Min_Adj:
int CustomStripifier::Min_Adj(int id)
{
  /*	Used for the lookahead to break ties. It will
	return the minimum adjacency found at this face.
  */
  int y,numverts,t,x=60;
  PF_FACES temp=NULL;
  ListHead *pListHead;
  
  /*	If polygon was used then we can't use this face */
  if (Done(id,&y) == NULL)
    return 60;
  
  /*	It was not used already */
  pListHead = PolFaces[id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  if ( temp != NULL )
    {
      numverts = temp->nPolSize;
      for (y = 0; y< numverts; y++)
	{
	  if (y != (numverts-1))
	    t = Number_Adj(*(temp->pPolygon+y),*(temp->pPolygon+y+1),id);
	  else
	    t = Number_Adj(*(temp->pPolygon),*(temp->pPolygon+(numverts-1)),id);
	  if (t < x)
	    x = t;
	}
    }
  if (x == -1)
    {
      printf("Error in the look\n");
      exit(0);
    }
  return x;
}

///	Edje_Least:
void CustomStripifier::Edge_Least(int *index,int *new1,int *new2,int face_id,int size)
{
  /*   We had a polygon without an input edge and now we re going to pick one
       of the edges with the least number of adjacencies to be the input
       edge
  */
  register int x,value,smallest=60;
  
  for (x = 0; x<size; x++)
    {
      if (x != (size -1) )
	value = Number_Adj(*(index+x),*(index+x+1),face_id);
      else 
	value = Number_Adj(*(index),*(index+size-1),face_id);
      if (value < smallest)
        {
	  smallest = value;
	  if (x != (size -1))
            {
	      *new1 = *(index+x);
	      *new2 = *(index+x+1);
            }
	  else
            {
	      *new1 = *(index);
	      *new2 = *(index+size-1);
            }
        }
    }
  if ((smallest == 60) || (smallest < 0))
    {
      printf("There is an error in getting the least edge\n");
      exit(0);
    }
}

///	Check_In_Polygon:
void CustomStripifier::Check_In_Polygon(int face_id, int *min, int size)
{
  /*  Check to see the adjacencies by going into a polygon that has
      greater than 4 sides.
  */
  
  ListHead *pListHead;
  PF_FACES temp;
  int y,id1,id2,id3,x=0,z=0;
  int saved[2];
  int big_saved[60];
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  /*   Get the input edge that we came in on */
  Last_Edge(&id1,&id2,&id3,0);
  
  /*  Find the number of adjacencies to the edges that are adjacent
      to the input edge.
  */
  for (y=0; y< size; y++)
    {
      if (y != (size-1))
        {
	  if (((*(temp->pPolygon+y) == id2) && (*(temp->pPolygon+y+1) != id3))
	      || ((*(temp->pPolygon+y) == id3) && (*(temp->pPolygon+y+1) != id2)))
            {
	      saved[x++] = Number_Adj(*(temp->pPolygon+y),
				      *(temp->pPolygon+y+1),face_id);
	      big_saved[z++] = saved[x-1];
            }
	  else
	    big_saved[z++] = Number_Adj(*(temp->pPolygon+y),
					*(temp->pPolygon+y+1),face_id);
        }
      else
        {
	  if (((*(temp->pPolygon) == id2) &&
	       (*(temp->pPolygon+size-1) != id3)) ||
	      ((*(temp->pPolygon) == id3) &&
	       (*(temp->pPolygon+size-1) != id2)))
            {
	      saved[x++] = Number_Adj(*(temp->pPolygon),
				      *(temp->pPolygon+size-1),face_id);
	      big_saved[z++] = saved[x-1];
            }
	  else
	    big_saved[z++] = Number_Adj(*(temp->pPolygon),
					*(temp->pPolygon+size-1),face_id);
        }
    }
  /*  There was an input edge */
  if (x == 2)
    {
      if (saved[0] < saved[1])
	/*  Count the polygon that we will be cutting as another adjacency*/
	*min = saved[0] + 1;
      else
	*min = saved[1] + 1;
    }
  /*  There was not an input edge */
  else
    {
      if (z != size)
        {
	  printf("There is an error with the z %d %d\n",size,z);
	  exit(0);
        }
      *min = 60;
      for (x = 0; x < size; x++)
        {
	  if (*min > big_saved[x])
	    *min = big_saved[x];
        }
    }
}

///	New_Face:
void CustomStripifier::New_Face (int face_id, int v1, int v2, int v3)
{
  /*	We want to change the face that was face_id, we will
	change it to a triangle, since the rest of the polygon
	was already outputtted
  */
  ListHead *pListHead;
  PF_FACES temp = NULL;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0);
  /*	Check each edge of the face and tally the number of adjacent
	polygons to this face. 
  */	      		
  if ( temp != NULL )
    {
      /*	Size of the polygon */
      if (temp->nPolSize != 4)
	{
	  printf("There is a miscalculation in the partial\n");
	  exit (0);
	}
      temp->nPolSize = 3;
      *(temp->pPolygon) = v1;
      *(temp->pPolygon+1) = v2;
      *(temp->pPolygon+2) = v3;
    }
}

///	New_Size_Face:
void CustomStripifier::New_Size_Face(int face_id)
{
  /*	We want to change the face that was face_id, we will
	change it to a triangle, since the rest of the polygon
	was already outputtted
  */
  ListHead *pListHead;
  PF_FACES temp = NULL;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  /*	Check each edge of the face and tally the number of adjacent
	polygons to this face. 
  */	      		
  if ( temp != NULL )
    (temp->nPolSize)--;
  else
    printf("There is an error in updating the size\n");
}

///	Check_In_Quad:
void  CustomStripifier::Check_In_Quad(int face_id,int *min)
{
  /*   Check to see what the adjacencies are for the polygons that
       are inside the quad, ie the 2 triangles that we can form.
  */
  ListHead *pListHead;
  int y,id1,id2,id3,x=0;
  int saved[4];
  PF_FACES temp;
  register int size = 4;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  /*   Get the input edge that we came in on */
  Last_Edge(&id1,&id2,&id3,0);
  
  /*    Now find the adjacencies for the inside triangles */
  for (y = 0; y< size; y++)
    {
      /*     Will not do this if the edge is the input edge */
      if (y != (size-1))
	{
	  if ((((*(temp->pPolygon+y) == id2) && 
		(*(temp->pPolygon+y+1) == id3))) ||
	      (((*(temp->pPolygon+y) == id3) &&
		(*(temp->pPolygon+y+1) == id2))))
	    saved[x++] = -1;
	  else
	    {
	      if (x == 4)
		{
		  printf("There is an error in the check in quad \n");
		  exit(0);
		}
	      /*    Save the number of Adjacent Polygons to this edge */
	      saved[x++] = Number_Adj(*(temp->pPolygon+y),
				      *(temp->pPolygon+y+1),face_id);
	    }
	}
      else if ((((*(temp->pPolygon) == id2) && 
		 (*(temp->pPolygon+size-1) == id3))) ||
	       (((*(temp->pPolygon) == id3) &&
		 (*(temp->pPolygon+size-1) == id2))) )
	saved[x++] = -1;
      else
        {
	  if (x == 4)
	    {
	      printf("There is an error in the check in quad \n");
	      exit(0);
	    }
	  /*    Save the number of Adjacent Polygons to this edge */
	  saved[x++] = Number_Adj(*(temp->pPolygon),
				  *(temp->pPolygon+size-1),face_id);
	  
        }
    }
  if (x != 4)
    {
      printf("Did not enter all the values %d \n",x);
      exit(0);
    }
  
  *min = 10;
  for (x=0; x<4; x++)
    {
      if (x!= 3)
	{
	  if ((saved[x] != -1) && (saved[x+1] != -1) && 
	      ((saved[x] + saved[x+1]) < *min))
	    *min = saved[x] + saved[x+1];
	}
      else
	{
	  if ((saved[0] != -1) && (saved[x] != -1) &&
	      ((saved[x] + saved[0]) < *min))
	    *min = saved[0] + saved[x];
	}
    }
}

///	Get_Output_Edge:
int CustomStripifier::Get_Output_Edge(int face_id, int size, int *index,int id2,int id3)
{
  /*  Return the vertex adjacent to either input1 or input2 that
      is adjacent to the least number of polygons on the edge that
      is shared with either input1 or input2.
  */
  register int x=0,y;
  int saved[2];
  int edges[2][1];
  
  for (y = 0; y < size; y++)
    {
      if (y != (size-1))
        {
	  if (((*(index+y) == id2) && (*(index+y+1) != id3))
	      || ((*(index+y) == id3) && (*(index+y+1) != id2)))
            {
	      saved[x++] = Number_Adj(*(index+y),*(index+y+1),face_id);
	      edges[x-1][0] = *(index+y+1);
            }
	  else if (y != 0)
            {
	      if (( (*(index+y) == id2) && (*(index+y-1) != id3) ) ||
		  ( (*(index+y) == id3) && (*(index+y-1) != id2)) )
                {
		  saved[x++] = Number_Adj(*(index+y),*(index+y-1),face_id);
		  edges[x-1][0] = *(index+y-1);
                }
            }
	  else if (y == 0)
            {
	      if (( (*(index) == id2) && (*(index+size-1) != id3) ) ||
		  ( (*(index) == id3) && (*(index+size-1) != id2)) )
                {
		  saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
		  edges[x-1][0] = *(index+size-1);
                }
            }
	  
        }
      else
        {
	  if (((*(index+size-1) == id2) && (*(index) != id3))
	      || ((*(index+size-1) == id3) && (*(index) != id2)))
            {
	      saved[x++] = Number_Adj(*(index),*(index+size-1),face_id);
	      edges[x-1][0] = *(index);
            }
	  
	  if (( (*(index+size-1) == id2) && (*(index+y-1) != id3) ) ||
	      ( (*(index+size-1) == id3) && (*(index+y-1) != id2)) )
	    {
	      saved[x++] = Number_Adj(*(index+size-1),*(index+y-1),face_id);
	      edges[x-1][0] = *(index+y-1);
	    }
        }
    }
  if ((x != 2))
    {
      printf("There is an error in getting the input edge %d \n",x);
      exit(0);
    }
  if (saved[0] < saved[1])
    return edges[0][0];
  else
    return edges[1][0];
  
}

///	Get_Input_Edge:
void CustomStripifier::Get_Input_Edge(int *index,int id1,int id2,int id3,
		    int *new1,int *new2,int size,int face_id)
{
  /*  We had a polygon without an input edge and now we are going to pick one
      as the input edge. The last triangle was id1,id2,id3, we will try to
      get an edge to have something in common with one of those vertices, 
      otherwise we will pick the edge with the least number of adjacencies.
  */
  
  register int x;
  int saved[3];
  
  saved[0] = -1;
  saved[1] = -1;
  saved[2] = -1;
  
  /*  Go through the edges to see if there is one in common with one
      of the vertices of the last triangle that we had, preferably id2 or
      id3 since those are the last 2 things in the stack of size 2.
  */
  for (x=0; x< size; x++)
    {
      if (*(index+x) == id1)
        {
	  if (x != (size-1))
	    saved[0] = *(index+x+1);
	  else
	    saved[0] = *(index);
        }
      
      if (*(index+x) == id2)
        {
	  if (x != (size-1))
	    saved[1] = *(index+x+1);
	  else
	    saved[1] = *(index);
        }
      
      if (*(index+x) == id3)
        {
	  if (x != (size -1))
	    saved[2] = *(index+x+1);
	  else
	    saved[2] = *(index);
        }
    }
  /*  Now see what we saved */
  if (saved[2] != -1)
    {
      *new1 = id3;
      *new2 = saved[2];
      return;
    }
  else if (saved[1] != -1)
    {
      *new1 = id2;
      *new2 = saved[1];
      return;
    }
  else if (saved[0] != -1)
    {
      *new1 = id1;
      *new2 = saved[0];
      return;
    }
  /*  We did not find anything so get the edge with the 
      least number of adjacencies
  */
  Edge_Least(index,new1,new2,face_id,size);
  
}

///	Find_Face:
int CustomStripifier::Find_Face(int current_face, int id1, int id2, int *bucket)
{
  /*	Find the face that is adjacent to the edge and is not the
	current face.
  */
  register int size,y,count=0;    
  PF_EDGES temp = NULL;
  PF_FACES temp2 = NULL;
  ListHead *pListHead;
  int next_face;
  BOOL there = FALSE;
  
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  /*  The input edge was a new edge */
  if (temp == NULL)
    return -1;
  
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                                   
      
      /*  The input edge was a new edge */
      if (temp == NULL)
	return -1;
    }
  /*	Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return -1;
  else
    {
      if (temp->edge[2] == current_face)
	next_face =  temp->edge[1];
      else 
	next_face = temp->edge[2];
    }
  /* We have the other face adjacent to this edge, it is 
     next_face. 
  */
  pListHead = PolFaces[next_face];
  temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  /* See if the face was already deleted, and where
     it is if it was not
  */
  
  if (Done(next_face,bucket) == NULL)
    return -1;
  
  /*  Make sure the edge is still in this polygon, and that it is not
      done
  */
  /* Size of the polygon */
  size = temp2->nPolSize;
  for (y = 0; y< size; y++)
    {
      /*  Make sure that the edge is still in the
	  polygon and was not deleted, because if the edge was
	  deleted, then we used it already.
      */
      if (y != (size-1))
	{
	  if( ((id1 == *(temp2->pPolygon+y)) && (id2 ==*(temp2->pPolygon+y+1)))
	      || ((id2 == *(temp2->pPolygon+y)) && (id1 ==*(temp2->pPolygon+y+1))))
	    /*	edge is still there we are ok */
	    there = TRUE;
	}
      else
	{		
	  if(((id1 == *(temp2->pPolygon)) && (id2 ==*(temp2->pPolygon+size-1))) ||
	     ((id2 == *(temp2->pPolygon)) && (id1 ==*(temp2->pPolygon+size-1))))
	    /*	edge is still there we are ok */
	    there = TRUE;
	}
    }
  
  if (!there)
    /*	Edge already used and deleted from the polygon*/
    return -1;
  else
    return next_face;
}

///	Look_Up:
BOOL CustomStripifier::Look_Up(int id1,int id2,int face_id)
{
  /*	See if the endpoints of the edge specified by id1 and id2
	are adjacent to the face with face_id 
  */
  register int count = 0;
  PF_EDGES temp  = NULL;
  ListHead *pListHead;
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    /*	Was a new edge that we created */
    return 0;
  
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                                  
      
      if (temp == NULL)
	/*	Was a new edge that we created */
	return 0;
    }
  /*	Was not adjacent to anything else except itself */
  if ((temp->edge[2] == face_id) || (temp->edge[1] == face_id))
    {
      /*	Edge was adjacent to face, make sure that edge is 
		still there
      */
      if (Exist(face_id,id1,id2))
	return 1;
      else
	return 0;
    }
  else
    return 0;
}

///	Add_Id_Strips:
void CustomStripifier::Add_Id_Strips(int id, int where)
{
  /*    Just save the triangle for later  */
  P_STRIPS pfNode;
  
  pfNode = (P_STRIPS) malloc(sizeof(Strips) );
  if ( pfNode )
    {
      pfNode->face_id = id;
      if (where == 1)
	AddTail(strips[0],(PLISTINFO) pfNode);
      /* We are backtracking in the strip */
      else
	AddHead(strips[0],(PLISTINFO) pfNode);
    }
  else
    {
      printf("There is not enough memory to allocate for the strips\n");
      exit(0);
    }
}

///	Num_Adj:
int CustomStripifier::Num_Adj(int id1, int id2)
{
  /*   Given edge whose endpoints are specified by id1 and id2,
       determine how many polygons share this edge and return that
       number minus one (since we do not want to include the polygon
       that the caller has already).
  */
  
  PF_EDGES temp = NULL;
  ListHead *pListHead;
  register count=-1;
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    {
      printf("There is an error in the creation of the table \n");
      exit(0);
    }
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                                    
      
      if (temp == NULL)
	{
	  printf("There is an error in the creation of the table\n");
	  exit(0);
	}
    }
  /*      Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return 0;
  return 1;
}

///	Add_Sgi_Adj:
void CustomStripifier::Add_Sgi_Adj(int bucket,int face_id)
{
  /*   This routine will add the face to the proper bucket,
       depending on how many faces are adjacent to it (what the
       value bucket should be).
  */
  P_ADJACENCIES pfNode;
  
  pfNode = (P_ADJACENCIES) malloc(sizeof(ADJACENCIES) );
  if ( pfNode )
    {
      pfNode->face_id = face_id;
      AddHead(array[bucket],(PLISTINFO) pfNode);
      face_array[face_id].bucket = bucket;
      face_array[face_id].pfNode = pfNode;
      face_array[face_id].head = array[bucket];
    }
  else
    {
      printf("Out of memory for the SGI adj list!\n");
      exit(0);
    }
}

///	Find_Adjacencies:
void CustomStripifier::Find_Adjacencies(int num_faces)
{
  register int	x,y;
  register int	numverts;
  PF_FACES			temp	=NULL;
  ListHead*			pListHead;
  
  /*   Fill in the adjacencies data structure for all the faces */
  for (x=0;x<num_faces;x++)
  {
    pListHead = PolFaces[x];
    temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
    if ( temp != NULL )
		{
	  	numverts = temp->nPolSize;
	  	if (numverts != 1)
	    {
	      for (y = 0; y< numverts; y++)
				{
		  		if (y != (numverts-1))
		    		Add_AdjEdge(*(temp->pPolygon+y),
												*(temp->pPolygon+y+1),x,y);
		  
		  		else 
		    		Add_AdjEdge(*(temp->pPolygon),
												*(temp->pPolygon+(numverts-1)),x,numverts-1);
		  
				}
	    }
	  	temp = NULL;
		}
	}
}

///	Clear_Ties:
void CustomStripifier::Clear_Ties()
{
  /*	Clear the buffer, because we do not have the tie
	any more that we had before */
  last = 0;
}

///	Add_Ties:
void CustomStripifier::Add_Ties(int id)
{
  /*	We have a tie to add to the buffer */
  ties_array[last++] = id;
}

///	Alternate_Tie:
int CustomStripifier::Alternate_Tie()
{
  /*	Alternate in what we choose to break the tie 
	We are just alternating between the first and
	second thing that we found
  */
  static int x = 0;
  register int t;
  
  t = ties_array[x];
  x++;
  if (x == 2)
    x = 0;
  return t;
}

///	Random_Tie:
int CustomStripifier::Random_Tie()
{
  /*	Randomly choose the next face with which
	to break the tie
  */
  register int num;
  
  num = rand();
  while (num >= last)
    num = num/20;
  return (ties_array[num]);
}

///	Look_Ahead:
int CustomStripifier::Look_Ahead(int id)
{
  /*	Look ahead at this face and save the minimum
	adjacency of all the faces that are adjacent to
	this face.
  */
  return Min_Adj(id);
}

///	Random_Look:
int CustomStripifier::Random_Look(int id[],int count)
{
  /*	We had a tie within a tie in the lookahead, 
	break it randomly 
  */
  register int num;
  
  num = rand();
  while (num >= count)
    num = num/20;
  return (id[num]);
}

///	Look_Ahead_Tie:
int CustomStripifier::Look_Ahead_Tie()
{
  /*	Look ahead and find the face to go to that
	will give the least number of adjacencies
  */
  int id[60],t,x,f=0,min = 60;
  
  for (x = 0; x < last; x++)
    {
      t = Look_Ahead(ties_array[x]);
      /*	We have a tie */
      if (t == min)
	id[f++] = ties_array[x];
      if (t < min)
	{
	  f = 0;
	  min = t;
	  id[f++] = ties_array[x];
	}
    }
  /*	No tie within the tie */
  if ( f == 1)
    return id[0];
  /*	Or ties, but we are at the end of strips */
  if (min == 0)
    return id[0];
  return (Random_Look(id,f));
}

///	Sequential_Tri:
int CustomStripifier::Sequential_Tri(int *index)
{
  /*  We have a triangle and need to break the ties at it.
      We will choose the edge that is sequential. There
      is definitely one since we know we have a triangle
      and that there is a tie and there are only 2 edges
      for the tie.
  */
  int reversed,e1,e2,e3,output1,output2,output3,output4;
  
  /*  e2 and e3 are the input edge to the triangle */
  Last_Edge(&e1,&e2,&e3,0);
  
  if ((e2 == 0) && (e3 == 0))
    /*  Starting the strip, don't need to do this */
    return ties_array[0];
  
  /*  For the 2 ties find the edge adjacent to face id */
  reversed = Get_EdgeEx(&output1,&output2,index,ties_array[0],3,0,0);
  reversed = Get_EdgeEx(&output3,&output4,index,ties_array[1],3,0,0);
  
  if ((output1 == e3) || (output2 == e3))
    return ties_array[0];
  if ((output3 == e3) || (output4 == e3))
    return ties_array[1];
  printf("There is an error trying to break sequential triangle \n");
  return -1;
}

///	Sequential_Quad:
int CustomStripifier::Sequential_Quad(int *index,	int triangulate)
{
  /*  We have a quad that need to break its ties, we will try
      and choose a side that is sequential, otherwise use lookahead
  */
  int reversed,output1,output2,x,e1,e2,e3; 
  
  /*  e2 and e3 are the input edge to the quad */
  Last_Edge(&e1,&e2,&e3,0);
  
  /*  No input edge */
  if ((e2 == 0) && (e3 == 0))
    return ties_array[0];
  
  /*  Go through the ties and see if there is a sequential one */
  for (x = 0; x < last; x++)
    {
      reversed = Get_EdgeEx(&output1,&output2,index,ties_array[x],4,0,0);
      /*  Partial and whole triangulation will have different requirements */
      if (((output1 == e3) || (output2 == e3)) && (triangulate == PARTIAL))
	return ties_array[x];
      if (((output1 != e3) && (output1 != e2) &&
	   (output2 != e3) && (output2 != e2)))
	return ties_array[x];
    }
  /*  There was not a tie that was sequential */
  return Look_Ahead_Tie();
}

///	Whole_Output:
void CustomStripifier::Whole_Output(int in1, int *index, int size, int *out1, int *out2)
{
  /*  Used to sequentially break ties in the whole triangulation for polygons
      greater than 4 sides. We will find the output edge that is good
      for sequential triangulation.
  */
  
  int half;
  
  /*  Put the input edge first in the list */
  Rearrange_IndexEx(index,size);
  
  if (!(EVEN(size)))
    {
      if (*(index) == in1)
	half = size/2 ;
      else
	half = size/2 +1;
    }
  else
    half = size/2;
  
  *out1 = *(index+half);
  *out2 = *(index+half+1);
}

///	Sequential_Poly:
int CustomStripifier::Sequential_Poly(int size, int *index, int triangulate)
{
  /*  We have a polygon of greater than 4 sides and wish to break the
      tie in the most sequential manner.
  */
  
  int x,reversed,output1,output2,e1,e2,e3,saved1=-1,saved2=-1,output3,output4;
  
  /*  e2 and e3 are the input edge to the quad */
  Last_Edge(&e1,&e2,&e3,0);
  
  /*  If we are using whole, find the output edge that is sequential */
  if (triangulate == WHOLE)
    Whole_Output(e2,index,size,&output3,&output4);
  
  /*  No input edge */
  if ((e2 == 0) && (e3 == 0))
    return ties_array[0];
  
  for (x = 0; x < last ; x++)
    {
      reversed = Get_EdgeEx(&output1,&output2,index,ties_array[x],size,0,0);
      /*  Partial that can be removed in just one triangle */
      if (((output1 == e3) || (output2 == e3)) && (triangulate == PARTIAL))
	saved1 = ties_array[x];
      /*  Partial removed in more than one triangle */
      if ((output1 != e3) && (output1 != e2) &&
	  (output2 != e3) && (output2 != e2) &&
	  (triangulate == PARTIAL) && (saved2 != -1))
	saved2 = ties_array[x];
      /*  Whole is not so easy, since the whole polygon must be done. Given
	  an input edge there is only one way to come out, approximately half
	  way around the polygon.
      */
      if (((output1 == output3) && (output2 == output4)) ||
	  ((output1 == output4) && (output2 == output3)) &&
	  (triangulate == WHOLE))
	return ties_array[x];
    }
  
  if (saved1 != -1)
    return saved1;
  if (saved2 != -1)
    return saved2;
  
  /*  There was not a tie that was sequential */
  return Look_Ahead_Tie();
}

///	Sequential_Tie:
int CustomStripifier::Sequential_Tie(int face_id,int triangulate)
{
  /*  Break the tie by choosing the face that will
      not give us a swap and is sequential. If there
      is not one, then do the lookahead to break the
      tie.
  */
  /*  Separate into 3 cases for simplicity, if the current
      polygon has 3 sides, 4 sides or if the sides were 
      greater. We can do the smaller cases faster, so that
      is why I separated the cases.
  */
  
  ListHead *pListFace;
  PF_FACES face;
  
  /*	Get the polygon with id face_id */
  pListFace  = PolFaces[face_id];
  face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
  
  if (face->nPolSize == 3)
    return(Sequential_Tri(face->pPolygon));
  if (face->nPolSize == 4)
    return(Sequential_Quad(face->pPolygon,triangulate));
  else
    return(Sequential_Poly(face->nPolSize,face->pPolygon,triangulate));
  
}

///	Get_Next_Face:
int CustomStripifier::Get_Next_Face(int t, int face_id, int triangulate)
{
  /*	Get the next face depending on what
	the user specified
  */
  
  /*	Did not have a tie, don't do anything */
  if (last == 1)
    return(ties_array[0]);
  if (t == RANDOM)
    return Random_Tie();
  if (t == ALTERNA)
    return Alternate_Tie();
  if (t == LOOK)
    return Look_Ahead_Tie();
  if (t == SEQUENTIAL)
    return Sequential_Tie(face_id,triangulate);
  
  printf("Illegal option specified for ties, using first \n");
  return (ties_array[0]);
}

///	new_vertex:
BOOL CustomStripifier::new_vertex(double difference, int id1,int id2,
		       struct vert_struct *n)
{
  /*   Is the difference between id1 and id2 (2 normal vertices that
       mapped to the same vertex) greater than the
       threshold that was specified?
  */
  struct vert_struct *pn1,*pn2;
  double dot_product;
  double distance1, distance2,distance;
  double rad;
  char arg1[100];
  char arg2[100];
  
  pn1 = n + id1;
  pn2 = n + id2;
  
  dot_product = ((pn1->x) * (pn2->x)) +
    ((pn1->y) * (pn2->y)) +
    ((pn1->z) * (pn2->z));
  /*   Get the absolute value */
  if (dot_product < 0)
    dot_product = dot_product * -1;
  
  distance1 = sqrt( (pn1->x * pn1->x) +
		    (pn1->y * pn1->y) +
		    (pn1->z * pn1->z) );
  distance2 = sqrt( (pn2->x * pn2->x) +
		    (pn2->y * pn2->y) +
		    (pn2->z * pn2->z) );
  distance = distance1 * distance2;
  
  rad = acos((double)dot_product/(double)distance);
  /*   convert to degrees */
  rad = (180 * rad)/GEO_PI;
  
  if ( rad <= difference)
    return FALSE;
  
  /*   double checking because of imprecision with floating
       point acos function
  */
  sprintf( arg1,"%.5f", rad );
  sprintf( arg2,"%.5f", difference );
  if ( strcmp( arg1, arg2 ) <=0 )
    return( FALSE );
  if ( rad <= difference)
    return FALSE;
  else 
    return TRUE;
}

///	Check_VN:
BOOL CustomStripifier::Check_VN(int vertex,int normal, struct vert_added *added)
{
  /*   Check to see if we already added this vertex and normal */
  register int x,n;
  
  n = (added+vertex)->num;
  for (x = 0; x < n; x++)
    {
      if (*((added+vertex)->normal+x) == normal)
	return TRUE;
    }
  return FALSE;
}

///	norm_array:
BOOL CustomStripifier::norm_array(int id, int vertex, double normal_difference,
                struct vert_struct *n, int num_vert)
{
  static int last;
  static struct vert_added *added;
  register int x;
  static BOOL first = TRUE;
  
  if (first)
    {
      /*   This is the first time that we are in here, so we will allocate
	   a structure that will save the vertices that we added, so that we
	   do not add the same thing twice
      */
      first = FALSE;
      added = (struct vert_added *) malloc (sizeof (struct vert_added ) * num_vert);
      /*   The number of vertices added for each vertex must be initialized to
	   zero
      */
      for (x = 0; x < num_vert; x++)
	(added+x)->num = 0;
    }
  
  if (vertex)
    /*   Set the pointer to the vertex, we will be calling again with the
	 normal to fill it with
    */
    last = id;
  else
    {    
      /*   Fill the pointer with the id of the normal */
      if (*(vert_norms + last) == 0)
	*(vert_norms + last) = id;
      else if ((*(vert_norms + last) != id) && ((int)normal_difference != 360))
	{
	  /*   difference is big enough, we need to create a new vertex */
	  if (new_vertex(normal_difference,id,*(vert_norms + last),n))
	    {
	      /*  First check to see if we added this vertex and normal already */
	      if (Check_VN(last,id,added))
		return FALSE;
	      /*  OK, create the new vertex, and have its id = the number of 
		  vertices and its normal what we have here
	      */
	      vert_norms = (int *)realloc(vert_norms, sizeof(int) * (num_vert + 1));
	      if (!vert_norms)
		{
		  printf("Allocation error - aborting\n");
		  exit(1);
		}
	      *(vert_norms + num_vert) = id;
	      /*   We created a new vertex, now put it in our added structure so
		   we do not add the same thing twice
	      */
	      (added+last)->num = (added+last)->num + 1;
	      if ((added+last)->num == 1)
		{
		  /*   First time */
		  (added+last)->normal =  (int *) malloc (sizeof (int ) * 1);
		  *((added+last)->normal) =  id;
		}
	      else
		{
		  /*   Not the first time, reallocate space */
		  (added+last)->normal = (int *)realloc((added+last)->normal, sizeof(int) * (added+last)->num);
		  *((added+last)->normal+((added+last)->num-1)) = id;
		}
	      return TRUE;
	    }
	}
    }
  return FALSE;
}

///	add_texture:
void CustomStripifier::add_texture(int id,BOOL vertex)
{
  /*   Save the texture with its vertex for future use when outputting */
  static int last;
  
  if (vertex)
    last = id;
  else
    *(vert_texture+last) = id;
}

///	add_vert_id:
int	CustomStripifier::add_vert_id(int id, int	index_count)
{
  register int x;
  
  //   Test if degenerate, if so do not add degenerate vertex
  for (x = 1; x < index_count ; x++)
  {
	if (ids[x] == id)
		return 0;
  }
  ids[index_count] = id;

  return 1;
}

///	add_norm_id:
void CustomStripifier::add_norm_id(int id, int index_count)
{
  norms[index_count] = id;
}

///	AddNewFace:
void CustomStripifier::AddNewFace(int ids[MAX1], int vert_count, int face_id, int norms[MAX1])
{
  PF_FACES			pfNode;
  PF_VERTICES		pfVertNode;
  int						*pTempInt;
  int						*pnorms;
  F_EDGES				**pTempVertptr;
  int						*pTempmarked;
	int						*pTempwalked;
  register	int	y;
	register	int	count = 0;

  //  Add a new face into our face data structure
  pfNode = (PF_FACES) malloc(sizeof(F_FACES));

  if (pfNode)
  {
		pfNode->pPolygon	=	(int*) malloc(sizeof(int) * (vert_count) );
		pfNode->pNorms		=	(int*) malloc(sizeof(int) * (vert_count) );

		pfNode->VertandId	=	(F_EDGES**)malloc(sizeof(F_EDGES*)
												*
												(vert_count));

		pfNode->marked		=	(int*)malloc(sizeof(int) * (vert_count));
		pfNode->walked		=	(int*)malloc(sizeof(int) * (vert_count));
  }

  pTempInt					=	pfNode->pPolygon;
  pnorms						=	pfNode->pNorms;
  pTempmarked				=	pfNode->marked;
  pTempwalked				=	pfNode->walked;
  pTempVertptr			=	pfNode->VertandId;
  pfNode->nPolSize	=	vert_count;
  pfNode->nOrgSize	=	vert_count;
  pfNode->seen			=	-1;
  pfNode->seen2			=	-1;

  for (y = 1; y <= vert_count; y++)
  {
		*(pTempInt + count)			=	ids[y];
		*(pnorms + count)				=	norms[y];
		*(pTempmarked + count)	=	FALSE;
		*(pTempwalked + count)	=	-1;
		*(pTempVertptr+count)		=	NULL;

		count++;

		/* Add this FaceNode to the Vertices Structure */
		pfVertNode				=	(PF_VERTICES) malloc(sizeof(F_VERTICES));
		pfVertNode->face	=	pfNode;

		AddHead(Vertices[ids[y]],(PLISTINFO) pfVertNode);
  }

  AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
  
}

///	CopyFace:
void CustomStripifier::CopyFace(int ids[MAX1], int vert_count, int face_id, int norms[MAX1])
{
  PF_FACES			pfNode;
  int						*pTempInt;
  int						*pnorms;
  F_EDGES				**pTempVertptr;
  int						*pTempmarked;
	int						*pTempwalked;
  register	int	y;
	register	int	count = 0;
  
  /*   Copy a face node into a new node, used after the global algorithm
       is run, so that we can save whatever is left into a new structure
  */
  
  pfNode	=	(PF_FACES) malloc(sizeof(F_FACES));

  if ( pfNode )
  {
      pfNode->pPolygon	=	(int*) malloc(	sizeof(int)
																					*
																					(vert_count));

      pfNode->pNorms		=	(int*) malloc(	sizeof(int)
																					*
																					(vert_count));

      pfNode->VertandId	=	(F_EDGES**) malloc(	sizeof(F_EDGES*)
																							*
																							(vert_count));

      pfNode->marked	=	(int*)malloc(sizeof(int) * (vert_count));
      pfNode->walked	=	(int*)malloc(sizeof(int) * (vert_count));
  }

  pTempInt					=	pfNode->pPolygon;
  pnorms						=	pfNode->pNorms;
  pTempmarked				=	pfNode->marked;
  pTempwalked				=	pfNode->walked;
  pTempVertptr			=	pfNode->VertandId;
  pfNode->nPolSize	=	vert_count;
  pfNode->nOrgSize	=	vert_count;
  pfNode->seen			=	-1;
  pfNode->seen2			=	-1;

  for (y = 0; y < vert_count; y++)
  {
		*(pTempInt + count)			=	ids[y];
		*(pnorms + count)				=	norms[y];
		*(pTempmarked + count)	=	FALSE;
		*(pTempwalked + count)	=	-1;
		*(pTempVertptr+count)		=	NULL;

		count++;
  }

  AddHead(PolFaces[face_id-1],(PLISTINFO) pfNode);
}

///	Add_AdjEdge:
void CustomStripifier::Add_AdjEdge(int v1,int v2,int fnum,int index1 )
{
  PF_EDGES			temp	=	NULL;
  PF_FACES			temp2 = NULL;
  PF_EDGES			pfNode;
  ListHead			*pListHead;
  ListHead			*pListFace;
  BOOL					flag	=	TRUE;
  register	int	count = 0;
  register	int	t;
	register	int	v3		=	-1;
  
  if (v1 > v2)
  {
		t		=	v1;
		v1	=	v2;
		v2	=	t;
  }

  pListFace	=	PolFaces[fnum];
  temp2			=	(PF_FACES) PeekList(pListFace,LISTHEAD,0);
  pListHead	=	PolEdges[v1];
  temp			=	(PF_EDGES) PeekList(pListHead,LISTHEAD,count);

  if (temp == NULL)
	{
		flag	=	FALSE;
	}

  count++;

  while (flag)
  {
		if (v2 == temp->edge[0])
		{
			/*	If greater than 2 polygons adjacent to an edge,
					then we will only save the first 2 that we found.
					We will have a small performance hit,
					but this does not happen often.
			*/
			if (temp->edge[2] == -1)
			{
				temp->edge[2]	=	fnum;
			}
			else
			{
				v3	=	temp->edge[2];

				//	More than 3 edges are adjacent.
				//	The mesh is not Manifold.
				mError	=	1;
			}

			flag	=	FALSE;
		}
		else
		{
			temp	=	( PF_EDGES ) GetNextNode(temp);

			count++;

			if (temp == NULL)
			{
				flag	=	FALSE;
			}
		}
	}
  
  /*   Did not find it */
  if (temp == NULL)
  {
    pfNode	=	(PF_EDGES) malloc(sizeof(F_EDGES));

    if (pfNode)
		{
			pfNode->edge[0]	=	v2;
			pfNode->edge[1]	=	fnum;
			pfNode->edge[2]	=	v3;

			AddTail(PolEdges[v1], (PLISTINFO) pfNode);
		}
		else
		{
			printf("Out of memory!\n");
			exit(1);
		}

		*(temp2->VertandId+index1)	=	pfNode;
	}
  else
	{
		*(temp2->VertandId+index1)	=	temp;
	}
}

///	power_10:
int CustomStripifier::power_10(int power)
{
  /*	Raise 10 to the power */
  register int i,p;
  
  p = 1;
  for (i = 1; i <= power; ++i)
    p = p * 10;
  return p;
}

///	power_negative:
float CustomStripifier::power_negative(int power)
{
  /*   Raise 10 to the negative power */
  
  register int i;
  float p;
  
  p = (float)1;
  for (i = 1; i<=power; i++)
    p = p * (float).1;
  return p;
}

///	convert_array:
float CustomStripifier::convert_array(int num[],int stack_size)
{
  /* Convert an array of characters to an integer */
  
  register int counter,c;
  float temp =(float)0.0;
  
  for (c=(stack_size-1), counter = 0; c>=0; c--, counter++)
    {
      if (num[c] == -1)
	/*   We are at the decimal point, convert to decimal
	     less than 1
	*/
	{
	  counter = -1;
	  temp = power_negative(stack_size - c - 1) * temp;
	}
      else 
	temp += power_10(counter) * num[c];
    }
  
  return(temp);
}

///	print_usage:
void CustomStripifier::print_usage(void) 
{
  printf("Usage: stripe [abfglopqrw] file_name\n");
  printf("Options:\n");
  printf(" -b\tSpecifies that the input file is in binary\n");
  printf(" -g\tFind triangle strips only within the groups specified in the data file\n");
  printf(" -o\tTurn off orientation checking\n\n");
  
  printf("Tie Breaking:\n");
  printf(" -a\tAlternate left-right direction in choosing next polygon\n");
  printf(" -f\tChoose the first polygon that it found\n");
  printf(" -l\tLook ahead one level in choosing the next polygon\n");
  printf(" -q\tChoose the polygon which does not produce a swap\n");
  printf(" -r\tRandomly choose the next polygon\n\n");
  
  printf("Triangulation:\n");
  printf(" -p\tPartially triangulate faces\n");
  printf(" -w\tFully triangluate faces\n");
}

///	get_options:
float CustomStripifier::get_options(int		argc,
																		char	**argv,
																		int		*f,
																		int		*t,
																		int		*tr,
																		int		*group,
																		int		*orientation)
{
  char c;
  int count = 0;
  int buffer[MAX1];
  int next = 0;
  /*    tie variable */
  enum tie_options tie = FIRST;
  /*   triangulation variable */
  enum triangulation_options triangulate = WHOLE;
  /*   normal difference variable (in degrees) */
  float norm_difference = (float)360.0;
  /*   file-type variable */
  enum file_options file_type = ASCII;
  
  *orientation = 1;
  
  /*      User has the wrong number of options */
  if ((argc > 6) || (argc < 2))
  {
    print_usage();
    exit(0);
  }
  
  /* Interpret the options specified */
  while (--argc > 0 && (*++argv)[0] == '-')
  {
    /*   At the next option that was specified */
    next = 1;
    while ((c = *++argv[0]))
			switch (c)
			{
				case 'f': 
					/*      Use the first polygon we see. */
					tie = FIRST;
					break;
			    
				case 'r':
					/*      Randomly choose the next polygon */
					tie = RANDOM;
					break;
			    
				case 'a':
					/*      Alternate direction in choosing the next polygon */
					tie = ALTERNA;
					break;
			    
				case 'l':
					/*      Use lookahead to choose the next polygon */
					tie = LOOK;
					break;
			    
				case 'q':
					/*  Try to reduce swaps */
					tie = SEQUENTIAL;
					break;
			    
				case 'p':
					/*      Use partial triangulation of polygons */
					triangulate = PARTIAL;
					break;
			    
				case 'w':
					/*      Use whole triangulation of polygons */
					triangulate = WHOLE;
					break;
			    
				case 'b':
					/*      Input file is in binary */
					file_type = BINARY;
					break;
			    
				case 'g':
					/*   Strips will be grouped according to the groups in 
				the data file. We will have to restrict strips to be
				in the grouping of the data file.
					*/
					*group = 1;
					break;
			    
							case 'o':
					*orientation = 0;
			    
					/*	Get each the value of the integer */
					/*	We have an integer */
				default:
					if ((c >= '0') && (c <= '9'))
						{
				/* More than one normal difference specified, use the last one */
				if (next == 1)
					{
						count = 0;
						next = 0;
					}
				buffer[count++] = ATOI(c);
						}
					/*   At the decimal point */
					else if (c == '.')
						{
				/* More than one normal difference specified, use the last one */
				if (next == 1)
					{
						count = 0;
						next = 0;
					}
				buffer[count++] = -1;
						}
					else 
						break;
			}
    }
  /*   Convert the buffer of characters to a floating pt integer */
  if (count != 0) 
    norm_difference = convert_array(buffer,count);
  *f = file_type;
  *t = tie;
  *tr = triangulate;
  return norm_difference;
}

///	AdjacentEx:
int CustomStripifier::AdjacentEx(int id2,int id1, int *list, int size)
{
  /*	Return the vertex that is adjacent to id1,
	but is not id2, in the list of integers.
  */
  
  register int x=0;
  
  while (x < size)
    {
      if (*(list+x) == id1)
	{
	  if ((x != (size -1)) && (x != 0))
	    {
	      if ( *(list+x+1) != id2)
		return *(list+x+1);
	      else
		return *(list+x-1);
	    }
	  else if (x == (size -1))
	    {
	      if (*(list) != id2)
		return *(list);
	      else
		return *(list+x-1);
	    }
	  else
	    {
	      if (*(list+size-1) != id2)
		return *(list+size-1);
	      else
		return *(list+x+1);
	    }
	}
      x++;
    }
  printf("Error in the list\n");
  exit(0);
}

///	Delete_From_ListEx:
void CustomStripifier::Delete_From_ListEx(int id,int *list, int size)
{
  /*	Delete the occurence of id in the list.
	(list has size size)
  */
  
  int *temp;
  register int x,y=0;
  
  temp = (int *) malloc(sizeof(int) * size);
  for (x=0; x<size; x++)
    {
      if (*(list+x) != id)
	{
	  *(temp+y) = *(list+x);
	  y++;
	}
    }
  if(y != (size-1))
    {
      printf("There is an error in the delete\n");
      exit(0);
    }
  *(temp+size-1) = -1;
  memcpy(list,temp,sizeof(int)*size);
  
}

///	Triangulate_QuadEx:
void CustomStripifier::Triangulate_QuadEx(int out_edge1,int out_edge2,int in_edge1,
			       int in_edge2,int size,int *index,
			       int reversed,
			       int where)
{
  int vertex4,vertex5;
  
  /*	This routine will nonblindly triangulate a quad, meaning
	that there is a definite input and a definite output
	edge that we must adhere to. Reversed will tell the orientation
	of the input edge. (Reversed is -1 is we do not have an input
	edge, in other words we are at the beginning of a strip.)
	Out_edge* is the output edge, and in_edge* is the input edge. 
	Index are the edges of the polygon
	and size is the size of the polygon. Begin is whether we are
	at the start of a new strip.
  */
  
  /*	If we do not have an input edge, then we can make our input
	edge whatever we like, therefore it will be easier to come
	out on the output edge.
  */
  if (reversed == -1)
    {
      vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
      vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
      Output_TriEx(vertex5,vertex4,out_edge1,NULL,-1,where);
      Output_TriEx(vertex4,out_edge1,out_edge2,NULL,-1,where);
      return;
    }
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*   Are they consecutive so that we form a triangle to
       peel off, but cannot use the whole quad?
  */
  
  if (in_edge2 == out_edge1) 
    {
      /*	Output the triangle that comes out the correct
		edge last. First output the triangle that comes out
		the wrong edge.
      */
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
      Output_TriEx(in_edge1,in_edge2,vertex4,NULL,-1,where);
      Output_TriEx(vertex4,in_edge2,out_edge2,NULL,-1,where);
      return;
    }
  /*	The next case is where it is impossible to come out the
	edge that we want. So we will have to start a new strip to
	come out on that edge. We will output the one triangle
	that we can, and then start the new strip with the triangle
	that comes out on the edge that we want to come out on.
  */
  else if (in_edge1 == out_edge1)
    {
      /*	We want to output the first triangle (whose output
		edge is not the one that we want.
		We have to find the vertex that we need, which is
		the other vertex which we do not have.
      */
      vertex4 = Get_Other_Vertex(in_edge2,in_edge1,out_edge2,index);
      Output_TriEx(in_edge2,in_edge1,vertex4,NULL,-1,where);
      Output_TriEx(vertex4,in_edge1,out_edge2,NULL,-1,where);
      return;
    }
  
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_TriEx(in_edge2,in_edge1,vertex4,NULL,-1,where);
      Output_TriEx(vertex4,in_edge1,out_edge1,NULL,-1,where);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_TriEx(in_edge1,in_edge2,vertex4,NULL,-1,where);
      Output_TriEx(vertex4,in_edge2,out_edge1,NULL,-1,where);
      return;
    }
  
  /*	The final case is where we want to come out the opposite edge.*/
  else
    {
      if( ((!reversed) &&
	   (out_edge1 == (AdjacentEx(in_edge1,in_edge2,index,size)))) ||
	  ((reversed) &&
	   (out_edge2 == (AdjacentEx(in_edge2,in_edge1,index,size)))))
	{
	  /*	We need to know the orientation of the input
		edge, so we know which way to put the diagonal.
		And also the output edge, so that we triangulate correctly.
	  */
	  Output_TriEx(in_edge1,in_edge2,out_edge2,NULL,-1,where);
	  Output_TriEx(in_edge2,out_edge2,out_edge1,NULL,-1,where);
	}
      else
	{
	  /*   Input and output orientation was reversed, so diagonal will
	       be reversed from above.
	  */
	  Output_TriEx(in_edge1,in_edge2,out_edge1,NULL,-1,where);
	  Output_TriEx(in_edge2,out_edge1,out_edge2,NULL,-1,where);
	}
      return;
    }
}

///	Triangulate_PolygonEx:
void CustomStripifier::Triangulate_PolygonEx(	int out_edge1,int out_edge2,
																							int in_edge1, int in_edge2,
																							int size,			int *index,
			   																			FILE *fp,			int reversed,
																							int face_id,  int where)
{
  /*	We have a polygon that we need to nonblindly triangulate.
	We will recursively try to triangulate it, until we are left
	with a polygon of size 4, which can use the quad routine
	from above. We will be taking off a triangle at a time
	and outputting it. We will have 3 cases similar to the
	cases for the quad above. The inputs to this routine
	are the same as for the quad routine.
  */
  
  int vertex4;
  int *temp;
  
  
  /*	Since we are calling this recursively, we have to check whether
	we are down to the case of the quad.
  */
  
  if (size == 4)
    {
      Triangulate_QuadEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
			 index,reversed,where);
      return;
    }
  
  
  
  /*	We do not have a specified input edge, and therefore we
	can make it anything we like, as long as we still come out 
	the output edge that we want.
  */
  if (reversed  == -1)
    {
      /*	Get the vertex for the last triangle, which is
		the one coming out the output edge, before we do
		any deletions to the list. We will be doing this
		bottom up.
      */
      vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(out_edge2,index,size);
      Triangulate_PolygonEx(out_edge1,vertex4,in_edge2,
			    vertex4,size-1,index,
			    fp,reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      /*	Lastly do the triangle that comes out the output
		edge.
      */
      Output_TriEx(vertex4,out_edge1,out_edge2,NULL,-1,where);
      return;
    }
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*  Are they consecutive so that we form a triangle to
      peel off that comes out the correct output edge, 
      but we cannot use the whole polygon?
  */
  if (in_edge2 == out_edge1) 
    {
      /*	Output the triangle that comes out the correct
		edge last. First recursively do the rest of the
		polygon.
      */
      /*	Do the rest of the polygon without the triangle. 
		We will be doing a fan triangulation.
      */
      /*	Get the vertex adjacent to in_edge1, but is not
		in_edge2.
      */
      vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
      Output_TriEx(in_edge1,in_edge2,vertex4,NULL,-1,where);
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(in_edge1,index,size);
      Triangulate_PolygonEx(out_edge1,out_edge2,in_edge2,
			    vertex4,size-1,index,fp,
			    !reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  
  /*	Next case is where it is again consecutive, but the triangle
	formed by the consecutive edges do not come out of the
	correct output edge. For this case, we can not do much to
	keep it sequential. Try and do the fan.
  */
  else if (in_edge1 == out_edge1)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
      Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,where);
      /*	Since that triangle goes out of the polygon (the
		output edge of it), we can make our new input edge
		anything we like, so we will try to make it good for
		the strip. (This will be like starting a new strip,
		all so that we can go out the correct output edge.)
      */
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(in_edge2,index,size);
      Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,
			    vertex4,size-1,index,fp,
			    reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
      Output_TriEx(in_edge2,in_edge1,vertex4,fp,-1,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(in_edge2,index,size);
      Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,
			    vertex4,size-1,index,fp,
			    reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
      Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(in_edge1,index,size);
      Triangulate_PolygonEx(out_edge1,out_edge2,vertex4,
			    in_edge2,size-1,index,fp,
			    reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
  
  /*	Else the edge is not consecutive, and it is sufficiently
	far away, for us not to make a conclusion at this time.
	So we can take off a triangle and recursively call this
	function.
  */
  else
    {
      vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
      Output_TriEx(in_edge1,in_edge2,vertex4,fp,-1,where);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(in_edge1,index,size);
      Triangulate_PolygonEx(out_edge1,out_edge2,in_edge2,
			    vertex4,size-1,index,fp,
			    !reversed,face_id,where);
      memcpy(index,temp,sizeof(int)*size);
      return;
    }
}

///	TriangulateEx:
void CustomStripifier::TriangulateEx(int out_edge1,int out_edge2,int in_edge1,
			  int in_edge2,int size,int *index,
			  FILE *output,int reversed,int face_id, int where)
{
  /*	We have the info we need to triangulate a polygon */
  
  if (size == 4)
    Triangulate_QuadEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
		       index,reversed,where);
  else
    Triangulate_PolygonEx(out_edge1,out_edge2,in_edge1,in_edge2,size,
			  index,output,reversed,face_id,where);
}

///	Non_Blind_TriangulateEx:
void CustomStripifier::Non_Blind_TriangulateEx(int size,int *index, 
			     FILE *output,int next_face_id,int face_id,int where)
{
  int id1,id2,id3;
  int nedge1,nedge2;
  int reversed;
  /*	We have a polygon that has to be triangulated and we cannot
	do it blindly, ie we will try to come out on the edge that
	has the least number of adjacencies
  */
  
  Last_Edge(&id1,&id2,&id3,0);
  /*	Find the edge that is adjacent to the new face ,
	also return whether the orientation is reversed in the
	face of the input edge, which is id2 and id3.
  */
  if (next_face_id == -1)
    {
      printf("The face is -1 and the size is %d\n",size);
      exit(0);
    }
  
  reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
  /*	Do the triangulation */
  
  /*	If reversed is -1, the input edge is not in the polygon, 
	therefore we can have the input edge to be anything we like,
	since we are at the beginning of a strip
  */
  TriangulateEx(nedge1,nedge2,id2,id3,size,index,output,reversed,
		face_id, where);
}

///	Rearrange_IndexEx:
void CustomStripifier::Rearrange_IndexEx(int *index, int size)
{
  /*	If we are in the middle of a strip we must find the
	edge to start on, which is the last edge that we had
	transmitted.
  */
  int x,f,y,e1,e2,e3;
  int increment = 1;
  int *temp;
  
  /*	Find where the input edge is in the input list */
  Last_Edge(&e1,&e2,&e3,0);
  for (y = 0; y < size; y++)
    {
      if (*(index+y) == e2)
	{
	  if ((y != (size - 1)) && (*(index+y+1) == e3))
	    break;
	  else if ((y == (size - 1)) && (*(index) == e3))
	    break;
	  else if ((y != 0) && (*(index+y-1) == e3))
	    {
	      increment = -1;
	      break;
	    }
	  else if ((y==0) && (*(index+size-1) == e3))
	    {
	      increment = -1;
	      break;
	    }
	}
      if (*(index+y) == e3)
	{
	  if ((y != (size - 1)) && (*(index+y+1) == e2))
	    break;
	  else if ((y == (size - 1)) && (*(index) == e2))
	    break;
	  else if ((y != 0) && (*(index+y-1) == e2))
	    {
	      increment = -1;
	      break;
	    }
	  else if ((y==0) && (*(index+size-1) == e2))
	    {
	      increment = -1;
	      break;
	    }
	}
      /*	Edge is not here, we are at the beginning */
      if ((y == (size-1)) && (increment != -1))
	return;
    }
  
  /*	Now put the list into a new list, starting with the
	input edge. Increment tells us whether we have to go 
	forward or backward.
  */
  /*	Was in good position already */
  if ((y == 0) && (increment == 1)) 
    return;
  
  
  temp = (int *) malloc(sizeof(int) * size);
  memcpy(temp,index,sizeof(int)*size);
  
  if (increment == 1)
    {
      x=0;
      for (f = y ; f< size; f++)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
      /*	Finish the rest of the list */	
      for(f = 0; f < y ; f++)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
    }
  else
    {
      x=0;
      for (f = y ; f >= 0; f--)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
      /*	Finish the rest of the list */	
      for(f = (size - 1); f > y ; f--)
	{
	  *(index+x) = *(temp+f);
	  x++;
	}
    }
}

///	Blind_TriangulateEx:
void CustomStripifier::Blind_TriangulateEx(int size, int *index,
			 BOOL begin, int where )
{
  /*	save sides in temp array, we need it so we know
	about swaps.
  */
  int mode, decreasing,increasing,e1,e2,e3;
  
  /*	Rearrange the index list so that the input edge is first
   */
  if (!begin)
    Rearrange_IndexEx(index,size);
  
  /*	We are given a polygon of more than 3 sides
	and want to triangulate it. We will output the
	triangles to the output file.
  */
  
  /*	Find where the input edge is in the input list */
  Last_Edge(&e1,&e2,&e3,0);
  if (( (!begin) && (*(index) == e2) ) || (begin))
    {
      Output_TriEx(*(index+0),*(index+1),*(index+size-1),NULL,-1,where);
      /*	If we have a quad, (chances are yes), then we know that
		we can just add one diagonal and be done. (divide the
		quad into 2 triangles.
      */
      if (size == 4)
        {
	  Output_TriEx(*(index+1),*(index+size-1),*(index+2),NULL,-1,where);
	  return;
        }
      increasing = 1;
      mode = 1;
      
    }
  else if (!begin)
    {
      Output_TriEx(*(index+1),*(index+0),*(index+size-1),NULL,-1,where);
      if (size == 4)
        {
	  Output_TriEx(*(index+0),*(index+size-1),*(index+2),NULL,-1,where);
	  return;
        }
      Output_TriEx(*(index+0),*(index+size-1),*(index+2),NULL,-1,where);
      increasing = 2;
      mode = 0;
    }
  if (size != 4)
    {
      /*	We do not have a quad, we have something bigger. */
      decreasing = size - 1;
      
      do
	{
	  /*	Will be alternating diagonals, so we will be increasing
		and decreasing around the polygon.
	  */
	  if (mode)
	    {
	      Output_TriEx(*(index+increasing),*(index+decreasing),
			   *(index+increasing+1),NULL,-1,where);
	      increasing++;
	    }
	  else
	    {
	      Output_TriEx(*(index+decreasing),*(index+increasing),
			   *(index+decreasing-1),NULL,-1,where);
	      decreasing--;
	    }
	  mode = !mode;
	} while ((decreasing - increasing) >= 2);
      
    }
}

///	Get_EdgeEx:
int CustomStripifier::Get_EdgeEx(int *edge1,int *edge2,int *index,int face_id,
	       int size, int id1, int id2)
{
  /*	Put the edge that is adjacent to face_id into edge1
	and edge2. For each edge see if it is adjacent to
	face_id. Id1 and id2 is the input edge, so see if 
	the orientation is reversed, and save it in reversed.
  */
  int x;
  int reversed = -1;
  BOOL set = FALSE;
  
  for (x=0; x< size; x++)
    {
      if (x == (size-1))
	{
	  if ((*(index) == id1) && (*(index+size-1)==id2))
	    {
	      if (set)
		return 1;
	      reversed = 1;
	    }
	  else if ((*(index) == id2) && (*(index+size-1)==id1))
	    {
	      if (set)
		return 0;
	      reversed = 0;
	    }
	  
	  if (Look_Up(*(index),*(index+size-1),face_id))
	    {
	      if ( (out1Ex != -1) &&
		   ( (out1Ex == *(index)) || (out1Ex == *(index+size-1)) ) &&
		   ( (out2Ex == *(index)) || (out2Ex == *(index+size-1)) ))
		{
		  set = TRUE;
		  *edge1 = *(index);
		  *edge2 = *(index+size-1);
		}
	      else if (out1Ex == -1)
		{
		  set = TRUE;
		  *edge1 = *(index);
		  *edge2 = *(index+size-1);
		}
	      if ((reversed != -1) && (set))  
		return reversed;
	    }
	}		
      else
	{
	  if ((*(index+x) == id1) && (*(index+x+1)==id2))
	    {
	      if (set)
		return 0;
	      reversed = 0;
	    }
	  else if ((*(index+x) == id2) && (*(index+x+1)==id1))
	    {
	      if (set)
		return 1;
	      reversed = 1;
	    }
	  
	  if (Look_Up(*(index+x),*(index+x+1),face_id))
	    {
	      if ( (out1Ex != -1) &&
		   ( (out1Ex == *(index+x)) || (out1Ex == *(index+x+1)) ) &&
		   ((out2Ex == *(index+x)) || (out2Ex == *(index+x+1))))
		{
		  set = TRUE;
		  *edge1 = *(index+x);
		  *edge2 = *(index+x+1);
		}
	      else if (out1Ex == -1)
		{
		  set = TRUE;
		  *edge1 = *(index+x);
		  *edge2 = *(index+x + 1);
		}
	      if ((reversed != -1) && (set))
		return reversed;
	    }
	}
    }			
  if ((x == size) && (reversed != -1))
    {
      /*	Could not find the output edge */
      printf("Error in the Lookup %d %d %d %d %d %d %d %d\n",
	     face_id,id1,id2,reversed,*edge1,*edge2,out1Ex,out2Ex);
      exit(0);
    }
  return reversed;
}

///	Update_FaceEx:
void CustomStripifier::Update_FaceEx(	int *next_bucket,int *min_face,
																			int face_id, int *e1,
			  															int *e2,int temp1,
																			int temp2,int *ties)
{
  /*	We have a face id that needs to be decremented.
	We have to determine where it is in the structure,
	so that we can decrement it.
  */
  /*	The number of adjacencies may have changed, so to locate
	it may be a little tricky. However we know that the number
	of adjacencies is less than or equal to the original number
	of adjacencies,
  */
  int y,size; 
  ListHead *pListHead;
  PF_FACES temp = NULL;
  PLISTINFO lpListInfo;
  static int each_poly = 0;
  BOOL there = FALSE;
  
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  /*	Check each edge of the face and tally the number of adjacent
	polygons to this face. 
  */	      		
  if ( temp != NULL )
    {
      /*	Size of the polygon */
      size = temp->nPolSize;
      for (y = 0; y< size; y++)
	{
	  /*	If we are doing partial triangulation, we must check
		to see whether the edge is still there in the polygon,
		since we might have done a portion of the polygon
		and saved the rest for later.
	  */
	  if (y != (size-1))
	    {
	      if( ((temp1 == *(temp->pPolygon+y)) && 
		   (temp2 ==*(temp->pPolygon+y+1))) ||
		  ((temp2 == *(temp->pPolygon+y)) &&
		   (temp1 ==*(temp->pPolygon+y+1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	  else
	    {
	      if( ((temp1 == *(temp->pPolygon)) && 
		   (temp2 == *(temp->pPolygon+size-1))) ||
		  ((temp2 == *(temp->pPolygon)) &&
		   (temp1 ==*(temp->pPolygon+size-1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	}
      
      if (!there)
	/*	Original edge was already used, we cannot use this polygon */
	return;
      
      /*	We have a starting point to start our search to locate
		this polygon. 
      */
      
      /*	Check to see if this polygon was done */
      lpListInfo = Done(face_id,&y);
      
      if (lpListInfo == NULL)
	return;
      
      /*  Was not done, but there is an error in the adjacency calculations */
      /*     If more than one edge is adj to it then maybe it was not updated */
      if (y == 0)
	return;
      
      /*	Now put the face in the proper bucket depending on tally. */
      /*	First add it to the new bucket, then remove it from the old */
      Add_Sgi_Adj(y-1,face_id);
      RemoveList(array[y],lpListInfo);
      
      /*	Save it if it was the smallest seen so far since then
		it will be the next face 
		Here we will have different options depending on
		what we want for resolving ties:
		1) First one we see we will use
		2) Random resolving
		3) Look ahead
		4) Alternating direction
      */
      /*	At a new strip */
      if (*next_bucket == 60)
	*ties = *ties + each_poly;
      /*	Have a tie */
      if (*next_bucket == (y-1))
	{
	  Add_Ties(face_id);
	  each_poly++;
	}
      /*	At a new minimum */
      if (*next_bucket > (y-1))
	{
	  *next_bucket = y-1;
	  *min_face = face_id;
	  *e1 = temp1;
	  *e2 = temp2;
	  each_poly = 0;
	  Clear_Ties();
	  Add_Ties(face_id);
	}
    }
}

///	Delete_AdjEx:
void CustomStripifier::Delete_AdjEx(int id1,					int id2,
																		int *next_bucket,	int *min_face, 
		  															int current_face,	int *e1,
																		int *e2,					int *ties)
{
  /*	Find the face that is adjacent to the edge and is not the
	current face. Delete one adjacency from it. Save the min
	adjacency seen so far.
  */
  register int count=0;
  PF_EDGES temp = NULL;
  ListHead *pListHead;
  int next_face;
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    /*	It could be a new edge that we created. So we can
	exit, since there is not a face adjacent to it.
    */
    return;
  while (temp->edge[0] != id2)
    {
      count++;
      temp = ( PF_EDGES )GetNextNode(temp);                                      
      
      if (temp == NULL)
	/*	Was a new edge that was created and therefore
		does not have anything adjacent to it
	*/
	return;
    }
  /*	Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return;
  
  /*	Was adjacent to something */
  else
    {
      if (temp->edge[2] == current_face)
	next_face =  temp->edge[1];
      else 
	next_face = temp->edge[2];
    }
  /*	We have the other face adjacent to this edge, it is 
	next_face. Now we need to decrement this faces' adjacencies.
  */
  Update_FaceEx(next_bucket, min_face, next_face,e1,e2,id1,id2,ties);
}

///	Change_FaceEx:
int CustomStripifier::Change_FaceEx(int face_id,int in1,int in2,
		  ListHead *pListHead, BOOL no_check)
{
  /*	We are doing a partial triangulation and we need to
	put the new face of triangle into the correct bucket
  */
  int input_adj,y;
  P_ADJACENCIES lpListInfo;  
  
  /*	Find the old number of adjacencies to this face,
	so we know where to delete it from
  */
  y = Old_Adj(face_id);
  pListHead = array[y];
  lpListInfo = face_array[face_id].pfNode;
  
  if (lpListInfo == NULL)
    {
      printf("There is an error finding the next polygon3 %d\n",face_id);
      exit(0);
    }
  
  /*	Do we need to change the adjacency? Maybe the edge on the triangle
	that was outputted was not adjacent to anything. We know if we
	have to check by "check". We came out on the output edge
	that we needed, then we know that the adjacencies will decrease
	by exactly one.
  */
  if (!no_check)
    {
      input_adj = Number_Adj(in1,in2,face_id);
      /*	If there weren't any then don't do anything */
      if (input_adj == 0)
	return y;
    }
  
  if (face_array[lpListInfo->face_id].head == pListHead)
    face_array[lpListInfo->face_id].pfNode = NULL;
  RemoveList(pListHead,(PLISTINFO)/*(temp*/lpListInfo);
  /*	Before we had a quad with y adjacencies. The in edge
	did not have an adjacency, since it was just deleted,
	since we came in on it. The outedge must have an adjacency
	otherwise we would have a bucket 0, and would not be in this
	routine. Therefore the new adjacency must be y-1
  */
  
  Add_Sgi_Adj(y-1,face_id);
  return (y-1);
}

///	Update_AdjacenciesEx:
int CustomStripifier::Update_AdjacenciesEx(int face_id, int *next_bucket, int *e1, int *e2,
			 int *ties)
{
  /*	Give the face with id face_id, we want to decrement
	all the faces that are adjacent to it, since we will
	be deleting face_id from the data structure.
	We will return the face that has the least number
	of adjacencies.
  */
  PF_FACES temp = NULL;
  ListHead *pListHead;
  int size,y,min_face = -1;
  
  *next_bucket = 60;
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  if ( temp == NULL )
    {
      printf("The face was already deleted, there is an error\n");
      exit(0);
    }
  
  /*	Size of the polygon */
  size = temp->nPolSize;
  for (y = 0; y< size; y++)
    {
      if (y != (size-1))
	Delete_AdjEx(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
		     next_bucket,&min_face,face_id,e1,e2,ties);
      else
	Delete_AdjEx(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
		     next_bucket,&min_face,face_id,e1,e2,ties);
    }
  return (min_face);
}

///	Find_Adj_TallyEx:
void CustomStripifier::Find_Adj_TallyEx(int id1, 					int id2,
																				int *next_bucket,	int *min_face,
			     															int current_face,	int *ties)
{
  /*	Find the face that is adjacent to the edge and is not the
	current face. Save the min adjacency seen so far.
  */
  int size,each_poly=0,y,count=0;           
  PF_EDGES temp = NULL;
  PF_FACES temp2 = NULL;
  ListHead *pListHead;
  int next_face;
  BOOL there = FALSE;
  
  
  /*	Always want smaller id first */
  switch_lower(&id1,&id2);
  
  pListHead = PolEdges[id1];
  temp = (PF_EDGES) PeekList(pListHead,LISTHEAD,count);
  if (temp == NULL)
    /*	This was a new edge that was created, so it is
	adjacent to nothing.
    */
    return;
  while (temp->edge[0] != id2)
    {
      count++;
      temp =( PF_EDGES ) GetNextNode(temp);                                       
      
      if (temp == NULL)
	/*	This was a new edge that we created */
	return;
    }
  /*	Was not adjacent to anything else except itself */
  if (temp->edge[2] == -1)
    return;
  else
    {
      if (temp->edge[2] == current_face)
	next_face =  temp->edge[1];
      else 
	next_face = temp->edge[2];
    }
  /*	We have the other face adjacent to this edge, it is 
	next_face. Find how many faces it is adjacent to.
  */
  pListHead = PolFaces[next_face];
  temp2 = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  /*	Check each edge of the face and tally the number of adjacent 
	polygons to this face. This will be the original number of
	polygons adjacent to this polygon, we must then see if this
	number has been decremented
  */	      		
  if ( temp2 != NULL )
    {
      /*	Size of the polygon */
      size = temp2->nPolSize;
      for (y = 0; y< size; y++)
	{
	  /*	Make sure that the edge is still in the
		polygon and was not deleted, because if the edge was
		deleted, then we used it already.
	  */
	  if (y != (size-1))
	    {
	      if( ((id1 == *(temp2->pPolygon+y)) &&
		   (id2 ==*(temp2->pPolygon+y+1))) ||
		  ((id2 == *(temp2->pPolygon+y)) &&
		   (id1 ==*(temp2->pPolygon+y+1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	  else
	    {		
	      if( ((id1 == *(temp2->pPolygon)) &&
		   (id2 ==*(temp2->pPolygon+size-1))) ||
		  ((id2 == *(temp2->pPolygon)) &&
		   (id1 ==*(temp2->pPolygon+size-1))))
		/*	edge is still there we are ok */
		there = TRUE;
	    }
	}
      
      if (!there)
	/*	Edge already used and deleted from the polygon*/
	return;
      
      /*	See if the face was already deleted, and where
		it is if it was not
      */
      if (Done(next_face,&y) == NULL)
	return;
      
      /*	Save it if it was the smallest seen so far since then
		it will be the next face 
		Here we will have different options depending on
		what we want for resolving ties:
		1) First one we see we will use
		2) Random resolving
		3) Look ahead
		4) Alternating direction
      */
      
      /*	At a new strip */
      if (*next_bucket == 60)
	*ties = *ties + each_poly;
      /*	Have a tie */
      if (*next_bucket == (y-1))
	{
	  Add_Ties(next_face);
	  each_poly++;
	}
      /*	At a new minimum */
      if (*next_bucket > (y-1))
	{
	  *next_bucket = y-1;
	  *min_face = next_face;
	  each_poly = 0;
	  Clear_Ties();
	  Add_Ties(next_face);
	}
    }
}

///	Min_Face_AdjEx:
int CustomStripifier::Min_Face_AdjEx(int face_id, int *next_bucket, int *ties)
{
  /*	Used for the Partial triangulation to find the next
	face. It will return the minimum adjacency face id
	found at this face.
  */
  PF_FACES temp = NULL;
  ListHead *pListHead;
  int size,y,min_face,test_face;
  
  *next_bucket = 60;
  pListHead = PolFaces[face_id];
  temp = ( PF_FACES ) PeekList( pListHead, LISTHEAD, 0 );
  
  if ( temp == NULL )
    {
      printf("The face was already deleted, there is an error\n");
      exit(0);
    }
  
  /*	Size of the polygon */
  size = temp->nPolSize;
  for (y = 0; y< size; y++)
    {
      if (y != (size-1))
	Find_Adj_TallyEx(*(temp->pPolygon+y),*(temp->pPolygon+y+1),
			 next_bucket,&min_face,face_id,ties);
      else
	Find_Adj_TallyEx(*(temp->pPolygon),*(temp->pPolygon+(size-1)),
			 next_bucket,&min_face,face_id,ties);
    }
  /*    Maybe we can do better by triangulating the face, because
	by triangulating the face we will go to a polygon of lesser
	adjacencies
  */
  if (size == 4)
    {
      /*    Checking for a quad whether to do the whole polygon will
	    result in better performance because the triangles in the polygon
	    have less adjacencies
      */
      Check_In_Quad(face_id,&test_face);
      if (*next_bucket > test_face)
	/*    We can do better by going through the polygon */
	min_face = face_id;
    }
  
  /*  We have a polygon with greater than 4 sides, check to see if going
      inside is better than going outside the polygon for the output edge.
  */
  else
    {
      Check_In_Polygon(face_id,&test_face,size);
      if (*next_bucket > test_face)
	/*  We can do better by going through the polygon */
	min_face = face_id;
    }
  
  return (min_face);
}

///	Find_StripsEx:
void CustomStripifier::Find_StripsEx(FILE *output,int *ties,
			  int  tie, int triangulate,
			  int  swaps,int *next_id)
{
  /*	This routine will peel off the strips from the model */
  
  ListHead			*pListHead;
  P_ADJACENCIES	temp				=	NULL;
  register int	max,bucket	=	0;
  BOOL					whole_flag	=	TRUE;
  int						dummy				= 0;
  int						cont				=	0;
  
  /*  Set the last known input edge to be null */
  Last_Edge(&dummy,&dummy,&dummy,1);
  
  /*	Search for lowest adjacency polygon and output strips */
  while (whole_flag)
	{
		bucket = -1;
    /*	Search for polygons in increasing number of adjacencies */
    while (bucket < 59)
		{
			bucket++;
			pListHead = array[bucket];
			max = NumOnList(pListHead);
			if (max > 0)
	    {
				temp = (P_ADJACENCIES) PeekList(pListHead,LISTHEAD,0);
	      if (temp == NULL)
				{
					printf("Error in the buckets%d %d %d\n",bucket,max,0);
					exit(0);
				}

	      Polygon_OutputEx(temp,temp->face_id,bucket,pListHead, output,ties,tie,triangulate,swaps,next_id,1);
	      /*  Try to extend backwards, if the starting polygon in the
						strip had 2 or more adjacencies to begin with
	      */
	      if (bucket >= 2)
					Extend_BackwardsEx(temp->face_id,output,ties,tie, triangulate,swaps,next_id);

				break;  
			}
		}
		/*	Went through the whole structure, it is empty and we are done.
		*/
		if ((bucket == 59) && (max == 0))
			whole_flag = FALSE;
      
    /*  We just finished a strip, send dummy data to signal the end
				of the strip so that we can output it.
    */
    else
		{
			Output_TriEx(-1,-2,-3,output,-10,1);
			Last_Edge(&dummy,&dummy,&dummy,1);
			cont++;
		}
  }
	printf("We got %d strips\n",cont);
}

///	SGI_Strip:
void CustomStripifier::SGI_Strip(int	num_faces,
																 FILE *output,
																 int	ties,
																 int	triangulate)
{
  int next_id = -1,t=0;
  
  /* We are going to output and find triangle strips
     according the the method that SGI uses, ie always
     choosing as the next triangle in our strip the triangle
     that has the least number of adjacencies. We do not have
     all triangles and will be triangulating on the fly those
     polygons that have more than 3 sides.
  */
  
  /* Build a table that has all the polygons sorted by the number
     of polygons adjacent to it.
  */
  /* Initialize it */
  Init_Table_SGI(num_faces);
  /* Build it */
  Build_SGI_Table(num_faces);
  
  /* We will have a structure to hold all the strips, until
     outputted.
  */
  InitStripTable();
  /*  Now we have the structure built to find the polygons according
      to the number of adjacencies. Now use the SGI Method to find
      strips according to the adjacencies
  */

  Find_StripsEx(output,&t,ties,triangulate,ON,&next_id);
  
}

///	P_Triangulate_Quad:
void CustomStripifier::P_Triangulate_Quad(int out_edge1,int out_edge2,
																					int in_edge1, int in_edge2,
																					int size,			int *index,
			       															int reversed, int face_id,
																					ListHead *pListHead, 
			       															P_ADJACENCIES temp,
			       															int where)
{
  int vertex4,vertex5,dummy=60;
  
  /*	This routine will nonblindly triangulate a quad, meaning
	that there is a definite input and a definite output
	edge that we must adhere to. Reversed will tell the orientation
	of the input edge. (Reversed is -1 is we do not have an input
	edge, in other words we are at the beginning of a strip.)
	Out_edge* is the output edge, and in_edge* is the input edge. 
	Index are the edges of the polygon
	and size is the size of the polygon. Begin is whether we are
	at the start of a new strip.
	Note that we will not necessarily triangulate the whole quad;
	maybe we will do half and leave the other half (a triangle)
	for later.
  */
  
  
  /*	If we do not have an input edge, then we can make our input
	edge whatever we like, therefore it will be easier to come
	out on the output edge.	In this case the whole quad is done.
  */
  if (reversed == -1)
    {
      vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
      vertex5 = Get_Other_Vertex(vertex4,out_edge1,out_edge2,index);
      Output_TriEx(vertex5,vertex4,out_edge1,NULL,-1,where);
      Output_TriEx(vertex4,out_edge1,out_edge2,NULL,-1,where);
      dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
      
      if (face_array[temp->face_id].head == pListHead)
        face_array[temp->face_id].pfNode = NULL;
      RemoveList(pListHead,(PLISTINFO) temp);
      return;
    }
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*  Are they consecutive so that we form a triangle to
      peel off, but cannot use the whole quad?
  */
  
  if (in_edge2 == out_edge1) 
    {
      /*	Output the triangle that comes out the correct
		edge. Save the other half for later.
      */
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
      Output_TriEx(in_edge1,in_edge2,out_edge2,NULL,-1,where);
      /*	Now we have a triangle used, and a triangle that is
		left for later.
      */
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,
		   face_id,&dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,in_edge2,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      /*	Put the new face in the proper bucket of adjacencies 
		There are 2 edges that need to be checked for the triangle
		that was just outputted. For the output edge we definitely
		will be decreasing the adjacency, but we must check for the
		input edge.
      */
      
      dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      dummy = Change_FaceEx(face_id,in_edge2,out_edge2,pListHead,TRUE);
      
      /*	Update the face data structure, by deleting the old
		face and putting in the triangle as the new face 
      */
      New_Face(face_id,in_edge1,out_edge2,vertex4);
      return;									  
    }
  else if (in_edge1 == out_edge1)
    {
      /*	We want to output the first triangle (whose output
		edge is not the one that we want.
		We have to find the vertex that we need, which is
		the other vertex which we do not have.
      */						
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge2,index);
      Output_TriEx(in_edge2,in_edge1,out_edge2,NULL,-1,where);
      /*	Now we have a triangle used, and a triangle that is
		left for later.
      */
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      dummy = Change_FaceEx(face_id,in_edge1,out_edge2,pListHead,TRUE);
      
      /*	Update the face data structure, by deleting the old
		face and putting in the triangle as the new face 
      */
      New_Face(face_id,in_edge2,out_edge2,vertex4);
      return;
    }
  
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_TriEx(in_edge2,in_edge1,out_edge1,NULL,-1,where);
      /*	Now we have a triangle used, and a triangle that is
		left for later.
      */
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      dummy = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Update the face data structure, by deleting the old
		face and putting in the triangle as the new face 
      */
      New_Face(face_id,in_edge2,out_edge1,vertex4);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      vertex4 = Get_Other_Vertex(in_edge1,in_edge2,out_edge1,index);
      Output_TriEx(in_edge1,in_edge2,out_edge1,NULL,-1,where);
      /*	Now we have a triangle used, and a triangle that is
		left for later.
      */
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      dummy = Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      dummy = Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Update the face data structure, by deleting the old
		face and putting in the triangle as the new face 
      */
      New_Face(face_id,in_edge1,out_edge1,vertex4);
      return;
    }
  
  /*	The final case is where we want to come out the opposite
	edge.
  */
  else
    {
      if( ((!reversed) && 
	   (out_edge1 == (AdjacentEx(in_edge1,in_edge2,index,size)))) ||
	  ((reversed) && 
	   (out_edge2 == (AdjacentEx(in_edge2,in_edge1,index,size)))))
	{
	  /*	We need to know the orientation of the input
		edge, so we know which way to put the diagonal.
                And also the output edge, so that we triangulate
                correctly. Does not need partial.
	  */
	  Output_TriEx(in_edge1,in_edge2,out_edge2,NULL,-1,where);
	  Output_TriEx(in_edge2,out_edge2,out_edge1,NULL,-1,where);
	  dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
	  
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	}
      else
	{
	  /*      Input and output orientation was reversed, so diagonal will
		  be reversed from above.
	  */
	  Output_TriEx(in_edge1,in_edge2,out_edge1,NULL,-1,where);
	  Output_TriEx(in_edge2,out_edge1,out_edge2,NULL,-1,where);
	  dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
	  
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	}
      return;
    }
}

///	P_Triangulate_Polygon:
void CustomStripifier::P_Triangulate_Polygon(	int out_edge1,int out_edge2,
																							int in_edge1, int in_edge2,
																							int size,	  	int *index,
																							FILE *fp,		  int reversed,
																							int face_id,	int *next_id,
				  																		ListHead *pListHead,
																							P_ADJACENCIES temp2,
				  																		int where)
{
  /*	We have a polygon greater than 4 sides, which we wish
	to partially triangulate
  */
  int next_bucket,vertex4,dummy = 60;
  int *temp;
  
  
  /*	Since we are calling this recursively, we have to check whether		
	we are down to the case of the quad.
  */
  if (size == 4)
    {
      P_Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
			 index,reversed,face_id,
			 pListHead,temp2,where);
      return;
    }
  
  /*	We do not have a specified input edge, and therefore we
	can make it anything we like, as long as we still come out 
	the output edge that we want.
  */
  if (reversed  == -1)
    {
      /*	Get the vertex for the last triangle, which is
		the one coming out the output edge, before we do
		any deletions to the list. We will be doing this
		bottom up.
      */
      vertex4 = AdjacentEx(out_edge1,out_edge2,index,size);
      temp = (int *) malloc(sizeof(int) * size);
      memcpy(temp,index,sizeof(int)*size);
      Delete_From_ListEx(out_edge2,index,size);
      /*	We do not have to partially triangulate, since
		we will do the whole thing, so use the whole routine
      */
      Triangulate_PolygonEx(vertex4,out_edge1,in_edge2,
			    vertex4,size-1,index,fp,
			    reversed,face_id,
			    where); 
      memcpy(index,temp,sizeof(int)*size);
      /*	Lastly do the triangle that comes out the output
		edge.
      */
      Output_TriEx(vertex4,out_edge1,out_edge2,NULL,-1,where);
      /*	We were able to do the whole polygon, now we
		can delete the whole thing from our data structure.
      */
      dummy = Update_AdjacenciesEx(face_id, &dummy, &dummy,&dummy,&dummy);
      
      if (face_array[temp2->face_id].head == pListHead)
        face_array[temp2->face_id].pfNode = NULL;
      RemoveList(pListHead,(PLISTINFO) temp2);
      return;
    }	  
  
  /*	These are the 5 cases that we can have for the output edge */
  
  /*  Are they consecutive so that we form a triangle to
      peel off that comes out the correct output edge, 
      but we cannot use the whole polygon?
  */
  if (in_edge2 == out_edge1) 
    {
      Output_TriEx(in_edge1,out_edge1,out_edge2,NULL,-1,where);
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge2,index,size);
      /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
      */
      New_Size_Face(face_id);
      return;
    }
  
  /*	Next case is where it is again consecutive, but the triangle
	formed by the consecutive edges do not come out of the
	correct output edge. (the input edge will be reversed in
	the next triangle)
  */
  else if (in_edge1 == out_edge1)
    {
      /*	Get vertex adjacent to in_edge2, but is not in_edge1 */
      Output_TriEx(in_edge2,in_edge1,out_edge2,NULL,-1,where);
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge1,index,size);
      /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
      */
      New_Size_Face(face_id);
      return;
    }
  
  /*	Consecutive cases again, but with the output edge reversed */
  else if (in_edge1 == out_edge2)
    {
      Output_TriEx(in_edge2,in_edge1,out_edge1,NULL,-1,where);
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge1,out_edge2,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge1,index,size);
      /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
      */
      New_Size_Face(face_id);
      return;
    }
  else if (in_edge2 == out_edge2)
    {
      Output_TriEx(in_edge1,in_edge2,out_edge1,NULL,-1,where);
      
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(out_edge2,out_edge1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,out_edge1,out_edge2,pListHead,TRUE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge2,index,size);
      /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
      */
      New_Size_Face(face_id);
      return;
    }
  
  /*	Else the edge is not consecutive, and it is sufficiently
	far away, for us not to make a conclusion at this time.
	So we can take off a triangle and recursively call this
	function.
  */
  else
    {
      if (!reversed)
	{
	  vertex4 = AdjacentEx(in_edge2,in_edge1,index,size);
	  Output_TriEx(in_edge1,in_edge2,vertex4,NULL,-1,where);
	  
	  /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
	  */
	  Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		       &dummy,&dummy,&dummy);
	  Delete_AdjEx(in_edge1,vertex4,&dummy,&dummy, 
		       face_id,&dummy,&dummy,&dummy);
	  
	  /*	Put the new face in the proper bucket of adjacencies */
	  next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,
				      pListHead,FALSE);
	  next_bucket = Change_FaceEx(face_id,in_edge1,vertex4,
				      pListHead,FALSE);
	  
	  /*	Create a new edgelist without the triangle that
		was just outputted.
	  */
	  Delete_From_ListEx(in_edge1,index,size);
	  /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
	  */
	  New_Size_Face(face_id);
	  
	  /*	Save the info for the new bucket, we will need it on
		the next pass for the variables, pListHead and temp 
	  */
	  pListHead = array[next_bucket];
	  temp2 = face_array[face_id].pfNode;
	  if (temp2 == NULL)
	    {
	      printf("There is an error finding the next polygon10\n",
		     next_bucket,face_id);
	      exit(0);
	    }
	  
	  P_Triangulate_Polygon(out_edge1,out_edge2,in_edge2,
				vertex4,size-1,index,fp,!reversed,
				face_id,next_id,pListHead,temp2,where);
	}
      else
	{
	  vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
	  Output_TriEx(in_edge2,in_edge1,vertex4,NULL,-1,where);
	  
	  /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
	  */
	  Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		       &dummy,&dummy,&dummy);
	  Delete_AdjEx(in_edge2,vertex4,&dummy,&dummy, 
		       face_id,&dummy,&dummy,&dummy);
	  
	  /*	Put the new face in the proper bucket of adjacencies */
	  next_bucket = Change_FaceEx(face_id,in_edge1,in_edge2,
				      pListHead,FALSE);
	  next_bucket = Change_FaceEx(face_id,in_edge2,vertex4,
				      pListHead,FALSE);
	  
	  /*	Create a new edgelist without the triangle that
		was just outputted.
	  */
	  Delete_From_ListEx(in_edge2,index,size);
	  
	  /*	Update the face data structure, by deleting the old
		face and putting in the polygon minus the triangle 
		as the new face, here we will be decrementing the size
		by one.
	  */
	  New_Size_Face(face_id);
	  
	  /*	Save the info for the new bucket, we will need it on
		the next pass for the variables, pListHead and temp 
	  */
	  pListHead = array[next_bucket];
	  temp2 = face_array[face_id].pfNode;
	  if (temp2 == NULL)
	    {
	      printf("There is an error finding the next polygon11 %d %d\n",
		     face_id,next_bucket);
	      exit(0);
	    }
	  
	  P_Triangulate_Polygon(out_edge1,out_edge2,vertex4,
				in_edge1,size-1,index,fp,!reversed,
				face_id,next_id,pListHead,temp2,where);
	}
      return;
    }
}

///	P_Triangulate:
void CustomStripifier::P_Triangulate(	int out_edge1,int out_edge2,int in_edge1,
			  															int in_edge2,	int size,			int *index,
			  															FILE *output,	int reversed,	int face_id,
			  															int *next_id,	ListHead *pListHead, 
			  															P_ADJACENCIES temp,int where)
{
  
  if (size == 4)
    P_Triangulate_Quad(out_edge1,out_edge2,in_edge1,in_edge2,size,
		       index,reversed,face_id,
		       pListHead,temp,where);
  else
    P_Triangulate_Polygon(out_edge1,out_edge2,in_edge1,in_edge2,size,
			  index,output,reversed,face_id,next_id,
			  pListHead,temp,where);
}

void CustomStripifier::Partial_Triangulate(int size,int *index, 
			 FILE *output,int next_face_id,int face_id,
			 int *next_id,ListHead *pListHead,
			 P_ADJACENCIES temp, int where)
{
  int id1,id2,id3;
  int nedge1,nedge2;
  int reversed;
  
  /*	We have a polygon that has to be triangulated and we cannot
	do it blindly, ie we will try to come out on the edge that
	has the least number of adjacencies, But also we do not
	want to triangulate the whole polygon now, so that means 
	we will output the least number of triangles that we can
	and then update the data structures, with the polygon
	that is left after we are done.
  */
  Last_Edge(&id1,&id2,&id3,0);
  
  /*	Find the edge that is adjacent to the new face ,
	also return whether the orientation is reversed in the
	face of the input edge, which is id2 and id3.
  */
  reversed = Get_EdgeEx(&nedge1,&nedge2,index,next_face_id,size,id2,id3);
  
  /*   Input edge and output edge can be the same if there are more than
       one polygon on an edge 
  */
  if ( ((nedge1 == id2) && (nedge2 == id3)) ||
       ((nedge1 == id3) && (nedge2 == id2)) )
    /*   Set output edge arbitrarily but when come out of here the
	 next face will be on the old output edge (identical one)
    */
    nedge2 = Return_Other(index,id2,id3);
  
  /*	Do the triangulation */	
  P_Triangulate(nedge1,nedge2,id2,id3,size,index,output,reversed,
		face_id,next_id,pListHead,temp,where);
}

///	Input_Edge:
void CustomStripifier::Input_Edge(int face_id,	int *index,
																	int size, 		int in_edge1,
																	int in_edge2, ListHead *pListHead,
		       												int where)
{
  /* The polygon had an input edge, specified by input1 and input2 */
  
  int output1,next_bucket;
  int vertex4, vertex5,dummy=60;
  
  output1 = Get_Output_Edge(face_id,size,index,in_edge1,in_edge2);
  vertex5 = AdjacentEx(in_edge2,in_edge1,index,size); 
  vertex4 = AdjacentEx(in_edge1,in_edge2,index,size);
  
  if (vertex4 == output1)
    {
      Output_TriEx(in_edge2,in_edge1,output1,NULL,-1,where);
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(in_edge2,output1,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,in_edge2,output1,pListHead,FALSE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge2,index,size);
      
    }	
  else if (vertex5 == output1)
    {
      Output_TriEx(in_edge1,in_edge2,vertex5,NULL,-1,where);
      /*	Now delete the adjacencies by one for all the faces
		that are adjacent to the triangle that we just outputted.
      */
      Delete_AdjEx(in_edge1,in_edge2,&dummy,&dummy,face_id,
		   &dummy,&dummy,&dummy);
      Delete_AdjEx(in_edge1,vertex5,&dummy,&dummy, 
		   face_id,&dummy,&dummy,&dummy);
      /*	Put the new face in the proper bucket of adjacencies */
      next_bucket=Change_FaceEx(face_id,in_edge1,in_edge2,pListHead,FALSE);
      next_bucket=Change_FaceEx(face_id,in_edge1,vertex5,pListHead,FALSE);
      
      /*	Create a new edgelist without the triangle that
		was just outputted.
      */
      Delete_From_ListEx(in_edge1,index,size);
    }
  
  /*	Update the face data structure, by deleting the old
	face and putting in the polygon minus the triangle 
	as the new face, here we will be decrementing the size
	by one.
  */
  New_Size_Face(face_id);
  return;
}

///	Inside_Polygon:
void CustomStripifier::Inside_Polygon(int size,int *index,
		    int face_id,ListHead *pListHead, int where)
{
  /* We know that we have a polygon that is greater than 4 sides, and
     that it is better for us to go inside the polygon for the next
     one, since inside will have less adjacencies than going outside.
     So, we are not doing partial for a part of the polygon.
  */
  int id1,id2,id3;
  int new1,new2;
  
  Last_Edge(&id1,&id2,&id3,0);
  
  /*  See if the input edge existed in the polygon, that will help us */
  if (Exist(face_id,id2,id3))
    Input_Edge(face_id,index,size,id2,id3,pListHead,where);
  else
    {
      /*  Make one of the input edges 
	  We will choose it by trying to get an edge that has something
	  in common with the last triangle, or by getting the edge that
	  is adjacent to the least number of thigs, with preference given
	  to the first option
      */
      
      Get_Input_Edge(index,id1,id2,id3,&new1,&new2,size,face_id);
      Input_Edge(face_id,index,size,new1,new2,pListHead,where);
    }
}

///	Finished:
int CustomStripifier::Finished(int *swap, FILE *output, int startnewstrip)
{
  /*   We have finished all the triangles, now is time to output to
       the data file. In the strips data structure, every three ids
       is  a triangle. Now we see whether we can swap, or make a new strip
       or continue the strip, and output the data accordingly to the
       data file. 
  */
  int num,x,vertex1,vertex2;
  ListHead *pListHead;
  int id[2],other1,other2,index = 0,a,b,c;
  P_STRIPS temp1,temp2,temp3,temp4,temp5,temp6;
  BOOL cptexture;
  *swap =0;
  
  cptexture = text;
  pListHead = strips[0];
  if (pListHead == NULL)
	return 0;
  
  num = NumOnList(pListHead);
  //printf ("There are %d triangles in the extend\n",num/3);
  
  // Go through the list triangle by triangle
  temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 0);
  temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 1);
  temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 2);
  
  // Next triangle for lookahead
  temp4 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 3);

  // There is only one polygon in the strip
  if (temp4 == NULL)
  {
	// Data might be mixed and we do not have textures for some of the vertices
    if ((text) &&  (vt[temp3->face_id] == 0))
		cptexture = FALSE;
    if ((norm) && (!cptexture)) {
		if (startnewstrip && orient) // If we want to keep orientation
			preserve_strip_orientation_with_normal(output, temp3->face_id+1,vn[temp3->face_id]+1,
						temp2->face_id+1,vn[temp2->face_id]+1, temp1->face_id+1,vn[temp1->face_id]+1);
		
		fprintf(output," %d//%d %d//%d %d//%d", temp3->face_id+1,vn[temp3->face_id]+1,
					temp2->face_id+1,vn[temp2->face_id]+1, temp1->face_id+1,vn[temp1->face_id]+1);
	}
	else if ((cptexture) && (!norm)) {
		if (startnewstrip && orient) /* If we want to keep orientation */
			preserve_strip_orientation_with_texture(output, temp3->face_id+1,vt[temp3->face_id]+1,
				temp2->face_id+1,vt[temp2->face_id]+1,	temp1->face_id+1,vt[temp1->face_id]+1);
		
		fprintf(output," %d/%d %d/%d %d/%d", temp3->face_id+1,vt[temp3->face_id]+1,
					temp2->face_id+1,vt[temp2->face_id]+1, temp1->face_id+1,vt[temp1->face_id]+1);
	}
    else if ((cptexture)&& (norm)) {
        if (startnewstrip && orient) /* If we want to keep orientation */
          preserve_strip_orientation_with_texture_and_normal(output, temp3->face_id+1,vt[temp3->face_id]+1,vn[temp3->face_id]+1,
				temp2->face_id+1,vt[temp2->face_id]+1,vn[temp2->face_id]+1, temp1->face_id+1,vt[temp1->face_id]+1,vn[temp1->face_id]+1);
        
        fprintf(output," %d/%d/%d %d/%d/%d %d/%d/%d", temp3->face_id+1,vt[temp3->face_id]+1,vn[temp3->face_id]+1,
                temp2->face_id+1,vt[temp2->face_id]+1,vn[temp2->face_id]+1, temp1->face_id+1,vt[temp1->face_id]+1,vn[temp1->face_id]+1);
    }
    else 
    {
		if (startnewstrip && orient) /* If we want to keep orientation */
			preserve_strip_orientation(output, temp3->face_id+1,temp2->face_id+1,temp1->face_id+1);
	  
		fprintf(output," %d %d %d", temp3->face_id+1,temp2->face_id+1,temp1->face_id+1);
		mi_vector[num_tiras].push_back(temp3->face_id);
		mi_vector[num_tiras].push_back(temp2->face_id);
		mi_vector[num_tiras].push_back(temp1->face_id);
    }
    Free_Strips();

    return 1;
  }
  
  // We have a real strip
  temp5 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 4);
  temp6 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 5);
  
  if ((temp1 == NULL) || (temp2 == NULL) || (temp3 == NULL) || (temp5 == NULL) || (temp6 == NULL))
  {
	printf("There is an error in the output of the triangles\n");
    exit(0);
  }
  
  // Find the vertex in the first triangle that is not in the second
  vertex1 = Different(temp1->face_id,temp2->face_id,temp3->face_id, temp4->face_id,temp5->face_id,temp6->face_id, &other1,&other2);
  // Find the vertex in the second triangle that is not in the first
  vertex2 = Different(temp4->face_id,temp5->face_id,temp6->face_id, temp1->face_id,temp2->face_id,temp3->face_id, &other1,&other2);
  
  // Lookahead for the correct order of the 2nd and 3rd vertex of the first triangle
  temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 6);
  temp2 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 7);
  temp3 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, 8);
  
  if (temp1 != NULL)
    other1 = Different(temp3->face_id,temp4->face_id,temp5->face_id, temp1->face_id,temp2->face_id,temp3->face_id,&other1,&a);
  
  id[index] = vertex1; index = !index;
  id[index] = other1; index = !index;
  id[index] = other2; index = !index;
  
  a = temp4->face_id; 
  b = temp5->face_id; 
  c = temp6->face_id;
  
	/*
  // If we need to rearrange the first sequence because otherwise there would have been a swap.
  if ((temp3 != NULL) && (text) && ( vt[temp3->face_id]==0))
    cptexture = FALSE;
  if ((norm) && (!cptexture)) {
    if (orient && startnewstrip) // If we want to keep orientation
      preserve_strip_orientation_with_normal(output, vertex1+1,vn[vertex1]+1, other1+1,vn[other1]+1, other2+1,vn[other2]+1);
    
    fprintf(output," %d//%d %d//%d %d//%d", vertex1+1,vn[vertex1]+1, other1+1,vn[other1]+1, other2+1,vn[other2]+1);
  }
  else if ((cptexture) && (!norm)) {
    if (orient && startnewstrip) // If we want to keep orientation
      preserve_strip_orientation_with_texture(output, vertex1+1,vt[vertex1]+1, other1+1,vt[other1]+1, other2+1,vt[other2]+1);
    
    fprintf(output," %d/%d %d/%d %d/%d", vertex1+1,vt[vertex1]+1, other1+1,vt[other1]+1, other2+1,vt[other2]+1);
  }
  else if ((cptexture) && (norm)) {
    if (orient && startnewstrip) // If we want to keep orientation
      preserve_strip_orientation_with_texture_and_normal(output, vertex1+1,vt[vertex1]+1,vn[vertex1]+1,
							 other1+1,vt[other1]+1,vn[other1]+1, other2+1,vt[other2]+1,vn[other2]+1);
    
    fprintf(output," %d/%d/%d %d/%d/%d %d/%d/%d", vertex1+1,vt[vertex1]+1,vn[vertex1]+1,
            other1+1,vt[other1]+1,vn[other1]+1, other2+1,vt[other2]+1,vn[other2]+1);
  }
  else
  {
	*/
	if (orient && startnewstrip) // If we want to keep orientation
		preserve_strip_orientation(output,vertex1+1,other1+1,other2+1);
    
    fprintf(output," %d %d %d",vertex1+1,other1+1,other2+1);
	mi_vector[num_tiras].push_back(vertex1);
	mi_vector[num_tiras].push_back(other1);
	mi_vector[num_tiras].push_back(other2);

	/*
  }
  */
  for (x = 6; x < num ; x = x+3)
  {
	//    Get the next triangle
    temp1 = ( P_STRIPS ) PeekList( pListHead, LISTHEAD, x);       
    temp2 = ( P_STRIPS ) GetNextNode(temp1);                                      
    temp3 = ( P_STRIPS ) GetNextNode(temp2);                                      
      
    //    Error checking
    if (!(member(id[0],a,b,c)) || !(member(id[1],a,b,c)) || !(member(vertex2,a,b,c)))
    {
		// If we used partial we might have a break in the middle of a strip
		fprintf(output,"\nt");
        startnewstrip = 1;
		mi_vector_tipo nada;
		mi_vector.push_back(nada);
		num_tiras++;
        // Find the vertex in the first triangle that is not in the second
        vertex1 = Different(a,b,c,temp1->face_id,temp2->face_id,temp3->face_id,&other1,&other2);
        // Find the vertex in the second triangle that is not in the first
        vertex2 = Different(temp1->face_id,temp2->face_id,temp3->face_id, a,b,c,&other1,&other2);
	  
        id[index] = vertex1; index = !index;
        id[index] = other1; index = !index;
        id[index] = other2; index = !index;
	}
      
    if ((temp1 == NULL ) || (temp2 == NULL) || (temp3 == NULL))
    {
		printf("There is an error in the triangle list \n");
        exit(0);
    }
      
    if ((id[0] == id[1]) || (id[0] == vertex2))
        continue;
      
    if ((member(id[index],temp1->face_id,temp2->face_id,temp3->face_id)))
    {
		if ((text) && ( vt[id[index]]==0))
			cptexture = FALSE;
        if ((!norm) && (!cptexture))
		{
            fprintf(output," %d",id[index]+1);
			mi_vector[num_tiras].push_back(id[index]);
		}
        else if ((norm) && (!cptexture))
            fprintf(output," %d//%d",id[index]+1,vn[id[index]]+1);
        else if ((!norm) && (cptexture))
            fprintf(output," %d/%d",id[index]+1,vt[id[index]]+1);
        else
            fprintf(output," %d/%d/%d", id[index]+1,vt[id[index]]+1,vn[id[index]]+1);

        index = !index;
        *swap = *swap + 1;
	}
      
    if ((text) && ( vt[vertex2]==0))
		cptexture = FALSE;
    if ((!norm) && (!cptexture))
	{
        fprintf(output,"\nq %d",vertex2+1);
		mi_vector[num_tiras].push_back(vertex2);
	}
    else if ((norm) && (!cptexture))
        fprintf(output,"\nq %d//%d",vertex2+1,vn[vertex2]+1);
    else if ((!norm) && (cptexture))
        fprintf(output,"\nq %d/%d",vertex2+1,vt[vertex2]+1);
    else
        fprintf(output,"\nq %d/%d/%d",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
      
    id[index] = vertex2; index = !index;
      
    //    Get the next vertex not in common
		vertex2	=	Different(temp1->face_id,temp2->face_id,temp3->face_id, a,b,c,&other1,&other2);
		a				=	temp1->face_id;
		b				=	temp2->face_id;
		c				=	temp3->face_id;
  }
  //   Do the last vertex
  if ((text) && (vt[vertex2]==0))
  {
	if (cptexture)
		fprintf(output,"\nq");
    cptexture = FALSE;
  }

  if ((!norm) && (!cptexture))
  {
    fprintf(output," %d",vertex2+1);
	mi_vector[num_tiras].push_back(vertex2);
  }
  else if ((norm) && (!cptexture))
    fprintf(output," %d//%d",vertex2+1,vn[vertex2]+1);
  else if ((!norm) && (cptexture))
    fprintf(output," %d/%d",vertex2+1,vt[vertex2]+1);
  else
    fprintf(output," %d/%d/%d",vertex2+1,vt[vertex2]+1,vn[vertex2]+1);
  
  Free_Strips();
  return (num/3);       
}

///	Output_Tri:
void CustomStripifier::Output_Tri(int id1, int id2, int id3,BOOL end)
{
  /*   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.
  */
  
  int temp1,temp2,temp3;
  
  /*  Make sure we do not have an error */
  /*    There are degeneracies in some of the files */
  if ( (id1 == id2) || (id1 == id3) || (id2 == id3))
    {
      printf("Degenerate triangle %d %d %d\n",id1,id2,id3);
      exit(0);
    }
  else
    {
      Last_Edge(&temp1,&temp2,&temp3,0);
      Add_Id_Strips(id1,end);
      Add_Id_Strips(id2,end);
      Add_Id_Strips(id3,end);
      Last_Edge(&id1,&id2,&id3,1);
    }
}

///	Polygon_Output:
int CustomStripifier::Polygon_Output(	P_ADJACENCIES temp,	int face_id,
																			int bucket,		  		ListHead *pListHead,
																			BOOL first, 				int *swaps,
			  															FILE *bands,				int color1,
																			int color2,					int color3,
																			BOOL global,		  	BOOL end)
{
  ListHead *pListFace;
  PF_FACES face;
  int next_face_id,next_bucket,e1,e2,e3,other1,other2,other3;
  P_ADJACENCIES lpListInfo; 
  int ties=0;
  
  /* We have a polygon to output, the id is face id, and the number
     of adjacent polygons to it is bucket. This routine extends the patches from
     either end to make longer triangle strips.
  */
  
  
  /*  Now get the edge */
  Last_Edge(&e1,&e2,&e3,0);
  
  /*  Get the polygon with id face_id */
  pListFace  = PolFaces[face_id];
  face = (PF_FACES) PeekList(pListFace,LISTHEAD,0);
  
  /*  We can't go any more */
  if ((face->nPolSize == 1) || ((face->nPolSize == 4) && (global)))
    /* if global, then we are still doing patches */
    {
      /*     Remove it from the list so we do not have to waste
	     time visiting it in the future, or winding up in an infinite loop
	     if it is the first on that we are looking at for a possible strip
      */
      if (face->nPolSize == 1) {
	if (face_array[temp->face_id].head == pListHead)
	  face_array[temp->face_id].pfNode = NULL;
	RemoveList(pListHead,(PLISTINFO) temp);
      }
      if (first)
	return 0;
      else
	return (Finished(swaps,bands,0));
    }
  
  if (face->nPolSize == 3)
    {
      /*      It is already a triangle */
      if (bucket == 0)
	{
	  /*      It is not adjacent to anything so we do not have to
		  worry about the order of the sides or updating adjacencies
	  */
	  
	  next_face_id = Different(*(face->pPolygon),*(face->pPolygon+1),
				   *(face->pPolygon+2),
				   e1,e2,e3,&other1,&other2);  
	  face->nPolSize = 1;
	  
	  /* If this is the first triangle in the strip */
	  if ((e2 == 0) && (e3 ==0))
	    {
	      e2 = other1;
	      e3 = other2;
	    }
	  
	  Output_Tri(e2,e3,next_face_id,end);
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  return (Finished(swaps,bands,0));
	}
      
      
      /*  It is a triangle with adjacencies. This means that we
	  have to:
	  1. Update the adjacencies in the list, because we are
	  using this polygon and it will be deleted.
	  2. Get the next polygon.
      */
      else
	{
	  /*   Return the face_id of the next polygon we will be using,
	       while updating the adjacency list by decrementing the
	       adjacencies of everything adjacent to the current triangle.
	  */
	  
	  next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
	  /*  Maybe we deleted something in a patch and could not
	      find an adj polygon */
	  if (next_face_id == -1)
	    {
	      Output_Tri(*(face->pPolygon),*(face->pPolygon+1),
			 *(face->pPolygon+2),end);
	      face->nPolSize = 1;
	      if (face_array[temp->face_id].head == pListHead)
		face_array[temp->face_id].pfNode = NULL;
	      RemoveList(pListHead,(PLISTINFO) temp);
	      return (Finished(swaps,bands,0));
	    }
	  
	  
	  /*      Find the other vertex to transmit in the triangle */
	  e3 = Return_Other(face->pPolygon,e1,e2);
	  Last_Edge(&other1,&other2,&other3,0);
	  
	  if ((other2 != 0) && (other3 != 0))
	    {
	      /*   See which vertex in the output edge is not in the input edge */
	      if ((e1 != other2) && (e1 != other3))
		e3 = e1;
	      else if ((e2 != other2) && (e2 != other3))
		e3 = e2;
	      else
		{
		  printf("There is an error in the tri with adj\n");
		  exit(0);
		}
	      
	      /*   See which vertex of the input edge is not in the output edge */
	      if ((other2 != e1) && (other2 != e2))
		{
		  other1 = other2;
		  other2 = other3;
		}
	      else if ((other3 != e1) && (other3 != e2))
		other1 = other3;
	      else
		{
		  printf("There is an error in getting the tri with adj\n");
		  exit(0);
		}
	      
	    }
	  else
	    {
	      /*     We are the first triangle in the strip and the starting edge
		     has not been set yet
	      */
	      /*  Maybe we deleted something in a patch and could not
		  find an adj polygon */
	      if (next_face_id == -1)
		{
		  Output_Tri(*(face->pPolygon),*(face->pPolygon+1),
			     *(face->pPolygon+2),end);
		  face->nPolSize = 1;
		  face_array[temp->face_id].pfNode = NULL;
		  RemoveList(pListHead,(PLISTINFO) temp);
		  return (Finished(swaps,bands,0));
		}
	      
	      other1 = e3;
	      e3 = e2;
	      other2 = e1;
	    }
	  
	  /*   At this point the adjacencies have been updated  and we
	       have the next polygon id 
	  */
	  
	  Output_Tri(other1,other2,e3,end);
	  face->nPolSize = 1;
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  
	  /*  Maybe we deleted something in a patch and could not
	      find an adj polygon */
	  if (next_face_id == -1)
	    return (Finished(swaps,bands,0));
	  
	  if (Done(next_face_id,&next_bucket) == NULL)
	    {
	      printf("We deleted the next face 4%d\n",next_face_id);
	      exit(0);
	    }
	  
	  pListHead = array[next_bucket]; 
	  lpListInfo = face_array[next_face_id].pfNode;
	  if (lpListInfo == NULL)
	    {
	      printf("There is an error finding the next polygon3 %d\n",
		     next_face_id);
	      exit(0);
	    }
	  return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
				 pListHead, FALSE, swaps,bands,
				 color1,color2,color3,global,end));
	  
	}
    }
  
  else
    {
      /*   It is not a triangle, we have to triangulate it .
	   Since it is not adjacent to anything we can triangulate it
	   blindly
      */
      if (bucket == 0)
        {
	  /*   It is the first polygon in the strip, therefore there is no
	       input edge to start with.
	  */
	  if ((e2 == 0) && (e3 ==0))
	    Blind_Triangulate(face->nPolSize,face->pPolygon,TRUE,1);
	  
	  else
	    Blind_Triangulate(face->nPolSize,face->pPolygon,FALSE,1);
	  
	  if (face_array[temp->face_id].head == pListHead)
	    face_array[temp->face_id].pfNode = NULL;
	  RemoveList(pListHead,(PLISTINFO) temp);
	  
	  /*      We will be at the beginning of the next strip. */
	  face->nPolSize = 1;
	  return (Finished(swaps,bands,0));
        }
      
      
      else
        {
	  
	  
	  /*  WHOLE triangulation */
	  /*  It is not a triangle and has adjacencies. 
	      This means that we have to:
	      1. Triangulate this polygon, not blindly because
	      we have an edge that we want to come out on, that
	      is the edge that is adjacent to a polygon with the
	      least number of adjacencies. Also we must come in
	      on the last seen edge.
	      2. Update the adjacencies in the list, because we are
	      using this polygon .
	      3. Get the next polygon.
	  */
	  /*      Return the face_id of the next polygon we will be using,
		  while updating the adjacency list by decrementing the
		  adjacencies of everything adjacent to the current polygon.
	  */
	  
	  next_face_id = Update_Adjacencies(face_id, &next_bucket, &e1,&e2,&ties);
	  
	  /*  Maybe we deleted something in a patch and could not
	      find an adj polygon */
	  if (next_face_id == -1)
	    {
	      
	      /*   If we are at the first polygon in the strip and
		   there is no input
		   edge, then begin is TRUE
	      */
	      if ((e2 == 0) && (e3 == 0))
		Blind_Triangulate(face->nPolSize,face->pPolygon,TRUE,1);
	      
	      else
		Blind_Triangulate(face->nPolSize,face->pPolygon,FALSE,1);
	      
	      if (face_array[temp->face_id].head == pListHead)
		face_array[temp->face_id].pfNode = NULL;
	      RemoveList(pListHead,(PLISTINFO) temp);
	      
	      /*      We will be at the beginning of the next strip. */
	      face->nPolSize = 1;
	      return (Finished(swaps,bands,0));
	    }
	  
	  if (Done(next_face_id,&next_bucket) == NULL)
	    {
	      printf("We deleted the next face 6 %d %d\n",next_face_id,face_id);
	      exit(0);
	    }
	  
	  Non_Blind_Triangulate(face->nPolSize,face->pPolygon, 
				bands,next_face_id,face_id,1,
				color1,color2,color3);
	  
	  if (face_array[temp->face_id].head == pListHead)        
	    face_array[temp->face_id].pfNode = NULL; 
	  RemoveList(pListHead,(PLISTINFO) temp);
	  face->nPolSize = 1;
	  pListHead = array[next_bucket];
	  lpListInfo = face_array[next_face_id].pfNode;
	  
	  if (lpListInfo == NULL)
	    {
	      printf("There is an error finding the next polygon2 %d %d\n",
		     next_face_id,next_bucket);
	      exit(0);
	    }
	  return (Polygon_Output(lpListInfo,next_face_id,next_bucket,
				 pListHead, FALSE, swaps,bands,
				 color1,color2,color3,global,end));
        }
      
    }
}       

///	Extend_Face:
int CustomStripifier::Extend_Face(int		face_id,
																	int		e1,
																	int		e2,
																	int		*swaps,
																	FILE	*bands,
																	int		color1,
																	int		color2,
																	int		color3,
																	int		*vert_norm,
																	int		normals,
																	int		*vert_texture,
																	int		texture)
{
  int						dummy	=	0;
	int						next_bucket;
  P_ADJACENCIES	lpListInfo;   
  ListHead			*pListHead;
  
  /*    Try to extend backwards off of the local strip that we just found */
  
  vn = vert_norm;
  vt = vert_texture;
  norm = normals;
  text = texture;
  
  *swaps = 0;
  /*	Find the face that is adjacent to the edge and is not the
	current face.
  */
  face_id = Find_Face(face_id, e1, e2,&next_bucket);
  if (face_id == -1)
    return 0;
  
  pListHead = array[next_bucket];
  lpListInfo = face_array[face_id].pfNode;
  
  if (lpListInfo == NULL)
    {
      printf("There is an error finding the next polygon3 %d\n",face_id);
      exit(0);
    }
  Last_Edge(&dummy,&e1,&e2,1);
  
  /*  Find a strip extending from the patch and return the cost */
  return (Polygon_Output(lpListInfo,face_id,next_bucket,pListHead,TRUE,swaps,
			 bands,color1,color2,color3,TRUE,TRUE));
}

///	ParseAndFreeList:
void CustomStripifier::ParseAndFreeList( ListHead *pListHead )
{
  PLISTINFO			value;
  register	int	c;
	register	int	num;
  
  /*    Freeing a linked list */
  num	=	NumOnList(pListHead);

  for (c = 0; c< num; c++)
	{
    value =   RemHead(pListHead);
	}
} 

///	Free_Strips:
void CustomStripifier::Free_Strips()
{
  /*    Free strips data structure */
  if (strips[0] == NULL)
    return;
  else
    ParseAndFreeList(strips[0]);
}

///	FreeFaceTable:
void CustomStripifier::FreeFaceTable(int nSize)
{
  register int nIndex;
  
  for ( nIndex=0; nIndex < nSize; nIndex++ )
    { 
      if ( PolFaces[nIndex] != NULL ) 
	ParseAndFreeList( PolFaces[nIndex] );
    }
  free( PolFaces );
}

///	FreeEdgeTable:
void CustomStripifier::FreeEdgeTable(int nSize)
{
  register int nIndex;
  
  for ( nIndex=0; nIndex < nSize; nIndex++ )
    {
      if ( PolEdges[nIndex] != NULL )
	ParseAndFreeList( PolEdges[nIndex] );
    }
  free( PolEdges );
}

///	End_Face_Struct:
void CustomStripifier::End_Face_Struct(int numfaces)
{
  FreeFaceTable(numfaces);
}

///	End_Edge_Struct:
void CustomStripifier::End_Edge_Struct(int numverts)
{
  FreeEdgeTable(numverts);
}

///	Calculate_Walks:
int CustomStripifier::Calculate_Walks(int lastvert,int y, PF_FACES temp2)
{
  /* Find the length of the walk */
  
  int previous_edge1, previous_edge2;
  register int nextvert,numverts,counter,walk=0;
  BOOL flag;
  F_EDGES *node;
  ListHead *pListHead;
  static int seen = 0;
  
  /* Find the edge that we are currently on */
  if (y != 3)
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon + y + 1);
    }
  else
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon);
    }
  
  temp2->seen = seen;
  counter = y;
  
  /*Find the adjacent face to this edge */
  node = *(temp2->VertandId+y);			
  if (node->edge[2] != lastvert)
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  
  /* Keep walking in this direction until we cannot do so */
  while ((nextvert != lastvert) && (nextvert != -1))
    {
      walk++;
      pListHead = PolFaces[nextvert];
      temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      numverts = temp2->nPolSize;
      if ((numverts != 4) || (temp2->seen == seen))
	{
	  walk--;
	  nextvert = -1;
	}
      else
	{
	  temp2->seen = seen;
	  /* Find edge that is not adjacent to the previous one */
	  counter = 0;
	  flag = TRUE;
	  while ((counter < 3) && (flag))
	    {
	      if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
		    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
		   ((*(temp2->pPolygon+counter) == previous_edge2) || 
		    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
		counter++;		
	      else
		flag = FALSE;	
	    }
	  /* Get the IDs of the next edge */
	  if (counter < 3)
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon + counter + 1);
	    }
	  else
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon);
	    }
	  
	  node = *(temp2->VertandId + counter);
	  if (node->edge[1] == nextvert)
	    nextvert = node->edge[2];
	  else
	    nextvert = node->edge[1];
	}
    }
  seen++;
  return walk;
}

///	Check_Right:
BOOL CustomStripifier::Check_Right(	int last_seen,PF_FACES temp2,
																		int y,int face_id)
{
  /* Check when we last saw the face to the right of the current
     one. We want to have seen it just before we started this strip
  */
  
  F_EDGES *node;
  ListHead *pListHead;
  register int nextvert,oldy;
  PF_FACES t;
  
  oldy = y;
  if (y != 3)
    y = y+1;
  else
    y = 0;
  node = *(temp2->VertandId + y);
  if (face_id == node->edge[1])
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  
  if (nextvert == -1)
    return FALSE;
  
  pListHead = PolFaces[nextvert];
  t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
  if (t->seen != (last_seen - 1))
    {
      /* maybe because of the numbering, we are not
	 on the right orientation, so we have to check the
	 opposite one to be sure 
      */
      if (oldy != 0)
	y = oldy-1;
      else
	y = 3;
      node = *(temp2->VertandId + y);
      if (face_id == node->edge[1])
	nextvert = node->edge[2];
      else
	nextvert = node->edge[1];
      if (nextvert == -1)
	return FALSE;
      pListHead = PolFaces[nextvert];
      t = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      if (t->seen != (last_seen - 1))
	return FALSE;
    }
  return TRUE;
}

///	Update_and_Test:
int CustomStripifier::Update_and_Test(PF_FACES temp2,int y,
																			BOOL first,int distance,
			   															int lastvert, int val)
{
  
  static int last_seen = 17;
  int previous_edge1, previous_edge2;
  register int original_distance,nextvert,numverts,counter;
  BOOL flag;
  F_EDGES *node;
  ListHead *pListHead;
  
  original_distance = distance;
  /* Find the edge that we are currently on */
  if (y != 3)
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon + y + 1);
    }
  else
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon);
    }
  
  temp2->seen = val;
  temp2->seen2 = val;
  
  node = *(temp2->VertandId+y);                   
  if (lastvert != node->edge[2])
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  
  /* Keep walking in this direction until we cannot do so  or
     we go to distance */
  while ((distance > 0)  && (nextvert != lastvert) && (nextvert != -1))
    {
      distance--;
      
      pListHead = PolFaces[nextvert];
      temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      temp2->seen = val;
      
      if (temp2->seen2 == val)
	{
	  last_seen++;
	  return (original_distance - distance);
	}
      
      temp2->seen2 = val;
      
      numverts = temp2->nPolSize;
      
      if (numverts != 4)
	nextvert = -1;
      
      else if ((!first) && (!(Check_Right(last_seen,temp2,y,nextvert))))
	{
	  last_seen++;
	  return (original_distance - distance);
	}
      else
	{
	  /* Find edge that is not adjacent to the previous one */
	  counter = 0;
	  flag = TRUE;
	  while ((counter < 3) && (flag))
	    {
	      if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
		    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
		   ((*(temp2->pPolygon+counter) == previous_edge2) ||
		    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
		counter++;
	      else
		flag = FALSE;
	    }
	  /* Get the IDs of the next edge */
	  if (counter < 3)
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon + counter + 1);
	    }
	  else
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon);
	    }
	  if      ( ((*(temp2->walked+counter) == -1) && 
		     (*(temp2->walked+counter+2) == -1)))
	    {
	      printf("There is an error in the walks!\n");
	      printf("1Code %d %d \n",*(temp2->walked+counter),
		     *(temp2->walked+counter+2));
	      exit(0);
	    }
	  else
	    {
	      if      ((*(temp2->walked+counter) == -1) && 
		       (*(temp2->walked+counter-2) ==  -1))
		{
		  printf("There is an error in the walks!\n");
		  printf("2Code %d %d \n",*(temp2->walked+counter),
			 *(temp2->walked+counter-2));
		  exit(0);
		}
	    }
	  node = *(temp2->VertandId + counter);
	  y = counter;
	  if (node->edge[1] == nextvert)
	    nextvert = node->edge[2];
	  else
	    nextvert = node->edge[1];
	}
    }
  
  last_seen++;
  
  if  (distance != 0)  
    {
      if (((nextvert == -1) || (nextvert == lastvert)) && (distance != 1))
	return (original_distance - distance);
    }
  return original_distance;
}

///	Test_Adj:
int CustomStripifier::Test_Adj(PF_FACES temp2,int x,int north,int distance,int lastvert, int value)
{
  /* if first time, then just update the last seen field */
  if (x==1)
    return(Update_and_Test(temp2,north,TRUE,distance,lastvert,value));
  /* else we have to check if we are adjacent to the last strip */
  else
    return(Update_and_Test(temp2,north,FALSE,distance,lastvert,value));
}

///	Find_Max:
int CustomStripifier::Find_Max(	PF_FACES temp2,	int lastvert,
																int north,			int left,
		    												int *lastminup,	int *lastminleft)
{
  int temp,walk,counter,minup,x,band_value;
  int previous_edge1, previous_edge2;
  F_EDGES	*node;
  ListHead *pListHead;
  BOOL flag;	
  static int last_seen = 0;
  register int smallest_so_far,nextvert,max=-1;         
  
  *lastminup = MAX_BAND;
  *lastminleft = 1;
  
  if (left == 3)
    {
      previous_edge1 = *(temp2->pPolygon + left);
      previous_edge2 = *(temp2->pPolygon);
    }
  
  else
    {
      previous_edge1 = *(temp2->pPolygon + left + 1);
      previous_edge2 = *(temp2->pPolygon + left);
    }
  
  temp2->seen = last_seen;
  walk = *(temp2->walked + left);
  
  for (x=1;x<=(walk+1); x++)
    {
      /*   test to see if we have a true band
	   that is, are they adjacent to each other
      */
      
      minup = *(temp2->walked + north) + 1;
      
      /*	if we are at the very first face, then we do not
		have to check the adjacent faces going up
		and our north distance is the distance of this face's
		north direction. 
      */
      if (x == 1) 
	{
	  *lastminup = minup;
	  minup = Test_Adj(temp2,x,north,*lastminup,lastvert,last_seen);
	  *lastminup = minup;
	  smallest_so_far = minup;	
	}
      
      
      /* find the largest band that we can have */
      if (minup < (*lastminup))
	{
	  /*	see if we really can go up all the way 
		temp should by less than our equal to minup
		if it is less, then one of the faces was not
		adjacent to those next to it and the band height
		will be smaller
	  */
	  temp = Test_Adj(temp2,x,north,minup,lastvert,last_seen);
	  if (temp > minup)
	    {
	      printf("There is an error in the test adj\n");
	      exit(0);
	    }
	  minup = temp;
	  band_value = x * minup;
	  if (minup < smallest_so_far)
	    {
	      if (band_value > max)
               	{
		  smallest_so_far = minup;
		  *lastminup = minup;
		  *lastminleft = x;
		  max = band_value;
		}
	      else
		smallest_so_far = minup;
	    }
	  else
	    {
	      band_value = x * smallest_so_far;
	      if (band_value > max)
		{
		  *lastminup = smallest_so_far;
		  *lastminleft = x;
		  max = band_value;
		}
	    }
	}
      else
	{
	  if (x != 1)
	    {
	      temp = Test_Adj(temp2,x,north,smallest_so_far,lastvert,last_seen);
	      if (temp > smallest_so_far)
		{
		  printf("There is an error in the test adj\n");
		  exit(0);
		}
	      smallest_so_far = temp;
	    }
	  band_value = x * smallest_so_far; 
	  if (band_value > max)
	    {
	      *lastminup = smallest_so_far;
	      *lastminleft = x;
	      max = band_value;
	    }
	}
      if ( x != (walk + 1))
	{
	  node = *(temp2->VertandId+left);
	  if (lastvert == node->edge[1])
	    nextvert = node->edge[2];
	  else
	    nextvert = node->edge[1];
	  
	  lastvert = nextvert;
	  
	  if (nextvert == -1)
	    return max;
	  
	  pListHead = PolFaces[nextvert];
	  temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
	  
	  /* if we have visited this face before, then there is an error */
	  if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
	       (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
	      || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
	    {
	      
	      if (lastvert == node->edge[1])
		nextvert = node->edge[2];
	      else
		nextvert = node->edge[1];
	      if (nextvert == -1)
		return max;
	      lastvert = nextvert;
	      /*   Last attempt to get the face ... */
	      pListHead = PolFaces[nextvert];
	      temp2 = (PF_FACES) PeekList(pListHead, LISTHEAD, 0);
	      if (((*(temp2->walked) == -1) && (*(temp2->walked+1) == -1) &&
		   (*(temp2->walked+2) == -1) && (*(temp2->walked+3) == -1))
		  || (temp2->nPolSize !=4) || (temp2->seen == last_seen))
		return max;    /*   The polygon was not saved with the edge, not
				    enough room. We will get the walk when we come
				    to that polygon later.
			       */
	    }
	  else
	    {
	      counter = 0;
	      flag = TRUE;
	      temp2->seen = last_seen;
	      
	      while ((counter < 3) && (flag))
		{
		  
		  if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
			(*(temp2->pPolygon+counter+1) == previous_edge2)) ||
		       ((*(temp2->pPolygon+counter) == previous_edge2) ||
			(*(temp2->pPolygon+counter+1) == previous_edge1)) )
		    counter++;
		  else
		    flag = FALSE;
		}
	    }
	  
	  /* Get the IDs of the next edge */
	  left = counter;
	  north = left+1;
	  if (left ==3)
	    north = 0;	
	  if (counter < 3)
	    {
	      previous_edge1 = *(temp2->pPolygon + counter + 1);
	      previous_edge2 = *(temp2->pPolygon + counter);
	    }
	  else
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon);
	    }
	  
	} 
      
    }
  last_seen++;
  return max;
}

///	Mark_Face:
void CustomStripifier::Mark_Face(	PF_FACES temp2, 		int color1,
																	int color2,     		int color3,
																	FILE *output_file,	BOOL end,
																	int *edge1,					int *edge2,
		      												int *face_id,				int norms,
																	int texture)
{
  static int last_quad[4];
  register int x,y,z=0;
  int saved[2];
  static int output1, output2,last_id;
  BOOL cptexture;
  
  /*   Are we done with the patch? If so return the last edge that
       we will come out on, and that will be the edge that we will
       start to extend upon.
  */
  
  cptexture = texture;
  if (end)
    {
      *edge1 = output1;
      *edge2 = output2;
      *face_id = last_id;
      return;
    }
  
  last_id = *face_id;
  *(temp2->walked) = -1;
  *(temp2->walked+1) = -1;
  *(temp2->walked+2) = -1;
  *(temp2->walked+3) = -1;
  added_quad++;
  temp2->nPolSize = 1;
  
  if (patch == 0)
    {
      /*   At the first quad in the strip -- save it */
      last_quad[0] = *(temp2->pPolygon);
      last_quad[1] = *(temp2->pPolygon+1);
      last_quad[2] = *(temp2->pPolygon+2);
      last_quad[3] = *(temp2->pPolygon+3);
      patch++;
    }
  else
    {
      /*   Now we have a triangle to output, find the edge in common */
      for (x=0; x < 4 ;x++)
	{
	  for (y=0; y< 4; y++)
	    {
	      if (last_quad[x] == *(temp2->pPolygon+y))
		{
		  saved[z++] = last_quad[x];               
		  if (z > 2)
		    {
		      /*    This means that there was a non convex or
			    an overlapping polygon
		      */
		      z--;
		      break;
		    }
		}                             
	    }
	}
      
      if (z != 2)
	{
	  printf("Z is not 2 %d \n",patch);
	  printf("4 %d %d %d %d %d %d %d\n",*(temp2->pPolygon),
		 *(temp2->pPolygon+1),*(temp2->pPolygon+2),*(temp2->pPolygon+3),
		 color1,color2,color3);
	  printf("%d %d %d %d\n",last_quad[0],last_quad[1],
		 last_quad[2],last_quad[3]);
	  exit(1);
	}
      
      if (patch == 1)
	{
	  /*   First one to output, there was no output edge */
	  patch++;
	  x = Adjacent(saved[0],saved[1],last_quad,4);
	  y = Adjacent(saved[1],saved[0],last_quad,4);
	  
	  /*   Data might be mixed and we do not have textures
	       for some of the vertices 
	  */
	  if ((texture) && 
	      (((vt[x]) == 0) ||
	       ((vt[y])==0) ||
	       ((vt[saved[1]])==0)))
	    cptexture = FALSE;
	  
	  if ((!norms) && (!cptexture))
	    {
	      fprintf(output_file,"\nt");
	      if (orient) /* If we want to preserve normal orientation */
		preserve_strip_orientation(output_file,x+1,y+1,saved[1]+1);
	      
	      fprintf(output_file," %d %d %d",x+1,y+1,saved[1]+1);
	      fprintf(output_file," %d",saved[0]+1);
	    }
	  else if ((norms) && (!cptexture))
	    {
	      fprintf(output_file,"\nt");
	      if (orient) /* If we want to preserve normal orientation */
		preserve_strip_orientation_with_normal(output_file,
						       x+1,vn[x] +1,
						       y+1,vn[y] +1,
						       saved[1]+1,vn[saved[1]]+1);
              
	      fprintf(output_file," %d//%d %d//%d %d//%d",
		      x+1,vn[x] +1,
		      y+1,vn[y] +1,
		      saved[1]+1,vn[saved[1]]+1);
	      fprintf(output_file," %d//%d",saved[0]+1,vn[saved[0]]+1);
	    }
	  else if ((cptexture) && (!norms))
	    {
	      fprintf(output_file,"\nt");
	      if (orient) /* If we want to preserve normal orientation */
		preserve_strip_orientation_with_texture(output_file,
							x+1,vt[x] +1,
							y+1,vt[y] +1,
							saved[1]+1,vt[saved[1]]+1);
	      
	      fprintf(output_file," %d/%d %d/%d %d/%d",
		      x+1,vt[x] +1,
		      y+1,vt[y] +1,
		      saved[1]+1,vt[saved[1]]+1);
	      
	      fprintf(output_file," %d//%d",saved[0]+1,vt[saved[0]]+1);
	    }
	  else
	    {
	      fprintf(output_file,"\nt");
	      if (orient) /* If we want to preserve normal orientation */
		preserve_strip_orientation_with_texture_and_normal(output_file,
								   x+1,vt[x]+1,vn[x] +1,
								   y+1,vt[y]+1,vn[y] +1,
								   saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
	      
	      fprintf(output_file," %d/%d/%d %d/%d/%d %d/%d/%d",
		      x+1,vt[x]+1,vn[x] +1,
		      y+1,vt[y]+1,vn[y] +1,
		      saved[1]+1,vt[saved[1]]+1,vn[saved[1]]+1);
	      
	      fprintf(output_file," %d/%d/%d",
		      saved[0]+1,vt[saved[0]]+1,vn[saved[0]]+1);
	    }
	  
	  x = Adjacent(saved[0],saved[1],temp2->pPolygon,4);
	  y = Adjacent(saved[1],saved[0],temp2->pPolygon,4);
	  
	  /*   Data might be mixed and we do not have textures 
	       for some of the vertices 
	  */
	  if ((texture) && ( (vt[x] == 0) || (vt[y]==0)))
	    {
	      if (cptexture)
		fprintf(output_file,"\nq");
	      cptexture = FALSE;
	    }
	  if ((!norms) && (!cptexture))
	    {
	      fprintf(output_file," %d",x+1);
	      fprintf(output_file," %d",y+1);
	    }
	  else if ((norms) && (!cptexture))
	    {
	      fprintf(output_file," %d//%d",x+1,vn[x]+1);
	      fprintf(output_file," %d//%d",y+1,vn[y]+1);
	    }
	  else if ((cptexture) && (!norms))
	    {
	      fprintf(output_file," %d/%d",x+1,vt[x]+1);
	      fprintf(output_file," %d/%d",y+1,vt[y]+1);
	    }
	  else
	    {
	      fprintf(output_file," %d/%d/%d",x+1,vt[x]+1,vn[x]+1);
	      fprintf(output_file," %d/%d/%d",y+1,vt[y]+1,vn[y]+1);
	    }
	  
	  output1 = x;
	  output2 = y;
	}
      
      else 
	{
	  x = Adjacent(output2,output1,temp2->pPolygon,4);
	  y = Adjacent(output1,output2,temp2->pPolygon,4);
	  /*   Data might be mixed and we do not have textures 
	       for some of the vertices */
	  if ((texture) && ( ((vt[x]) == 0) || ((vt[y])==0) ))
	    texture = FALSE;
	  
	  if ((!norms) && (!texture))
	    {
	      fprintf(output_file,"\nq %d",x+1);
	      fprintf(output_file," %d",y+1);
	    }
	  else if ((norms) && (!texture))
	    {
	      fprintf(output_file,"\nq %d//%d",x+1,vn[x]+1);
	      fprintf(output_file," %d//%d" ,y+1,vn[y]+1);
	    }
	  else if ((texture) && (!norms))
	    {
	      fprintf(output_file,"\nq %d/%d",x+1,vt[x]+1);
	      fprintf(output_file," %d/%d",y+1,vt[y]+1);
	    }
	  else
	    {
	      fprintf(output_file,"\nq %d/%d/%d",x+1,vt[x]+1,vn[x]+1);
	      fprintf(output_file," %d/%d/%d",y+1,vt[y]+1,vn[y]+1);
	    }
	  
	  output1 = x;
	  output2 = y;
	}
      
      last_quad[0] = *(temp2->pPolygon);
      last_quad[1] = *(temp2->pPolygon+1);
      last_quad[2] = *(temp2->pPolygon+2);
      last_quad[3] = *(temp2->pPolygon+3);
    }
}

///	Assign_Walk:
void CustomStripifier::Assign_Walk(	int lastvert,		PF_FACES temp2,
																		int front_walk,	int y,
																		int back_walk)
{
  /*      Go back and do the walk again, but this time save the lengths inside
	  the data structure.
	  y was the starting edge number for the front_walk length
	  back_walk is the length of the walk along the opposite edge
  */
  int previous_edge1, previous_edge2;
  register int walk = 0,nextvert,numverts,counter;
  BOOL flag;
  F_EDGES *node;
  ListHead *pListHead;
  static int seen = 0;
  static BOOL first = TRUE;         
  BOOL wrap = FALSE, set = FALSE;              
  
  
  /*     In the "Fast_Reset" resetting will be true */
  if ((resetting) && (first))
    {
      seen = 0;
      first = FALSE;
    }
  
  seen++;
  
  /*     Had a band who could be a cycle  */
  if (front_walk == back_walk)
    wrap = TRUE;
  
  /* Find the edge that we are currently on */
  if (y != 3)
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon + y + 1);
    }
  else
    {
      previous_edge1 = *(temp2->pPolygon +y);
      previous_edge2 = *(temp2->pPolygon);
    }
  
  /* Assign the lengths */
  if (y < 2) 
    {
      *(temp2->walked+y) = front_walk--;
      *(temp2->walked+y+2) = back_walk++;
    }
  else
    {				
      *(temp2->walked+y) = front_walk--;
      *(temp2->walked+y-2) = back_walk++;
    }
  
  /*Find the adjacent face to this edge */
  node = *(temp2->VertandId+y);                   
  
  if (node->edge[2] != lastvert)
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  
  temp2->seen3 = seen;
  
  /* Keep walking in this direction until we cannot do so */
  while ((nextvert != lastvert) && (nextvert != -1) && (front_walk >= 0))
    {
      walk++;
      pListHead = PolFaces[nextvert];
      
      temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      numverts = temp2->nPolSize;
      if ((numverts != 4))
	{
	  nextvert = -1;
	  /* Don't include this face in the walk */
	  walk--;
	}
      else
	{
	  /* Find edge that is not adjacent to the previous one */
	  counter = 0;
	  flag = TRUE;
	  while ((counter < 3) && (flag))
	    {
	      if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
		    (*(temp2->pPolygon+counter+1) == previous_edge2)) ||
		   ((*(temp2->pPolygon+counter) == previous_edge2) ||
		    (*(temp2->pPolygon+counter+1) == previous_edge1)) )
		counter++;
	      else
		flag = FALSE;
	    }
	  /* Get the IDs of the next edge */
	  if (counter < 3)
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon + counter + 1);
	    }
	  else
	    {
	      previous_edge1 = *(temp2->pPolygon + counter);
	      previous_edge2 = *(temp2->pPolygon);
	    }
	  
	  
	  /*      Put in the walk lengths */
	  if (counter < 2)
	    {
	      if (((*(temp2->walked + counter) >= 0)
		   || (*(temp2->walked +counter + 2) >= 0)))
		{
		  if ((resetting == FALSE) && ((temp2->seen3) != (seen-1)))
		    {
		      /*   If there are more than 2 polygons adjacent
			   to an edge then we can be trying to assign more than
			   once. We will save the smaller one
		      */
		      temp2->seen3 = seen;
		      if ( (*(temp2->walked+counter) <= front_walk) &&
			   (*(temp2->walked+counter+2) <= back_walk) )
			return;
		      if (*(temp2->walked+counter) > front_walk)
			*(temp2->walked+counter) = front_walk--;
		      else
			front_walk--;
		      if (*(temp2->walked+counter+2) > back_walk)
			*(temp2->walked+counter+2) = back_walk++;
		      else
			back_walk++;
		    }
		  else if (resetting == FALSE)
		    {
		      /* if there was a cycle then all lengths are the same */
		      walk--;
		      back_walk--;
		      front_walk++;
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter+2) = back_walk++;
		    }
		  else if (((temp2->seen3 == (seen-1))
			    && (wrap) && (walk == 1)) || (set))
		    {
		      /* if there was a cycle then all lengths are the same */
		      set = TRUE;
		      walk--;
		      back_walk--;
		      front_walk++;
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter+2) = back_walk++;
		    }
		  else
		    {
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter+2) = back_walk++;
		    }
		} /* if was > 0 */	
	      else
		{
		  temp2->seen3 = seen;
		  *(temp2->walked+counter) = front_walk--;
		  *(temp2->walked+counter+2) = back_walk++;
		}
	    }
	  
	  else
	    {
	      if (((*(temp2->walked + counter) >= 0 )
		   || (*(temp2->walked +counter - 2) >= 0)) )
		{
		  if ((temp2->seen3 != (seen-1))  && (resetting == FALSE))
		    {
		      /*   If there are more than 2 polygons adjacent
			   to an edge then we can be trying to assign more than
			   once. We will save the smaller one
		      */
		      temp2->seen3 = seen;
		      if ( (*(temp2->walked+counter) <= front_walk) &&
			   (*(temp2->walked+counter-2) <= back_walk) )
			return;
		      if (*(temp2->walked+counter) > front_walk)
			*(temp2->walked+counter) = front_walk--;
		      else
			front_walk--;
		      if (*(temp2->walked+counter-2) > back_walk)
			*(temp2->walked+counter-2) = back_walk++;
		      else
			back_walk++;
		    }
		  else if (resetting == FALSE)
		    {
		      walk--;
		      back_walk--;
		      front_walk++;
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter-2) = back_walk++;
		    }
		  else if (((temp2->seen3 == (seen-1)) && (walk == 1) && (wrap))
			   || (set))
		    {
		      /* if there was a cycle then all lengths are the same */
		      set = TRUE;
		      walk--;
		      back_walk--;
		      front_walk++;
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter-2) = back_walk++;
		    }
		  else
		    {
		      temp2->seen3 = seen;
		      *(temp2->walked+counter) = front_walk--;
		      *(temp2->walked+counter-2) = back_walk++;
		    }
		}
	      else
		{
		  temp2->seen3 = seen;
		  *(temp2->walked+counter) = front_walk--;
		  *(temp2->walked+counter-2) = back_walk++;
		}
	      
	    } 
	  if (nextvert != -1)
	    {
	      node = *(temp2->VertandId + counter);
	      if (node->edge[1] == nextvert)
		nextvert = node->edge[2];
	      else
		nextvert = node->edge[1];
	    }
	  
	}
    }
  if ((EVEN(seen)) )
    seen+=2;
}

///	Fast_Reset:
void CustomStripifier::Fast_Reset(int x)
{
  register int y,numverts;
  register int front_walk, back_walk;
  ListHead *pListHead;
  PF_FACES temp = NULL;
  
  pListHead = PolFaces[x];
  temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
  numverts = temp->nPolSize;
  
  front_walk = 0; 
  back_walk = 0;          
  resetting = TRUE;
  
  /* we are doing this only for quads */
  if (numverts == 4)
    {
      /* 	for each face not seen yet, do North and South together
		and East and West together
      */
      for (y=0;y<2;y++)
	{
	  /* Check if the opposite sides were seen already */
	  /* Find walk for the first edge */
	  front_walk = Calculate_Walks(x,y,temp);
	  /* Find walk in the opposite direction */
	  back_walk = Calculate_Walks(x,y+2,temp);
	  /* 	Now put into the data structure the numbers that
		we have found
	  */
	  Assign_Walk(x,temp,front_walk,y,back_walk);
	  Assign_Walk(x,temp,back_walk,y+2,front_walk);
	}
    }
  resetting = FALSE;
}

///	Reset_Max:
void CustomStripifier::Reset_Max(	PF_FACES temp2,int face_id,
																	int north,int last_north,
		      												int orientation,int last_left,
																	FILE *output_file,int color1,
																	int color2,int color3,
		      												BOOL start)
{
  int previous_edge1,previous_edge2;
  F_EDGES *node;
  ListHead *pListHead;
  int f,t,nextvert,counter;
  BOOL flag;
  
  
  /*   Reset walks on faces, since we just found a patch */
  if (orientation !=3)
    {
      previous_edge1 = *(temp2->pPolygon + orientation+1);
      previous_edge2 = *(temp2->pPolygon + orientation );
    }
  else
    {
      previous_edge1 = *(temp2->pPolygon + orientation );
      previous_edge2 = *(temp2->pPolygon);
    }
  
  /* only if we are going left, otherwise there will be -1 there */
  /*Find the adjacent face to this edge */
  
  for (t = 0; t <=3 ; t++)
    {
      node = *(temp2->VertandId+t);
      
      if (face_id == node->edge[1])
	f = node->edge[2];
      else
	f = node->edge[1];
      
      if (f != -1)
	Fast_Reset(f);
    }
  
  node = *(temp2->VertandId+orientation);
  if (face_id == node->edge[1])
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  
  while ((last_left--) > 1)
    {
      
      if (start)
	Reset_Max(temp2,face_id,orientation,last_left,north,last_north,
		  output_file,color1,color2,color3,FALSE);		
      
      face_id = nextvert;
      pListHead = PolFaces[nextvert];                
      temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      if ((temp2->nPolSize != 4) && (temp2->nPolSize != 1))
	{
	  /*   There is more than 2 polygons on the edge, and we could have
	       gotten the wrong one
	  */
	  if (nextvert != node->edge[1])
	    nextvert = node->edge[1];
	  else
	    nextvert = node->edge[2];
	  pListHead = PolFaces[nextvert];          
	  temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
	  node = *(temp2->VertandId+orientation);
	}
      
      
      if (!start)
	{
	  for (t = 0; t <=3 ; t++)
	    {
	      node = *(temp2->VertandId+t);
              
	      if (face_id == node->edge[1])
		f = node->edge[2];
	      else
		f = node->edge[1];
	      
	      if (f != -1)
		Fast_Reset(f);
	    }
        }
      
      
      counter = 0;
      flag = TRUE;
      while ((counter < 3) && (flag))
        {
	  if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
		(*(temp2->pPolygon+counter+1) == previous_edge2)) ||
	       ((*(temp2->pPolygon+counter) == previous_edge2) ||
		(*(temp2->pPolygon+counter+1) == previous_edge1)) )
	    counter++;
	  else
	    flag = FALSE;
        }
      
      /* Get the IDs of the next edge */
      if (counter < 3)
        {
	  previous_edge1 = *(temp2->pPolygon + counter+1);
	  previous_edge2 = *(temp2->pPolygon + counter);
        }
      else
        {
	  previous_edge1 = *(temp2->pPolygon + counter);
	  previous_edge2 = *(temp2->pPolygon);
        }
      orientation = counter;
      
      node = *(temp2->VertandId + counter);
      if (node->edge[1] == nextvert)
	nextvert = node->edge[2];
      else
	nextvert = node->edge[1];
      
      if (!reversed)
        {
	  if (counter != 3)
	    north = counter +1;
	  else
	    north = 0;
        }
      else
        {
	  if (counter != 0)
	    north = counter -1;
	  else
	    north = 3;
	  
        }
    }
  if (start)
    Reset_Max(temp2,face_id,orientation,last_left,north,last_north,output_file,
	      color1,color2,color3,FALSE);
  else if (nextvert != -1)       
    Fast_Reset(nextvert);
  
}

///	Peel_Max
int CustomStripifier::Peel_Max(	PF_FACES temp2,int face_id,
																int north,int last_north,
																int orientation,int last_left,
																FILE *output_file,int color1,
																int color2,int color3,
		    												BOOL start, int *swaps_added,
																int norms, int texture)
{
  int end1,end2,last_id,s=0,walk = 0;
  int previous_edge1,previous_edge2;
  int static last_seen = 1000;
  F_EDGES *node;
  ListHead *pListHead;
  int nextvert,numverts,counter,dummy,tris=0;
  BOOL flag;
  
  /* Peel the patch from the model.
     We will try and extend off the end of each strip in the patch. We will return
     the number of triangles completed by this extension only, and the number of
     swaps in the extension only.
  */	
  patch = 0;
  
  if (orientation !=3)
    {
      previous_edge1 = *(temp2->pPolygon + orientation+1);
      previous_edge2 = *(temp2->pPolygon + orientation );
    }
  else
    {
      previous_edge1 = *(temp2->pPolygon + orientation );
      previous_edge2 = *(temp2->pPolygon);
    }
  
  
  walk = *(temp2->walked + orientation);
  
  /* only if we are going left, otherwise there will be -1 there */
  if ((start) && ((walk+1) < last_left))
    {
      printf("There is an error in the left %d %d\n",walk,last_left);
      exit(0);
    }
  
  /* Find the adjacent face to this edge */
  node = *(temp2->VertandId+orientation);
  if (face_id == node->edge[1])
    nextvert = node->edge[2];
  else
    nextvert = node->edge[1];
  temp2->seen = last_seen;
  
  
  while ((last_left--) > 1)
    {
      if (start)
	tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,
			 output_file,color1,color2,color3,FALSE,swaps_added,
			 norms,texture);		    
      else
	Mark_Face(temp2,color1,color2,color3,output_file,FALSE,
		  &dummy,&dummy,&face_id,norms,texture);
      
      
      pListHead = PolFaces[nextvert];      
      temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      numverts = temp2->nPolSize;
      
      if ((numverts != 4) || (temp2->seen == last_seen) 
	  ||  (nextvert == -1))
	{
	  
	  /*   There is more than 2 polygons on the edge, and we could have
	       gotten the wrong one
	  */
	  if (nextvert != node->edge[1])
	    nextvert = node->edge[1];
	  else
	    nextvert = node->edge[2];
	  pListHead = PolFaces[nextvert];
	  temp2 = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
	  numverts = temp2->nPolSize;
	  if ((numverts != 4) || (temp2->seen == last_seen) )
	    {
	      printf("Peel 2 %d\n",numverts);
	      exit(1);
	    }
        }
      
      face_id = nextvert;
      temp2->seen = last_seen;
      
      counter = 0;
      flag = TRUE;
      while ((counter < 3) && (flag))
        {
	  if ( ((*(temp2->pPolygon+counter) == previous_edge1) ||
		(*(temp2->pPolygon+counter+1) == previous_edge2)) ||
	       ((*(temp2->pPolygon+counter) == previous_edge2) ||
		(*(temp2->pPolygon+counter+1) == previous_edge1)) )
	    counter++;
	  else
	    flag = FALSE;
        }
      /* Get the IDs of the next edge */
      if (counter < 3)
        {
	  previous_edge1 = *(temp2->pPolygon + counter+1);
	  previous_edge2 = *(temp2->pPolygon + counter);
        }
      else
        {
	  previous_edge1 = *(temp2->pPolygon + counter);
	  previous_edge2 = *(temp2->pPolygon);
        }
      orientation = counter;
      
      node = *(temp2->VertandId + counter);
      if (node->edge[1] == nextvert)
	nextvert = node->edge[2];
      else
	nextvert = node->edge[1];
      
      if (!reversed)
        {
	  if (counter != 3)
	    north = counter +1;
	  else
	    north = 0;
        }
      else
        {
	  if (counter != 0)
	    north = counter -1;
	  else
	    north = 3;
        }
    }
  
  if (start)
    tris += Peel_Max(temp2,face_id,orientation,last_left,north,last_north,
		     output_file,color1,color2,color3,FALSE,swaps_added,
		     norms,texture);	
  else
    Mark_Face(temp2,color1,color2,color3,output_file,FALSE,
	      &dummy,&dummy,&face_id,norms,texture);/* do the last face */
  
  last_seen++;
  
  /*    Get the edge that we came out on the last strip of the patch */
  Mark_Face(NULL,0,0,0,output_file,TRUE,&end1,&end2,&last_id,norms,texture);
  tris += Extend_Face(last_id,end1,end2,&s,output_file,color1,color2,color3,
		      vn,norms,vt,texture);
  *swaps_added = *swaps_added + s;
  return tris;
}

///	Find_Bands:
void CustomStripifier::Find_Bands(int numfaces,	FILE *output_file,
																	int *swaps,		int *bands,
                									int *cost,		int *tri,
																	int norms,		int *vert_norms,
																	int texture,	int *vert_texture)
{
  
  register int x,y,max1,max2,numverts,face_id,flag,maximum = 25;
  ListHead *pListHead;
  PF_FACES temp = NULL;
  int color1 = 0, color2 = 100, color3 = 255;
  int smaller;                        
  int north_length1,last_north,left_length1,last_left,north_length2,left_length2;
  int total_tri = 0, total_swaps = 0,last_id;
  int end1, end2,s=0;
  register int cutoff = 20;
  
  /*   Code that will find the patches. "Cutoff" will be
       the cutoff of the area of the patches that we will be allowing. After
       we reach this cutoff length, then we will run the local algorithm on the
       remaining faces.
  */
  
  /* 	For each faces that is left find the largest possible band that we can
	have with the remaining faces. Note that we will only be finding patches
	consisting of quads.
  */
  
  vn = vert_norms;
  vt = vert_texture;
  y=1;
  *bands = 0;
  
  while ((maximum >= cutoff))
    {
      y++;
      maximum = -1;
      for (x=0; x<numfaces; x++)
	{ 
	  
          /*   Used to produce the triangle strips */
	  
          /* for each face, get the face */
	  pListHead = PolFaces[x];
	  temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
	  numverts = temp->nPolSize;
	  
          /* we are doing this only for quads */
	  if (numverts == 4)
	    {
	      /*   We want a face that is has not been used yet,
		   since we know that that face must be part of
		   a band. Then we will find the largest band that
		   the face may be contained in
	      */
	      
	      /*  Doing the north and the left */
	      if ((*(temp->walked) != -1) && (*(temp->walked+3) != -1))
		max1 = Find_Max(temp,x,0,3,&north_length1,&left_length1);
	      if ((*(temp->walked+1) != -1) && (*(temp->walked+2) != -1))
		max2 = Find_Max(temp,x,2,1,&north_length2,&left_length2);
	      if ((max1 != (north_length1 * left_length1)) ||
		  (max2 != (north_length2 * left_length2)))
		{
		  printf("Max1 %d, %d %d	Max2 %d, %d %d\n",
			 max1,north_length1,left_length1,max2,
			 north_length2,left_length2);
		  exit(0);
		}
	      
	      
	      if ((max1 > max2) && (max1 > maximum))
		{
		  maximum = max1;
		  face_id = x;
		  flag = 1; 
		  last_north = north_length1;
		  last_left = left_length1;
		  /* so we know we saved max1 */
		}
	      else if ((max2 > maximum) )
		{
		  maximum = max2;
		  face_id = x;
		  flag = 2; 
		  last_north = north_length2;
		  last_left = left_length2;
		  /* so we know we saved max2 */
		}
	    }
	}
      if ((maximum < cutoff) && (*bands == 0))
	return;
      pListHead = PolFaces[face_id];
      temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);	
      /*   There are no patches that we found in this pass */
      if (maximum == -1)
	break;
      /*printf("The maximum is  face %d area %d: lengths %d %d\n",face_id,maximum,last_north,last_left);*/
      
      if (last_north > last_left)
	{
          smaller = last_left;
	}
      else
	{
          smaller = last_north;
	}
      
      
      if (flag == 1)
	{
	  if (last_north > last_left) /*     go north sequentially */
	    {
	      total_tri += Peel_Max(temp,face_id,0,last_north,3,last_left,
				    output_file,color1,color2,color3,TRUE,
				    &s,norms,texture);
	      Reset_Max(temp,face_id,0,last_north,3,last_left,
			output_file,color1,color2,color3,TRUE);
	      total_swaps += s;
	    }
	  else
	    {
	      reversed = TRUE;
	      total_tri += Peel_Max(temp,face_id,3,last_left,0,last_north,
				    output_file,color1,color2,color3,TRUE,
				    &s,norms,texture);
	      Reset_Max(temp,face_id,3,last_left,0,last_north,output_file,
			color1,color2,color3,TRUE);
	      reversed = FALSE;
	      total_swaps += s;
	    }
	  
	  
	  /*    Get the edge that we came out on the last strip of the patch */
	  Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
	  total_tri += Extend_Face(last_id,end1,end2,&s,output_file,
				   color1,color2,color3,vn,norms,vt,texture);
	  total_swaps += s;
	  
	}
      else
	{
	  if (last_north > last_left)
	    {
	      total_tri += Peel_Max(temp,face_id,2,last_north,1,last_left,
				    output_file,color1,color2,color3,TRUE,
				    &s,norms,texture); 
	      Reset_Max(temp,face_id,2,last_north,1,last_left,output_file,
			color1,color2,color3,TRUE); 
	      total_swaps += s;
	    }
	  else
	    {
	      reversed = TRUE;
	      total_tri += Peel_Max(temp,face_id,1,last_left,2,last_north,
				    output_file,color1,color2,color3,TRUE,
				    &s,norms,texture);
	      Reset_Max(temp,face_id,1,last_left,2,last_north,output_file,
			color1,color2,color3,TRUE);
	      reversed = FALSE;
	      total_swaps += s;
	    }
	  
	  /*    Get the edge that we came out on on the patch */
	  Mark_Face(NULL,0,0,0,NULL,TRUE,&end1,&end2,&last_id,norms,texture);
	  total_tri += Extend_Face(last_id,end1,end2,&s,output_file,
				   color1,color2,color3,vn,norms,vt,texture);
	  total_swaps += s;
	}
      
      /*  Now compute the cost of transmitting this band, is equal to 
	  going across the larger portion sequentially,
	  and swapping 3 times per other dimension
      */
      
      total_tri += (maximum * 2);
      *bands = *bands + smaller;
      
    }
  
  /*printf("We transmitted %d triangles,using %d swaps and %d strips\n",total_tri,
    total_swaps, *bands);
    printf("COST %d\n",total_tri + total_swaps + *bands + *bands);*/
  *cost = total_tri + total_swaps + *bands + *bands;
  *tri = total_tri;
  added_quad = added_quad * 4;
  *swaps = total_swaps;
}

///	Save_Rest:
void CustomStripifier::Save_Rest(int *numfaces)
{
  /*  Put the polygons that are left into a data structure so that we can run the
      stripping code on it.
  */
  register int x,y=0,numverts;
  ListHead *pListHead;
  PF_FACES temp=NULL;
  
  for (x=0; x<*numfaces; x++)
    { 
      /* for each face, get the face */
      pListHead = PolFaces[x];
      temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      numverts = temp->nPolSize;
      /*  If we did not do the face before add it to data structure with new 
	  face id number
      */
      if (numverts != 1)
	{
	  CopyFace(temp->pPolygon,numverts,y+1,temp->pNorms);
	  y++;
	}
      /*   Used it, so remove it */
      else
	RemoveList(pListHead,(PLISTINFO) temp);
      
    }
  *numfaces = y;
}

///	Save_Walks:
void CustomStripifier::Save_Walks(int numfaces)
{
  int x,y,numverts;
  int front_walk, back_walk;
  ListHead *pListHead;
  PF_FACES temp = NULL;
  
  for (x=0; x<numfaces; x++)
    { 
      /* for each face, get the face */
      pListHead = PolFaces[x];
      temp = (PF_FACES) PeekList(pListHead,LISTHEAD,0);
      numverts = temp->nPolSize;
      front_walk = 0; 
      back_walk = 0;
      
      /* we are finding patches only for quads */
      if (numverts == 4)
	{
	  /* 	for each face not seen yet, do North and South together
		and East and West together
	  */
	  for (y=0;y<2;y++)
	    {
	      /*   Check if the opposite sides were seen already from another
		   starting face, if they were then there is no need to do 
		   the walk again
	      */
	      
	      if 	( ((*(temp->walked+y) == -1) &&
			   (*(temp->walked+y+2) == -1) ))
		{
		  /* Find walk for the first edge */
		  front_walk = Calculate_Walks(x,y,temp);
		  /* Find walk in the opposite direction */
		  back_walk = Calculate_Walks(x,y+2,temp);
		  /* 	Now put into the data structure the numbers that
			we have found
		  */
		  Assign_Walk(x,temp,front_walk,y,back_walk);
		  Assign_Walk(x,temp,back_walk,y+2,front_walk);
		}
	    }
	}
    }
}

///	OpenOutputFile:
FILE *	CustomStripifier::OpenOutputFile(char *fname)
{
  FILE	*bands;
  int		flength	=	0;
  char	*newfname;
  
  // get the length of the fname.
  flength	=	int(strlen(fname));

  // make a new string in memory one larger than fname.
  newfname	=	(char *) malloc(sizeof(char) * (flength+2));

  // Copy the fname to the newfname.
  strcpy(newfname,fname);

  // Add an 'f' to the end of it.
  newfname[flength]		=	'f';
  newfname[flength+1]	=	'\0';
  
  printf("   Output file : %s\n",newfname); 
  
  // File that will contain the triangle strip data
  bands	=	fopen(newfname,"w");
  fprintf(bands,"#%s: a triangle strip representation created by STRIPE.\n#This is a .objf file\n#by Francine Evans\n",fname);
  
  return	bands;
}

///	AllocateStruct:	Reserves memory for structures.
void CustomStripifier::AllocateStruct(int num_faces,
										int num_vert,
										int num_nvert,
										int num_texture)
{
  /* Allocate structures for the information */
  Start_Face_Struct(num_faces);
  Start_Vertex_Struct(num_vert);
  
  vertices	=	(struct vert_struct *)
							malloc (sizeof (struct vert_struct) * num_vert);
  
  if (num_nvert > 0)
  {
		nvertices		=	(struct vert_struct *)
									malloc (sizeof (struct vert_struct) * num_nvert);

		vert_norms	=	(int *) 
									malloc (sizeof (int) * num_vert);

		/*	Initialize entries to zero, in case there are 2 hits
				to the same vertex we will know it - used for determining
				the normal difference
		*/
		init_vert_norms(num_vert);
  }
  else
    nvertices = NULL;
  
  if (num_texture > 0)
	{
		vert_texture	=	(int *) malloc (sizeof(int) * num_vert);

		init_vert_texture(num_vert);
	}
  
  /*   Set up the temporary 'p' pointers  */
  pvertices		=	vertices;
  pnvertices	=	nvertices;
  
}

///	miReadFile: Loads the object in memory.
void CustomStripifier::miReadFile(char *fname, char *file_open, FILE *bands, Geometry::SubMesh *geoSubMesh)
{
  int		face_id	=	0;
  int		vert_count;
	int		num_vert=0;
  int		vertex;
  int		temp[MAX1];
	int		i	=	0;
	int		num_buffers	=	0;
  Geometry::VertexBuffer	*geoVertexBuffer	=	geoSubMesh->mVertexBuffer;
	
	/**
	 * Faces
	 */
	for(unsigned int j = 0; j < geoSubMesh->mIndexCount; j = j + 3)
	{
		
		// loop on the number of vertices in this line of face data.
		vert_count = 0;
		
		//	3 vertices of a triangle.
		for(int k = 0;k < 3;k++)
		{
			// no nvertices.
			vertex						=	geoSubMesh->mIndex[j+k];
			temp[vert_count]	=	vertex;

			vert_count++;

			add_vert_id(vertex,vert_count);
		}

		//	Increment the number of faces.
		face_id++;

		//	Add a new face to the list.
		AddNewFace(ids,vert_count,face_id,norms);

	}

  // Done reading in all the information into data structures.
  num_faces	=	face_id;

  printf(" Done.\n\n");

  free(vertices);
  free(nvertices);

}

///	stripify:	Make triangle strips for a given mesh.
int CustomStripifier::stripify (char								*fname,
																Geometry::Mesh			*geoMesh)
{
  BOOL								quads = FALSE;
	BOOL								oddStrip;
	FILE								*bands;
	char								*file_open;
	int									i;
	unsigned int						j;
	int									f;
	int									t;
	int									tr;
	int									num_buffers	=	0;
	int									cost				=	0;
  int									num_vert		=	0;
	int									num_faces		=	0;
	int									num_nvert   = 0;
	int									num_texture	= 0;
	int									num_tris    = 0;
	int									totalStripIndices;

	Geometry::SubMesh*	geoSubMesh;
  mi_vector_tipo			v_indices;
    
  /*  Scan the file once to find out the number of vertices,
			vertice normals, and faces so we can set up some memory structures.*/
  f					=	ASCII;
  file_open =	"w+";
  tr				=	1;
  t					=	3;
  orient		=	1;

	//	Proces OK.
	mError			=	0;


	//	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)
		{
			v_indices.clear();
			mi_vector.clear();
			mi_vector.push_back(v_indices);
			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;

			//	Debug.
			//vt	=	new	int[num_vert];
			//vn	=	new int[num_vert];
			text	=	0;
			norm	=	0;

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			// Open the output file.
			bands	=	OpenOutputFile(fname);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			//	Reserve memory for the mesh structure.
			AllocateStruct(num_faces,num_vert,num_nvert,num_texture);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			//	Load the object into memory.
			miReadFile(fname,file_open,bands,geoSubMesh);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			Start_Edge_Struct(num_vert);
			Find_Adjacencies(num_faces);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

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

			// Initialize it.
			face_array = NULL;
			Init_Table_SGI(num_faces);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			//	Build it.
			Build_SGI_Table(num_faces);
			InitStripTable();

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			SGI_Strip(num_faces,bands,t,tr);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			//	Get the total cost.
			Output_TriEx(-1,-2,-3,NULL,-20,cost);

			End_Face_Struct(num_faces);
			End_Edge_Struct(num_vert);
			fclose(bands);

			//	2006-02-14.
			//	Updtate progress bar.
			if (mUPB)
			{
				mUPB(percent);
			}
			//-----------------------

			num_vert	=	num_tiras;

			totalStripIndices	=	0;


			//	Asigna el numero de tiras.
			geoSubMesh->mStripCount	=	num_tiras;

			//	Reserva memoria para el array de punteros al inicio
			//	de las tiras.
			//for(i = 0; i < geoSubMesh->mStripCount; i++)
			//{
			geoSubMesh->mStrip	=	(Index**) malloc(	sizeof(Index*)
					*
					geoSubMesh->mStripCount);
			//}

			//	2006-02-28.
			//	La primera sera diferente.
			v_indices	=	mi_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								=		mi_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];
			//--------------------------------------------

			//	La primera sera diferente.
			v_indices	=	mi_vector[1];

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



			//	Copia la primera tira en el array de indices.
			for(j	=	0;j < v_indices.size();j++)
			{
				geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[j];
			}

			//	Asigna el inicio de la primera tira de triangulos.
			geoSubMesh->mStrip[0]	=	&geoSubMesh->mIndex[0];

			//	2006-02-14.
			//	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;
			}
			*/

			//	Para todas las tiras menos la primera.
			for(i	=	2;	i <= num_tiras;	i++)
			{
				
				/*	copia en el inicio de la tira el final de la anterior.
						triangulos degenerados.	*/
				/*
				geoSubMesh->mIndex[totalStripIndices++]	=	geoSubMesh->
					mIndex[totalStripIndices-1];
				*/

				v_indices								=	mi_vector[i];

				//geoSubMesh->mIndexCount	=	geoSubMesh->mIndexCount	+	v_indices.size() + 2;

				/*	copia el inicio de la tira 2 veces.
						triangulos degenerados.
						*/
				
				geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[0];

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

				//	Triangulo Degenerado.
				//geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[0];

				/*
				//	Insert a new vertex if the strip es odd.
				if(oddStrip)
				{
					//	geoSubMesh->mIndexCount++;
					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;
				}
				*/
				
				//	Copia la tira en curso en el array de indices.
				for(j=1;j<v_indices.size();j++)
				{
					geoSubMesh->mIndex[totalStripIndices++]	=	v_indices[j];
				}
			}
		}
	}//	End For. SubMeshes.

	//	2006-02-14.
	//	Updtate progress bar.
	if (mUPB)
	{
		mUPB(100.0);
	}
	//-----------------------

	return	1;
}

//-----------------------------------------------------------------------------
//	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()
{	
	delete	MeshGlobal;
}

MeshStripifier::~MeshStripifier()
{
}

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

///	Stripify:
int CustomStripifier::Stripify()
{
	//	Init variables.
	resetting		=	FALSE;
	added_quad	=	0;
	reversed		=	FALSE;
	patch				=	0;
	out1				=	-1;
	out2				=	-1;
	out1Ex			=	-1;
	out2Ex			=	-1;
	last				=	0;

	//	Make Triangle Strips.
	return	stripify("out.obj",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;
}