tf2/tf2_src/utils/common/mstristrip.cpp

//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose: 
//
// $NoKeywords: $
//
//=============================================================================//
//-----------------------------------------------------------------------------
// FILE: TRISTRIP.CPP
//
// Desc: Xbox tristripper
//
// Copyright (c) 1999-2000 Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------

// identifier was truncated to '255' characters in the debug information
#pragma warning(disable: 4786)
// conversion from 'double' to 'float'
#pragma warning(disable: 4244)
#pragma warning(disable: 4530)

#include <stdio.h>
#include <stdarg.h>
#include <algorithm>
#include <list>
#include <vector>

#include <assert.h>
#ifdef _DEBUG
#include <crtdbg.h>
#endif

#include "mstristrip.h"

using namespace std;

//=========================================================================
// structs
//=========================================================================
typedef vector<WORD> STRIPVERTS;
typedef list<STRIPVERTS *> STRIPLIST;
typedef WORD (*TRIANGLELIST)[3];

struct TRIANGLEINFO
{
    int neighbortri[3];
    int neighboredge[3];
};

// return true if strip starts clockwise
inline bool FIsStripCW(const STRIPVERTS &stripvertices)
{
    // last index should have cw/ccw bool
    return !!stripvertices[stripvertices.size() - 1];
}

// return length of strip
inline int StripLen(const STRIPVERTS &stripvertices)
{
    return (int)stripvertices.size() - 1;
}

// free all stripverts and clear the striplist
inline void FreeStripListVerts(STRIPLIST *pstriplist)
{
    STRIPLIST::iterator istriplist = pstriplist->begin();
    while(istriplist != pstriplist->end())
    {
        STRIPVERTS *pstripverts = *istriplist;
        delete pstripverts;
        pstriplist->erase(istriplist++);
    }
}

//=========================================================================
// main stripper class
//=========================================================================
class CStripper
{
public:
    // ctors/dtors
    CStripper(int numtris, TRIANGLELIST ptriangles);
    ~CStripper();

    // initialize tri info
    void InitTriangleInfo(int tri, int vert);

    // get maximum length strip from tri/vert
    int CreateStrip(int tri, int vert, int maxlen, int *pswaps,
        bool flookahead, bool fstartcw, int *pstriptris, int *pstripverts);

    // stripify entire mesh
    void BuildStrips(STRIPLIST *pstriplist, int maxlen, bool flookahead);

    // blast strip indices to ppstripindices
    int CreateManyStrips(STRIPLIST *pstriplist, WORD **ppstripindices);
    int CreateLongStrip(STRIPLIST *pstriplist, WORD **ppstripindices);

    inline int GetNeighborCount(int tri)
    {
        int count = 0;
        for(int vert = 0; vert < 3; vert++)
        {
            int neighbortri = m_ptriinfo[tri].neighbortri[vert];
            count += (neighbortri != -1) && !m_pused[neighbortri];
        }
        return count;
    }

    // from callee
    int m_numtris;              // # tris
    TRIANGLELIST m_ptriangles;  // trilist

    TRIANGLEINFO *m_ptriinfo;   // tri edge, neighbor info
    int *m_pused;               // tri used flag
};

//=========================================================================
// vertex cache class
//=========================================================================
class CVertCache
{
public:
    CVertCache()
        { Reset(); }
    ~CVertCache()
        {};

    // reset cache
    void Reset()
    {
        m_iCachePtr = 0;
        m_cachehits = 0;
        memset(m_rgCache, 0xff, sizeof(m_rgCache));
    }

    // add vertindex to cache
    bool Add(int strip, int vertindex);

    int NumCacheHits() const
        { return m_cachehits; }

//    enum { CACHE_SIZE = 10 };
    enum { CACHE_SIZE = 18 };

private:
    int m_cachehits;                // current # of cache hits
    WORD m_rgCache[CACHE_SIZE];     // vertex cache
    int m_rgCacheStrip[CACHE_SIZE]; // strip # which added vert
    int m_iCachePtr;                // fifo ptr
};

//=========================================================================
// Get maximum length of strip starting at tri/vert
//=========================================================================
int CStripper::CreateStrip(int tri, int vert, int maxlen, int *pswaps,
    bool flookahead, bool fstartcw, int *pstriptris, int *pstripverts)
{
    *pswaps = 0;

    // this guy has already been used?
    if(m_pused[tri])
        return 0;

    // mark tri as used
    m_pused[tri] = 1;

    int swaps = 0;

    // add first tri info
    pstriptris[0] = tri;
    pstriptris[1] = tri;
    pstriptris[2] = tri;

    if(fstartcw)
    {
        pstripverts[0] = (vert) % 3;
        pstripverts[1] = (vert + 1) % 3;
        pstripverts[2] = (vert + 2) % 3;
    }
    else
    {
        pstripverts[0] = (vert + 1) % 3;
        pstripverts[1] = (vert + 0) % 3;
        pstripverts[2] = (vert + 2) % 3;
    }
    fstartcw = !fstartcw;

    // get next tri information
    int edge = (fstartcw ? vert + 2 : vert + 1) % 3;
    int nexttri = m_ptriinfo[tri].neighbortri[edge];
    int nextvert = m_ptriinfo[tri].neighboredge[edge];

    // start building the strip until we run out of room or indices
	int stripcount;
    for( stripcount = 3; stripcount < maxlen; stripcount++)
    {
        // dead end?
        if(nexttri == -1 || m_pused[nexttri])
            break;

        // move to next tri
        tri = nexttri;
        vert = nextvert;

        // toggle orientation
        fstartcw = !fstartcw;

        // find the next natural edge
        int edge = (fstartcw ? vert + 2 : vert + 1) % 3;
        nexttri = m_ptriinfo[tri].neighbortri[edge];
        nextvert = m_ptriinfo[tri].neighboredge[edge];

        bool fswap = false;
        if(nexttri == -1 || m_pused[nexttri])
        {
            // if the next tri is a dead end - try swapping orientation
            fswap = true;
        }
        else if(flookahead)
        {
            // try a swap and see who our new neighbor would be
            int edgeswap = (fstartcw ? vert + 1 : vert + 2) % 3;
            int nexttriswap = m_ptriinfo[tri].neighbortri[edgeswap];
            int nextvertswap = m_ptriinfo[tri].neighboredge[edgeswap];

            if(nexttriswap != -1 && !m_pused[nexttriswap])
            {
                assert(nexttri != -1);

                // if the swap neighbor has a lower count, change directions
                if(GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri))
                {
                    fswap = true;
                }
                else if(GetNeighborCount(nexttriswap) == GetNeighborCount(nexttri))
                {
                    // if they have the same number of neighbors - check their neighbors
                    edgeswap = (fstartcw ? nextvertswap + 2 : nextvertswap + 1) % 3;
                    nexttriswap = m_ptriinfo[nexttriswap].neighbortri[edgeswap];

                    int edge1 = (fstartcw ? nextvert + 1 : nextvert + 2) % 3;
                    int nexttri1 = m_ptriinfo[nexttri].neighbortri[edge1];

                    if(nexttri1 == -1 || m_pused[nexttri1])
                    {
                        // natural winding order leads us to a dead end so turn
                        fswap = true;
                    }
                    else if(nexttriswap != -1 && !m_pused[nexttriswap])
                    {
                        // check neighbor counts on both directions and swap if it's better
                        if(GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri1))
                            fswap = true;
                    }
                }
            }
        }

        if(fswap)
        {
            // we've been told to change directions so make sure we actually can
            // and then add the swap vertex
            int edgeswap = (fstartcw ? vert + 1 : vert + 2) % 3;
            nexttri = m_ptriinfo[tri].neighbortri[edgeswap];
            nextvert = m_ptriinfo[tri].neighboredge[edgeswap];

            if(nexttri != -1 && !m_pused[nexttri])
            {
                pstriptris[stripcount] = pstriptris[stripcount - 2];
                pstripverts[stripcount] = pstripverts[stripcount - 2];
                stripcount++;
                swaps++;
                fstartcw = !fstartcw;
            }
        }

        // record index information
        pstriptris[stripcount] = tri;
        pstripverts[stripcount] = (vert + 2) % 3;

        // mark triangle as used
        m_pused[tri] = 1;
    }

    // clear the used flags
    for(int j = 2; j < stripcount; j++)
        m_pused[pstriptris[j]] = 0;

    // return swap count and striplen
    *pswaps = swaps;
    return stripcount;
}

//=========================================================================
// Given a striplist and current cache state, pick the best next strip
//=========================================================================
STRIPLIST::iterator FindBestCachedStrip(STRIPLIST *pstriplist,
    const CVertCache &vertcachestate)
{
    if(pstriplist->empty())
		return pstriplist->end();

    bool fFlipStrip = false;
    int maxcachehits = -1;
    STRIPLIST::iterator istriplistbest = pstriplist->begin();

    int striplen = StripLen(**istriplistbest);
    bool fstartcw = FIsStripCW(**istriplistbest);

    // go through all the other strips looking for the best caching
    for(STRIPLIST::iterator istriplist = pstriplist->begin();
        istriplist != pstriplist->end();
        ++istriplist)
    {
        bool fFlip = false;
        const STRIPVERTS &stripverts = **istriplist;
        int striplennew = StripLen(stripverts);

        // check cache if this strip is the same type as us (ie: cw/odd)
        if((FIsStripCW(stripverts) == fstartcw) &&
            ((striplen & 0x1) == (striplennew & 0x1)))
        {
            // copy current state of cache
            CVertCache vertcachenew = vertcachestate;

            // figure out what this guy would do to our cache
            for(int ivert = 0; ivert < striplennew; ivert++)
                vertcachenew.Add(2, stripverts[ivert]);

            // even length strip - see if better cache hits reversed
            if(!(striplennew & 0x1))
            {
                CVertCache vertcacheflipped = vertcachestate;

                for(int ivert = StripLen(stripverts) - 1; ivert >= 0; ivert--)
                    vertcacheflipped.Add(2, stripverts[ivert]);

                if(vertcacheflipped.NumCacheHits() > vertcachenew.NumCacheHits())
                {
                    vertcachenew = vertcacheflipped;
                    fFlip = true;
                }
            }

            // record the best number of cache hits to date
            int numcachehits = vertcachenew.NumCacheHits() - vertcachestate.NumCacheHits();
            if(numcachehits > maxcachehits)
            {
                maxcachehits = numcachehits;
                istriplistbest = istriplist;
                fFlipStrip = fFlip;
            }
        }
    }

    if(fFlipStrip)
    {
        STRIPVERTS &stripverts = **istriplistbest;
        STRIPVERTS::iterator vend = stripverts.end();
        
        reverse(stripverts.begin(), --vend);
    }

    // make sure we keep the list in order and always pull off
    // the first dude.
    if(istriplistbest != pstriplist->begin())
        swap(*istriplistbest, *pstriplist->begin());

    return pstriplist->begin();
}


//=========================================================================
// Don't merge the strips - just blast em into the stripbuffer one by one
// (useful for debugging)
//=========================================================================
int CStripper::CreateManyStrips(STRIPLIST *pstriplist, WORD **ppstripindices)
{
    // allow room for each of the strips size plus the final 0
    int indexcount = (int)pstriplist->size() + 1;

    // we're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
	STRIPLIST::iterator istriplist;
    for( istriplist = pstriplist->begin(); istriplist != pstriplist->end(); ++istriplist)
    {
        // add striplength plus potential degenerate to swap ccw --> cw
        indexcount += StripLen(**istriplist) + 1;
    }

    // alloc the space for all this stuff
    WORD *pstripindices = new WORD [indexcount];
    assert(pstripindices);

    CVertCache vertcache;
    int numstripindices = 0;

    for(istriplist = pstriplist->begin();
        !pstriplist->empty();
        istriplist = FindBestCachedStrip(pstriplist, vertcache))
    {
        const STRIPVERTS &stripverts = **istriplist;

        if(!FIsStripCW(stripverts))
        {
            // add an extra index if it's ccw
            pstripindices[numstripindices++] = StripLen(stripverts) + 1;
            pstripindices[numstripindices++] = stripverts[0];
        }
        else
        {
            // add the strip length
            pstripindices[numstripindices++] = StripLen(stripverts);
        }

        // add all the strip indices
        for(int i = 0; i < StripLen(stripverts); i++)
        {
            pstripindices[numstripindices++] = stripverts[i];
            vertcache.Add(1, stripverts[i]);
        }

        // free this guy and pop him off the list
        delete &stripverts;
        pstriplist->pop_front();
    }

    // add terminating zero
    pstripindices[numstripindices++] = 0;
    *ppstripindices = pstripindices;

    return numstripindices;
}

//=========================================================================
// Merge striplist into one big uberlist with (hopefully) optimal caching
//=========================================================================
int CStripper::CreateLongStrip(STRIPLIST *pstriplist, WORD **ppstripindices)
{
    // allow room for one strip length plus a possible 3 extra indices per
    // concatenated strip list plus the final 0
    int indexcount = ((int)pstriplist->size() * 3) + 2;

    // we're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
	STRIPLIST::iterator istriplist;
    for( istriplist = pstriplist->begin(); istriplist != pstriplist->end(); ++istriplist)
    {
        indexcount += StripLen(**istriplist);
    }

    // alloc the space for all this stuff
    WORD *pstripindices = new WORD [indexcount];
    assert(pstripindices);

    CVertCache vertcache;
    int numstripindices = 0;

    // add first strip
    istriplist = pstriplist->begin();
    const STRIPVERTS &stripverts = **istriplist;

    // first strip should be cw
    assert(FIsStripCW(stripverts));

    for(int ivert = 0; ivert < StripLen(stripverts); ivert++)
    {
        pstripindices[numstripindices++] = stripverts[ivert];
        vertcache.Add(1, stripverts[ivert]);
    }

    // kill first dude
    delete &stripverts;
    pstriplist->erase(istriplist);

    // add all the others
    while(pstriplist->size())
    {
        istriplist = FindBestCachedStrip(pstriplist, vertcache);
        STRIPVERTS &stripverts = **istriplist;
        short lastvert = pstripindices[numstripindices - 1];
        short firstvert = stripverts[0];

        if(firstvert != lastvert)
        {
            // add degenerate from last strip
            pstripindices[numstripindices++] = lastvert;

            // add degenerate from our strip
            pstripindices[numstripindices++] = firstvert;
        }

        // if we're not orientated correctly, we need to add a degenerate
        if(FIsStripCW(stripverts) != !(numstripindices & 0x1))
        {
            // This shouldn't happen - we're currently trying very hard
            // to keep everything oriented correctly.
            assert(false);
            pstripindices[numstripindices++] = firstvert;
        }

        // add these verts
        for(int ivert = 0; ivert < StripLen(stripverts); ivert++)
        {
            pstripindices[numstripindices++] = stripverts[ivert];
            vertcache.Add(1, stripverts[ivert]);
        }

        // free these guys
        delete &stripverts;
        pstriplist->erase(istriplist);
    }

    *ppstripindices = pstripindices;
    return numstripindices;
}

//=========================================================================
// Build a (hopefully) optimal set of strips from a trilist
//=========================================================================
void CStripper::BuildStrips(STRIPLIST *pstriplist, int maxlen, bool flookahead)
{
    // temp indices storage
    const int ctmpverts = 1024;
    int pstripverts[ctmpverts + 1];
    int pstriptris[ctmpverts + 1];

    assert(maxlen <= ctmpverts);

    // clear all the used flags for the tris
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);

    bool fstartcw = true;
    for(;;)
    {
        int besttri = 0;
        int bestvert = 0;
        float bestratio = 2.0f;
        int bestneighborcount = INT_MAX;

		int tri;
        for( tri = 0; tri < m_numtris; tri++)
        {
            // if used the continue
            if(m_pused[tri])
                continue;

            // get the neighbor count
            int curneightborcount = GetNeighborCount(tri);
            assert(curneightborcount >= 0 && curneightborcount <= 3);

            // push all the singletons to the very end
            if(!curneightborcount)
                curneightborcount = 4;

            // if this guy has more neighbors than the current best - bail
            if(curneightborcount > bestneighborcount)
                continue;

            // try starting the strip with each of this tris verts
            for(int vert = 0; vert < 3; vert++)
            {
                int swaps;
                int len = CreateStrip(tri, vert, maxlen, &swaps, flookahead,
                    fstartcw, pstriptris, pstripverts);
                assert(len);

                float ratio = (len == 3) ? 1.0f : (float)swaps / len;

                // check if this ratio is better than what we've already got for
                // this neighborcount
                if((curneightborcount < bestneighborcount) ||
                    ((curneightborcount == bestneighborcount) && (ratio < bestratio)))
                {
                    bestneighborcount = curneightborcount;

                    besttri = tri;
                    bestvert = vert;
                    bestratio = ratio;
                }

            }
        }

        // no strips found?
        if(bestneighborcount == INT_MAX)
            break;

        // recreate this strip
        int swaps;
        int len = CreateStrip(besttri, bestvert, maxlen,
            &swaps, flookahead, fstartcw, pstriptris, pstripverts);
        assert(len);

        // mark the tris on the best strip as used
        for(tri = 0; tri < len; tri++)
            m_pused[pstriptris[tri]] = 1;

        // create a new STRIPVERTS and stuff in the indices
        STRIPVERTS *pstripvertices = new STRIPVERTS(len + 1);
        assert(pstripvertices);

        // store orientation in first entry
        for(tri = 0; tri < len; tri++)
            (*pstripvertices)[tri] = m_ptriangles[pstriptris[tri]][pstripverts[tri]];
        (*pstripvertices)[len] = fstartcw;

        // store the STRIPVERTS
        pstriplist->push_back(pstripvertices);

        // if strip was odd - swap orientation
        if((len & 0x1))
            fstartcw = !fstartcw;
    }

#ifdef _DEBUG
    // make sure all tris are used
    for(int t = 0; t < m_numtris; t++)
        assert(m_pused[t]);
#endif
}

//=========================================================================
// Guesstimate on the total index count for this list of strips
//=========================================================================
int EstimateStripCost(STRIPLIST *pstriplist)
{
    int count = 0;

    for(STRIPLIST::iterator istriplist = pstriplist->begin();
        istriplist != pstriplist->end();
        ++istriplist)
    {
        // add count of indices
        count += StripLen(**istriplist);
    }

    // assume 2 indices per strip to tack all these guys together
    return count + ((int)pstriplist->size() - 1) * 2;
}

//=========================================================================
// Initialize triangle information (edges, #neighbors, etc.)
//=========================================================================
void CStripper::InitTriangleInfo(int tri, int vert)
{
    WORD *ptriverts = &m_ptriangles[tri + 1][0];
    int vert1 = m_ptriangles[tri][(vert + 1) % 3];
    int vert2 = m_ptriangles[tri][vert];

    for(int itri = tri + 1; itri < m_numtris; itri++, ptriverts += 3)
    {
        if(m_pused[itri] != 0x7)
        {
            for(int ivert = 0; ivert < 3; ivert++)
            {
                if((ptriverts[ivert] == vert1) &&
                    (ptriverts[(ivert + 1) % 3] == vert2))
                {
                    // add the triangle info
                    m_ptriinfo[tri].neighbortri[vert] = itri;
                    m_ptriinfo[tri].neighboredge[vert] = ivert;
                    m_pused[tri] |= (1 << vert);

                    m_ptriinfo[itri].neighbortri[ivert] = tri;
                    m_ptriinfo[itri].neighboredge[ivert] = vert;
                    m_pused[itri] |= (1 << ivert);
                    return;
                }
            }
        }
    }
}

//=========================================================================
// CStripper ctor
//=========================================================================
CStripper::CStripper(int numtris, TRIANGLELIST ptriangles)
{
    // store trilist info
    m_numtris = numtris;
    m_ptriangles = ptriangles;

    m_pused = new int[numtris];
    assert(m_pused);
    m_ptriinfo = new TRIANGLEINFO[numtris];
    assert(m_ptriinfo);

    // init triinfo
	int itri;
    for( itri = 0; itri < numtris; itri++)
    {
        m_ptriinfo[itri].neighbortri[0] = -1;
        m_ptriinfo[itri].neighbortri[1] = -1;
        m_ptriinfo[itri].neighbortri[2] = -1;
    }

    // clear the used flag
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);

    // go through all the triangles and find edges, neighbor counts
    for(itri = 0; itri < numtris; itri++)
    {
        for(int ivert = 0; ivert < 3; ivert++)
        {
            if(!(m_pused[itri] & (1 << ivert)))
                InitTriangleInfo(itri, ivert);
        }
    }

    // clear the used flags from InitTriangleInfo
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);
}

//=========================================================================
// CStripper dtor
//=========================================================================
CStripper::~CStripper()
{
    // free stuff
    delete [] m_pused;
    m_pused = NULL;

    delete [] m_ptriinfo;
    m_ptriinfo = NULL;
}

//=========================================================================
// Add an index to the cache - returns true if it was added, false otherwise
//=========================================================================
bool CVertCache::Add(int strip, int vertindex)
{
    // find index in cache
    for(int iCache = 0; iCache < CACHE_SIZE; iCache++)
    {
        if(vertindex == m_rgCache[iCache])
        {
            // if it's in the cache and it's from a different strip
            // change the strip to the new one and count the cache hit
            if(strip != m_rgCacheStrip[iCache])
            {
                m_cachehits++;
                m_rgCacheStrip[iCache] = strip;
                return true;
            }

            // we added this item to the cache earlier - carry on
            return false;
        }
    }

    // not in cache, add vert and strip
    m_rgCache[m_iCachePtr] = vertindex;
    m_rgCacheStrip[m_iCachePtr] = strip;
    m_iCachePtr = (m_iCachePtr + 1) % CACHE_SIZE;
    return true;
}

#ifdef _DEBUG
//=========================================================================
// Turn on c runtime leak checking, etc.
//=========================================================================
void EnableLeakChecking()
{
    int flCrtDbgFlags = _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG);

    flCrtDbgFlags &=
        ~(_CRTDBG_LEAK_CHECK_DF |
        _CRTDBG_CHECK_ALWAYS_DF |
        _CRTDBG_DELAY_FREE_MEM_DF);

    // always check for memory leaks
    flCrtDbgFlags |= _CRTDBG_LEAK_CHECK_DF;

    // others you may / may not want to set
    flCrtDbgFlags |= _CRTDBG_CHECK_ALWAYS_DF;
    flCrtDbgFlags |= _CRTDBG_DELAY_FREE_MEM_DF;

    _CrtSetDbgFlag(flCrtDbgFlags);

    // all types of reports go via OutputDebugString
    _CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_DEBUG);
    _CrtSetReportMode(_CRT_ERROR, _CRTDBG_MODE_DEBUG);
    _CrtSetReportMode(_CRT_ASSERT, _CRTDBG_MODE_DEBUG);

    // big errors and asserts get their own assert window
    _CrtSetReportMode(_CRT_ERROR, _CRTDBG_MODE_WNDW);
    _CrtSetReportMode(_CRT_ASSERT, _CRTDBG_MODE_WNDW);

    // _CrtSetBreakAlloc(0);
}
#endif

//=========================================================================
// Main Stripify routine
//=========================================================================
int Stripify(int numtris, WORD *ptriangles, int *pnumindices, WORD **ppstripindices)
{
    if(!numtris || !ptriangles)
        return 0;

#ifdef _DEBUG
//    EnableLeakChecking();
#endif

    CStripper stripper(numtris, (TRIANGLELIST)ptriangles);

    // map of various args to try stripifying mesh with
    struct ARGMAP
    {
        int     maxlen;         // maximum length of strips
        bool    flookahead;     // use sgi greedy lookahead (or not)
    } rgargmap[] =
    {
        { 1024,  true  },
        { 1024,  false },
    };
    static const int cargmaps = sizeof(rgargmap) / sizeof(rgargmap[0]);
    STRIPLIST   striplistbest;
    int         bestlistcost = 0;

    for(int imap = 0; imap < cargmaps; imap++)
    {
        STRIPLIST striplist;

        // build the strip with the various args
        stripper.BuildStrips(&striplist, rgargmap[imap].maxlen,
            rgargmap[imap].flookahead);

        // guesstimate the list cost and store it if it's good
        int listcost = EstimateStripCost(&striplist);
        if(!bestlistcost || (listcost < bestlistcost))
        {
            // free the old best list
            FreeStripListVerts(&striplistbest);

            // store the new best list
            striplistbest = striplist;
            bestlistcost = listcost;
            assert(bestlistcost > 0);
        }
        else
        {
            FreeStripListVerts(&striplist);
        }
    }

#ifdef NEVER
    // Return the strips in [size1 i1 i2 i3][size2 i4 i5 i6]...[0] format
    // Very useful for debugging...
    return stripper.CreateManyStrips(&striplistbest, ppstripindices);
#endif // NEVER

    // return one big long strip
    int numindices = stripper.CreateLongStrip(&striplistbest, ppstripindices);

    if(pnumindices)
        *pnumindices = numindices;
    return numindices;
}

//=========================================================================
// Class used to vertices for locality of access.
//=========================================================================
struct SortEntry
{
public:
    int iFirstUsed;
    int iOrigIndex;

    bool operator<(const SortEntry& rhs)
    {
        return iFirstUsed < rhs.iFirstUsed;
    }
};

//=========================================================================
// Reorder the vertices
//=========================================================================
void ComputeVertexPermutation(int numstripindices, WORD* pstripindices,
                              int* pnumverts, WORD** ppvertexpermutation)
{
    // Sort verts to maximize locality.
    SortEntry* pSortTable = new SortEntry[*pnumverts];

    // Fill in original index.
	int i;
    for( i = 0; i < *pnumverts; i++)
    {
        pSortTable[i].iOrigIndex = i;
        pSortTable[i].iFirstUsed = -1;
    }

    // Fill in first used flag.
    for(i = 0; i < numstripindices; i++)
    {
        int index = pstripindices[i];

        if(pSortTable[index].iFirstUsed == -1)
            pSortTable[index].iFirstUsed = i;
    }

    // Sort the table.
    sort(pSortTable, pSortTable + *pnumverts);

    // Copy re-mapped to orignal vertex permutaion into output array.
    *ppvertexpermutation = new WORD[*pnumverts];

    for(i = 0; i < *pnumverts; i++)
    {
        (*ppvertexpermutation)[i] = pSortTable[i].iOrigIndex;
    }

    // Build original to re-mapped permutation.
    WORD* pInversePermutation = new WORD[numstripindices];

    for(i = 0; i < *pnumverts; i++)
    {
        pInversePermutation[pSortTable[i].iOrigIndex] = i;
    }

    // We need to remap indices as well.
    for(i = 0; i < numstripindices; i++)
    {
        pstripindices[i] = pInversePermutation[pstripindices[i]];
    }

    delete[] pSortTable;
    delete[] pInversePermutation;
}