From f56bb35301836e56582a575a75864392a0177875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20P=2E=20Tjern=C3=B8?= Date: Mon, 2 Dec 2013 19:31:46 -0800 Subject: Fix line endings. WHAMMY. --- mp/src/utils/common/mstristrip.cpp | 1860 ++++++++++++++++++------------------ 1 file changed, 930 insertions(+), 930 deletions(-) (limited to 'mp/src/utils/common/mstristrip.cpp') 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 -#include -#include -#include -#include - -#include -#ifdef _DEBUG -#include -#endif - -#include "mstristrip.h" - -using namespace std; - -//========================================================================= -// structs -//========================================================================= -typedef vector STRIPVERTS; -typedef list 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 +#include +#include +#include +#include + +#include +#ifdef _DEBUG +#include +#endif + +#include "mstristrip.h" + +using namespace std; + +//========================================================================= +// structs +//========================================================================= +typedef vector STRIPVERTS; +typedef list 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; +} + -- cgit v1.2.3