Fix line endings. WHAMMY.

1 files changed, 930 insertions, 930 deletions

diff --git a/mp/src/utils/common/mstristrip.cpp b/mp/src/utils/common/mstristrip.cpp
index 9e611f94..ad6ebdc8 100644
--- a/mp/src/utils/common/mstristrip.cpp
+++ b/mp/src/utils/common/mstristrip.cpp
@@ -1,930 +1,930 @@
-//========= 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) const

-    {

-        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;

-}

-

+//========= 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) const
+    {
+        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;
+}
+