---

sglLineStripper.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: sglLineStripper.hpp
 *   Author: Tom Stimson
 *  Created: 9 September 1999
 *  Summary: strip line segments together
 *****************************************************************************/

#ifndef __SGL_LINE_STRIPPER_HPP
#define __SGL_LINE_STRIPPER_HPP

#include <sgldb.h>
#include <deque>
#include <list>
#include <vector>
#include <sglHashTable.hpp>
#include <sglOStream.hpp>


template <class T>
class SGLDB_DLL_API sglLineStripper
{
public:
   sglLineStripper();
   ~sglLineStripper();

   void addSegment(const T& end1, const T& end2);

   void lineStripify();

   void reset();

   unsigned int getNumSegments() {return m_segment;}

   unsigned int getNumStrips() {return m_strips.size();}

   const deque<T>& getStrip(unsigned int indx) {return *(m_strips[indx]);}

private:
   // not implemented
   sglLineStripper(const sglLineStripper &);
   const sglLineStripper &operator=(const sglLineStripper &);


   class segment
   {
   public:
      segment(T end1, T end2, bool used) :
            m_end1(end1), m_end2(end2), m_used(used) {};
      ~segment() {};
   public:
      T    m_end1;
      T    m_end2;
      bool m_used;
   };
   class segmentEnd
   {
   public:
      T                          m_v;

      typename list< segment >::iterator  m_seg;

      int hash(unsigned int hashsize)
         {
            int val = m_v.hash();
            val = val & 0x7fffffff;
            return val % hashsize;
         }

      bool isEqual(segmentEnd *rhs)
         {
            return m_v == rhs->m_v && !(rhs->m_seg->m_used);
         }
   };
   friend class segmentEnd;

private:
   unsigned int         m_num_segments;
   list<segment>        m_segments;
   vector< deque<T>* >  m_strips;
   unsigned int         m_strip_len;
};

//----------------------------------------------------------------------------

template <class T>
inline 
sglLineStripper<T>::sglLineStripper() :
      m_num_segments(0),
      m_strip_len(0)
{
}

//----------------------------------------------------------------------------

template <class T>
inline 
sglLineStripper<T>::~sglLineStripper()
{
   reset();
}

//----------------------------------------------------------------------------

template <class T>
inline 
void sglLineStripper<T>::reset()
{
   while (!m_strips.empty())
   {
      deque<T>* strip = m_strips.back();
      delete strip;
      m_strips.pop_back();
   }
   if (!m_segments.empty())
   {
      m_segments.erase(m_segments.begin(), m_segments.end());
   }
   m_num_segments = 0;
   m_strip_len = 0;
}

//----------------------------------------------------------------------------

template <class T>
inline 
void sglLineStripper<T>::addSegment(const T& end1, const T& end2)
{
   m_segments.push_back(segment(end1, end2, false));
   ++m_num_segments;
}

//----------------------------------------------------------------------------

template <class T>
inline 
void sglLineStripper<T>::lineStripify()
{
   sglHashTable<segmentEnd> segHash(m_num_segments/2);
   segmentEnd* ends = new segmentEnd[m_num_segments*2];
   segmentEnd* nextEnd = ends;
   for (typename list<segment>::iterator ii = m_segments.begin();
        ii != m_segments.end(); ++ii)
   {
      nextEnd->m_v = ii->m_end1;
      nextEnd->m_seg = ii;
      segHash.add(nextEnd++);
      nextEnd->m_v = ii->m_end2;
      nextEnd->m_seg = ii;
      segHash.add(nextEnd++);
   }

   segmentEnd* lastEnd = nextEnd;
   for (nextEnd = ends; nextEnd != lastEnd; ++nextEnd)
   {
      if (!(nextEnd->m_seg->m_used))
      {
         deque<T> *tmpList = new deque<T>();
         tmpList->push_back(nextEnd->m_seg->m_end1);
         tmpList->push_back(nextEnd->m_seg->m_end2);
         nextEnd->m_seg->m_used = true;

         for(;;)
         {
            segmentEnd first;
            first.m_v = tmpList->front();
            first.m_seg = 0;
            segmentEnd* match = segHash.search(&first);
            if (match)
            {
               if (match->m_seg->m_end1 == first.m_v)
                  tmpList->push_front(match->m_seg->m_end2);
               else
                  tmpList->push_front(match->m_seg->m_end1);
               match->m_seg->m_used = true;
            }
            else
            {
               break;
            }
         }
         for(;;)
         {
            segmentEnd second;
            second.m_v = tmpList->back();
            second.m_seg = 0;
            segmentEnd* match = segHash.search(&second);
            if (match)
            {
               if (match->m_seg->m_end1 == second.m_v)
                  tmpList->push_back(match->m_seg->m_end2);
               else
                  tmpList->push_back(match->m_seg->m_end1);
               match->m_seg->m_used = true;
            }
            else
            {
               break;
            }
         }

         m_strips.push_back(tmpList);
         m_strip_len += tmpList->size();
      }
   }

   delete[] ends;

   sglPrintInfo() << "sglLineStripper: Number of input segments = " 
                  << m_num_segments << endl;
   sglPrintInfo() << "sglLineStripper: Number of line strips =    "
                  << m_strips.size() << endl;
   sglPrintInfo() << "sglLineStripper: Avg. strip length =        " 
                  << ((float) m_strip_len/(float) m_strips.size())
                  << endl;
   sglPrintInfo() << "sglLineStripper: Total vertices to "
      "send to the pipe = " << m_strip_len << endl;
}


#endif

---