source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/GeoMeshStripifier.cpp @ 986

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