---

sglTriStripper.hpp

/*****************************************************************************
 * SGL: A Scene Graph Library
 *
 * Copyright (C) 1997-2001  Scott McMillan   All Rights Reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *****************************************************************************
 *     File: sglTriStripper.hpp 
 *  Created: 23 June 1997 (tea time - tee time) 
 *  Summary: class containing all of the data for one geoset (a geometry set
 *           with vertices, normals, and texcoords and indices). 
 *****************************************************************************/

#ifndef __SGL_TRI_STRIPPER_HPP
#define __SGL_TRI_STRIPPER_HPP

#include <sgldb.h>
#include <vector>

#include <sglTriStruct.hpp>
#include <sglHashTable.hpp>
#include <sglVector.hpp>
#include <sglOStream.hpp>

//============================================================================
template <class T>
class SGLDB_DLL_API sglTriStripper
{
public:
   sglTriStripper();
   virtual ~sglTriStripper();

   unsigned int getNumTriangles() const {return m_num_triangles;}

   void addTriangleFace(sglTriStruct<T> *tri);

   void addPolyFace(const vector<T>& vertList);

   static void computeFaceNormal(const sglVec3f &v0,
                                 const sglVec3f &v1,
                                 const sglVec3f &v2,
                                 sglVec3f& normal);

   void computeSmoothNormals(const sglVec3f* verts,
                             unsigned int (*addNormal)(void*,sglVec3f&),
                             void* passThrough);

   void computeFacetedNormals(const sglVec3f* verts,
                              unsigned int (*addNormal)(void*,sglVec3f&),
                              void* passThrough);

   void triStripify( bool verbose = true );

   void reset();

   void copyTriangleIndexLists(unsigned int *index_vlist,
                               unsigned int *index_nlist,
                               unsigned int *index_tlist,
                               unsigned int *index_clist);

   unsigned int getNumStrips() const {return m_strip.size();}

   vector<T> *getStrip(unsigned int index);

    void copyStrip(unsigned int index,
                   unsigned int *index_vlist,
                   unsigned int *index_nlist,
                   unsigned int *index_tlist,
                   unsigned int *index_clist);

private:
   sglTriStripper(const sglTriStripper &);
   // assignment operator forbidden
   sglTriStripper &operator=(const sglTriStripper &);

   void createStrip(sglTriList<T> *trilist);

   typedef typename sglTriList<T>::iterator list_iterator;

   void removeadjacencies(list_iterator tri);

   void allocLists();
   void freeLists();

private:
   unsigned int m_num_triangles;
   sglTriList<T> *m_trilist;
   sglTriList<T> *m_donetrilist;
   sglTriList<T> *m_adjtrilist[4];


   vector<vector<T>*> m_strip;
   unsigned int m_strip_len;
   unsigned int m_num_swaps;
};

//struct edgeStruct;

template <class T>
class sglEdgeStruct
{
public:
   int hash(unsigned int hashsize)
      {
         int val = (*tri)->v[adjnumber].edgeHash() * 
             (*tri)->v[(adjnumber+1)%3].edgeHash();
         val = val & 0x7fffffff;
         return val % hashsize;
      }


   bool isEqual(sglEdgeStruct *edge2)
      {
         return ((*tri)->v[adjnumber] == 
                 (*(edge2->tri))->v[(edge2->adjnumber+1)%3])
             && ((*tri)->v[(adjnumber+1)%3] == 
                 (*(edge2->tri))->v[edge2->adjnumber]);
      }


   typedef typename sglTriList<T>::iterator list_iterator;

   list_iterator tri;
   unsigned int adjnumber;
};



//============================================================================
// class sglTriStripper
//============================================================================

//----------------------------------------------------------------------------
template <class T>
inline sglTriStripper<T>::sglTriStripper() :
      m_num_triangles(0),
      m_strip(),
      m_strip_len(0),
      m_num_swaps(0)
{
   allocLists();
}

//----------------------------------------------------------------------------
template <class T>
inline sglTriStripper<T>::~sglTriStripper()
{
   freeLists();
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::reset()
{
   freeLists();
   m_num_triangles = 0;
   m_strip_len = 0;
   m_num_swaps = 0;
   allocLists();
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::allocLists()
{
   m_trilist = new sglTriList<T>();
   m_donetrilist = new sglTriList<T>();
   for (int i=0; i<4; i++)
      m_adjtrilist[i] = new sglTriList<T>();
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::freeLists()
{
   if (m_donetrilist)
   {
      if (!m_donetrilist->empty())
         sglPrintWarning()
            << "sglTriStripper logic error: m_donetrilist not empty" << endl;
      delete m_donetrilist;
   }
   if (m_adjtrilist[0])
   {
       if (!m_adjtrilist[0]->empty())
          sglPrintWarning()
             << "sglTriStripper logic error: m_adjtrilist[0] not empty"
             << endl;
       delete m_adjtrilist[0];
   }
   if (m_adjtrilist[1])
   {
       if (!m_adjtrilist[1]->empty())
          sglPrintWarning()
             << "sglTriStripper logic error: m_adjtrilist[1] not empty"
             << endl;
       delete m_adjtrilist[1];
   }
   if (m_adjtrilist[2])
   {
      if (!m_adjtrilist[2]->empty())
         sglPrintWarning()
            << "sglTriStripper logic error: m_adjtrilist[2] not empty"
            << endl;
      delete m_adjtrilist[2];
   }
   if(m_adjtrilist[3])
   {
      if (!m_adjtrilist[3]->empty())
         sglPrintWarning()
            << "sglTriStripper logic error: m_adjtrilist[3] not empty "
            << endl;
      delete m_adjtrilist[3];
   }
   if (m_trilist)
   {
       while (!m_trilist->empty())
       {
           list_iterator tri = m_trilist->begin();
           delete *tri;
           m_trilist->erase(tri);
       }
      delete m_trilist;
   }

   while (!m_strip.empty())
   {
      vector<T>* strip = m_strip.back();
      m_strip.pop_back();
      delete strip;
   }
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::addTriangleFace(sglTriStruct<T> *tri)
{
   // Do not add degenerate triangles
   if (tri->isDegenerate())
   {
      sglPrintInfo() << "sglTriStripper::addTriangleFace() warning: "
                     << "ignoring degenerate triangle" << endl;

      delete tri;
      return;
   }

   // insert at the head of the list
   m_trilist->push_back(tri);

   tri->used = false;
   tri->adjcount = 0;
   for (int i=0; i<3; i++) tri->adj[i] = NULL;
   tri->index = m_num_triangles++;

   sglPrintDebug() << *tri;
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::addPolyFace(const vector<T>& vertList)
{
   if (vertList.size() > 2)
   {
      unsigned int first = 0;
      unsigned int middle = 1;
      unsigned int last = vertList.size()-1;
      unsigned int lower_next = 2;
      unsigned int upper_next = vertList.size()-2;
      for (unsigned int i = 0; i < vertList.size()-2; ++i)
      {
         sglTriStruct<T>* tri = new sglTriStruct<T>;
         tri->v[0] = vertList[first];
         tri->v[1] = vertList[middle];
         tri->v[2] = vertList[last];
         addTriangleFace(tri);

         if (i%2 == 0)
         {
            first = last;
            last = lower_next++;
         }
         else
         {
            middle = last;
            last = upper_next--;
         }
      }
   }
   else
   {
      sglPrintInfo() << "sglTriStripper::addPolyFace() warning: "
                     << "ignoring degenerate face" << endl;
   }
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::computeFaceNormal(const sglVec3f &v0,
                                                 const sglVec3f &v1,
                                                 const sglVec3f &v2,
                                                 sglVec3f& normal)
{
   sglVec3f a, b;

   a.sub(v1, v0);
   b.sub(v2, v0);

   normal.cross(a, b);
   normal.normalize();
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::computeSmoothNormals(
    const sglVec3f* verts,
    unsigned int (*addNormal)(void*, sglVec3f&),
    void* passThrough)
{
   // ==============  Compute smooth normals  ==================
   // HACK slow and stupid!!
   if (T::hasNormals())
   {
      bool foundOne = false;
      for (list_iterator tri = m_trilist->begin(); 
           tri != m_trilist->end(); ++tri)
      {
         for (unsigned int i=0; i<3; ++i)
         {
            if ((*tri)->v[i].getNormal() == UINT_MAX)
            {
               if (foundOne == false)
               {
                  foundOne = true;
                  sglPrintInfo()
                     << "sglTriStripper: computing normals" << endl;
               }
               sglVec3f normal = sglVec3f(0,0,0);
               vector<T*> sameList;
               for (list_iterator tri2 = m_trilist->begin(); 
                    tri2 != m_trilist->end(); ++tri2)
               {
                  T* vert = (*tri2)->findSameLocation(&(*tri)->v[i]);
                  if (vert)
                  {
                     sameList.push_back(vert);
                     sglVec3f faceNormal;
                     computeFaceNormal(verts[(*tri2)->v[0].vi],
                                       verts[(*tri2)->v[1].vi],
                                       verts[(*tri2)->v[2].vi],
                                       faceNormal);
                     normal += faceNormal;
                  }
               }
               normal.normalize();
               unsigned int nindex = addNormal(passThrough, normal);
               for (typename vector<T*>::iterator v = sameList.begin();
                    v != sameList.end(); ++v)
               {
                  if ((*v)->getNormal() == UINT_MAX)
                      (*v)->setNormal(nindex);
               }
            }
         }
      }
   }
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::computeFacetedNormals(
    const sglVec3f* verts,
    unsigned int (*addNormal)(void*, sglVec3f&),
    void* passThrough)
{
   // ==============  Compute faceted normals  ==================
   if (T::hasNormals())
   {
      bool foundOne = false;
      for (list_iterator tri = m_trilist->begin(); 
           tri != m_trilist->end(); ++tri)
      {
         if ((*tri)->v[0].getNormal() == UINT_MAX ||
             (*tri)->v[1].getNormal() == UINT_MAX ||
             (*tri)->v[2].getNormal() == UINT_MAX)
         {
            if (foundOne == false)
            {
               foundOne = true;
               sglPrintInfo() << "sglTriStripper: computing normals" << endl;
            }
            sglVec3f faceNormal;
            computeFaceNormal(verts[(*tri)->v[0].vi],
                              verts[(*tri)->v[1].vi],
                              verts[(*tri)->v[2].vi],
                              faceNormal);
            //sglPrintDebug() << "normal = " << faceNormal << endl;
            unsigned int nindex = addNormal(passThrough, faceNormal);
            for (unsigned int i=0; i<3; ++i)
            {
               if ((*tri)->v[i].getNormal() == UINT_MAX)
                   (*tri)->v[i].setNormal(nindex);
            }
         }
      }
   }
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::triStripify( bool verbose )
{
   list_iterator tri;
   int i;

   if( verbose )
      sglPrintInfo() << "Number of input triangles: "
                  << m_num_triangles << endl;

   // =========== Eliminate vertex equivalent triangles ===============

   // initialize hash table for triangles
   sglHashTable< sglTriStruct<T> > *thash = 
       new sglHashTable< sglTriStruct<T> >((m_num_triangles/8)+1);

   for (tri = m_trilist->begin(); tri != m_trilist->end(); )
   {
      if (thash->search(*tri))
      {
         if( verbose )
            sglPrintInfo() << "sglTriStripper::triStripify(): removing "
                           << "duplicate tri " << *tri
                           << (*tri)->v[0].vi << (*tri)->v[1].vi 
                           << (*tri)->v[2].vi << endl;

         list_iterator todie = tri++;
         delete *todie;
         m_trilist->erase(todie);
      }
      else
      {
         thash->add(*tri);
         ++tri;
      }
   }
   delete thash;

   // ==============  Compute triangle adjacencies  ==================

   // initialize a hash table for edges
   sglHashTable< sglEdgeStruct<T> > *ehash = 
       new sglHashTable< sglEdgeStruct<T> >(m_num_triangles);
   sglEdgeStruct<T>* edges = new sglEdgeStruct<T>[3*m_num_triangles];
   sglEdgeStruct<T>* freeedge = edges;

   // add each edge of every triangle to hash table
   for (tri = m_trilist->begin(); tri != m_trilist->end(); ++tri)
   {
      freeedge->tri = tri; 
      freeedge->adjnumber = 0;
      ehash->add(freeedge++);
      freeedge->tri = tri; 
      freeedge->adjnumber = 1;
      ehash->add(freeedge++);
      freeedge->tri = tri; 
      freeedge->adjnumber = 2;
      ehash->add(freeedge++);
   }

   // for each triangle search the list for edges of other triangles
   for (tri = m_trilist->begin(); tri != m_trilist->end(); ++tri)
   {
      for (i=0; i<3; i++)
      {
         // skip this one if it has already been done
         if ((*tri)->adj[i] != 0)
         {
            continue;
         }

         sglEdgeStruct<T> nextedge;
         nextedge.tri = tri;
         nextedge.adjnumber = i;
         sglEdgeStruct<T> *edge = ehash->search(&nextedge);
         if (edge)
         {
            if (edge->tri == tri)
               edge = ehash->searchagain(&nextedge, edge);
            if (edge)
            {
               if ((*(edge->tri))->adj[edge->adjnumber] == NULL)
               {
                  (*tri)->adj[i] = edge->tri;
                  (*(edge->tri))->adj[edge->adjnumber] = tri;
               }
               else
               {
                  //sglPrintDebug() << "Why does this happen??" << endl;
               }
            }
         }
      }
   }

   delete[] edges;
   delete ehash;

#ifdef DEBUG
   // test adjacency pointers for consistency
   int j,k;

   for (tri = m_trilist->begin(); tri != m_trilist->end(); ++tri)
   {
      for (i = 0; i < 3; i++)
      {
         sglTriList<T>::iterator nexttri = (*tri)->adj[i];
         if (nexttri != 0)
         {
            k=0;
            for (j = 0; j < 3; j++)
            {
               if (tri == (*nexttri)->adj[j])
               {
                  k += 1;
               }
            }
            if (k != 1)
            {
               sglPrintWarning() << *tri << " ERROR: to " << *nexttri
                                 << " k = " << k << endl;;
               sglPrintWarning() << **tri;
               sglPrintWarning() << **nexttri;
            }
         }
      }
   }
#endif

   // compute adjacency statistics and add to the appropriate adjtrilist
   int count, adjcount[4] = {0,0,0,0};

   for (tri = m_trilist->begin(); tri != m_trilist->end();)
   {
      for (i=0, count=0; i<3; ++i)
      {
         if ((*tri)->adj[i] != 0)
         {
            count += 1;
         }
      }
      (*tri)->adjcount = count;
      adjcount[count] += 1;

      list_iterator lasttri = tri++;

      // move it from main list to appropriate adjtrilist
      m_adjtrilist[count]->splice(m_adjtrilist[count]->begin(),
                                  *m_trilist, lasttri);
   }

   if( verbose )
      sglPrintInfo() << "adjacencies: 0:" << adjcount[0]
                     << ", 1:" << adjcount[1]
                     << ", 2:" << adjcount[2]
                     << ", 3:" << adjcount[3] << endl;

// ============ search for connected triangles and output ==============
 
   // Don't meshify singular triangles just leave them in their list
   for (tri = m_adjtrilist[0]->begin(); tri != m_adjtrilist[0]->end(); ++tri)
   {
      (*tri)->used = true;
   }

   for (;;)
   {
      sglTriList<T> *oldlist;
      // choose a seed triangle with the minimum number of adjacencies
      if ((tri = m_adjtrilist[1]->begin()) != m_adjtrilist[1]->end())
      {
         oldlist = m_adjtrilist[1];
      }
      else if ((tri = m_adjtrilist[2]->begin()) != m_adjtrilist[2]->end())
      {
         oldlist = m_adjtrilist[2];
      }
      else if ((tri = m_adjtrilist[3]->begin()) != m_adjtrilist[3]->end())
      {
         oldlist = m_adjtrilist[3];
      }
      else
         break;

      // start a new list to hold the triangles that belong to this list
      sglTriList<T> *newtrilist = new sglTriList<T>();

      newtrilist->splice(newtrilist->begin(), *oldlist, tri);
      removeadjacencies(tri);  //remove this tri from adj ptrs of adjacent tris
      int tricount = 1;

      // extend in one direction using triangles with min adjacencies
      while ((tri = (*tri)->minadj()) != 0)
      {
         newtrilist->splice(newtrilist->begin(),
                            *(m_adjtrilist[(*tri)->adjcount]), tri);
         removeadjacencies(tri);
         tricount++;
      }

      // if seed has two or more adjacencies, extend in other direction
      // Big bug fix! - I had to fix this because code before did not do what
      // the previous comment says.
      tri = newtrilist->end();
      --tri;
      list_iterator nexttri = NULL;
      for (i=0; i<3; i++)
      {
         list_iterator prevtri = tri;
         --prevtri;
         if ((*tri)->adj[i] != 0 &&
             ((*tri)->adj[i] != prevtri) &&
             (!((*((*tri)->adj[i]))->used)))
         {
            nexttri = (*tri)->adj[i];
            break;
         }
      }

      for (tri = nexttri; tri != 0; tri = (*tri)->minadj())
      {
         newtrilist->splice(newtrilist->end(),
                            *(m_adjtrilist[(*tri)->adjcount]), tri);
         removeadjacencies(tri);
         tricount++;
      }

      sglPrintDebug() << "tricount=" << tricount << ", ";

      // output the resulting mesh
      if (tricount > 1)
      {
         createStrip(newtrilist);
      }
      if (!newtrilist->empty())
         sglPrintWarning()
            << "sglTriStripper logic error: newtrilist not empty" << endl;
      delete newtrilist;
   }

   // free unneeded trilists and move isolated triangles to m_trilist
   while (!m_donetrilist->empty())
   {
       tri = m_donetrilist->begin();
       delete *tri;
       m_donetrilist->erase(tri);
   }
   delete m_donetrilist;
   m_donetrilist = NULL;

   if (!m_adjtrilist[1]->empty())
      sglPrintWarning()
         << "sglTriStripper logic error: m_adjtrilist[1] not empty"
         << endl;
   delete m_adjtrilist[1];
   m_adjtrilist[1] = NULL;

   if (!m_adjtrilist[2]->empty())
      sglPrintWarning()
         << "sglTriStripper logic error: m_adjtrilist[2] not empty" << endl;
   delete m_adjtrilist[2];
   m_adjtrilist[2] = NULL;

   if (!m_adjtrilist[3]->empty())
      sglPrintWarning()
         << "sglTriStripper logic error: m_adjtrilist[3] not empty" << endl;
   delete m_adjtrilist[3];
   m_adjtrilist[3] = NULL;

   if (!m_trilist->empty())
      sglPrintWarning()
         << "sglTriStripper logic error: m_trilist not empty" << endl;
   delete m_trilist;

   m_trilist = m_adjtrilist[0];
   m_adjtrilist[0] = NULL;

   // recount the number of isolated triangles
   m_num_triangles = 0;
   for (tri = m_trilist->begin(); tri != m_trilist->end(); ++tri)
   {
      m_num_triangles++;
   }

   // Output the statistics
   if( verbose )
   {
      sglPrintInfo() << "Number of isolated triangles: "
                     << m_num_triangles << endl;
      sglPrintInfo() << "Number of stripped triangles: " 
                     << (m_strip_len - (2*m_strip.size())) - m_num_swaps
                     << endl;
      sglPrintInfo() << "Number of triangle strips: "
                     << m_strip.size() << endl;
      sglPrintInfo() << "Number of triangle swaps: " << m_num_swaps << endl;
      if (m_strip.size())
      {
         sglPrintInfo() << "Avg. strip length: "
                        << ((float) m_strip_len/(float) m_strip.size())
                        << endl;
      }
      sglPrintInfo() << "Total vertices to send to the pipe: " 
                     << m_strip_len + 3*m_num_triangles << endl;
   }
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::createStrip(sglTriList<T> *trilist)
{
   vector<T> *tristrip = new vector<T>();

   // ----------------------------------------------------------
   // build the list of vertices here
   T *vbuf[2];  // last two vertices pushed down the gfx pipeline
   list_iterator tri = trilist->begin();

//   sglPrintDebug() << **tri;

   // *** start output with vertex that is not in the second triangle
   list_iterator nexttri = tri;
   ++nexttri;
   T *vert = sglTriStruct<T>::notCommon(*tri, *nexttri);

   // get index of triangle
   int i;
   for (i=0; i<3; i++)
   {
      if (vert == &((*tri)->v[i]))
         break;
   }

   // bgntmesh();
   int vbuf_index = 0;

   // v3f(tri->v[i]);
   tristrip->push_back(*vert);
   vbuf[vbuf_index] = vert;
   vbuf_index = !vbuf_index;

   // v3f(tri->v[(i + 1) % 3]);
   tristrip->push_back((*tri)->v[(i + 1) % 3]);
   vbuf[vbuf_index] = &((*tri)->v[(i + 1) % 3]);
   vbuf_index = !vbuf_index;

   // v3f(tri->v[(i + 2) % 3]);
   tristrip->push_back((*tri)->v[(i + 2) % 3]);
   vbuf[vbuf_index] = &((*tri)->v[(i + 2) % 3]);
   vbuf_index = !vbuf_index;

   // *** find vertex of second triangle that is not in the first
   T *nextvert = sglTriStruct<T>::notCommon(*nexttri, *tri);

   // *** transfer triangle to done list
   m_donetrilist->splice(m_donetrilist->begin(), *trilist, tri);

   for (tri = nexttri++; nexttri != trilist->end(); tri = nexttri++)
   {
//      sglPrintDebug() << **tri;

      // *** check for errors
      if ((!(*tri)->isMember(vbuf[0])) || 
          (!(*tri)->isMember(vbuf[1])) ||
          (!(*tri)->isMember(nextvert)))
      {
         sglPrintWarning() << "ERROR 1 in mesh generation" << endl;
      }
      if ((vbuf[0]->vi == vbuf[1]->vi) || (vbuf[0]->vi == nextvert->vi))
      {
         sglPrintWarning() << "ERROR 2 in mesh generation" << endl;
      }
      // *** decide whether to swap or not
      if ((*nexttri)->isMember(vbuf[vbuf_index]))
      {
         //swaptmesh();
         tristrip->push_back(*(vbuf[vbuf_index]));
         vbuf_index = !vbuf_index;
         ++m_num_swaps;
      }

      // *** output the next vertex
      tristrip->push_back(*nextvert);
      //REPLACEVERT(nextvert);
      vbuf[vbuf_index] = nextvert;
      vbuf_index = !vbuf_index;

      // *** determine the next output vertex
      nextvert = sglTriStruct<T>::notCommon(*nexttri, *tri);

      // *** transfer tri to the done list
      m_donetrilist->splice(m_donetrilist->begin(), *trilist, tri);
   }

//   sglPrintDebug() << **tri;

   // *** output the last vertex
   tristrip->push_back(*nextvert);

   m_donetrilist->splice(m_donetrilist->begin(), *trilist, tri);
   
   // ----------------------------------------------------------
   // insert strip into list
   m_strip.push_back(tristrip);

   m_strip_len += tristrip->size();

   sglPrintDebug() << "Created strip with " << tristrip->size()
                   << " vertices (" << m_strip_len << ")" << endl;
}

//----------------------------------------------------------------------------
template <class T>
inline void sglTriStripper<T>::removeadjacencies(
   sglTriStripper<T>::list_iterator tri)
{
   int i, j;
   list_iterator adjtri;

   (*tri)->used = true;
   for (i = 0; i < 3; i++)
   {
      if ((adjtri = (*tri)->adj[i]) != 0)
      {
         for (j = 0; j < 3; j++)
         {
            if (tri == (*adjtri)->adj[j])
            {
               (*adjtri)->adj[j] = 0;
               break;
            }
         }
         (*adjtri)->adjcount -= 1;
         m_adjtrilist[(*adjtri)->adjcount]->splice(
             m_adjtrilist[(*adjtri)->adjcount]->begin(),
             *m_adjtrilist[(*adjtri)->adjcount+1], adjtri);
      }
   }
}

//----------------------------------------------------------------------------
template <class T>
inline vector<T> *sglTriStripper<T>::getStrip(unsigned int index)
{
   if (index < m_strip.size())
   {
      return m_strip[index];
   }
   return NULL;
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNTC>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *index_nlist,
    unsigned int *index_tlist,
    unsigned int *index_clist)
{
   sglTriList<sglVertStructVNTC>::iterator ii;
   sglTriList<sglVertStructVNTC>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVNTC* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_nlist[index]   = v[0].ni;
      index_tlist[index]   = v[0].ti;
      index_clist[index++] = v[0].ci;
      index_vlist[index]   = v[1].vi;
      index_nlist[index]   = v[1].ni;
      index_tlist[index]   = v[1].ti;
      index_clist[index++] = v[1].ci;
      index_vlist[index]   = v[2].vi;
      index_nlist[index]   = v[2].ni;
      index_tlist[index]   = v[2].ti;
      index_clist[index++] = v[2].ci;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNT>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *index_nlist,
    unsigned int *index_tlist,
    unsigned int *)
{
   sglTriList<sglVertStructVNT>::iterator ii;
   sglTriList<sglVertStructVNT>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVNT* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_nlist[index]   = v[0].ni;
      index_tlist[index++] = v[0].ti;
      index_vlist[index]   = v[1].vi;
      index_nlist[index]   = v[1].ni;
      index_tlist[index++] = v[1].ti;
      index_vlist[index]   = v[2].vi;
      index_nlist[index]   = v[2].ni;
      index_tlist[index++] = v[2].ti;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNC>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *index_nlist,
    unsigned int *,
    unsigned int *index_clist)
{
   sglTriList<sglVertStructVNC>::iterator ii;
   sglTriList<sglVertStructVNC>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVNC* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_nlist[index]   = v[0].ni;
      index_clist[index++] = v[0].ci;
      index_vlist[index]   = v[1].vi;
      index_nlist[index]   = v[1].ni;
      index_clist[index++] = v[1].ci;
      index_vlist[index]   = v[2].vi;
      index_nlist[index]   = v[2].ni;
      index_clist[index++] = v[2].ci;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVN>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *index_nlist,
    unsigned int *,
    unsigned int *)
{
   sglTriList<sglVertStructVN>::iterator ii;
   sglTriList<sglVertStructVN>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVN* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_nlist[index++] = v[0].ni;
      index_vlist[index]   = v[1].vi;
      index_nlist[index++] = v[1].ni;
      index_vlist[index]   = v[2].vi;
      index_nlist[index++] = v[2].ni;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVTC>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *,
    unsigned int *index_tlist,
    unsigned int *index_clist)
{
   sglTriList<sglVertStructVTC>::iterator ii;
   sglTriList<sglVertStructVTC>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVTC* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_tlist[index]   = v[0].ti;
      index_clist[index++] = v[0].ci;
      index_vlist[index]   = v[1].vi;
      index_tlist[index]   = v[1].ti;
      index_clist[index++] = v[1].ci;
      index_vlist[index]   = v[2].vi;
      index_tlist[index]   = v[2].ti;
      index_clist[index++] = v[2].ci;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVT>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *,
    unsigned int *index_tlist,
    unsigned int *)
{
   sglTriList<sglVertStructVT>::iterator ii;
   sglTriList<sglVertStructVT>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVT* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_tlist[index++] = v[0].ti;
      index_vlist[index]   = v[1].vi;
      index_tlist[index++] = v[1].ti;
      index_vlist[index]   = v[2].vi;
      index_tlist[index++] = v[2].ti;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVC>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *,
    unsigned int *,
    unsigned int *index_clist)
{
   sglTriList<sglVertStructVC>::iterator ii;
   sglTriList<sglVertStructVC>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructVC* v = (*ii)->v;
      index_vlist[index]   = v[0].vi;
      index_clist[index++] = v[0].ci;
      index_vlist[index]   = v[1].vi;
      index_clist[index++] = v[1].ci;
      index_vlist[index]   = v[2].vi;
      index_clist[index++] = v[2].ci;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructV>::copyTriangleIndexLists(
    unsigned int *index_vlist,
    unsigned int *,
    unsigned int *,
    unsigned int *)
{
   sglTriList<sglVertStructV>::iterator ii;
   sglTriList<sglVertStructV>::iterator end = m_trilist->end();
   unsigned int index = 0;

   for (ii = m_trilist->begin(); ii != end; ++ii)
   {
      sglVertStructV* v = (*ii)->v;
      index_vlist[index++] = v[0].vi;
      index_vlist[index++] = v[1].vi;
      index_vlist[index++] = v[2].vi;
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNTC>::copyStrip(unsigned int index,
                                                 unsigned int *index_vlist,
                                                 unsigned int *index_nlist,
                                                 unsigned int *index_tlist,
                                                 unsigned int *index_clist)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVNTC>::iterator k = m_strip[index]->begin();
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_nlist[ii] = k->ni;
         index_tlist[ii] = k->ti;
         index_clist[ii++] = k->ci;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNT>::copyStrip(unsigned int index,
                                                 unsigned int *index_vlist,
                                                 unsigned int *index_nlist,
                                                 unsigned int *index_tlist,
                                                 unsigned int *)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVNT>::iterator k = m_strip[index]->begin();
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_nlist[ii] = k->ni;
         index_tlist[ii++] = k->ti;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVNC>::copyStrip(unsigned int index,
                                                unsigned int *index_vlist,
                                                unsigned int *index_nlist,
                                                unsigned int *,
                                                unsigned int *index_clist)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVNC>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_nlist[ii] = k->ni;
         index_clist[ii++] = k->ci;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVN>::copyStrip(unsigned int index,
                                                unsigned int *index_vlist,
                                                unsigned int *index_nlist,
                                                unsigned int *,
                                                unsigned int *)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVN>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_nlist[ii++] = k->ni;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVTC>::copyStrip(unsigned int index,
                                                unsigned int *index_vlist,
                                                unsigned int *,
                                                unsigned int *index_tlist,
                                                unsigned int *index_clist)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVTC>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_tlist[ii] = k->ti;
         index_clist[ii++] = k->ci;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVT>::copyStrip(unsigned int index,
                                                unsigned int *index_vlist,
                                                unsigned int *,
                                                unsigned int *index_tlist,
                                                unsigned int *)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVT>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_tlist[ii++] = k->ti;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructVC>::copyStrip(unsigned int index,
                                               unsigned int *index_vlist,
                                               unsigned int *,
                                               unsigned int *,
                                               unsigned int *index_clist)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructVC>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii] = k->vi;
         index_clist[ii++] = k->ci;
      }
   }
}

//----------------------------------------------------------------------------
template <>
inline void sglTriStripper<sglVertStructV>::copyStrip(unsigned int index,
                                               unsigned int *index_vlist,
                                               unsigned int *,
                                               unsigned int *,
                                               unsigned int *)
{
   if (index < m_strip.size())
   {
      unsigned int ii = 0;
      for (vector<sglVertStructV>::iterator k = m_strip[index]->begin(); 
           k != m_strip[index]->end(); ++k)
      {
         index_vlist[ii++] = k->vi;
      }
   }
}

#endif

---