diff options
| author | Joe Ludwig <[email protected]> | 2013-06-26 15:22:04 -0700 |
|---|---|---|
| committer | Joe Ludwig <[email protected]> | 2013-06-26 15:22:04 -0700 |
| commit | 39ed87570bdb2f86969d4be821c94b722dc71179 (patch) | |
| tree | abc53757f75f40c80278e87650ea92808274aa59 /mp/src/utils/common/mstristrip.cpp | |
| download | source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.tar.xz source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.zip | |
First version of the SOurce SDK 2013
Diffstat (limited to 'mp/src/utils/common/mstristrip.cpp')
| -rw-r--r-- | mp/src/utils/common/mstristrip.cpp | 930 |
1 files changed, 930 insertions, 0 deletions
diff --git a/mp/src/utils/common/mstristrip.cpp b/mp/src/utils/common/mstristrip.cpp new file mode 100644 index 00000000..6a66de2f --- /dev/null +++ b/mp/src/utils/common/mstristrip.cpp @@ -0,0 +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)
+ {
+ 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;
+}
+
|